public class SortedArrayStringMap extends java.lang.Object implements IndexedStringMap
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:
BiConsumer
and TriConsumer
.SortedArrayStringMap
, the full thread context
data can be transferred with two array copies and two field updates.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.
Modifier and Type | Field and 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 and Description |
---|
SortedArrayStringMap() |
SortedArrayStringMap(int initialCapacity) |
SortedArrayStringMap(java.util.Map<java.lang.String,?> map) |
SortedArrayStringMap(ReadOnlyStringMap other) |
Modifier and Type | Method and 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()
|
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). |
private static final int DEFAULT_INITIAL_CAPACITY
private static final long serialVersionUID
private static final int HASHVAL
private static final TriConsumer<java.lang.String,java.lang.Object,StringMap> PUT_ALL
private static final java.lang.String[] EMPTY
private static final java.lang.String FROZEN
private transient java.lang.String[] keys
private transient java.lang.Object[] values
private transient int size
private static final java.lang.reflect.Method setObjectInputFilter
private static final java.lang.reflect.Method getObjectInputFilter
private static final java.lang.reflect.Method newObjectInputFilter
private int threshold
private boolean immutable
private transient boolean iterating
public SortedArrayStringMap()
public SortedArrayStringMap(int initialCapacity)
public SortedArrayStringMap(ReadOnlyStringMap other)
public SortedArrayStringMap(java.util.Map<java.lang.String,?> map)
private void assertNotFrozen()
private void assertNoConcurrentModification()
public void clear()
StringMap
public boolean containsKey(java.lang.String key)
ReadOnlyStringMap
true
if this data structure contains the specified key, false
otherwise.containsKey
in interface ReadOnlyStringMap
key
- the key whose presence to check. May be null
.true
if this data structure contains the specified key, false
otherwise.public java.util.Map<java.lang.String,java.lang.String> toMap()
ReadOnlyStringMap
null
mutable Map<String, String>
containing a snapshot of this data structure.toMap
in interface ReadOnlyStringMap
Map<String, String>
form.public void freeze()
StringMap
freeze()
method was called
will result in an UnsupportedOperationException
being thrown.public boolean isFrozen()
StringMap
public <V> V getValue(java.lang.String key)
ReadOnlyStringMap
null
if the specified key does not exist in this collection.getValue
in interface ReadOnlyStringMap
key
- the key whose value to return.null
.public boolean isEmpty()
ReadOnlyStringMap
true
if this collection is empty (size is zero), false
otherwise.isEmpty
in interface ReadOnlyStringMap
true
if this collection is empty (size is zero).public int indexOfKey(java.lang.String key)
IndexedReadOnlyStringMap
(-(insertion point) - 1)
.indexOfKey
in interface IndexedReadOnlyStringMap
key
- the key whose index in the ordered sequence of keys to return(-(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.private int nullKeyIndex()
public void putValue(java.lang.String key, java.lang.Object value)
StringMap
private void insertAt(int index, java.lang.String key, java.lang.Object value)
public void putAll(ReadOnlyStringMap source)
StringMap
ReadOnlyStringMap
into this StringMap
.private void initFrom0(SortedArrayStringMap other)
private void merge(SortedArrayStringMap other)
private void ensureCapacity()
private void resize(int newCapacity)
private void inflateTable(int toSize)
public void remove(java.lang.String key)
StringMap
public java.lang.String getKeyAt(int index)
IndexedReadOnlyStringMap
null
if the specified index is less than zero or greater or equal to the size of this collection.getKeyAt
in interface IndexedReadOnlyStringMap
index
- the index of the key to returnnull
public <V> V getValueAt(int index)
IndexedReadOnlyStringMap
null
if the specified index is less than zero or greater or equal to the size of this collection.getValueAt
in interface IndexedReadOnlyStringMap
index
- the index of the value to returnnull
public int size()
ReadOnlyStringMap
size
in interface ReadOnlyStringMap
public <V> void forEach(BiConsumer<java.lang.String,? super V> action)
ReadOnlyStringMap
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.
forEach
in interface ReadOnlyStringMap
V
- type of the value.action
- The action to be performed for each key-value pair in this collection.public <V,T> void forEach(TriConsumer<java.lang.String,? super V,T> action, T state)
ReadOnlyStringMap
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.
forEach
in interface ReadOnlyStringMap
V
- type of the value.T
- type of the third parameter.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.public boolean equals(java.lang.Object obj)
StringMap
equals
in interface StringMap
equals
in class java.lang.Object
obj
- the reference object with which to compare.true
if this object is the same as the obj argument; false
otherwise.StringMap.hashCode()
public int hashCode()
StringMap
private static int hashCode(java.lang.Object[] values, int length)
public java.lang.String toString()
toString
in class java.lang.Object
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
SortedArrayStringMap
instance to a stream (i.e.,
serialize it).java.io.IOException
private static byte[] marshall(java.lang.Object obj) throws java.io.IOException
java.io.IOException
private static java.lang.Object unmarshall(byte[] data, java.io.ObjectInputStream inputStream) throws java.io.IOException, java.lang.ClassNotFoundException
java.io.IOException
java.lang.ClassNotFoundException
private static int ceilingNextPowerOfTwo(int x)
From Hacker's Delight, Chapter 3, Harry S. Warren Jr.
x
- Value to round upprivate void readObject(java.io.ObjectInputStream s) throws java.io.IOException, java.lang.ClassNotFoundException
SortedArrayStringMap
instance from a stream (i.e.,
deserialize it).java.io.IOException
java.lang.ClassNotFoundException
private void handleSerializationException(java.lang.Throwable t, int i, java.lang.String key)