1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
37
38
39
40
41
42
43
44
45
46
47
48
49
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
57 private static final long DEFAULT_MAX_MEM_USAGE = 50000;
58
59 private static final int DEFAULT_INITIAL_CAPACITY = 16;
60
61 private static final int MAXIMUM_CAPACITY = 1 << 30;
62
63 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
64
65
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
71 private final float loadFactor;
72
73 private int size;
74
75 private int threshold;
76
77 private Entry [] entries;
78
79
80 private Entry<K,V> headPtr;
81
82 private Entry<K,V> tailPtr;
83
84
85 private long memTotal = 0;
86
87 private long memFree = 0;
88
89
90 private long hitCount = 0;
91
92 private long missCount = 0;
93
94
95
96
97
98
99
100
101
102
103
104
105
106
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
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
136
137
138
139
140
141
142
143
144
145 public LruHashMap(int initialCapacity, float loadFactor) {
146 this(initialCapacity, loadFactor, DEFAULT_MAX_MEM_USAGE);
147 }
148
149
150
151
152
153
154
155
156
157
158 public LruHashMap(int initialCapacity) {
159 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_MAX_MEM_USAGE);
160 }
161
162
163
164
165
166
167
168
169
170 public LruHashMap(long maxMemUsage) {
171 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR,
172 maxMemUsage);
173 }
174
175
176
177
178
179 public LruHashMap() {
180 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR,
181 DEFAULT_MAX_MEM_USAGE);
182 }
183
184
185
186
187
188
189
190
191 public long getMemFree() {
192 return memFree;
193 }
194
195
196
197
198
199
200 public long getMemMax() {
201 return memTotal;
202 }
203
204
205
206
207
208
209 public long getMemUsed() {
210 return (memTotal - memFree);
211 }
212
213
214
215
216
217
218
219 public long getHitCount() {
220 return hitCount;
221 }
222
223
224
225
226
227
228
229 public long getMissCount() {
230 return missCount;
231 }
232
233
234
235
236
237
238
239 public double getHitRatio() {
240 return (double)((double)hitCount/
241 ((double)(hitCount+missCount)));
242 }
243
244
245
246
247
248
249
250
251
252
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
267
268
269
270 public long heapSize() {
271 return (memTotal - memFree);
272 }
273
274
275
276
277
278
279
280
281
282
283
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
297 hitCount++;
298 updateLru(e);
299 return e.value;
300 }
301 e = e.next;
302 }
303 }
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
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
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
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
344
345
346
347
348
349 public synchronized V remove(Object key) {
350 Entry<K,V> e = removeEntryForKey((K)key);
351 if(e == null) return null;
352
353 memFree += e.heapSize();
354 return e.value;
355 }
356
357
358
359
360
361
362 public int size() {
363 return size;
364 }
365
366
367
368
369
370
371 public boolean isEmpty() {
372 return size == 0;
373 }
374
375
376
377
378
379
380
381 public synchronized void clear() {
382 memFree += clearAll();
383 }
384
385
386
387
388
389
390
391
392
393
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
410
411
412
413
414
415
416
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
431
432
433
434
435
436
437
438
439
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
449
450
451
452
453
454
455
456
457
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
467
468
469
470 private long getMinimumUsage() {
471 return OVERHEAD + (entries.length * ClassSize.REFERENCE);
472 }
473
474
475
476
477
478
479
480
481 private void checkAndFreeMemory(long memNeeded) {
482 while(memFree < memNeeded) {
483 evictFromLru();
484 }
485 memFree -= memNeeded;
486 }
487
488
489
490
491
492
493
494 private long evictFromLru() {
495 long freed = headPtr.heapSize();
496 memFree += freed;
497 removeEntry(headPtr);
498 return freed;
499 }
500
501
502
503
504
505
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
527
528
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
570
571
572
573
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
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
616
617
618
619
620
621
622
623
624
625
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
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
641 if (size++ >= threshold) {
642 growTable(2 * entries.length);
643 }
644 return newE.heapSize();
645 }
646
647
648
649
650
651
652
653
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
675
676
677
678
679
680 private void growTable(int newCapacity) {
681 Entry [] oldTable = entries;
682 int oldCapacity = oldTable.length;
683
684
685 if (oldCapacity == MAXIMUM_CAPACITY) {
686 threshold = Integer.MAX_VALUE;
687 return;
688 }
689
690
691 long requiredSpace = (newCapacity - oldCapacity) * ClassSize.REFERENCE;
692
693
694 checkAndFreeMemory(requiredSpace);
695
696 Entry [] newTable = new Entry[newCapacity];
697
698
699 for(int i=0; i < oldCapacity; i++) {
700 Entry<K,V> entry = oldTable[i];
701 if(entry != null) {
702
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
720
721
722
723
724
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
737
738
739
740
741
742
743 private boolean isEqual(Object x, Object y) {
744 return (x == y || x.equals(y));
745 }
746
747
748
749
750
751
752
753
754
755 private int hashIndex(int hashValue, int length) {
756 return hashValue & (length - 1);
757 }
758
759
760
761
762
763
764
765
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
784
785
786
787
788
789
790 private int calculateThreshold(int capacity, float factor) {
791 return (int)(capacity * factor);
792 }
793
794
795
796
797
798 private void init() {
799 memFree -= OVERHEAD;
800 memFree -= (entries.length * ClassSize.REFERENCE);
801 }
802
803
804
805
806
807
808
809
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
823
824
825
826 public Set<Entry<K,V>> entryTableSet() {
827 Set<Entry<K,V>> entrySet = new HashSet<Entry<K,V>>();
828 Entry [] table = entries;
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
839
840
841
842 public Entry getHeadPtr() {
843 return headPtr;
844 }
845
846
847
848
849
850
851 public Entry getTailPtr() {
852 return tailPtr;
853 }
854
855
856
857
858
859
860
861
862
863
864
865
866
867 public Set<Map.Entry<K,V>> entrySet() {
868 throw new UnsupportedOperationException(
869 "entrySet() is intentionally unimplemented");
870 }
871
872
873
874
875 public boolean equals(Object o) {
876 throw new UnsupportedOperationException(
877 "equals(Object) is intentionally unimplemented");
878 }
879
880
881
882
883 public int hashCode() {
884 throw new UnsupportedOperationException(
885 "hashCode(Object) is intentionally unimplemented");
886 }
887
888
889
890
891 public Set<K> keySet() {
892 throw new UnsupportedOperationException(
893 "keySet() is intentionally unimplemented");
894 }
895
896
897
898
899 public void putAll(Map<? extends K, ? extends V> m) {
900 throw new UnsupportedOperationException(
901 "putAll() is intentionally unimplemented");
902 }
903
904
905
906
907 public Collection<V> values() {
908 throw new UnsupportedOperationException(
909 "values() is intentionally unimplemented");
910 }
911
912
913
914
915
916
917
918
919
920
921
922 protected static class Entry<K extends HeapSize, V extends HeapSize>
923 implements Map.Entry<K,V>, HeapSize {
924
925 static final int OVERHEAD = 1 * Bytes.SIZEOF_LONG +
926 5 * ClassSize.REFERENCE + 2 * Bytes.SIZEOF_INT;
927
928
929 protected final K key;
930
931 protected V value;
932
933 protected final int hash;
934
935 protected Entry<K,V> next;
936
937
938 protected Entry<K,V> prevPtr;
939
940 protected Entry<K,V> nextPtr;
941
942
943 protected long heapSize;
944
945
946
947
948
949
950
951
952
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
962 heapSize = OVERHEAD + k.heapSize() + v.heapSize();
963 }
964
965
966
967
968
969
970 public K getKey() {
971 return key;
972 }
973
974
975
976
977
978
979 public V getValue() {
980 return value;
981 }
982
983
984
985
986
987
988
989
990
991
992
993 public V setValue(V newValue) {
994 V oldValue = value;
995 value = newValue;
996 return oldValue;
997 }
998
999
1000
1001
1002
1003
1004
1005
1006
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
1017
1018
1019
1020
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
1039
1040
1041
1042
1043 public int hashCode() {
1044 return (key.hashCode() ^ value.hashCode());
1045 }
1046
1047
1048
1049
1050
1051
1052 public String toString() {
1053 return getKey() + "=" + getValue();
1054 }
1055
1056
1057
1058
1059
1060
1061 protected void setPrevPtr(Entry<K,V> prevPtr){
1062 this.prevPtr = prevPtr;
1063 }
1064
1065
1066
1067
1068
1069 protected Entry<K,V> getPrevPtr(){
1070 return prevPtr;
1071 }
1072
1073
1074
1075
1076
1077 protected void setNextPtr(Entry<K,V> nextPtr){
1078 this.nextPtr = nextPtr;
1079 }
1080
1081
1082
1083
1084
1085 protected Entry<K,V> getNextPtr(){
1086 return nextPtr;
1087 }
1088
1089
1090
1091
1092
1093 public long heapSize() {
1094 return heapSize;
1095 }
1096 }
1097 }
1098
1099