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, 0 insertions, 618 deletions
diff --git a/java/src/main/java/com/google/protobuf/SmallSortedMap.java b/java/src/main/java/com/google/protobuf/SmallSortedMap.java deleted file mode 100644 index 0674d2e..0000000 --- a/java/src/main/java/com/google/protobuf/SmallSortedMap.java +++ /dev/null @@ -1,618 +0,0 @@ -// 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; - } - } -} |