Package org.apache.logging.log4j.util

Class SortedArrayStringMap

  • All Implemented Interfaces:
    java.io.Serializable, IndexedReadOnlyStringMap, IndexedStringMap, ReadOnlyStringMap, StringMap
    public class SortedArrayStringMap
extends java.lang.Object
implements IndexedStringMap
    Consider this class private. Array-based implementation of the ReadOnlyStringMap interface. Keys are held in a sorted array.

    This is not a generic collection, but makes some trade-offs to optimize for the Log4j context data use case:

    • Garbage-free iteration over key-value pairs with BiConsumer and TriConsumer.
    • Fast copy. If the ThreadContextMap is also an instance of SortedArrayStringMap, the full thread context data can be transferred with two array copies and two field updates.
    • Acceptable performance for small data sets. The current implementation stores keys in a sorted array, values are stored in a separate array at the same index. Worst-case performance of get and containsKey is O(log N), worst-case performance of put and remove is O(N log N). The expectation is that for the small values of N (less than 100) that are the vast majority of ThreadContext use cases, the constants dominate performance more than the asymptotic performance of the algorithms used.
    • Compact representation.
    Since:
    2.7
    See Also:
    Serialized Form

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void assertNoConcurrentModification()  
      private void assertNotFrozen()  
      private static int ceilingNextPowerOfTwo​(int x)
      Calculate the next power of 2, greater than or equal to x.
      void clear()
      Removes all key-value pairs from this collection.
      boolean containsKey​(java.lang.String key)
      Returns true if this data structure contains the specified key, false otherwise.
      private void ensureCapacity()  
      boolean equals​(java.lang.Object obj)
      Indicates whether some other object is "equal to" this one.
      <V> void forEach​(BiConsumer<java.lang.String,​? super V> action)
      Performs the given action for each key-value pair in this data structure until all entries have been processed or the action throws an exception.
      <V,​T>
      void      		 forEach​(TriConsumer<java.lang.String,​? super V,​T> action, T state)
      Performs the given action for each key-value pair in this data structure until all entries have been processed or the action throws an exception.
      void freeze()
      Makes this collection immutable.
      java.lang.String getKeyAt​(int index)
      Viewing all key-value pairs as a sequence sorted by key, this method returns the key at the specified index, or null if the specified index is less than zero or greater or equal to the size of this collection.
      <V> V getValue​(java.lang.String key)
      Returns the value for the specified key, or null if the specified key does not exist in this collection.
      <V> V getValueAt​(int index)
      Viewing all key-value pairs as a sequence sorted by key, this method returns the value at the specified index, or null if the specified index is less than zero or greater or equal to the size of this collection.
      private void handleSerializationException​(java.lang.Throwable t, int i, java.lang.String key)  
      int hashCode()
      Returns a hash code value for the object.
      private static int hashCode​(java.lang.Object[] values, int length)  
      int indexOfKey​(java.lang.String key)
      Viewing all key-value pairs as a sequence sorted by key, this method returns the index of the specified key in that sequence.
      private void inflateTable​(int toSize)
      Inflates the table.
      private void initFrom0​(SortedArrayStringMap other)  
      private void insertAt​(int index, java.lang.String key, java.lang.Object value)  
      boolean isEmpty()
      Returns true if this collection is empty (size is zero), false otherwise.
      boolean isFrozen()
      Returns true if this object has been frozen, false otherwise.
      private static byte[] marshall​(java.lang.Object obj)  
      private void merge​(SortedArrayStringMap other)  
      private int nullKeyIndex()  
      void putAll​(ReadOnlyStringMap source)
      Copies all key-value pairs from the specified ReadOnlyStringMap into this StringMap.
      void putValue​(java.lang.String key, java.lang.Object value)
      Puts the specified key-value pair into the collection.
      private void readObject​(java.io.ObjectInputStream s)
      Reconstitute the SortedArrayStringMap instance from a stream (i.e., deserialize it).
      void remove​(java.lang.String key)
      Removes the key-value pair for the specified key from this data structure.
      private void resize​(int newCapacity)  
      int size()
      Returns the number of key-value pairs in this collection.
      java.util.Map<java.lang.String,​java.lang.String> toMap()
      Returns a non-null mutable Map<String, String> containing a snapshot of this data structure.
      java.lang.String toString()  
      private static java.lang.Object unmarshall​(byte[] data, java.io.ObjectInputStream inputStream)  
      private void writeObject​(java.io.ObjectOutputStream s)
      Save the state of the SortedArrayStringMap instance to a stream (i.e., serialize it).

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • DEFAULT_INITIAL_CAPACITY

        private static final int DEFAULT_INITIAL_CAPACITY
        The default initial capacity.
        See Also:
        Constant Field Values

      • PUT_ALL

        private static final TriConsumer<java.lang.String,​java.lang.Object,​StringMap> PUT_ALL

      • EMPTY

        private static final java.lang.String[] EMPTY
        An empty array instance to share when the table is not inflated.

      • keys

        private transient java.lang.String[] keys

      • values

        private transient java.lang.Object[] values

      • size

        private transient int size
        The number of key-value mappings contained in this map.

      • setObjectInputFilter

        private static final java.lang.reflect.Method setObjectInputFilter

      • getObjectInputFilter

        private static final java.lang.reflect.Method getObjectInputFilter

      • newObjectInputFilter

        private static final java.lang.reflect.Method newObjectInputFilter

      • threshold

        private int threshold
        The next size value at which to resize (capacity * load factor).

      • immutable

        private boolean immutable

      • iterating

        private transient boolean iterating

    • Constructor Detail

      • SortedArrayStringMap

        public SortedArrayStringMap()

      • SortedArrayStringMap

        public SortedArrayStringMap​(int initialCapacity)

      • SortedArrayStringMap

        public SortedArrayStringMap​(java.util.Map<java.lang.String,​?> map)

    • Method Detail

      • assertNotFrozen

        private void assertNotFrozen()

      • assertNoConcurrentModification

        private void assertNoConcurrentModification()

      • clear

        public void clear()
        Description copied from interface: StringMap
        Removes all key-value pairs from this collection.
        Specified by:
        clear in interface StringMap

      • containsKey

        public boolean containsKey​(java.lang.String key)
        Description copied from interface: ReadOnlyStringMap
        Returns true if this data structure contains the specified key, false otherwise.
        Specified by:
        containsKey in interface ReadOnlyStringMap
        Parameters:
        key - the key whose presence to check. May be null.
        Returns:
        true if this data structure contains the specified key, false otherwise.

      • toMap

        public java.util.Map<java.lang.String,​java.lang.String> toMap()
        Description copied from interface: ReadOnlyStringMap
        Returns a non-null mutable Map<String, String> containing a snapshot of this data structure.
        Specified by:
        toMap in interface ReadOnlyStringMap
        Returns:
        a mutable copy of this data structure in Map<String, String> form.

      • freeze

        public void freeze()
        Description copied from interface: StringMap
        Makes this collection immutable. Attempts to modify the collection after the freeze() method was called will result in an UnsupportedOperationException being thrown.
        Specified by:
        freeze in interface StringMap

      • isFrozen

        public boolean isFrozen()
        Description copied from interface: StringMap
        Returns true if this object has been frozen, false otherwise.
        Specified by:
        isFrozen in interface StringMap
        Returns:
        true if this object has been frozen, false otherwise

      • getValue

        public <V> V getValue​(java.lang.String key)
        Description copied from interface: ReadOnlyStringMap
        Returns the value for the specified key, or null if the specified key does not exist in this collection.
        Specified by:
        getValue in interface ReadOnlyStringMap
        Parameters:
        key - the key whose value to return.
        Returns:
        the value for the specified key or null.

      • isEmpty

        public boolean isEmpty()
        Description copied from interface: ReadOnlyStringMap
        Returns true if this collection is empty (size is zero), false otherwise.
        Specified by:
        isEmpty in interface ReadOnlyStringMap
        Returns:
        true if this collection is empty (size is zero).

      • indexOfKey

        public int indexOfKey​(java.lang.String key)
        Description copied from interface: IndexedReadOnlyStringMap
        Viewing all key-value pairs as a sequence sorted by key, this method returns the index of the specified key in that sequence. If the specified key is not found, this method returns (-(insertion point) - 1).
        Specified by:
        indexOfKey in interface IndexedReadOnlyStringMap
        Parameters:
        key - the key whose index in the ordered sequence of keys to return
        Returns:
        the index of the specified key or (-(insertion point) - 1) if the key is not found. The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or size() if all elements are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

      • nullKeyIndex

        private int nullKeyIndex()

      • putValue

        public void putValue​(java.lang.String key,
                     java.lang.Object value)
        Description copied from interface: StringMap
        Puts the specified key-value pair into the collection.
        Specified by:
        putValue in interface StringMap
        Parameters:
        key - the key to add or remove. Keys may be null.
        value - the value to add. Values may be null.

      • insertAt

        private void insertAt​(int index,
                      java.lang.String key,
                      java.lang.Object value)

      • putAll

        public void putAll​(ReadOnlyStringMap source)
        Description copied from interface: StringMap
        Copies all key-value pairs from the specified ReadOnlyStringMap into this StringMap.
        Specified by:
        putAll in interface StringMap
        Parameters:
        source - the ReadOnlyStringMap to copy key-value pairs from

      • ensureCapacity

        private void ensureCapacity()

      • resize

        private void resize​(int newCapacity)

      • inflateTable

        private void inflateTable​(int toSize)
        Inflates the table.

      • remove

        public void remove​(java.lang.String key)
        Description copied from interface: StringMap
        Removes the key-value pair for the specified key from this data structure.
        Specified by:
        remove in interface StringMap
        Parameters:
        key - the key to remove. May be null.

      • getKeyAt

        public java.lang.String getKeyAt​(int index)
        Description copied from interface: IndexedReadOnlyStringMap
        Viewing all key-value pairs as a sequence sorted by key, this method returns the key at the specified index, or null if the specified index is less than zero or greater or equal to the size of this collection.
        Specified by:
        getKeyAt in interface IndexedReadOnlyStringMap
        Parameters:
        index - the index of the key to return
        Returns:
        the key at the specified index or null

      • getValueAt

        public <V> V getValueAt​(int index)
        Description copied from interface: IndexedReadOnlyStringMap
        Viewing all key-value pairs as a sequence sorted by key, this method returns the value at the specified index, or null if the specified index is less than zero or greater or equal to the size of this collection.
        Specified by:
        getValueAt in interface IndexedReadOnlyStringMap
        Parameters:
        index - the index of the value to return
        Returns:
        the value at the specified index or null

      • size

        public int size()
        Description copied from interface: ReadOnlyStringMap
        Returns the number of key-value pairs in this collection.
        Specified by:
        size in interface ReadOnlyStringMap
        Returns:
        the number of key-value pairs in this collection.

      • forEach

        public <V> void forEach​(BiConsumer<java.lang.String,​? super V> action)
        Description copied from interface: ReadOnlyStringMap
        Performs the given action for each key-value pair in this data structure until all entries have been processed or the action throws an exception.

        Some implementations may not support structural modifications (adding new elements or removing elements) while iterating over the contents. In such implementations, attempts to add or remove elements from the BiConsumer's BiConsumer.accept(Object, Object) accept} method may cause a ConcurrentModificationException to be thrown.

        Specified by:
        forEach in interface ReadOnlyStringMap
        Type Parameters:
        V - type of the value.
        Parameters:
        action - The action to be performed for each key-value pair in this collection.

      • forEach

        public <V,​T> void forEach​(TriConsumer<java.lang.String,​? super V,​T> action,
                                T state)
        Description copied from interface: ReadOnlyStringMap
        Performs the given action for each key-value pair in this data structure until all entries have been processed or the action throws an exception.

        The third parameter lets callers pass in a stateful object to be modified with the key-value pairs, so the TriConsumer implementation itself can be stateless and potentially reusable.

        Some implementations may not support structural modifications (adding new elements or removing elements) while iterating over the contents. In such implementations, attempts to add or remove elements from the TriConsumer's accept method may cause a ConcurrentModificationException to be thrown.

        Specified by:
        forEach in interface ReadOnlyStringMap
        Type Parameters:
        V - type of the value.
        T - type of the third parameter.
        Parameters:
        action - The action to be performed for each key-value pair in this collection.
        state - the object to be passed as the third parameter to each invocation on the specified triconsumer.

      • equals

        public boolean equals​(java.lang.Object obj)
        Description copied from interface: StringMap
        Indicates whether some other object is "equal to" this one.
        Specified by:
        equals in interface StringMap
        Overrides:
        equals in class java.lang.Object
        Parameters:
        obj - the reference object with which to compare.
        Returns:
        true if this object is the same as the obj argument; false otherwise.
        See Also:
        StringMap.hashCode()

      • hashCode

        public int hashCode()
        Description copied from interface: StringMap
        Returns a hash code value for the object.
        Specified by:
        hashCode in interface StringMap
        Overrides:
        hashCode in class java.lang.Object
        Returns:
        a hash code value for this object.

      • hashCode

        private static int hashCode​(java.lang.Object[] values,
                            int length)

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • writeObject

        private void writeObject​(java.io.ObjectOutputStream s)
                  throws java.io.IOException
        Save the state of the SortedArrayStringMap instance to a stream (i.e., serialize it).
        Throws:
        java.io.IOException

      • marshall

        private static byte[] marshall​(java.lang.Object obj)
                        throws java.io.IOException
        Throws:
        java.io.IOException

      • unmarshall

        private static java.lang.Object unmarshall​(byte[] data,
                                           java.io.ObjectInputStream inputStream)
                                    throws java.io.IOException,
                                           java.lang.ClassNotFoundException
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException

      • ceilingNextPowerOfTwo

        private static int ceilingNextPowerOfTwo​(int x)
        Calculate the next power of 2, greater than or equal to x.

        From Hacker's Delight, Chapter 3, Harry S. Warren Jr.

        Parameters:
        x - Value to round up
        Returns:
        The next power of 2 from x inclusive

      • readObject

        private void readObject​(java.io.ObjectInputStream s)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException
        Reconstitute the SortedArrayStringMap instance from a stream (i.e., deserialize it).
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException

      • handleSerializationException

        private void handleSerializationException​(java.lang.Throwable t,
                                          int i,
                                          java.lang.String key)