class SmallSortedMap<K extends java.lang.Comparable<K>,V>
extends java.util.AbstractMap<K,V>
k
mappings in an
array for a configurable value of k
, allowing direct access to the
corresponding Entry
s without the need to create an Iterator. The
remaining entries are stored in an overflow map. Iteration over the entries
in the map should be done as follows:
for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) {
process(fieldMap.getArrayEntryAt(i));
}
for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) {
process(entry);
}
The resulting iteration is in order of ascending field tag number. The
object returned by entrySet()
adheres to the same contract but is
less efficient as it necessarily involves creating an object for iteration.
The tradeoff for this memory efficiency is that the worst case running time
of the put()
operation is O(k + lg n)
, which happens when
entries are added in descending order. k
should be chosen such that
it covers enough common cases without adversely affecting larger maps. In
practice, the worst case scenario does not happen for extensions because
extension fields are serialized and deserialized in order of ascending tag
number, but the worst case scenario can happen for DynamicMessages.
The running time for all other operations is similar to that of
TreeMap
.
Instances are not thread-safe until makeImmutable()
is called,
after which any modifying operation will result in an
UnsupportedOperationException
.
Modifier and Type | Class and Description |
---|---|
private static class |
SmallSortedMap.EmptySet
Helper class that holds immutable instances of an Iterable/Iterator that
we return when the overflow entries is empty.
|
private class |
SmallSortedMap.Entry
Entry implementation that implements Comparable in order to support
binary search within the entry array.
|
private class |
SmallSortedMap.EntryIterator
Iterator implementation that switches from the entry array to the overflow
entries appropriately.
|
private class |
SmallSortedMap.EntrySet
Stateless view of the entries in the field map.
|
Modifier and Type | Field and Description |
---|---|
private java.util.List<SmallSortedMap.Entry> |
entryList |
private boolean |
isImmutable |
private SmallSortedMap.EntrySet |
lazyEntrySet |
private int |
maxArraySize |
private java.util.Map<K,V> |
overflowEntries |
Modifier | Constructor and Description |
---|---|
private |
SmallSortedMap(int arraySize) |
Modifier and Type | Method and Description |
---|---|
private int |
binarySearchInArray(K key) |
private void |
checkMutable() |
void |
clear() |
boolean |
containsKey(java.lang.Object o)
The implementation throws a
ClassCastException if o is not an
object of type K . |
private void |
ensureEntryArrayMutable()
Lazily creates the entry list.
|
java.util.Set<java.util.Map.Entry<K,V>> |
entrySet()
Similar to the AbstractMap implementation of
keySet() and
values() , the entry set is created the first time this method is
called, and returned in response to all subsequent calls. |
boolean |
equals(java.lang.Object o) |
V |
get(java.lang.Object o)
The implementation throws a
ClassCastException if o is not an
object of type K . |
java.util.Map.Entry<K,V> |
getArrayEntryAt(int index) |
int |
getNumArrayEntries() |
int |
getNumOverflowEntries() |
java.lang.Iterable<java.util.Map.Entry<K,V>> |
getOverflowEntries() |
private java.util.SortedMap<K,V> |
getOverflowEntriesMutable() |
int |
hashCode() |
boolean |
isImmutable() |
void |
makeImmutable()
Make this map immutable from this point forward.
|
(package private) static <FieldDescriptorType extends FieldSet.FieldDescriptorLite<FieldDescriptorType>> |
newFieldMap(int arraySize)
Creates a new instance for mapping FieldDescriptors to their values.
|
(package private) static <K extends java.lang.Comparable<K>,V> |
newInstanceForTest(int arraySize)
Creates a new instance for testing.
|
V |
put(K key,
V value) |
V |
remove(java.lang.Object o)
The implementation throws a
ClassCastException if o is not an
object of type K . |
private V |
removeArrayEntryAt(int index) |
int |
size() |
clone, containsValue, isEmpty, keySet, putAll, toString, values
private final int maxArraySize
private java.util.List<SmallSortedMap.Entry> entryList
private boolean isImmutable
private volatile SmallSortedMap.EntrySet lazyEntrySet
static <FieldDescriptorType extends FieldSet.FieldDescriptorLite<FieldDescriptorType>> SmallSortedMap<FieldDescriptorType,java.lang.Object> newFieldMap(int arraySize)
makeImmutable()
implementation will convert the List values
of any repeated fields to unmodifiable lists.arraySize
- The size of the entry array containing the
lexicographically smallest mappings.static <K extends java.lang.Comparable<K>,V> SmallSortedMap<K,V> newInstanceForTest(int arraySize)
arraySize
- The size of the entry array containing the
lexicographically smallest mappings.public void makeImmutable()
public boolean isImmutable()
makeImmutable()
has been called.public int getNumArrayEntries()
public java.util.Map.Entry<K,V> getArrayEntryAt(int index)
index
.public int getNumOverflowEntries()
public java.lang.Iterable<java.util.Map.Entry<K,V>> getOverflowEntries()
public int size()
public boolean containsKey(java.lang.Object o)
ClassCastException
if o is not an
object of type K
.
public V get(java.lang.Object o)
ClassCastException
if o is not an
object of type K
.
public void clear()
public V remove(java.lang.Object o)
ClassCastException
if o is not an
object of type K
.
private V removeArrayEntryAt(int index)
private int binarySearchInArray(K key)
key
- The key to find in the entry array.java.util.Arrays#binarySearch()
.public java.util.Set<java.util.Map.Entry<K,V>> entrySet()
keySet()
and
values()
, the entry set is created the first time this method is
called, and returned in response to all subsequent calls.
private void checkMutable()
java.lang.UnsupportedOperationException
- if makeImmutable()
has
has been called.private java.util.SortedMap<K,V> getOverflowEntriesMutable()
SortedMap
to which overflow entries mappings can be
added or removed.java.lang.UnsupportedOperationException
- if makeImmutable()
has been
called.private void ensureEntryArrayMutable()
public boolean equals(java.lang.Object o)