1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.hadoop.hbase.types;
20
21 import org.apache.hadoop.hbase.classification.InterfaceAudience;
22 import org.apache.hadoop.hbase.classification.InterfaceStability;
23
24 import java.util.AbstractMap;
25 import java.util.Collection;
26 import java.util.Comparator;
27 import java.util.Iterator;
28 import java.util.Map;
29 import java.util.NavigableSet;
30 import java.util.Set;
31 import java.util.SortedSet;
32 import java.util.concurrent.ConcurrentNavigableMap;
33
34
35
36
37
38
39
40
41
42 @InterfaceAudience.Private
43 @InterfaceStability.Stable
44 public class CopyOnWriteArrayMap<K, V> extends AbstractMap<K, V>
45 implements Map<K, V>, ConcurrentNavigableMap<K, V> {
46 private final Comparator<? super K> keyComparator;
47 private volatile ArrayHolder<K, V> holder;
48
49 public CopyOnWriteArrayMap() {
50 this(new Comparator<K>() {
51 @Override
52 public int compare(K o1, K o2) {
53 return ((Comparable) o1).compareTo(o2);
54 }
55 });
56 }
57
58 public CopyOnWriteArrayMap(final Comparator<? super K> keyComparator) {
59 this.keyComparator = keyComparator;
60 this.holder = new ArrayHolder<>(keyComparator, new Comparator<Entry<K, V>>() {
61 @Override
62 public int compare(Entry<K, V> o1, Entry<K, V> o2) {
63 return keyComparator.compare(o1.getKey(), o2.getKey());
64 }
65 });
66 }
67
68 private CopyOnWriteArrayMap(final Comparator<? super K> keyComparator, ArrayHolder<K, V> holder) {
69 this.keyComparator = keyComparator;
70 this.holder = holder;
71 }
72
73
74
75
76
77
78
79
80
81
82
83 @Override
84 public Comparator<? super K> comparator() {
85 return keyComparator;
86 }
87
88 @Override
89 public ConcurrentNavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
90 ArrayHolder<K, V> current = this.holder;
91 int index = current.find(fromKey);
92
93 if (!inclusive && index >= 0) {
94 index++;
95 } else if (index < 0) {
96 index = -(index + 1);
97 }
98 return new CopyOnWriteArrayMap<>(
99 this.keyComparator,
100 new ArrayHolder<>(
101 current.entries,
102 index,
103 current.endIndex,
104 current.keyComparator,
105 current.comparator));
106 }
107
108 @Override
109 public ConcurrentNavigableMap<K, V> tailMap(K fromKey) {
110 return this.tailMap(fromKey, true);
111 }
112
113 @Override
114 public K firstKey() {
115 ArrayHolder<K, V> current = this.holder;
116 if (current.getLength() == 0) {
117 return null;
118 }
119 return current.entries[current.startIndex].getKey();
120 }
121
122 @Override
123 public K lastKey() {
124 ArrayHolder<K, V> current = this.holder;
125 if (current.getLength() == 0) {
126 return null;
127 }
128 return current.entries[current.endIndex - 1].getKey();
129 }
130
131 @Override
132 public Entry<K, V> lowerEntry(K key) {
133 ArrayHolder<K, V> current = this.holder;
134 if (current.getLength() == 0) {
135 return null;
136 }
137
138 int index = current.find(key);
139
140
141 if (index >= 0) {
142 index -= 1;
143 } else {
144 index = -(index + 1) - 1;
145 }
146
147 if (index < current.startIndex || index >= current.endIndex) {
148 return null;
149 }
150 return current.entries[index];
151 }
152
153 @Override
154 public K lowerKey(K key) {
155 Map.Entry<K, V> entry = lowerEntry(key);
156 if (entry == null) {
157 return null;
158 }
159 return entry.getKey();
160 }
161
162 @Override
163 public Entry<K, V> floorEntry(K key) {
164 ArrayHolder<K, V> current = this.holder;
165 if (current.getLength() == 0) {
166 return null;
167 }
168 int index = current.find(key);
169 if (index < 0) {
170 index = -(index + 1) - 1;
171 }
172 if (index < current.startIndex || index >= current.endIndex) {
173 return null;
174 }
175
176 return current.entries[index];
177 }
178
179 @Override
180 public K floorKey(K key) {
181 Map.Entry<K, V> entry = floorEntry(key);
182 if (entry == null) {
183 return null;
184 }
185 return entry.getKey();
186 }
187
188 @Override
189 public Entry<K, V> ceilingEntry(K key) {
190 ArrayHolder<K, V> current = this.holder;
191 if (current.getLength() == 0) {
192 return null;
193 }
194 int index = current.find(key);
195 if (index < 0) {
196 index = -(index + 1);
197 }
198 if (index < current.startIndex || index >= current.endIndex) {
199 return null;
200 }
201
202 return current.entries[index];
203 }
204
205 @Override
206 public K ceilingKey(K key) {
207 Map.Entry<K, V> entry = ceilingEntry(key);
208 if (entry == null) {
209 return null;
210 }
211 return entry.getKey();
212 }
213
214 @Override
215 public Entry<K, V> higherEntry(K key) {
216 ArrayHolder<K, V> current = this.holder;
217 if (current.getLength() == 0) {
218 return null;
219 }
220 int index = current.find(key);
221
222
223 if (index >= 0) {
224 index += 1;
225 } else {
226 index = -(index + 1);
227 }
228
229 if (index < current.startIndex || index >= current.endIndex) {
230 return null;
231 }
232 return current.entries[index];
233 }
234
235 @Override
236 public K higherKey(K key) {
237 Map.Entry<K, V> entry = higherEntry(key);
238 if (entry == null) {
239 return null;
240 }
241 return entry.getKey();
242 }
243
244 @Override
245 public Entry<K, V> firstEntry() {
246 ArrayHolder<K, V> current = this.holder;
247 if (current.getLength() == 0) {
248 return null;
249 }
250 return current.entries[current.startIndex];
251 }
252
253 @Override
254 public Entry<K, V> lastEntry() {
255 ArrayHolder<K, V> current = this.holder;
256 if (current.getLength() == 0) {
257 return null;
258 }
259 return current.entries[current.endIndex - 1];
260 }
261
262 @Override
263 public int size() {
264 return holder.getLength();
265 }
266
267 @Override
268 public boolean isEmpty() {
269 return holder.getLength() == 0;
270 }
271
272 @Override
273 public boolean containsKey(Object key) {
274 ArrayHolder<K, V> current = this.holder;
275 int index = current.find((K) key);
276 return index >= 0;
277 }
278
279 @Override
280 public V get(Object key) {
281
282 ArrayHolder<K, V> current = this.holder;
283 int index = current.find((K) key);
284 if (index >= 0) {
285 return current.entries[index].getValue();
286 }
287 return null;
288 }
289
290 @Override
291 public NavigableSet<K> keySet() {
292 return new ArrayKeySet<>(this.holder);
293 }
294
295 @Override
296 public Collection<V> values() {
297 return new ArrayValueCollection<>(this.holder);
298 }
299
300 @Override
301 public Set<Entry<K, V>> entrySet() {
302 return new ArrayEntrySet<>(this.holder);
303 }
304
305
306
307
308
309
310
311
312
313
314
315 @Override
316 public synchronized V put(K key, V value) {
317 ArrayHolder<K, V> current = this.holder;
318 int index = current.find(key);
319 COWEntry<K, V> newEntry = new COWEntry<>(key, value);
320 if (index >= 0) {
321 this.holder = current.replace(index, newEntry);
322 return current.entries[index].getValue();
323 } else {
324 this.holder = current.insert(-(index + 1), newEntry);
325 }
326 return null;
327 }
328
329 @Override
330 public synchronized V remove(Object key) {
331
332 ArrayHolder<K, V> current = this.holder;
333 int index = current.find((K) key);
334 if (index >= 0) {
335 this.holder = current.remove(index);
336 return current.entries[index].getValue();
337 }
338 return null;
339 }
340
341 @Override
342 public synchronized void clear() {
343 this.holder = new ArrayHolder<>(this.holder.keyComparator, this.holder.comparator);
344 }
345
346 @Override
347 public synchronized V putIfAbsent(K key, V value) {
348 ArrayHolder<K, V> current = this.holder;
349 int index = current.find(key);
350
351 if (index < 0) {
352 COWEntry<K, V> newEntry = new COWEntry<>(key, value);
353 this.holder = current.insert(-(index + 1), newEntry);
354 return value;
355 }
356 return current.entries[index].getValue();
357 }
358
359 @Override
360 public synchronized boolean remove(Object key, Object value) {
361 ArrayHolder<K, V> current = this.holder;
362 int index = current.find((K) key);
363
364 if (index >= 0 && current.entries[index].getValue().equals(value)) {
365 this.holder = current.remove(index);
366 return true;
367 }
368 return false;
369 }
370
371 @Override
372 public synchronized boolean replace(K key, V oldValue, V newValue) {
373 ArrayHolder<K, V> current = this.holder;
374 int index = current.find(key);
375
376 if (index >= 0 && current.entries[index].getValue().equals(oldValue)) {
377 COWEntry<K, V> newEntry = new COWEntry<>(key, newValue);
378 this.holder = current.replace(index, newEntry);
379 return true;
380 }
381 return false;
382 }
383
384 @Override
385 public synchronized V replace(K key, V value) {
386 ArrayHolder<K, V> current = this.holder;
387 int index = current.find(key);
388
389 if (index >= 0) {
390 COWEntry<K, V> newEntry = new COWEntry<>(key, value);
391 this.holder = current.replace(index, newEntry);
392 return current.entries[index].getValue();
393 }
394 return null;
395 }
396
397 @Override
398 public Entry<K, V> pollFirstEntry() {
399 throw new UnsupportedOperationException();
400 }
401
402 @Override
403 public Entry<K, V> pollLastEntry() {
404 throw new UnsupportedOperationException();
405 }
406
407 @Override
408 public ConcurrentNavigableMap<K, V> descendingMap() {
409 throw new UnsupportedOperationException();
410 }
411
412 @Override
413 public NavigableSet<K> navigableKeySet() {
414 throw new UnsupportedOperationException();
415 }
416
417 @Override
418 public ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey) {
419 throw new UnsupportedOperationException();
420 }
421
422 @Override
423 public ConcurrentNavigableMap<K, V> headMap(K toKey) {
424 throw new UnsupportedOperationException();
425 }
426
427 @Override
428 public ConcurrentNavigableMap<K, V> subMap(K fromKey,
429 boolean fromInclusive,
430 K toKey,
431 boolean toInclusive) {
432 throw new UnsupportedOperationException();
433 }
434
435 @Override
436 public ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive) {
437 throw new UnsupportedOperationException();
438 }
439
440 @Override
441 public NavigableSet<K> descendingKeySet() {
442 throw new UnsupportedOperationException();
443 }
444
445 private final class ArrayKeySet<K, V> implements NavigableSet<K> {
446
447 private final ArrayHolder<K, V> holder;
448
449 private ArrayKeySet(ArrayHolder<K, V> holder) {
450 this.holder = holder;
451 }
452
453 @Override
454 public int size() {
455 return holder.getLength();
456 }
457
458 @Override
459 public boolean isEmpty() {
460 return holder.getLength() == 0;
461 }
462
463 @Override
464 public boolean contains(Object o) {
465 ArrayHolder<K, V> current = this.holder;
466
467 for (int i = current.startIndex; i < current.endIndex; i++) {
468 if (current.entries[i].getValue().equals(o)) {
469 return true;
470 }
471 }
472 return false;
473 }
474
475 @Override
476 public K lower(K k) {
477 throw new UnsupportedOperationException();
478 }
479
480 @Override
481 public K floor(K k) {
482 throw new UnsupportedOperationException();
483 }
484
485 @Override
486 public K ceiling(K k) {
487 throw new UnsupportedOperationException();
488 }
489
490 @Override
491 public K higher(K k) {
492 throw new UnsupportedOperationException();
493 }
494
495 @Override
496 public K pollFirst() {
497 throw new UnsupportedOperationException();
498 }
499
500 @Override
501 public K pollLast() {
502 throw new UnsupportedOperationException();
503 }
504
505 @Override
506 public Iterator<K> iterator() {
507 return new ArrayKeyIterator<>(this.holder);
508 }
509
510 @Override
511 public NavigableSet<K> descendingSet() {
512 throw new UnsupportedOperationException();
513 }
514
515 @Override
516 public Iterator<K> descendingIterator() {
517 throw new UnsupportedOperationException();
518 }
519
520 @Override
521 public NavigableSet<K> subSet(K fromElement,
522 boolean fromInclusive,
523 K toElement,
524 boolean toInclusive) {
525 throw new UnsupportedOperationException();
526 }
527
528 @Override
529 public NavigableSet<K> headSet(K toElement, boolean inclusive) {
530 throw new UnsupportedOperationException();
531 }
532
533 @Override
534 public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
535 throw new UnsupportedOperationException();
536 }
537
538 @Override
539 public Comparator<? super K> comparator() {
540 return (Comparator<? super K>) keyComparator;
541 }
542
543 @Override
544 public SortedSet<K> subSet(K fromElement, K toElement) {
545 return null;
546 }
547
548 @Override
549 public SortedSet<K> headSet(K toElement) {
550 return null;
551 }
552
553 @Override
554 public SortedSet<K> tailSet(K fromElement) {
555 return null;
556 }
557
558 @Override
559 public K first() {
560 ArrayHolder<K, V> current = this.holder;
561 if (current.getLength() == 0) {
562 return null;
563 }
564 return current.entries[current.startIndex].getKey();
565 }
566
567 @Override
568 public K last() {
569 ArrayHolder<K, V> current = this.holder;
570 if (current.getLength() == 0) {
571 return null;
572 }
573 return current.entries[current.endIndex - 1].getKey();
574 }
575
576 @Override
577 public Object[] toArray() {
578 throw new UnsupportedOperationException();
579 }
580
581 @Override
582 public <T> T[] toArray(T[] a) {
583 throw new UnsupportedOperationException();
584 }
585
586 @Override
587 public boolean add(K k) {
588 throw new UnsupportedOperationException();
589 }
590
591 @Override
592 public boolean remove(Object o) {
593 throw new UnsupportedOperationException();
594 }
595
596 @Override
597 public boolean containsAll(Collection<?> c) {
598 throw new UnsupportedOperationException();
599 }
600
601 @Override
602 public boolean addAll(Collection<? extends K> c) {
603 throw new UnsupportedOperationException();
604 }
605
606 @Override
607 public boolean retainAll(Collection<?> c) {
608 throw new UnsupportedOperationException();
609 }
610
611 @Override
612 public boolean removeAll(Collection<?> c) {
613 throw new UnsupportedOperationException();
614 }
615
616 @Override
617 public void clear() {
618 throw new UnsupportedOperationException();
619 }
620 }
621
622 private final class ArrayValueCollection<K, V> implements Collection<V> {
623
624 private final ArrayHolder<K, V> holder;
625
626 private ArrayValueCollection(ArrayHolder<K, V> holder) {
627 this.holder = holder;
628 }
629
630 @Override
631 public int size() {
632 return holder.getLength();
633 }
634
635 @Override
636 public boolean isEmpty() {
637 return holder.getLength() == 0;
638 }
639
640 @Override
641 public boolean contains(Object o) {
642 throw new UnsupportedOperationException();
643 }
644
645 @Override
646 public Iterator<V> iterator() {
647 return new ArrayValueIterator<>(this.holder);
648 }
649
650 @Override
651 public Object[] toArray() {
652 throw new UnsupportedOperationException();
653 }
654
655 @Override
656 public <T> T[] toArray(T[] a) {
657 throw new UnsupportedOperationException();
658 }
659
660 @Override
661 public boolean add(V v) {
662 throw new UnsupportedOperationException();
663 }
664
665 @Override
666 public boolean remove(Object o) {
667 throw new UnsupportedOperationException();
668 }
669
670 @Override
671 public boolean containsAll(Collection<?> c) {
672 throw new UnsupportedOperationException();
673 }
674
675 @Override
676 public boolean addAll(Collection<? extends V> c) {
677 throw new UnsupportedOperationException();
678 }
679
680 @Override
681 public boolean removeAll(Collection<?> c) {
682 throw new UnsupportedOperationException();
683 }
684
685 @Override
686 public boolean retainAll(Collection<?> c) {
687 throw new UnsupportedOperationException();
688 }
689
690 @Override
691 public void clear() {
692 throw new UnsupportedOperationException();
693 }
694
695 @Override
696 public boolean equals(Object o) {
697 return false;
698 }
699
700 @Override
701 public int hashCode() {
702 return 0;
703 }
704 }
705
706 private final class ArrayKeyIterator<K, V> implements Iterator<K> {
707 int index;
708 private final ArrayHolder<K, V> holder;
709
710 private ArrayKeyIterator(ArrayHolder<K, V> holder) {
711 this.holder = holder;
712 index = holder.startIndex;
713 }
714
715
716 @Override
717 public boolean hasNext() {
718 return index < holder.endIndex;
719 }
720
721 @Override
722 public K next() {
723 return holder.entries[index++].getKey();
724 }
725
726 @Override
727 public void remove() {
728 throw new UnsupportedOperationException("remove");
729 }
730 }
731
732 private final class ArrayValueIterator<K, V> implements Iterator<V> {
733 int index;
734 private final ArrayHolder<K, V> holder;
735
736 private ArrayValueIterator(ArrayHolder<K, V> holder) {
737 this.holder = holder;
738 index = holder.startIndex;
739 }
740
741
742 @Override
743 public boolean hasNext() {
744 return index < holder.endIndex;
745 }
746
747 @Override
748 public V next() {
749 return holder.entries[index++].getValue();
750 }
751
752 @Override
753 public void remove() {
754 throw new UnsupportedOperationException("remove");
755 }
756 }
757
758 private final class ArrayEntryIterator<K, V> implements Iterator<Map.Entry<K, V>> {
759
760 int index;
761 private final ArrayHolder<K, V> holder;
762
763 private ArrayEntryIterator(ArrayHolder<K, V> holder) {
764 this.holder = holder;
765 this.index = holder.startIndex;
766 }
767
768 @Override
769 public boolean hasNext() {
770 return index < holder.endIndex;
771 }
772
773 @Override
774 public Entry<K, V> next() {
775 return holder.entries[index++];
776 }
777
778 @Override
779 public void remove() {
780 throw new UnsupportedOperationException("remove");
781 }
782 }
783
784 private final class ArrayEntrySet<K, V> implements Set<Map.Entry<K, V>> {
785 private final ArrayHolder<K, V> holder;
786
787 private ArrayEntrySet(ArrayHolder<K, V> holder) {
788 this.holder = holder;
789 }
790
791 @Override
792 public int size() {
793 return holder.getLength();
794 }
795
796 @Override
797 public boolean isEmpty() {
798 return holder.getLength() == 0;
799 }
800
801 @Override
802 public boolean contains(Object o) {
803 return false;
804 }
805
806 @Override
807 public Iterator<Entry<K, V>> iterator() {
808 return new ArrayEntryIterator<>(this.holder);
809 }
810
811 @Override
812 public Object[] toArray() {
813 throw new UnsupportedOperationException();
814 }
815
816 @Override
817 public <T> T[] toArray(T[] a) {
818 throw new UnsupportedOperationException();
819 }
820
821 @Override
822 public boolean add(Entry<K, V> kvEntry) {
823 throw new UnsupportedOperationException();
824 }
825
826 @Override
827 public boolean remove(Object o) {
828 throw new UnsupportedOperationException();
829 }
830
831 @Override
832 public boolean containsAll(Collection<?> c) {
833 throw new UnsupportedOperationException();
834 }
835
836 @Override
837 public boolean addAll(Collection<? extends Entry<K, V>> c) {
838 throw new UnsupportedOperationException();
839 }
840
841 @Override
842 public boolean retainAll(Collection<?> c) {
843 throw new UnsupportedOperationException();
844 }
845
846 @Override
847 public boolean removeAll(Collection<?> c) {
848 throw new UnsupportedOperationException();
849 }
850
851 @Override
852 public void clear() {
853 throw new UnsupportedOperationException();
854 }
855 }
856
857 private final static class ArrayHolder<K, V> {
858 private final COWEntry<K, V>[] entries;
859 private final int startIndex;
860 private final int endIndex;
861 private final Comparator<? super K> keyComparator;
862 private final Comparator<Map.Entry<K, V>> comparator;
863
864
865 int getLength() {
866 return endIndex - startIndex;
867 }
868
869
870
871
872
873
874
875
876
877 int find(K needle) {
878 int begin = startIndex;
879 int end = endIndex - 1;
880
881 while (begin <= end) {
882 int mid = begin + ((end - begin) / 2);
883 K midKey = entries[ mid].key;
884 int compareRes = keyComparator.compare(midKey, needle);
885
886
887
888 if (compareRes == 0) {
889 return mid;
890 } else if (compareRes < 0) {
891
892
893 begin = mid + 1;
894 } else {
895
896
897 end = mid - 1;
898 }
899 }
900
901 return (-1 * begin) - 1;
902 }
903
904 ArrayHolder<K, V> replace(int index, COWEntry<K, V> newEntry) {
905
906 COWEntry<K, V>[] newEntries = entries.clone();
907 newEntries[index] = newEntry;
908 return new ArrayHolder<>(newEntries, startIndex, endIndex, keyComparator, comparator);
909 }
910
911 ArrayHolder<K, V> remove(int index) {
912 COWEntry<K,V>[] newEntries = new COWEntry[getLength() - 1];
913 System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex);
914 System.arraycopy(this.entries, index + 1, newEntries, index, entries.length - index - 1);
915 return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator);
916 }
917
918 ArrayHolder<K, V> insert(int index, COWEntry<K, V> newEntry) {
919 COWEntry<K,V>[] newEntries = new COWEntry[getLength() + 1];
920 System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex);
921 newEntries[index] = newEntry;
922 System.arraycopy(this.entries, index, newEntries, index + 1, getLength() - index);
923 return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator);
924 }
925
926 private ArrayHolder(
927 final Comparator<? super K> keyComparator,
928 final Comparator<Map.Entry<K, V>> comparator) {
929 this.endIndex = 0;
930 this.startIndex = 0;
931 this.entries = new COWEntry[] {};
932 this.keyComparator = keyComparator;
933 this.comparator = comparator;
934 }
935
936 private ArrayHolder(COWEntry[] entries,
937 int startIndex, int endIndex,
938 final Comparator<? super K> keyComparator,
939 Comparator<Map.Entry<K, V>> comparator) {
940 this.entries = entries;
941 this.startIndex = startIndex;
942 this.endIndex = endIndex;
943 this.keyComparator = keyComparator;
944 this.comparator = comparator;
945 }
946 }
947
948 private final static class COWEntry<K, V> implements Map.Entry<K, V> {
949 K key = null;
950 V value = null;
951
952 COWEntry(K key, V value) {
953 this.key = key;
954 this.value = value;
955 }
956
957 @Override
958 public K getKey() {
959 return key;
960 }
961
962 @Override
963 public V getValue() {
964 return value;
965 }
966
967 @Override
968 public V setValue(V value) {
969 V oldValue = this.value;
970 this.value = value;
971 return oldValue;
972 }
973 }
974 }