diff options
author | Adam Lesinski <adamlesinski@google.com> | 2014-03-07 11:30:59 -0500 |
---|---|---|
committer | Adam Lesinski <adamlesinski@google.com> | 2014-03-27 11:42:10 -0700 |
commit | 776abc24cdd18610232a50b997cce3cffa74609b (patch) | |
tree | 9ec6c84c00b7e8e653b9bc1c91e612cdf2afb32d /core | |
parent | 350159c65a52092db04f1b8efce6943f61e50e73 (diff) | |
download | frameworks_base-776abc24cdd18610232a50b997cce3cffa74609b.zip frameworks_base-776abc24cdd18610232a50b997cce3cffa74609b.tar.gz frameworks_base-776abc24cdd18610232a50b997cce3cffa74609b.tar.bz2 |
Uses VMRuntime.newUnpaddedArray for ideal array sizes
Bug:13028925
Change-Id: I0a9301248b10a339afbdc5e4ffe3310ac4fa1fb7
Diffstat (limited to 'core')
27 files changed, 406 insertions, 447 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() {} +} |