Package com.google.protobuf

Class SmallSortedMap<K extends FieldSet.FieldDescriptorLite<K>>

  • All Implemented Interfaces:
    java.util.Map<K,​java.lang.Object>
    class SmallSortedMap<K extends FieldSet.FieldDescriptorLite<K>>
extends java.util.AbstractMap<K,​java.lang.Object>
    A custom map implementation from FieldSet.FieldDescriptorLite to Object.

    This implementation is heavily optimized for insertion and iteration when the map is built (via put()) with keys (FieldDescriptors) in ascending sorted order. When entries are added in increasing order of the FieldDescriptor, no sorting overhead is incurred. The entries are simply appended to a backing array, making memory allocation and insertion highly efficient.

    Iteration over the entries is straightforward and avoids the creation of an Iterator object. It should be done as follows: 

    
 for (int i = 0; i < fieldMap.size(); i++) {
   process(fieldMap.getArrayEntryAt(i));
 }
    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.

    If entries are added out of order, the map defers sorting until necessary (e.g., when iterating, querying size, or retrieving elements). This lazily sorts and deduplicates the underlying array.

    Modifying operations (such as put(), remove(), or clear()) are not thread-safe until makeImmutable() is called, after which any modifying operation will result in an UnsupportedOperationException. However, instances are thread-safe for concurrent read-only operations (such as get() or size()) even before makeImmutable() is called, as long as no modifying operations are performed concurrently.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private class  SmallSortedMap.Entry
      Entry implementation that implements Comparable in order to support binary search within the entry array.
      private class  SmallSortedMap.EntryIterator
      Iterator implementation that switches from the entry array to the overflow entries appropriately.
      private class  SmallSortedMap.EntrySet
      Stateless view of the entries in the field map.

      • Nested classes/interfaces inherited from class java.util.AbstractMap

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private int binarySearch​(K key)  
      private void checkMutable()  
      void clear()  
      boolean containsKey​(java.lang.Object o)
      The implementation throws a ClassCastException if o is not an object of type K.
      private void ensureCapacity​(int minCapacity)  
      private void ensureSortedAndDeduplicated()
      Ensures that the entries in the map are sorted and deduplicated.
      java.util.Set<java.util.Map.Entry<K,​java.lang.Object>> 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.
      boolean equals​(java.lang.Object o)  
      java.lang.Object get​(java.lang.Object o)
      The implementation throws a ClassCastException if o is not an object of type K.
      java.util.Map.Entry<K,​java.lang.Object> getArrayEntryAt​(int index)  
      int hashCode()  
      boolean isEmpty()  
      boolean isImmutable()  
      void makeImmutable()
      Make this map immutable from this point forward.
      java.lang.Object put​(K key, java.lang.Object value)  
      void putAll​(java.util.Map<? extends K,​?> map)  
      java.lang.Object remove​(java.lang.Object o)
      The implementation throws a ClassCastException if o is not an object of type K.
      int size()  

      • Methods inherited from class java.util.AbstractMap

        clone, containsValue, keySet, toString, values

      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.util.Map

        compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll

    • Field Detail

      • DEFAULT_FIELD_MAP_ARRAY_SIZE

        static final int DEFAULT_FIELD_MAP_ARRAY_SIZE
        See Also:
        Constant Field Values

      • entries

        private java.lang.Object[] entries

      • size

        private int size

      • isImmutable

        private boolean isImmutable

      • isSortedAndDedupped

        private volatile boolean isSortedAndDedupped

    • Constructor Detail

      • SmallSortedMap

        SmallSortedMap()

      • SmallSortedMap

        SmallSortedMap​(int initialCapacity)

    • Method Detail

      • makeImmutable

        public void makeImmutable()
        Make this map immutable from this point forward. Immutable maps are guaranteed to be sorted and deduplicated.

      • isImmutable

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

      • getArrayEntryAt

        public java.util.Map.Entry<K,​java.lang.Object> getArrayEntryAt​(int index)
        Returns:
        The array entry at the given index.

      • 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 FieldSet.FieldDescriptorLite<K>,​java.lang.Object>
        Overrides:
        containsKey in class java.util.AbstractMap<K extends FieldSet.FieldDescriptorLite<K>,​java.lang.Object>

      • get

        public java.lang.Object 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 FieldSet.FieldDescriptorLite<K>,​java.lang.Object>
        Overrides:
        get in class java.util.AbstractMap<K extends FieldSet.FieldDescriptorLite<K>,​java.lang.Object>

      • ensureCapacity

        private void ensureCapacity​(int minCapacity)

      • ensureSortedAndDeduplicated

        private void ensureSortedAndDeduplicated()
        Ensures that the entries in the map are sorted and deduplicated.

        Immutable maps are guaranteed to be already sorted and deduplicated.

      • binarySearch

        private int binarySearch​(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,​java.lang.Object>> 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 FieldSet.FieldDescriptorLite<K>,​java.lang.Object>
        Specified by:
        entrySet in class java.util.AbstractMap<K extends FieldSet.FieldDescriptorLite<K>,​java.lang.Object>

      • checkMutable

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