001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, software 013 * distributed under the License is distributed on an "AS IS" BASIS, 014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 015 * See the License for the specific language governing permissions and 016 * limitations under the License. 017 */ 018package org.apache.hadoop.hbase.types; 019 020import java.util.AbstractMap; 021import java.util.Collection; 022import java.util.Comparator; 023import java.util.Iterator; 024import java.util.Map; 025import java.util.NavigableSet; 026import java.util.NoSuchElementException; 027import java.util.Set; 028import java.util.SortedSet; 029import java.util.concurrent.ConcurrentNavigableMap; 030import org.apache.yetus.audience.InterfaceAudience; 031import org.apache.yetus.audience.InterfaceStability; 032 033/** 034 * A Map that keeps a sorted array in order to provide the concurrent map interface. Keeping a 035 * sorted array means that it's much more cache line friendly, making reads faster than the tree 036 * version. In order to make concurrent reads and writes safe this does a copy on write. There can 037 * only be one concurrent write at a time. 038 */ 039@InterfaceAudience.Private 040@InterfaceStability.Stable 041@SuppressWarnings({ "unchecked", "rawtypes", "hiding", "TypeParameterShadowing" }) 042public class CopyOnWriteArrayMap<K, V> extends AbstractMap<K, V> 043 implements Map<K, V>, ConcurrentNavigableMap<K, V> { 044 private final Comparator<? super K> keyComparator; 045 private volatile ArrayHolder<K, V> holder; 046 047 public CopyOnWriteArrayMap() { 048 this(new Comparator<K>() { 049 @Override 050 public int compare(K o1, K o2) { 051 return ((Comparable) o1).compareTo(o2); 052 } 053 }); 054 } 055 056 public CopyOnWriteArrayMap(final Comparator<? super K> keyComparator) { 057 this.keyComparator = keyComparator; 058 this.holder = new ArrayHolder<>(keyComparator, new Comparator<Entry<K, V>>() { 059 @Override 060 public int compare(Entry<K, V> o1, Entry<K, V> o2) { 061 return keyComparator.compare(o1.getKey(), o2.getKey()); 062 } 063 }); 064 } 065 066 private CopyOnWriteArrayMap(final Comparator<? super K> keyComparator, ArrayHolder<K, V> holder) { 067 this.keyComparator = keyComparator; 068 this.holder = holder; 069 } 070 071 /* 072 * Un synchronized read operations. No locking. No waiting No copying. These should all be FAST. 073 */ 074 075 @Override 076 public Comparator<? super K> comparator() { 077 return keyComparator; 078 } 079 080 @Override 081 public ConcurrentNavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 082 ArrayHolder<K, V> current = this.holder; 083 int index = current.find(fromKey); 084 085 if (!inclusive && index >= 0) { 086 index++; 087 } else if (index < 0) { 088 index = -(index + 1); 089 } 090 return new CopyOnWriteArrayMap<>(this.keyComparator, new ArrayHolder<>(current.entries, index, 091 current.endIndex, current.keyComparator, current.comparator)); 092 } 093 094 @Override 095 public ConcurrentNavigableMap<K, V> tailMap(K fromKey) { 096 return this.tailMap(fromKey, true); 097 } 098 099 @Override 100 public K firstKey() { 101 ArrayHolder<K, V> current = this.holder; 102 if (current.getLength() == 0) { 103 return null; 104 } 105 return current.entries[current.startIndex].getKey(); 106 } 107 108 @Override 109 public K lastKey() { 110 ArrayHolder<K, V> current = this.holder; 111 if (current.getLength() == 0) { 112 return null; 113 } 114 return current.entries[current.endIndex - 1].getKey(); 115 } 116 117 @Override 118 public Entry<K, V> lowerEntry(K key) { 119 ArrayHolder<K, V> current = this.holder; 120 if (current.getLength() == 0) { 121 return null; 122 } 123 124 int index = current.find(key); 125 126 // There's a key exactly equal. 127 if (index >= 0) { 128 index -= 1; 129 } else { 130 index = -(index + 1) - 1; 131 } 132 133 if (index < current.startIndex || index >= current.endIndex) { 134 return null; 135 } 136 return current.entries[index]; 137 } 138 139 @Override 140 public K lowerKey(K key) { 141 Map.Entry<K, V> entry = lowerEntry(key); 142 if (entry == null) { 143 return null; 144 } 145 return entry.getKey(); 146 } 147 148 @Override 149 public Entry<K, V> floorEntry(K key) { 150 ArrayHolder<K, V> current = this.holder; 151 if (current.getLength() == 0) { 152 return null; 153 } 154 int index = current.find(key); 155 if (index < 0) { 156 index = -(index + 1) - 1; 157 } 158 if (index < current.startIndex || index >= current.endIndex) { 159 return null; 160 } 161 162 return current.entries[index]; 163 } 164 165 @Override 166 public K floorKey(K key) { 167 Map.Entry<K, V> entry = floorEntry(key); 168 if (entry == null) { 169 return null; 170 } 171 return entry.getKey(); 172 } 173 174 @Override 175 public Entry<K, V> ceilingEntry(K key) { 176 ArrayHolder<K, V> current = this.holder; 177 if (current.getLength() == 0) { 178 return null; 179 } 180 int index = current.find(key); 181 if (index < 0) { 182 index = -(index + 1); 183 } 184 if (index < current.startIndex || index >= current.endIndex) { 185 return null; 186 } 187 188 return current.entries[index]; 189 } 190 191 @Override 192 public K ceilingKey(K key) { 193 Map.Entry<K, V> entry = ceilingEntry(key); 194 if (entry == null) { 195 return null; 196 } 197 return entry.getKey(); 198 } 199 200 @Override 201 public Entry<K, V> higherEntry(K key) { 202 ArrayHolder<K, V> current = this.holder; 203 if (current.getLength() == 0) { 204 return null; 205 } 206 int index = current.find(key); 207 208 // There's a key exactly equal. 209 if (index >= 0) { 210 index += 1; 211 } else { 212 index = -(index + 1); 213 } 214 215 if (index < current.startIndex || index >= current.endIndex) { 216 return null; 217 } 218 return current.entries[index]; 219 } 220 221 @Override 222 public K higherKey(K key) { 223 Map.Entry<K, V> entry = higherEntry(key); 224 if (entry == null) { 225 return null; 226 } 227 return entry.getKey(); 228 } 229 230 @Override 231 public Entry<K, V> firstEntry() { 232 ArrayHolder<K, V> current = this.holder; 233 if (current.getLength() == 0) { 234 return null; 235 } 236 return current.entries[current.startIndex]; 237 } 238 239 @Override 240 public Entry<K, V> lastEntry() { 241 ArrayHolder<K, V> current = this.holder; 242 if (current.getLength() == 0) { 243 return null; 244 } 245 return current.entries[current.endIndex - 1]; 246 } 247 248 @Override 249 public int size() { 250 return holder.getLength(); 251 } 252 253 @Override 254 public boolean isEmpty() { 255 return holder.getLength() == 0; 256 } 257 258 @Override 259 public boolean containsKey(Object key) { 260 ArrayHolder<K, V> current = this.holder; 261 int index = current.find((K) key); 262 return index >= 0; 263 } 264 265 @Override 266 public V get(Object key) { 267 268 ArrayHolder<K, V> current = this.holder; 269 int index = current.find((K) key); 270 if (index >= 0) { 271 return current.entries[index].getValue(); 272 } 273 return null; 274 } 275 276 @Override 277 public NavigableSet<K> keySet() { 278 return new ArrayKeySet<>(this.holder); 279 } 280 281 @Override 282 public Collection<V> values() { 283 return new ArrayValueCollection<>(this.holder); 284 } 285 286 @Override 287 public Set<Entry<K, V>> entrySet() { 288 return new ArrayEntrySet<>(this.holder); 289 } 290 291 /* 292 * Synchronized write methods. Every method should be synchronized. Only one modification at a 293 * time. These will be slow. 294 */ 295 296 @Override 297 public synchronized V put(K key, V value) { 298 ArrayHolder<K, V> current = this.holder; 299 int index = current.find(key); 300 COWEntry<K, V> newEntry = new COWEntry<>(key, value); 301 if (index >= 0) { 302 this.holder = current.replace(index, newEntry); 303 return current.entries[index].getValue(); 304 } else { 305 this.holder = current.insert(-(index + 1), newEntry); 306 } 307 return null; 308 } 309 310 @Override 311 public synchronized V remove(Object key) { 312 313 ArrayHolder<K, V> current = this.holder; 314 int index = current.find((K) key); 315 if (index >= 0) { 316 this.holder = current.remove(index); 317 return current.entries[index].getValue(); 318 } 319 return null; 320 } 321 322 @Override 323 public synchronized void clear() { 324 this.holder = new ArrayHolder<>(this.holder.keyComparator, this.holder.comparator); 325 } 326 327 @Override 328 public synchronized V putIfAbsent(K key, V value) { 329 ArrayHolder<K, V> current = this.holder; 330 int index = current.find(key); 331 332 if (index < 0) { 333 COWEntry<K, V> newEntry = new COWEntry<>(key, value); 334 this.holder = current.insert(-(index + 1), newEntry); 335 return value; 336 } 337 return current.entries[index].getValue(); 338 } 339 340 @Override 341 public synchronized boolean remove(Object key, Object value) { 342 ArrayHolder<K, V> current = this.holder; 343 int index = current.find((K) key); 344 345 if (index >= 0 && current.entries[index].getValue().equals(value)) { 346 this.holder = current.remove(index); 347 return true; 348 } 349 return false; 350 } 351 352 @Override 353 public synchronized boolean replace(K key, V oldValue, V newValue) { 354 ArrayHolder<K, V> current = this.holder; 355 int index = current.find(key); 356 357 if (index >= 0 && current.entries[index].getValue().equals(oldValue)) { 358 COWEntry<K, V> newEntry = new COWEntry<>(key, newValue); 359 this.holder = current.replace(index, newEntry); 360 return true; 361 } 362 return false; 363 } 364 365 @Override 366 public synchronized V replace(K key, V value) { 367 ArrayHolder<K, V> current = this.holder; 368 int index = current.find(key); 369 370 if (index >= 0) { 371 COWEntry<K, V> newEntry = new COWEntry<>(key, value); 372 this.holder = current.replace(index, newEntry); 373 return current.entries[index].getValue(); 374 } 375 return null; 376 } 377 378 @Override 379 public Entry<K, V> pollFirstEntry() { 380 throw new UnsupportedOperationException(); 381 } 382 383 @Override 384 public Entry<K, V> pollLastEntry() { 385 throw new UnsupportedOperationException(); 386 } 387 388 @Override 389 public ConcurrentNavigableMap<K, V> descendingMap() { 390 throw new UnsupportedOperationException(); 391 } 392 393 @Override 394 public NavigableSet<K> navigableKeySet() { 395 throw new UnsupportedOperationException(); 396 } 397 398 @Override 399 public ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey) { 400 throw new UnsupportedOperationException(); 401 } 402 403 @Override 404 public ConcurrentNavigableMap<K, V> headMap(K toKey) { 405 throw new UnsupportedOperationException(); 406 } 407 408 @Override 409 public ConcurrentNavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, 410 boolean toInclusive) { 411 throw new UnsupportedOperationException(); 412 } 413 414 @Override 415 public ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive) { 416 throw new UnsupportedOperationException(); 417 } 418 419 @Override 420 public NavigableSet<K> descendingKeySet() { 421 throw new UnsupportedOperationException(); 422 } 423 424 private final class ArrayKeySet<K, V> implements NavigableSet<K> { 425 426 private final ArrayHolder<K, V> holder; 427 428 private ArrayKeySet(ArrayHolder<K, V> holder) { 429 this.holder = holder; 430 } 431 432 @Override 433 public int size() { 434 return holder.getLength(); 435 } 436 437 @Override 438 public boolean isEmpty() { 439 return holder.getLength() == 0; 440 } 441 442 @Override 443 public boolean contains(Object o) { 444 ArrayHolder<K, V> current = this.holder; 445 446 for (int i = current.startIndex; i < current.endIndex; i++) { 447 if (current.entries[i].getValue().equals(o)) { 448 return true; 449 } 450 } 451 return false; 452 } 453 454 @Override 455 public K lower(K k) { 456 throw new UnsupportedOperationException(); 457 } 458 459 @Override 460 public K floor(K k) { 461 throw new UnsupportedOperationException(); 462 } 463 464 @Override 465 public K ceiling(K k) { 466 throw new UnsupportedOperationException(); 467 } 468 469 @Override 470 public K higher(K k) { 471 throw new UnsupportedOperationException(); 472 } 473 474 @Override 475 public K pollFirst() { 476 throw new UnsupportedOperationException(); 477 } 478 479 @Override 480 public K pollLast() { 481 throw new UnsupportedOperationException(); 482 } 483 484 @Override 485 public Iterator<K> iterator() { 486 return new ArrayKeyIterator<>(this.holder); 487 } 488 489 @Override 490 public NavigableSet<K> descendingSet() { 491 throw new UnsupportedOperationException(); 492 } 493 494 @Override 495 public Iterator<K> descendingIterator() { 496 throw new UnsupportedOperationException(); 497 } 498 499 @Override 500 public NavigableSet<K> subSet(K fromElement, boolean fromInclusive, K toElement, 501 boolean toInclusive) { 502 throw new UnsupportedOperationException(); 503 } 504 505 @Override 506 public NavigableSet<K> headSet(K toElement, boolean inclusive) { 507 throw new UnsupportedOperationException(); 508 } 509 510 @Override 511 public NavigableSet<K> tailSet(K fromElement, boolean inclusive) { 512 throw new UnsupportedOperationException(); 513 } 514 515 @Override 516 public Comparator<? super K> comparator() { 517 return (Comparator<? super K>) keyComparator; 518 } 519 520 @Override 521 public SortedSet<K> subSet(K fromElement, K toElement) { 522 return null; 523 } 524 525 @Override 526 public SortedSet<K> headSet(K toElement) { 527 return null; 528 } 529 530 @Override 531 public SortedSet<K> tailSet(K fromElement) { 532 return null; 533 } 534 535 @Override 536 public K first() { 537 ArrayHolder<K, V> current = this.holder; 538 if (current.getLength() == 0) { 539 return null; 540 } 541 return current.entries[current.startIndex].getKey(); 542 } 543 544 @Override 545 public K last() { 546 ArrayHolder<K, V> current = this.holder; 547 if (current.getLength() == 0) { 548 return null; 549 } 550 return current.entries[current.endIndex - 1].getKey(); 551 } 552 553 @Override 554 public Object[] toArray() { 555 throw new UnsupportedOperationException(); 556 } 557 558 @Override 559 public <T> T[] toArray(T[] a) { 560 throw new UnsupportedOperationException(); 561 } 562 563 @Override 564 public boolean add(K k) { 565 throw new UnsupportedOperationException(); 566 } 567 568 @Override 569 public boolean remove(Object o) { 570 throw new UnsupportedOperationException(); 571 } 572 573 @Override 574 public boolean containsAll(Collection<?> c) { 575 throw new UnsupportedOperationException(); 576 } 577 578 @Override 579 public boolean addAll(Collection<? extends K> c) { 580 throw new UnsupportedOperationException(); 581 } 582 583 @Override 584 public boolean retainAll(Collection<?> c) { 585 throw new UnsupportedOperationException(); 586 } 587 588 @Override 589 public boolean removeAll(Collection<?> c) { 590 throw new UnsupportedOperationException(); 591 } 592 593 @Override 594 public void clear() { 595 throw new UnsupportedOperationException(); 596 } 597 } 598 599 private final class ArrayValueCollection<K, V> implements Collection<V> { 600 601 private final ArrayHolder<K, V> holder; 602 603 private ArrayValueCollection(ArrayHolder<K, V> holder) { 604 this.holder = holder; 605 } 606 607 @Override 608 public int size() { 609 return holder.getLength(); 610 } 611 612 @Override 613 public boolean isEmpty() { 614 return holder.getLength() == 0; 615 } 616 617 @Override 618 public boolean contains(Object o) { 619 throw new UnsupportedOperationException(); 620 } 621 622 @Override 623 public Iterator<V> iterator() { 624 return new ArrayValueIterator<>(this.holder); 625 } 626 627 @Override 628 public Object[] toArray() { 629 throw new UnsupportedOperationException(); 630 } 631 632 @Override 633 public <T> T[] toArray(T[] a) { 634 throw new UnsupportedOperationException(); 635 } 636 637 @Override 638 public boolean add(V v) { 639 throw new UnsupportedOperationException(); 640 } 641 642 @Override 643 public boolean remove(Object o) { 644 throw new UnsupportedOperationException(); 645 } 646 647 @Override 648 public boolean containsAll(Collection<?> c) { 649 throw new UnsupportedOperationException(); 650 } 651 652 @Override 653 public boolean addAll(Collection<? extends V> c) { 654 throw new UnsupportedOperationException(); 655 } 656 657 @Override 658 public boolean removeAll(Collection<?> c) { 659 throw new UnsupportedOperationException(); 660 } 661 662 @Override 663 public boolean retainAll(Collection<?> c) { 664 throw new UnsupportedOperationException(); 665 } 666 667 @Override 668 public void clear() { 669 throw new UnsupportedOperationException(); 670 } 671 672 @Override 673 @edu.umd.cs.findbugs.annotations.SuppressWarnings(value = "EQ_ALWAYS_FALSE", 674 justification = "Intentional") 675 public boolean equals(Object o) { 676 return false; // FindBugs: Causes EQ_ALWAYS_FALSE. Suppressed. 677 } 678 679 @Override 680 public int hashCode() { 681 return 0; 682 } 683 } 684 685 private static final class ArrayKeyIterator<K, V> implements Iterator<K> { 686 int index; 687 private final ArrayHolder<K, V> holder; 688 689 private ArrayKeyIterator(ArrayHolder<K, V> holder) { 690 this.holder = holder; 691 index = holder.startIndex; 692 } 693 694 @Override 695 public boolean hasNext() { 696 return index < holder.endIndex; 697 } 698 699 @Override 700 public K next() { 701 return holder.entries[index++].getKey(); 702 } 703 704 @Override 705 public void remove() { 706 throw new UnsupportedOperationException("remove"); 707 } 708 } 709 710 private static final class ArrayValueIterator<K, V> implements Iterator<V> { 711 int index; 712 private final ArrayHolder<K, V> holder; 713 714 private ArrayValueIterator(ArrayHolder<K, V> holder) { 715 this.holder = holder; 716 index = holder.startIndex; 717 } 718 719 @Override 720 public boolean hasNext() { 721 return index < holder.endIndex; 722 } 723 724 @Override 725 public V next() { 726 return holder.entries[index++].getValue(); 727 } 728 729 @Override 730 public void remove() { 731 throw new UnsupportedOperationException("remove"); 732 } 733 } 734 735 private static final class ArrayEntryIterator<K, V> implements Iterator<Map.Entry<K, V>> { 736 737 int index; 738 private final ArrayHolder<K, V> holder; 739 740 private ArrayEntryIterator(ArrayHolder<K, V> holder) { 741 this.holder = holder; 742 this.index = holder.startIndex; 743 } 744 745 @Override 746 public boolean hasNext() { 747 return index < holder.endIndex; 748 } 749 750 @Override 751 @edu.umd.cs.findbugs.annotations.SuppressWarnings(value = "IT_NO_SUCH_ELEMENT", 752 justification = "Intentional") 753 public Entry<K, V> next() { 754 if (!hasNext()) { 755 throw new NoSuchElementException(); 756 } 757 return holder.entries[index++]; 758 } 759 760 @Override 761 public void remove() { 762 throw new UnsupportedOperationException("remove"); 763 } 764 } 765 766 private final class ArrayEntrySet<K, V> implements Set<Map.Entry<K, V>> { 767 private final ArrayHolder<K, V> holder; 768 769 private ArrayEntrySet(ArrayHolder<K, V> holder) { 770 this.holder = holder; 771 } 772 773 @Override 774 public int size() { 775 return holder.getLength(); 776 } 777 778 @Override 779 public boolean isEmpty() { 780 return holder.getLength() == 0; 781 } 782 783 @Override 784 public boolean contains(Object o) { 785 return false; 786 } 787 788 @Override 789 public Iterator<Entry<K, V>> iterator() { 790 return new ArrayEntryIterator<>(this.holder); 791 } 792 793 @Override 794 public Object[] toArray() { 795 throw new UnsupportedOperationException(); 796 } 797 798 @Override 799 public <T> T[] toArray(T[] a) { 800 throw new UnsupportedOperationException(); 801 } 802 803 @Override 804 public boolean add(Entry<K, V> kvEntry) { 805 throw new UnsupportedOperationException(); 806 } 807 808 @Override 809 public boolean remove(Object o) { 810 throw new UnsupportedOperationException(); 811 } 812 813 @Override 814 public boolean containsAll(Collection<?> c) { 815 throw new UnsupportedOperationException(); 816 } 817 818 @Override 819 public boolean addAll(Collection<? extends Entry<K, V>> c) { 820 throw new UnsupportedOperationException(); 821 } 822 823 @Override 824 public boolean retainAll(Collection<?> c) { 825 throw new UnsupportedOperationException(); 826 } 827 828 @Override 829 public boolean removeAll(Collection<?> c) { 830 throw new UnsupportedOperationException(); 831 } 832 833 @Override 834 public void clear() { 835 throw new UnsupportedOperationException(); 836 } 837 } 838 839 private final static class ArrayHolder<K, V> { 840 private final COWEntry<K, V>[] entries; 841 private final int startIndex; 842 private final int endIndex; 843 private final Comparator<? super K> keyComparator; 844 private final Comparator<Map.Entry<K, V>> comparator; 845 846 int getLength() { 847 return endIndex - startIndex; 848 } 849 850 /** 851 * Binary search for a given key 852 * @param needle The key to look for in all of the entries 853 * @return Same return value as Arrays.binarySearch. Positive numbers mean the index. Otherwise 854 * (-1 * insertion point) - 1 855 */ 856 int find(K needle) { 857 int begin = startIndex; 858 int end = endIndex - 1; 859 860 while (begin <= end) { 861 int mid = begin + ((end - begin) / 2); 862 K midKey = entries[mid].key; 863 int compareRes = keyComparator.compare(midKey, needle); 864 865 // 0 means equals 866 // We found the key. 867 if (compareRes == 0) { 868 return mid; 869 } else if (compareRes < 0) { 870 // midKey is less than needle so we need 871 // to look at farther up 872 begin = mid + 1; 873 } else { 874 // midKey is greater than needle so we 875 // need to look down. 876 end = mid - 1; 877 } 878 } 879 880 return (-1 * begin) - 1; 881 } 882 883 ArrayHolder<K, V> replace(int index, COWEntry<K, V> newEntry) { 884 // TODO should this restart the array back at start index 0 ? 885 COWEntry<K, V>[] newEntries = entries.clone(); 886 newEntries[index] = newEntry; 887 return new ArrayHolder<>(newEntries, startIndex, endIndex, keyComparator, comparator); 888 } 889 890 ArrayHolder<K, V> remove(int index) { 891 COWEntry<K, V>[] newEntries = new COWEntry[getLength() - 1]; 892 System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex); 893 System.arraycopy(this.entries, index + 1, newEntries, index, entries.length - index - 1); 894 return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator); 895 } 896 897 ArrayHolder<K, V> insert(int index, COWEntry<K, V> newEntry) { 898 COWEntry<K, V>[] newEntries = new COWEntry[getLength() + 1]; 899 System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex); 900 newEntries[index] = newEntry; 901 System.arraycopy(this.entries, index, newEntries, index + 1, getLength() - index); 902 return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator); 903 } 904 905 private ArrayHolder(final Comparator<? super K> keyComparator, 906 final Comparator<Map.Entry<K, V>> comparator) { 907 this.endIndex = 0; 908 this.startIndex = 0; 909 this.entries = new COWEntry[] {}; 910 this.keyComparator = keyComparator; 911 this.comparator = comparator; 912 } 913 914 private ArrayHolder(COWEntry[] entries, int startIndex, int endIndex, 915 final Comparator<? super K> keyComparator, Comparator<Map.Entry<K, V>> comparator) { 916 this.entries = entries; 917 this.startIndex = startIndex; 918 this.endIndex = endIndex; 919 this.keyComparator = keyComparator; 920 this.comparator = comparator; 921 } 922 } 923 924 private final static class COWEntry<K, V> implements Map.Entry<K, V> { 925 K key = null; 926 V value = null; 927 928 COWEntry(K key, V value) { 929 this.key = key; 930 this.value = value; 931 } 932 933 @Override 934 public K getKey() { 935 return key; 936 } 937 938 @Override 939 public V getValue() { 940 return value; 941 } 942 943 @Override 944 public V setValue(V value) { 945 V oldValue = this.value; 946 this.value = value; 947 return oldValue; 948 } 949 } 950}