Class SmallSortedMap<K extends java.lang.Comparable<K>,​V>

  • All Implemented Interfaces:
    java.util.Map<K,​V>

    class SmallSortedMap<K extends java.lang.Comparable<K>,​V>
    extends java.util.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 Detail

      • DEFAULT_FIELD_MAP_ARRAY_SIZE

        static final int DEFAULT_FIELD_MAP_ARRAY_SIZE
        See Also:
        Constant Field Values
      • overflowEntries

        private java.util.Map<K extends java.lang.Comparable<K>,​V> overflowEntries
      • isImmutable

        private boolean isImmutable
      • overflowEntriesDescending

        private java.util.Map<K extends java.lang.Comparable<K>,​V> overflowEntriesDescending
    • Constructor Detail

      • SmallSortedMap

        private SmallSortedMap()
    • Method Detail

      • newFieldMap

        static <FieldDescriptorType extends FieldSet.FieldDescriptorLite<FieldDescriptorType>> SmallSortedMap<FieldDescriptorType,​java.lang.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.
        Parameters:
        arraySize - The size of the entry array containing the lexicographically smallest mappings.
      • newInstanceForTest

        static <K extends java.lang.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 java.util.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 java.lang.Iterable<java.util.Map.Entry<K,​V>> getOverflowEntries()
        Returns:
        An iterable over the overflow entries.
      • size

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

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

        Specified by:
        containsKey in interface java.util.Map<K extends java.lang.Comparable<K>,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K extends java.lang.Comparable<K>,​V>
      • get

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

        Specified by:
        get in interface java.util.Map<K extends java.lang.Comparable<K>,​V>
        Overrides:
        get in class java.util.AbstractMap<K extends java.lang.Comparable<K>,​V>
      • put

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

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

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

        Specified by:
        remove in interface java.util.Map<K extends java.lang.Comparable<K>,​V>
        Overrides:
        remove in class java.util.AbstractMap<K extends java.lang.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 java.util.Arrays#binarySearch().
      • entrySet

        public java.util.Set<java.util.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 java.util.Map<K extends java.lang.Comparable<K>,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<K extends java.lang.Comparable<K>,​V>
      • descendingEntrySet

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

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

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

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

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

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