diff options
Diffstat (limited to 'java/src/main/java/com/google/protobuf/SmallSortedMap.java')
| -rw-r--r-- | java/src/main/java/com/google/protobuf/SmallSortedMap.java | 618 |
1 files changed, 618 insertions, 0 deletions
diff --git a/java/src/main/java/com/google/protobuf/SmallSortedMap.java b/java/src/main/java/com/google/protobuf/SmallSortedMap.java new file mode 100644 index 0000000..0674d2e --- /dev/null +++ b/java/src/main/java/com/google/protobuf/SmallSortedMap.java @@ -0,0 +1,618 @@ +// 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; + } + } +} |