1 /**
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.xbean.propertyeditor;
18
19 import java.lang.ref.Reference;
20 import java.lang.ref.WeakReference;
21 import java.lang.ref.ReferenceQueue;
22 import java.util.Collection;
23 import java.util.Map;
24 import java.util.Set;
25
26 /**
27 * Streamlined version of a WeakIdentityHashMap. Provides Identity semantics with
28 * Weak References to keys. This allows proxies to be GC'ed when no longer referenced
29 * by clients. <code>BasicProxymanager.destroyProxy()</code> need not be invoked when a
30 * proxy is no longer needed. Note that this is not a full Map implementation.
31 * The iteration and collection capabilities of Map have been discarded to keep the
32 * implementation lightweight.
33 * <p>
34 * Much of this code was cribbed from the Commons Collection 3.1 implementation of
35 * <code>ReferenceIdentityMap</code> and <code>AbstractReferenceMap</code>.
36 */
37 public class ReferenceIdentityMap implements Map {
38
39 /** The default capacity to use. Always use a power of 2!!! */
40 private static final int DEFAULT_CAPACITY = 16;
41 /** The default load factor to use */
42 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
43 /** The maximum capacity allowed */
44 private static final int MAXIMUM_CAPACITY = 1 << 30;
45
46 /** Load factor, normally 0.75 */
47 private float loadFactor;
48 /** The size of the map */
49 private transient int size;
50 /** Map entries */
51 private transient ReferenceEntry[] data;
52 /** Size at which to rehash */
53 private transient int threshold;
54
55 /**
56 * ReferenceQueue used to eliminate GC'ed entries.
57 */
58 private ReferenceQueue purgeQueue;
59
60 public ReferenceIdentityMap() {
61 this.loadFactor = DEFAULT_LOAD_FACTOR;
62 this.data = new ReferenceEntry[DEFAULT_CAPACITY];
63 this.threshold = calculateThreshold(DEFAULT_CAPACITY, loadFactor);
64 this.purgeQueue = new ReferenceQueue();
65 }
66
67 /**
68 * Gets the size of the map.
69 *
70 * @return the size
71 */
72 public int size() {
73 purge();
74 return size;
75 }
76
77 /**
78 * Checks whether the map is currently empty.
79 *
80 * @return true if the map is currently size zero
81 */
82 public boolean isEmpty() {
83 purge();
84 return (size == 0);
85 }
86
87 /**
88 * Checks whether the map contains the specified key.
89 *
90 * @param key the key to search for
91 * @return true if the map contains the key
92 */
93 public boolean containsKey(Object key) {
94 purge();
95 ReferenceEntry entry = getEntry(key);
96 if (entry == null) {
97 return false;
98 }
99 return (entry.getValue() != null);
100 }
101
102 /**
103 * Checks whether the map contains the specified value.
104 *
105 * @param value the value to search for
106 * @return true if the map contains the value
107 */
108 public boolean containsValue(Object value) {
109 purge();
110 if (value == null || size == 0) {
111 return false;
112 }
113 ReferenceEntry [] table = data;
114 for (int i = 0; i < table.length; i++) {
115 ReferenceEntry entry = table[i];
116 while (entry != null) {
117 if (value.equals(entry.getValue())) {
118 return true;
119 }
120 entry = entry.next;
121 }
122 }
123 return false;
124 }
125
126 /**
127 * Gets the value mapped to the key specified.
128 *
129 * @param key the key
130 * @return the mapped value, null if no match
131 */
132 public Object get(Object key) {
133 purge();
134 ReferenceEntry entry = getEntry(key);
135 if (entry == null) {
136 return null;
137 }
138 return entry.getValue();
139 }
140
141
142 /**
143 * Puts a key-value entry into this map.
144 * Neither the key nor the value may be null.
145 *
146 * @param key the key to add, must not be null
147 * @param value the value to add, must not be null
148 * @return the value previously mapped to this key, null if none
149 */
150 public Object put(Object key, Object value) {
151 assert key != null: "key is null";
152 assert value != null: "value is null";
153
154 purge();
155
156 int hashCode = hash(key);
157 int index = hashIndex(hashCode, data.length);
158 ReferenceEntry entry = data[index];
159 while (entry != null) {
160 if (entry.hashCode == hashCode && key == entry.getKey()) {
161 return entry.setValue(value);
162 }
163 entry = entry.next;
164 }
165
166 createEntry(index, hashCode, key, value);
167 return null;
168 }
169
170 /**
171 * Removes the specified mapping from this map.
172 *
173 * @param key the mapping to remove
174 * @return the value mapped to the removed key, null if key not in map
175 */
176 public Object remove(Object key) {
177 if (key == null) {
178 return null;
179 }
180 purge();
181 int hashCode = hash(key);
182 int index = hashIndex(hashCode, data.length);
183 ReferenceEntry entry = data[index];
184 ReferenceEntry previous = null;
185 while (entry != null) {
186 if (entry.hashCode == hashCode && (key == entry.getKey())) {
187 Object oldValue = entry.getValue();
188 removeEntry(entry, index, previous);
189 return oldValue;
190 }
191 previous = entry;
192 entry = entry.next;
193 }
194 return null;
195 }
196
197 /**
198 * Clears the map, resetting the size to zero and nullifying references
199 * to avoid garbage collection issues.
200 */
201 public void clear() {
202 ReferenceEntry[] data = this.data;
203 for (int i = data.length - 1; i >= 0; i--) {
204 data[i] = null;
205 }
206 size = 0;
207 while (purgeQueue.poll() != null) {} // drain the queue
208 }
209
210 public Collection values() {
211 throw new UnsupportedOperationException();
212 }
213
214 public void putAll(Map t) {
215 throw new UnsupportedOperationException();
216 }
217
218 public Set entrySet() {
219 throw new UnsupportedOperationException();
220 }
221
222 public Set keySet() {
223 throw new UnsupportedOperationException();
224 }
225
226 // end of public methods
227
228 /**
229 * Gets the entry mapped to the key specified.
230 * @param key the key
231 * @return the entry, null if no match
232 */
233 private ReferenceEntry getEntry(Object key) {
234 if (key == null) {
235 return null;
236 }
237 int hashCode = hash(key);
238 ReferenceEntry entry = data[hashIndex(hashCode, data.length)];
239 while (entry != null) {
240 if (entry.hashCode == hashCode && (key == entry.getKey())) {
241 return entry;
242 }
243 entry = entry.next;
244 }
245 return null;
246 }
247
248 /**
249 * Creates a new ReferenceEntry.
250 *
251 * @param index the index into the data map
252 * @param hashCode the hash code for the new entry
253 * @param key the key to store
254 * @param value the value to store
255 * @return the newly created entry
256 */
257 private ReferenceEntry createEntry(int index, int hashCode, Object key, Object value) {
258 ReferenceEntry newEntry = new ReferenceEntry(this, data[index], hashCode, key, value);
259 data[index] = newEntry;
260 size++;
261 checkCapacity();
262 return newEntry;
263 }
264
265 /**
266 * Removes an entry from the chain stored in a particular index.
267 * <p>
268 * This implementation removes the entry from the data storage table.
269 * The size is not updated.
270 *
271 * @param entry the entry to remove
272 * @param hashIndex the index into the data structure
273 * @param previous the previous entry in the chain
274 */
275 private void removeEntry(ReferenceEntry entry, int hashIndex, ReferenceEntry previous) {
276 if (previous == null) {
277 data[hashIndex] = entry.next;
278 } else {
279 previous.next = entry.next;
280 }
281 size--;
282 entry.next = null;
283 entry.clear();
284 entry.value = null;
285 }
286
287 /**
288 * Checks the capacity of the map and enlarges it if necessary.
289 * <p>
290 * This implementation uses the threshold to check if the map needs enlarging
291 */
292 private void checkCapacity() {
293 if (size >= threshold) {
294 int newCapacity = data.length * 2;
295 if (newCapacity <= MAXIMUM_CAPACITY) {
296 ensureCapacity(newCapacity);
297 }
298 }
299 }
300
301 /**
302 * Changes the size of the data structure to the capacity proposed.
303 *
304 * @param newCapacity the new capacity of the array (a power of two, less or equal to max)
305 */
306 private void ensureCapacity(int newCapacity) {
307 int oldCapacity = data.length;
308 if (newCapacity <= oldCapacity) {
309 return;
310 }
311
312 ReferenceEntry oldEntries[] = data;
313 ReferenceEntry newEntries[] = new ReferenceEntry[newCapacity];
314
315 for (int i = oldCapacity - 1; i >= 0; i--) {
316 ReferenceEntry entry = oldEntries[i];
317 if (entry != null) {
318 oldEntries[i] = null; // gc
319 do {
320 ReferenceEntry next = entry.next;
321 int index = hashIndex(entry.hashCode, newCapacity);
322 entry.next = newEntries[index];
323 newEntries[index] = entry;
324 entry = next;
325 } while (entry != null);
326 }
327 }
328 threshold = calculateThreshold(newCapacity, loadFactor);
329 data = newEntries;
330 }
331
332 /**
333 * Calculates the new threshold of the map, where it will be resized.
334 * This implementation uses the load factor.
335 *
336 * @param newCapacity the new capacity
337 * @param factor the load factor
338 * @return the new resize threshold
339 */
340 private int calculateThreshold(int newCapacity, float factor) {
341 return (int) (newCapacity * factor);
342 }
343
344 /**
345 * Gets the hash code for the key specified.
346 * <p>
347 * This implementation uses the identity hash code.
348 *
349 * @param key the key to get a hash code for
350 * @return the hash code
351 */
352 private int hash(Object key) {
353 return System.identityHashCode(key);
354 }
355
356 /**
357 * Gets the index into the data storage for the hashCode specified.
358 * This implementation uses the least significant bits of the hashCode.
359 *
360 * @param hashCode the hash code to use
361 * @param dataSize the size of the data to pick a bucket from
362 * @return the bucket index
363 */
364 private int hashIndex(int hashCode, int dataSize) {
365 return hashCode & (dataSize - 1);
366 }
367
368 // Code that handles WeakReference cleanup... Invoked prior to
369 // any operation accessing the ReferenceEntry array...
370
371 /**
372 * Purges stale mappings from this map.
373 * <p>
374 * Note that this method is not synchronized! Special
375 * care must be taken if, for instance, you want stale
376 * mappings to be removed on a periodic basis by some
377 * background thread.
378 */
379 private void purge() {
380 Reference entryRef = purgeQueue.poll();
381 while (entryRef != null) {
382 purge(entryRef);
383 entryRef = purgeQueue.poll();
384 }
385 }
386
387 /**
388 * Purges the specified reference.
389 *
390 * @param purgedEntry the reference to purge
391 */
392 private void purge(Reference purgedEntry) {
393 int hash = ((ReferenceEntry)purgedEntry).hashCode;
394 int index = hashIndex(hash, data.length);
395 ReferenceEntry previous = null;
396 ReferenceEntry currentEntry = data[index];
397 while (currentEntry != null) {
398 if (currentEntry == purgedEntry) {
399 currentEntry.purged();
400 if (previous == null) {
401 data[index] = currentEntry.next;
402 } else {
403 previous.next = currentEntry.next;
404 }
405 this.size--;
406 return;
407 }
408 previous = currentEntry;
409 currentEntry = currentEntry.next;
410 }
411 }
412
413 /**
414 * Each entry in the Map is represented with a ReferenceEntry.
415 * <p>
416 * If getKey() or getValue() returns null, it means
417 * the mapping is stale and should be removed.
418 *
419 * @since Commons Collections 3.1
420 */
421 private static class ReferenceEntry extends WeakReference {
422 /** The next entry in the hash chain */
423 private ReferenceEntry next;
424 /** The hash code of the key */
425 private int hashCode;
426 /** The value */
427 private Object value;
428
429 /**
430 * Creates a new entry object for the ReferenceMap.
431 *
432 * @param parent the parent map
433 * @param next the next entry in the hash bucket
434 * @param hashCode the hash code of the key
435 * @param key the key
436 * @param value the value
437 */
438 private ReferenceEntry(ReferenceIdentityMap parent, ReferenceEntry next, int hashCode, Object key, Object value) {
439 super(key, parent.purgeQueue);
440 this.next = next;
441 this.hashCode = hashCode;
442 this.value = value;
443 }
444
445 /**
446 * Gets the key from the entry.
447 * This method dereferences weak and soft keys and thus may return null.
448 *
449 * @return the key, which may be null if it was garbage collected
450 */
451 private Object getKey() {
452 return this.get();
453 }
454
455 /**
456 * Gets the value from the entry.
457 * This method dereferences weak and soft value and thus may return null.
458 *
459 * @return the value, which may be null if it was garbage collected
460 */
461 private Object getValue() {
462 return value;
463 }
464
465 /**
466 * Sets the value of the entry.
467 *
468 * @param obj the object to store
469 * @return the previous value
470 */
471 private Object setValue(Object obj) {
472 Object old = getValue();
473 value = obj;
474 return old;
475 }
476
477 /**
478 * Purges this entry.
479 */
480 private void purged() {
481 this.clear();
482 value = null;
483 }
484 }
485 }