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