Merge "Uses VMRuntime.newUnpaddedArray for ideal array sizes"

29 files changed, 415 insertions, 504 deletions

diff --git a/core/java/android/content/res/ColorStateList.java b/core/java/android/content/res/ColorStateList.java
index 419abf2..5674154 100644
--- a/core/java/android/content/res/ColorStateList.java
+++ b/core/java/android/content/res/ColorStateList.java
@@ -19,6 +19,7 @@ package android.content.res;
 import android.graphics.Color;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
 
 import org.xmlpull.v1.XmlPullParser;
 import org.xmlpull.v1.XmlPullParserException;
@@ -181,10 +182,9 @@ public class ColorStateList implements Parcelable {
         final int innerDepth = parser.getDepth()+1;
         int depth;
 
-        int listAllocated = 20;
+        int[][] stateSpecList = ArrayUtils.newUnpaddedArray(int[].class, 20);
+        int[] colorList = new int[stateSpecList.length];
         int listSize = 0;
-        int[] colorList = new int[listAllocated];
-        int[][] stateSpecList = new int[listAllocated][];
 
         while ((type=parser.next()) != XmlPullParser.END_DOCUMENT
                && ((depth=parser.getDepth()) >= innerDepth
@@ -248,21 +248,8 @@ public class ColorStateList implements Parcelable {
                 mDefaultColor = color;
             }
 
-            if (listSize + 1 >= listAllocated) {
-                listAllocated = ArrayUtils.idealIntArraySize(listSize + 1);
-
-                int[] ncolor = new int[listAllocated];
-                System.arraycopy(colorList, 0, ncolor, 0, listSize);
-
-                int[][] nstate = new int[listAllocated][];
-                System.arraycopy(stateSpecList, 0, nstate, 0, listSize);
-
-                colorList = ncolor;
-                stateSpecList = nstate;
-            }
-
-            colorList[listSize] = color;
-            stateSpecList[listSize] = stateSpec;
+            colorList = GrowingArrayUtils.append(colorList, listSize, color);
+            stateSpecList = GrowingArrayUtils.append(stateSpecList, listSize, stateSpec);
             listSize++;
         }
 
diff --git a/core/java/android/text/DynamicLayout.java b/core/java/android/text/DynamicLayout.java
index 06935ae..77ef1da 100644
--- a/core/java/android/text/DynamicLayout.java
+++ b/core/java/android/text/DynamicLayout.java
@@ -21,6 +21,7 @@ import android.text.style.UpdateLayout;
 import android.text.style.WrapTogetherSpan;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
 
 import java.lang.ref.WeakReference;
 
@@ -401,7 +402,7 @@ public class DynamicLayout extends Layout
 
         if (mBlockEndLines == null) {
             // Initial creation of the array, no test on previous block ending line
-            mBlockEndLines = new int[ArrayUtils.idealIntArraySize(1)];
+            mBlockEndLines = ArrayUtils.newUnpaddedIntArray(1);
             mBlockEndLines[mNumberOfBlocks] = line;
             mNumberOfBlocks++;
             return;
@@ -409,13 +410,7 @@ public class DynamicLayout extends Layout
 
         final int previousBlockEndLine = mBlockEndLines[mNumberOfBlocks - 1];
         if (line > previousBlockEndLine) {
-            if (mNumberOfBlocks == mBlockEndLines.length) {
-                // Grow the array if needed
-                int[] blockEndLines = new int[ArrayUtils.idealIntArraySize(mNumberOfBlocks + 1)];
-                System.arraycopy(mBlockEndLines, 0, blockEndLines, 0, mNumberOfBlocks);
-                mBlockEndLines = blockEndLines;
-            }
-            mBlockEndLines[mNumberOfBlocks] = line;
+            mBlockEndLines = GrowingArrayUtils.append(mBlockEndLines, mNumberOfBlocks, line);
             mNumberOfBlocks++;
         }
     }
@@ -483,9 +478,9 @@ public class DynamicLayout extends Layout
         }
 
         if (newNumberOfBlocks > mBlockEndLines.length) {
-            final int newSize = ArrayUtils.idealIntArraySize(newNumberOfBlocks);
-            int[] blockEndLines = new int[newSize];
-            int[] blockIndices = new int[newSize];
+            int[] blockEndLines = ArrayUtils.newUnpaddedIntArray(
+                    Math.max(mBlockEndLines.length * 2, newNumberOfBlocks));
+            int[] blockIndices = new int[blockEndLines.length];
             System.arraycopy(mBlockEndLines, 0, blockEndLines, 0, firstBlock);
             System.arraycopy(mBlockIndices, 0, blockIndices, 0, firstBlock);
             System.arraycopy(mBlockEndLines, lastBlock + 1,
diff --git a/core/java/android/text/Html.java b/core/java/android/text/Html.java
index c80321c..2fcc597 100644
--- a/core/java/android/text/Html.java
+++ b/core/java/android/text/Html.java
@@ -211,7 +211,7 @@ public class Html {
 
     private static String getOpenParaTagWithDirection(Spanned text, int start, int end) {
         final int len = end - start;
-        final byte[] levels = new byte[ArrayUtils.idealByteArraySize(len)];
+        final byte[] levels = ArrayUtils.newUnpaddedByteArray(len);
         final char[] buffer = TextUtils.obtain(len);
         TextUtils.getChars(text, start, end, buffer, 0);
 
diff --git a/core/java/android/text/Layout.java b/core/java/android/text/Layout.java
index 9dfd383..4bfcaff 100644
--- a/core/java/android/text/Layout.java
+++ b/core/java/android/text/Layout.java
@@ -31,6 +31,7 @@ import android.text.style.ReplacementSpan;
 import android.text.style.TabStopSpan;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
 
 import java.util.Arrays;
 
@@ -403,14 +404,9 @@ public abstract class Layout {
                                 // construction
                                 if (mLineBackgroundSpans.spanStarts[j] >= end ||
                                         mLineBackgroundSpans.spanEnds[j] <= start) continue;
-                                if (spansLength == spans.length) {
-                                    // The spans array needs to be expanded
-                                    int newSize = ArrayUtils.idealObjectArraySize(2 * spansLength);
-                                    ParagraphStyle[] newSpans = new ParagraphStyle[newSize];
-                                    System.arraycopy(spans, 0, newSpans, 0, spansLength);
-                                    spans = newSpans;
-                                }
-                                spans[spansLength++] = mLineBackgroundSpans.spans[j];
+                                spans = GrowingArrayUtils.append(
+                                        spans, spansLength, mLineBackgroundSpans.spans[j]);
+                                spansLength++;
                             }
                         }
                     }
diff --git a/core/java/android/text/MeasuredText.java b/core/java/android/text/MeasuredText.java
index 101d6a2..f8e3c83 100644
--- a/core/java/android/text/MeasuredText.java
+++ b/core/java/android/text/MeasuredText.java
@@ -98,10 +98,10 @@ class MeasuredText {
         mPos = 0;
 
         if (mWidths == null || mWidths.length < len) {
-            mWidths = new float[ArrayUtils.idealFloatArraySize(len)];
+            mWidths = ArrayUtils.newUnpaddedFloatArray(len);
         }
         if (mChars == null || mChars.length < len) {
-            mChars = new char[ArrayUtils.idealCharArraySize(len)];
+            mChars = ArrayUtils.newUnpaddedCharArray(len);
         }
         TextUtils.getChars(text, start, end, mChars, 0);
 
@@ -130,7 +130,7 @@ class MeasuredText {
             mEasy = true;
         } else {
             if (mLevels == null || mLevels.length < len) {
-                mLevels = new byte[ArrayUtils.idealByteArraySize(len)];
+                mLevels = ArrayUtils.newUnpaddedByteArray(len);
             }
             int bidiRequest;
             if (textDir == TextDirectionHeuristics.LTR) {
diff --git a/core/java/android/text/PackedIntVector.java b/core/java/android/text/PackedIntVector.java
index d87f600..546ab44 100644
--- a/core/java/android/text/PackedIntVector.java
+++ b/core/java/android/text/PackedIntVector.java
@@ -17,6 +17,7 @@
 package android.text;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
 
 
 /**
@@ -252,9 +253,9 @@ class PackedIntVector {
      */
     private final void growBuffer() {
         final int columns = mColumns;
-        int newsize = size() + 1;
-        newsize = ArrayUtils.idealIntArraySize(newsize * columns) / columns;
-        int[] newvalues = new int[newsize * columns];
+        int[] newvalues = ArrayUtils.newUnpaddedIntArray(
+                GrowingArrayUtils.growSize(size()) * columns);
+        int newsize = newvalues.length / columns;
 
         final int[] valuegap = mValueGap;
         final int rowgapstart = mRowGapStart;
diff --git a/core/java/android/text/PackedObjectVector.java b/core/java/android/text/PackedObjectVector.java
index a29df09..b777e16 100644
--- a/core/java/android/text/PackedObjectVector.java
+++ b/core/java/android/text/PackedObjectVector.java
@@ -17,6 +17,9 @@
 package android.text;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 class PackedObjectVector<E>
 {
@@ -32,12 +35,11 @@ class PackedObjectVector<E>
     PackedObjectVector(int columns)
     {
         mColumns = columns;
-        mRows = ArrayUtils.idealIntArraySize(0) / mColumns;
+        mValues = EmptyArray.OBJECT;
+        mRows = 0;
 
         mRowGapStart = 0;
         mRowGapLength = mRows;
-
-        mValues = new Object[mRows * mColumns];
     }
 
     public E
@@ -109,10 +111,9 @@ class PackedObjectVector<E>
     private void
     growBuffer()
     {
-        int newsize = size() + 1;
-        newsize = ArrayUtils.idealIntArraySize(newsize * mColumns) / mColumns;
-        Object[] newvalues = new Object[newsize * mColumns];
-
+        Object[] newvalues = ArrayUtils.newUnpaddedObjectArray(
+                GrowingArrayUtils.growSize(size()) * mColumns);
+        int newsize = newvalues.length / mColumns;
         int after = mRows - (mRowGapStart + mRowGapLength);
 
         System.arraycopy(mValues, 0, newvalues, 0, mColumns * mRowGapStart);
diff --git a/core/java/android/text/SpannableStringBuilder.java b/core/java/android/text/SpannableStringBuilder.java
index b55cd6a..f440853 100644
--- a/core/java/android/text/SpannableStringBuilder.java
+++ b/core/java/android/text/SpannableStringBuilder.java
@@ -21,6 +21,9 @@ import android.graphics.Paint;
 import android.util.Log;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 import java.lang.reflect.Array;
 
@@ -54,19 +57,17 @@ public class SpannableStringBuilder implements CharSequence, GetChars, Spannable
 
         if (srclen < 0) throw new StringIndexOutOfBoundsException();
 
-        int len = ArrayUtils.idealCharArraySize(srclen + 1);
-        mText = new char[len];
+        mText = ArrayUtils.newUnpaddedCharArray(GrowingArrayUtils.growSize(srclen));
         mGapStart = srclen;
-        mGapLength = len - srclen;
+        mGapLength = mText.length - srclen;
 
         TextUtils.getChars(text, start, end, mText, 0);
 
         mSpanCount = 0;
-        int alloc = ArrayUtils.idealIntArraySize(0);
-        mSpans = new Object[alloc];
-        mSpanStarts = new int[alloc];
-        mSpanEnds = new int[alloc];
-        mSpanFlags = new int[alloc];
+        mSpans = EmptyArray.OBJECT;
+        mSpanStarts = EmptyArray.INT;
+        mSpanEnds = EmptyArray.INT;
+        mSpanFlags = EmptyArray.INT;
 
         if (text instanceof Spanned) {
             Spanned sp = (Spanned) text;
@@ -130,12 +131,14 @@ public class SpannableStringBuilder implements CharSequence, GetChars, Spannable
 
     private void resizeFor(int size) {
         final int oldLength = mText.length;
-        final int newLength = ArrayUtils.idealCharArraySize(size + 1);
-        final int delta = newLength - oldLength;
-        if (delta == 0) return;
+        if (size + 1 <= oldLength) {
+            return;
+        }
 
-        char[] newText = new char[newLength];
+        char[] newText = ArrayUtils.newUnpaddedCharArray(GrowingArrayUtils.growSize(size));
         System.arraycopy(mText, 0, newText, 0, mGapStart);
+        final int newLength = newText.length;
+        final int delta = newLength - oldLength;
         final int after = oldLength - (mGapStart + mGapLength);
         System.arraycopy(mText, oldLength - after, newText, newLength - after, after);
         mText = newText;
@@ -679,28 +682,10 @@ public class SpannableStringBuilder implements CharSequence, GetChars, Spannable
             }
         }
 
-        if (mSpanCount + 1 >= mSpans.length) {
-            int newsize = ArrayUtils.idealIntArraySize(mSpanCount + 1);
-            Object[] newspans = new Object[newsize];
-            int[] newspanstarts = new int[newsize];
-            int[] newspanends = new int[newsize];
-            int[] newspanflags = new int[newsize];
-
-            System.arraycopy(mSpans, 0, newspans, 0, mSpanCount);
-            System.arraycopy(mSpanStarts, 0, newspanstarts, 0, mSpanCount);
-            System.arraycopy(mSpanEnds, 0, newspanends, 0, mSpanCount);
-            System.arraycopy(mSpanFlags, 0, newspanflags, 0, mSpanCount);
-
-            mSpans = newspans;
-            mSpanStarts = newspanstarts;
-            mSpanEnds = newspanends;
-            mSpanFlags = newspanflags;
-        }
-
-        mSpans[mSpanCount] = what;
-        mSpanStarts[mSpanCount] = start;
-        mSpanEnds[mSpanCount] = end;
-        mSpanFlags[mSpanCount] = flags;
+        mSpans = GrowingArrayUtils.append(mSpans, mSpanCount, what);
+        mSpanStarts = GrowingArrayUtils.append(mSpanStarts, mSpanCount, start);
+        mSpanEnds = GrowingArrayUtils.append(mSpanEnds, mSpanCount, end);
+        mSpanFlags = GrowingArrayUtils.append(mSpanFlags, mSpanCount, flags);
         mSpanCount++;
 
         if (send) sendSpanAdded(what, nstart, nend);
diff --git a/core/java/android/text/SpannableStringInternal.java b/core/java/android/text/SpannableStringInternal.java
index 456a3e5..d114d32 100644
--- a/core/java/android/text/SpannableStringInternal.java
+++ b/core/java/android/text/SpannableStringInternal.java
@@ -17,6 +17,9 @@
 package android.text;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 import java.lang.reflect.Array;
 
@@ -29,9 +32,8 @@ import java.lang.reflect.Array;
         else
             mText = source.toString().substring(start, end);
 
-        int initial = ArrayUtils.idealIntArraySize(0);
-        mSpans = new Object[initial];
-        mSpanData = new int[initial * 3];
+        mSpans = EmptyArray.OBJECT;
+        mSpanData = EmptyArray.INT;
 
         if (source instanceof Spanned) {
             Spanned sp = (Spanned) source;
@@ -115,9 +117,9 @@ import java.lang.reflect.Array;
         }
 
         if (mSpanCount + 1 >= mSpans.length) {
-            int newsize = ArrayUtils.idealIntArraySize(mSpanCount + 1);
-            Object[] newtags = new Object[newsize];
-            int[] newdata = new int[newsize * 3];
+            Object[] newtags = ArrayUtils.newUnpaddedObjectArray(
+                    GrowingArrayUtils.growSize(mSpanCount));
+            int[] newdata = new int[newtags.length * 3];
 
             System.arraycopy(mSpans, 0, newtags, 0, mSpanCount);
             System.arraycopy(mSpanData, 0, newdata, 0, mSpanCount * 3);
diff --git a/core/java/android/text/StaticLayout.java b/core/java/android/text/StaticLayout.java
index e7d6fda..535eee1 100644
--- a/core/java/android/text/StaticLayout.java
+++ b/core/java/android/text/StaticLayout.java
@@ -26,6 +26,7 @@ import android.text.style.TabStopSpan;
 import android.util.Log;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
 
 /**
  * StaticLayout is a Layout for text that will not be edited after it
@@ -130,9 +131,8 @@ public class StaticLayout extends Layout {
             mEllipsizedWidth = outerwidth;
         }
 
-        mLines = new int[ArrayUtils.idealIntArraySize(2 * mColumns)];
-        mLineDirections = new Directions[
-                             ArrayUtils.idealIntArraySize(2 * mColumns)];
+        mLineDirections = ArrayUtils.newUnpaddedArray(Directions.class, 2 * mColumns);
+        mLines = new int[mLineDirections.length];
         mMaximumVisibleLineCount = maxLines;
 
         mMeasured = MeasuredText.obtain();
@@ -149,8 +149,8 @@ public class StaticLayout extends Layout {
         super(text, null, 0, null, 0, 0);
 
         mColumns = COLUMNS_ELLIPSIZE;
-        mLines = new int[ArrayUtils.idealIntArraySize(2 * mColumns)];
-        mLineDirections = new Directions[ArrayUtils.idealIntArraySize(2 * mColumns)];
+        mLineDirections = ArrayUtils.newUnpaddedArray(Directions.class, 2 * mColumns);
+        mLines = new int[mLineDirections.length];
         // FIXME This is never recycled
         mMeasured = MeasuredText.obtain();
     }
@@ -215,8 +215,7 @@ public class StaticLayout extends Layout {
                 if (chooseHt.length != 0) {
                     if (chooseHtv == null ||
                         chooseHtv.length < chooseHt.length) {
-                        chooseHtv = new int[ArrayUtils.idealIntArraySize(
-                                            chooseHt.length)];
+                        chooseHtv = ArrayUtils.newUnpaddedIntArray(chooseHt.length);
                     }
 
                     for (int i = 0; i < chooseHt.length; i++) {
@@ -599,16 +598,16 @@ public class StaticLayout extends Layout {
         int[] lines = mLines;
 
         if (want >= lines.length) {
-            int nlen = ArrayUtils.idealIntArraySize(want + 1);
-            int[] grow = new int[nlen];
-            System.arraycopy(lines, 0, grow, 0, lines.length);
-            mLines = grow;
-            lines = grow;
-
-            Directions[] grow2 = new Directions[nlen];
+            Directions[] grow2 = ArrayUtils.newUnpaddedArray(
+                    Directions.class, GrowingArrayUtils.growSize(want));
             System.arraycopy(mLineDirections, 0, grow2, 0,
                              mLineDirections.length);
             mLineDirections = grow2;
+
+            int[] grow = new int[grow2.length];
+            System.arraycopy(lines, 0, grow, 0, lines.length);
+            mLines = grow;
+            lines = grow;
         }
 
         if (chooseHt != null) {
diff --git a/core/java/android/text/TextLine.java b/core/java/android/text/TextLine.java
index 1fecf81..d892f19 100644
--- a/core/java/android/text/TextLine.java
+++ b/core/java/android/text/TextLine.java
@@ -153,7 +153,7 @@ class TextLine {
 
         if (mCharsValid) {
             if (mChars == null || mChars.length < mLen) {
-                mChars = new char[ArrayUtils.idealCharArraySize(mLen)];
+                mChars = ArrayUtils.newUnpaddedCharArray(mLen);
             }
             TextUtils.getChars(text, start, limit, mChars, 0);
             if (hasReplacement) {
diff --git a/core/java/android/text/TextUtils.java b/core/java/android/text/TextUtils.java
index 596ca8c..f06ae71 100644
--- a/core/java/android/text/TextUtils.java
+++ b/core/java/android/text/TextUtils.java
@@ -1321,7 +1321,7 @@ public class TextUtils {
         }
 
         if (buf == null || buf.length < len)
-            buf = new char[ArrayUtils.idealCharArraySize(len)];
+            buf = ArrayUtils.newUnpaddedCharArray(len);
 
         return buf;
     }
diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java
index df1d4cd..9a0b7fc 100644
--- a/core/java/android/util/ArrayMap.java
+++ b/core/java/android/util/ArrayMap.java
@@ -16,6 +16,8 @@
 
 package android.util;
 
+import libcore.util.EmptyArray;
+
 import java.util.Collection;
 import java.util.Map;
 import java.util.Set;
@@ -234,8 +236,8 @@ public final class ArrayMap<K, V> implements Map<K, V> {
      * will grow once items are added to it.
      */
     public ArrayMap() {
-        mHashes = ContainerHelpers.EMPTY_INTS;
-        mArray = ContainerHelpers.EMPTY_OBJECTS;
+        mHashes = EmptyArray.INT;
+        mArray = EmptyArray.OBJECT;
         mSize = 0;
     }
 
@@ -244,8 +246,8 @@ public final class ArrayMap<K, V> implements Map<K, V> {
      */
     public ArrayMap(int capacity) {
         if (capacity == 0) {
-            mHashes = ContainerHelpers.EMPTY_INTS;
-            mArray = ContainerHelpers.EMPTY_OBJECTS;
+            mHashes = EmptyArray.INT;
+            mArray = EmptyArray.OBJECT;
         } else {
             allocArrays(capacity);
         }
@@ -253,8 +255,8 @@ public final class ArrayMap<K, V> implements Map<K, V> {
     }
 
     private ArrayMap(boolean immutable) {
-        mHashes = EMPTY_IMMUTABLE_INTS;
-        mArray = ContainerHelpers.EMPTY_OBJECTS;
+        mHashes = EmptyArray.INT;
+        mArray = EmptyArray.OBJECT;
         mSize = 0;
     }
 
@@ -275,8 +277,8 @@ public final class ArrayMap<K, V> implements Map<K, V> {
     public void clear() {
         if (mSize > 0) {
             freeArrays(mHashes, mArray, mSize);
-            mHashes = ContainerHelpers.EMPTY_INTS;
-            mArray = ContainerHelpers.EMPTY_OBJECTS;
+            mHashes = EmptyArray.INT;
+            mArray = EmptyArray.OBJECT;
             mSize = 0;
         }
     }
@@ -540,8 +542,8 @@ public final class ArrayMap<K, V> implements Map<K, V> {
             // Now empty.
             if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
             freeArrays(mHashes, mArray, mSize);
-            mHashes = ContainerHelpers.EMPTY_INTS;
-            mArray = ContainerHelpers.EMPTY_OBJECTS;
+            mHashes = EmptyArray.INT;
+            mArray = EmptyArray.OBJECT;
             mSize = 0;
         } else {
             if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java
index 3c695e9..9d4b720 100644
--- a/core/java/android/util/ArraySet.java
+++ b/core/java/android/util/ArraySet.java
@@ -16,6 +16,8 @@
 
 package android.util;
 
+import libcore.util.EmptyArray;
+
 import java.lang.reflect.Array;
 import java.util.Collection;
 import java.util.Iterator;
@@ -222,8 +224,8 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
      * will grow once items are added to it.
      */
     public ArraySet() {
-        mHashes = ContainerHelpers.EMPTY_INTS;
-        mArray = ContainerHelpers.EMPTY_OBJECTS;
+        mHashes = EmptyArray.INT;
+        mArray = EmptyArray.OBJECT;
         mSize = 0;
     }
 
@@ -232,8 +234,8 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
      */
     public ArraySet(int capacity) {
         if (capacity == 0) {
-            mHashes = ContainerHelpers.EMPTY_INTS;
-            mArray = ContainerHelpers.EMPTY_OBJECTS;
+            mHashes = EmptyArray.INT;
+            mArray = EmptyArray.OBJECT;
         } else {
             allocArrays(capacity);
         }
@@ -258,8 +260,8 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
     public void clear() {
         if (mSize != 0) {
             freeArrays(mHashes, mArray, mSize);
-            mHashes = ContainerHelpers.EMPTY_INTS;
-            mArray = ContainerHelpers.EMPTY_OBJECTS;
+            mHashes = EmptyArray.INT;
+            mArray = EmptyArray.OBJECT;
             mSize = 0;
         }
     }
@@ -413,8 +415,8 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
             // Now empty.
             if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
             freeArrays(mHashes, mArray, mSize);
-            mHashes = ContainerHelpers.EMPTY_INTS;
-            mArray = ContainerHelpers.EMPTY_OBJECTS;
+            mHashes = EmptyArray.INT;
+            mArray = EmptyArray.OBJECT;
             mSize = 0;
         } else {
             if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
diff --git a/core/java/android/util/ContainerHelpers.java b/core/java/android/util/ContainerHelpers.java
index 624c4bd..4e5fefb 100644
--- a/core/java/android/util/ContainerHelpers.java
+++ b/core/java/android/util/ContainerHelpers.java
@@ -17,10 +17,6 @@
 package android.util;
 
 class ContainerHelpers {
-    static final boolean[] EMPTY_BOOLEANS = new boolean[0];
-    static final int[] EMPTY_INTS = new int[0];
-    static final long[] EMPTY_LONGS = new long[0];
-    static final Object[] EMPTY_OBJECTS = new Object[0];
 
     // This is Arrays.binarySearch(), but doesn't do any argument validation.
     static int binarySearch(int[] array, int size, int value) {
diff --git a/core/java/android/util/LongArray.java b/core/java/android/util/LongArray.java
index d5f15f0..54a6882 100644
--- a/core/java/android/util/LongArray.java
+++ b/core/java/android/util/LongArray.java
@@ -17,6 +17,7 @@
 package android.util;
 
 import com.android.internal.util.ArrayUtils;
+import libcore.util.EmptyArray;
 
 /**
  * Implements a growing array of long primitives.
@@ -41,10 +42,9 @@ public class LongArray implements Cloneable {
      */
     public LongArray(int initialCapacity) {
         if (initialCapacity == 0) {
-            mValues = ContainerHelpers.EMPTY_LONGS;
+            mValues = EmptyArray.LONG;
         } else {
-            initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
-            mValues = new long[initialCapacity];
+            mValues = ArrayUtils.newUnpaddedLongArray(initialCapacity);
         }
         mSize = 0;
     }
@@ -97,7 +97,7 @@ public class LongArray implements Cloneable {
             final int targetCap = currentSize + (currentSize < (MIN_CAPACITY_INCREMENT / 2) ?
                     MIN_CAPACITY_INCREMENT : currentSize >> 1);
             final int newCapacity = targetCap > minCapacity ? targetCap : minCapacity;
-            final long[] newValues = new long[ArrayUtils.idealLongArraySize(newCapacity)];
+            final long[] newValues = ArrayUtils.newUnpaddedLongArray(newCapacity);
             System.arraycopy(mValues, 0, newValues, 0, currentSize);
             mValues = newValues;
         }
diff --git a/core/java/android/util/LongSparseArray.java b/core/java/android/util/LongSparseArray.java
index dab853a..6b45ff4 100644
--- a/core/java/android/util/LongSparseArray.java
+++ b/core/java/android/util/LongSparseArray.java
@@ -17,6 +17,9 @@
 package android.util;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 /**
  * SparseArray mapping longs to Objects.  Unlike a normal array of Objects,
@@ -70,12 +73,11 @@ public class LongSparseArray<E> implements Cloneable {
      */
     public LongSparseArray(int initialCapacity) {
         if (initialCapacity == 0) {
-            mKeys = ContainerHelpers.EMPTY_LONGS;
-            mValues = ContainerHelpers.EMPTY_OBJECTS;
+            mKeys = EmptyArray.LONG;
+            mValues = EmptyArray.OBJECT;
         } else {
-            initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
-            mKeys = new long[initialCapacity];
-            mValues = new Object[initialCapacity];
+            mKeys = ArrayUtils.newUnpaddedLongArray(initialCapacity);
+            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
         }
         mSize = 0;
     }
@@ -202,28 +204,8 @@ public class LongSparseArray<E> implements Cloneable {
                 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
             }
 
-            if (mSize >= mKeys.length) {
-                int n = ArrayUtils.idealLongArraySize(mSize + 1);
-
-                long[] nkeys = new long[n];
-                Object[] nvalues = new Object[n];
-
-                // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
-                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-                mKeys = nkeys;
-                mValues = nvalues;
-            }
-
-            if (mSize - i != 0) {
-                // Log.e("SparseArray", "move " + (mSize - i));
-                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
-                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
-            }
-
-            mKeys[i] = key;
-            mValues[i] = value;
+            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
+            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
             mSize++;
         }
     }
@@ -353,24 +335,9 @@ public class LongSparseArray<E> implements Cloneable {
             gc();
         }
 
-        int pos = mSize;
-        if (pos >= mKeys.length) {
-            int n = ArrayUtils.idealLongArraySize(pos + 1);
-
-            long[] nkeys = new long[n];
-            Object[] nvalues = new Object[n];
-
-            // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
-            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-            mKeys = nkeys;
-            mValues = nvalues;
-        }
-
-        mKeys[pos] = key;
-        mValues[pos] = value;
-        mSize = pos + 1;
+        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
+        mValues = GrowingArrayUtils.append(mValues, mSize, value);
+        mSize++;
     }
 
     /**
diff --git a/core/java/android/util/LongSparseLongArray.java b/core/java/android/util/LongSparseLongArray.java
index b8073dd..a361457 100644
--- a/core/java/android/util/LongSparseLongArray.java
+++ b/core/java/android/util/LongSparseLongArray.java
@@ -17,6 +17,9 @@
 package android.util;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 /**
  * Map of {@code long} to {@code long}. Unlike a normal array of longs, there
@@ -62,12 +65,11 @@ public class LongSparseLongArray implements Cloneable {
      */
     public LongSparseLongArray(int initialCapacity) {
         if (initialCapacity == 0) {
-            mKeys = ContainerHelpers.EMPTY_LONGS;
-            mValues = ContainerHelpers.EMPTY_LONGS;
+            mKeys = EmptyArray.LONG;
+            mValues = EmptyArray.LONG;
         } else {
-            initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
-            mKeys = new long[initialCapacity];
-            mValues = new long[initialCapacity];
+            mKeys = ArrayUtils.newUnpaddedLongArray(initialCapacity);
+            mValues = new long[mKeys.length];
         }
         mSize = 0;
     }
@@ -140,17 +142,8 @@ public class LongSparseLongArray implements Cloneable {
         } else {
             i = ~i;
 
-            if (mSize >= mKeys.length) {
-                growKeyAndValueArrays(mSize + 1);
-            }
-
-            if (mSize - i != 0) {
-                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
-                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
-            }
-
-            mKeys[i] = key;
-            mValues[i] = value;
+            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
+            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
             mSize++;
         }
     }
@@ -234,27 +227,9 @@ public class LongSparseLongArray implements Cloneable {
             return;
         }
 
-        int pos = mSize;
-        if (pos >= mKeys.length) {
-            growKeyAndValueArrays(pos + 1);
-        }
-
-        mKeys[pos] = key;
-        mValues[pos] = value;
-        mSize = pos + 1;
-    }
-
-    private void growKeyAndValueArrays(int minNeededSize) {
-        int n = ArrayUtils.idealLongArraySize(minNeededSize);
-
-        long[] nkeys = new long[n];
-        long[] nvalues = new long[n];
-
-        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-        mKeys = nkeys;
-        mValues = nvalues;
+        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
+        mValues = GrowingArrayUtils.append(mValues, mSize, value);
+        mSize++;
     }
 
     /**
diff --git a/core/java/android/util/SparseArray.java b/core/java/android/util/SparseArray.java
index 46d9d45..92e874f 100644
--- a/core/java/android/util/SparseArray.java
+++ b/core/java/android/util/SparseArray.java
@@ -17,6 +17,9 @@
 package android.util;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 /**
  * SparseArrays map integers to Objects.  Unlike a normal array of Objects,
@@ -70,12 +73,11 @@ public class SparseArray<E> implements Cloneable {
      */
     public SparseArray(int initialCapacity) {
         if (initialCapacity == 0) {
-            mKeys = ContainerHelpers.EMPTY_INTS;
-            mValues = ContainerHelpers.EMPTY_OBJECTS;
+            mKeys = EmptyArray.INT;
+            mValues = EmptyArray.OBJECT;
         } else {
-            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
-            mKeys = new int[initialCapacity];
-            mValues = new Object[initialCapacity];
+            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
+            mKeys = new int[mValues.length];
         }
         mSize = 0;
     }
@@ -215,28 +217,8 @@ public class SparseArray<E> implements Cloneable {
                 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
             }
 
-            if (mSize >= mKeys.length) {
-                int n = ArrayUtils.idealIntArraySize(mSize + 1);
-
-                int[] nkeys = new int[n];
-                Object[] nvalues = new Object[n];
-
-                // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
-                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-                mKeys = nkeys;
-                mValues = nvalues;
-            }
-
-            if (mSize - i != 0) {
-                // Log.e("SparseArray", "move " + (mSize - i));
-                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
-                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
-            }
-
-            mKeys[i] = key;
-            mValues[i] = value;
+            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
+            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
             mSize++;
         }
     }
@@ -368,24 +350,9 @@ public class SparseArray<E> implements Cloneable {
             gc();
         }
 
-        int pos = mSize;
-        if (pos >= mKeys.length) {
-            int n = ArrayUtils.idealIntArraySize(pos + 1);
-
-            int[] nkeys = new int[n];
-            Object[] nvalues = new Object[n];
-
-            // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
-            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-            mKeys = nkeys;
-            mValues = nvalues;
-        }
-
-        mKeys[pos] = key;
-        mValues[pos] = value;
-        mSize = pos + 1;
+        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
+        mValues = GrowingArrayUtils.append(mValues, mSize, value);
+        mSize++;
     }
 
     /**
diff --git a/core/java/android/util/SparseBooleanArray.java b/core/java/android/util/SparseBooleanArray.java
index f59ef0f6d..e293b1f 100644
--- a/core/java/android/util/SparseBooleanArray.java
+++ b/core/java/android/util/SparseBooleanArray.java
@@ -17,6 +17,9 @@
 package android.util;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 /**
  * SparseBooleanArrays map integers to booleans.
@@ -57,12 +60,11 @@ public class SparseBooleanArray implements Cloneable {
      */
     public SparseBooleanArray(int initialCapacity) {
         if (initialCapacity == 0) {
-            mKeys = ContainerHelpers.EMPTY_INTS;
-            mValues = ContainerHelpers.EMPTY_BOOLEANS;
+            mKeys = EmptyArray.INT;
+            mValues = EmptyArray.BOOLEAN;
         } else {
-            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
-            mKeys = new int[initialCapacity];
-            mValues = new boolean[initialCapacity];
+            mKeys = ArrayUtils.newUnpaddedIntArray(initialCapacity);
+            mValues = new boolean[mKeys.length];
         }
         mSize = 0;
     }
@@ -135,28 +137,8 @@ public class SparseBooleanArray implements Cloneable {
         } else {
             i = ~i;
 
-            if (mSize >= mKeys.length) {
-                int n = ArrayUtils.idealIntArraySize(mSize + 1);
-
-                int[] nkeys = new int[n];
-                boolean[] nvalues = new boolean[n];
-
-                // Log.e("SparseBooleanArray", "grow " + mKeys.length + " to " + n);
-                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-                mKeys = nkeys;
-                mValues = nvalues;
-            }
-
-            if (mSize - i != 0) {
-                // Log.e("SparseBooleanArray", "move " + (mSize - i));
-                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
-                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
-            }
-
-            mKeys[i] = key;
-            mValues[i] = value;
+            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
+            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
             mSize++;
         }
     }
@@ -245,24 +227,9 @@ public class SparseBooleanArray implements Cloneable {
             return;
         }
 
-        int pos = mSize;
-        if (pos >= mKeys.length) {
-            int n = ArrayUtils.idealIntArraySize(pos + 1);
-
-            int[] nkeys = new int[n];
-            boolean[] nvalues = new boolean[n];
-
-            // Log.e("SparseBooleanArray", "grow " + mKeys.length + " to " + n);
-            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-            mKeys = nkeys;
-            mValues = nvalues;
-        }
-
-        mKeys[pos] = key;
-        mValues[pos] = value;
-        mSize = pos + 1;
+        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
+        mValues = GrowingArrayUtils.append(mValues, mSize, value);
+        mSize++;
     }
 
     /**
diff --git a/core/java/android/util/SparseIntArray.java b/core/java/android/util/SparseIntArray.java
index 4f5ca07..2b85a21 100644
--- a/core/java/android/util/SparseIntArray.java
+++ b/core/java/android/util/SparseIntArray.java
@@ -17,6 +17,9 @@
 package android.util;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 /**
  * SparseIntArrays map integers to integers.  Unlike a normal array of integers,
@@ -60,12 +63,11 @@ public class SparseIntArray implements Cloneable {
      */
     public SparseIntArray(int initialCapacity) {
         if (initialCapacity == 0) {
-            mKeys = ContainerHelpers.EMPTY_INTS;
-            mValues = ContainerHelpers.EMPTY_INTS;
+            mKeys = EmptyArray.INT;
+            mValues = EmptyArray.INT;
         } else {
-            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
-            mKeys = new int[initialCapacity];
-            mValues = new int[initialCapacity];
+            mKeys = ArrayUtils.newUnpaddedIntArray(initialCapacity);
+            mValues = new int[mKeys.length];
         }
         mSize = 0;
     }
@@ -138,28 +140,8 @@ public class SparseIntArray implements Cloneable {
         } else {
             i = ~i;
 
-            if (mSize >= mKeys.length) {
-                int n = ArrayUtils.idealIntArraySize(mSize + 1);
-
-                int[] nkeys = new int[n];
-                int[] nvalues = new int[n];
-
-                // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n);
-                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-                mKeys = nkeys;
-                mValues = nvalues;
-            }
-
-            if (mSize - i != 0) {
-                // Log.e("SparseIntArray", "move " + (mSize - i));
-                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
-                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
-            }
-
-            mKeys[i] = key;
-            mValues[i] = value;
+            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
+            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
             mSize++;
         }
     }
@@ -243,24 +225,9 @@ public class SparseIntArray implements Cloneable {
             return;
         }
 
-        int pos = mSize;
-        if (pos >= mKeys.length) {
-            int n = ArrayUtils.idealIntArraySize(pos + 1);
-
-            int[] nkeys = new int[n];
-            int[] nvalues = new int[n];
-
-            // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n);
-            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-            mKeys = nkeys;
-            mValues = nvalues;
-        }
-
-        mKeys[pos] = key;
-        mValues[pos] = value;
-        mSize = pos + 1;
+        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
+        mValues = GrowingArrayUtils.append(mValues, mSize, value);
+        mSize++;
     }
 
     /**
diff --git a/core/java/android/util/SparseLongArray.java b/core/java/android/util/SparseLongArray.java
index 39fc8a3..0166c4a 100644
--- a/core/java/android/util/SparseLongArray.java
+++ b/core/java/android/util/SparseLongArray.java
@@ -17,6 +17,9 @@
 package android.util;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
+
+import libcore.util.EmptyArray;
 
 /**
  * SparseLongArrays map integers to longs.  Unlike a normal array of longs,
@@ -60,12 +63,11 @@ public class SparseLongArray implements Cloneable {
      */
     public SparseLongArray(int initialCapacity) {
         if (initialCapacity == 0) {
-            mKeys = ContainerHelpers.EMPTY_INTS;
-            mValues = ContainerHelpers.EMPTY_LONGS;
+            mKeys = EmptyArray.INT;
+            mValues = EmptyArray.LONG;
         } else {
-            initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
-            mKeys = new int[initialCapacity];
-            mValues = new long[initialCapacity];
+            mValues = ArrayUtils.newUnpaddedLongArray(initialCapacity);
+            mKeys = new int[mValues.length];
         }
         mSize = 0;
     }
@@ -138,17 +140,8 @@ public class SparseLongArray implements Cloneable {
         } else {
             i = ~i;
 
-            if (mSize >= mKeys.length) {
-                growKeyAndValueArrays(mSize + 1);
-            }
-
-            if (mSize - i != 0) {
-                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
-                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
-            }
-
-            mKeys[i] = key;
-            mValues[i] = value;
+            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
+            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
             mSize++;
         }
     }
@@ -232,27 +225,9 @@ public class SparseLongArray implements Cloneable {
             return;
         }
 
-        int pos = mSize;
-        if (pos >= mKeys.length) {
-            growKeyAndValueArrays(pos + 1);
-        }
-
-        mKeys[pos] = key;
-        mValues[pos] = value;
-        mSize = pos + 1;
-    }
-
-    private void growKeyAndValueArrays(int minNeededSize) {
-        int n = ArrayUtils.idealLongArraySize(minNeededSize);
-
-        int[] nkeys = new int[n];
-        long[] nvalues = new long[n];
-
-        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-        mKeys = nkeys;
-        mValues = nvalues;
+        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
+        mValues = GrowingArrayUtils.append(mValues, mSize, value);
+        mSize++;
     }
 
     /**
diff --git a/core/java/android/widget/Editor.java b/core/java/android/widget/Editor.java
index 333e631..14e7951 100644
--- a/core/java/android/widget/Editor.java
+++ b/core/java/android/widget/Editor.java
@@ -25,6 +25,7 @@ import android.text.InputFilter;
 import android.text.SpannableString;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
 import com.android.internal.widget.EditableInputConnection;
 
 import android.R;
@@ -1341,7 +1342,7 @@ public class Editor {
 
         if (layout instanceof DynamicLayout) {
             if (mTextDisplayLists == null) {
-                mTextDisplayLists = new TextDisplayList[ArrayUtils.idealObjectArraySize(0)];
+                mTextDisplayLists = ArrayUtils.emptyArray(TextDisplayList.class);
             }
 
             DynamicLayout dynamicLayout = (DynamicLayout) layout;
@@ -1441,10 +1442,7 @@ public class Editor {
         }
 
         // No available index found, the pool has to grow
-        int newSize = ArrayUtils.idealIntArraySize(length + 1);
-        TextDisplayList[] displayLists = new TextDisplayList[newSize];
-        System.arraycopy(mTextDisplayLists, 0, displayLists, 0, length);
-        mTextDisplayLists = displayLists;
+        mTextDisplayLists = GrowingArrayUtils.append(mTextDisplayLists, length, null);
         return length;
     }
 
diff --git a/core/java/android/widget/SpellChecker.java b/core/java/android/widget/SpellChecker.java
index 1cda631..595f023 100644
--- a/core/java/android/widget/SpellChecker.java
+++ b/core/java/android/widget/SpellChecker.java
@@ -35,6 +35,7 @@ import android.view.textservice.TextInfo;
 import android.view.textservice.TextServicesManager;
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
 
 import java.text.BreakIterator;
 import java.util.Locale;
@@ -105,9 +106,9 @@ public class SpellChecker implements SpellCheckerSessionListener {
         mTextView = textView;
 
         // Arbitrary: these arrays will automatically double their sizes on demand
-        final int size = ArrayUtils.idealObjectArraySize(1);
-        mIds = new int[size];
-        mSpellCheckSpans = new SpellCheckSpan[size];
+        final int size = 1;
+        mIds = ArrayUtils.newUnpaddedIntArray(size);
+        mSpellCheckSpans = new SpellCheckSpan[mIds.length];
 
         setLocale(mTextView.getSpellCheckerLocale());
 
@@ -184,17 +185,9 @@ public class SpellChecker implements SpellCheckerSessionListener {
             if (mIds[i] < 0) return i;
         }
 
-        if (mLength == mSpellCheckSpans.length) {
-            final int newSize = mLength * 2;
-            int[] newIds = new int[newSize];
-            SpellCheckSpan[] newSpellCheckSpans = new SpellCheckSpan[newSize];
-            System.arraycopy(mIds, 0, newIds, 0, mLength);
-            System.arraycopy(mSpellCheckSpans, 0, newSpellCheckSpans, 0, mLength);
-            mIds = newIds;
-            mSpellCheckSpans = newSpellCheckSpans;
-        }
-
-        mSpellCheckSpans[mLength] = new SpellCheckSpan();
+        mIds = GrowingArrayUtils.append(mIds, mLength, 0);
+        mSpellCheckSpans = GrowingArrayUtils.append(
+                mSpellCheckSpans, mLength, new SpellCheckSpan());
         mLength++;
         return mLength - 1;
     }
diff --git a/core/java/com/android/internal/app/ProcessStats.java b/core/java/com/android/internal/app/ProcessStats.java
index b1535e3..882bec9 100644
--- a/core/java/com/android/internal/app/ProcessStats.java
+++ b/core/java/com/android/internal/app/ProcessStats.java
@@ -29,8 +29,11 @@ import android.util.Slog;
 import android.util.SparseArray;
 import android.util.TimeUtils;
 import android.webkit.WebViewFactory;
-import com.android.internal.util.ArrayUtils;
+
+import com.android.internal.util.GrowingArrayUtils;
+
 import dalvik.system.VMRuntime;
+import libcore.util.EmptyArray;
 
 import java.io.IOException;
 import java.io.InputStream;
@@ -1621,21 +1624,10 @@ public final class ProcessStats implements Parcelable {
     }
 
     int addLongData(int index, int type, int num) {
-        int tableLen = mAddLongTable != null ? mAddLongTable.length : 0;
-        if (mAddLongTableSize >= tableLen) {
-            int newSize = ArrayUtils.idealIntArraySize(tableLen + 1);
-            int[] newTable = new int[newSize];
-            if (tableLen > 0) {
-                System.arraycopy(mAddLongTable, 0, newTable, 0, tableLen);
-            }
-            mAddLongTable = newTable;
-        }
-        if (mAddLongTableSize > 0 && mAddLongTableSize - index != 0) {
-            System.arraycopy(mAddLongTable, index, mAddLongTable, index + 1,
-                    mAddLongTableSize - index);
-        }
         int off = allocLongData(num);
-        mAddLongTable[index] = type | off;
+        mAddLongTable = GrowingArrayUtils.insert(
+                mAddLongTable != null ? mAddLongTable : EmptyArray.INT,
+                mAddLongTableSize, index, type | off);
         mAddLongTableSize++;
         return off;
     }
diff --git a/core/java/com/android/internal/util/ArrayUtils.java b/core/java/com/android/internal/util/ArrayUtils.java
index 9137d3c..d177410 100644
--- a/core/java/com/android/internal/util/ArrayUtils.java
+++ b/core/java/com/android/internal/util/ArrayUtils.java
@@ -16,11 +16,10 @@
 
 package com.android.internal.util;
 
-import java.lang.reflect.Array;
+import dalvik.system.VMRuntime;
+import libcore.util.EmptyArray;
 
-// XXX these should be changed to reflect the actual memory allocator we use.
-// it looks like right now objects want to be powers of 2 minus 8
-// and the array size eats another 4 bytes
+import java.lang.reflect.Array;
 
 /**
  * ArrayUtils contains some methods that you can call to find out
@@ -28,46 +27,42 @@ import java.lang.reflect.Array;
  */
 public class ArrayUtils
 {
-    private static Object[] EMPTY = new Object[0];
     private static final int CACHE_SIZE = 73;
     private static Object[] sCache = new Object[CACHE_SIZE];
 
     private ArrayUtils() { /* cannot be instantiated */ }
 
-    public static int idealByteArraySize(int need) {
-        for (int i = 4; i < 32; i++)
-            if (need <= (1 << i) - 12)
-                return (1 << i) - 12;
-
-        return need;
+    public static byte[] newUnpaddedByteArray(int minLen) {
+        return (byte[])VMRuntime.getRuntime().newUnpaddedArray(byte.class, minLen);
     }
 
-    public static int idealBooleanArraySize(int need) {
-        return idealByteArraySize(need);
+    public static char[] newUnpaddedCharArray(int minLen) {
+        return (char[])VMRuntime.getRuntime().newUnpaddedArray(char.class, minLen);
     }
 
-    public static int idealShortArraySize(int need) {
-        return idealByteArraySize(need * 2) / 2;
+    public static int[] newUnpaddedIntArray(int minLen) {
+        return (int[])VMRuntime.getRuntime().newUnpaddedArray(int.class, minLen);
     }
 
-    public static int idealCharArraySize(int need) {
-        return idealByteArraySize(need * 2) / 2;
+    public static boolean[] newUnpaddedBooleanArray(int minLen) {
+        return (boolean[])VMRuntime.getRuntime().newUnpaddedArray(boolean.class, minLen);
     }
 
-    public static int idealIntArraySize(int need) {
-        return idealByteArraySize(need * 4) / 4;
+    public static long[] newUnpaddedLongArray(int minLen) {
+        return (long[])VMRuntime.getRuntime().newUnpaddedArray(long.class, minLen);
     }
 
-    public static int idealFloatArraySize(int need) {
-        return idealByteArraySize(need * 4) / 4;
+    public static float[] newUnpaddedFloatArray(int minLen) {
+        return (float[])VMRuntime.getRuntime().newUnpaddedArray(float.class, minLen);
     }
 
-    public static int idealObjectArraySize(int need) {
-        return idealByteArraySize(need * 4) / 4;
+    public static Object[] newUnpaddedObjectArray(int minLen) {
+        return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen);
     }
 
-    public static int idealLongArraySize(int need) {
-        return idealByteArraySize(need * 8) / 8;
+    @SuppressWarnings("unchecked")
+    public static <T> T[] newUnpaddedArray(Class<T> clazz, int minLen) {
+        return (T[])VMRuntime.getRuntime().newUnpaddedArray(clazz, minLen);
     }
 
     /**
@@ -102,9 +97,10 @@ public class ArrayUtils
      * it will return the same empty array every time to avoid reallocation,
      * although this is not guaranteed.
      */
+    @SuppressWarnings("unchecked")
     public static <T> T[] emptyArray(Class<T> kind) {
         if (kind == Object.class) {
-            return (T[]) EMPTY;
+            return (T[]) EmptyArray.OBJECT;
         }
 
         int bucket = ((System.identityHashCode(kind) / 8) & 0x7FFFFFFF) % CACHE_SIZE;
diff --git a/core/java/com/android/internal/util/GrowingArrayUtils.java b/core/java/com/android/internal/util/GrowingArrayUtils.java
new file mode 100644
index 0000000..b4d2d730
--- /dev/null
+++ b/core/java/com/android/internal/util/GrowingArrayUtils.java
@@ -0,0 +1,196 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.internal.util;
+
+/**
+ * A helper class that aims to provide comparable growth performance to ArrayList, but on primitive
+ * arrays. Common array operations are implemented for efficient use in dynamic containers.
+ *
+ * All methods in this class assume that the length of an array is equivalent to its capacity and
+ * NOT the number of elements in the array. The current size of the array is always passed in as a
+ * parameter.
+ *
+ * @hide
+ */
+public final class GrowingArrayUtils {
+
+    /**
+     * Appends an element to the end of the array, growing the array if there is no more room.
+     * @param array The array to which to append the element. This must NOT be null.
+     * @param currentSize The number of elements in the array. Must be less than or equal to
+     *                    array.length.
+     * @param element The element to append.
+     * @return the array to which the element was appended. This may be different than the given
+     *         array.
+     */
+    public static <T> T[] append(T[] array, int currentSize, T element) {
+        assert currentSize <= array.length;
+
+        if (currentSize + 1 > array.length) {
+            @SuppressWarnings("unchecked")
+            T[] newArray = ArrayUtils.newUnpaddedArray(
+                    (Class<T>) array.getClass().getComponentType(), growSize(currentSize));
+            System.arraycopy(array, 0, newArray, 0, currentSize);
+            array = newArray;
+        }
+        array[currentSize] = element;
+        return array;
+    }
+
+    /**
+     * Primitive int version of {@link #append(Object[], int, Object)}.
+     */
+    public static int[] append(int[] array, int currentSize, int element) {
+        assert currentSize <= array.length;
+
+        if (currentSize + 1 > array.length) {
+            int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
+            System.arraycopy(array, 0, newArray, 0, currentSize);
+            array = newArray;
+        }
+        array[currentSize] = element;
+        return array;
+    }
+
+    /**
+     * Primitive long version of {@link #append(Object[], int, Object)}.
+     */
+    public static long[] append(long[] array, int currentSize, long element) {
+        assert currentSize <= array.length;
+
+        if (currentSize + 1 > array.length) {
+            long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
+            System.arraycopy(array, 0, newArray, 0, currentSize);
+            array = newArray;
+        }
+        array[currentSize] = element;
+        return array;
+    }
+
+    /**
+     * Primitive boolean version of {@link #append(Object[], int, Object)}.
+     */
+    public static boolean[] append(boolean[] array, int currentSize, boolean element) {
+        assert currentSize <= array.length;
+
+        if (currentSize + 1 > array.length) {
+            boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
+            System.arraycopy(array, 0, newArray, 0, currentSize);
+            array = newArray;
+        }
+        array[currentSize] = element;
+        return array;
+    }
+
+    /**
+     * Inserts an element into the array at the specified index, growing the array if there is no
+     * more room.
+     *
+     * @param array The array to which to append the element. Must NOT be null.
+     * @param currentSize The number of elements in the array. Must be less than or equal to
+     *                    array.length.
+     * @param element The element to insert.
+     * @return the array to which the element was appended. This may be different than the given
+     *         array.
+     */
+    public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
+        assert currentSize <= array.length;
+
+        if (currentSize + 1 <= array.length) {
+            System.arraycopy(array, index, array, index + 1, currentSize - index);
+            array[index] = element;
+            return array;
+        }
+
+        @SuppressWarnings("unchecked")
+        T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
+                growSize(currentSize));
+        System.arraycopy(array, 0, newArray, 0, index);
+        newArray[index] = element;
+        System.arraycopy(array, index, newArray, index + 1, array.length - index);
+        return newArray;
+    }
+
+    /**
+     * Primitive int version of {@link #insert(Object[], int, int, Object)}.
+     */
+    public static int[] insert(int[] array, int currentSize, int index, int element) {
+        assert currentSize <= array.length;
+
+        if (currentSize + 1 <= array.length) {
+            System.arraycopy(array, index, array, index + 1, currentSize - index);
+            array[index] = element;
+            return array;
+        }
+
+        int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
+        System.arraycopy(array, 0, newArray, 0, index);
+        newArray[index] = element;
+        System.arraycopy(array, index, newArray, index + 1, array.length - index);
+        return newArray;
+    }
+
+    /**
+     * Primitive long version of {@link #insert(Object[], int, int, Object)}.
+     */
+    public static long[] insert(long[] array, int currentSize, int index, long element) {
+        assert currentSize <= array.length;
+
+        if (currentSize + 1 <= array.length) {
+            System.arraycopy(array, index, array, index + 1, currentSize - index);
+            array[index] = element;
+            return array;
+        }
+
+        long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
+        System.arraycopy(array, 0, newArray, 0, index);
+        newArray[index] = element;
+        System.arraycopy(array, index, newArray, index + 1, array.length - index);
+        return newArray;
+    }
+
+    /**
+     * Primitive boolean version of {@link #insert(Object[], int, int, Object)}.
+     */
+    public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) {
+        assert currentSize <= array.length;
+
+        if (currentSize + 1 <= array.length) {
+            System.arraycopy(array, index, array, index + 1, currentSize - index);
+            array[index] = element;
+            return array;
+        }
+
+        boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
+        System.arraycopy(array, 0, newArray, 0, index);
+        newArray[index] = element;
+        System.arraycopy(array, index, newArray, index + 1, array.length - index);
+        return newArray;
+    }
+
+    /**
+     * Given the current size of an array, returns an ideal size to which the array should grow.
+     * This is typically double the given size, but should not be relied upon to do so in the
+     * future.
+     */
+    public static int growSize(int currentSize) {
+        return currentSize <= 4 ? 8 : currentSize * 2;
+    }
+
+    // Uninstantiable
+    private GrowingArrayUtils() {}
+}
diff --git a/graphics/java/android/graphics/TemporaryBuffer.java b/graphics/java/android/graphics/TemporaryBuffer.java
index c5b8143..36a2275 100644
--- a/graphics/java/android/graphics/TemporaryBuffer.java
+++ b/graphics/java/android/graphics/TemporaryBuffer.java
@@ -31,7 +31,7 @@ public class TemporaryBuffer {
         }
 
         if (buf == null || buf.length < len) {
-            buf = new char[ArrayUtils.idealCharArraySize(len)];
+            buf = ArrayUtils.newUnpaddedCharArray(len);
         }
 
         return buf;
diff --git a/tools/layoutlib/bridge/src/com/android/layoutlib/bridge/util/SparseWeakArray.java b/tools/layoutlib/bridge/src/com/android/layoutlib/bridge/util/SparseWeakArray.java
index 53e1640..a2a8aa9 100644
--- a/tools/layoutlib/bridge/src/com/android/layoutlib/bridge/util/SparseWeakArray.java
+++ b/tools/layoutlib/bridge/src/com/android/layoutlib/bridge/util/SparseWeakArray.java
@@ -18,6 +18,7 @@ package com.android.layoutlib.bridge.util;
 
 
 import com.android.internal.util.ArrayUtils;
+import com.android.internal.util.GrowingArrayUtils;
 
 import android.util.SparseArray;
 
@@ -59,10 +60,8 @@ public class SparseWeakArray<E> {
      * number of mappings.
      */
     public SparseWeakArray(int initialCapacity) {
-        initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
-
-        mKeys = new long[initialCapacity];
-        mValues = new WeakReference[initialCapacity];
+        mKeys = ArrayUtils.newUnpaddedLongArray(initialCapacity);
+        mValues = new WeakReference[mKeys.length];
         mSize = 0;
     }
 
@@ -142,18 +141,6 @@ public class SparseWeakArray<E> {
 
         mGarbage = false;
         mSize = o;
-
-        int newSize = ArrayUtils.idealLongArraySize(mSize);
-        if (newSize < mKeys.length) {
-            long[] nkeys = new long[newSize];
-            WeakReference<?>[] nvalues = new WeakReference[newSize];
-
-            System.arraycopy(mKeys, 0, nkeys, 0, newSize);
-            System.arraycopy(mValues, 0, nvalues, 0, newSize);
-
-            mKeys = nkeys;
-            mValues = nvalues;
-        }
     }
 
     /**
@@ -182,28 +169,8 @@ public class SparseWeakArray<E> {
                 i = ~binarySearch(mKeys, 0, mSize, key);
             }
 
-            if (mSize >= mKeys.length) {
-                int n = ArrayUtils.idealLongArraySize(mSize + 1);
-
-                long[] nkeys = new long[n];
-                WeakReference<?>[] nvalues = new WeakReference[n];
-
-                // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
-                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-                mKeys = nkeys;
-                mValues = nvalues;
-            }
-
-            if (mSize - i != 0) {
-                // Log.e("SparseArray", "move " + (mSize - i));
-                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
-                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
-            }
-
-            mKeys[i] = key;
-            mValues[i] = new WeakReference(value);
+            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
+            mValues = GrowingArrayUtils.insert(mValues, mSize, i, new WeakReference(value));
             mSize++;
         }
     }
@@ -321,24 +288,9 @@ public class SparseWeakArray<E> {
             gc();
         }
 
-        int pos = mSize;
-        if (pos >= mKeys.length) {
-            int n = ArrayUtils.idealLongArraySize(pos + 1);
-
-            long[] nkeys = new long[n];
-            WeakReference<?>[] nvalues = new WeakReference[n];
-
-            // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
-            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
-            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
-
-            mKeys = nkeys;
-            mValues = nvalues;
-        }
-
-        mKeys[pos] = key;
-        mValues[pos] = new WeakReference(value);
-        mSize = pos + 1;
+        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
+        mValues = GrowingArrayUtils.append(mValues, mSize, new WeakReference(value));
+        mSize++;
     }
 
     private boolean hasReclaimedRefs() {