Class SortedArrayStringMap

java.lang.Object
org.apache.logging.log4j.util.SortedArrayStringMap
All Implemented Interfaces:
Serializable, IndexedReadOnlyStringMap, IndexedStringMap, ReadOnlyStringMap, StringMap

public class SortedArrayStringMap extends 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:
  • Field Details

    • DEFAULT_INITIAL_CAPACITY

      private static final int DEFAULT_INITIAL_CAPACITY
      The default initial capacity.
      See Also:
    • serialVersionUID

      private static final long serialVersionUID
      See Also:
    • HASHVAL

      private static final int HASHVAL
      See Also:
    • PUT_ALL

      private static final TriConsumer<String,Object,StringMap> PUT_ALL
    • EMPTY

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

      private static final String FROZEN
      See Also:
    • keys

      private transient String[] keys
    • values

      private transient Object[] values
    • size

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

      private static final Method setObjectInputFilter
    • getObjectInputFilter

      private static final Method getObjectInputFilter
    • newObjectInputFilter

      private static final 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 Details

    • SortedArrayStringMap

      public SortedArrayStringMap()
    • SortedArrayStringMap

      public SortedArrayStringMap(int initialCapacity)
    • SortedArrayStringMap

      public SortedArrayStringMap(ReadOnlyStringMap other)
    • SortedArrayStringMap

      public SortedArrayStringMap(Map<String,?> map)
  • Method Details

    • 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(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 Map<String,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(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(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(String key, 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, String key, 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
    • initFrom0

      private void initFrom0(SortedArrayStringMap other)
    • merge

      private void merge(SortedArrayStringMap other)
    • ensureCapacity

      private void ensureCapacity()
    • resize

      private void resize(int newCapacity)
    • inflateTable

      private void inflateTable(int toSize)
      Inflates the table.
    • remove

      public void remove(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 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<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<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(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 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:
    • 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 Object
      Returns:
      a hash code value for this object.
    • hashCode

      private static int hashCode(Object[] values, int length)
    • toString

      public String toString()
      Overrides:
      toString in class Object
    • writeObject

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

      private static byte[] marshall(Object obj) throws IOException
      Throws:
      IOException
    • unmarshall

      private static Object unmarshall(byte[] data, ObjectInputStream inputStream) throws IOException, ClassNotFoundException
      Throws:
      IOException
      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(ObjectInputStream s) throws IOException, ClassNotFoundException
      Reconstitute the SortedArrayStringMap instance from a stream (i.e., deserialize it).
      Throws:
      IOException
      ClassNotFoundException
    • handleSerializationException

      private void handleSerializationException(Throwable t, int i, String key)