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      // putIfAbsent contract requires returning null if no previous entry exists
336      return null;
337    }
338    return current.entries[index].getValue();
339  }
340
341  @Override
342  public synchronized boolean remove(Object key, Object value) {
343    ArrayHolder<K, V> current = this.holder;
344    int index = current.find((K) key);
345
346    if (index >= 0 && current.entries[index].getValue().equals(value)) {
347      this.holder = current.remove(index);
348      return true;
349    }
350    return false;
351  }
352
353  @Override
354  public synchronized boolean replace(K key, V oldValue, V newValue) {
355    ArrayHolder<K, V> current = this.holder;
356    int index = current.find(key);
357
358    if (index >= 0 && current.entries[index].getValue().equals(oldValue)) {
359      COWEntry<K, V> newEntry = new COWEntry<>(key, newValue);
360      this.holder = current.replace(index, newEntry);
361      return true;
362    }
363    return false;
364  }
365
366  @Override
367  public synchronized V replace(K key, V value) {
368    ArrayHolder<K, V> current = this.holder;
369    int index = current.find(key);
370
371    if (index >= 0) {
372      COWEntry<K, V> newEntry = new COWEntry<>(key, value);
373      this.holder = current.replace(index, newEntry);
374      return current.entries[index].getValue();
375    }
376    return null;
377  }
378
379  @Override
380  public Entry<K, V> pollFirstEntry() {
381    throw new UnsupportedOperationException();
382  }
383
384  @Override
385  public Entry<K, V> pollLastEntry() {
386    throw new UnsupportedOperationException();
387  }
388
389  @Override
390  public ConcurrentNavigableMap<K, V> descendingMap() {
391    throw new UnsupportedOperationException();
392  }
393
394  @Override
395  public NavigableSet<K> navigableKeySet() {
396    throw new UnsupportedOperationException();
397  }
398
399  @Override
400  public ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey) {
401    throw new UnsupportedOperationException();
402  }
403
404  @Override
405  public ConcurrentNavigableMap<K, V> headMap(K toKey) {
406    throw new UnsupportedOperationException();
407  }
408
409  @Override
410  public ConcurrentNavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey,
411    boolean toInclusive) {
412    throw new UnsupportedOperationException();
413  }
414
415  @Override
416  public ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive) {
417    throw new UnsupportedOperationException();
418  }
419
420  @Override
421  public NavigableSet<K> descendingKeySet() {
422    throw new UnsupportedOperationException();
423  }
424
425  private final class ArrayKeySet<K, V> implements NavigableSet<K> {
426
427    private final ArrayHolder<K, V> holder;
428
429    private ArrayKeySet(ArrayHolder<K, V> holder) {
430      this.holder = holder;
431    }
432
433    @Override
434    public int size() {
435      return holder.getLength();
436    }
437
438    @Override
439    public boolean isEmpty() {
440      return holder.getLength() == 0;
441    }
442
443    @Override
444    public boolean contains(Object o) {
445      ArrayHolder<K, V> current = this.holder;
446
447      for (int i = current.startIndex; i < current.endIndex; i++) {
448        if (current.entries[i].getValue().equals(o)) {
449          return true;
450        }
451      }
452      return false;
453    }
454
455    @Override
456    public K lower(K k) {
457      throw new UnsupportedOperationException();
458    }
459
460    @Override
461    public K floor(K k) {
462      throw new UnsupportedOperationException();
463    }
464
465    @Override
466    public K ceiling(K k) {
467      throw new UnsupportedOperationException();
468    }
469
470    @Override
471    public K higher(K k) {
472      throw new UnsupportedOperationException();
473    }
474
475    @Override
476    public K pollFirst() {
477      throw new UnsupportedOperationException();
478    }
479
480    @Override
481    public K pollLast() {
482      throw new UnsupportedOperationException();
483    }
484
485    @Override
486    public Iterator<K> iterator() {
487      return new ArrayKeyIterator<>(this.holder);
488    }
489
490    @Override
491    public NavigableSet<K> descendingSet() {
492      throw new UnsupportedOperationException();
493    }
494
495    @Override
496    public Iterator<K> descendingIterator() {
497      throw new UnsupportedOperationException();
498    }
499
500    @Override
501    public NavigableSet<K> subSet(K fromElement, boolean fromInclusive, K toElement,
502      boolean toInclusive) {
503      throw new UnsupportedOperationException();
504    }
505
506    @Override
507    public NavigableSet<K> headSet(K toElement, boolean inclusive) {
508      throw new UnsupportedOperationException();
509    }
510
511    @Override
512    public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
513      throw new UnsupportedOperationException();
514    }
515
516    @Override
517    public Comparator<? super K> comparator() {
518      return (Comparator<? super K>) keyComparator;
519    }
520
521    @Override
522    public SortedSet<K> subSet(K fromElement, K toElement) {
523      return null;
524    }
525
526    @Override
527    public SortedSet<K> headSet(K toElement) {
528      return null;
529    }
530
531    @Override
532    public SortedSet<K> tailSet(K fromElement) {
533      return null;
534    }
535
536    @Override
537    public K first() {
538      ArrayHolder<K, V> current = this.holder;
539      if (current.getLength() == 0) {
540        return null;
541      }
542      return current.entries[current.startIndex].getKey();
543    }
544
545    @Override
546    public K last() {
547      ArrayHolder<K, V> current = this.holder;
548      if (current.getLength() == 0) {
549        return null;
550      }
551      return current.entries[current.endIndex - 1].getKey();
552    }
553
554    @Override
555    public Object[] toArray() {
556      throw new UnsupportedOperationException();
557    }
558
559    @Override
560    public <T> T[] toArray(T[] a) {
561      throw new UnsupportedOperationException();
562    }
563
564    @Override
565    public boolean add(K k) {
566      throw new UnsupportedOperationException();
567    }
568
569    @Override
570    public boolean remove(Object o) {
571      throw new UnsupportedOperationException();
572    }
573
574    @Override
575    public boolean containsAll(Collection<?> c) {
576      throw new UnsupportedOperationException();
577    }
578
579    @Override
580    public boolean addAll(Collection<? extends K> c) {
581      throw new UnsupportedOperationException();
582    }
583
584    @Override
585    public boolean retainAll(Collection<?> c) {
586      throw new UnsupportedOperationException();
587    }
588
589    @Override
590    public boolean removeAll(Collection<?> c) {
591      throw new UnsupportedOperationException();
592    }
593
594    @Override
595    public void clear() {
596      throw new UnsupportedOperationException();
597    }
598  }
599
600  private final class ArrayValueCollection<K, V> implements Collection<V> {
601
602    private final ArrayHolder<K, V> holder;
603
604    private ArrayValueCollection(ArrayHolder<K, V> holder) {
605      this.holder = holder;
606    }
607
608    @Override
609    public int size() {
610      return holder.getLength();
611    }
612
613    @Override
614    public boolean isEmpty() {
615      return holder.getLength() == 0;
616    }
617
618    @Override
619    public boolean contains(Object o) {
620      throw new UnsupportedOperationException();
621    }
622
623    @Override
624    public Iterator<V> iterator() {
625      return new ArrayValueIterator<>(this.holder);
626    }
627
628    @Override
629    public Object[] toArray() {
630      throw new UnsupportedOperationException();
631    }
632
633    @Override
634    public <T> T[] toArray(T[] a) {
635      throw new UnsupportedOperationException();
636    }
637
638    @Override
639    public boolean add(V v) {
640      throw new UnsupportedOperationException();
641    }
642
643    @Override
644    public boolean remove(Object o) {
645      throw new UnsupportedOperationException();
646    }
647
648    @Override
649    public boolean containsAll(Collection<?> c) {
650      throw new UnsupportedOperationException();
651    }
652
653    @Override
654    public boolean addAll(Collection<? extends V> c) {
655      throw new UnsupportedOperationException();
656    }
657
658    @Override
659    public boolean removeAll(Collection<?> c) {
660      throw new UnsupportedOperationException();
661    }
662
663    @Override
664    public boolean retainAll(Collection<?> c) {
665      throw new UnsupportedOperationException();
666    }
667
668    @Override
669    public void clear() {
670      throw new UnsupportedOperationException();
671    }
672
673    @Override
674    @edu.umd.cs.findbugs.annotations.SuppressWarnings(value = "EQ_ALWAYS_FALSE",
675        justification = "Intentional")
676    public boolean equals(Object o) {
677      return false; // FindBugs: Causes EQ_ALWAYS_FALSE. Suppressed.
678    }
679
680    @Override
681    public int hashCode() {
682      return 0;
683    }
684  }
685
686  private static final class ArrayKeyIterator<K, V> implements Iterator<K> {
687    int index;
688    private final ArrayHolder<K, V> holder;
689
690    private ArrayKeyIterator(ArrayHolder<K, V> holder) {
691      this.holder = holder;
692      index = holder.startIndex;
693    }
694
695    @Override
696    public boolean hasNext() {
697      return index < holder.endIndex;
698    }
699
700    @Override
701    public K next() {
702      return holder.entries[index++].getKey();
703    }
704
705    @Override
706    public void remove() {
707      throw new UnsupportedOperationException("remove");
708    }
709  }
710
711  private static final class ArrayValueIterator<K, V> implements Iterator<V> {
712    int index;
713    private final ArrayHolder<K, V> holder;
714
715    private ArrayValueIterator(ArrayHolder<K, V> holder) {
716      this.holder = holder;
717      index = holder.startIndex;
718    }
719
720    @Override
721    public boolean hasNext() {
722      return index < holder.endIndex;
723    }
724
725    @Override
726    public V next() {
727      return holder.entries[index++].getValue();
728    }
729
730    @Override
731    public void remove() {
732      throw new UnsupportedOperationException("remove");
733    }
734  }
735
736  private static final class ArrayEntryIterator<K, V> implements Iterator<Map.Entry<K, V>> {
737
738    int index;
739    private final ArrayHolder<K, V> holder;
740
741    private ArrayEntryIterator(ArrayHolder<K, V> holder) {
742      this.holder = holder;
743      this.index = holder.startIndex;
744    }
745
746    @Override
747    public boolean hasNext() {
748      return index < holder.endIndex;
749    }
750
751    @Override
752    @edu.umd.cs.findbugs.annotations.SuppressWarnings(value = "IT_NO_SUCH_ELEMENT",
753        justification = "Intentional")
754    public Entry<K, V> next() {
755      if (!hasNext()) {
756        throw new NoSuchElementException();
757      }
758      return holder.entries[index++];
759    }
760
761    @Override
762    public void remove() {
763      throw new UnsupportedOperationException("remove");
764    }
765  }
766
767  private final class ArrayEntrySet<K, V> implements Set<Map.Entry<K, V>> {
768    private final ArrayHolder<K, V> holder;
769
770    private ArrayEntrySet(ArrayHolder<K, V> holder) {
771      this.holder = holder;
772    }
773
774    @Override
775    public int size() {
776      return holder.getLength();
777    }
778
779    @Override
780    public boolean isEmpty() {
781      return holder.getLength() == 0;
782    }
783
784    @Override
785    public boolean contains(Object o) {
786      return false;
787    }
788
789    @Override
790    public Iterator<Entry<K, V>> iterator() {
791      return new ArrayEntryIterator<>(this.holder);
792    }
793
794    @Override
795    public Object[] toArray() {
796      throw new UnsupportedOperationException();
797    }
798
799    @Override
800    public <T> T[] toArray(T[] a) {
801      throw new UnsupportedOperationException();
802    }
803
804    @Override
805    public boolean add(Entry<K, V> kvEntry) {
806      throw new UnsupportedOperationException();
807    }
808
809    @Override
810    public boolean remove(Object o) {
811      throw new UnsupportedOperationException();
812    }
813
814    @Override
815    public boolean containsAll(Collection<?> c) {
816      throw new UnsupportedOperationException();
817    }
818
819    @Override
820    public boolean addAll(Collection<? extends Entry<K, V>> c) {
821      throw new UnsupportedOperationException();
822    }
823
824    @Override
825    public boolean retainAll(Collection<?> c) {
826      throw new UnsupportedOperationException();
827    }
828
829    @Override
830    public boolean removeAll(Collection<?> c) {
831      throw new UnsupportedOperationException();
832    }
833
834    @Override
835    public void clear() {
836      throw new UnsupportedOperationException();
837    }
838  }
839
840  private final static class ArrayHolder<K, V> {
841    private final COWEntry<K, V>[] entries;
842    private final int startIndex;
843    private final int endIndex;
844    private final Comparator<? super K> keyComparator;
845    private final Comparator<Map.Entry<K, V>> comparator;
846
847    int getLength() {
848      return endIndex - startIndex;
849    }
850
851    /**
852     * Binary search for a given key
853     * @param needle The key to look for in all of the entries
854     * @return Same return value as Arrays.binarySearch. Positive numbers mean the index. Otherwise
855     *         (-1 * insertion point) - 1
856     */
857    int find(K needle) {
858      int begin = startIndex;
859      int end = endIndex - 1;
860
861      while (begin <= end) {
862        int mid = begin + ((end - begin) / 2);
863        K midKey = entries[mid].key;
864        int compareRes = keyComparator.compare(midKey, needle);
865
866        // 0 means equals
867        // We found the key.
868        if (compareRes == 0) {
869          return mid;
870        } else if (compareRes < 0) {
871          // midKey is less than needle so we need
872          // to look at farther up
873          begin = mid + 1;
874        } else {
875          // midKey is greater than needle so we
876          // need to look down.
877          end = mid - 1;
878        }
879      }
880
881      return (-1 * begin) - 1;
882    }
883
884    ArrayHolder<K, V> replace(int index, COWEntry<K, V> newEntry) {
885      // TODO should this restart the array back at start index 0 ?
886      COWEntry<K, V>[] newEntries = entries.clone();
887      newEntries[index] = newEntry;
888      return new ArrayHolder<>(newEntries, startIndex, endIndex, keyComparator, comparator);
889    }
890
891    ArrayHolder<K, V> remove(int index) {
892      COWEntry<K, V>[] newEntries = new COWEntry[getLength() - 1];
893      System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex);
894      System.arraycopy(this.entries, index + 1, newEntries, index, entries.length - index - 1);
895      return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator);
896    }
897
898    ArrayHolder<K, V> insert(int index, COWEntry<K, V> newEntry) {
899      COWEntry<K, V>[] newEntries = new COWEntry[getLength() + 1];
900      System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex);
901      newEntries[index] = newEntry;
902      System.arraycopy(this.entries, index, newEntries, index + 1, getLength() - index);
903      return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator);
904    }
905
906    private ArrayHolder(final Comparator<? super K> keyComparator,
907      final Comparator<Map.Entry<K, V>> comparator) {
908      this.endIndex = 0;
909      this.startIndex = 0;
910      this.entries = new COWEntry[] {};
911      this.keyComparator = keyComparator;
912      this.comparator = comparator;
913    }
914
915    private ArrayHolder(COWEntry[] entries, int startIndex, int endIndex,
916      final Comparator<? super K> keyComparator, Comparator<Map.Entry<K, V>> comparator) {
917      this.entries = entries;
918      this.startIndex = startIndex;
919      this.endIndex = endIndex;
920      this.keyComparator = keyComparator;
921      this.comparator = comparator;
922    }
923  }
924
925  private final static class COWEntry<K, V> implements Map.Entry<K, V> {
926    K key = null;
927    V value = null;
928
929    COWEntry(K key, V value) {
930      this.key = key;
931      this.value = value;
932    }
933
934    @Override
935    public K getKey() {
936      return key;
937    }
938
939    @Override
940    public V getValue() {
941      return value;
942    }
943
944    @Override
945    public V setValue(V value) {
946      V oldValue = this.value;
947      this.value = value;
948      return oldValue;
949    }
950  }
951}