• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc.  All rights reserved.
3 // https://developers.google.com/protocol-buffers/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 //     * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 //     * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following disclaimer
13 // in the documentation and/or other materials provided with the
14 // distribution.
15 //     * Neither the name of Google Inc. nor the names of its
16 // contributors may be used to endorse or promote products derived from
17 // this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 
31 package com.google.protobuf;
32 
33 import java.util.AbstractMap;
34 import java.util.AbstractSet;
35 import java.util.ArrayList;
36 import java.util.Collections;
37 import java.util.Iterator;
38 import java.util.List;
39 import java.util.Map;
40 import java.util.NoSuchElementException;
41 import java.util.Set;
42 import java.util.SortedMap;
43 import java.util.TreeMap;
44 
45 /**
46  * A custom map implementation from FieldDescriptor to Object optimized to
47  * minimize the number of memory allocations for instances with a small number
48  * of mappings. The implementation stores the first {@code k} mappings in an
49  * array for a configurable value of {@code k}, allowing direct access to the
50  * corresponding {@code Entry}s without the need to create an Iterator. The
51  * remaining entries are stored in an overflow map. Iteration over the entries
52  * in the map should be done as follows:
53  *
54  * <pre>   {@code
55  * for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) {
56  *   process(fieldMap.getArrayEntryAt(i));
57  * }
58  * for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) {
59  *   process(entry);
60  * }
61  * }</pre>
62  *
63  * The resulting iteration is in order of ascending field tag number. The
64  * object returned by {@link #entrySet()} adheres to the same contract but is
65  * less efficient as it necessarily involves creating an object for iteration.
66  * <p>
67  * The tradeoff for this memory efficiency is that the worst case running time
68  * of the {@code put()} operation is {@code O(k + lg n)}, which happens when
69  * entries are added in descending order. {@code k} should be chosen such that
70  * it covers enough common cases without adversely affecting larger maps. In
71  * practice, the worst case scenario does not happen for extensions because
72  * extension fields are serialized and deserialized in order of ascending tag
73  * number, but the worst case scenario can happen for DynamicMessages.
74  * <p>
75  * The running time for all other operations is similar to that of
76  * {@code TreeMap}.
77  * <p>
78  * Instances are not thread-safe until {@link #makeImmutable()} is called,
79  * after which any modifying operation will result in an
80  * {@link UnsupportedOperationException}.
81  *
82  * @author darick@google.com Darick Tong
83  */
84 // This class is final for all intents and purposes because the constructor is
85 // private. However, the FieldDescriptor-specific logic is encapsulated in
86 // a subclass to aid testability of the core logic.
87 class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> {
88 
89   /**
90    * Creates a new instance for mapping FieldDescriptors to their values.
91    * The {@link #makeImmutable()} implementation will convert the List values
92    * of any repeated fields to unmodifiable lists.
93    *
94    * @param arraySize The size of the entry array containing the
95    *        lexicographically smallest mappings.
96    */
97   static <FieldDescriptorType extends
98       FieldSet.FieldDescriptorLite<FieldDescriptorType>>
newFieldMap(int arraySize)99       SmallSortedMap<FieldDescriptorType, Object> newFieldMap(int arraySize) {
100     return new SmallSortedMap<FieldDescriptorType, Object>(arraySize) {
101       @Override
102       @SuppressWarnings("unchecked")
103       public void makeImmutable() {
104         if (!isImmutable()) {
105           for (int i = 0; i < getNumArrayEntries(); i++) {
106             final Map.Entry<FieldDescriptorType, Object> entry =
107                 getArrayEntryAt(i);
108             if (entry.getKey().isRepeated()) {
109               final List value = (List) entry.getValue();
110               entry.setValue(Collections.unmodifiableList(value));
111             }
112           }
113           for (Map.Entry<FieldDescriptorType, Object> entry :
114                    getOverflowEntries()) {
115             if (entry.getKey().isRepeated()) {
116               final List value = (List) entry.getValue();
117               entry.setValue(Collections.unmodifiableList(value));
118             }
119           }
120         }
121         super.makeImmutable();
122       }
123     };
124   }
125 
126   /**
127    * Creates a new instance for testing.
128    *
129    * @param arraySize The size of the entry array containing the
130    *        lexicographically smallest mappings.
131    */
132   static <K extends Comparable<K>, V> SmallSortedMap<K, V> newInstanceForTest(
133       int arraySize) {
134     return new SmallSortedMap<K, V>(arraySize);
135   }
136 
137   private final int maxArraySize;
138   // The "entry array" is actually a List because generic arrays are not
139   // allowed. ArrayList also nicely handles the entry shifting on inserts and
140   // removes.
141   private List<Entry> entryList;
142   private Map<K, V> overflowEntries;
143   private boolean isImmutable;
144   // The EntrySet is a stateless view of the Map. It's initialized the first
145   // time it is requested and reused henceforth.
146   private volatile EntrySet lazyEntrySet;
147 
148   /**
149    * @code arraySize Size of the array in which the lexicographically smallest
150    *       mappings are stored. (i.e. the {@code k} referred to in the class
151    *       documentation).
152    */
153   private SmallSortedMap(int arraySize) {
154     this.maxArraySize = arraySize;
155     this.entryList = Collections.emptyList();
156     this.overflowEntries = Collections.emptyMap();
157   }
158 
159   /** Make this map immutable from this point forward. */
160   public void makeImmutable() {
161     if (!isImmutable) {
162       // Note: There's no need to wrap the entryList in an unmodifiableList
163       // because none of the list's accessors are exposed. The iterator() of
164       // overflowEntries, on the other hand, is exposed so it must be made
165       // unmodifiable.
166       overflowEntries = overflowEntries.isEmpty() ?
167           Collections.<K, V>emptyMap() :
168           Collections.unmodifiableMap(overflowEntries);
169       isImmutable = true;
170     }
171   }
172 
173   /** @return Whether {@link #makeImmutable()} has been called. */
174   public boolean isImmutable() {
175     return isImmutable;
176   }
177 
178   /** @return The number of entries in the entry array. */
179   public int getNumArrayEntries() {
180     return entryList.size();
181   }
182 
183   /** @return The array entry at the given {@code index}. */
184   public Map.Entry<K, V> getArrayEntryAt(int index) {
185     return entryList.get(index);
186   }
187 
188   /** @return There number of overflow entries. */
189   public int getNumOverflowEntries() {
190     return overflowEntries.size();
191   }
192 
193   /** @return An iterable over the overflow entries. */
194   public Iterable<Map.Entry<K, V>> getOverflowEntries() {
195     return overflowEntries.isEmpty() ?
196         EmptySet.<Map.Entry<K, V>>iterable() :
197         overflowEntries.entrySet();
198   }
199 
200   @Override
201   public int size() {
202     return entryList.size() + overflowEntries.size();
203   }
204 
205   /**
206    * The implementation throws a {@code ClassCastException} if o is not an
207    * object of type {@code K}.
208    *
209    * {@inheritDoc}
210    */
211   @Override
212   public boolean containsKey(Object o) {
213     @SuppressWarnings("unchecked")
214     final K key = (K) o;
215     return binarySearchInArray(key) >= 0 || overflowEntries.containsKey(key);
216   }
217 
218   /**
219    * The implementation throws a {@code ClassCastException} if o is not an
220    * object of type {@code K}.
221    *
222    * {@inheritDoc}
223    */
224   @Override
get(Object o)225   public V get(Object o) {
226     @SuppressWarnings("unchecked")
227     final K key = (K) o;
228     final int index = binarySearchInArray(key);
229     if (index >= 0) {
230       return entryList.get(index).getValue();
231     }
232     return overflowEntries.get(key);
233   }
234 
235   @Override
put(K key, V value)236   public V put(K key, V value) {
237     checkMutable();
238     final int index = binarySearchInArray(key);
239     if (index >= 0) {
240       // Replace existing array entry.
241       return entryList.get(index).setValue(value);
242     }
243     ensureEntryArrayMutable();
244     final int insertionPoint = -(index + 1);
245     if (insertionPoint >= maxArraySize) {
246       // Put directly in overflow.
247       return getOverflowEntriesMutable().put(key, value);
248     }
249     // Insert new Entry in array.
250     if (entryList.size() == maxArraySize) {
251       // Shift the last array entry into overflow.
252       final Entry lastEntryInArray = entryList.remove(maxArraySize - 1);
253       getOverflowEntriesMutable().put(lastEntryInArray.getKey(),
254                                       lastEntryInArray.getValue());
255     }
256     entryList.add(insertionPoint, new Entry(key, value));
257     return null;
258   }
259 
260   @Override
clear()261   public void clear() {
262     checkMutable();
263     if (!entryList.isEmpty()) {
264       entryList.clear();
265     }
266     if (!overflowEntries.isEmpty()) {
267       overflowEntries.clear();
268     }
269   }
270 
271   /**
272    * The implementation throws a {@code ClassCastException} if o is not an
273    * object of type {@code K}.
274    *
275    * {@inheritDoc}
276    */
277   @Override
remove(Object o)278   public V remove(Object o) {
279     checkMutable();
280     @SuppressWarnings("unchecked")
281     final K key = (K) o;
282     final int index = binarySearchInArray(key);
283     if (index >= 0) {
284       return removeArrayEntryAt(index);
285     }
286     // overflowEntries might be Collections.unmodifiableMap(), so only
287     // call remove() if it is non-empty.
288     if (overflowEntries.isEmpty()) {
289       return null;
290     } else {
291       return overflowEntries.remove(key);
292     }
293   }
294 
removeArrayEntryAt(int index)295   private V removeArrayEntryAt(int index) {
296     checkMutable();
297     final V removed = entryList.remove(index).getValue();
298     if (!overflowEntries.isEmpty()) {
299       // Shift the first entry in the overflow to be the last entry in the
300       // array.
301       final Iterator<Map.Entry<K, V>> iterator =
302           getOverflowEntriesMutable().entrySet().iterator();
303       entryList.add(new Entry(iterator.next()));
304       iterator.remove();
305     }
306     return removed;
307   }
308 
309   /**
310    * @param key The key to find in the entry array.
311    * @return The returned integer position follows the same semantics as the
312    *     value returned by {@link java.util.Arrays#binarySearch()}.
313    */
binarySearchInArray(K key)314   private int binarySearchInArray(K key) {
315     int left = 0;
316     int right = entryList.size() - 1;
317 
318     // Optimization: For the common case in which entries are added in
319     // ascending tag order, check the largest element in the array before
320     // doing a full binary search.
321     if (right >= 0) {
322       int cmp = key.compareTo(entryList.get(right).getKey());
323       if (cmp > 0) {
324         return -(right + 2);  // Insert point is after "right".
325       } else if (cmp == 0) {
326         return right;
327       }
328     }
329 
330     while (left <= right) {
331       int mid = (left + right) / 2;
332       int cmp = key.compareTo(entryList.get(mid).getKey());
333       if (cmp < 0) {
334         right = mid - 1;
335       } else if (cmp > 0) {
336         left = mid + 1;
337       } else {
338         return mid;
339       }
340     }
341     return -(left + 1);
342   }
343 
344   /**
345    * Similar to the AbstractMap implementation of {@code keySet()} and
346    * {@code values()}, the entry set is created the first time this method is
347    * called, and returned in response to all subsequent calls.
348    *
349    * {@inheritDoc}
350    */
351   @Override
entrySet()352   public Set<Map.Entry<K, V>> entrySet() {
353     if (lazyEntrySet == null) {
354       lazyEntrySet = new EntrySet();
355     }
356     return lazyEntrySet;
357   }
358 
359   /**
360    * @throws UnsupportedOperationException if {@link #makeImmutable()} has
361    *         has been called.
362    */
checkMutable()363   private void checkMutable() {
364     if (isImmutable) {
365       throw new UnsupportedOperationException();
366     }
367   }
368 
369   /**
370    * @return a {@link SortedMap} to which overflow entries mappings can be
371    *         added or removed.
372    * @throws UnsupportedOperationException if {@link #makeImmutable()} has been
373    *         called.
374    */
375   @SuppressWarnings("unchecked")
getOverflowEntriesMutable()376   private SortedMap<K, V> getOverflowEntriesMutable() {
377     checkMutable();
378     if (overflowEntries.isEmpty() && !(overflowEntries instanceof TreeMap)) {
379       overflowEntries = new TreeMap<K, V>();
380     }
381     return (SortedMap<K, V>) overflowEntries;
382   }
383 
384   /**
385    * Lazily creates the entry list. Any code that adds to the list must first
386    * call this method.
387    */
ensureEntryArrayMutable()388   private void ensureEntryArrayMutable() {
389     checkMutable();
390     if (entryList.isEmpty() && !(entryList instanceof ArrayList)) {
391       entryList = new ArrayList<Entry>(maxArraySize);
392     }
393   }
394 
395   /**
396    * Entry implementation that implements Comparable in order to support
397    * binary search within the entry array. Also checks mutability in
398    * {@link #setValue()}.
399    */
400   private class Entry implements Map.Entry<K, V>, Comparable<Entry> {
401 
402     private final K key;
403     private V value;
404 
Entry(Map.Entry<K, V> copy)405     Entry(Map.Entry<K, V> copy) {
406       this(copy.getKey(), copy.getValue());
407     }
408 
Entry(K key, V value)409     Entry(K key, V value) {
410       this.key = key;
411       this.value = value;
412     }
413 
414     @Override
getKey()415     public K getKey() {
416       return key;
417     }
418 
419     @Override
getValue()420     public V getValue() {
421       return value;
422     }
423 
424     @Override
compareTo(Entry other)425     public int compareTo(Entry other) {
426       return getKey().compareTo(other.getKey());
427     }
428 
429     @Override
setValue(V newValue)430     public V setValue(V newValue) {
431       checkMutable();
432       final V oldValue = this.value;
433       this.value = newValue;
434       return oldValue;
435     }
436 
437     @Override
equals(Object o)438     public boolean equals(Object o) {
439       if (o == this) {
440         return true;
441       }
442       if (!(o instanceof Map.Entry)) {
443         return false;
444       }
445       @SuppressWarnings("unchecked")
446       Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
447       return equals(key, other.getKey()) && equals(value, other.getValue());
448     }
449 
450     @Override
hashCode()451     public int hashCode() {
452       return (key == null ? 0 : key.hashCode()) ^
453           (value == null ? 0 : value.hashCode());
454     }
455 
456     @Override
toString()457     public String toString() {
458       return key + "=" + value;
459     }
460 
461     /** equals() that handles null values. */
equals(Object o1, Object o2)462     private boolean equals(Object o1, Object o2) {
463       return o1 == null ? o2 == null : o1.equals(o2);
464     }
465   }
466 
467   /**
468    * Stateless view of the entries in the field map.
469    */
470   private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
471 
472     @Override
iterator()473     public Iterator<Map.Entry<K, V>> iterator() {
474       return new EntryIterator();
475     }
476 
477     @Override
size()478     public int size() {
479       return SmallSortedMap.this.size();
480     }
481 
482     /**
483      * Throws a {@link ClassCastException} if o is not of the expected type.
484      *
485      * {@inheritDoc}
486      */
487     @Override
contains(Object o)488     public boolean contains(Object o) {
489       @SuppressWarnings("unchecked")
490       final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
491       final V existing = get(entry.getKey());
492       final V value = entry.getValue();
493       return existing == value ||
494           (existing != null && existing.equals(value));
495     }
496 
497     @Override
add(Map.Entry<K, V> entry)498     public boolean add(Map.Entry<K, V> entry) {
499       if (!contains(entry)) {
500         put(entry.getKey(), entry.getValue());
501         return true;
502       }
503       return false;
504     }
505 
506     /**
507      * Throws a {@link ClassCastException} if o is not of the expected type.
508      *
509      * {@inheritDoc}
510      */
511     @Override
remove(Object o)512     public boolean remove(Object o) {
513       @SuppressWarnings("unchecked")
514       final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
515       if (contains(entry)) {
516         SmallSortedMap.this.remove(entry.getKey());
517         return true;
518       }
519       return false;
520     }
521 
522     @Override
clear()523     public void clear() {
524       SmallSortedMap.this.clear();
525     }
526   }
527 
528   /**
529    * Iterator implementation that switches from the entry array to the overflow
530    * entries appropriately.
531    */
532   private class EntryIterator implements Iterator<Map.Entry<K, V>> {
533 
534     private int pos = -1;
535     private boolean nextCalledBeforeRemove;
536     private Iterator<Map.Entry<K, V>> lazyOverflowIterator;
537 
538     @Override
hasNext()539     public boolean hasNext() {
540       return (pos + 1) < entryList.size() ||
541           getOverflowIterator().hasNext();
542     }
543 
544     @Override
next()545     public Map.Entry<K, V> next() {
546       nextCalledBeforeRemove = true;
547       // Always increment pos so that we know whether the last returned value
548       // was from the array or from overflow.
549       if (++pos < entryList.size()) {
550         return entryList.get(pos);
551       }
552       return getOverflowIterator().next();
553     }
554 
555     @Override
remove()556     public void remove() {
557       if (!nextCalledBeforeRemove) {
558         throw new IllegalStateException("remove() was called before next()");
559       }
560       nextCalledBeforeRemove = false;
561       checkMutable();
562 
563       if (pos < entryList.size()) {
564         removeArrayEntryAt(pos--);
565       } else {
566         getOverflowIterator().remove();
567       }
568     }
569 
570     /**
571      * It is important to create the overflow iterator only after the array
572      * entries have been iterated over because the overflow entry set changes
573      * when the client calls remove() on the array entries, which invalidates
574      * any existing iterators.
575      */
getOverflowIterator()576     private Iterator<Map.Entry<K, V>> getOverflowIterator() {
577       if (lazyOverflowIterator == null) {
578         lazyOverflowIterator = overflowEntries.entrySet().iterator();
579       }
580       return lazyOverflowIterator;
581     }
582   }
583 
584   /**
585    * Helper class that holds immutable instances of an Iterable/Iterator that
586    * we return when the overflow entries is empty. This eliminates the creation
587    * of an Iterator object when there is nothing to iterate over.
588    */
589   private static class EmptySet {
590 
591     private static final Iterator<Object> ITERATOR =
592         new Iterator<Object>() {
593           @Override
594           public boolean hasNext() {
595             return false;
596           }
597           @Override
598           public Object next() {
599             throw new NoSuchElementException();
600           }
601           @Override
602           public void remove() {
603             throw new UnsupportedOperationException();
604           }
605         };
606 
607     private static final Iterable<Object> ITERABLE =
608         new Iterable<Object>() {
609           @Override
610           public Iterator<Object> iterator() {
611             return ITERATOR;
612           }
613         };
614 
615     @SuppressWarnings("unchecked")
iterable()616     static <T> Iterable<T> iterable() {
617       return (Iterable<T>) ITERABLE;
618     }
619   }
620 
621   @Override
equals(Object o)622   public boolean equals(Object o) {
623     if (this == o) {
624       return true;
625     }
626 
627     if (!(o instanceof SmallSortedMap)) {
628       return super.equals(o);
629     }
630 
631     SmallSortedMap<?, ?> other = (SmallSortedMap<?, ?>) o;
632     final int size = size();
633     if (size != other.size()) {
634       return false;
635     }
636 
637     // Best effort try to avoid allocating an entry set.
638     final int numArrayEntries = getNumArrayEntries();
639     if (numArrayEntries != other.getNumArrayEntries()) {
640       return entrySet().equals(other.entrySet());
641     }
642 
643     for (int i = 0; i < numArrayEntries; i++) {
644       if (!getArrayEntryAt(i).equals(other.getArrayEntryAt(i))) {
645         return false;
646       }
647     }
648 
649     if (numArrayEntries != size) {
650       return overflowEntries.equals(other.overflowEntries);
651     }
652 
653 
654     return true;
655   }
656 
657   @Override
hashCode()658   public int hashCode() {
659     int h = 0;
660     final int listSize = getNumArrayEntries();
661     for (int i = 0; i < listSize; i++) {
662       h += entryList.get(i).hashCode();
663     }
664     // Avoid the iterator allocation if possible.
665     if (getNumOverflowEntries() > 0) {
666       h += overflowEntries.hashCode();
667     }
668     return h;
669   }
670 }
671