Package com.google.protobuf
Class SmallSortedMap<K extends java.lang.Comparable<K>,V>
- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- com.google.protobuf.SmallSortedMap<K,V>
-
- All Implemented Interfaces:
java.util.Map<K,V>
class SmallSortedMap<K extends java.lang.Comparable<K>,V> extends java.util.AbstractMap<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 firstk
mappings in an array for a configurable value ofk
, allowing direct access to the correspondingEntry
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:
The resulting iteration is in order of ascending field tag number. The object returned byfor (int i = 0; i < fieldMap.getNumArrayEntries(); i++) { process(fieldMap.getArrayEntryAt(i)); } for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) { process(entry); }
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 isO(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 anUnsupportedOperationException
.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
SmallSortedMap.DescendingEntryIterator
Reverse Iterator implementation that switches from the entry array to the overflow entries appropriately.private class
SmallSortedMap.DescendingEntrySet
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.
-
Field Summary
Fields Modifier and Type Field Description (package private) static int
DEFAULT_FIELD_MAP_ARRAY_SIZE
private java.lang.Object[]
entries
private int
entriesSize
private boolean
isImmutable
private SmallSortedMap.EntrySet
lazyEntrySet
private java.util.Map<K,V>
overflowEntries
private java.util.Map<K,V>
overflowEntriesDescending
-
Constructor Summary
Constructors Modifier Constructor Description private
SmallSortedMap()
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private int
binarySearchInArray(K key)
private void
checkMutable()
void
clear()
boolean
containsKey(java.lang.Object o)
The implementation throws aClassCastException
if o is not an object of typeK
.(package private) java.util.Set<java.util.Map.Entry<K,V>>
descendingEntrySet()
private void
ensureEntryArrayMutable()
Lazily creates the entry array.java.util.Set<java.util.Map.Entry<K,V>>
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
equals(java.lang.Object o)
V
get(java.lang.Object o)
The implementation throws aClassCastException
if o is not an object of typeK
.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 <FieldDescriptorT extends FieldSet.FieldDescriptorLite<FieldDescriptorT>>
SmallSortedMap<FieldDescriptorT,java.lang.Object>newFieldMap()
Creates a new instance for mapping FieldDescriptors to their values.(package private) static <K extends java.lang.Comparable<K>,V>
SmallSortedMap<K,V>newInstanceForTest()
Creates a new instance for testing.V
put(K key, V value)
V
remove(java.lang.Object o)
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
-
-
-
-
Field Detail
-
DEFAULT_FIELD_MAP_ARRAY_SIZE
static final int DEFAULT_FIELD_MAP_ARRAY_SIZE
- See Also:
- Constant Field Values
-
entries
private java.lang.Object[] entries
-
entriesSize
private int entriesSize
-
isImmutable
private boolean isImmutable
-
lazyEntrySet
private volatile SmallSortedMap.EntrySet lazyEntrySet
-
-
Method Detail
-
newFieldMap
static <FieldDescriptorT extends FieldSet.FieldDescriptorLite<FieldDescriptorT>> SmallSortedMap<FieldDescriptorT,java.lang.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
static <K extends java.lang.Comparable<K>,V> SmallSortedMap<K,V> 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
public java.util.Map.Entry<K,V> getArrayEntryAt(int index)
- Returns:
- The array entry at the given
index
.
-
getNumOverflowEntries
public int getNumOverflowEntries()
- Returns:
- There number of overflow entries.
-
getOverflowEntries
public java.lang.Iterable<java.util.Map.Entry<K,V>> getOverflowEntries()
- Returns:
- An iterable over the overflow entries.
-
size
public int size()
-
containsKey
public boolean containsKey(java.lang.Object o)
The implementation throws aClassCastException
if o is not an object of typeK
.
-
get
public V get(java.lang.Object o)
The implementation throws aClassCastException
if o is not an object of typeK
.
-
clear
public void clear()
-
remove
public V remove(java.lang.Object o)
The implementation throws aClassCastException
if o is not an object of typeK
.
-
removeArrayEntryAt
private V removeArrayEntryAt(int index)
-
binarySearchInArray
private int binarySearchInArray(K key)
- Parameters:
key
- The key to find in the entry array.- Returns:
- The returned integer position follows the same semantics as the value returned by
java.util.Arrays#binarySearch()
.
-
entrySet
public java.util.Set<java.util.Map.Entry<K,V>> 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.
-
checkMutable
private void checkMutable()
- Throws:
java.lang.UnsupportedOperationException
- ifmakeImmutable()
has has been called.
-
getOverflowEntriesMutable
private java.util.SortedMap<K,V> getOverflowEntriesMutable()
- Returns:
- a
SortedMap
to which overflow entries mappings can be added or removed. - Throws:
java.lang.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
public boolean equals(java.lang.Object o)
-
-