am 9aaf5076: ProtoBuf update * Added IntMap that uses Hashtable for larger keys * Chagned to use IntMap to allow larger tags * Changed to use autoboxing for int/longs.

Merge commit '9aaf507646c866ab131bf2bcd973882ff9f553cf'

* commit '9aaf507646c866ab131bf2bcd973882ff9f553cf':
  ProtoBuf update

4 files changed, 653 insertions, 171 deletions

diff --git a/src/com/google/common/io/protocol/IntMap.java b/src/com/google/common/io/protocol/IntMap.java
new file mode 100644
index 0000000..9f0b8fc
--- /dev/null
+++ b/src/com/google/common/io/protocol/IntMap.java
@@ -0,0 +1,383 @@
+// Copyright 2009 Google Inc. All Rights Reserved.
+
+package com.google.common.io.protocol;
+
+import java.util.Enumeration;
+import java.util.Hashtable;
+import java.util.NoSuchElementException;
+
+/**
+ * A Map from primitive integers to Object values. This stores values
+ * for smaller keys in an Object array, and uses {@link Hashtable}
+ * only for larger keys. This is specifically designed to be used by
+ * J2me protocol buffer runtime ({@link ProtoBuf}, {@link ProtoBufType})
+ * to support large tags that are commonly used in Extensions/MessageSet.
+ *
+ * This class is not thread safe, so the client has to provide
+ * appropriate locking mechanism if the map is to be used from
+ * multiple threads.
+ */
+public class IntMap {
+  private static final int MAX_LOWER_BUFFER_SIZE = 64;
+  private static final int INITIAL_LOWER_BUFFER_SIZE = 8;
+
+  /**
+   * An iterator that returns int keys of the IntMap. IntMap has its
+   * own Iterator instead of Enumeration to avoid autoboxing.  This
+   * uses the same buffer of the IntMap, so you should not update the
+   * IntMap while the iterator is in use. Once the IntMap is changed,
+   * the behavior of preiously obtained iterator is undefined, and a new
+   * KeyIterator has to be used instead.
+   */
+  public class KeyIterator {
+    private int oneAheadIndex = 0;
+    private int currentKey = Integer.MIN_VALUE;
+    private Enumeration  higherKeyEnumerator = null;
+
+    /**
+     * @returns true if there is more keys.
+     */
+    public boolean hasNext() {
+      if (currentKey != Integer.MIN_VALUE) {
+        return true;
+      }
+      if (oneAheadIndex <= maxLowerKey) {
+        for (; oneAheadIndex <= maxLowerKey; oneAheadIndex++) {
+          if (lower[oneAheadIndex] != null) {
+            // record the key, then increment the oneAheadIndex.
+            currentKey = oneAheadIndex++;
+            return true;
+          }
+        }
+      }
+      if (higher != null) {
+        if (higherKeyEnumerator == null) {
+          higherKeyEnumerator = higher.keys();
+        }
+        if (higherKeyEnumerator.hasMoreElements()) {
+          Integer key = (Integer) higherKeyEnumerator.nextElement();
+          currentKey = key.intValue();
+          return true;
+        }
+      }
+      return false;
+    }
+
+    /**
+     * @returns next key
+     * @throws NoSuchElementException if there is no more keys.
+     */
+    public int next() {
+      if (currentKey == Integer.MIN_VALUE && !hasNext()) {
+        throw new NoSuchElementException();
+      }
+      int key = currentKey;
+      currentKey = Integer.MIN_VALUE;
+      return key;
+    }
+  }
+
+  /** Stores values for lower keys */
+  private Object[] lower;
+
+  /** Hashtable for higher tags */
+  private Hashtable higher;
+
+  /** A maximum key that has been ever added to the lower buffer.*/
+  private int maxLowerKey;
+
+  /** A maximum key that has been ever added to the map.*/
+  private int maxKey;
+
+  /** the number of elements in lower buffer */
+  private int lowerCount;
+
+  /**
+   * Constructs an {@link IntMap} with default lower buffer size.
+   */
+  public IntMap() {
+    this(INITIAL_LOWER_BUFFER_SIZE); // can expand 3 times
+  }
+
+  /**
+   * Constructs an {@link IntMap} with the suggested initial lower buffer size.
+   * The argument is just a hint and may not be used. If its value is
+   * larger than {@link MAX_LOWER_BUFFER_SIZE} or negative, it will use the
+   * MAX_LOWER_BUFFER_SIZE instead.
+   */
+  IntMap(int initialLowerBufferSize) {
+    int lowerBufferSize = INITIAL_LOWER_BUFFER_SIZE;
+    if (initialLowerBufferSize > 0) {
+      lowerBufferSize = Math.min(initialLowerBufferSize, MAX_LOWER_BUFFER_SIZE);
+    }
+    lower = new Object[lowerBufferSize];
+    lowerCount = 0;
+    maxKey = Integer.MIN_VALUE;
+    maxLowerKey = Integer.MIN_VALUE;
+  }
+
+  /**
+   * A factory method to constructs an {@link IntMap} with the same
+   * lower buffer size.
+   *
+   * @return a new IntMap whose lower buffer size is same as
+   * this instance.
+   */
+  public IntMap newIntMapWithSameBufferSize() {
+    return new IntMap(maxLowerKey);
+  }
+
+  /**
+   * @return the {@link KeyIterator} of the map.
+   */
+  public KeyIterator keys() {
+    return new KeyIterator();
+  }
+
+  /**
+   * Returns max key that ever added to the map. Note that this is not
+   * max for current state. Removing the max key will not update the
+   * max key value. If nothing is added, it will return {@link
+   * Integer.MIN_VALUE}, which means you cannot tell if an value is
+   * added with MIN_VALUE key.
+   */
+  public int maxKey() {
+    return maxKey;
+  }
+
+  /**
+   * Returns the number of key-value pairs in the map.
+   */
+  public int size() {
+    return higher == null ? lowerCount : lowerCount + higher.size();
+  }
+
+  /**
+   * @return true if the map is empty.
+   */
+  public boolean isEmpty() {
+    return size() == 0;
+  }
+
+  /**
+   * Clears all key/value pairs. The map becomes empty after this
+   * operation, but does not release memory.
+   */
+  public void clear() {
+    for (int i = 0; i < lower.length; i++) {
+      lower[i] = null;
+    }
+    if (higher != null) higher.clear();
+    maxKey = Integer.MIN_VALUE;
+    maxLowerKey = Integer.MIN_VALUE;
+    lowerCount = 0;
+  }
+
+  /**
+   * Returns the value associated with the given key.
+   *
+   * @param key a key
+   * @return the value associated with the given key. null if the map has
+   * no value for the key.
+   */
+  public Object get(int key) {
+    if (key > maxKey) {
+      return null;
+    } else if (0 <= key && key <= maxLowerKey) {
+      return lower[key];
+    } else if (higher != null) {
+      return higher.get(key);
+    } else {
+      return null;
+    }
+  }
+
+  /**
+   * Maps the specified key to the given value in the {@link IntMap}.
+   * Caveat: Passing null value removes the value from the map. This is to
+   * keep the semantics used in {@link ProtoBuf}.
+   *
+   * @param key a key
+   * @param value the value to be added to the Map. If this is null,
+   * the key will be removed from the map. This method does nothing if
+   * the key does not exist and value is null.
+   */
+  public void put(int key, Object value) {
+    if (value == null) {
+      remove(key);
+      return;
+    }
+    expandLowerIfNecessary(key);
+    maxKey = Math.max(key, maxKey);
+    if (0 <= key && key < lower.length) {
+      maxLowerKey = Math.max(key, maxLowerKey);
+      if (lower[key] == null) {
+        lowerCount++;
+      }
+      lower[key] = value;
+    } else {
+      if (higher == null) {
+        higher = new Hashtable();
+      }
+      higher.put(key, value);
+    }
+  }
+
+  /**
+   * Removes the key and corresponding value from the {@link IntMap}.
+   *
+   * @param key the key to remove. This method does nothing if the map does not
+   * have the value corresponding for the key.
+   * @return the removed value. null if the map does not have the value for
+   * the key.
+   */
+  public Object remove(int key) {
+    Object deleted = null;
+    if (0 <= key && key < lower.length) {
+      deleted = lower[key];
+      if (deleted != null) {
+        lowerCount--;
+      }
+      lower[key] = null;
+    } else if (higher != null) {
+      return higher.remove(key);
+    }
+    return deleted;
+  }
+
+  /**
+   * Tests if given key has a corresponding value in this {@link IntMap}.
+   *
+   * @param key possible key.
+   * @return <code>true</code> if the given key has the correspoding
+   * value. <code>false</code> otherwise.
+   */
+  public boolean containsKey(int key) {
+    if (0 <= key && key < lower.length) {
+      return lower[key] != null;
+    } else if (higher != null) {
+      return higher.containsKey(key);
+    }
+    return false;
+  }
+
+  /**
+   * Returns hashcode for {@link IntMap}.
+   */
+  public int hashCode() {
+    int hashCode = 1;
+    for (int i = 0; i < lower.length ; i++) {
+      Object value = lower[i];
+      if (value != null) {
+        hashCode = 31 * hashCode + value.hashCode() + i;
+      }
+    }
+    // Hashtable in J2me does not implement hashCode(), so we simply
+    // use the size of hashtable.
+    return higher == null ? hashCode : hashCode + higher.size();
+  }
+
+  /**
+   * Compares the equality. Two IntMaps are considered equals iff
+   * both map have the same key-value pairs.
+   * Caveat: This assumes that the Class of each value object implements
+   * equals correctly. This may not be the case in J2me.
+   *
+   * @param object an object to be compared with
+   * @return true if the specified Object is equal to this IntMap
+   */
+  public boolean equals(Object object) {
+    if (this == object) {
+      return true;
+    }
+    if (object == null || !(object instanceof IntMap)) {
+      return false;
+    }
+    IntMap peer = (IntMap) object;
+    if (size() != peer.size()) {
+      return false;
+    }
+    return compareLowerBuffer(lower, peer.lower) &&
+        compareHashtable(higher, peer.higher);
+  }
+
+  private boolean compareLowerBuffer(Object[] lower1, Object[] lower2) {
+    int min = Math.min(lower1.length, lower2.length);
+
+    for (int i = 0; i < min; i++) {
+      if ((lower1[i] == null && lower2[i] != null) ||
+          (lower1[i] != null && !lower1[i].equals(lower2[i]))) {
+        return false;
+      }
+    }
+    // make sure there are no values in remaining fields.
+    if (lower1.length > lower2.length) {
+      for (int i = min; i < lower1.length; i++) {
+        if (lower1[i] != null) return false;
+      }
+    } else if (lower1.length < lower2.length) {
+      for (int i = min; i < lower2.length; i++) {
+        if (lower2[i] != null) return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * J2me's Hashtable does not implement equal, Bummer!
+   */
+  private static boolean compareHashtable(Hashtable h1, Hashtable h2) {
+    if (h1 == h2) { // null == null is caught here
+      return true;
+    }
+    if (h1 == null || h2 == null) {
+      return false;
+    }
+    if (h1.size() != h2.size()) {
+      return false;
+    }
+    // Ensure the values are the same.
+    Enumeration h1Keys = h1.keys();
+    while (h1Keys.hasMoreElements()) {
+      Object key = h1Keys.nextElement();
+      Object h1Value = h1.get(key);
+      Object h2Value = h2.get(key);
+      if (!h1Value.equals(h2Value)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Expands lower buffer iff the key does not fit to current buffer size,
+   * but will fit in MAX buffer size.
+   */
+  private void expandLowerIfNecessary(int key) {
+    if (key <= MAX_LOWER_BUFFER_SIZE && key >= lower.length && key > 0) {
+      int size = lower.length;
+      do {
+        size <<= 1;
+      } while (size <= key);
+      size = Math.min(size, MAX_LOWER_BUFFER_SIZE);
+      Object[] newLower = new Object[size];
+      System.arraycopy(lower, 0, newLower, 0, lower.length);
+      lower = newLower;
+    }
+  }
+
+  /* {@inheritDoc} */
+  public String toString() {
+    StringBuffer buffer = new StringBuffer("IntMap{lower:");
+    for (int i = 0; i < lower.length; i++) {
+      if (lower[i] != null) {
+        buffer.append(i);
+        buffer.append("=>");
+        buffer.append(lower[i]);
+        buffer.append(", ");
+      }
+    }
+    buffer.append(", higher:" + higher + "}");
+    return buffer.toString();
+  }
+}
diff --git a/src/com/google/common/io/protocol/ProtoBuf.java b/src/com/google/common/io/protocol/ProtoBuf.java
index 2a2f8b7..ae7e4a6 100644
--- a/src/com/google/common/io/protocol/ProtoBuf.java
+++ b/src/com/google/common/io/protocol/ProtoBuf.java
@@ -7,9 +7,7 @@ import java.io.*;
 import java.util.*;
 
 /**
- * Protocol buffer message object. Currently, it is assumed that tags ids are 
- * not large. This could be improved by storing a start offset, reducing the 
- * assumption to a dense number space.
+ * Protocol buffer message object.
  * <p>
  * ProtoBuf instances may or may not reference a ProtoBufType instance,
  * representing information from a corresponding .proto file, which defines tag 
@@ -33,7 +31,6 @@ import java.util.*;
  * this behavior is that default values cannot be removed -- they would reappear
  * after a serialization cycle. If a tag has repeated values, setXXX(tag, value)
  * will overwrite all of them and getXXX(tag) will throw an exception.
- *
  */
 
 public class ProtoBuf {
@@ -45,7 +42,9 @@ public class ProtoBuf {
   private static final String MSG_MISMATCH = "Type mismatch";
   private static final String MSG_UNSUPPORTED = "Unsupp.Type";
 
-  // names copied from //net/proto2/internal/wire_format.cc
+  // see
+  // http://code.google.com/apis/protocolbuffers/docs/overview.html
+  // for more details about wire format.
   static final int WIRETYPE_END_GROUP = 4;
   static final int WIRETYPE_FIXED32 = 5;
   static final int WIRETYPE_FIXED64 = 1;
@@ -56,20 +55,19 @@ public class ProtoBuf {
   /** Maximum number of bytes for VARINT wire format (64 bit, 7 bit/byte) */
   private static final int VARINT_MAX_BYTES = 10;
   
-  private static Long[] SMALL_NUMBERS = {
-      new Long(0), new Long(1), new Long(2), new Long(3), new Long(4),
-      new Long(5), new Long(6), new Long(7), new Long(8), new Long(9),
-      new Long(10), new Long(11), new Long(12), new Long(13), new Long(14),
-      new Long(15)};
-
   private ProtoBufType msgType;
-  private final Vector values = new Vector();
+  private final IntMap values;
   
   /** 
    * Wire types picked up on the wire or implied by setters (if no other
    * type information is available.
    */
-  private final StringBuffer wireTypes = new StringBuffer();
+  private final IntMap wireTypes;
+
+  /**
+   * Saved by a call to #getCachedDataSize(false) and returned in #getCachedSize()
+   */
+  private int cachedSize = Integer.MIN_VALUE;
 
   /**
    * Creates a protocol message according to the given description. The
@@ -78,14 +76,22 @@ public class ProtoBuf {
    */
   public ProtoBuf(ProtoBufType type) {
     this.msgType = type;
+    if (type != null) {
+      // if the type is known, use the type to create IntMaps.
+      values = type.newIntMapForProtoBuf();
+      wireTypes = type.newIntMapForProtoBuf();
+    } else {
+      values = new IntMap();
+      wireTypes = new IntMap();
+    }
   }
 
-  /** 
+  /**
    * Clears all data stored in this ProtoBuf.
    */
   public void clear() {
-    values.setSize(0);
-    wireTypes.setLength(0);
+    values.clear();
+    wireTypes.clear();
   }
   
   /**
@@ -210,7 +216,7 @@ public class ProtoBuf {
     return (int) ((Long) getObject(tag, ProtoBufType.TYPE_INT32)).longValue();
   }
 
-  /** 
+  /**
    * Returns the integer value for the given repeated tag at the given index. 
    */
   public int getInt(int tag, int index) {
@@ -305,7 +311,8 @@ public class ProtoBuf {
    * @param type the new type
    */
   void setType(ProtoBufType type) {
-    if (values.size() != 0 || 
+    // reject if the type is already set, or value is alreay set.
+    if (!values.isEmpty() ||
         (msgType != null && type != null && type != msgType)) {
       throw new IllegalArgumentException();
     }
@@ -359,7 +366,8 @@ public class ProtoBuf {
    * @return          this
    * @throws          IOException raised if an IO exception occurs in the 
    *                  underlying stream or the end of the stream is reached at 
-   *                  an unexpected position
+   *                  an unexpected position, or if we encounter bad data
+   *                  while reading.
    */
   public int parse(InputStream is, int available) throws IOException {
 
@@ -376,11 +384,7 @@ public class ProtoBuf {
         break;
       }
       int tag = (int) (tagAndType >>> 3);
-      while (wireTypes.length() <= tag){
-        wireTypes.append((char) ProtoBufType.TYPE_UNDEFINED);
-      }
-      wireTypes.setCharAt(tag, (char) wireType);
-
+      wireTypes.put(tag, wireType);
       // first step: decode tag value
       Object value;
       switch (wireType) {
@@ -390,8 +394,7 @@ public class ProtoBuf {
           if (isZigZagEncodedType(tag)) {
             v = zigZagDecode(v);
           }
-          value = (v >= 0 && v < SMALL_NUMBERS.length) ? 
-              SMALL_NUMBERS[(int) v] : new Long(v);
+          value = v;
           break;
 
         // also used for fixed values
@@ -408,9 +411,7 @@ public class ProtoBuf {
             shift += 8;
           }
 
-          value = (v >= 0 && v < SMALL_NUMBERS.length) 
-              ? SMALL_NUMBERS[(int) v]
-              : new Long(v);
+          value = v;
           break;
 
         case WIRETYPE_LENGTH_DELIMITED:
@@ -445,7 +446,8 @@ public class ProtoBuf {
           break;
 
         default:
-          throw new RuntimeException(MSG_UNSUPPORTED + wireType);
+          throw new IOException("Unknown wire type " + wireType +
+              ", reading garbage data?");
       }
       insertObject(tag, getCount(tag), value);
     }
@@ -466,9 +468,9 @@ public class ProtoBuf {
       throw new ArrayIndexOutOfBoundsException();
     }
     if (count == 1){
-      values.setElementAt(null, tag);
+      values.remove(tag);
     } else {
-      Vector v = (Vector) values.elementAt(tag);
+      Vector v = (Vector) values.get(tag);
       v.removeElementAt(index);
     }
   }
@@ -477,12 +479,15 @@ public class ProtoBuf {
    * Returns the number of repeated and optional (0..1) values for a given tag.
    * Note: Default values are not counted (and in general not considered in 
    * access methods for repeated tags), but considered for has(tag). 
+   *
+   * @param tag the tag of the field
+   * @throws ArrayIndexOutOfBoundsException when tag is < 0
    */
   public int getCount(int tag) {
-    if (tag >= values.size()){
-      return 0;
+    if (tag < 0) {
+      throw new ArrayIndexOutOfBoundsException(tag);
     }
-    Object o = values.elementAt(tag);
+    Object o = values.get(tag);
     if (o == null){
       return 0;
     }
@@ -502,38 +507,69 @@ public class ProtoBuf {
       tagType = msgType.getType(tag);
     }
 
-    if (tagType == ProtoBufType.TYPE_UNDEFINED && tag < wireTypes.length()) {
-      tagType = wireTypes.charAt(tag);
+    if (tagType == ProtoBufType.TYPE_UNDEFINED) {
+      Integer tagTypeObj = (Integer) wireTypes.get(tag);
+      if (tagTypeObj != null) {
+        tagType = tagTypeObj.intValue();
+      }
     }
-    
+
     if (tagType == ProtoBufType.TYPE_UNDEFINED && getCount(tag) > 0) {
       Object o = getObject(tag, 0, ProtoBufType.TYPE_UNDEFINED);
-      
-      tagType = (o instanceof Long) || (o instanceof Boolean) 
+
+      tagType = (o instanceof Long) || (o instanceof Boolean)
         ? WIRETYPE_VARINT : WIRETYPE_LENGTH_DELIMITED;
     }
-    
+
     return tagType;
   }
-  
+
   /** 
    * Returns the number of bytes needed to store this protocol buffer 
    */
   public int getDataSize() {
+    return getCachedDataSize(false /* don't trust cache */);
+  }
+
+  /**
+   * Each Protobuf keeps track of a <code> cachedSize </code> that is
+   * used to short circuit evaluation of its children's sizes. This value
+   * should only be trusted if you are reasonably certain it cannot be
+   * corrupt. (A corrupt cache can happen if any child ProtoBuf of this
+   * ProtoBuf has had a value set. In general, it is best to only trust
+   * the cache if you have just finished cleansing it.)
+   *
+   * <P/>The cache can be cleansed by calling this method with
+   * trustCache = false.
+   *
+   * @param trustCache if the cached size should be trusted. Set false to
+   * recompuate the size.
+   */
+  private int getCachedDataSize(boolean trustCache) {
+    if (cachedSize != Integer.MIN_VALUE && trustCache) {
+      return cachedSize;
+    }
     int size = 0;
-    for (int tag = 0; tag <= maxTag(); tag++) {
+    IntMap.KeyIterator itr = values.keys();
+    while(itr.hasNext()) {
+      int tag = itr.next();
       for (int i = 0; i < getCount(tag); i++) {
-        size += getDataSize(tag, i);
+        size += getCachedDataSize(tag, i, trustCache);
       }
-    }      
-    return size;
+    }
+    cachedSize = size;
+
+    return cachedSize;
   }
-  
- 
-  /** 
-   * Returns the size of the given value 
+
+  /**
+   * Returns the size of the child.
+   *
+   * @param tag tag used to determine the type of this child
+   * @param i used to determine which count this child is
+   * @param trustSizeCache passed down to #getCachedDataSize()
    */
-  private int getDataSize(int tag, int i) {
+  private int getCachedDataSize(int tag, int i, boolean trustSizeCache) {
     int tagSize = getVarIntSize(tag << 3);
     
     switch(getWireType(tag)){
@@ -551,20 +587,20 @@ public class ProtoBuf {
         // take end group into account....
         return tagSize + getProtoBuf(tag, i).getDataSize() + tagSize;
     }
-    
+
     // take the object as stored
     Object o = getObject(tag, i, ProtoBufType.TYPE_UNDEFINED);
-    
+
     int contentSize;
-    
-    if (o instanceof byte[]){
+
+    if (o instanceof byte[]) {
       contentSize = ((byte[]) o).length;
     } else if (o instanceof String) {
       contentSize = encodeUtf8((String) o, null, 0);
     } else {
-      contentSize = ((ProtoBuf) o).getDataSize();
+      contentSize = ((ProtoBuf) o).getCachedDataSize(trustSizeCache);
     }
-    
+
     return tagSize + getVarIntSize(contentSize) + contentSize;
   }
 
@@ -584,67 +620,93 @@ public class ProtoBuf {
     return size;
   }
 
-  /** 
+  /**
    * Writes this and nested protocol buffers to the given output stream.
    * 
    * @param os target output stream
-   * @throws   IOException thrown if there is an IOException
+   * @throws IOException thrown if there is an IOException
    */
   public void outputTo(OutputStream os) throws IOException {
-    for (int tag = 0; tag <= maxTag(); tag++) {
-      int size = getCount(tag);
-      int wireType = getWireType(tag);
-      
-      // ignore default values
-      for (int i = 0; i < size; i++) {
-        writeVarInt(os, (tag << 3) | wireType);
-
-        switch (wireType) {
-          case WIRETYPE_FIXED32:
-          case WIRETYPE_FIXED64:
-            long v = ((Long) getObject(tag, i, ProtoBufType.TYPE_INT64))
-                .longValue();
-            int cnt = (wireType == WIRETYPE_FIXED32) ? 4 : 8;
-            for (int b = 0; b < cnt; b++) {
-              os.write((int) (v & 0x0ff));
-              v >>= 8;
-            }
-            break;
+    // We can't know what changed since we last output, so refresh the children.
+    getDataSize();
+    outputToInternal(os);
+  }
 
-          case WIRETYPE_VARINT:
-            v = ((Long) getObject(tag, i, ProtoBufType.TYPE_INT64)).longValue();
-            if (isZigZagEncodedType(tag)) {
-              v = zigZagEncode(v);
-            }
-            writeVarInt(os, v);
-            break;
-
-          case WIRETYPE_LENGTH_DELIMITED:
-            Object o = getObject(tag, i, 
-                getType(tag) == ProtoBufType.TYPE_MESSAGE 
-                ? ProtoBufType.TYPE_UNDEFINED
-                : ProtoBufType.TYPE_DATA);
-            
-            if (o instanceof byte[]){
-              byte[] data = (byte[]) o;
-              writeVarInt(os, data.length);
-              os.write(data);
-            } else {
-              ProtoBuf msg = (ProtoBuf) o;
-              writeVarInt(os, msg.getDataSize());
-              msg.outputTo(os);
-            }
-            break;
-
-          case WIRETYPE_START_GROUP:
-            ((ProtoBuf) getObject(tag, i, ProtoBufType.TYPE_GROUP))
-                .outputTo(os);
-            writeVarInt(os, (tag << 3) | WIRETYPE_END_GROUP);
-            break;
-            
-          default:
-            throw new IllegalArgumentException();
-        }
+  /**
+   * Recursive output method wrapped by #outputTo()
+   * 
+   * @param os target output stream
+   * @throws IOException thrown if there is an IOException
+   */
+  private void outputToInternal(OutputStream os) throws IOException {
+    IntMap.KeyIterator itr = values.keys();
+    while (itr.hasNext()) {
+      int tag = itr.next();
+      outputField(tag, os);
+    }
+  }
+
+  /**
+   * Output a field indicated by the tag to given stream.
+   *
+   * @param tag the tag of the field to output.
+   * @param os target output stream
+   * @throws IOException thrown if there is an IOException
+   */
+  private void outputField(int tag, OutputStream os) throws IOException {
+    int size = getCount(tag);
+    int wireType = getWireType(tag);
+    int wireTypeTag = (tag << 3) | wireType;
+
+    // ignore default values
+    for (int i = 0; i < size; i++) {
+      writeVarInt(os, wireTypeTag);
+      switch (wireType) {
+        case WIRETYPE_FIXED32:
+        case WIRETYPE_FIXED64:
+          long v = ((Long) getObject(tag, i, ProtoBufType.TYPE_INT64))
+              .longValue();
+          int cnt = (wireType == WIRETYPE_FIXED32) ? 4 : 8;
+          for (int b = 0; b < cnt; b++) {
+            os.write((int) (v & 0x0ff));
+            v >>= 8;
+          }
+          break;
+
+        case WIRETYPE_VARINT:
+          v = ((Long) getObject(tag, i, ProtoBufType.TYPE_INT64)).longValue();
+          if (isZigZagEncodedType(tag)) {
+            v = zigZagEncode(v);
+          }
+          writeVarInt(os, v);
+          break;
+
+        case WIRETYPE_LENGTH_DELIMITED:
+          Object o = getObject(tag, i,
+                               getType(tag) == ProtoBufType.TYPE_MESSAGE
+                               ? ProtoBufType.TYPE_UNDEFINED
+                               : ProtoBufType.TYPE_DATA);
+
+          if (o instanceof byte[]) {
+            byte[] data = (byte[]) o;
+            writeVarInt(os, data.length);
+            os.write(data);
+          } else {
+
+            ProtoBuf msg = (ProtoBuf) o;
+            writeVarInt(os, msg.getCachedDataSize(true));
+            msg.outputToInternal(os);
+          }
+          break;
+
+        case WIRETYPE_START_GROUP:
+          ((ProtoBuf) getObject(tag, i, ProtoBufType.TYPE_GROUP))
+              .outputToInternal(os);
+          writeVarInt(os, (tag << 3) | WIRETYPE_END_GROUP);
+          break;
+
+        default:
+          throw new IllegalArgumentException();
       }
     }
   }
@@ -693,12 +755,12 @@ public class ProtoBuf {
     outputTo(baos);
     return baos.toByteArray();
   }
-  
+
   /**
    * Returns the largest tag id used in this message (to simplify testing). 
    */
   public int maxTag() {
-    return values.size() - 1;
+    return values.maxKey();
   }
 
   /** 
@@ -726,8 +788,7 @@ public class ProtoBuf {
    * Sets the given tag to the given long value.
    */
   public void setLong(int tag, long value) {
-    setObject(tag, value >= 0 && value < SMALL_NUMBERS.length
-        ? SMALL_NUMBERS[(int) value] : new Long(value));
+    setObject(tag, value);
   }
 
   /**
@@ -795,8 +856,7 @@ public class ProtoBuf {
    * Inserts the given long value for the given tag at the given index. 
    */
   public void insertLong(int tag, int index, long value) {
-    insertObject(tag, index, value >= 0 && value < SMALL_NUMBERS.length
-        ? SMALL_NUMBERS[(int) value] : new Long(value));
+    insertObject(tag, index, value);
   }
 
   /**
@@ -879,8 +939,8 @@ public class ProtoBuf {
         case ProtoBufType.TYPE_GROUP:
         case ProtoBufType.TYPE_MESSAGE:
           if (msgType == null || msgType.getData(tag) == null ||
-              ((ProtoBuf) object).msgType == null || 
-              ((ProtoBuf) object).msgType == msgType.getData(tag)) {
+              ((ProtoBuf) object).msgType == null ||
+              ((ProtoBuf) object).msgType.equals(msgType.getData(tag))) {
             return;
           }
       }
@@ -944,7 +1004,7 @@ public class ProtoBuf {
       throw new ArrayIndexOutOfBoundsException();
     }
 
-    Object o = values.elementAt(tag);
+    Object o = values.get(tag);
     
     Vector v = null;
     if (o instanceof Vector) {
@@ -1025,14 +1085,14 @@ public class ProtoBuf {
     if (count == 0) {
       setObject(tag, o);
     } else {
-      Object curr = values.elementAt(tag);
+      Object curr = values.get(tag);
       Vector v;
       if (curr instanceof Vector) {
         v = (Vector) curr;
       } else {
         v = new Vector();
         v.addElement(curr);
-        values.setElementAt(v, tag);
+        values.put(tag, v);
       }
       v.insertElementAt(o, index);
     }
@@ -1042,7 +1102,7 @@ public class ProtoBuf {
    * Converts the object if a better suited class exists for the given .proto 
    * type. If the formats are not compatible, an exception is thrown.
    */
-  private Object convert(Object obj, int tagType) {
+  private static Object convert(Object obj, int tagType) {
     switch (tagType) {
       case ProtoBufType.TYPE_UNDEFINED:
         return obj;
@@ -1068,7 +1128,7 @@ public class ProtoBuf {
       case ProtoBufType.TYPE_SINT32:
       case ProtoBufType.TYPE_SINT64:
         if (obj instanceof Boolean) {
-          return SMALL_NUMBERS[((Boolean) obj).booleanValue() ? 1 : 0];
+          return ((Boolean) obj).booleanValue() ? 1 : 0;
         }
         return obj;
       case ProtoBufType.TYPE_DATA:
@@ -1153,13 +1213,13 @@ public class ProtoBuf {
    * values.
    */
   private void setObject(int tag, Object o) {
-    if (values.size() <= tag) {
-      values.setSize(tag + 1);
+    if (tag < 0) {
+      throw new ArrayIndexOutOfBoundsException();
     }
     if (o != null) {
       assertTypeMatch(tag, o);
     }
-    values.setElementAt(o, tag);
+    values.put(tag, o);
   }
 
   /** 
diff --git a/src/com/google/common/io/protocol/ProtoBufType.java b/src/com/google/common/io/protocol/ProtoBufType.java
index 4b6408e..728346f 100644
--- a/src/com/google/common/io/protocol/ProtoBufType.java
+++ b/src/com/google/common/io/protocol/ProtoBufType.java
@@ -6,9 +6,8 @@ package com.google.common.io.protocol;
 import java.util.*;
 
 /**
- * This class can be used to create a memory model of a .proto file. Currently, 
- * it is assumed that tags ids are not large. This could be improved by storing 
- * a start offset, relaxing the assumption to a dense number space.
+ * This class can be used to create a memory model of a .proto file.
+ * 
  */
 public class ProtoBufType {
   // Note: Values 0..15 are reserved for wire types!
@@ -42,11 +41,46 @@ public class ProtoBufType {
   public static final int REQUIRED = 0x100;
   public static final int OPTIONAL = 0x200;
   public static final int REPEATED = 0x400;
-  
-  private final StringBuffer types = new StringBuffer();
-  private final Vector data = new Vector();
+
+  private final IntMap types = new IntMap();
+
+  /*
+   * A struct to store field type and default object.
+   * Two TypeInfo objects are equal iff both have the
+   * euqal type and object.
+   */
+  static class TypeInfo {
+    private int type;
+    private Object data;
+    TypeInfo(int t, Object d) {
+      type = t;
+      data = d;
+    }
+
+    public int hashCode() {
+      return type;
+    }
+
+    public boolean equals(Object obj) {
+      if (this == obj) {
+        return true;
+      }
+      if (obj == null || !(obj instanceof TypeInfo)) {
+        return false;
+      }
+      TypeInfo peerTypeInfo = (TypeInfo) obj;
+      return  type == peerTypeInfo.type &&
+          (data == peerTypeInfo.data ||
+           (data != null && data.equals(peerTypeInfo.data)));
+    }
+
+    public String toString() {
+      return "TypeInfo{type=" + type + ", data=" + data + "}";
+    }
+  };
+
   private final String typeName;
-  
+
   /**
    * Empty constructor.
    */
@@ -74,35 +108,36 @@ public class ProtoBufType {
    * @return               this is returned to permit cascading
    */
   public ProtoBufType addElement(int optionsAndType, int tag, Object data) {
-    while (types.length() <= tag) {
-      types.append((char) TYPE_UNDEFINED);
-      this.data.addElement(null);
-    }
-    types.setCharAt(tag, (char) optionsAndType);
-    this.data.setElementAt(data, tag);
-
+    types.put(tag, new TypeInfo(optionsAndType, data));
     return this;
   }
-  
+
+  /**
+   * Returns a IntMap that has the same lower buffer size as types.
+   * This is for ProtoBuf to create IntMap with pre-allocated
+   * internal buffer.
+   */
+  /* package protected */ IntMap newIntMapForProtoBuf() {
+    return types.newIntMapWithSameBufferSize();
+  }
+
   /** 
    * Returns the type for the given tag id (without modifiers such as OPTIONAL,
    * REPEATED). For undefined tags, TYPE_UNDEFINED is returned.
    */  
   public int getType(int tag) {
-    return (tag < 0 || tag >= types.length()) 
-        ? TYPE_UNDEFINED
-        : (types.charAt(tag) & MASK_TYPE);
+    TypeInfo typeInfo = (TypeInfo) types.get(tag);
+    return typeInfo == null ? TYPE_UNDEFINED : typeInfo.type & MASK_TYPE;
   }
   
-  /** 
+  /**
    * Returns a bit combination of the modifiers for the given tag id 
    * (OPTIONAL, REPEATED, REQUIRED). For undefined tags, OPTIONAL|REPEATED
    * is returned.
-   */  
+   */
   public int getModifiers(int tag) {
-    return (tag < 0 || tag >= types.length()) 
-        ? (OPTIONAL | REPEATED)
-        : (types.charAt(tag) & MASK_MODIFIER);
+    TypeInfo typeInfo = (TypeInfo) types.get(tag);
+    return typeInfo == null ? (OPTIONAL | REPEATED) : typeInfo.type & MASK_MODIFIER;
   }
   
   /**
@@ -111,14 +146,15 @@ public class ProtoBufType {
    * tags, null is returned.
    */
   public Object getData(int tag) {
-    return (tag < 0 || tag >= data.size()) ? null : data.elementAt(tag);
+    TypeInfo typeInfo = (TypeInfo) types.get(tag);
+    return typeInfo == null ? typeInfo : typeInfo.data;
   }
   
   /**
    * Returns the type name set in the constructor for debugging purposes.
    */
   public String toString() {
-    return typeName;
+    return "ProtoBufType Name: " + typeName;
   }
   
   /**
@@ -138,9 +174,9 @@ public class ProtoBufType {
     }
     ProtoBufType other = (ProtoBufType) object;
 
-    return stringEquals(types, other.types);
+    return types.equals(other.types);
   }
-   
+
   /**
    * {@inheritDoc}
    */
@@ -151,20 +187,4 @@ public class ProtoBufType {
       return super.hashCode();
     }
   }
-
-  public static boolean stringEquals(CharSequence a, CharSequence b) {
-    if (a == b) return true;
-    int length;
-    if (a != null && b != null && (length = a.length()) == b.length()) {
-      if (a instanceof String && b instanceof String) {
-        return a.equals(b);
-      } else {
-        for (int i = 0; i < length; i++) {
-          if (a.charAt(i) != b.charAt(i)) return false;
-        }
-        return true;
-      }
-    }
-    return false;
-  }
 }
diff --git a/src/com/google/common/io/protocol/ProtoBufUtil.java b/src/com/google/common/io/protocol/ProtoBufUtil.java
index 72e1bca..b47e79c 100644
--- a/src/com/google/common/io/protocol/ProtoBufUtil.java
+++ b/src/com/google/common/io/protocol/ProtoBufUtil.java
@@ -22,6 +22,25 @@ public final class ProtoBufUtil {
     }
   }
 
+  /** Convenience method to return a string value from of a proto or null. */
+  public static String getProtoValueOrNull(ProtoBuf proto, int tag) {
+    try {
+      return (proto != null && proto.has(tag)) ? proto.getString(tag) : null;
+    } catch (ClassCastException e) {
+      return null;
+    }
+  }
+
+  /** Convenience method to return a string value from of a proto or null. */
+  public static String getProtoValueOrNull(ProtoBuf proto, int tag, int index) {
+    try {
+      return (proto != null && proto.has(tag) && proto.getCount(tag) > index) ?
+          proto.getString(tag, index) : null;
+    } catch (ClassCastException e) {
+      return null;
+    }
+  }
+
   /** Convenience method to return a string value from of a sub-proto or "". */
   public static String getSubProtoValueOrEmpty(
       ProtoBuf proto, int sub, int tag) {