Class UnmodifiableArrayBackedMap

java.lang.Object
java.util.AbstractMap<String,String>
org.apache.logging.log4j.internal.map.UnmodifiableArrayBackedMap
All Implemented Interfaces:
Serializable, Map<String,String>, ReadOnlyStringMap
public class UnmodifiableArrayBackedMap extends AbstractMap<String,String> implements ReadOnlyStringMap
This class represents an immutable map, which stores its state inside a single Object[]:
  1. [0] contains the number of entries
  2. Others contain alternating key-value pairs, for example [1]="1" and [2]="value_for_1"
Keys are calculated using (index * 2 + 1) and values are (index * 2 + 2). Performance:
  • Implements very low-cost copies: shallow-copy the array.
  • Doesn't matter for mutable operations, since we don't allow them.
  • Iterates very quickly, since it iterates directly across the array. This contrasts with HashMap's requirement to scan each bucket in the table and chase each pointer.
  • Is linear on gets, puts, and removes, since the table must be scanned to find a matching key.
Allocation:
  • Zero on reads.
  • Copy-and-modify operations allocate exactly two objects: the new array and the new Map instance. This is substantially better than HashMap, which requires a new Node for each entry.
See Also:

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:

    • EMPTY_MAP

      public static final UnmodifiableArrayBackedMap EMPTY_MAP

    • NUM_FIXED_ARRAY_ENTRIES

      private static final int NUM_FIXED_ARRAY_ENTRIES
      See Also:

    • backingArray

      private Object[] backingArray
      backingArray is functionally final, but marking it as such can cause performance problems. Consider marking it final after https://bugs.openjdk.org/browse/JDK-8324186 is solved.

    • numEntries

      private int numEntries

  • Constructor Details

    • UnmodifiableArrayBackedMap

      private UnmodifiableArrayBackedMap(int capacity)

    • UnmodifiableArrayBackedMap

      private UnmodifiableArrayBackedMap(Object[] backingArray)

    • UnmodifiableArrayBackedMap

      UnmodifiableArrayBackedMap(UnmodifiableArrayBackedMap other)

  • Method Details

    • getArrayIndexForKey

      private static int getArrayIndexForKey(int entryIndex)

    • getArrayIndexForValue

      private static int getArrayIndexForValue(int entryIndex)

    • getMap

      public static UnmodifiableArrayBackedMap getMap(Object[] backingArray)

    • add

      private void add(String key, String value)

    • clear

      public void clear()
      Specified by:
      clear in interface Map<String,String>
      Overrides:
      clear in class AbstractMap<String,String>

    • containsKey

      public boolean containsKey(Object key)
      Scans the array to find a matching key. Linear performance.
      Specified by:
      containsKey in interface Map<String,String>
      Overrides:
      containsKey in class AbstractMap<String,String>

    • 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.

    • getBackingArray

      public Object[] getBackingArray()

    • containsValue

      public boolean containsValue(Object value)
      Scans the array to find a matching value, with linear time. Allows null parameter.
      Specified by:
      containsValue in interface Map<String,String>
      Overrides:
      containsValue in class AbstractMap<String,String>

    • copyAndPut

      public UnmodifiableArrayBackedMap copyAndPut(String key, String value)
      Creates a new instance that contains the same entries as this map, plus either the new entry or updated value passed in the parameters.
      Parameters:
      key -
      value -
      Returns:

    • copyAndPutAll

      public UnmodifiableArrayBackedMap copyAndPutAll(Map<String,String> entriesToAdd)
      Creates a new instance that contains the same entries as this map, plus the new entries or updated values passed in the parameters.

    • copyAndRemove

      public UnmodifiableArrayBackedMap copyAndRemove(String key)
      Creates a new instance that contains the same entries as this map, minus the entry with the specified key (if such an entry exists).

    • copyAndRemoveAll

      public UnmodifiableArrayBackedMap copyAndRemoveAll(Iterable<String> keysToRemoveIterable)
      Creates a new instance where the entries of provided keys are removed.

    • updateNumEntriesInArray

      private void updateNumEntriesInArray()
      Copies the locally-tracked numEntries into the first array slot. Requires autoboxing so call should be minimized - for example, once per bulk update operation.

    • forEach

      public void forEach(BiConsumer<? super String, ? super String> action)
      This version of forEach is defined on the Map interface.
      Specified by:
      forEach in interface Map<String,String>

    • forEach

      public <V> void forEach(BiConsumer<String, ? super V> action)
      This version of forEach is defined on the ReadOnlyStringMap interface.
      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,S> void forEach(TriConsumer<String, ? super V, S> action, S 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.
      S - 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.

    • entrySet

      public Set<Map.Entry<String,String>> entrySet()
      Specified by:
      entrySet in interface Map<String,String>
      Specified by:
      entrySet in class AbstractMap<String,String>

    • get

      public String get(Object key)
      Scans the array to find a matching key. Linear-time.
      Specified by:
      get in interface Map<String,String>
      Overrides:
      get in class AbstractMap<String,String>

    • 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.

    • addOrOverwriteKey

      private void addOrOverwriteKey(String key, String value)
      Find an existing entry (if any) and overwrites the value, if found
      Parameters:
      key -
      value -

    • put

      public String put(String key, String value)
      Specified by:
      put in interface Map<String,String>
      Overrides:
      put in class AbstractMap<String,String>

    • putAll

      public void putAll(Map<? extends String, ? extends String> m)
      Specified by:
      putAll in interface Map<String,String>
      Overrides:
      putAll in class AbstractMap<String,String>

    • remove

      public String remove(Object key)
      Specified by:
      remove in interface Map<String,String>
      Overrides:
      remove in class AbstractMap<String,String>

    • size

      public int size()
      Description copied from interface: ReadOnlyStringMap
      Returns the number of key-value pairs in this collection.
      Specified by:
      size in interface Map<String,String>
      Specified by:
      size in interface ReadOnlyStringMap
      Overrides:
      size in class AbstractMap<String,String>
      Returns:
      the number of key-value pairs in this collection.

    • 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.