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