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 */ 018 019package org.apache.hadoop.hbase.types; 020 021import java.util.AbstractMap; 022import java.util.Collection; 023import java.util.Comparator; 024import java.util.Iterator; 025import java.util.Map; 026import java.util.NavigableSet; 027import java.util.NoSuchElementException; 028import java.util.Set; 029import java.util.SortedSet; 030import java.util.concurrent.ConcurrentNavigableMap; 031 032import org.apache.yetus.audience.InterfaceAudience; 033import org.apache.yetus.audience.InterfaceStability; 034 035/** 036 * A Map that keeps a sorted array in order to provide the concurrent map interface. 037 * Keeping a sorted array means that it's much more cache line friendly, making reads faster 038 * than the tree version. 039 * 040 * In order to make concurrent reads and writes safe this does a copy on write. 041 * There can only be one concurrent write at a time. 042 */ 043@InterfaceAudience.Private 044@InterfaceStability.Stable 045public class CopyOnWriteArrayMap<K, V> extends AbstractMap<K, V> 046 implements Map<K, V>, ConcurrentNavigableMap<K, V> { 047 private final Comparator<? super K> keyComparator; 048 private volatile ArrayHolder<K, V> holder; 049 050 public CopyOnWriteArrayMap() { 051 this(new Comparator<K>() { 052 @Override 053 public int compare(K o1, K o2) { 054 return ((Comparable) o1).compareTo(o2); 055 } 056 }); 057 } 058 059 public CopyOnWriteArrayMap(final Comparator<? super K> keyComparator) { 060 this.keyComparator = keyComparator; 061 this.holder = new ArrayHolder<>(keyComparator, new Comparator<Entry<K, V>>() { 062 @Override 063 public int compare(Entry<K, V> o1, Entry<K, V> o2) { 064 return keyComparator.compare(o1.getKey(), o2.getKey()); 065 } 066 }); 067 } 068 069 private CopyOnWriteArrayMap(final Comparator<? super K> keyComparator, ArrayHolder<K, V> holder) { 070 this.keyComparator = keyComparator; 071 this.holder = holder; 072 } 073 074 /* 075 Un synchronized read operations. 076 077 No locking. 078 No waiting 079 No copying. 080 081 These should all be FAST. 082 */ 083 084 @Override 085 public Comparator<? super K> comparator() { 086 return keyComparator; 087 } 088 089 @Override 090 public ConcurrentNavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 091 ArrayHolder<K, V> current = this.holder; 092 int index = current.find(fromKey); 093 094 if (!inclusive && index >= 0) { 095 index++; 096 } else if (index < 0) { 097 index = -(index + 1); 098 } 099 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 // There's a key exactly equal. 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 // There's a key exactly equal. 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 Synchronized write methods. 308 309 Every method should be synchronized. 310 Only one modification at a time. 311 312 These will be slow. 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; // FindBugs: Causes EQ_ALWAYS_FALSE. Suppressed. 701 } 702 703 @Override 704 public int hashCode() { 705 return 0; 706 } 707 } 708 709 private static 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 static 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 static 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 * Binary search for a given key 880 * @param needle The key to look for in all of the entries 881 * @return Same return value as Arrays.binarySearch. 882 * Positive numbers mean the index. Otherwise (-1 * insertion point) - 1 883 */ 884 int find(K needle) { 885 int begin = startIndex; 886 int end = endIndex - 1; 887 888 while (begin <= end) { 889 int mid = begin + ((end - begin) / 2); 890 K midKey = entries[ mid].key; 891 int compareRes = keyComparator.compare(midKey, needle); 892 893 // 0 means equals 894 // We found the key. 895 if (compareRes == 0) { 896 return mid; 897 } else if (compareRes < 0) { 898 // midKey is less than needle so we need 899 // to look at farther up 900 begin = mid + 1; 901 } else { 902 // midKey is greater than needle so we 903 // need to look down. 904 end = mid - 1; 905 } 906 } 907 908 return (-1 * begin) - 1; 909 } 910 911 ArrayHolder<K, V> replace(int index, COWEntry<K, V> newEntry) { 912 // TODO should this restart the array back at start index 0 ? 913 COWEntry<K, V>[] newEntries = entries.clone(); 914 newEntries[index] = newEntry; 915 return new ArrayHolder<>(newEntries, startIndex, endIndex, keyComparator, comparator); 916 } 917 918 ArrayHolder<K, V> remove(int index) { 919 COWEntry<K,V>[] newEntries = new COWEntry[getLength() - 1]; 920 System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex); 921 System.arraycopy(this.entries, index + 1, newEntries, index, entries.length - index - 1); 922 return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator); 923 } 924 925 ArrayHolder<K, V> insert(int index, COWEntry<K, V> newEntry) { 926 COWEntry<K,V>[] newEntries = new COWEntry[getLength() + 1]; 927 System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex); 928 newEntries[index] = newEntry; 929 System.arraycopy(this.entries, index, newEntries, index + 1, getLength() - index); 930 return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator); 931 } 932 933 private ArrayHolder( 934 final Comparator<? super K> keyComparator, 935 final Comparator<Map.Entry<K, V>> comparator) { 936 this.endIndex = 0; 937 this.startIndex = 0; 938 this.entries = new COWEntry[] {}; 939 this.keyComparator = keyComparator; 940 this.comparator = comparator; 941 } 942 943 private ArrayHolder(COWEntry[] entries, 944 int startIndex, int endIndex, 945 final Comparator<? super K> keyComparator, 946 Comparator<Map.Entry<K, V>> comparator) { 947 this.entries = entries; 948 this.startIndex = startIndex; 949 this.endIndex = endIndex; 950 this.keyComparator = keyComparator; 951 this.comparator = comparator; 952 } 953 } 954 955 private final static class COWEntry<K, V> implements Map.Entry<K, V> { 956 K key = null; 957 V value = null; 958 959 COWEntry(K key, V value) { 960 this.key = key; 961 this.value = value; 962 } 963 964 @Override 965 public K getKey() { 966 return key; 967 } 968 969 @Override 970 public V getValue() { 971 return value; 972 } 973 974 @Override 975 public V setValue(V value) { 976 V oldValue = this.value; 977 this.value = value; 978 return oldValue; 979 } 980 } 981}