View Javadoc

1   /**
2    * Copyright 2010 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  package org.apache.hadoop.hbase.regionserver;
21  
22  import org.apache.commons.logging.Log;
23  import org.apache.commons.logging.LogFactory;
24  import org.apache.hadoop.hbase.io.HeapSize;
25  import org.apache.hadoop.hbase.util.Bytes;
26  import org.apache.hadoop.hbase.util.ClassSize;
27  
28  import java.util.ArrayList;
29  import java.util.Collection;
30  import java.util.HashSet;
31  import java.util.List;
32  import java.util.Map;
33  import java.util.Set;
34  
35  /**
36   * The LruHashMap is a memory-aware HashMap with a configurable maximum
37   * memory footprint.
38   * <p>
39   * It maintains an ordered list of all entries in the map ordered by
40   * access time.  When space needs to be freed becase the maximum has been
41   * reached, or the application has asked to free memory, entries will be
42   * evicted according to an LRU (least-recently-used) algorithm.  That is,
43   * those entries which have not been accessed the longest will be evicted
44   * first.
45   * <p>
46   * Both the Key and Value Objects used for this class must extend
47   * <code>HeapSize</code> in order to track heap usage.
48   * <p>
49   * This class contains internal synchronization and is thread-safe.
50   */
51  public class LruHashMap<K extends HeapSize, V extends HeapSize>
52  implements HeapSize, Map<K,V> {
53  
54    static final Log LOG = LogFactory.getLog(LruHashMap.class);
55  
56    /** The default size (in bytes) of the LRU */
57    private static final long DEFAULT_MAX_MEM_USAGE = 50000;
58    /** The default capacity of the hash table */
59    private static final int DEFAULT_INITIAL_CAPACITY = 16;
60    /** The maxmum capacity of the hash table */
61    private static final int MAXIMUM_CAPACITY = 1 << 30;
62    /** The default load factor to use */
63    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
64  
65    /** Memory overhead of this Object (for HeapSize) */
66    private static final int OVERHEAD = 5 * Bytes.SIZEOF_LONG +
67      2 * Bytes.SIZEOF_INT + 2 * Bytes.SIZEOF_FLOAT + 3 * ClassSize.REFERENCE +
68      1 * ClassSize.ARRAY;
69  
70    /** Load factor allowed (usually 75%) */
71    private final float loadFactor;
72    /** Number of key/vals in the map */
73    private int size;
74    /** Size at which we grow hash */
75    private int threshold;
76    /** Entries in the map */
77    private Entry [] entries;
78  
79    /** Pointer to least recently used entry */
80    private Entry<K,V> headPtr;
81    /** Pointer to most recently used entry */
82    private Entry<K,V> tailPtr;
83  
84    /** Maximum memory usage of this map */
85    private long memTotal = 0;
86    /** Amount of available memory */
87    private long memFree = 0;
88  
89    /** Number of successful (found) get() calls */
90    private long hitCount = 0;
91    /** Number of unsuccessful (not found) get() calls */
92    private long missCount = 0;
93  
94    /**
95     * Constructs a new, empty map with the specified initial capacity,
96     * load factor, and maximum memory usage.
97     *
98     * @param initialCapacity the initial capacity
99     * @param loadFactor the load factor
100    * @param maxMemUsage the maximum total memory usage
101    * @throws IllegalArgumentException if the initial capacity is less than one
102    * @throws IllegalArgumentException if the initial capacity is greater than
103    * the maximum capacity
104    * @throws IllegalArgumentException if the load factor is <= 0
105    * @throws IllegalArgumentException if the max memory usage is too small
106    * to support the base overhead
107    */
108   public LruHashMap(int initialCapacity, float loadFactor,
109   long maxMemUsage) {
110     if (initialCapacity < 1) {
111       throw new IllegalArgumentException("Initial capacity must be > 0");
112     }
113     if (initialCapacity > MAXIMUM_CAPACITY) {
114       throw new IllegalArgumentException("Initial capacity is too large");
115     }
116     if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
117       throw new IllegalArgumentException("Load factor must be > 0");
118     }
119     if (maxMemUsage <= (OVERHEAD + initialCapacity * ClassSize.REFERENCE)) {
120       throw new IllegalArgumentException("Max memory usage too small to " +
121       "support base overhead");
122     }
123 
124     /** Find a power of 2 >= initialCapacity */
125     int capacity = calculateCapacity(initialCapacity);
126     this.loadFactor = loadFactor;
127     this.threshold = calculateThreshold(capacity,loadFactor);
128     this.entries = new Entry[capacity];
129     this.memFree = maxMemUsage;
130     this.memTotal = maxMemUsage;
131     init();
132   }
133 
134   /**
135    * Constructs a new, empty map with the specified initial capacity and
136    * load factor, and default maximum memory usage.
137    *
138    * @param initialCapacity the initial capacity
139    * @param loadFactor the load factor
140    * @throws IllegalArgumentException if the initial capacity is less than one
141    * @throws IllegalArgumentException if the initial capacity is greater than
142    * the maximum capacity
143    * @throws IllegalArgumentException if the load factor is <= 0
144    */
145   public LruHashMap(int initialCapacity, float loadFactor) {
146     this(initialCapacity, loadFactor, DEFAULT_MAX_MEM_USAGE);
147   }
148 
149   /**
150    * Constructs a new, empty map with the specified initial capacity and
151    * with the default load factor and maximum memory usage.
152    *
153    * @param initialCapacity the initial capacity
154    * @throws IllegalArgumentException if the initial capacity is less than one
155    * @throws IllegalArgumentException if the initial capacity is greater than
156    * the maximum capacity
157    */
158   public LruHashMap(int initialCapacity) {
159     this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_MAX_MEM_USAGE);
160   }
161 
162   /**
163    * Constructs a new, empty map with the specified maximum memory usage
164    * and with default initial capacity and load factor.
165    *
166    * @param maxMemUsage the maximum total memory usage
167    * @throws IllegalArgumentException if the max memory usage is too small
168    * to support the base overhead
169    */
170   public LruHashMap(long maxMemUsage) {
171     this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR,
172     maxMemUsage);
173   }
174 
175   /**
176    * Constructs a new, empty map with the default initial capacity,
177    * load factor and maximum memory usage.
178    */
179   public LruHashMap() {
180     this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR,
181     DEFAULT_MAX_MEM_USAGE);
182   }
183 
184   //--------------------------------------------------------------------------
185   /**
186    * Get the currently available memory for this LRU in bytes.
187    * This is (maxAllowed - currentlyUsed).
188    *
189    * @return currently available bytes
190    */
191   public long getMemFree() {
192     return memFree;
193   }
194 
195   /**
196    * Get the maximum memory allowed for this LRU in bytes.
197    *
198    * @return maximum allowed bytes
199    */
200   public long getMemMax() {
201     return memTotal;
202   }
203 
204   /**
205    * Get the currently used memory for this LRU in bytes.
206    *
207    * @return currently used memory in bytes
208    */
209   public long getMemUsed() {
210     return (memTotal - memFree); // FindBugs IS2_INCONSISTENT_SYNC
211   }
212 
213   /**
214    * Get the number of hits to the map.  This is the number of times
215    * a call to get() returns a matched key.
216    *
217    * @return number of hits
218    */
219   public long getHitCount() {
220     return hitCount;
221   }
222 
223   /**
224    * Get the number of misses to the map.  This is the number of times
225    * a call to get() returns null.
226    *
227    * @return number of misses
228    */
229   public long getMissCount() {
230     return missCount; // FindBugs IS2_INCONSISTENT_SYNC
231   }
232 
233   /**
234    * Get the hit ratio.  This is the number of hits divided by the
235    * total number of requests.
236    *
237    * @return hit ratio (double between 0 and 1)
238    */
239   public double getHitRatio() {
240     return (double)((double)hitCount/
241       ((double)(hitCount+missCount)));
242   }
243 
244   /**
245    * Free the requested amount of memory from the LRU map.
246    *
247    * This will do LRU eviction from the map until at least as much
248    * memory as requested is freed.  This does not affect the maximum
249    * memory usage parameter.
250    *
251    * @param requestedAmount memory to free from LRU in bytes
252    * @return actual amount of memory freed in bytes
253    */
254   public synchronized long freeMemory(long requestedAmount) throws Exception {
255     if(requestedAmount > (getMemUsed() - getMinimumUsage())) {
256       return clearAll();
257     }
258     long freedMemory = 0;
259     while(freedMemory < requestedAmount) {
260       freedMemory += evictFromLru();
261     }
262     return freedMemory;
263   }
264 
265   /**
266    * The total memory usage of this map
267    *
268    * @return memory usage of map in bytes
269    */
270   public long heapSize() {
271     return (memTotal - memFree);
272   }
273 
274   //--------------------------------------------------------------------------
275   /**
276    * Retrieves the value associated with the specified key.
277    *
278    * If an entry is found, it is updated in the LRU as the most recently
279    * used (last to be evicted) entry in the map.
280    *
281    * @param key the key
282    * @return the associated value, or null if none found
283    * @throws NullPointerException if key is null
284    */
285   public synchronized V get(Object key) {
286     checkKey((K)key);
287     int hash = hash(key);
288     int i = hashIndex(hash, entries.length);
289     Entry<K,V> e = entries[i];
290     while (true) {
291       if (e == null) {
292         missCount++;
293         return null;
294       }
295       if (e.hash == hash && isEqual(key, e.key))  {
296         // Hit!  Update position in LRU
297         hitCount++;
298         updateLru(e);
299         return e.value;
300       }
301       e = e.next;
302     }
303   }
304 
305   /**
306    * Insert a key-value mapping into the map.
307    *
308    * Entry will be inserted as the most recently used.
309    *
310    * Both the key and value are required to be Objects and must
311    * implement the HeapSize interface.
312    *
313    * @param key the key
314    * @param value the value
315    * @return the value that was previously mapped to this key, null if none
316    * @throws UnsupportedOperationException if either objects do not
317    * implement HeapSize
318    * @throws NullPointerException if the key or value is null
319    */
320   public synchronized V put(K key, V value) {
321     checkKey(key);
322     checkValue(value);
323     int hash = hash(key);
324     int i = hashIndex(hash, entries.length);
325 
326     // For old values
327     for (Entry<K,V> e = entries[i]; e != null; e = e.next) {
328       if (e.hash == hash && isEqual(key, e.key)) {
329         V oldValue = e.value;
330         long memChange = e.replaceValue(value);
331         checkAndFreeMemory(memChange);
332         // If replacing an old value for this key, update in LRU
333         updateLru(e);
334         return oldValue;
335       }
336     }
337     long memChange = addEntry(hash, key, value, i);
338     checkAndFreeMemory(memChange);
339     return null;
340   }
341 
342   /**
343    * Deletes the mapping for the specified key if it exists.
344    *
345    * @param key the key of the entry to be removed from the map
346    * @return the value associated with the specified key, or null
347    * if no mapping exists.
348    */
349   public synchronized V remove(Object key) {
350     Entry<K,V> e = removeEntryForKey((K)key);
351     if(e == null) return null;
352     // Add freed memory back to available
353     memFree += e.heapSize();
354     return e.value;
355   }
356 
357   /**
358    * Gets the size (number of entries) of the map.
359    *
360    * @return size of the map
361    */
362   public int size() {
363     return size;
364   }
365 
366   /**
367    * Checks whether the map is currently empty.
368    *
369    * @return true if size of map is zero
370    */
371   public boolean isEmpty() {
372     return size == 0;
373   }
374 
375   /**
376    * Clears all entries from the map.
377    *
378    * This frees all entries, tracking memory usage along the way.
379    * All references to entries are removed so they can be GC'd.
380    */
381   public synchronized void clear() {
382     memFree += clearAll();
383   }
384 
385   //--------------------------------------------------------------------------
386   /**
387    * Checks whether there is a value in the map for the specified key.
388    *
389    * Does not affect the LRU.
390    *
391    * @param key the key to check
392    * @return true if the map contains a value for this key, false if not
393    * @throws NullPointerException if the key is null
394    */
395   public synchronized boolean containsKey(Object key) {
396     checkKey((K)key);
397     int hash = hash(key);
398     int i = hashIndex(hash, entries.length);
399     Entry e = entries[i];
400     while (e != null) {
401       if (e.hash == hash && isEqual(key, e.key))
402           return true;
403       e = e.next;
404     }
405     return false;
406   }
407 
408   /**
409    * Checks whether this is a mapping which contains the specified value.
410    *
411    * Does not affect the LRU.  This is an inefficient operation.
412    *
413    * @param value the value to check
414    * @return true if the map contains an entry for this value, false
415    * if not
416    * @throws NullPointerException if the value is null
417    */
418   public synchronized boolean containsValue(Object value) {
419     checkValue((V)value);
420     Entry[] tab = entries;
421     for (int i = 0; i < tab.length ; i++)
422       for (Entry e = tab[i] ; e != null ; e = e.next)
423           if (value.equals(e.value))
424             return true;
425     return false;
426   }
427 
428   //--------------------------------------------------------------------------
429   /**
430    * Enforces key constraints.  Null keys are not permitted and key must
431    * implement HeapSize.  It should not be necessary to verify the second
432    * constraint because that's enforced on instantiation?
433    *
434    * Can add other constraints in the future.
435    *
436    * @param key the key
437    * @throws NullPointerException if the key is null
438    * @throws UnsupportedOperationException if the key class does not
439    * implement the HeapSize interface
440    */
441   private void checkKey(K key) {
442     if(key == null) {
443       throw new NullPointerException("null keys are not allowed");
444     }
445   }
446 
447   /**
448    * Enforces value constraints.  Null values are not permitted and value must
449    * implement HeapSize.  It should not be necessary to verify the second
450    * constraint because that's enforced on instantiation?
451    *
452    * Can add other contraints in the future.
453    *
454    * @param value the value
455    * @throws NullPointerException if the value is null
456    * @throws UnsupportedOperationException if the value class does not
457    * implement the HeapSize interface
458    */
459   private void checkValue(V value) {
460     if(value == null) {
461       throw new NullPointerException("null values are not allowed");
462     }
463   }
464 
465   /**
466    * Returns the minimum memory usage of the base map structure.
467    *
468    * @return baseline memory overhead of object in bytes
469    */
470   private long getMinimumUsage() {
471     return OVERHEAD + (entries.length * ClassSize.REFERENCE);
472   }
473 
474   //--------------------------------------------------------------------------
475   /**
476    * Evicts and frees based on LRU until at least as much memory as requested
477    * is available.
478    *
479    * @param memNeeded the amount of memory needed in bytes
480    */
481   private void checkAndFreeMemory(long memNeeded) {
482     while(memFree < memNeeded) {
483       evictFromLru();
484     }
485     memFree -= memNeeded;
486   }
487 
488   /**
489    * Evicts based on LRU.  This removes all references and updates available
490    * memory.
491    *
492    * @return amount of memory freed in bytes
493    */
494   private long evictFromLru() {
495     long freed = headPtr.heapSize();
496     memFree += freed;
497     removeEntry(headPtr);
498     return freed;
499   }
500 
501   /**
502    * Moves the specified entry to the most recently used slot of the
503    * LRU.  This is called whenever an entry is fetched.
504    *
505    * @param e entry that was accessed
506    */
507   private void updateLru(Entry<K,V> e) {
508     Entry<K,V> prev = e.getPrevPtr();
509     Entry<K,V> next = e.getNextPtr();
510     if(next != null) {
511       if(prev != null) {
512         prev.setNextPtr(next);
513         next.setPrevPtr(prev);
514       } else {
515         headPtr = next;
516         headPtr.setPrevPtr(null);
517       }
518       e.setNextPtr(null);
519       e.setPrevPtr(tailPtr);
520       tailPtr.setNextPtr(e);
521       tailPtr = e;
522     }
523   }
524 
525   /**
526    * Removes the specified entry from the map and LRU structure.
527    *
528    * @param entry entry to be removed
529    */
530   private void removeEntry(Entry<K,V> entry) {
531     K k = entry.key;
532     int hash = entry.hash;
533     int i = hashIndex(hash, entries.length);
534     Entry<K,V> prev = entries[i];
535     Entry<K,V> e = prev;
536 
537     while (e != null) {
538       Entry<K,V> next = e.next;
539       if (e.hash == hash && isEqual(k, e.key)) {
540           size--;
541           if (prev == e) {
542             entries[i] = next;
543           } else {
544             prev.next = next;
545           }
546 
547           Entry<K,V> prevPtr = e.getPrevPtr();
548           Entry<K,V> nextPtr = e.getNextPtr();
549 
550           if(prevPtr != null && nextPtr != null) {
551             prevPtr.setNextPtr(nextPtr);
552             nextPtr.setPrevPtr(prevPtr);
553           } else if(prevPtr != null) {
554             tailPtr = prevPtr;
555             prevPtr.setNextPtr(null);
556           } else if(nextPtr != null) {
557             headPtr = nextPtr;
558             nextPtr.setPrevPtr(null);
559           }
560 
561           return;
562       }
563       prev = e;
564       e = next;
565     }
566   }
567 
568   /**
569    * Removes and returns the entry associated with the specified
570    * key.
571    *
572    * @param key key of the entry to be deleted
573    * @return entry that was removed, or null if none found
574    */
575   private Entry<K,V> removeEntryForKey(K key) {
576     int hash = hash(key);
577     int i = hashIndex(hash, entries.length);
578     Entry<K,V> prev = entries[i];
579     Entry<K,V> e = prev;
580 
581     while (e != null) {
582       Entry<K,V> next = e.next;
583       if (e.hash == hash && isEqual(key, e.key)) {
584           size--;
585           if (prev == e) {
586             entries[i] = next;
587           } else {
588             prev.next = next;
589           }
590 
591           // Updating LRU
592           Entry<K,V> prevPtr = e.getPrevPtr();
593           Entry<K,V> nextPtr = e.getNextPtr();
594           if(prevPtr != null && nextPtr != null) {
595             prevPtr.setNextPtr(nextPtr);
596             nextPtr.setPrevPtr(prevPtr);
597           } else if(prevPtr != null) {
598             tailPtr = prevPtr;
599             prevPtr.setNextPtr(null);
600           } else if(nextPtr != null) {
601             headPtr = nextPtr;
602             nextPtr.setPrevPtr(null);
603           }
604 
605           return e;
606       }
607       prev = e;
608       e = next;
609     }
610 
611     return e;
612   }
613 
614  /**
615   * Adds a new entry with the specified key, value, hash code, and
616   * bucket index to the map.
617   *
618   * Also puts it in the bottom (most-recent) slot of the list and
619   * checks to see if we need to grow the array.
620   *
621   * @param hash hash value of key
622   * @param key the key
623   * @param value the value
624   * @param bucketIndex index into hash array to store this entry
625   * @return the amount of heap size used to store the new entry
626   */
627   private long addEntry(int hash, K key, V value, int bucketIndex) {
628     Entry<K,V> e = entries[bucketIndex];
629     Entry<K,V> newE = new Entry<K,V>(hash, key, value, e, tailPtr);
630     entries[bucketIndex] = newE;
631     // add as most recently used in lru
632     if (size == 0) {
633       headPtr = newE;
634       tailPtr = newE;
635     } else {
636       newE.setPrevPtr(tailPtr);
637       tailPtr.setNextPtr(newE);
638       tailPtr = newE;
639     }
640     // Grow table if we are past the threshold now
641     if (size++ >= threshold) {
642       growTable(2 * entries.length);
643     }
644     return newE.heapSize();
645   }
646 
647   /**
648    * Clears all the entries in the map.  Tracks the amount of memory being
649    * freed along the way and returns the total.
650    *
651    * Cleans up all references to allow old entries to be GC'd.
652    *
653    * @return total memory freed in bytes
654    */
655   private long clearAll() {
656     Entry cur;
657     long freedMemory = 0;
658     for(int i=0; i<entries.length; i++) {
659       cur = entries[i];
660       while(cur != null) {
661         freedMemory += cur.heapSize();
662         cur = cur.next;
663       }
664       entries[i] = null;
665     }
666     headPtr = null;
667     tailPtr = null;
668     size = 0;
669     return freedMemory;
670   }
671 
672   //--------------------------------------------------------------------------
673   /**
674    * Recreates the entire contents of the hashmap into a new array
675    * with double the capacity.  This method is called when the number of
676    * keys in the map reaches the current threshold.
677    *
678    * @param newCapacity the new size of the hash entries
679    */
680   private void growTable(int newCapacity) {
681     Entry [] oldTable = entries;
682     int oldCapacity = oldTable.length;
683 
684     // Do not allow growing the table beyond the max capacity
685     if (oldCapacity == MAXIMUM_CAPACITY) {
686       threshold = Integer.MAX_VALUE;
687       return;
688     }
689 
690     // Determine how much additional space will be required to grow the array
691     long requiredSpace = (newCapacity - oldCapacity) * ClassSize.REFERENCE;
692 
693     // Verify/enforce we have sufficient memory to grow
694     checkAndFreeMemory(requiredSpace);
695 
696     Entry [] newTable = new Entry[newCapacity];
697 
698     // Transfer existing entries to new hash table
699     for(int i=0; i < oldCapacity; i++) {
700       Entry<K,V> entry = oldTable[i];
701       if(entry != null) {
702         // Set to null for GC
703         oldTable[i] = null;
704         do {
705           Entry<K,V> next = entry.next;
706           int idx = hashIndex(entry.hash, newCapacity);
707           entry.next = newTable[idx];
708           newTable[idx] = entry;
709           entry = next;
710         } while(entry != null);
711       }
712     }
713 
714     entries = newTable;
715     threshold = (int)(newCapacity * loadFactor);
716   }
717 
718   /**
719    * Gets the hash code for the specified key.
720    * This implementation uses the additional hashing routine
721    * from JDK 1.4.
722    *
723    * @param key the key to get a hash value for
724    * @return the hash value
725    */
726   private int hash(Object key) {
727     int h = key.hashCode();
728     h += ~(h << 9);
729     h ^=  (h >>> 14);
730     h +=  (h << 4);
731     h ^=  (h >>> 10);
732     return h;
733   }
734 
735   /**
736    * Compares two objects for equality.  Method uses equals method and
737    * assumes neither value is null.
738    *
739    * @param x the first value
740    * @param y the second value
741    * @return true if equal
742    */
743   private boolean isEqual(Object x, Object y) {
744     return (x == y || x.equals(y));
745   }
746 
747   /**
748    * Determines the index into the current hash table for the specified
749    * hashValue.
750    *
751    * @param hashValue the hash value
752    * @param length the current number of hash buckets
753    * @return the index of the current hash array to use
754    */
755   private int hashIndex(int hashValue, int length) {
756     return hashValue & (length - 1);
757   }
758 
759   /**
760    * Calculates the capacity of the array backing the hash
761    * by normalizing capacity to a power of 2 and enforcing
762    * capacity limits.
763    *
764    * @param proposedCapacity the proposed capacity
765    * @return the normalized capacity
766    */
767   private int calculateCapacity(int proposedCapacity) {
768     int newCapacity = 1;
769     if(proposedCapacity > MAXIMUM_CAPACITY) {
770       newCapacity = MAXIMUM_CAPACITY;
771     } else {
772       while(newCapacity < proposedCapacity) {
773         newCapacity <<= 1;
774       }
775       if(newCapacity > MAXIMUM_CAPACITY) {
776         newCapacity = MAXIMUM_CAPACITY;
777       }
778     }
779     return newCapacity;
780   }
781 
782   /**
783    * Calculates the threshold of the map given the capacity and load
784    * factor.  Once the number of entries in the map grows to the
785    * threshold we will double the size of the array.
786    *
787    * @param capacity the size of the array
788    * @param factor the load factor of the hash
789    */
790   private int calculateThreshold(int capacity, float factor) {
791     return (int)(capacity * factor);
792   }
793 
794   /**
795    * Set the initial heap usage of this class.  Includes class variable
796    * overhead and the entry array.
797    */
798   private void init() {
799     memFree -= OVERHEAD;
800     memFree -= (entries.length * ClassSize.REFERENCE);
801   }
802 
803   //--------------------------------------------------------------------------
804   /**
805    * Debugging function that returns a List sorted by access time.
806    *
807    * The order is oldest to newest (first in list is next to be evicted).
808    *
809    * @return Sorted list of entries
810    */
811   public List<Entry<K,V>> entryLruList() {
812     List<Entry<K,V>> entryList = new ArrayList<Entry<K,V>>();
813     Entry<K,V> entry = headPtr;
814     while(entry != null) {
815       entryList.add(entry);
816       entry = entry.getNextPtr();
817     }
818     return entryList;
819   }
820 
821   /**
822    * Debugging function that returns a Set of all entries in the hash table.
823    *
824    * @return Set of entries in hash
825    */
826   public Set<Entry<K,V>> entryTableSet() {
827     Set<Entry<K,V>> entrySet = new HashSet<Entry<K,V>>();
828     Entry [] table = entries; // FindBugs IS2_INCONSISTENT_SYNC
829     for(int i=0;i<table.length;i++) {
830       for(Entry e = table[i]; e != null; e = e.next) {
831         entrySet.add(e);
832       }
833     }
834     return entrySet;
835   }
836 
837   /**
838    * Get the head of the linked list (least recently used).
839    *
840    * @return head of linked list
841    */
842   public Entry getHeadPtr() {
843     return headPtr;
844   }
845 
846   /**
847    * Get the tail of the linked list (most recently used).
848    *
849    * @return tail of linked list
850    */
851   public Entry getTailPtr() {
852     return tailPtr;
853   }
854 
855   //--------------------------------------------------------------------------
856   /**
857    * To best optimize this class, some of the methods that are part of a
858    * Map implementation are not supported.  This is primarily related
859    * to being able to get Sets and Iterators of this map which require
860    * significant overhead and code complexity to support and are
861    * unnecessary for the requirements of this class.
862    */
863 
864   /**
865    * Intentionally unimplemented.
866    */
867   public Set<Map.Entry<K,V>> entrySet() {
868     throw new UnsupportedOperationException(
869     "entrySet() is intentionally unimplemented");
870   }
871 
872   /**
873    * Intentionally unimplemented.
874    */
875   public boolean equals(Object o) {
876     throw new UnsupportedOperationException(
877     "equals(Object) is intentionally unimplemented");
878   }
879 
880   /**
881    * Intentionally unimplemented.
882    */
883   public int hashCode() {
884     throw new UnsupportedOperationException(
885     "hashCode(Object) is intentionally unimplemented");
886   }
887 
888   /**
889    * Intentionally unimplemented.
890    */
891   public Set<K> keySet() {
892     throw new UnsupportedOperationException(
893     "keySet() is intentionally unimplemented");
894   }
895 
896   /**
897    * Intentionally unimplemented.
898    */
899   public void putAll(Map<? extends K, ? extends V> m) {
900     throw new UnsupportedOperationException(
901     "putAll() is intentionally unimplemented");
902   }
903 
904   /**
905    * Intentionally unimplemented.
906    */
907   public Collection<V> values() {
908     throw new UnsupportedOperationException(
909     "values() is intentionally unimplemented");
910   }
911 
912   //--------------------------------------------------------------------------
913   /**
914    * Entry to store key/value mappings.
915    * <p>
916    * Contains previous and next pointers for the doubly linked-list which is
917    * used for LRU eviction.
918    * <p>
919    * Instantiations of this class are memory aware.  Both the key and value
920    * classes used must also implement <code>HeapSize</code>.
921    */
922   protected static class Entry<K extends HeapSize, V extends HeapSize>
923   implements Map.Entry<K,V>, HeapSize {
924     /** The baseline overhead memory usage of this class */
925     static final int OVERHEAD = 1 * Bytes.SIZEOF_LONG +
926       5 * ClassSize.REFERENCE + 2 * Bytes.SIZEOF_INT;
927 
928     /** The key */
929     protected final K key;
930     /** The value */
931     protected V value;
932     /** The hash value for this entries key */
933     protected final int hash;
934     /** The next entry in the hash chain (for collisions) */
935     protected Entry<K,V> next;
936 
937     /** The previous entry in the LRU list (towards LRU) */
938     protected Entry<K,V> prevPtr;
939     /** The next entry in the LRU list (towards MRU) */
940     protected Entry<K,V> nextPtr;
941 
942     /** The precomputed heap size of this entry */
943     protected long heapSize;
944 
945     /**
946      * Create a new entry.
947      *
948      * @param h the hash value of the key
949      * @param k the key
950      * @param v the value
951      * @param nextChainPtr the next entry in the hash chain, null if none
952      * @param prevLruPtr the previous entry in the LRU
953      */
954     Entry(int h, K k, V v, Entry<K,V> nextChainPtr, Entry<K,V> prevLruPtr) {
955       value = v;
956       next = nextChainPtr;
957       key = k;
958       hash = h;
959       prevPtr = prevLruPtr;
960       nextPtr = null;
961       // Pre-compute heap size
962       heapSize = OVERHEAD + k.heapSize() + v.heapSize();
963     }
964 
965     /**
966      * Get the key of this entry.
967      *
968      * @return the key associated with this entry
969      */
970     public K getKey() {
971       return key;
972     }
973 
974     /**
975      * Get the value of this entry.
976      *
977      * @return the value currently associated with this entry
978      */
979     public V getValue() {
980       return value;
981     }
982 
983     /**
984      * Set the value of this entry.
985      *
986      * It is not recommended to use this method when changing the value.
987      * Rather, using <code>replaceValue</code> will return the difference
988      * in heap usage between the previous and current values.
989      *
990      * @param newValue the new value to associate with this entry
991      * @return the value previously associated with this entry
992      */
993     public V setValue(V newValue) {
994       V oldValue = value;
995       value = newValue;
996       return oldValue;
997     }
998 
999     /**
1000      * Replace the value of this entry.
1001      *
1002      * Computes and returns the difference in heap size when changing
1003      * the value associated with this entry.
1004      *
1005      * @param newValue the new value to associate with this entry
1006      * @return the change in heap usage of this entry in bytes
1007      */
1008     protected long replaceValue(V newValue) {
1009       long sizeDiff = newValue.heapSize() - value.heapSize();
1010       value = newValue;
1011       heapSize += sizeDiff;
1012       return sizeDiff;
1013     }
1014 
1015     /**
1016      * Returns true is the specified entry has the same key and the
1017      * same value as this entry.
1018      *
1019      * @param o entry to test against current
1020      * @return true is entries have equal key and value, false if no
1021      */
1022     public boolean equals(Object o) {
1023       if (!(o instanceof Map.Entry))
1024           return false;
1025       Map.Entry e = (Map.Entry)o;
1026       Object k1 = getKey();
1027       Object k2 = e.getKey();
1028       if (k1 == k2 || (k1 != null && k1.equals(k2))) {
1029           Object v1 = getValue();
1030           Object v2 = e.getValue();
1031           if (v1 == v2 || (v1 != null && v1.equals(v2)))
1032             return true;
1033       }
1034       return false;
1035     }
1036 
1037     /**
1038      * Returns the hash code of the entry by xor'ing the hash values
1039      * of the key and value of this entry.
1040      *
1041      * @return hash value of this entry
1042      */
1043     public int hashCode() {
1044       return (key.hashCode() ^ value.hashCode());
1045     }
1046 
1047     /**
1048      * Returns String representation of the entry in form "key=value"
1049      *
1050      * @return string value of entry
1051      */
1052     public String toString() {
1053       return getKey() + "=" + getValue();
1054     }
1055 
1056     //------------------------------------------------------------------------
1057     /**
1058      * Sets the previous pointer for the entry in the LRU.
1059      * @param prevPtr previous entry
1060      */
1061     protected void setPrevPtr(Entry<K,V> prevPtr){
1062       this.prevPtr = prevPtr;
1063     }
1064 
1065     /**
1066      * Returns the previous pointer for the entry in the LRU.
1067      * @return previous entry
1068      */
1069     protected Entry<K,V> getPrevPtr(){
1070       return prevPtr;
1071     }
1072 
1073     /**
1074      * Sets the next pointer for the entry in the LRU.
1075      * @param nextPtr next entry
1076      */
1077     protected void setNextPtr(Entry<K,V> nextPtr){
1078       this.nextPtr = nextPtr;
1079     }
1080 
1081     /**
1082      * Returns the next pointer for the entry in teh LRU.
1083      * @return next entry
1084      */
1085     protected Entry<K,V> getNextPtr(){
1086       return nextPtr;
1087     }
1088 
1089     /**
1090      * Returns the pre-computed and "deep" size of the Entry
1091      * @return size of the entry in bytes
1092      */
1093     public long heapSize() {
1094       return heapSize;
1095     }
1096   }
1097 }
1098 
1099