diff options
author | Ben Gruver <bgruv@google.com> | 2013-03-30 16:36:27 -0700 |
---|---|---|
committer | Ben Gruver <bgruv@google.com> | 2013-03-30 16:36:27 -0700 |
commit | 9531284b1b6a29371ae8d8e6cfe3e1f1bfe23296 (patch) | |
tree | ad97079e9df5e1202ce07369fc2a15d730758558 /util | |
parent | 08637a8e1f1dff5a36dbed68e7f4d40e900533cf (diff) | |
download | smali-9531284b1b6a29371ae8d8e6cfe3e1f1bfe23296.tar.gz |
Port MethodAnalyzer and various dependencies from dexlib
Diffstat (limited to 'util')
-rw-r--r-- | util/src/main/java/org/jf/util/BitSetUtils.java | 44 | ||||
-rw-r--r-- | util/src/main/java/org/jf/util/SparseArray.java | 373 |
2 files changed, 417 insertions, 0 deletions
diff --git a/util/src/main/java/org/jf/util/BitSetUtils.java b/util/src/main/java/org/jf/util/BitSetUtils.java new file mode 100644 index 00000000..777a857a --- /dev/null +++ b/util/src/main/java/org/jf/util/BitSetUtils.java @@ -0,0 +1,44 @@ +/* + * 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; + +import java.util.BitSet; + +public class BitSetUtils { + public static BitSet bitSetOfIndexes(int... indexes) { + BitSet bitSet = new BitSet(); + for (int index: indexes) { + bitSet.set(index); + } + return bitSet; + } +} diff --git a/util/src/main/java/org/jf/util/SparseArray.java b/util/src/main/java/org/jf/util/SparseArray.java new file mode 100644 index 00000000..474e21c7 --- /dev/null +++ b/util/src/main/java/org/jf/util/SparseArray.java @@ -0,0 +1,373 @@ +/* + * 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; + +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +/** + * SparseArrays map integers to Objects. Unlike a normal array of Objects, + * there can be gaps in the indices. It is intended to be more efficient + * than using a HashMap to map Integers to Objects. + */ +public class SparseArray<E> { + private static final Object DELETED = new Object(); + private boolean mGarbage = false; + + /** + * Creates a new SparseArray containing no mappings. + */ + public SparseArray() { + this(10); + } + + /** + * Creates a new SparseArray containing no mappings that will not + * require any additional memory allocation to store the specified + * number of mappings. + */ + public SparseArray(int initialCapacity) { + mKeys = new int[initialCapacity]; + mValues = new Object[initialCapacity]; + mSize = 0; + } + + /** + * Gets the Object mapped from the specified key, or <code>null</code> + * if no such mapping has been made. + */ + public E get(int key) { + return get(key, null); + } + + /** + * Gets the Object mapped from the specified key, or the specified Object + * if no such mapping has been made. + */ + public E get(int key, E valueIfKeyNotFound) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i < 0 || mValues[i] == DELETED) { + return valueIfKeyNotFound; + } else { + return (E) 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) { + if (mValues[i] != DELETED) { + mValues[i] = DELETED; + mGarbage = true; + } + } + } + + /** + * Alias for {@link #delete(int)}. + */ + public void remove(int key) { + delete(key); + } + + private void gc() { + // Log.e("SparseArray", "gc start with " + mSize); + + int n = mSize; + int o = 0; + int[] keys = mKeys; + Object[] values = mValues; + + for (int i = 0; i < n; i++) { + Object val = values[i]; + + if (val != DELETED) { + if (i != o) { + keys[o] = keys[i]; + values[o] = val; + } + + o++; + } + } + + mGarbage = false; + mSize = o; + + // Log.e("SparseArray", "gc end with " + 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, E value) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i >= 0) { + mValues[i] = value; + } else { + i = ~i; + + if (i < mSize && mValues[i] == DELETED) { + mKeys[i] = key; + mValues[i] = value; + return; + } + + if (mGarbage && mSize >= mKeys.length) { + gc(); + + // Search again because indices may have changed. + i = ~binarySearch(mKeys, 0, mSize, key); + } + + if (mSize >= mKeys.length) { + int n = Math.max(mSize + 1, mKeys.length * 2); + + 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; + mSize++; + } + } + + /** + * Returns the number of key-value mappings that this SparseArray + * currently stores. + */ + public int size() { + if (mGarbage) { + gc(); + } + + 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 + * SparseArray stores. + */ + public int keyAt(int index) { + if (mGarbage) { + gc(); + } + + 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 + * SparseArray stores. + */ + public E valueAt(int index) { + if (mGarbage) { + gc(); + } + + return (E) mValues[index]; + } + + /** + * Given an index in the range <code>0...size()-1</code>, sets a new + * value for the <code>index</code>th key-value mapping that this + * SparseArray stores. + */ + public void setValueAt(int index, E value) { + if (mGarbage) { + gc(); + } + + mValues[index] = value; + } + + /** + * 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) { + if (mGarbage) { + gc(); + } + + 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(E value) { + if (mGarbage) { + gc(); + } + + for (int i = 0; i < mSize; i++) + if (mValues[i] == value) + return i; + + return -1; + } + + /** + * Removes all key-value mappings from this SparseArray. + */ + public void clear() { + int n = mSize; + Object[] values = mValues; + + for (int i = 0; i < n; i++) { + values[i] = null; + } + + mSize = 0; + mGarbage = false; + } + + /** + * 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, E value) { + if (mSize != 0 && key <= mKeys[mSize - 1]) { + put(key, value); + return; + } + + if (mGarbage && mSize >= mKeys.length) { + gc(); + } + + int pos = mSize; + if (pos >= mKeys.length) { + int n = Math.max(pos + 1, mKeys.length * 2); + + 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; + } + + /** + * Increases the size of the underlying storage if needed, to ensure that it can + * hold the specified number of items without having to allocate additional memory + * @param capacity the number of items + */ + public void ensureCapacity(int capacity) { + if (mGarbage && mSize >= mKeys.length) { + gc(); + } + + if (mKeys.length < capacity) { + int[] nkeys = new int[capacity]; + Object[] nvalues = new Object[capacity]; + + System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); + System.arraycopy(mValues, 0, nvalues, 0, mValues.length); + + mKeys = nkeys; + mValues = nvalues; + } + } + + 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; + } + + /** + * @return a read-only list of the values in this SparseArray which are in ascending order, based on their + * associated key + */ + public List<E> getValues() { + return Collections.unmodifiableList(Arrays.asList((E[])mValues)); + } + + private int[] mKeys; + private Object[] mValues; + private int mSize; +} |