File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\mvstore\cache\CacheLIRS.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.mvstore.cache;
8
9 import java.util.AbstractMap;
10 import java.util.ArrayList;
11 import java.util.HashMap;
12 import java.util.HashSet;
13 import java.util.List;
14 import java.util.Map;
15 import java.util.Set;
16
17 /**
18 * A scan resistant cache. It is meant to cache objects that are relatively
19 * costly to acquire, for example file content.
20 * <p>
21 * This implementation is multi-threading safe and supports concurrent access.
22 * Null keys or null values are not allowed. The map fill factor is at most 75%.
23 * <p>
24 * Each entry is assigned a distinct memory size, and the cache will try to use
25 * at most the specified amount of memory. The memory unit is not relevant,
26 * however it is suggested to use bytes as the unit.
27 * <p>
28 * This class implements an approximation of the the LIRS replacement algorithm
29 * invented by Xiaodong Zhang and Song Jiang as described in
30 * http://www.cse.ohio-state.edu/~zhang/lirs-sigmetrics-02.html with a few
31 * smaller changes: An additional queue for non-resident entries is used, to
32 * prevent unbound memory usage. The maximum size of this queue is at most the
33 * size of the rest of the stack. About 6.25% of the mapped entries are cold.
34 * <p>
35 * Internally, the cache is split into a number of segments, and each segment is
36 * an individual LIRS cache.
37 * <p>
38 * Accessed entries are only moved to the top of the stack if at least a number
39 * of other entries have been moved to the front (1% by default). Write access
40 * and moving entries to the top of the stack is synchronized per segment.
41 *
42 * @author Thomas Mueller
43 * @param <K> the key type
44 * @param <V> the value type
45 */
46 public class CacheLIRS<K, V> extends AbstractMap<K, V> implements Map<K, V> {
47
48 /**
49 * The maximum memory this cache should use.
50 */
51 private long maxMemory;
52
53 /**
54 * The average memory used by one entry.
55 */
56 private int averageMemory;
57
58 private final Segment<K, V>[] segments;
59
60 private final int segmentCount;
61 private final int segmentShift;
62 private final int segmentMask;
63 private final int stackMoveDistance;
64
65 @SuppressWarnings("unchecked")
66 private CacheLIRS(long maxMemory, int averageMemory, int segmentCount, int stackMoveDistance) {
67 setMaxMemory(maxMemory);
68 setAverageMemory(averageMemory);
69 if (Integer.bitCount(segmentCount) != 1) {
70 throw new IllegalArgumentException("The segment count must be a power of 2, is " + segmentCount);
71 }
72 this.segmentCount = segmentCount;
73 this.segmentMask = segmentCount - 1;
74 this.stackMoveDistance = stackMoveDistance;
75 segments = new Segment[segmentCount];
76 clear();
77 this.segmentShift = Integer.numberOfTrailingZeros(segments[0].entries.length);
78 }
79
80 /**
81 * Remove all entries.
82 */
83 public void clear() {
84 long max = Math.max(1, maxMemory / segmentCount);
85 for (int i = 0; i < segmentCount; i++) {
86 segments[i] = new Segment<K, V>(
87 max, averageMemory, stackMoveDistance);
88 }
89 }
90
91 private Entry<K, V> find(Object key) {
92 int hash = getHash(key);
93 return getSegment(hash).find(key, hash);
94 }
95
96 /**
97 * Check whether there is a resident entry for the given key. This
98 * method does not adjust the internal state of the cache.
99 *
100 * @param key the key (may not be null)
101 * @return true if there is a resident entry
102 */
103 public boolean containsKey(Object key) {
104 int hash = getHash(key);
105 return getSegment(hash).containsKey(key, hash);
106 }
107
108 /**
109 * Get the value for the given key if the entry is cached. This method does
110 * not modify the internal state.
111 *
112 * @param key the key (may not be null)
113 * @return the value, or null if there is no resident entry
114 */
115 public V peek(K key) {
116 Entry<K, V> e = find(key);
117 return e == null ? null : e.value;
118 }
119
120 /**
121 * Add an entry to the cache. The entry may or may not exist in the
122 * cache yet. This method will usually mark unknown entries as cold and
123 * known entries as hot.
124 *
125 * @param key the key (may not be null)
126 * @param value the value (may not be null)
127 * @param memory the memory used for the given entry
128 * @return the old value, or null if there was no resident entry
129 */
130 public V put(K key, V value, int memory) {
131 int hash = getHash(key);
132 return getSegment(hash).put(key, hash, value, memory);
133 }
134
135 /**
136 * Add an entry to the cache using the average memory size.
137 *
138 * @param key the key (may not be null)
139 * @param value the value (may not be null)
140 * @return the old value, or null if there was no resident entry
141 */
142 public V put(K key, V value) {
143 return put(key, value, averageMemory);
144 }
145
146 /**
147 * Remove an entry. Both resident and non-resident entries can be
148 * removed.
149 *
150 * @param key the key (may not be null)
151 * @return the old value, or null if there was no resident entry
152 */
153 public synchronized V remove(Object key) {
154 int hash = getHash(key);
155 return getSegment(hash).remove(key, hash);
156 }
157
158 /**
159 * Get the memory used for the given key.
160 *
161 * @param key the key (may not be null)
162 * @return the memory, or 0 if there is no resident entry
163 */
164 public int getMemory(K key) {
165 int hash = getHash(key);
166 return getSegment(hash).getMemory(key, hash);
167 }
168
169 /**
170 * Get the value for the given key if the entry is cached. This method
171 * adjusts the internal state of the cache sometimes, to ensure commonly
172 * used entries stay in the cache.
173 *
174 * @param key the key (may not be null)
175 * @return the value, or null if there is no resident entry
176 */
177 public V get(Object key) {
178 int hash = getHash(key);
179 return getSegment(hash).get(key, hash);
180 }
181
182 private Segment<K, V> getSegment(int hash) {
183 int segmentIndex = (hash >>> segmentShift) & segmentMask;
184 return segments[segmentIndex];
185 }
186
187 /**
188 * Get the hash code for the given key. The hash code is
189 * further enhanced to spread the values more evenly.
190 *
191 * @param key the key
192 * @return the hash code
193 */
194 static int getHash(Object key) {
195 int hash = key.hashCode();
196 // a supplemental secondary hash function
197 // to protect against hash codes that don't differ much
198 hash = ((hash >>> 16) ^ hash) * 0x45d9f3b;
199 hash = ((hash >>> 16) ^ hash) * 0x45d9f3b;
200 hash = (hash >>> 16) ^ hash;
201 return hash;
202 }
203
204 /**
205 * Get the currently used memory.
206 *
207 * @return the used memory
208 */
209 public long getUsedMemory() {
210 long x = 0;
211 for (Segment<K, V> s : segments) {
212 x += s.usedMemory;
213 }
214 return x;
215 }
216
217 /**
218 * Set the maximum memory this cache should use. This will not
219 * immediately cause entries to get removed however; it will only change
220 * the limit. To resize the internal array, call the clear method.
221 *
222 * @param maxMemory the maximum size (1 or larger)
223 */
224 public void setMaxMemory(long maxMemory) {
225 if (maxMemory <= 0) {
226 throw new IllegalArgumentException("Max memory must be larger than 0");
227 }
228 this.maxMemory = maxMemory;
229 if (segments != null) {
230 long max = 1 + maxMemory / segments.length;
231 for (Segment<K, V> s : segments) {
232 s.setMaxMemory(max);
233 }
234 }
235 }
236
237 /**
238 * Set the average memory used per entry. It is used to calculate the
239 * length of the internal array.
240 *
241 * @param averageMemory the average memory used (1 or larger)
242 */
243 public void setAverageMemory(int averageMemory) {
244 if (averageMemory <= 0) {
245 throw new IllegalArgumentException("Average memory must be larger than 0");
246 }
247 this.averageMemory = averageMemory;
248 if (segments != null) {
249 for (Segment<K, V> s : segments) {
250 s.setAverageMemory(averageMemory);
251 }
252 }
253 }
254
255 /**
256 * Get the average memory used per entry.
257 *
258 * @return the average memory
259 */
260 public int getAverageMemory() {
261 return averageMemory;
262 }
263
264 /**
265 * Get the maximum memory to use.
266 *
267 * @return the maximum memory
268 */
269 public long getMaxMemory() {
270 return maxMemory;
271 }
272
273 /**
274 * Create a new cache with the given number of entries, and the default
275 * settings (an average size of 1 per entry, 16 segments, and stack move
276 * distance equals to the maximum number of entries divided by 100).
277 *
278 * @param maxEntries the maximum number of entries
279 * @return the cache
280 */
281 public static <K, V> CacheLIRS<K, V> newInstance(int maxEntries) {
282 return new CacheLIRS<K, V>(maxEntries, 1, 16, maxEntries / 100);
283 }
284
285 /**
286 * Create a new cache with the given memory size.
287 *
288 * @param maxMemory the maximum memory to use (1 or larger)
289 * @param averageMemory the average memory (1 or larger)
290 * @param segmentCount the number of cache segments (must be a power of 2)
291 * @param stackMoveDistance how many other item are to be moved to the top
292 * of the stack before the current item is moved
293 * @return the cache
294 */
295 public static <K, V> CacheLIRS<K, V> newInstance(int maxMemory, int averageMemory,
296 int segmentCount, int stackMoveDistance) {
297 return new CacheLIRS<K, V>(maxMemory, averageMemory, segmentCount, stackMoveDistance);
298 }
299
300 /**
301 * Get the entry set for all resident entries.
302 *
303 * @return the entry set
304 */
305 public synchronized Set<Map.Entry<K, V>> entrySet() {
306 HashMap<K, V> map = new HashMap<K, V>();
307 for (K k : keySet()) {
308 map.put(k, find(k).value);
309 }
310 return map.entrySet();
311 }
312
313 /**
314 * Get the set of keys for resident entries.
315 *
316 * @return the set of keys
317 */
318 public synchronized Set<K> keySet() {
319 HashSet<K> set = new HashSet<K>();
320 for (Segment<K, V> s : segments) {
321 set.addAll(s.keySet());
322 }
323 return set;
324 }
325
326 /**
327 * Get the number of non-resident entries in the cache.
328 *
329 * @return the number of non-resident entries
330 */
331 public int sizeNonResident() {
332 int x = 0;
333 for (Segment<K, V> s : segments) {
334 x += s.queue2Size;
335 }
336 return x;
337 }
338
339 /**
340 * Get the length of the internal map array.
341 *
342 * @return the size of the array
343 */
344 public int sizeMapArray() {
345 int x = 0;
346 for (Segment<K, V> s : segments) {
347 x += s.entries.length;
348 }
349 return x;
350 }
351
352 /**
353 * Get the number of hot entries in the cache.
354 *
355 * @return the number of hot entries
356 */
357 public int sizeHot() {
358 int x = 0;
359 for (Segment<K, V> s : segments) {
360 x += s.mapSize - s.queueSize - s.queue2Size;
361 }
362 return x;
363 }
364
365 /**
366 * Get the number of resident entries.
367 *
368 * @return the number of entries
369 */
370 public int size() {
371 int x = 0;
372 for (Segment<K, V> s : segments) {
373 x += s.mapSize - s.queue2Size;
374 }
375 return x;
376 }
377
378 /**
379 * Get the list of keys. This method allows to read the internal state of
380 * the cache.
381 *
382 * @param cold if true, only keys for the cold entries are returned
383 * @param nonResident true for non-resident entries
384 * @return the key list
385 */
386 public synchronized List<K> keys(boolean cold, boolean nonResident) {
387 ArrayList<K> keys = new ArrayList<K>();
388 for (Segment<K, V> s : segments) {
389 keys.addAll(s.keys(cold, nonResident));
390 }
391 return keys;
392 }
393
394 /**
395 * A cache segment
396 *
397 * @param <K> the key type
398 * @param <V> the value type
399 */
400 static class Segment<K, V> {
401
402 /**
403 * The number of (hot, cold, and non-resident) entries in the map.
404 */
405 int mapSize;
406
407 /**
408 * The size of the LIRS queue for resident cold entries.
409 */
410 int queueSize;
411
412 /**
413 * The size of the LIRS queue for non-resident cold entries.
414 */
415 int queue2Size;
416
417 /**
418 * The map array. The size is always a power of 2.
419 */
420 Entry<K, V>[] entries;
421
422 /**
423 * The currently used memory.
424 */
425 long usedMemory;
426
427 /**
428 * How many other item are to be moved to the top of the stack before
429 * the current item is moved.
430 */
431 private final int stackMoveDistance;
432
433 /**
434 * The maximum memory this cache should use.
435 */
436 private long maxMemory;
437
438 /**
439 * The average memory used by one entry.
440 */
441 private int averageMemory;
442
443 /**
444 * The bit mask that is applied to the key hash code to get the index in the
445 * map array. The mask is the length of the array minus one.
446 */
447 private int mask;
448
449 /**
450 * The LIRS stack size.
451 */
452 private int stackSize;
453
454 /**
455 * The stack of recently referenced elements. This includes all hot entries,
456 * the recently referenced cold entries, and all non-resident cold entries.
457 */
458 private Entry<K, V> stack;
459
460 /**
461 * The queue of resident cold entries.
462 */
463 private Entry<K, V> queue;
464
465 /**
466 * The queue of non-resident cold entries.
467 */
468 private Entry<K, V> queue2;
469
470 /**
471 * The number of times any item was moved to the top of the stack.
472 */
473 private int stackMoveCounter;
474
475 /**
476 * Create a new cache.
477 *
478 * @param maxMemory the maximum memory to use
479 * @param averageMemory the average memory usage of an object
480 * @param stackMoveDistance the number of other entries to be moved to
481 * the top of the stack before moving an entry to the top
482 */
483 Segment(long maxMemory, int averageMemory, int stackMoveDistance) {
484 setMaxMemory(maxMemory);
485 setAverageMemory(averageMemory);
486 this.stackMoveDistance = stackMoveDistance;
487 clear();
488 }
489
490 private void clear() {
491
492 // calculate the size of the map array
493 // assume a fill factor of at most 80%
494 long maxLen = (long) (maxMemory / averageMemory / 0.75);
495 // the size needs to be a power of 2
496 long l = 8;
497 while (l < maxLen) {
498 l += l;
499 }
500 // the array size is at most 2^31 elements
501 int len = (int) Math.min(1L << 31, l);
502 // the bit mask has all bits set
503 mask = len - 1;
504
505 // initialize the stack and queue heads
506 stack = new Entry<K, V>();
507 stack.stackPrev = stack.stackNext = stack;
508 queue = new Entry<K, V>();
509 queue.queuePrev = queue.queueNext = queue;
510 queue2 = new Entry<K, V>();
511 queue2.queuePrev = queue2.queueNext = queue2;
512
513 // first set to null - avoiding out of memory
514 entries = null;
515 @SuppressWarnings("unchecked")
516 Entry<K, V>[] e = new Entry[len];
517 entries = e;
518
519 mapSize = 0;
520 usedMemory = 0;
521 stackSize = queueSize = queue2Size = 0;
522 }
523
524 /**
525 * Get the memory used for the given key.
526 *
527 * @param key the key (may not be null)
528 * @param hash the hash
529 * @return the memory, or 0 if there is no resident entry
530 */
531 int getMemory(K key, int hash) {
532 Entry<K, V> e = find(key, hash);
533 return e == null ? 0 : e.memory;
534 }
535
536 /**
537 * Get the value for the given key if the entry is cached. This method
538 * adjusts the internal state of the cache sometimes, to ensure commonly
539 * used entries stay in the cache.
540 *
541 * @param key the key (may not be null)
542 * @param hash the hash
543 * @return the value, or null if there is no resident entry
544 */
545 V get(Object key, int hash) {
546 Entry<K, V> e = find(key, hash);
547 if (e == null) {
548 // the entry was not found
549 return null;
550 }
551 V value = e.value;
552 if (value == null) {
553 // it was a non-resident entry
554 return null;
555 }
556 if (e.isHot()) {
557 if (e != stack.stackNext) {
558 if (stackMoveDistance == 0 || stackMoveCounter - e.topMove > stackMoveDistance) {
559 access(key, hash);
560 }
561 }
562 } else {
563 access(key, hash);
564 }
565 return value;
566 }
567
568 /**
569 * Access an item, moving the entry to the top of the stack or front of the
570 * queue if found.
571 *
572 * @param key the key
573 */
574 private synchronized void access(Object key, int hash) {
575 Entry<K, V> e = find(key, hash);
576 if (e == null || e.value == null) {
577 return;
578 }
579 if (e.isHot()) {
580 if (e != stack.stackNext) {
581 if (stackMoveDistance == 0 || stackMoveCounter - e.topMove > stackMoveDistance) {
582 // move a hot entry to the top of the stack
583 // unless it is already there
584 boolean wasEnd = e == stack.stackPrev;
585 removeFromStack(e);
586 if (wasEnd) {
587 // if moving the last entry, the last entry
588 // could not be cold, which is not allowed
589 pruneStack();
590 }
591 addToStack(e);
592 }
593 }
594 } else {
595 removeFromQueue(e);
596 if (e.stackNext != null) {
597 // resident cold entries become hot
598 // if they are on the stack
599 removeFromStack(e);
600 // which means a hot entry needs to become cold
601 convertOldestHotToCold();
602 } else {
603 // cold entries that are not on the stack
604 // move to the front of the queue
605 addToQueue(queue, e);
606 }
607 // in any case, the cold entry is moved to the top of the stack
608 addToStack(e);
609 }
610 }
611
612 /**
613 * Add an entry to the cache. The entry may or may not exist in the
614 * cache yet. This method will usually mark unknown entries as cold and
615 * known entries as hot.
616 *
617 * @param key the key (may not be null)
618 * @param hash the hash
619 * @param value the value (may not be null)
620 * @param memory the memory used for the given entry
621 * @return the old value, or null if there was no resident entry
622 */
623 synchronized V put(K key, int hash, V value, int memory) {
624 if (value == null) {
625 throw new NullPointerException();
626 }
627 V old;
628 Entry<K, V> e = find(key, hash);
629 if (e == null) {
630 old = null;
631 } else {
632 old = e.value;
633 remove(key, hash);
634 }
635 e = new Entry<K, V>();
636 e.key = key;
637 e.value = value;
638 e.memory = memory;
639 int index = hash & mask;
640 e.mapNext = entries[index];
641 entries[index] = e;
642 usedMemory += memory;
643 if (usedMemory > maxMemory && mapSize > 0) {
644 // an old entry needs to be removed
645 evict(e);
646 }
647 mapSize++;
648 // added entries are always added to the stack
649 addToStack(e);
650 return old;
651 }
652
653 /**
654 * Remove an entry. Both resident and non-resident entries can be
655 * removed.
656 *
657 * @param key the key (may not be null)
658 * @param hash the hash
659 * @return the old value, or null if there was no resident entry
660 */
661 synchronized V remove(Object key, int hash) {
662 int index = hash & mask;
663 Entry<K, V> e = entries[index];
664 if (e == null) {
665 return null;
666 }
667 V old;
668 if (e.key.equals(key)) {
669 old = e.value;
670 entries[index] = e.mapNext;
671 } else {
672 Entry<K, V> last;
673 do {
674 last = e;
675 e = e.mapNext;
676 if (e == null) {
677 return null;
678 }
679 } while (!e.key.equals(key));
680 old = e.value;
681 last.mapNext = e.mapNext;
682 }
683 mapSize--;
684 usedMemory -= e.memory;
685 if (e.stackNext != null) {
686 removeFromStack(e);
687 }
688 if (e.isHot()) {
689 // when removing a hot entry, the newest cold entry gets hot,
690 // so the number of hot entries does not change
691 e = queue.queueNext;
692 if (e != queue) {
693 removeFromQueue(e);
694 if (e.stackNext == null) {
695 addToStackBottom(e);
696 }
697 }
698 } else {
699 removeFromQueue(e);
700 }
701 pruneStack();
702 return old;
703 }
704
705 /**
706 * Evict cold entries (resident and non-resident) until the memory limit is
707 * reached. The new entry is added as a cold entry, except if it is the only
708 * entry.
709 *
710 * @param newCold a new cold entry
711 */
712 private void evict(Entry<K, V> newCold) {
713 // ensure there are not too many hot entries:
714 // left shift of 5 is multiplication by 32, that means if there are less
715 // than 1/32 (3.125%) cold entries, a new hot entry needs to become cold
716 while ((queueSize << 5) < mapSize) {
717 convertOldestHotToCold();
718 }
719 if (stackSize > 0) {
720 // the new cold entry is at the top of the queue
721 addToQueue(queue, newCold);
722 }
723 // the oldest resident cold entries become non-resident
724 // but at least one cold entry (the new one) must stay
725 while (usedMemory > maxMemory && queueSize > 1) {
726 Entry<K, V> e = queue.queuePrev;
727 usedMemory -= e.memory;
728 removeFromQueue(e);
729 e.value = null;
730 e.memory = 0;
731 addToQueue(queue2, e);
732 // the size of the non-resident-cold entries needs to be limited
733 while (queue2Size + queue2Size > stackSize) {
734 e = queue2.queuePrev;
735 int hash = getHash(e.key);
736 remove(e.key, hash);
737 }
738 }
739 }
740
741 private void convertOldestHotToCold() {
742 // the last entry of the stack is known to be hot
743 Entry<K, V> last = stack.stackPrev;
744 // remove from stack - which is done anyway in the stack pruning, but we
745 // can do it here as well
746 removeFromStack(last);
747 // adding an entry to the queue will make it cold
748 addToQueue(queue, last);
749 pruneStack();
750 }
751
752 /**
753 * Ensure the last entry of the stack is cold.
754 */
755 private void pruneStack() {
756 while (true) {
757 Entry<K, V> last = stack.stackPrev;
758 if (last == stack || last.isHot()) {
759 break;
760 }
761 // the cold entry is still in the queue
762 removeFromStack(last);
763 }
764 }
765
766 /**
767 * Try to find an entry in the map.
768 *
769 * @param key the key
770 * @param hash the hash
771 * @return the entry (might be a non-resident)
772 */
773 Entry<K, V> find(Object key, int hash) {
774 int index = hash & mask;
775 Entry<K, V> e = entries[index];
776 while (e != null && !e.key.equals(key)) {
777 e = e.mapNext;
778 }
779 return e;
780 }
781
782 private void addToStack(Entry<K, V> e) {
783 e.stackPrev = stack;
784 e.stackNext = stack.stackNext;
785 e.stackNext.stackPrev = e;
786 stack.stackNext = e;
787 stackSize++;
788 e.topMove = stackMoveCounter++;
789 }
790
791 private void addToStackBottom(Entry<K, V> e) {
792 e.stackNext = stack;
793 e.stackPrev = stack.stackPrev;
794 e.stackPrev.stackNext = e;
795 stack.stackPrev = e;
796 stackSize++;
797 }
798
799 private void removeFromStack(Entry<K, V> e) {
800 e.stackPrev.stackNext = e.stackNext;
801 e.stackNext.stackPrev = e.stackPrev;
802 e.stackPrev = e.stackNext = null;
803 stackSize--;
804 }
805
806 private void addToQueue(Entry<K, V> q, Entry<K, V> e) {
807 e.queuePrev = q;
808 e.queueNext = q.queueNext;
809 e.queueNext.queuePrev = e;
810 q.queueNext = e;
811 if (e.value != null) {
812 queueSize++;
813 } else {
814 queue2Size++;
815 }
816 }
817
818 private void removeFromQueue(Entry<K, V> e) {
819 e.queuePrev.queueNext = e.queueNext;
820 e.queueNext.queuePrev = e.queuePrev;
821 e.queuePrev = e.queueNext = null;
822 if (e.value != null) {
823 queueSize--;
824 } else {
825 queue2Size--;
826 }
827 }
828
829 /**
830 * Get the list of keys. This method allows to read the internal state of
831 * the cache.
832 *
833 * @param cold if true, only keys for the cold entries are returned
834 * @param nonResident true for non-resident entries
835 * @return the key list
836 */
837 synchronized List<K> keys(boolean cold, boolean nonResident) {
838 ArrayList<K> keys = new ArrayList<K>();
839 if (cold) {
840 Entry<K, V> start = nonResident ? queue2 : queue;
841 for (Entry<K, V> e = start.queueNext; e != start; e = e.queueNext) {
842 keys.add(e.key);
843 }
844 } else {
845 for (Entry<K, V> e = stack.stackNext; e != stack; e = e.stackNext) {
846 keys.add(e.key);
847 }
848 }
849 return keys;
850 }
851
852 /**
853 * Check whether there is a resident entry for the given key. This
854 * method does not adjust the internal state of the cache.
855 *
856 * @param key the key (may not be null)
857 * @param hash the hash
858 * @return true if there is a resident entry
859 */
860 boolean containsKey(Object key, int hash) {
861 Entry<K, V> e = find(key, hash);
862 return e != null && e.value != null;
863 }
864
865 /**
866 * Get the set of keys for resident entries.
867 *
868 * @return the set of keys
869 */
870 synchronized Set<K> keySet() {
871 HashSet<K> set = new HashSet<K>();
872 for (Entry<K, V> e = stack.stackNext; e != stack; e = e.stackNext) {
873 set.add(e.key);
874 }
875 for (Entry<K, V> e = queue.queueNext; e != queue; e = e.queueNext) {
876 set.add(e.key);
877 }
878 return set;
879 }
880
881 /**
882 * Set the maximum memory this cache should use. This will not
883 * immediately cause entries to get removed however; it will only change
884 * the limit. To resize the internal array, call the clear method.
885 *
886 * @param maxMemory the maximum size (1 or larger)
887 */
888 void setMaxMemory(long maxMemory) {
889 if (maxMemory <= 0) {
890 throw new IllegalArgumentException("Max memory must be larger than 0");
891 }
892 this.maxMemory = maxMemory;
893 }
894
895 /**
896 * Set the average memory used per entry. It is used to calculate the
897 * length of the internal array.
898 *
899 * @param averageMemory the average memory used (1 or larger)
900 */
901 void setAverageMemory(int averageMemory) {
902 if (averageMemory <= 0) {
903 throw new IllegalArgumentException("Average memory must be larger than 0");
904 }
905 this.averageMemory = averageMemory;
906 }
907
908 }
909
910 /**
911 * A cache entry. Each entry is either hot (low inter-reference recency;
912 * LIR), cold (high inter-reference recency; HIR), or non-resident-cold. Hot
913 * entries are in the stack only. Cold entries are in the queue, and may be
914 * in the stack. Non-resident-cold entries have their value set to null and
915 * are in the stack and in the non-resident queue.
916 *
917 * @param <K> the key type
918 * @param <V> the value type
919 */
920 static class Entry<K, V> {
921
922 /**
923 * The key.
924 */
925 K key;
926
927 /**
928 * The value. Set to null for non-resident-cold entries.
929 */
930 V value;
931
932 /**
933 * The estimated memory used.
934 */
935 int memory;
936
937 /**
938 * When the item was last moved to the top of the stack.
939 */
940 int topMove;
941
942 /**
943 * The next entry in the stack.
944 */
945 Entry<K, V> stackNext;
946
947 /**
948 * The previous entry in the stack.
949 */
950 Entry<K, V> stackPrev;
951
952 /**
953 * The next entry in the queue (either the resident queue or the
954 * non-resident queue).
955 */
956 Entry<K, V> queueNext;
957
958 /**
959 * The previous entry in the queue.
960 */
961 Entry<K, V> queuePrev;
962
963 /**
964 * The next entry in the map
965 */
966 Entry<K, V> mapNext;
967
968 /**
969 * Whether this entry is hot. Cold entries are in one of the two queues.
970 *
971 * @return whether the entry is hot
972 */
973 boolean isHot() {
974 return queueNext == null;
975 }
976
977 }
978
979 }
980