1
// Protocol Buffers - Google's data interchange format
2
// Copyright 2008 Google Inc. All rights reserved.
3
// http://code.google.com/p/protobuf/
5
// Redistribution and use in source and binary forms, with or without
6
// modification, are permitted provided that the following conditions are
9
// * Redistributions of source code must retain the above copyright
10
// notice, this list of conditions and the following disclaimer.
11
// * Redistributions in binary form must reproduce the above
12
// copyright notice, this list of conditions and the following disclaimer
13
// in the documentation and/or other materials provided with the
15
// * Neither the name of Google Inc. nor the names of its
16
// contributors may be used to endorse or promote products derived from
17
// this software without specific prior written permission.
19
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31
package com.google.protobuf;
33
import java.util.AbstractMap;
34
import java.util.AbstractSet;
35
import java.util.ArrayList;
36
import java.util.Collections;
37
import java.util.Iterator;
38
import java.util.TreeMap;
39
import java.util.List;
41
import java.util.NoSuchElementException;
43
import java.util.SortedMap;
46
* A custom map implementation from FieldDescriptor to Object optimized to
47
* minimize the number of memory allocations for instances with a small number
48
* of mappings. The implementation stores the first {@code k} mappings in an
49
* array for a configurable value of {@code k}, allowing direct access to the
50
* corresponding {@code Entry}s without the need to create an Iterator. The
51
* remaining entries are stored in an overflow map. Iteration over the entries
52
* in the map should be done as follows:
55
* for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) {
56
* process(fieldMap.getArrayEntryAt(i));
58
* for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) {
63
* The resulting iteration is in order of ascending field tag number. The
64
* object returned by {@link #entrySet()} adheres to the same contract but is
65
* less efficient as it necessarily involves creating an object for iteration.
67
* The tradeoff for this memory efficiency is that the worst case running time
68
* of the {@code put()} operation is {@code O(k + lg n)}, which happens when
69
* entries are added in descending order. {@code k} should be chosen such that
70
* it covers enough common cases without adversely affecting larger maps. In
71
* practice, the worst case scenario does not happen for extensions because
72
* extension fields are serialized and deserialized in order of ascending tag
73
* number, but the worst case scenario can happen for DynamicMessages.
75
* The running time for all other operations is similar to that of
78
* Instances are not thread-safe until {@link #makeImmutable()} is called,
79
* after which any modifying operation will result in an
80
* {@link UnsupportedOperationException}.
82
* @author darick@google.com Darick Tong
84
// This class is final for all intents and purposes because the constructor is
85
// private. However, the FieldDescriptor-specific logic is encapsulated in
86
// a subclass to aid testability of the core logic.
87
class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> {
90
* Creates a new instance for mapping FieldDescriptors to their values.
91
* The {@link #makeImmutable()} implementation will convert the List values
92
* of any repeated fields to unmodifiable lists.
94
* @param arraySize The size of the entry array containing the
95
* lexicographically smallest mappings.
97
static <FieldDescriptorType extends
98
FieldSet.FieldDescriptorLite<FieldDescriptorType>>
99
SmallSortedMap<FieldDescriptorType, Object> newFieldMap(int arraySize) {
100
return new SmallSortedMap<FieldDescriptorType, Object>(arraySize) {
102
@SuppressWarnings("unchecked")
103
public void makeImmutable() {
104
if (!isImmutable()) {
105
for (int i = 0; i < getNumArrayEntries(); i++) {
106
final Map.Entry<FieldDescriptorType, Object> entry =
108
if (entry.getKey().isRepeated()) {
109
final List value = (List) entry.getValue();
110
entry.setValue(Collections.unmodifiableList(value));
113
for (Map.Entry<FieldDescriptorType, Object> entry :
114
getOverflowEntries()) {
115
if (entry.getKey().isRepeated()) {
116
final List value = (List) entry.getValue();
117
entry.setValue(Collections.unmodifiableList(value));
121
super.makeImmutable();
127
* Creates a new instance for testing.
129
* @param arraySize The size of the entry array containing the
130
* lexicographically smallest mappings.
132
static <K extends Comparable<K>, V> SmallSortedMap<K, V> newInstanceForTest(
134
return new SmallSortedMap<K, V>(arraySize);
137
private final int maxArraySize;
138
// The "entry array" is actually a List because generic arrays are not
139
// allowed. ArrayList also nicely handles the entry shifting on inserts and
141
private List<Entry> entryList;
142
private Map<K, V> overflowEntries;
143
private boolean isImmutable;
144
// The EntrySet is a stateless view of the Map. It's initialized the first
145
// time it is requested and reused henceforth.
146
private volatile EntrySet lazyEntrySet;
149
* @code arraySize Size of the array in which the lexicographically smallest
150
* mappings are stored. (i.e. the {@code k} referred to in the class
153
private SmallSortedMap(int arraySize) {
154
this.maxArraySize = arraySize;
155
this.entryList = Collections.emptyList();
156
this.overflowEntries = Collections.emptyMap();
159
/** Make this map immutable from this point forward. */
160
public void makeImmutable() {
162
// Note: There's no need to wrap the entryList in an unmodifiableList
163
// because none of the list's accessors are exposed. The iterator() of
164
// overflowEntries, on the other hand, is exposed so it must be made
166
overflowEntries = overflowEntries.isEmpty() ?
167
Collections.<K, V>emptyMap() :
168
Collections.unmodifiableMap(overflowEntries);
173
/** @return Whether {@link #makeImmutable()} has been called. */
174
public boolean isImmutable() {
178
/** @return The number of entries in the entry array. */
179
public int getNumArrayEntries() {
180
return entryList.size();
183
/** @return The array entry at the given {@code index}. */
184
public Map.Entry<K, V> getArrayEntryAt(int index) {
185
return entryList.get(index);
188
/** @return There number of overflow entries. */
189
public int getNumOverflowEntries() {
190
return overflowEntries.size();
193
/** @return An iterable over the overflow entries. */
194
public Iterable<Map.Entry<K, V>> getOverflowEntries() {
195
return overflowEntries.isEmpty() ?
196
EmptySet.<Map.Entry<K, V>>iterable() :
197
overflowEntries.entrySet();
202
return entryList.size() + overflowEntries.size();
206
* The implementation throws a {@code ClassCastException} if o is not an
207
* object of type {@code K}.
212
public boolean containsKey(Object o) {
213
@SuppressWarnings("unchecked")
215
return binarySearchInArray(key) >= 0 || overflowEntries.containsKey(key);
219
* The implementation throws a {@code ClassCastException} if o is not an
220
* object of type {@code K}.
225
public V get(Object o) {
226
@SuppressWarnings("unchecked")
228
final int index = binarySearchInArray(key);
230
return entryList.get(index).getValue();
232
return overflowEntries.get(key);
236
public V put(K key, V value) {
238
final int index = binarySearchInArray(key);
240
// Replace existing array entry.
241
return entryList.get(index).setValue(value);
243
ensureEntryArrayMutable();
244
final int insertionPoint = -(index + 1);
245
if (insertionPoint >= maxArraySize) {
246
// Put directly in overflow.
247
return getOverflowEntriesMutable().put(key, value);
249
// Insert new Entry in array.
250
if (entryList.size() == maxArraySize) {
251
// Shift the last array entry into overflow.
252
final Entry lastEntryInArray = entryList.remove(maxArraySize - 1);
253
getOverflowEntriesMutable().put(lastEntryInArray.getKey(),
254
lastEntryInArray.getValue());
256
entryList.add(insertionPoint, new Entry(key, value));
261
public void clear() {
263
if (!entryList.isEmpty()) {
266
if (!overflowEntries.isEmpty()) {
267
overflowEntries.clear();
272
* The implementation throws a {@code ClassCastException} if o is not an
273
* object of type {@code K}.
278
public V remove(Object o) {
280
@SuppressWarnings("unchecked")
282
final int index = binarySearchInArray(key);
284
return removeArrayEntryAt(index);
286
// overflowEntries might be Collections.unmodifiableMap(), so only
287
// call remove() if it is non-empty.
288
if (overflowEntries.isEmpty()) {
291
return overflowEntries.remove(key);
295
private V removeArrayEntryAt(int index) {
297
final V removed = entryList.remove(index).getValue();
298
if (!overflowEntries.isEmpty()) {
299
// Shift the first entry in the overflow to be the last entry in the
301
final Iterator<Map.Entry<K, V>> iterator =
302
getOverflowEntriesMutable().entrySet().iterator();
303
entryList.add(new Entry(iterator.next()));
310
* @param key The key to find in the entry array.
311
* @return The returned integer position follows the same semantics as the
312
* value returned by {@link java.util.Arrays#binarySearch()}.
314
private int binarySearchInArray(K key) {
316
int right = entryList.size() - 1;
318
// Optimization: For the common case in which entries are added in
319
// ascending tag order, check the largest element in the array before
320
// doing a full binary search.
322
int cmp = key.compareTo(entryList.get(right).getKey());
324
return -(right + 2); // Insert point is after "right".
325
} else if (cmp == 0) {
330
while (left <= right) {
331
int mid = (left + right) / 2;
332
int cmp = key.compareTo(entryList.get(mid).getKey());
335
} else if (cmp > 0) {
345
* Similar to the AbstractMap implementation of {@code keySet()} and
346
* {@code values()}, the entry set is created the first time this method is
347
* called, and returned in response to all subsequent calls.
352
public Set<Map.Entry<K, V>> entrySet() {
353
if (lazyEntrySet == null) {
354
lazyEntrySet = new EntrySet();
360
* @throws UnsupportedOperationException if {@link #makeImmutable()} has
363
private void checkMutable() {
365
throw new UnsupportedOperationException();
370
* @return a {@link SortedMap} to which overflow entries mappings can be
372
* @throws UnsupportedOperationException if {@link #makeImmutable()} has been
375
@SuppressWarnings("unchecked")
376
private SortedMap<K, V> getOverflowEntriesMutable() {
378
if (overflowEntries.isEmpty() && !(overflowEntries instanceof TreeMap)) {
379
overflowEntries = new TreeMap<K, V>();
381
return (SortedMap<K, V>) overflowEntries;
385
* Lazily creates the entry list. Any code that adds to the list must first
388
private void ensureEntryArrayMutable() {
390
if (entryList.isEmpty() && !(entryList instanceof ArrayList)) {
391
entryList = new ArrayList<Entry>(maxArraySize);
396
* Entry implementation that implements Comparable in order to support
397
* binary search witin the entry array. Also checks mutability in
398
* {@link #setValue()}.
400
private class Entry implements Map.Entry<K, V>, Comparable<Entry> {
405
Entry(Map.Entry<K, V> copy) {
406
this(copy.getKey(), copy.getValue());
409
Entry(K key, V value) {
420
public V getValue() {
425
public int compareTo(Entry other) {
426
return getKey().compareTo(other.getKey());
430
public V setValue(V newValue) {
432
final V oldValue = this.value;
433
this.value = newValue;
438
public boolean equals(Object o) {
442
if (!(o instanceof Map.Entry)) {
445
@SuppressWarnings("unchecked")
446
Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
447
return equals(key, other.getKey()) && equals(value, other.getValue());
451
public int hashCode() {
452
return (key == null ? 0 : key.hashCode()) ^
453
(value == null ? 0 : value.hashCode());
457
public String toString() {
458
return key + "=" + value;
461
/** equals() that handles null values. */
462
private boolean equals(Object o1, Object o2) {
463
return o1 == null ? o2 == null : o1.equals(o2);
468
* Stateless view of the entries in the field map.
470
private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
473
public Iterator<Map.Entry<K, V>> iterator() {
474
return new EntryIterator();
479
return SmallSortedMap.this.size();
483
* Throws a {@link ClassCastException} if o is not of the expected type.
488
public boolean contains(Object o) {
489
@SuppressWarnings("unchecked")
490
final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
491
final V existing = get(entry.getKey());
492
final V value = entry.getValue();
493
return existing == value ||
494
(existing != null && existing.equals(value));
498
public boolean add(Map.Entry<K, V> entry) {
499
if (!contains(entry)) {
500
put(entry.getKey(), entry.getValue());
507
* Throws a {@link ClassCastException} if o is not of the expected type.
512
public boolean remove(Object o) {
513
@SuppressWarnings("unchecked")
514
final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
515
if (contains(entry)) {
516
SmallSortedMap.this.remove(entry.getKey());
523
public void clear() {
524
SmallSortedMap.this.clear();
529
* Iterator implementation that switches from the entry array to the overflow
530
* entries appropriately.
532
private class EntryIterator implements Iterator<Map.Entry<K, V>> {
534
private int pos = -1;
535
private boolean nextCalledBeforeRemove;
536
private Iterator<Map.Entry<K, V>> lazyOverflowIterator;
539
public boolean hasNext() {
540
return (pos + 1) < entryList.size() ||
541
getOverflowIterator().hasNext();
545
public Map.Entry<K, V> next() {
546
nextCalledBeforeRemove = true;
547
// Always increment pos so that we know whether the last returned value
548
// was from the array or from overflow.
549
if (++pos < entryList.size()) {
550
return entryList.get(pos);
552
return getOverflowIterator().next();
556
public void remove() {
557
if (!nextCalledBeforeRemove) {
558
throw new IllegalStateException("remove() was called before next()");
560
nextCalledBeforeRemove = false;
563
if (pos < entryList.size()) {
564
removeArrayEntryAt(pos--);
566
getOverflowIterator().remove();
571
* It is important to create the overflow iterator only after the array
572
* entries have been iterated over because the overflow entry set changes
573
* when the client calls remove() on the array entries, which invalidates
574
* any existing iterators.
576
private Iterator<Map.Entry<K, V>> getOverflowIterator() {
577
if (lazyOverflowIterator == null) {
578
lazyOverflowIterator = overflowEntries.entrySet().iterator();
580
return lazyOverflowIterator;
585
* Helper class that holds immutable instances of an Iterable/Iterator that
586
* we return when the overflow entries is empty. This eliminates the creation
587
* of an Iterator object when there is nothing to iterate over.
589
private static class EmptySet {
591
private static final Iterator<Object> ITERATOR = new Iterator<Object>() {
593
public boolean hasNext() {
597
public Object next() {
598
throw new NoSuchElementException();
601
public void remove() {
602
throw new UnsupportedOperationException();
606
private static final Iterable<Object> ITERABLE = new Iterable<Object>() {
608
public Iterator<Object> iterator() {
613
@SuppressWarnings("unchecked")
614
static <T> Iterable<T> iterable() {
615
return (Iterable<T>) ITERABLE;
added
removed
java/src/main/java/com/google/protobuf/SmallSortedMap.java
