Class SortedArrayStringMap
- java.lang.Object
-
- org.apache.logging.log4j.util.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 theReadOnlyStringMap
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
andTriConsumer
. - 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
andcontainsKey
is O(log N), worst-case performance ofput
andremove
is O(N log N). The expectation is that for the small values ofN
(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
-
-
Field Summary
Fields Modifier and Type Field Description private static int
DEFAULT_INITIAL_CAPACITY
The default initial capacity.private static java.lang.String[]
EMPTY
An empty array instance to share when the table is not inflated.private static java.lang.String
FROZEN
private static java.lang.reflect.Method
getObjectInputFilter
private static int
HASHVAL
private boolean
immutable
private boolean
iterating
private java.lang.String[]
keys
private static java.lang.reflect.Method
newObjectInputFilter
private static TriConsumer<java.lang.String,java.lang.Object,StringMap>
PUT_ALL
private static long
serialVersionUID
private static java.lang.reflect.Method
setObjectInputFilter
private int
size
The number of key-value mappings contained in this map.private int
threshold
The next size value at which to resize (capacity * load factor).private java.lang.Object[]
values
-
Constructor Summary
Constructors Constructor Description SortedArrayStringMap()
SortedArrayStringMap(int initialCapacity)
SortedArrayStringMap(java.util.Map<java.lang.String,?> map)
SortedArrayStringMap(ReadOnlyStringMap other)
-
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)
Returnstrue
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>
voidforEach(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, ornull
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, ornull
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, ornull
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()
Returnstrue
if this collection is empty (size is zero),false
otherwise.boolean
isFrozen()
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 specifiedReadOnlyStringMap
into thisStringMap
.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 theSortedArrayStringMap
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
mutableMap<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 theSortedArrayStringMap
instance to a stream (i.e., serialize it).
-
-
-
Field Detail
-
DEFAULT_INITIAL_CAPACITY
private static final int DEFAULT_INITIAL_CAPACITY
The default initial capacity.- See Also:
- Constant Field Values
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
HASHVAL
private static final int HASHVAL
- 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.
-
FROZEN
private static final java.lang.String FROZEN
- See Also:
- Constant Field Values
-
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(ReadOnlyStringMap other)
-
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.
-
containsKey
public boolean containsKey(java.lang.String key)
Description copied from interface:ReadOnlyStringMap
Returnstrue
if this data structure contains the specified key,false
otherwise.- Specified by:
containsKey
in interfaceReadOnlyStringMap
- Parameters:
key
- the key whose presence to check. May benull
.- 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
mutableMap<String, String>
containing a snapshot of this data structure.- Specified by:
toMap
in interfaceReadOnlyStringMap
- 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 thefreeze()
method was called will result in anUnsupportedOperationException
being thrown.
-
isFrozen
public boolean isFrozen()
Description copied from interface:StringMap
-
getValue
public <V> V getValue(java.lang.String key)
Description copied from interface:ReadOnlyStringMap
Returns the value for the specified key, ornull
if the specified key does not exist in this collection.- Specified by:
getValue
in interfaceReadOnlyStringMap
- 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
Returnstrue
if this collection is empty (size is zero),false
otherwise.- Specified by:
isEmpty
in interfaceReadOnlyStringMap
- 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 interfaceIndexedReadOnlyStringMap
- 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, orsize()
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.
-
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 specifiedReadOnlyStringMap
into thisStringMap
.
-
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(java.lang.String key)
Description copied from interface:StringMap
Removes the key-value pair for the specified key from this data structure.
-
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, ornull
if the specified index is less than zero or greater or equal to the size of this collection.- Specified by:
getKeyAt
in interfaceIndexedReadOnlyStringMap
- 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, ornull
if the specified index is less than zero or greater or equal to the size of this collection.- Specified by:
getValueAt
in interfaceIndexedReadOnlyStringMap
- 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 interfaceReadOnlyStringMap
- 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
'sBiConsumer.accept(Object, Object)
accept} method may cause aConcurrentModificationException
to be thrown.- Specified by:
forEach
in interfaceReadOnlyStringMap
- 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
'saccept
method may cause aConcurrentModificationException
to be thrown.- Specified by:
forEach
in interfaceReadOnlyStringMap
- 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 interfaceStringMap
- Overrides:
equals
in classjava.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.
-
hashCode
private static int hashCode(java.lang.Object[] values, int length)
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
writeObject
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
Save the state of theSortedArrayStringMap
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 theSortedArrayStringMap
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)
-
-