src/third_party/protobuf/java/src/main/java/com/google/protobuf/SmallSortedMap.java

   1 // Protocol Buffers - Google's data interchange format
   2 // Copyright 2008 Google Inc.  All rights reserved.
   3 // http://code.google.com/p/protobuf/
   4 //
   5 // Redistribution and use in source and binary forms, with or without
   6 // modification, are permitted provided that the following conditions are
   7 // met:
   8 //
   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
  14 // distribution.
  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.
  18 //
  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.
  30
  31 package com.google.protobuf;
  32
  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;
  40 import java.util.Map;
  41 import java.util.NoSuchElementException;
  42 import java.util.Set;
  43 import java.util.SortedMap;
  44
  45 /**
  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:
  53  *
  54  * <pre>   {@code
  55  * for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) {
  56  *   process(fieldMap.getArrayEntryAt(i));
  57  * }
  58  * for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) {
  59  *   process(entry);
  60  * }
  61  * }</pre>
  62  *
  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.
  66  * <p>
  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.
  74  * <p>
  75  * The running time for all other operations is similar to that of
  76  * {@code TreeMap}.
  77  * <p>
  78  * Instances are not thread-safe until {@link #makeImmutable()} is called,
  79  * after which any modifying operation will result in an
  80  * {@link UnsupportedOperationException}.
  81  *
  82  * @author darick@google.com Darick Tong
  83  */
  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> {
  88
  89   /**
  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.
  93    *
  94    * @param arraySize The size of the entry array containing the
  95    *        lexicographically smallest mappings.
  96    */
  97   static <FieldDescriptorType extends
  98       FieldSet.FieldDescriptorLite<FieldDescriptorType>>
  99       SmallSortedMap<FieldDescriptorType, Object> newFieldMap(int arraySize) {
 100     return new SmallSortedMap<FieldDescriptorType, Object>(arraySize) {
 101       @Override
 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 =
 107                 getArrayEntryAt(i);
 108             if (entry.getKey().isRepeated()) {
 109               final List value = (List) entry.getValue();
 110               entry.setValue(Collections.unmodifiableList(value));
 111             }
 112           }
 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));
 118             }
 119           }
 120         }
 121         super.makeImmutable();
 122       }
 123     };
 124   }
 125
 126   /**
 127    * Creates a new instance for testing.
 128    *
 129    * @param arraySize The size of the entry array containing the
 130    *        lexicographically smallest mappings.
 131    */
 132   static <K extends Comparable<K>, V> SmallSortedMap<K, V> newInstanceForTest(
 133       int arraySize) {
 134     return new SmallSortedMap<K, V>(arraySize);
 135   }
 136
 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
 140   // removes.
 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;
 147
 148   /**
 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
 151    *       documentation).
 152    */
 153   private SmallSortedMap(int arraySize) {
 154     this.maxArraySize = arraySize;
 155     this.entryList = Collections.emptyList();
 156     this.overflowEntries = Collections.emptyMap();
 157   }
 158
 159   /** Make this map immutable from this point forward. */
 160   public void makeImmutable() {
 161     if (!isImmutable) {
 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
 165       // unmodifiable.
 166       overflowEntries = overflowEntries.isEmpty() ?
 167           Collections.<K, V>emptyMap() :
 168           Collections.unmodifiableMap(overflowEntries);
 169       isImmutable = true;
 170     }
 171   }
 172
 173   /** @return Whether {@link #makeImmutable()} has been called. */
 174   public boolean isImmutable() {
 175     return isImmutable;
 176   }
 177
 178   /** @return The number of entries in the entry array. */
 179   public int getNumArrayEntries() {
 180     return entryList.size();
 181   }
 182
 183   /** @return The array entry at the given {@code index}. */
 184   public Map.Entry<K, V> getArrayEntryAt(int index) {
 185     return entryList.get(index);
 186   }
 187
 188   /** @return There number of overflow entries. */
 189   public int getNumOverflowEntries() {
 190     return overflowEntries.size();
 191   }
 192
 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();
 198   }
 199
 200   @Override
 201   public int size() {
 202     return entryList.size() + overflowEntries.size();
 203   }
 204
 205   /**
 206    * The implementation throws a {@code ClassCastException} if o is not an
 207    * object of type {@code K}.
 208    *
 209    * {@inheritDoc}
 210    */
 211   @Override
 212   public boolean containsKey(Object o) {
 213     @SuppressWarnings("unchecked")
 214     final K key = (K) o;
 215     return binarySearchInArray(key) >= 0 || overflowEntries.containsKey(key);
 216   }
 217
 218   /**
 219    * The implementation throws a {@code ClassCastException} if o is not an
 220    * object of type {@code K}.
 221    *
 222    * {@inheritDoc}
 223    */
 224   @Override
 225   public V get(Object o) {
 226     @SuppressWarnings("unchecked")
 227     final K key = (K) o;
 228     final int index = binarySearchInArray(key);
 229     if (index >= 0) {
 230       return entryList.get(index).getValue();
 231     }
 232     return overflowEntries.get(key);
 233   }
 234
 235   @Override
 236   public V put(K key, V value) {
 237     checkMutable();
 238     final int index = binarySearchInArray(key);
 239     if (index >= 0) {
 240       // Replace existing array entry.
 241       return entryList.get(index).setValue(value);
 242     }
 243     ensureEntryArrayMutable();
 244     final int insertionPoint = -(index + 1);
 245     if (insertionPoint >= maxArraySize) {
 246       // Put directly in overflow.
 247       return getOverflowEntriesMutable().put(key, value);
 248     }
 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());
 255     }
 256     entryList.add(insertionPoint, new Entry(key, value));
 257     return null;
 258   }
 259
 260   @Override
 261   public void clear() {
 262     checkMutable();
 263     if (!entryList.isEmpty()) {
 264       entryList.clear();
 265     }
 266     if (!overflowEntries.isEmpty()) {
 267       overflowEntries.clear();
 268     }
 269   }
 270
 271   /**
 272    * The implementation throws a {@code ClassCastException} if o is not an
 273    * object of type {@code K}.
 274    *
 275    * {@inheritDoc}
 276    */
 277   @Override
 278   public V remove(Object o) {
 279     checkMutable();
 280     @SuppressWarnings("unchecked")
 281     final K key = (K) o;
 282     final int index = binarySearchInArray(key);
 283     if (index >= 0) {
 284       return removeArrayEntryAt(index);
 285     }
 286     // overflowEntries might be Collections.unmodifiableMap(), so only
 287     // call remove() if it is non-empty.
 288     if (overflowEntries.isEmpty()) {
 289       return null;
 290     } else {
 291       return overflowEntries.remove(key);
 292     }
 293   }
 294
 295   private V removeArrayEntryAt(int index) {
 296     checkMutable();
 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
 300       // array.
 301       final Iterator<Map.Entry<K, V>> iterator =
 302           getOverflowEntriesMutable().entrySet().iterator();
 303       entryList.add(new Entry(iterator.next()));
 304       iterator.remove();
 305     }
 306     return removed;
 307   }
 308
 309   /**
 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()}.
 313    */
 314   private int binarySearchInArray(K key) {
 315     int left = 0;
 316     int right = entryList.size() - 1;
 317
 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.
 321     if (right >= 0) {
 322       int cmp = key.compareTo(entryList.get(right).getKey());
 323       if (cmp > 0) {
 324         return -(right + 2);  // Insert point is after "right".
 325       } else if (cmp == 0) {
 326         return right;
 327       }
 328     }
 329
 330     while (left <= right) {
 331       int mid = (left + right) / 2;
 332       int cmp = key.compareTo(entryList.get(mid).getKey());
 333       if (cmp < 0) {
 334         right = mid - 1;
 335       } else if (cmp > 0) {
 336         left = mid + 1;
 337       } else {
 338         return mid;
 339       }
 340     }
 341     return -(left + 1);
 342   }
 343
 344   /**
 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.
 348    *
 349    * {@inheritDoc}
 350    */
 351   @Override
 352   public Set<Map.Entry<K, V>> entrySet() {
 353     if (lazyEntrySet == null) {
 354       lazyEntrySet = new EntrySet();
 355     }
 356     return lazyEntrySet;
 357   }
 358
 359   /**
 360    * @throws UnsupportedOperationException if {@link #makeImmutable()} has
 361    *         has been called.
 362    */
 363   private void checkMutable() {
 364     if (isImmutable) {
 365       throw new UnsupportedOperationException();
 366     }
 367   }
 368
 369   /**
 370    * @return a {@link SortedMap} to which overflow entries mappings can be
 371    *         added or removed.
 372    * @throws UnsupportedOperationException if {@link #makeImmutable()} has been
 373    *         called.
 374    */
 375   @SuppressWarnings("unchecked")
 376   private SortedMap<K, V> getOverflowEntriesMutable() {
 377     checkMutable();
 378     if (overflowEntries.isEmpty() && !(overflowEntries instanceof TreeMap)) {
 379       overflowEntries = new TreeMap<K, V>();
 380     }
 381     return (SortedMap<K, V>) overflowEntries;
 382   }
 383
 384   /**
 385    * Lazily creates the entry list. Any code that adds to the list must first
 386    * call this method.
 387    */
 388   private void ensureEntryArrayMutable() {
 389     checkMutable();
 390     if (entryList.isEmpty() && !(entryList instanceof ArrayList)) {
 391       entryList = new ArrayList<Entry>(maxArraySize);
 392     }
 393   }
 394
 395   /**
 396    * Entry implementation that implements Comparable in order to support
 397    * binary search within the entry array. Also checks mutability in
 398    * {@link #setValue()}.
 399    */
 400   private class Entry implements Map.Entry<K, V>, Comparable<Entry> {
 401
 402     private final K key;
 403     private V value;
 404
 405     Entry(Map.Entry<K, V> copy) {
 406       this(copy.getKey(), copy.getValue());
 407     }
 408
 409     Entry(K key, V value) {
 410       this.key = key;
 411       this.value = value;
 412     }
 413
 414     //@Override (Java 1.6 override semantics, but we must support 1.5)
 415     public K getKey() {
 416       return key;
 417     }
 418
 419     //@Override (Java 1.6 override semantics, but we must support 1.5)
 420     public V getValue() {
 421       return value;
 422     }
 423
 424     //@Override (Java 1.6 override semantics, but we must support 1.5)
 425     public int compareTo(Entry other) {
 426       return getKey().compareTo(other.getKey());
 427     }
 428
 429     //@Override (Java 1.6 override semantics, but we must support 1.5)
 430     public V setValue(V newValue) {
 431       checkMutable();
 432       final V oldValue = this.value;
 433       this.value = newValue;
 434       return oldValue;
 435     }
 436
 437     @Override
 438     public boolean equals(Object o) {
 439       if (o == this) {
 440         return true;
 441       }
 442       if (!(o instanceof Map.Entry)) {
 443         return false;
 444       }
 445       @SuppressWarnings("unchecked")
 446       Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
 447       return equals(key, other.getKey()) && equals(value, other.getValue());
 448     }
 449
 450     @Override
 451     public int hashCode() {
 452       return (key == null ? 0 : key.hashCode()) ^
 453           (value == null ? 0 : value.hashCode());
 454     }
 455
 456     @Override
 457     public String toString() {
 458       return key + "=" + value;
 459     }
 460
 461     /** equals() that handles null values. */
 462     private boolean equals(Object o1, Object o2) {
 463       return o1 == null ? o2 == null : o1.equals(o2);
 464     }
 465   }
 466
 467   /**
 468    * Stateless view of the entries in the field map.
 469    */
 470   private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
 471
 472     @Override
 473     public Iterator<Map.Entry<K, V>> iterator() {
 474       return new EntryIterator();
 475     }
 476
 477     @Override
 478     public int size() {
 479       return SmallSortedMap.this.size();
 480     }
 481
 482     /**
 483      * Throws a {@link ClassCastException} if o is not of the expected type.
 484      *
 485      * {@inheritDoc}
 486      */
 487     @Override
 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));
 495     }
 496
 497     @Override
 498     public boolean add(Map.Entry<K, V> entry) {
 499       if (!contains(entry)) {
 500         put(entry.getKey(), entry.getValue());
 501         return true;
 502       }
 503       return false;
 504     }
 505
 506     /**
 507      * Throws a {@link ClassCastException} if o is not of the expected type.
 508      *
 509      * {@inheritDoc}
 510      */
 511     @Override
 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());
 517         return true;
 518       }
 519       return false;
 520     }
 521
 522     @Override
 523     public void clear() {
 524       SmallSortedMap.this.clear();
 525     }
 526   }
 527
 528   /**
 529    * Iterator implementation that switches from the entry array to the overflow
 530    * entries appropriately.
 531    */
 532   private class EntryIterator implements Iterator<Map.Entry<K, V>> {
 533
 534     private int pos = -1;
 535     private boolean nextCalledBeforeRemove;
 536     private Iterator<Map.Entry<K, V>> lazyOverflowIterator;
 537
 538     //@Override (Java 1.6 override semantics, but we must support 1.5)
 539     public boolean hasNext() {
 540       return (pos + 1) < entryList.size() ||
 541           getOverflowIterator().hasNext();
 542     }
 543
 544     //@Override (Java 1.6 override semantics, but we must support 1.5)
 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);
 551       }
 552       return getOverflowIterator().next();
 553     }
 554
 555     //@Override (Java 1.6 override semantics, but we must support 1.5)
 556     public void remove() {
 557       if (!nextCalledBeforeRemove) {
 558         throw new IllegalStateException("remove() was called before next()");
 559       }
 560       nextCalledBeforeRemove = false;
 561       checkMutable();
 562
 563       if (pos < entryList.size()) {
 564         removeArrayEntryAt(pos--);
 565       } else {
 566         getOverflowIterator().remove();
 567       }
 568     }
 569
 570     /**
 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.
 575      */
 576     private Iterator<Map.Entry<K, V>> getOverflowIterator() {
 577       if (lazyOverflowIterator == null) {
 578         lazyOverflowIterator = overflowEntries.entrySet().iterator();
 579       }
 580       return lazyOverflowIterator;
 581     }
 582   }
 583
 584   /**
 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.
 588    */
 589   private static class EmptySet {
 590
 591     private static final Iterator<Object> ITERATOR = new Iterator<Object>() {
 592       //@Override (Java 1.6 override semantics, but we must support 1.5)
 593       public boolean hasNext() {
 594         return false;
 595       }
 596       //@Override (Java 1.6 override semantics, but we must support 1.5)
 597       public Object next() {
 598         throw new NoSuchElementException();
 599       }
 600       //@Override (Java 1.6 override semantics, but we must support 1.5)
 601       public void remove() {
 602         throw new UnsupportedOperationException();
 603       }
 604     };
 605
 606     private static final Iterable<Object> ITERABLE = new Iterable<Object>() {
 607       //@Override (Java 1.6 override semantics, but we must support 1.5)
 608       public Iterator<Object> iterator() {
 609         return ITERATOR;
 610       }
 611     };
 612
 613     @SuppressWarnings("unchecked")
 614     static <T> Iterable<T> iterable() {
 615       return (Iterable<T>) ITERABLE;
 616     }
 617   }
 618 }