Class SmallSortedMap<K extends Comparable<K>,V>

java.lang.Object
java.util.AbstractMap<K,V>
com.google.protobuf.SmallSortedMap<K,V>
All Implemented Interfaces:
Map<K,V>

class SmallSortedMap<K extends Comparable<K>,V> extends AbstractMap<K,V>
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 k mappings in an array for a configurable value of k, allowing direct access to the corresponding Entrys 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:

 for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) {
   process(fieldMap.getArrayEntryAt(i));
 }
 for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) {
   process(entry);
 }
 
The resulting iteration is in order of ascending field tag number. The object returned by entrySet() adheres to the same contract but is less efficient as it necessarily involves creating an object for iteration.

The tradeoff for this memory efficiency is that the worst case running time of the put() operation is O(k + lg n), which happens when entries are added in descending order. 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.

The running time for all other operations is similar to that of TreeMap.

Instances are not thread-safe until makeImmutable() is called, after which any modifying operation will result in an UnsupportedOperationException.

  • Field Details

    • DEFAULT_FIELD_MAP_ARRAY_SIZE

      static final int DEFAULT_FIELD_MAP_ARRAY_SIZE
      See Also:
    • entries

      private Object[] entries
    • entriesSize

      private int entriesSize
    • overflowEntries

      private Map<K extends Comparable<K>,V> overflowEntries
    • isImmutable

      private boolean isImmutable
    • lazyEntrySet

      private volatile SmallSortedMap<K extends Comparable<K>,V>.EntrySet lazyEntrySet
    • overflowEntriesDescending

      private Map<K extends Comparable<K>,V> overflowEntriesDescending
  • Constructor Details

    • SmallSortedMap

      private SmallSortedMap()
  • Method Details

    • newFieldMap

      static <FieldDescriptorT extends FieldSet.FieldDescriptorLite<FieldDescriptorT>> SmallSortedMap<FieldDescriptorT,Object> newFieldMap()
      Creates a new instance for mapping FieldDescriptors to their values. The makeImmutable() implementation will convert the List values of any repeated fields to unmodifiable lists.
    • newInstanceForTest

      static <K extends Comparable<K>, V> SmallSortedMap<K,V> newInstanceForTest()
      Creates a new instance for testing.
    • makeImmutable

      public void makeImmutable()
      Make this map immutable from this point forward.
    • isImmutable

      public boolean isImmutable()
      Returns:
      Whether makeImmutable() has been called.
    • getNumArrayEntries

      public int getNumArrayEntries()
      Returns:
      The number of entries in the entry array.
    • getArrayEntryAt

      public Map.Entry<K,V> getArrayEntryAt(int index)
      Returns:
      The array entry at the given index.
    • getNumOverflowEntries

      public int getNumOverflowEntries()
      Returns:
      There number of overflow entries.
    • getOverflowEntries

      public Iterable<Map.Entry<K,V>> getOverflowEntries()
      Returns:
      An iterable over the overflow entries.
    • size

      public int size()
      Specified by:
      size in interface Map<K extends Comparable<K>,V>
      Overrides:
      size in class AbstractMap<K extends Comparable<K>,V>
    • containsKey

      public boolean containsKey(Object o)
      The implementation throws a ClassCastException if o is not an object of type K.

      Specified by:
      containsKey in interface Map<K extends Comparable<K>,V>
      Overrides:
      containsKey in class AbstractMap<K extends Comparable<K>,V>
    • get

      public V get(Object o)
      The implementation throws a ClassCastException if o is not an object of type K.

      Specified by:
      get in interface Map<K extends Comparable<K>,V>
      Overrides:
      get in class AbstractMap<K extends Comparable<K>,V>
    • put

      public V put(K key, V value)
      Specified by:
      put in interface Map<K extends Comparable<K>,V>
      Overrides:
      put in class AbstractMap<K extends Comparable<K>,V>
    • clear

      public void clear()
      Specified by:
      clear in interface Map<K extends Comparable<K>,V>
      Overrides:
      clear in class AbstractMap<K extends Comparable<K>,V>
    • remove

      public V remove(Object o)
      The implementation throws a ClassCastException if o is not an object of type K.

      Specified by:
      remove in interface Map<K extends Comparable<K>,V>
      Overrides:
      remove in class AbstractMap<K extends Comparable<K>,V>
    • removeArrayEntryAt

      private V removeArrayEntryAt(int index)
    • binarySearchInArray

      private int binarySearchInArray(K key)
      Parameters:
      key - The key to find in the entry array.
      Returns:
      The returned integer position follows the same semantics as the value returned by
      invalid reference
      java.util.Arrays#binarySearch()
      .
    • entrySet

      public Set<Map.Entry<K,V>> entrySet()
      Similar to the AbstractMap implementation of keySet() and values(), the entry set is created the first time this method is called, and returned in response to all subsequent calls.

      Specified by:
      entrySet in interface Map<K extends Comparable<K>,V>
      Specified by:
      entrySet in class AbstractMap<K extends Comparable<K>,V>
    • descendingEntrySet

      Set<Map.Entry<K,V>> descendingEntrySet()
    • checkMutable

      private void checkMutable()
      Throws:
      UnsupportedOperationException - if makeImmutable() has has been called.
    • getOverflowEntriesMutable

      private SortedMap<K,V> getOverflowEntriesMutable()
      Returns:
      a SortedMap to which overflow entries mappings can be added or removed.
      Throws:
      UnsupportedOperationException - if makeImmutable() has been called.
    • ensureEntryArrayMutable

      private void ensureEntryArrayMutable()
      Lazily creates the entry array. Any code that adds to the array must first call this method.
    • equals

      public boolean equals(Object o)
      Specified by:
      equals in interface Map<K extends Comparable<K>,V>
      Overrides:
      equals in class AbstractMap<K extends Comparable<K>,V>
    • hashCode

      public int hashCode()
      Specified by:
      hashCode in interface Map<K extends Comparable<K>,V>
      Overrides:
      hashCode in class AbstractMap<K extends Comparable<K>,V>