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