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