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