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}