Subversion Repositories Code-Repo

// Protocol Buffers - Google's data interchange format

// Copyright 2008 Google Inc.  All rights reserved.

// http://code.google.com/p/protobuf/

//

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

// notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

// copyright notice, this list of conditions and the following disclaimer

// in the documentation and/or other materials provided with the

// distribution.

//     * Neither the name of Google Inc. nor the names of its

// contributors may be used to endorse or promote products derived from

// this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

package com.google.protobuf;

import java.util.AbstractMap;

import java.util.AbstractSet;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Iterator;

import java.util.TreeMap;

import java.util.List;

import java.util.Map;

import java.util.NoSuchElementException;

import java.util.Set;

import java.util.SortedMap;

/**

 * 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 {@code k} mappings in an

 * array for a configurable value of {@code k}, allowing direct access to the

 * corresponding {@code 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:

 *

 * <pre>

 * for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) {

 *   process(fieldMap.getArrayEntryAt(i));

 * }

 * for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) {

 *   process(entry);

 * }

 * </pre>

 *

 * The resulting iteration is in order of ascending field tag number. The

 * object returned by {@link #entrySet()} adheres to the same contract but is

 * less efficient as it necessarily involves creating an object for iteration.

 * <p>

 * The tradeoff for this memory efficiency is that the worst case running time

 * of the {@code put()} operation is {@code O(k + lg n)}, which happens when

 * entries are added in descending order. {@code 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.

 * <p>

 * The running time for all other operations is similar to that of

 * {@code TreeMap}.

 * <p>

 * Instances are not thread-safe until {@link #makeImmutable()} is called,

 * after which any modifying operation will result in an

 * {@link UnsupportedOperationException}.

 *

 * @author darick@google.com Darick Tong

 */

// This class is final for all intents and purposes because the constructor is

// private. However, the FieldDescriptor-specific logic is encapsulated in

// a subclass to aid testability of the core logic.

class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> {

  /**

   * Creates a new instance for mapping FieldDescriptors to their values.

   * The {@link #makeImmutable()} implementation will convert the List values

   * of any repeated fields to unmodifiable lists.

   *

   * @param arraySize The size of the entry array containing the

   *        lexicographically smallest mappings.

   */

  static <FieldDescriptorType extends

      FieldSet.FieldDescriptorLite<FieldDescriptorType>>

      SmallSortedMap<FieldDescriptorType, Object> newFieldMap(int arraySize) {

    return new SmallSortedMap<FieldDescriptorType, Object>(arraySize) {

      @Override

      @SuppressWarnings("unchecked")

      public void makeImmutable() {

        if (!isImmutable()) {

          for (int i = 0; i < getNumArrayEntries(); i++) {

            final Map.Entry<FieldDescriptorType, Object> entry =

                getArrayEntryAt(i);

            if (entry.getKey().isRepeated()) {

              final List value = (List) entry.getValue();

              entry.setValue(Collections.unmodifiableList(value));

            }

          }

          for (Map.Entry<FieldDescriptorType, Object> entry :

                   getOverflowEntries()) {

            if (entry.getKey().isRepeated()) {

              final List value = (List) entry.getValue();

              entry.setValue(Collections.unmodifiableList(value));

            }

          }

        }

        super.makeImmutable();

      }

    };

  }

  /**

   * Creates a new instance for testing.

   *

   * @param arraySize The size of the entry array containing the

   *        lexicographically smallest mappings.

   */

  static <K extends Comparable<K>, V> SmallSortedMap<K, V> newInstanceForTest(

      int arraySize) {

    return new SmallSortedMap<K, V>(arraySize);

  }

  private final int maxArraySize;

  // The "entry array" is actually a List because generic arrays are not

  // allowed. ArrayList also nicely handles the entry shifting on inserts and

  // removes.

  private List<Entry> entryList;

  private Map<K, V> overflowEntries;

  private boolean isImmutable;

  // The EntrySet is a stateless view of the Map. It's initialized the first

  // time it is requested and reused henceforth.

  private volatile EntrySet lazyEntrySet;

  /**

   * @code arraySize Size of the array in which the lexicographically smallest

   *       mappings are stored. (i.e. the {@code k} referred to in the class

   *       documentation).

   */

  private SmallSortedMap(int arraySize) {

    this.maxArraySize = arraySize;

    this.entryList = Collections.emptyList();

    this.overflowEntries = Collections.emptyMap();

  }

  /** Make this map immutable from this point forward. */

  public void makeImmutable() {

    if (!isImmutable) {

      // Note: There's no need to wrap the entryList in an unmodifiableList

      // because none of the list's accessors are exposed. The iterator() of

      // overflowEntries, on the other hand, is exposed so it must be made

      // unmodifiable.

      overflowEntries = overflowEntries.isEmpty() ?

          Collections.<K, V>emptyMap() :

          Collections.unmodifiableMap(overflowEntries);

      isImmutable = true;

    }

  }

  /** @return Whether {@link #makeImmutable()} has been called. */

  public boolean isImmutable() {

    return isImmutable;

  }

  /** @return The number of entries in the entry array. */

  public int getNumArrayEntries() {

    return entryList.size();

  }

  /** @return The array entry at the given {@code index}. */

  public Map.Entry<K, V> getArrayEntryAt(int index) {

    return entryList.get(index);

  }

  /** @return There number of overflow entries. */

  public int getNumOverflowEntries() {

    return overflowEntries.size();

  }

  /** @return An iterable over the overflow entries. */

  public Iterable<Map.Entry<K, V>> getOverflowEntries() {

    return overflowEntries.isEmpty() ?

        EmptySet.<Map.Entry<K, V>>iterable() :

        overflowEntries.entrySet();

  }

  @Override

  public int size() {

    return entryList.size() + overflowEntries.size();

  }

  /**

   * The implementation throws a {@code ClassCastException} if o is not an

   * object of type {@code K}.

   *

   * {@inheritDoc}

   */

  @Override

  public boolean containsKey(Object o) {

    @SuppressWarnings("unchecked")

    final K key = (K) o;

    return binarySearchInArray(key) >= 0 || overflowEntries.containsKey(key);

  }

  /**

   * The implementation throws a {@code ClassCastException} if o is not an

   * object of type {@code K}.

   *

   * {@inheritDoc}

   */

  @Override

  public V get(Object o) {

    @SuppressWarnings("unchecked")

    final K key = (K) o;

    final int index = binarySearchInArray(key);

    if (index >= 0) {

      return entryList.get(index).getValue();

    }

    return overflowEntries.get(key);

  }

  @Override

  public V put(K key, V value) {

    checkMutable();

    final int index = binarySearchInArray(key);

    if (index >= 0) {

      // Replace existing array entry.

      return entryList.get(index).setValue(value);

    }

    ensureEntryArrayMutable();

    final int insertionPoint = -(index + 1);

    if (insertionPoint >= maxArraySize) {

      // Put directly in overflow.

      return getOverflowEntriesMutable().put(key, value);

    }

    // Insert new Entry in array.

    if (entryList.size() == maxArraySize) {

      // Shift the last array entry into overflow.

      final Entry lastEntryInArray = entryList.remove(maxArraySize - 1);

      getOverflowEntriesMutable().put(lastEntryInArray.getKey(),

                                      lastEntryInArray.getValue());

    }

    entryList.add(insertionPoint, new Entry(key, value));

    return null;

  }

  @Override

  public void clear() {

    checkMutable();

    if (!entryList.isEmpty()) {

      entryList.clear();

    }

    if (!overflowEntries.isEmpty()) {

      overflowEntries.clear();

    }

  }

  /**

   * The implementation throws a {@code ClassCastException} if o is not an

   * object of type {@code K}.

   *

   * {@inheritDoc}

   */

  @Override

  public V remove(Object o) {

    checkMutable();

    @SuppressWarnings("unchecked")

    final K key = (K) o;

    final int index = binarySearchInArray(key);

    if (index >= 0) {

      return removeArrayEntryAt(index);

    }

    // overflowEntries might be Collections.unmodifiableMap(), so only

    // call remove() if it is non-empty.

    if (overflowEntries.isEmpty()) {

      return null;

    } else {

      return overflowEntries.remove(key);

    }

  }

  private V removeArrayEntryAt(int index) {

    checkMutable();

    final V removed = entryList.remove(index).getValue();

    if (!overflowEntries.isEmpty()) {

      // Shift the first entry in the overflow to be the last entry in the

      // array.

      final Iterator<Map.Entry<K, V>> iterator =

          getOverflowEntriesMutable().entrySet().iterator();

      entryList.add(new Entry(iterator.next()));

      iterator.remove();

    }

    return removed;

  }

  /**

   * @param key The key to find in the entry array.

   * @return The returned integer position follows the same semantics as the

   *     value returned by {@link java.util.Arrays#binarySearch()}.

   */

  private int binarySearchInArray(K key) {

    int left = 0;

    int right = entryList.size() - 1;

    // Optimization: For the common case in which entries are added in

    // ascending tag order, check the largest element in the array before

    // doing a full binary search.

    if (right >= 0) {

      int cmp = key.compareTo(entryList.get(right).getKey());

      if (cmp > 0) {

        return -(right + 2);  // Insert point is after "right".

      } else if (cmp == 0) {

        return right;

      }

    }

    while (left <= right) {

      int mid = (left + right) / 2;

      int cmp = key.compareTo(entryList.get(mid).getKey());

      if (cmp < 0) {

        right = mid - 1;

      } else if (cmp > 0) {

        left = mid + 1;

      } else {

        return mid;

      }

    }

    return -(left + 1);

  }

  /**

   * Similar to the AbstractMap implementation of {@code keySet()} and

   * {@code values()}, the entry set is created the first time this method is

   * called, and returned in response to all subsequent calls.

   *

   * {@inheritDoc}

   */

  @Override

  public Set<Map.Entry<K, V>> entrySet() {

    if (lazyEntrySet == null) {

      lazyEntrySet = new EntrySet();

    }

    return lazyEntrySet;

  }

  /**

   * @throws UnsupportedOperationException if {@link #makeImmutable()} has

   *         has been called.

   */

  private void checkMutable() {

    if (isImmutable) {

      throw new UnsupportedOperationException();

    }

  }

  /**

   * @return a {@link SortedMap} to which overflow entries mappings can be

   *         added or removed.

   * @throws UnsupportedOperationException if {@link #makeImmutable()} has been

   *         called.

   */

  @SuppressWarnings("unchecked")

  private SortedMap<K, V> getOverflowEntriesMutable() {

    checkMutable();

    if (overflowEntries.isEmpty() && !(overflowEntries instanceof TreeMap)) {

      overflowEntries = new TreeMap<K, V>();

    }

    return (SortedMap<K, V>) overflowEntries;

  }

  /**

   * Lazily creates the entry list. Any code that adds to the list must first

   * call this method.

   */

  private void ensureEntryArrayMutable() {

    checkMutable();

    if (entryList.isEmpty() && !(entryList instanceof ArrayList)) {

      entryList = new ArrayList<Entry>(maxArraySize);

    }

  }

  /**

   * Entry implementation that implements Comparable in order to support

   * binary search witin the entry array. Also checks mutability in

   * {@link #setValue()}.

   */

  private class Entry implements Map.Entry<K, V>, Comparable<Entry> {

    private final K key;

    private V value;

    Entry(Map.Entry<K, V> copy) {

      this(copy.getKey(), copy.getValue());

    }

    Entry(K key, V value) {

      this.key = key;

      this.value = value;

    }

    //@Override (Java 1.6 override semantics, but we must support 1.5)

    public K getKey() {

      return key;

    }

    //@Override (Java 1.6 override semantics, but we must support 1.5)

    public V getValue() {

      return value;

    }

    //@Override (Java 1.6 override semantics, but we must support 1.5)

    public int compareTo(Entry other) {

      return getKey().compareTo(other.getKey());

    }

    //@Override (Java 1.6 override semantics, but we must support 1.5)

    public V setValue(V newValue) {

      checkMutable();

      final V oldValue = this.value;

      this.value = newValue;

      return oldValue;

    }

    @Override

    public boolean equals(Object o) {

      if (o == this) {

        return true;

      }

      if (!(o instanceof Map.Entry)) {

        return false;

      }

      @SuppressWarnings("unchecked")

      Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;

      return equals(key, other.getKey()) && equals(value, other.getValue());

    }

    @Override

    public int hashCode() {

      return (key == null ? 0 : key.hashCode()) ^

          (value == null ? 0 : value.hashCode());

    }

    @Override

    public String toString() {

      return key + "=" + value;

    }

    /** equals() that handles null values. */

    private boolean equals(Object o1, Object o2) {

      return o1 == null ? o2 == null : o1.equals(o2);

    }

  }

  /**

   * Stateless view of the entries in the field map.

   */

  private class EntrySet extends AbstractSet<Map.Entry<K, V>> {

    @Override

    public Iterator<Map.Entry<K, V>> iterator() {

      return new EntryIterator();

    }

    @Override

    public int size() {

      return SmallSortedMap.this.size();

    }

    /**

     * Throws a {@link ClassCastException} if o is not of the expected type.

     *

     * {@inheritDoc}

     */

    @Override

    public boolean contains(Object o) {

      @SuppressWarnings("unchecked")

      final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;

      final V existing = get(entry.getKey());

      final V value = entry.getValue();

      return existing == value ||

          (existing != null && existing.equals(value));

    }

    @Override

    public boolean add(Map.Entry<K, V> entry) {

      if (!contains(entry)) {

        put(entry.getKey(), entry.getValue());

        return true;

      }

      return false;

    }

    /**

     * Throws a {@link ClassCastException} if o is not of the expected type.

     *

     * {@inheritDoc}

     */

    @Override

    public boolean remove(Object o) {

      @SuppressWarnings("unchecked")

      final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;

      if (contains(entry)) {

        SmallSortedMap.this.remove(entry.getKey());

        return true;

      }

      return false;

    }

    @Override

    public void clear() {

      SmallSortedMap.this.clear();

    }

  }

  /**

   * Iterator implementation that switches from the entry array to the overflow

   * entries appropriately.

   */

  private class EntryIterator implements Iterator<Map.Entry<K, V>> {

    private int pos = -1;

    private boolean nextCalledBeforeRemove;

    private Iterator<Map.Entry<K, V>> lazyOverflowIterator;

    //@Override (Java 1.6 override semantics, but we must support 1.5)

    public boolean hasNext() {

      return (pos + 1) < entryList.size() ||

          getOverflowIterator().hasNext();

    }

    //@Override (Java 1.6 override semantics, but we must support 1.5)

    public Map.Entry<K, V> next() {

      nextCalledBeforeRemove = true;

      // Always increment pos so that we know whether the last returned value

      // was from the array or from overflow.

      if (++pos < entryList.size()) {

        return entryList.get(pos);

      }

      return getOverflowIterator().next();

    }

    //@Override (Java 1.6 override semantics, but we must support 1.5)

    public void remove() {

      if (!nextCalledBeforeRemove) {

        throw new IllegalStateException("remove() was called before next()");

      }

      nextCalledBeforeRemove = false;

      checkMutable();

      if (pos < entryList.size()) {

        removeArrayEntryAt(pos--);

      } else {

        getOverflowIterator().remove();

      }

    }

    /**

     * It is important to create the overflow iterator only after the array

     * entries have been iterated over because the overflow entry set changes

     * when the client calls remove() on the array entries, which invalidates

     * any existing iterators.

     */

    private Iterator<Map.Entry<K, V>> getOverflowIterator() {

      if (lazyOverflowIterator == null) {

        lazyOverflowIterator = overflowEntries.entrySet().iterator();

      }

      return lazyOverflowIterator;

    }

  }

  /**

   * Helper class that holds immutable instances of an Iterable/Iterator that

   * we return when the overflow entries is empty. This eliminates the creation

   * of an Iterator object when there is nothing to iterate over.

   */

  private static class EmptySet {

    private static final Iterator<Object> ITERATOR = new Iterator<Object>() {

      //@Override (Java 1.6 override semantics, but we must support 1.5)

      public boolean hasNext() {

        return false;

      }

      //@Override (Java 1.6 override semantics, but we must support 1.5)

      public Object next() {

        throw new NoSuchElementException();

      }

      //@Override (Java 1.6 override semantics, but we must support 1.5)

      public void remove() {

        throw new UnsupportedOperationException();

      }

    };

    private static final Iterable<Object> ITERABLE = new Iterable<Object>() {

      //@Override (Java 1.6 override semantics, but we must support 1.5)

      public Iterator<Object> iterator() {

        return ITERATOR;

      }

    };

    @SuppressWarnings("unchecked")

    static <T> Iterable<T> iterable() {

      return (Iterable<T>) ITERABLE;

    }

  }

}