1 /* 2 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.beans; 27 28 import java.lang.ref.ReferenceQueue; 29 import java.lang.ref.WeakReference; 30 31 /** 32 * Hash table based mapping, which uses weak references to store keys 33 * and reference-equality in place of object-equality to compare them. 34 * An entry will automatically be removed when its key is no longer 35 * in ordinary use. Both null values and the null key are supported. 36 * This class does not require additional synchronization. 37 * A thread-safety is provided by a fragile combination 38 * of synchronized blocks and volatile fields. 39 * Be very careful during editing! 40 * 41 * @see java.util.IdentityHashMap 42 * @see java.util.WeakHashMap 43 */ 44 abstract class WeakIdentityMap<T> { 45 46 private static final int MAXIMUM_CAPACITY = 1 << 30; // it MUST be a power of two 47 private static final Object NULL = new Object(); // special object for null key 48 49 private final ReferenceQueue<Object> queue = new ReferenceQueue<Object>(); 50 51 private volatile Entry<T>[] table = newTable(1<<3); // table's length MUST be a power of two 52 private int threshold = 6; // the next size value at which to resize 53 private int size = 0; // the number of key-value mappings 54 get(Object key)55 public T get(Object key) { 56 removeStaleEntries(); 57 if (key == null) { 58 key = NULL; 59 } 60 int hash = key.hashCode(); 61 Entry<T>[] table = this.table; 62 // unsynchronized search improves performance 63 // the null value does not mean that there are no needed entry 64 int index = getIndex(table, hash); 65 for (Entry<T> entry = table[index]; entry != null; entry = entry.next) { 66 if (entry.isMatched(key, hash)) { 67 return entry.value; 68 } 69 } 70 synchronized (NULL) { 71 // synchronized search improves stability 72 // we must create and add new value if there are no needed entry 73 index = getIndex(this.table, hash); 74 for (Entry<T> entry = this.table[index]; entry != null; entry = entry.next) { 75 if (entry.isMatched(key, hash)) { 76 return entry.value; 77 } 78 } 79 T value = create(key); 80 this.table[index] = new Entry<T>(key, hash, value, this.queue, this.table[index]); 81 if (++this.size >= this.threshold) { 82 if (this.table.length == MAXIMUM_CAPACITY) { 83 this.threshold = Integer.MAX_VALUE; 84 } 85 else { 86 removeStaleEntries(); 87 table = newTable(this.table.length * 2); 88 transfer(this.table, table); 89 // If ignoring null elements and processing ref queue caused massive 90 // shrinkage, then restore old table. This should be rare, but avoids 91 // unbounded expansion of garbage-filled tables. 92 if (this.size >= this.threshold / 2) { 93 this.table = table; 94 this.threshold *= 2; 95 } 96 else { 97 transfer(table, this.table); 98 } 99 } 100 } 101 return value; 102 } 103 } 104 create(Object key)105 protected abstract T create(Object key); 106 removeStaleEntries()107 private void removeStaleEntries() { 108 Object ref = this.queue.poll(); 109 if (ref != null) { 110 synchronized (NULL) { 111 do { 112 @SuppressWarnings("unchecked") 113 Entry<T> entry = (Entry<T>) ref; 114 int index = getIndex(this.table, entry.hash); 115 116 Entry<T> prev = this.table[index]; 117 Entry<T> current = prev; 118 while (current != null) { 119 Entry<T> next = current.next; 120 if (current == entry) { 121 if (prev == entry) { 122 this.table[index] = next; 123 } 124 else { 125 prev.next = next; 126 } 127 entry.value = null; // Help GC 128 entry.next = null; // Help GC 129 this.size--; 130 break; 131 } 132 prev = current; 133 current = next; 134 } 135 ref = this.queue.poll(); 136 } 137 while (ref != null); 138 } 139 } 140 } 141 transfer(Entry<T>[] oldTable, Entry<T>[] newTable)142 private void transfer(Entry<T>[] oldTable, Entry<T>[] newTable) { 143 for (int i = 0; i < oldTable.length; i++) { 144 Entry<T> entry = oldTable[i]; 145 oldTable[i] = null; 146 while (entry != null) { 147 Entry<T> next = entry.next; 148 Object key = entry.get(); 149 if (key == null) { 150 entry.value = null; // Help GC 151 entry.next = null; // Help GC 152 this.size--; 153 } 154 else { 155 int index = getIndex(newTable, entry.hash); 156 entry.next = newTable[index]; 157 newTable[index] = entry; 158 } 159 entry = next; 160 } 161 } 162 } 163 164 165 @SuppressWarnings("unchecked") newTable(int length)166 private Entry<T>[] newTable(int length) { 167 return (Entry<T>[]) new Entry<?>[length]; 168 } 169 getIndex(Entry<?>[] table, int hash)170 private static int getIndex(Entry<?>[] table, int hash) { 171 return hash & (table.length - 1); 172 } 173 174 private static class Entry<T> extends WeakReference<Object> { 175 private final int hash; 176 private volatile T value; 177 private volatile Entry<T> next; 178 Entry(Object key, int hash, T value, ReferenceQueue<Object> queue, Entry<T> next)179 Entry(Object key, int hash, T value, ReferenceQueue<Object> queue, Entry<T> next) { 180 super(key, queue); 181 this.hash = hash; 182 this.value = value; 183 this.next = next; 184 } 185 isMatched(Object key, int hash)186 boolean isMatched(Object key, int hash) { 187 return (this.hash == hash) && (key == get()); 188 } 189 } 190 } 191