EMMA Coverage Report (generated Sun Mar 01 22:06:14 CET 2015)
[all classes][org.h2.mvstore.cache]

COVERAGE SUMMARY FOR SOURCE FILE [CacheLongKeyLIRS.java]

nameclass, %method, %block, %line, %
CacheLongKeyLIRS.java100% (3/3)97%  (56/58)96%  (1643/1708)97%  (351/361)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class CacheLongKeyLIRS100% (1/1)94%  (31/33)92%  (657/718)93%  (117/126)
getHits (): long 0%   (0/1)0%   (0/26)0%   (0/4)
getMisses (): long 0%   (0/1)0%   (0/29)0%   (0/4)
remove (long): Object 100% (1/1)85%  (28/33)86%  (6/7)
CacheLongKeyLIRS (long, int, int): void 100% (1/1)98%  (45/46)100% (10/10)
CacheLongKeyLIRS (int): void 100% (1/1)100% (7/7)100% (2/2)
clear (): void 100% (1/1)100% (29/29)100% (4/4)
containsKey (long): boolean 100% (1/1)100% (10/10)100% (2/2)
containsValue (Object): boolean 100% (1/1)100% (5/5)100% (1/1)
entrySet (): Set 100% (1/1)100% (29/29)100% (5/5)
find (long): CacheLongKeyLIRS$Entry 100% (1/1)100% (10/10)100% (2/2)
get (long): Object 100% (1/1)100% (10/10)100% (2/2)
getHash (long): int 100% (1/1)100% (31/31)100% (5/5)
getMap (): Map 100% (1/1)100% (32/32)100% (7/7)
getMaxMemory (): long 100% (1/1)100% (3/3)100% (1/1)
getMemory (long): int 100% (1/1)100% (10/10)100% (2/2)
getSegment (int): CacheLongKeyLIRS$Segment 100% (1/1)100% (7/7)100% (1/1)
getSegmentIndex (int): int 100% (1/1)100% (8/8)100% (1/1)
getUsedMemory (): long 100% (1/1)100% (26/26)100% (4/4)
isEmpty (): boolean 100% (1/1)100% (7/7)100% (1/1)
keySet (): Set 100% (1/1)100% (28/28)100% (4/4)
keys (boolean, boolean): List 100% (1/1)100% (30/30)100% (4/4)
peek (long): Object 100% (1/1)100% (11/11)100% (2/2)
put (long, Object): Object 100% (1/1)100% (8/8)100% (1/1)
put (long, Object, int): Object 100% (1/1)100% (35/35)100% (7/7)
putAll (Map): void 100% (1/1)100% (22/22)100% (4/4)
resizeIfNeeded (CacheLongKeyLIRS$Segment, int): CacheLongKeyLIRS$Segment 100% (1/1)100% (28/28)100% (8/8)
setMaxMemory (long): void 100% (1/1)100% (52/52)100% (7/7)
size (): int 100% (1/1)100% (29/29)100% (4/4)
sizeHot (): int 100% (1/1)100% (32/32)100% (4/4)
sizeMapArray (): int 100% (1/1)100% (27/27)100% (4/4)
sizeNonResident (): int 100% (1/1)100% (26/26)100% (4/4)
sizeOf (Object): int 100% (1/1)100% (2/2)100% (1/1)
values (): List 100% (1/1)100% (30/30)100% (7/7)
     
class CacheLongKeyLIRS$Segment100% (1/1)100% (23/23)100% (976/980)100% (232/233)
convertOldestHotToCold (): void 100% (1/1)83%  (19/23)86%  (6/7)
CacheLongKeyLIRS$Segment (CacheLongKeyLIRS$Segment, int): void 100% (1/1)100% (103/103)100% (29/29)
CacheLongKeyLIRS$Segment (long, int, int): void 100% (1/1)100% (62/62)100% (13/13)
access (long, int): void 100% (1/1)100% (71/71)100% (19/19)
addToMap (CacheLongKeyLIRS$Entry): void 100% (1/1)100% (33/33)100% (6/6)
addToQueue (CacheLongKeyLIRS$Entry, CacheLongKeyLIRS$Entry): void 100% (1/1)100% (31/31)100% (8/8)
addToStack (CacheLongKeyLIRS$Entry): void 100% (1/1)100% (33/33)100% (7/7)
addToStackBottom (CacheLongKeyLIRS$Entry): void 100% (1/1)100% (24/24)100% (6/6)
containsKey (long, int): boolean 100% (1/1)100% (14/14)100% (2/2)
copy (CacheLongKeyLIRS$Entry): CacheLongKeyLIRS$Entry 100% (1/1)100% (22/22)100% (6/6)
evict (CacheLongKeyLIRS$Entry): void 100% (1/1)100% (82/82)100% (18/18)
find (long, int): CacheLongKeyLIRS$Entry 100% (1/1)100% (23/23)100% (5/5)
get (long, int): Object 100% (1/1)100% (64/64)100% (15/15)
getMemory (long, int): int 100% (1/1)100% (12/12)100% (2/2)
getNewMapLen (): int 100% (1/1)100% (35/35)100% (6/6)
keySet (): Set 100% (1/1)100% (42/42)100% (6/6)
keys (boolean, boolean): List 100% (1/1)100% (51/51)100% (11/11)
pruneStack (): void 100% (1/1)100% (13/13)100% (6/6)
put (long, int, Object, int): Object 100% (1/1)100% (84/84)100% (20/20)
remove (long, int): Object 100% (1/1)100% (98/98)100% (27/27)
removeFromQueue (CacheLongKeyLIRS$Entry): void 100% (1/1)100% (33/33)100% (7/7)
removeFromStack (CacheLongKeyLIRS$Entry): void 100% (1/1)100% (23/23)100% (5/5)
setMaxMemory (long): void 100% (1/1)100% (4/4)100% (2/2)
     
class CacheLongKeyLIRS$Entry100% (1/1)100% (2/2)100% (10/10)100% (2/2)
CacheLongKeyLIRS$Entry (): void 100% (1/1)100% (3/3)100% (1/1)
isHot (): boolean 100% (1/1)100% (7/7)100% (1/1)

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 */
6package org.h2.mvstore.cache;
7 
8import java.util.ArrayList;
9import java.util.HashMap;
10import java.util.HashSet;
11import java.util.List;
12import java.util.Map;
13import java.util.Set;
14import 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 */
45public 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}

[all classes][org.h2.mvstore.cache]
EMMA 2.0.5312 (C) Vladimir Roubtsov