Package com.google.protobuf
Class SmallSortedMap<K extends Comparable<K>,V>
java.lang.Object
java.util.AbstractMap<K,V>
com.google.protobuf.SmallSortedMap<K,V>
- All Implemented Interfaces:
Map<K,
V>
A custom map implementation from FieldDescriptor to Object optimized to minimize the number of
memory allocations for instances with a small number of mappings. The implementation stores the
first
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
.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
Reverse Iterator implementation that switches from the entry array to the overflow entries appropriately.private class
private class
Entry implementation that implements Comparable in order to support binary search within the entry array.private class
Iterator implementation that switches from the entry array to the overflow entries appropriately.private class
Stateless view of the entries in the field map.Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,
V>, AbstractMap.SimpleImmutableEntry<K, V> -
Field Summary
FieldsModifier and TypeFieldDescription(package private) static final int
private Object[]
private int
private boolean
private SmallSortedMap<K,
V>.EntrySet -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate int
binarySearchInArray
(K key) private void
void
clear()
boolean
The implementation throws aClassCastException
if o is not an object of typeK
.private void
Lazily creates the entry array.entrySet()
Similar to the AbstractMap implementation ofkeySet()
andvalues()
, the entry set is created the first time this method is called, and returned in response to all subsequent calls.boolean
The implementation throws aClassCastException
if o is not an object of typeK
.getArrayEntryAt
(int index) int
int
int
hashCode()
boolean
void
Make this map immutable from this point forward.(package private) static <FieldDescriptorT extends FieldSet.FieldDescriptorLite<FieldDescriptorT>>
SmallSortedMap<FieldDescriptorT, Object> Creates a new instance for mapping FieldDescriptors to their values.(package private) static <K extends Comparable<K>,
V>
SmallSortedMap<K, V> Creates a new instance for testing.The implementation throws aClassCastException
if o is not an object of typeK
.private V
removeArrayEntryAt
(int index) int
size()
Methods inherited from class java.util.AbstractMap
clone, containsValue, isEmpty, keySet, putAll, toString, values
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll
-
Field Details
-
DEFAULT_FIELD_MAP_ARRAY_SIZE
static final int DEFAULT_FIELD_MAP_ARRAY_SIZE- See Also:
-
entries
-
entriesSize
private int entriesSize -
overflowEntries
-
isImmutable
private boolean isImmutable -
lazyEntrySet
-
overflowEntriesDescending
-
-
Constructor Details
-
SmallSortedMap
private SmallSortedMap()
-
-
Method Details
-
newFieldMap
static <FieldDescriptorT extends FieldSet.FieldDescriptorLite<FieldDescriptorT>> SmallSortedMap<FieldDescriptorT,Object> newFieldMap()Creates a new instance for mapping FieldDescriptors to their values. ThemakeImmutable()
implementation will convert the List values of any repeated fields to unmodifiable lists. -
newInstanceForTest
Creates a new instance for testing. -
makeImmutable
public void makeImmutable()Make this map immutable from this point forward. -
isImmutable
public boolean isImmutable()- Returns:
- Whether
makeImmutable()
has been called.
-
getNumArrayEntries
public int getNumArrayEntries()- Returns:
- The number of entries in the entry array.
-
getArrayEntryAt
- Returns:
- The array entry at the given
index
.
-
getNumOverflowEntries
public int getNumOverflowEntries()- Returns:
- There number of overflow entries.
-
getOverflowEntries
- Returns:
- An iterable over the overflow entries.
-
size
public int size()- Specified by:
size
in interfaceMap<K extends Comparable<K>,
V> - Overrides:
size
in classAbstractMap<K extends Comparable<K>,
V>
-
containsKey
The implementation throws aClassCastException
if o is not an object of typeK
.- Specified by:
containsKey
in interfaceMap<K extends Comparable<K>,
V> - Overrides:
containsKey
in classAbstractMap<K extends Comparable<K>,
V>
-
get
The implementation throws aClassCastException
if o is not an object of typeK
.- Specified by:
get
in interfaceMap<K extends Comparable<K>,
V> - Overrides:
get
in classAbstractMap<K extends Comparable<K>,
V>
-
put
- Specified by:
put
in interfaceMap<K extends Comparable<K>,
V> - Overrides:
put
in classAbstractMap<K extends Comparable<K>,
V>
-
clear
public void clear()- Specified by:
clear
in interfaceMap<K extends Comparable<K>,
V> - Overrides:
clear
in classAbstractMap<K extends Comparable<K>,
V>
-
remove
The implementation throws aClassCastException
if o is not an object of typeK
.- Specified by:
remove
in interfaceMap<K extends Comparable<K>,
V> - Overrides:
remove
in classAbstractMap<K extends Comparable<K>,
V>
-
removeArrayEntryAt
-
binarySearchInArray
- Parameters:
key
- The key to find in the entry array.- Returns:
- The returned integer position follows the same semantics as the value returned by
invalid reference
java.util.Arrays#binarySearch()
-
entrySet
Similar to the AbstractMap implementation ofkeySet()
andvalues()
, the entry set is created the first time this method is called, and returned in response to all subsequent calls.- Specified by:
entrySet
in interfaceMap<K extends Comparable<K>,
V> - Specified by:
entrySet
in classAbstractMap<K extends Comparable<K>,
V>
-
descendingEntrySet
-
checkMutable
private void checkMutable()- Throws:
UnsupportedOperationException
- ifmakeImmutable()
has has been called.
-
getOverflowEntriesMutable
- Returns:
- a
SortedMap
to which overflow entries mappings can be added or removed. - Throws:
UnsupportedOperationException
- ifmakeImmutable()
has been called.
-
ensureEntryArrayMutable
private void ensureEntryArrayMutable()Lazily creates the entry array. Any code that adds to the array must first call this method. -
equals
- Specified by:
equals
in interfaceMap<K extends Comparable<K>,
V> - Overrides:
equals
in classAbstractMap<K extends Comparable<K>,
V>
-
hashCode
public int hashCode()- Specified by:
hashCode
in interfaceMap<K extends Comparable<K>,
V> - Overrides:
hashCode
in classAbstractMap<K extends Comparable<K>,
V>
-