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
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
105 protected abstract T create(Object key);
106
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
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")
166 private Entry<T>[] newTable(int length) {
167 return (Entry<T>[]) new Entry<?>[length];
168 }
169
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
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
186 boolean isMatched(Object key, int hash) {
187 return (this.hash == hash) && (key == get());
188 }
189 }
190 }
191