View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase.types;
20  
21  import org.apache.hadoop.hbase.classification.InterfaceAudience;
22  import org.apache.hadoop.hbase.classification.InterfaceStability;
23  
24  import java.util.AbstractMap;
25  import java.util.Collection;
26  import java.util.Comparator;
27  import java.util.Iterator;
28  import java.util.Map;
29  import java.util.NavigableSet;
30  import java.util.Set;
31  import java.util.SortedSet;
32  import java.util.concurrent.ConcurrentNavigableMap;
33  
34  /**
35   * A Map that keeps a sorted array in order to provide the concurrent map interface.
36   * Keeping a sorted array means that it's much more cache line friendly, making reads faster
37   * than the tree version.
38   *
39   * In order to make concurrent reads and writes safe this does a copy on write.
40   * There can only be one concurrent write at a time.
41   */
42  @InterfaceAudience.Private
43  @InterfaceStability.Stable
44  public class CopyOnWriteArrayMap<K, V> extends AbstractMap<K, V>
45      implements Map<K, V>, ConcurrentNavigableMap<K, V> {
46    private final Comparator<? super K> keyComparator;
47    private volatile ArrayHolder<K, V> holder;
48  
49    public CopyOnWriteArrayMap() {
50      this(new Comparator<K>() {
51        @Override
52        public int compare(K o1, K o2) {
53          return ((Comparable) o1).compareTo(o2);
54        }
55      });
56    }
57  
58    public CopyOnWriteArrayMap(final Comparator<? super K> keyComparator) {
59      this.keyComparator = keyComparator;
60      this.holder = new ArrayHolder<>(keyComparator, new Comparator<Entry<K, V>>() {
61        @Override
62        public int compare(Entry<K, V> o1, Entry<K, V> o2) {
63          return keyComparator.compare(o1.getKey(), o2.getKey());
64        }
65      });
66    }
67  
68    private CopyOnWriteArrayMap(final Comparator<? super K> keyComparator, ArrayHolder<K, V> holder) {
69      this.keyComparator = keyComparator;
70      this.holder = holder;
71    }
72  
73    /*
74      Un synchronized read operations.
75  
76      No locking.
77      No waiting
78      No copying.
79  
80      These should all be FAST.
81     */
82  
83    @Override
84    public Comparator<? super K> comparator() {
85      return keyComparator;
86    }
87  
88    @Override
89    public ConcurrentNavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
90      ArrayHolder<K, V> current = this.holder;
91      int index = current.find(fromKey);
92  
93      if (!inclusive && index >= 0) {
94        index++;
95      } else if (index < 0) {
96        index = -(index + 1);
97      }
98      return new CopyOnWriteArrayMap<>(
99          this.keyComparator,
100         new ArrayHolder<>(
101             current.entries,
102             index,
103             current.endIndex,
104             current.keyComparator,
105             current.comparator));
106   }
107 
108   @Override
109   public ConcurrentNavigableMap<K, V> tailMap(K fromKey) {
110     return this.tailMap(fromKey, true);
111   }
112 
113   @Override
114   public K firstKey() {
115     ArrayHolder<K, V> current = this.holder;
116     if (current.getLength() == 0) {
117       return null;
118     }
119     return current.entries[current.startIndex].getKey();
120   }
121 
122   @Override
123   public K lastKey() {
124     ArrayHolder<K, V> current = this.holder;
125     if (current.getLength() == 0) {
126       return null;
127     }
128     return current.entries[current.endIndex - 1].getKey();
129   }
130 
131   @Override
132   public Entry<K, V> lowerEntry(K key) {
133     ArrayHolder<K, V> current = this.holder;
134     if (current.getLength() == 0) {
135       return null;
136     }
137 
138     int index = current.find(key);
139 
140     // There's a key exactly equal.
141     if (index >= 0) {
142       index -= 1;
143     } else {
144       index = -(index + 1) - 1;
145     }
146 
147     if (index < current.startIndex || index >= current.endIndex) {
148       return null;
149     }
150     return current.entries[index];
151   }
152 
153   @Override
154   public K lowerKey(K key) {
155     Map.Entry<K, V> entry = lowerEntry(key);
156     if (entry == null) {
157       return null;
158     }
159     return entry.getKey();
160   }
161 
162   @Override
163   public Entry<K, V> floorEntry(K key) {
164     ArrayHolder<K, V> current = this.holder;
165     if (current.getLength() == 0) {
166       return null;
167     }
168     int index = current.find(key);
169     if (index < 0) {
170       index = -(index + 1) - 1;
171     }
172     if (index < current.startIndex || index >= current.endIndex) {
173       return null;
174     }
175 
176     return current.entries[index];
177   }
178 
179   @Override
180   public K floorKey(K key) {
181     Map.Entry<K, V> entry = floorEntry(key);
182     if (entry == null) {
183       return null;
184     }
185     return entry.getKey();
186   }
187 
188   @Override
189   public Entry<K, V> ceilingEntry(K key) {
190     ArrayHolder<K, V> current = this.holder;
191     if (current.getLength() == 0) {
192       return null;
193     }
194     int index = current.find(key);
195     if (index < 0) {
196       index = -(index + 1);
197     }
198     if (index < current.startIndex || index >= current.endIndex) {
199       return null;
200     }
201 
202     return current.entries[index];
203   }
204 
205   @Override
206   public K ceilingKey(K key) {
207     Map.Entry<K, V> entry = ceilingEntry(key);
208     if (entry == null) {
209       return null;
210     }
211     return entry.getKey();
212   }
213 
214   @Override
215   public Entry<K, V> higherEntry(K key) {
216     ArrayHolder<K, V> current = this.holder;
217     if (current.getLength() == 0) {
218       return null;
219     }
220     int index = current.find(key);
221 
222     // There's a key exactly equal.
223     if (index >= 0) {
224       index += 1;
225     } else {
226       index = -(index + 1);
227     }
228 
229     if (index < current.startIndex || index >= current.endIndex) {
230       return null;
231     }
232     return current.entries[index];
233   }
234 
235   @Override
236   public K higherKey(K key) {
237     Map.Entry<K, V> entry = higherEntry(key);
238     if (entry == null) {
239       return null;
240     }
241     return entry.getKey();
242   }
243 
244   @Override
245   public Entry<K, V> firstEntry() {
246     ArrayHolder<K, V> current = this.holder;
247     if (current.getLength() == 0) {
248       return null;
249     }
250     return current.entries[current.startIndex];
251   }
252 
253   @Override
254   public Entry<K, V> lastEntry() {
255     ArrayHolder<K, V> current = this.holder;
256     if (current.getLength() == 0) {
257       return null;
258     }
259     return current.entries[current.endIndex - 1];
260   }
261 
262   @Override
263   public int size() {
264     return holder.getLength();
265   }
266 
267   @Override
268   public boolean isEmpty() {
269     return holder.getLength() == 0;
270   }
271 
272   @Override
273   public boolean containsKey(Object key) {
274     ArrayHolder<K, V> current = this.holder;
275     int index = current.find((K) key);
276     return index >= 0;
277   }
278 
279   @Override
280   public V get(Object key) {
281 
282     ArrayHolder<K, V> current = this.holder;
283     int index = current.find((K) key);
284     if (index >= 0) {
285       return current.entries[index].getValue();
286     }
287     return null;
288   }
289 
290   @Override
291   public NavigableSet<K> keySet() {
292     return new ArrayKeySet<>(this.holder);
293   }
294 
295   @Override
296   public Collection<V> values() {
297     return new ArrayValueCollection<>(this.holder);
298   }
299 
300   @Override
301   public Set<Entry<K, V>> entrySet() {
302     return new ArrayEntrySet<>(this.holder);
303   }
304 
305   /*
306      Synchronized write methods.
307 
308      Every method should be synchronized.
309      Only one modification at a time.
310 
311      These will be slow.
312    */
313 
314 
315   @Override
316   public synchronized V put(K key, V value) {
317     ArrayHolder<K, V> current = this.holder;
318     int index = current.find(key);
319     COWEntry<K, V> newEntry = new COWEntry<>(key, value);
320     if (index >= 0) {
321       this.holder = current.replace(index, newEntry);
322       return current.entries[index].getValue();
323     } else {
324       this.holder = current.insert(-(index + 1), newEntry);
325     }
326     return null;
327   }
328 
329   @Override
330   public synchronized V remove(Object key) {
331 
332     ArrayHolder<K, V> current = this.holder;
333     int index = current.find((K) key);
334     if (index >= 0) {
335       this.holder = current.remove(index);
336       return current.entries[index].getValue();
337     }
338     return null;
339   }
340 
341   @Override
342   public synchronized void clear() {
343     this.holder = new ArrayHolder<>(this.holder.keyComparator, this.holder.comparator);
344   }
345 
346   @Override
347   public synchronized V putIfAbsent(K key, V value) {
348     ArrayHolder<K, V> current = this.holder;
349     int index = current.find(key);
350 
351     if (index < 0) {
352       COWEntry<K, V> newEntry = new COWEntry<>(key, value);
353       this.holder = current.insert(-(index + 1), newEntry);
354       return value;
355     }
356     return current.entries[index].getValue();
357   }
358 
359   @Override
360   public synchronized boolean remove(Object key, Object value) {
361     ArrayHolder<K, V> current = this.holder;
362     int index = current.find((K) key);
363 
364     if (index >= 0 && current.entries[index].getValue().equals(value)) {
365       this.holder = current.remove(index);
366       return true;
367     }
368     return false;
369   }
370 
371   @Override
372   public synchronized boolean replace(K key, V oldValue, V newValue) {
373     ArrayHolder<K, V> current = this.holder;
374     int index = current.find(key);
375 
376     if (index >= 0 && current.entries[index].getValue().equals(oldValue)) {
377       COWEntry<K, V> newEntry = new COWEntry<>(key, newValue);
378       this.holder = current.replace(index, newEntry);
379       return true;
380     }
381     return false;
382   }
383 
384   @Override
385   public synchronized V replace(K key, V value) {
386     ArrayHolder<K, V> current = this.holder;
387     int index = current.find(key);
388 
389     if (index >= 0) {
390       COWEntry<K, V> newEntry = new COWEntry<>(key, value);
391       this.holder = current.replace(index, newEntry);
392       return current.entries[index].getValue();
393     }
394     return null;
395   }
396 
397   @Override
398   public Entry<K, V> pollFirstEntry() {
399     throw new UnsupportedOperationException();
400   }
401 
402   @Override
403   public Entry<K, V> pollLastEntry() {
404     throw new UnsupportedOperationException();
405   }
406 
407   @Override
408   public ConcurrentNavigableMap<K, V> descendingMap() {
409     throw new UnsupportedOperationException();
410   }
411 
412   @Override
413   public NavigableSet<K> navigableKeySet() {
414     throw new UnsupportedOperationException();
415   }
416 
417   @Override
418   public ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey) {
419     throw new UnsupportedOperationException();
420   }
421 
422   @Override
423   public ConcurrentNavigableMap<K, V> headMap(K toKey) {
424     throw new UnsupportedOperationException();
425   }
426 
427   @Override
428   public ConcurrentNavigableMap<K, V> subMap(K fromKey,
429                                              boolean fromInclusive,
430                                              K toKey,
431                                              boolean toInclusive) {
432     throw new UnsupportedOperationException();
433   }
434 
435   @Override
436   public ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive) {
437     throw new UnsupportedOperationException();
438   }
439 
440   @Override
441   public NavigableSet<K> descendingKeySet() {
442     throw new UnsupportedOperationException();
443   }
444 
445   private final class ArrayKeySet<K, V> implements NavigableSet<K> {
446 
447     private final ArrayHolder<K, V> holder;
448 
449     private ArrayKeySet(ArrayHolder<K, V> holder) {
450       this.holder = holder;
451     }
452 
453     @Override
454     public int size() {
455       return holder.getLength();
456     }
457 
458     @Override
459     public boolean isEmpty() {
460       return holder.getLength() == 0;
461     }
462 
463     @Override
464     public boolean contains(Object o) {
465       ArrayHolder<K, V> current = this.holder;
466 
467       for (int i = current.startIndex; i < current.endIndex; i++) {
468         if (current.entries[i].getValue().equals(o)) {
469           return true;
470         }
471       }
472       return false;
473     }
474 
475     @Override
476     public K lower(K k) {
477       throw new UnsupportedOperationException();
478     }
479 
480     @Override
481     public K floor(K k) {
482       throw new UnsupportedOperationException();
483     }
484 
485     @Override
486     public K ceiling(K k) {
487       throw new UnsupportedOperationException();
488     }
489 
490     @Override
491     public K higher(K k) {
492       throw new UnsupportedOperationException();
493     }
494 
495     @Override
496     public K pollFirst() {
497       throw new UnsupportedOperationException();
498     }
499 
500     @Override
501     public K pollLast() {
502       throw new UnsupportedOperationException();
503     }
504 
505     @Override
506     public Iterator<K> iterator() {
507       return new ArrayKeyIterator<>(this.holder);
508     }
509 
510     @Override
511     public NavigableSet<K> descendingSet() {
512       throw new UnsupportedOperationException();
513     }
514 
515     @Override
516     public Iterator<K> descendingIterator() {
517       throw new UnsupportedOperationException();
518     }
519 
520     @Override
521     public NavigableSet<K> subSet(K fromElement,
522                                   boolean fromInclusive,
523                                   K toElement,
524                                   boolean toInclusive) {
525       throw new UnsupportedOperationException();
526     }
527 
528     @Override
529     public NavigableSet<K> headSet(K toElement, boolean inclusive) {
530       throw new UnsupportedOperationException();
531     }
532 
533     @Override
534     public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
535       throw new UnsupportedOperationException();
536     }
537 
538     @Override
539     public Comparator<? super K> comparator() {
540       return (Comparator<? super K>) keyComparator;
541     }
542 
543     @Override
544     public SortedSet<K> subSet(K fromElement, K toElement) {
545       return null;
546     }
547 
548     @Override
549     public SortedSet<K> headSet(K toElement) {
550       return null;
551     }
552 
553     @Override
554     public SortedSet<K> tailSet(K fromElement) {
555       return null;
556     }
557 
558     @Override
559     public K first() {
560       ArrayHolder<K, V> current = this.holder;
561       if (current.getLength() == 0) {
562         return null;
563       }
564       return current.entries[current.startIndex].getKey();
565     }
566 
567     @Override
568     public K last() {
569       ArrayHolder<K, V> current = this.holder;
570       if (current.getLength() == 0) {
571         return null;
572       }
573       return current.entries[current.endIndex - 1].getKey();
574     }
575 
576     @Override
577     public Object[] toArray() {
578       throw new UnsupportedOperationException();
579     }
580 
581     @Override
582     public <T> T[] toArray(T[] a) {
583       throw new UnsupportedOperationException();
584     }
585 
586     @Override
587     public boolean add(K k) {
588       throw new UnsupportedOperationException();
589     }
590 
591     @Override
592     public boolean remove(Object o) {
593       throw new UnsupportedOperationException();
594     }
595 
596     @Override
597     public boolean containsAll(Collection<?> c) {
598       throw new UnsupportedOperationException();
599     }
600 
601     @Override
602     public boolean addAll(Collection<? extends K> c) {
603       throw new UnsupportedOperationException();
604     }
605 
606     @Override
607     public boolean retainAll(Collection<?> c) {
608       throw new UnsupportedOperationException();
609     }
610 
611     @Override
612     public boolean removeAll(Collection<?> c) {
613       throw new UnsupportedOperationException();
614     }
615 
616     @Override
617     public void clear() {
618       throw new UnsupportedOperationException();
619     }
620   }
621 
622   private final class ArrayValueCollection<K, V> implements Collection<V> {
623 
624     private final ArrayHolder<K, V> holder;
625 
626     private ArrayValueCollection(ArrayHolder<K, V> holder) {
627       this.holder = holder;
628     }
629 
630     @Override
631     public int size() {
632       return holder.getLength();
633     }
634 
635     @Override
636     public boolean isEmpty() {
637       return holder.getLength() == 0;
638     }
639 
640     @Override
641     public boolean contains(Object o) {
642       throw new UnsupportedOperationException();
643     }
644 
645     @Override
646     public Iterator<V> iterator() {
647       return new ArrayValueIterator<>(this.holder);
648     }
649 
650     @Override
651     public Object[] toArray() {
652       throw new UnsupportedOperationException();
653     }
654 
655     @Override
656     public <T> T[] toArray(T[] a) {
657       throw new UnsupportedOperationException();
658     }
659 
660     @Override
661     public boolean add(V v) {
662       throw new UnsupportedOperationException();
663     }
664 
665     @Override
666     public boolean remove(Object o) {
667       throw new UnsupportedOperationException();
668     }
669 
670     @Override
671     public boolean containsAll(Collection<?> c) {
672       throw new UnsupportedOperationException();
673     }
674 
675     @Override
676     public boolean addAll(Collection<? extends V> c) {
677       throw new UnsupportedOperationException();
678     }
679 
680     @Override
681     public boolean removeAll(Collection<?> c) {
682       throw new UnsupportedOperationException();
683     }
684 
685     @Override
686     public boolean retainAll(Collection<?> c) {
687       throw new UnsupportedOperationException();
688     }
689 
690     @Override
691     public void clear() {
692       throw new UnsupportedOperationException();
693     }
694 
695     @Override
696     public boolean equals(Object o) {
697       return false;
698     }
699 
700     @Override
701     public int hashCode() {
702       return 0;
703     }
704   }
705 
706   private final class ArrayKeyIterator<K, V> implements Iterator<K> {
707     int index;
708     private final ArrayHolder<K, V> holder;
709 
710     private ArrayKeyIterator(ArrayHolder<K, V> holder) {
711       this.holder = holder;
712       index = holder.startIndex;
713     }
714 
715 
716     @Override
717     public boolean hasNext() {
718       return index < holder.endIndex;
719     }
720 
721     @Override
722     public K next() {
723       return holder.entries[index++].getKey();
724     }
725 
726     @Override
727     public void remove() {
728       throw new UnsupportedOperationException("remove");
729     }
730   }
731 
732   private final class ArrayValueIterator<K, V> implements Iterator<V> {
733     int index;
734     private final ArrayHolder<K, V> holder;
735 
736     private ArrayValueIterator(ArrayHolder<K, V> holder) {
737       this.holder = holder;
738       index = holder.startIndex;
739     }
740 
741 
742     @Override
743     public boolean hasNext() {
744       return index < holder.endIndex;
745     }
746 
747     @Override
748     public V next() {
749       return holder.entries[index++].getValue();
750     }
751 
752     @Override
753     public void remove() {
754       throw new UnsupportedOperationException("remove");
755     }
756   }
757 
758   private final class ArrayEntryIterator<K, V> implements Iterator<Map.Entry<K, V>> {
759 
760     int index;
761     private final ArrayHolder<K, V> holder;
762 
763     private ArrayEntryIterator(ArrayHolder<K, V> holder) {
764       this.holder = holder;
765       this.index = holder.startIndex;
766     }
767 
768     @Override
769     public boolean hasNext() {
770       return index < holder.endIndex;
771     }
772 
773     @Override
774     public Entry<K, V> next() {
775       return holder.entries[index++];
776     }
777 
778     @Override
779     public void remove() {
780       throw new UnsupportedOperationException("remove");
781     }
782   }
783 
784   private final class ArrayEntrySet<K, V> implements Set<Map.Entry<K, V>> {
785     private final ArrayHolder<K, V> holder;
786 
787     private ArrayEntrySet(ArrayHolder<K, V> holder) {
788       this.holder = holder;
789     }
790 
791     @Override
792     public int size() {
793       return holder.getLength();
794     }
795 
796     @Override
797     public boolean isEmpty() {
798       return holder.getLength() == 0;
799     }
800 
801     @Override
802     public boolean contains(Object o) {
803       return false;
804     }
805 
806     @Override
807     public Iterator<Entry<K, V>> iterator() {
808       return new ArrayEntryIterator<>(this.holder);
809     }
810 
811     @Override
812     public Object[] toArray() {
813       throw new UnsupportedOperationException();
814     }
815 
816     @Override
817     public <T> T[] toArray(T[] a) {
818       throw new UnsupportedOperationException();
819     }
820 
821     @Override
822     public boolean add(Entry<K, V> kvEntry) {
823       throw new UnsupportedOperationException();
824     }
825 
826     @Override
827     public boolean remove(Object o) {
828       throw new UnsupportedOperationException();
829     }
830 
831     @Override
832     public boolean containsAll(Collection<?> c) {
833       throw new UnsupportedOperationException();
834     }
835 
836     @Override
837     public boolean addAll(Collection<? extends Entry<K, V>> c) {
838       throw new UnsupportedOperationException();
839     }
840 
841     @Override
842     public boolean retainAll(Collection<?> c) {
843       throw new UnsupportedOperationException();
844     }
845 
846     @Override
847     public boolean removeAll(Collection<?> c) {
848       throw new UnsupportedOperationException();
849     }
850 
851     @Override
852     public void clear() {
853       throw new UnsupportedOperationException();
854     }
855   }
856 
857   private final static class ArrayHolder<K, V> {
858     private final COWEntry<K, V>[] entries;
859     private final int startIndex;
860     private final int endIndex;
861     private final Comparator<? super K> keyComparator;
862     private final Comparator<Map.Entry<K, V>> comparator;
863 
864 
865     int getLength() {
866       return endIndex - startIndex;
867     }
868 
869 
870     /**
871      * Binary search for a given key
872      * @param needle The key to look for in all of the entries
873      * @return Same return value as Arrays.binarySearch.
874      * Positive numbers mean the index.
875      * Otherwise (-1 * insertion point) - 1
876      */
877     int find(K needle) {
878       int begin = startIndex;
879       int end = endIndex - 1;
880 
881       while (begin <= end) {
882         int mid = begin + ((end - begin) / 2);
883         K midKey = entries[ mid].key;
884         int compareRes = keyComparator.compare(midKey, needle);
885 
886         // 0 means equals
887         // We found the key.
888         if (compareRes == 0) {
889           return mid;
890         } else if (compareRes < 0) {
891           // midKey is less than needle so we need
892           // to look at farther up
893           begin = mid + 1;
894         } else {
895           // midKey is greater than needle so we
896           // need to look down.
897           end = mid - 1;
898         }
899       }
900 
901       return (-1 * begin) - 1;
902     }
903 
904     ArrayHolder<K, V> replace(int index, COWEntry<K, V> newEntry) {
905       // TODO should this restart the array back at start index 0 ?
906       COWEntry<K, V>[] newEntries = entries.clone();
907       newEntries[index] = newEntry;
908       return new ArrayHolder<>(newEntries, startIndex, endIndex, keyComparator, comparator);
909     }
910 
911     ArrayHolder<K, V> remove(int index) {
912       COWEntry<K,V>[] newEntries = new COWEntry[getLength() - 1];
913       System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex);
914       System.arraycopy(this.entries, index + 1, newEntries, index, entries.length - index - 1);
915       return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator);
916     }
917 
918     ArrayHolder<K, V> insert(int index, COWEntry<K, V> newEntry) {
919       COWEntry<K,V>[] newEntries = new COWEntry[getLength() + 1];
920       System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex);
921       newEntries[index] = newEntry;
922       System.arraycopy(this.entries, index, newEntries, index + 1, getLength() - index);
923       return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator);
924     }
925 
926     private ArrayHolder(
927         final Comparator<? super K> keyComparator,
928         final Comparator<Map.Entry<K, V>> comparator) {
929       this.endIndex = 0;
930       this.startIndex = 0;
931       this.entries = new COWEntry[] {};
932       this.keyComparator = keyComparator;
933       this.comparator = comparator;
934     }
935 
936     private ArrayHolder(COWEntry[] entries,
937                         int startIndex, int endIndex,
938                         final Comparator<? super K> keyComparator,
939                         Comparator<Map.Entry<K, V>> comparator) {
940       this.entries = entries;
941       this.startIndex = startIndex;
942       this.endIndex = endIndex;
943       this.keyComparator = keyComparator;
944       this.comparator = comparator;
945     }
946   }
947 
948   private final static class COWEntry<K, V> implements Map.Entry<K, V> {
949     K key = null;
950     V value = null;
951 
952     COWEntry(K key, V value) {
953       this.key = key;
954       this.value = value;
955     }
956 
957     @Override
958     public K getKey() {
959       return key;
960     }
961 
962     @Override
963     public V getValue() {
964       return value;
965     }
966 
967     @Override
968     public V setValue(V value) {
969       V oldValue = this.value;
970       this.value = value;
971       return oldValue;
972     }
973   }
974 }