diff options
author | Ben Gruver <bgruv@google.com> | 2013-04-07 17:01:49 -0700 |
---|---|---|
committer | Ben Gruver <bgruv@google.com> | 2013-04-08 00:09:15 -0700 |
commit | ffe82bdcb5c914b3a60b630c6d3abe6fc9229dec (patch) | |
tree | 9f9330a318e29b98b76658621e85ecac8b730ad9 /util | |
parent | 92d690894a3d91f776c39fb83b464f1d0c3e422a (diff) | |
download | smali-ffe82bdcb5c914b3a60b630c6d3abe6fc9229dec.tar.gz |
Fully remove the dependency on the old dexlib from baksmali
Diffstat (limited to 'util')
-rw-r--r-- | util/src/main/java/org/jf/util/SparseIntArray.java | 268 |
1 files changed, 268 insertions, 0 deletions
diff --git a/util/src/main/java/org/jf/util/SparseIntArray.java b/util/src/main/java/org/jf/util/SparseIntArray.java new file mode 100644 index 00000000..2b8b5e0a --- /dev/null +++ b/util/src/main/java/org/jf/util/SparseIntArray.java @@ -0,0 +1,268 @@ +/* + * Copyright 2013, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.jf.util; + +/** + * SparseIntArrays map integers to integers. Unlike a normal array of integers, + * there can be gaps in the indices. It is intended to be more efficient + * than using a HashMap to map Integers to Integers. + */ +public class SparseIntArray { + /** + * Creates a new SparseIntArray containing no mappings. + */ + public SparseIntArray() { + this(10); + } + + /** + * Creates a new SparseIntArray containing no mappings that will not + * require any additional memory allocation to store the specified + * number of mappings. + */ + public SparseIntArray(int initialCapacity) { + mKeys = new int[initialCapacity]; + mValues = new int[initialCapacity]; + mSize = 0; + } + + /** + * Gets the int mapped from the specified key, or <code>0</code> + * if no such mapping has been made. + */ + public int get(int key) { + return get(key, 0); + } + + /** + * Gets the int mapped from the specified key, or the specified value + * if no such mapping has been made. + */ + public int get(int key, int valueIfKeyNotFound) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i < 0) { + return valueIfKeyNotFound; + } else { + return mValues[i]; + } + } + + /** + * Gets the int mapped from the specified key, or if not present, the + * closest key that is less than the specified key. + */ + public int getClosestSmaller(int key) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i < 0) { + i = ~i; + if (i > 0) { + i--; + } + return mValues[i]; + } else { + return mValues[i]; + } + } + + /** + * Removes the mapping from the specified key, if there was any. + */ + public void delete(int key) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i >= 0) { + removeAt(i); + } + } + + /** + * Removes the mapping at the given index. + */ + public void removeAt(int index) { + System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); + System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); + mSize--; + } + + /** + * Adds a mapping from the specified key to the specified value, + * replacing the previous mapping from the specified key if there + * was one. + */ + public void put(int key, int value) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i >= 0) { + mValues[i] = value; + } else { + i = ~i; + + if (mSize >= mKeys.length) { + int n = Math.max(mSize + 1, mKeys.length * 2); + + 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; + mSize++; + } + } + + /** + * Returns the number of key-value mappings that this SparseIntArray + * currently stores. + */ + public int size() { + return mSize; + } + + /** + * Given an index in the range <code>0...size()-1</code>, returns + * the key from the <code>index</code>th key-value mapping that this + * SparseIntArray stores. + */ + public int keyAt(int index) { + return mKeys[index]; + } + + /** + * Given an index in the range <code>0...size()-1</code>, returns + * the value from the <code>index</code>th key-value mapping that this + * SparseIntArray stores. + */ + public int valueAt(int index) { + return mValues[index]; + } + + /** + * Returns the index for which {@link #keyAt} would return the + * specified key, or a negative number if the specified + * key is not mapped. + */ + public int indexOfKey(int key) { + return binarySearch(mKeys, 0, mSize, key); + } + + /** + * Returns an index for which {@link #valueAt} would return the + * specified key, or a negative number if no keys map to the + * specified value. + * Beware that this is a linear search, unlike lookups by key, + * and that multiple keys can map to the same value and this will + * find only one of them. + */ + public int indexOfValue(int value) { + for (int i = 0; i < mSize; i++) + if (mValues[i] == value) + return i; + + return -1; + } + + /** + * Removes all key-value mappings from this SparseIntArray. + */ + public void clear() { + mSize = 0; + } + + /** + * Puts a key/value pair into the array, optimizing for the case where + * the key is greater than all existing keys in the array. + */ + public void append(int key, int value) { + if (mSize != 0 && key <= mKeys[mSize - 1]) { + put(key, value); + return; + } + + int pos = mSize; + if (pos >= mKeys.length) { + int n = Math.max(pos + 1, mKeys.length * 2); + + 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; + } + + private static int binarySearch(int[] a, int start, int len, int key) { + int high = start + len, low = start - 1, guess; + + while (high - low > 1) { + guess = (high + low) / 2; + + if (a[guess] < key) + low = guess; + else + high = guess; + } + + if (high == start + len) + return ~(start + len); + else if (a[high] == key) + return high; + else + return ~high; + } + + private int[] mKeys; + private int[] mValues; + private int mSize; +} |