| // Protocol Buffers - Google's data interchange format |
| // Copyright 2008 Google Inc. All rights reserved. |
| // https://developers.google.com/protocol-buffers/ |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following disclaimer |
| // in the documentation and/or other materials provided with the |
| // distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived from |
| // this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| package com.google.protobuf; |
| |
| import java.util.AbstractMap; |
| import java.util.AbstractSet; |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import java.util.Iterator; |
| import java.util.TreeMap; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.NoSuchElementException; |
| import java.util.Set; |
| import java.util.SortedMap; |
| |
| /** |
| * A custom map implementation from FieldDescriptor to Object optimized to |
| * minimize the number of memory allocations for instances with a small number |
| * of mappings. The implementation stores the first {@code k} mappings in an |
| * array for a configurable value of {@code k}, allowing direct access to the |
| * corresponding {@code Entry}s without the need to create an Iterator. The |
| * remaining entries are stored in an overflow map. Iteration over the entries |
| * in the map should be done as follows: |
| * |
| * <pre> {@code |
| * for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) { |
| * process(fieldMap.getArrayEntryAt(i)); |
| * } |
| * for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) { |
| * process(entry); |
| * } |
| * }</pre> |
| * |
| * The resulting iteration is in order of ascending field tag number. The |
| * object returned by {@link #entrySet()} adheres to the same contract but is |
| * less efficient as it necessarily involves creating an object for iteration. |
| * <p> |
| * The tradeoff for this memory efficiency is that the worst case running time |
| * of the {@code put()} operation is {@code O(k + lg n)}, which happens when |
| * entries are added in descending order. {@code k} should be chosen such that |
| * it covers enough common cases without adversely affecting larger maps. In |
| * practice, the worst case scenario does not happen for extensions because |
| * extension fields are serialized and deserialized in order of ascending tag |
| * number, but the worst case scenario can happen for DynamicMessages. |
| * <p> |
| * The running time for all other operations is similar to that of |
| * {@code TreeMap}. |
| * <p> |
| * Instances are not thread-safe until {@link #makeImmutable()} is called, |
| * after which any modifying operation will result in an |
| * {@link UnsupportedOperationException}. |
| * |
| * @author darick@google.com Darick Tong |
| */ |
| // This class is final for all intents and purposes because the constructor is |
| // private. However, the FieldDescriptor-specific logic is encapsulated in |
| // a subclass to aid testability of the core logic. |
| class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { |
| |
| /** |
| * Creates a new instance for mapping FieldDescriptors to their values. |
| * The {@link #makeImmutable()} implementation will convert the List values |
| * of any repeated fields to unmodifiable lists. |
| * |
| * @param arraySize The size of the entry array containing the |
| * lexicographically smallest mappings. |
| */ |
| static <FieldDescriptorType extends |
| FieldSet.FieldDescriptorLite<FieldDescriptorType>> |
| SmallSortedMap<FieldDescriptorType, Object> newFieldMap(int arraySize) { |
| return new SmallSortedMap<FieldDescriptorType, Object>(arraySize) { |
| @Override |
| @SuppressWarnings("unchecked") |
| public void makeImmutable() { |
| if (!isImmutable()) { |
| for (int i = 0; i < getNumArrayEntries(); i++) { |
| final Map.Entry<FieldDescriptorType, Object> entry = |
| getArrayEntryAt(i); |
| if (entry.getKey().isRepeated()) { |
| final List value = (List) entry.getValue(); |
| entry.setValue(Collections.unmodifiableList(value)); |
| } |
| } |
| for (Map.Entry<FieldDescriptorType, Object> entry : |
| getOverflowEntries()) { |
| if (entry.getKey().isRepeated()) { |
| final List value = (List) entry.getValue(); |
| entry.setValue(Collections.unmodifiableList(value)); |
| } |
| } |
| } |
| super.makeImmutable(); |
| } |
| }; |
| } |
| |
| /** |
| * Creates a new instance for testing. |
| * |
| * @param arraySize The size of the entry array containing the |
| * lexicographically smallest mappings. |
| */ |
| static <K extends Comparable<K>, V> SmallSortedMap<K, V> newInstanceForTest( |
| int arraySize) { |
| return new SmallSortedMap<K, V>(arraySize); |
| } |
| |
| private final int maxArraySize; |
| // The "entry array" is actually a List because generic arrays are not |
| // allowed. ArrayList also nicely handles the entry shifting on inserts and |
| // removes. |
| private List<Entry> entryList; |
| private Map<K, V> overflowEntries; |
| private boolean isImmutable; |
| // The EntrySet is a stateless view of the Map. It's initialized the first |
| // time it is requested and reused henceforth. |
| private volatile EntrySet lazyEntrySet; |
| |
| /** |
| * @code arraySize Size of the array in which the lexicographically smallest |
| * mappings are stored. (i.e. the {@code k} referred to in the class |
| * documentation). |
| */ |
| private SmallSortedMap(int arraySize) { |
| this.maxArraySize = arraySize; |
| this.entryList = Collections.emptyList(); |
| this.overflowEntries = Collections.emptyMap(); |
| } |
| |
| /** Make this map immutable from this point forward. */ |
| public void makeImmutable() { |
| if (!isImmutable) { |
| // Note: There's no need to wrap the entryList in an unmodifiableList |
| // because none of the list's accessors are exposed. The iterator() of |
| // overflowEntries, on the other hand, is exposed so it must be made |
| // unmodifiable. |
| overflowEntries = overflowEntries.isEmpty() ? |
| Collections.<K, V>emptyMap() : |
| Collections.unmodifiableMap(overflowEntries); |
| isImmutable = true; |
| } |
| } |
| |
| /** @return Whether {@link #makeImmutable()} has been called. */ |
| public boolean isImmutable() { |
| return isImmutable; |
| } |
| |
| /** @return The number of entries in the entry array. */ |
| public int getNumArrayEntries() { |
| return entryList.size(); |
| } |
| |
| /** @return The array entry at the given {@code index}. */ |
| public Map.Entry<K, V> getArrayEntryAt(int index) { |
| return entryList.get(index); |
| } |
| |
| /** @return There number of overflow entries. */ |
| public int getNumOverflowEntries() { |
| return overflowEntries.size(); |
| } |
| |
| /** @return An iterable over the overflow entries. */ |
| public Iterable<Map.Entry<K, V>> getOverflowEntries() { |
| return overflowEntries.isEmpty() ? |
| EmptySet.<Map.Entry<K, V>>iterable() : |
| overflowEntries.entrySet(); |
| } |
| |
| @Override |
| public int size() { |
| return entryList.size() + overflowEntries.size(); |
| } |
| |
| /** |
| * The implementation throws a {@code ClassCastException} if o is not an |
| * object of type {@code K}. |
| * |
| * {@inheritDoc} |
| */ |
| @Override |
| public boolean containsKey(Object o) { |
| @SuppressWarnings("unchecked") |
| final K key = (K) o; |
| return binarySearchInArray(key) >= 0 || overflowEntries.containsKey(key); |
| } |
| |
| /** |
| * The implementation throws a {@code ClassCastException} if o is not an |
| * object of type {@code K}. |
| * |
| * {@inheritDoc} |
| */ |
| @Override |
| public V get(Object o) { |
| @SuppressWarnings("unchecked") |
| final K key = (K) o; |
| final int index = binarySearchInArray(key); |
| if (index >= 0) { |
| return entryList.get(index).getValue(); |
| } |
| return overflowEntries.get(key); |
| } |
| |
| @Override |
| public V put(K key, V value) { |
| checkMutable(); |
| final int index = binarySearchInArray(key); |
| if (index >= 0) { |
| // Replace existing array entry. |
| return entryList.get(index).setValue(value); |
| } |
| ensureEntryArrayMutable(); |
| final int insertionPoint = -(index + 1); |
| if (insertionPoint >= maxArraySize) { |
| // Put directly in overflow. |
| return getOverflowEntriesMutable().put(key, value); |
| } |
| // Insert new Entry in array. |
| if (entryList.size() == maxArraySize) { |
| // Shift the last array entry into overflow. |
| final Entry lastEntryInArray = entryList.remove(maxArraySize - 1); |
| getOverflowEntriesMutable().put(lastEntryInArray.getKey(), |
| lastEntryInArray.getValue()); |
| } |
| entryList.add(insertionPoint, new Entry(key, value)); |
| return null; |
| } |
| |
| @Override |
| public void clear() { |
| checkMutable(); |
| if (!entryList.isEmpty()) { |
| entryList.clear(); |
| } |
| if (!overflowEntries.isEmpty()) { |
| overflowEntries.clear(); |
| } |
| } |
| |
| /** |
| * The implementation throws a {@code ClassCastException} if o is not an |
| * object of type {@code K}. |
| * |
| * {@inheritDoc} |
| */ |
| @Override |
| public V remove(Object o) { |
| checkMutable(); |
| @SuppressWarnings("unchecked") |
| final K key = (K) o; |
| final int index = binarySearchInArray(key); |
| if (index >= 0) { |
| return removeArrayEntryAt(index); |
| } |
| // overflowEntries might be Collections.unmodifiableMap(), so only |
| // call remove() if it is non-empty. |
| if (overflowEntries.isEmpty()) { |
| return null; |
| } else { |
| return overflowEntries.remove(key); |
| } |
| } |
| |
| private V removeArrayEntryAt(int index) { |
| checkMutable(); |
| final V removed = entryList.remove(index).getValue(); |
| if (!overflowEntries.isEmpty()) { |
| // Shift the first entry in the overflow to be the last entry in the |
| // array. |
| final Iterator<Map.Entry<K, V>> iterator = |
| getOverflowEntriesMutable().entrySet().iterator(); |
| entryList.add(new Entry(iterator.next())); |
| iterator.remove(); |
| } |
| return removed; |
| } |
| |
| /** |
| * @param key The key to find in the entry array. |
| * @return The returned integer position follows the same semantics as the |
| * value returned by {@link java.util.Arrays#binarySearch()}. |
| */ |
| private int binarySearchInArray(K key) { |
| int left = 0; |
| int right = entryList.size() - 1; |
| |
| // Optimization: For the common case in which entries are added in |
| // ascending tag order, check the largest element in the array before |
| // doing a full binary search. |
| if (right >= 0) { |
| int cmp = key.compareTo(entryList.get(right).getKey()); |
| if (cmp > 0) { |
| return -(right + 2); // Insert point is after "right". |
| } else if (cmp == 0) { |
| return right; |
| } |
| } |
| |
| while (left <= right) { |
| int mid = (left + right) / 2; |
| int cmp = key.compareTo(entryList.get(mid).getKey()); |
| if (cmp < 0) { |
| right = mid - 1; |
| } else if (cmp > 0) { |
| left = mid + 1; |
| } else { |
| return mid; |
| } |
| } |
| return -(left + 1); |
| } |
| |
| /** |
| * Similar to the AbstractMap implementation of {@code keySet()} and |
| * {@code values()}, the entry set is created the first time this method is |
| * called, and returned in response to all subsequent calls. |
| * |
| * {@inheritDoc} |
| */ |
| @Override |
| public Set<Map.Entry<K, V>> entrySet() { |
| if (lazyEntrySet == null) { |
| lazyEntrySet = new EntrySet(); |
| } |
| return lazyEntrySet; |
| } |
| |
| /** |
| * @throws UnsupportedOperationException if {@link #makeImmutable()} has |
| * has been called. |
| */ |
| private void checkMutable() { |
| if (isImmutable) { |
| throw new UnsupportedOperationException(); |
| } |
| } |
| |
| /** |
| * @return a {@link SortedMap} to which overflow entries mappings can be |
| * added or removed. |
| * @throws UnsupportedOperationException if {@link #makeImmutable()} has been |
| * called. |
| */ |
| @SuppressWarnings("unchecked") |
| private SortedMap<K, V> getOverflowEntriesMutable() { |
| checkMutable(); |
| if (overflowEntries.isEmpty() && !(overflowEntries instanceof TreeMap)) { |
| overflowEntries = new TreeMap<K, V>(); |
| } |
| return (SortedMap<K, V>) overflowEntries; |
| } |
| |
| /** |
| * Lazily creates the entry list. Any code that adds to the list must first |
| * call this method. |
| */ |
| private void ensureEntryArrayMutable() { |
| checkMutable(); |
| if (entryList.isEmpty() && !(entryList instanceof ArrayList)) { |
| entryList = new ArrayList<Entry>(maxArraySize); |
| } |
| } |
| |
| /** |
| * Entry implementation that implements Comparable in order to support |
| * binary search within the entry array. Also checks mutability in |
| * {@link #setValue()}. |
| */ |
| private class Entry implements Map.Entry<K, V>, Comparable<Entry> { |
| |
| private final K key; |
| private V value; |
| |
| Entry(Map.Entry<K, V> copy) { |
| this(copy.getKey(), copy.getValue()); |
| } |
| |
| Entry(K key, V value) { |
| this.key = key; |
| this.value = value; |
| } |
| |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public K getKey() { |
| return key; |
| } |
| |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public V getValue() { |
| return value; |
| } |
| |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public int compareTo(Entry other) { |
| return getKey().compareTo(other.getKey()); |
| } |
| |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public V setValue(V newValue) { |
| checkMutable(); |
| final V oldValue = this.value; |
| this.value = newValue; |
| return oldValue; |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| if (o == this) { |
| return true; |
| } |
| if (!(o instanceof Map.Entry)) { |
| return false; |
| } |
| @SuppressWarnings("unchecked") |
| Map.Entry<?, ?> other = (Map.Entry<?, ?>) o; |
| return equals(key, other.getKey()) && equals(value, other.getValue()); |
| } |
| |
| @Override |
| public int hashCode() { |
| return (key == null ? 0 : key.hashCode()) ^ |
| (value == null ? 0 : value.hashCode()); |
| } |
| |
| @Override |
| public String toString() { |
| return key + "=" + value; |
| } |
| |
| /** equals() that handles null values. */ |
| private boolean equals(Object o1, Object o2) { |
| return o1 == null ? o2 == null : o1.equals(o2); |
| } |
| } |
| |
| /** |
| * Stateless view of the entries in the field map. |
| */ |
| private class EntrySet extends AbstractSet<Map.Entry<K, V>> { |
| |
| @Override |
| public Iterator<Map.Entry<K, V>> iterator() { |
| return new EntryIterator(); |
| } |
| |
| @Override |
| public int size() { |
| return SmallSortedMap.this.size(); |
| } |
| |
| /** |
| * Throws a {@link ClassCastException} if o is not of the expected type. |
| * |
| * {@inheritDoc} |
| */ |
| @Override |
| public boolean contains(Object o) { |
| @SuppressWarnings("unchecked") |
| final Map.Entry<K, V> entry = (Map.Entry<K, V>) o; |
| final V existing = get(entry.getKey()); |
| final V value = entry.getValue(); |
| return existing == value || |
| (existing != null && existing.equals(value)); |
| } |
| |
| @Override |
| public boolean add(Map.Entry<K, V> entry) { |
| if (!contains(entry)) { |
| put(entry.getKey(), entry.getValue()); |
| return true; |
| } |
| return false; |
| } |
| |
| /** |
| * Throws a {@link ClassCastException} if o is not of the expected type. |
| * |
| * {@inheritDoc} |
| */ |
| @Override |
| public boolean remove(Object o) { |
| @SuppressWarnings("unchecked") |
| final Map.Entry<K, V> entry = (Map.Entry<K, V>) o; |
| if (contains(entry)) { |
| SmallSortedMap.this.remove(entry.getKey()); |
| return true; |
| } |
| return false; |
| } |
| |
| @Override |
| public void clear() { |
| SmallSortedMap.this.clear(); |
| } |
| } |
| |
| /** |
| * Iterator implementation that switches from the entry array to the overflow |
| * entries appropriately. |
| */ |
| private class EntryIterator implements Iterator<Map.Entry<K, V>> { |
| |
| private int pos = -1; |
| private boolean nextCalledBeforeRemove; |
| private Iterator<Map.Entry<K, V>> lazyOverflowIterator; |
| |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public boolean hasNext() { |
| return (pos + 1) < entryList.size() || |
| getOverflowIterator().hasNext(); |
| } |
| |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public Map.Entry<K, V> next() { |
| nextCalledBeforeRemove = true; |
| // Always increment pos so that we know whether the last returned value |
| // was from the array or from overflow. |
| if (++pos < entryList.size()) { |
| return entryList.get(pos); |
| } |
| return getOverflowIterator().next(); |
| } |
| |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public void remove() { |
| if (!nextCalledBeforeRemove) { |
| throw new IllegalStateException("remove() was called before next()"); |
| } |
| nextCalledBeforeRemove = false; |
| checkMutable(); |
| |
| if (pos < entryList.size()) { |
| removeArrayEntryAt(pos--); |
| } else { |
| getOverflowIterator().remove(); |
| } |
| } |
| |
| /** |
| * It is important to create the overflow iterator only after the array |
| * entries have been iterated over because the overflow entry set changes |
| * when the client calls remove() on the array entries, which invalidates |
| * any existing iterators. |
| */ |
| private Iterator<Map.Entry<K, V>> getOverflowIterator() { |
| if (lazyOverflowIterator == null) { |
| lazyOverflowIterator = overflowEntries.entrySet().iterator(); |
| } |
| return lazyOverflowIterator; |
| } |
| } |
| |
| /** |
| * Helper class that holds immutable instances of an Iterable/Iterator that |
| * we return when the overflow entries is empty. This eliminates the creation |
| * of an Iterator object when there is nothing to iterate over. |
| */ |
| private static class EmptySet { |
| |
| private static final Iterator<Object> ITERATOR = new Iterator<Object>() { |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public boolean hasNext() { |
| return false; |
| } |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public Object next() { |
| throw new NoSuchElementException(); |
| } |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public void remove() { |
| throw new UnsupportedOperationException(); |
| } |
| }; |
| |
| private static final Iterable<Object> ITERABLE = new Iterable<Object>() { |
| //@Override (Java 1.6 override semantics, but we must support 1.5) |
| public Iterator<Object> iterator() { |
| return ITERATOR; |
| } |
| }; |
| |
| @SuppressWarnings("unchecked") |
| static <T> Iterable<T> iterable() { |
| return (Iterable<T>) ITERABLE; |
| } |
| } |
| } |