diff options
Diffstat (limited to 'java/core/src/main/java/com/google/protobuf/SmallSortedMap.java')
| -rw-r--r-- | java/core/src/main/java/com/google/protobuf/SmallSortedMap.java | 182 |
1 files changed, 78 insertions, 104 deletions
diff --git a/java/core/src/main/java/com/google/protobuf/SmallSortedMap.java b/java/core/src/main/java/com/google/protobuf/SmallSortedMap.java index 279edc4d..6bd65d6f 100644 --- a/java/core/src/main/java/com/google/protobuf/SmallSortedMap.java +++ b/java/core/src/main/java/com/google/protobuf/SmallSortedMap.java @@ -43,15 +43,14 @@ import java.util.SortedMap; import java.util.TreeMap; /** - * 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: + * 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 + * <pre>{@code * for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) { * process(fieldMap.getArrayEntryAt(i)); * } @@ -60,24 +59,21 @@ import java.util.TreeMap; * } * }</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}. + * 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 */ @@ -87,15 +83,14 @@ import java.util.TreeMap; 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. + * 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. + * @param arraySize The size of the entry array containing the lexicographically smallest + * mappings. */ - static <FieldDescriptorType extends - FieldSet.FieldDescriptorLite<FieldDescriptorType>> + static <FieldDescriptorType extends FieldSet.FieldDescriptorLite<FieldDescriptorType>> SmallSortedMap<FieldDescriptorType, Object> newFieldMap(int arraySize) { return new SmallSortedMap<FieldDescriptorType, Object>(arraySize) { @Override @@ -103,15 +98,13 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { public void makeImmutable() { if (!isImmutable()) { for (int i = 0; i < getNumArrayEntries(); i++) { - final Map.Entry<FieldDescriptorType, Object> entry = - getArrayEntryAt(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()) { + for (Map.Entry<FieldDescriptorType, Object> entry : getOverflowEntries()) { if (entry.getKey().isRepeated()) { final List value = (List) entry.getValue(); entry.setValue(Collections.unmodifiableList(value)); @@ -126,11 +119,10 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { /** * Creates a new instance for testing. * - * @param arraySize The size of the entry array containing the - * lexicographically smallest mappings. + * @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) { + static <K extends Comparable<K>, V> SmallSortedMap<K, V> newInstanceForTest(int arraySize) { return new SmallSortedMap<K, V>(arraySize); } @@ -146,9 +138,8 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { 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). + * @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; @@ -163,9 +154,10 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { // 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); + overflowEntries = + overflowEntries.isEmpty() + ? Collections.<K, V>emptyMap() + : Collections.unmodifiableMap(overflowEntries); isImmutable = true; } } @@ -192,9 +184,9 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { /** @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(); + return overflowEntries.isEmpty() + ? EmptySet.<Map.Entry<K, V>>iterable() + : overflowEntries.entrySet(); } @@ -204,10 +196,9 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } /** - * The implementation throws a {@code ClassCastException} if o is not an - * object of type {@code K}. + * The implementation throws a {@code ClassCastException} if o is not an object of type {@code K}. * - * {@inheritDoc} + * <p>{@inheritDoc} */ @Override public boolean containsKey(Object o) { @@ -217,10 +208,9 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } /** - * The implementation throws a {@code ClassCastException} if o is not an - * object of type {@code K}. + * The implementation throws a {@code ClassCastException} if o is not an object of type {@code K}. * - * {@inheritDoc} + * <p>{@inheritDoc} */ @Override public V get(Object o) { @@ -251,8 +241,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { if (entryList.size() == maxArraySize) { // Shift the last array entry into overflow. final Entry lastEntryInArray = entryList.remove(maxArraySize - 1); - getOverflowEntriesMutable().put(lastEntryInArray.getKey(), - lastEntryInArray.getValue()); + getOverflowEntriesMutable().put(lastEntryInArray.getKey(), lastEntryInArray.getValue()); } entryList.add(insertionPoint, new Entry(key, value)); return null; @@ -270,10 +259,9 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } /** - * The implementation throws a {@code ClassCastException} if o is not an - * object of type {@code K}. + * The implementation throws a {@code ClassCastException} if o is not an object of type {@code K}. * - * {@inheritDoc} + * <p>{@inheritDoc} */ @Override public V remove(Object o) { @@ -299,8 +287,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { 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(); + final Iterator<Map.Entry<K, V>> iterator = getOverflowEntriesMutable().entrySet().iterator(); entryList.add(new Entry(iterator.next())); iterator.remove(); } @@ -309,8 +296,8 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { /** * @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()}. + * @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; @@ -322,7 +309,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { if (right >= 0) { int cmp = key.compareTo(entryList.get(right).getKey()); if (cmp > 0) { - return -(right + 2); // Insert point is after "right". + return -(right + 2); // Insert point is after "right". } else if (cmp == 0) { return right; } @@ -343,11 +330,11 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } /** - * 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. + * 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} + * <p>{@inheritDoc} */ @Override public Set<Map.Entry<K, V>> entrySet() { @@ -358,10 +345,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } - /** - * @throws UnsupportedOperationException if {@link #makeImmutable()} has - * has been called. - */ + /** @throws UnsupportedOperationException if {@link #makeImmutable()} has has been called. */ private void checkMutable() { if (isImmutable) { throw new UnsupportedOperationException(); @@ -369,10 +353,8 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } /** - * @return a {@link SortedMap} to which overflow entries mappings can be - * added or removed. - * @throws UnsupportedOperationException if {@link #makeImmutable()} has been - * called. + * @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() { @@ -383,10 +365,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { return (SortedMap<K, V>) overflowEntries; } - /** - * Lazily creates the entry list. Any code that adds to the list must first - * call this method. - */ + /** 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)) { @@ -395,9 +374,8 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } /** - * Entry implementation that implements Comparable in order to support - * binary search within the entry array. Also checks mutability in - * {@link #setValue()}. + * 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> { @@ -451,8 +429,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { @Override public int hashCode() { - return (key == null ? 0 : key.hashCode()) ^ - (value == null ? 0 : value.hashCode()); + return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode()); } @Override @@ -466,9 +443,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } } - /** - * Stateless view of the entries in the field map. - */ + /** Stateless view of the entries in the field map. */ private class EntrySet extends AbstractSet<Map.Entry<K, V>> { @Override @@ -484,7 +459,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { /** * Throws a {@link ClassCastException} if o is not of the expected type. * - * {@inheritDoc} + * <p>{@inheritDoc} */ @Override public boolean contains(Object o) { @@ -492,8 +467,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { 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)); + return existing == value || (existing != null && existing.equals(value)); } @Override @@ -508,7 +482,7 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { /** * Throws a {@link ClassCastException} if o is not of the expected type. * - * {@inheritDoc} + * <p>{@inheritDoc} */ @Override public boolean remove(Object o) { @@ -529,8 +503,8 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { /** - * Iterator implementation that switches from the entry array to the overflow - * entries appropriately. + * Iterator implementation that switches from the entry array to the overflow entries + * appropriately. */ private class EntryIterator implements Iterator<Map.Entry<K, V>> { @@ -571,10 +545,9 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } /** - * 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. + * 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) { @@ -585,9 +558,9 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { } /** - * 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. + * 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 { @@ -597,10 +570,12 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { public boolean hasNext() { return false; } + @Override public Object next() { throw new NoSuchElementException(); } + @Override public void remove() { throw new UnsupportedOperationException(); @@ -653,7 +628,6 @@ class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> { return overflowEntries.equals(other.overflowEntries); } - return true; } |