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 package com.sun.beans.util;
26
27 import java.lang.ref.ReferenceQueue;
28 import java.lang.ref.SoftReference;
29 import java.lang.ref.WeakReference;
30 import java.util.Objects;
31
32 /**
33 * Hash table based implementation of the cache,
34 * which allows to use weak or soft references for keys and values.
35 * An entry in a {@code Cache} will automatically be removed
36 * when its key or value is no longer in ordinary use.
37 *
38 * @author Sergey Malenkov
39 * @since 1.8
40 */
41 public abstract class Cache<K,V> {
42 private static final int MAXIMUM_CAPACITY = 1 << 30; // maximum capacity MUST be a power of two <= 1<<30
43
44 private final boolean identity; // defines whether the identity comparison is used
45 private final Kind keyKind; // a reference kind for the cache keys
46 private final Kind valueKind; // a reference kind for the cache values
47
48 private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); // queue for references to remove
49
50 private volatile CacheEntry<K,V>[] table = newTable(1 << 3); // table's length MUST be a power of two
51 private int threshold = 6; // the next size value at which to resize
52 private int size; // the number of key-value mappings contained in this map
53
54 /**
55 * Creates a corresponding value for the specified key.
56 *
57 * @param key a key that can be used to create a value
58 * @return a corresponding value for the specified key
59 */
60 public abstract V create(K key);
61
62 /**
63 * Constructs an empty {@code Cache}.
64 * The default initial capacity is 8.
65 * The default load factor is 0.75.
66 *
67 * @param keyKind a reference kind for keys
68 * @param valueKind a reference kind for values
69 *
70 * @throws NullPointerException if {@code keyKind} or {@code valueKind} are {@code null}
71 */
72 public Cache(Kind keyKind, Kind valueKind) {
73 this(keyKind, valueKind, false);
74 }
75
76 /**
77 * Constructs an empty {@code Cache}
78 * with the specified comparison method.
79 * The default initial capacity is 8.
80 * The default load factor is 0.75.
81 *
82 * @param keyKind a reference kind for keys
83 * @param valueKind a reference kind for values
84 * @param identity defines whether reference-equality
85 * is used in place of object-equality
86 *
87 * @throws NullPointerException if {@code keyKind} or {@code valueKind} are {@code null}
88 */
89 public Cache(Kind keyKind, Kind valueKind, boolean identity) {
90 Objects.requireNonNull(keyKind, "keyKind");
91 Objects.requireNonNull(valueKind, "valueKind");
92 this.keyKind = keyKind;
93 this.valueKind = valueKind;
94 this.identity = identity;
95 }
96
97 /**
98 * Returns the value to which the specified key is mapped,
99 * or {@code null} if there is no mapping for the key.
100 *
101 * @param key the key whose cached value is to be returned
102 * @return a value to which the specified key is mapped,
103 * or {@code null} if there is no mapping for {@code key}
104 *
105 * @throws NullPointerException if {@code key} is {@code null}
106 * or corresponding value is {@code null}
107 */
108 public final V get(K key) {
109 Objects.requireNonNull(key, "key");
110 removeStaleEntries();
111 int hash = hash(key);
112 // unsynchronized search improves performance
113 // the null value does not mean that there are no needed entry
114 CacheEntry<K,V>[] table = this.table; // unsynchronized access
115 V current = getEntryValue(key, hash, table[index(hash, table)]);
116 if (current != null) {
117 return current;
118 }
119 synchronized (this.queue) {
120 // synchronized search improves stability
121 // we must create and add new value if there are no needed entry
122 int index = index(hash, this.table);
123 current = getEntryValue(key, hash, this.table[index]);
124 if (current != null) {
125 return current;
126 }
127 V value = create(key);
128 Objects.requireNonNull(value, "value");
129 this.table[index] = new CacheEntry<>(hash, key, value, this.table[index]);
130 if (++this.size >= this.threshold) {
131 if (this.table.length == MAXIMUM_CAPACITY) {
132 this.threshold = Integer.MAX_VALUE;
133 } else {
134 removeStaleEntries();
135 table = newTable(this.table.length << 1);
136 transfer(this.table, table);
137 // If ignoring null elements and processing ref queue caused massive
138 // shrinkage, then restore old table. This should be rare, but avoids
139 // unbounded expansion of garbage-filled tables.
140 if (this.size >= this.threshold / 2) {
141 this.table = table;
142 this.threshold <<= 1;
143 } else {
144 transfer(table, this.table);
145 }
146 removeStaleEntries();
147 }
148 }
149 return value;
150 }
151 }
152
153 /**
154 * Removes the cached value that corresponds to the specified key.
155 *
156 * @param key the key whose mapping is to be removed from this cache
157 */
158 public final void remove(K key) {
159 if (key != null) {
160 synchronized (this.queue) {
161 removeStaleEntries();
162 int hash = hash(key);
163 int index = index(hash, this.table);
164 CacheEntry<K,V> prev = this.table[index];
165 CacheEntry<K,V> entry = prev;
166 while (entry != null) {
167 CacheEntry<K,V> next = entry.next;
168 if (entry.matches(hash, key)) {
169 if (entry == prev) {
170 this.table[index] = next;
171 } else {
172 prev.next = next;
173 }
174 entry.unlink();
175 break;
176 }
177 prev = entry;
178 entry = next;
179 }
180 }
181 }
182 }
183
184 /**
185 * Removes all of the mappings from this cache.
186 * It will be empty after this call returns.
187 */
188 public final void clear() {
189 synchronized (this.queue) {
190 int index = this.table.length;
191 while (0 < index--) {
192 CacheEntry<K,V> entry = this.table[index];
193 while (entry != null) {
194 CacheEntry<K,V> next = entry.next;
195 entry.unlink();
196 entry = next;
197 }
198 this.table[index] = null;
199 }
200 while (null != this.queue.poll()) {
201 // Clear out the reference queue.
202 }
203 }
204 }
205
206 /**
207 * Retrieves object hash code and applies a supplemental hash function
208 * to the result hash, which defends against poor quality hash functions.
209 * This is critical because {@code Cache} uses power-of-two length hash tables,
210 * that otherwise encounter collisions for hashCodes that do not differ
211 * in lower bits.
212 *
213 * @param key the object which hash code is to be calculated
214 * @return a hash code value for the specified object
215 */
216 private int hash(Object key) {
217 if (this.identity) {
218 int hash = System.identityHashCode(key);
219 return (hash << 1) - (hash << 8);
220 }
221 int hash = key.hashCode();
222 // This function ensures that hashCodes that differ only by
223 // constant multiples at each bit position have a bounded
224 // number of collisions (approximately 8 at default load factor).
225 hash ^= (hash >>> 20) ^ (hash >>> 12);
226 return hash ^ (hash >>> 7) ^ (hash >>> 4);
227 }
228
229 /**
230 * Returns index of the specified hash code in the given table.
231 * Note that the table size must be a power of two.
232 *
233 * @param hash the hash code
234 * @param table the table
235 * @return an index of the specified hash code in the given table
236 */
237 private static int index(int hash, Object[] table) {
238 return hash & (table.length - 1);
239 }
240
241 /**
242 * Creates a new array for the cache entries.
243 *
244 * @param size requested capacity MUST be a power of two
245 * @return a new array for the cache entries
246 */
247 @SuppressWarnings("unchecked")
248 private CacheEntry<K,V>[] newTable(int size) {
249 return (CacheEntry<K,V>[]) new CacheEntry[size];
250 }
251
252 private V getEntryValue(K key, int hash, CacheEntry<K,V> entry) {
253 while (entry != null) {
254 if (entry.matches(hash, key)) {
255 return entry.value.getReferent();
256 }
257 entry = entry.next;
258 }
259 return null;
260 }
261
262 private void removeStaleEntries() {
263 Object reference = this.queue.poll();
264 if (reference != null) {
265 synchronized (this.queue) {
266 do {
267 if (reference instanceof Ref) {
268 Ref ref = (Ref) reference;
269 @SuppressWarnings("unchecked")
270 CacheEntry<K,V> owner = (CacheEntry<K,V>) ref.getOwner();
271 if (owner != null) {
272 int index = index(owner.hash, this.table);
273 CacheEntry<K,V> prev = this.table[index];
274 CacheEntry<K,V> entry = prev;
275 while (entry != null) {
276 CacheEntry<K,V> next = entry.next;
277 if (entry == owner) {
278 if (entry == prev) {
279 this.table[index] = next;
280 } else {
281 prev.next = next;
282 }
283 entry.unlink();
284 break;
285 }
286 prev = entry;
287 entry = next;
288 }
289 }
290 }
291 reference = this.queue.poll();
292 }
293 while (reference != null);
294 }
295 }
296 }
297
298 private void transfer(CacheEntry<K,V>[] oldTable, CacheEntry<K,V>[] newTable) {
299 int oldIndex = oldTable.length;
300 while (0 < oldIndex--) {
301 CacheEntry<K,V> entry = oldTable[oldIndex];
302 oldTable[oldIndex] = null;
303 while (entry != null) {
304 CacheEntry<K,V> next = entry.next;
305 if (entry.key.isStale() || entry.value.isStale()) {
306 entry.unlink();
307 } else {
308 int newIndex = index(entry.hash, newTable);
309 entry.next = newTable[newIndex];
310 newTable[newIndex] = entry;
311 }
312 entry = next;
313 }
314 }
315 }
316
317 /**
318 * Represents a cache entry (key-value pair).
319 */
320 private final class CacheEntry<K,V> {
321 private final int hash;
322 private final Ref<K> key;
323 private final Ref<V> value;
324 private volatile CacheEntry<K,V> next;
325
326 /**
327 * Constructs an entry for the cache.
328 *
329 * @param hash the hash code calculated for the entry key
330 * @param key the entry key
331 * @param value the initial value of the entry
332 * @param next the next entry in a chain
333 */
334 private CacheEntry(int hash, K key, V value, CacheEntry<K,V> next) {
335 this.hash = hash;
336 this.key = Cache.this.keyKind.create(this, key, Cache.this.queue);
337 this.value = Cache.this.valueKind.create(this, value, Cache.this.queue);
338 this.next = next;
339 }
340
341 /**
342 * Determines whether the entry has the given key with the given hash code.
343 *
344 * @param hash an expected hash code
345 * @param object an object to be compared with the entry key
346 * @return {@code true} if the entry has the given key with the given hash code;
347 * {@code false} otherwise
348 */
349 private boolean matches(int hash, Object object) {
350 if (this.hash != hash) {
351 return false;
352 }
353 Object key = this.key.getReferent();
354 return (key == object) || !Cache.this.identity && (key != null) && key.equals(object);
355 }
356
357 /**
358 * Marks the entry as actually removed from the cache.
359 */
360 private void unlink() {
361 this.next = null;
362 this.key.removeOwner();
363 this.value.removeOwner();
364 Cache.this.size--;
365 }
366 }
367
368 /**
369 * Basic interface for references.
370 * It defines the operations common for the all kind of references.
371 *
372 * @param <T> the type of object to refer
373 */
374 private static interface Ref<T> {
375 /**
376 * Returns the object that possesses information about the reference.
377 *
378 * @return the owner of the reference or {@code null} if the owner is unknown
379 */
380 Object getOwner();
381
382 /**
383 * Returns the object to refer.
384 *
385 * @return the referred object or {@code null} if it was collected
386 */
387 T getReferent();
388
389 /**
390 * Determines whether the referred object was taken by the garbage collector or not.
391 *
392 * @return {@code true} if the referred object was collected
393 */
394 boolean isStale();
395
396 /**
397 * Marks this reference as removed from the cache.
398 */
399 void removeOwner();
400 }
401
402 /**
403 * Represents a reference kind.
404 */
405 public static enum Kind {
406 STRONG {
407 <T> Ref<T> create(Object owner, T value, ReferenceQueue<? super T> queue) {
408 return new Strong<>(owner, value);
409 }
410 },
411 SOFT {
412 <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue) {
413 return (referent == null)
414 ? new Strong<>(owner, referent)
415 : new Soft<>(owner, referent, queue);
416 }
417 },
418 WEAK {
419 <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue) {
420 return (referent == null)
421 ? new Strong<>(owner, referent)
422 : new Weak<>(owner, referent, queue);
423 }
424 };
425
426 /**
427 * Creates a reference to the specified object.
428 *
429 * @param <T> the type of object to refer
430 * @param owner the owner of the reference, if needed
431 * @param referent the object to refer
432 * @param queue the queue to register the reference with,
433 * or {@code null} if registration is not required
434 * @return the reference to the specified object
435 */
436 abstract <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue);
437
438 /**
439 * This is an implementation of the {@link Cache.Ref} interface
440 * that uses the strong references that prevent their referents
441 * from being made finalizable, finalized, and then reclaimed.
442 *
443 * @param <T> the type of object to refer
444 */
445 private static final class Strong<T> implements Ref<T> {
446 private Object owner;
447 private final T referent;
448
449 /**
450 * Creates a strong reference to the specified object.
451 *
452 * @param owner the owner of the reference, if needed
453 * @param referent the non-null object to refer
454 */
455 private Strong(Object owner, T referent) {
456 this.owner = owner;
457 this.referent = referent;
458 }
459
460 /**
461 * Returns the object that possesses information about the reference.
462 *
463 * @return the owner of the reference or {@code null} if the owner is unknown
464 */
465 public Object getOwner() {
466 return this.owner;
467 }
468
469 /**
470 * Returns the object to refer.
471 *
472 * @return the referred object
473 */
474 public T getReferent() {
475 return this.referent;
476 }
477
478 /**
479 * Determines whether the referred object was taken by the garbage collector or not.
480 *
481 * @return {@code true} if the referred object was collected
482 */
483 public boolean isStale() {
484 return false;
485 }
486
487 /**
488 * Marks this reference as removed from the cache.
489 */
490 public void removeOwner() {
491 this.owner = null;
492 }
493 }
494
495 /**
496 * This is an implementation of the {@link Cache.Ref} interface
497 * that uses the soft references that are cleared at the discretion
498 * of the garbage collector in response to a memory request.
499 *
500 * @param <T> the type of object to refer
501 * @see java.lang.ref.SoftReference
502 */
503 private static final class Soft<T> extends SoftReference<T> implements Ref<T> {
504 private Object owner;
505
506 /**
507 * Creates a soft reference to the specified object.
508 *
509 * @param owner the owner of the reference, if needed
510 * @param referent the non-null object to refer
511 * @param queue the queue to register the reference with,
512 * or {@code null} if registration is not required
513 */
514 private Soft(Object owner, T referent, ReferenceQueue<? super T> queue) {
515 super(referent, queue);
516 this.owner = owner;
517 }
518
519 /**
520 * Returns the object that possesses information about the reference.
521 *
522 * @return the owner of the reference or {@code null} if the owner is unknown
523 */
524 public Object getOwner() {
525 return this.owner;
526 }
527
528 /**
529 * Returns the object to refer.
530 *
531 * @return the referred object or {@code null} if it was collected
532 */
533 public T getReferent() {
534 return get();
535 }
536
537 /**
538 * Determines whether the referred object was taken by the garbage collector or not.
539 *
540 * @return {@code true} if the referred object was collected
541 */
542 public boolean isStale() {
543 return null == get();
544 }
545
546 /**
547 * Marks this reference as removed from the cache.
548 */
549 public void removeOwner() {
550 this.owner = null;
551 }
552 }
553
554 /**
555 * This is an implementation of the {@link Cache.Ref} interface
556 * that uses the weak references that do not prevent their referents
557 * from being made finalizable, finalized, and then reclaimed.
558 *
559 * @param <T> the type of object to refer
560 * @see java.lang.ref.WeakReference
561 */
562 private static final class Weak<T> extends WeakReference<T> implements Ref<T> {
563 private Object owner;
564
565 /**
566 * Creates a weak reference to the specified object.
567 *
568 * @param owner the owner of the reference, if needed
569 * @param referent the non-null object to refer
570 * @param queue the queue to register the reference with,
571 * or {@code null} if registration is not required
572 */
573 private Weak(Object owner, T referent, ReferenceQueue<? super T> queue) {
574 super(referent, queue);
575 this.owner = owner;
576 }
577
578 /**
579 * Returns the object that possesses information about the reference.
580 *
581 * @return the owner of the reference or {@code null} if the owner is unknown
582 */
583 public Object getOwner() {
584 return this.owner;
585 }
586
587 /**
588 * Returns the object to refer.
589 *
590 * @return the referred object or {@code null} if it was collected
591 */
592 public T getReferent() {
593 return get();
594 }
595
596 /**
597 * Determines whether the referred object was taken by the garbage collector or not.
598 *
599 * @return {@code true} if the referred object was collected
600 */
601 public boolean isStale() {
602 return null == get();
603 }
604
605 /**
606 * Marks this reference as removed from the cache.
607 */
608 public void removeOwner() {
609 this.owner = null;
610 }
611 }
612 }
613 }