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}