| // Protocol Buffers - Google's data interchange format |
| // Copyright 2014 Google Inc. All rights reserved. |
| // https://developers.google.com/protocol-buffers/ |
| // |
| // 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 com.google.protobuf.nano; |
| |
| |
| /** |
| * A custom version of {@code android.util.SparseArray} with the minimal API |
| * for storing {@link FieldData} objects. |
| * |
| * <p>This class is an internal implementation detail of nano and should not |
| * be called directly by clients. |
| * |
| * Based on {@code android.support.v4.util.SpareArrayCompat}. |
| */ |
| public final class FieldArray implements Cloneable { |
| private static final FieldData DELETED = new FieldData(); |
| private boolean mGarbage = false; |
| |
| private int[] mFieldNumbers; |
| private FieldData[] mData; |
| private int mSize; |
| |
| /** |
| * Creates a new FieldArray containing no fields. |
| */ |
| FieldArray() { |
| this(10); |
| } |
| |
| /** |
| * Creates a new FieldArray containing no mappings that will not |
| * require any additional memory allocation to store the specified |
| * number of mappings. |
| */ |
| FieldArray(int initialCapacity) { |
| initialCapacity = idealIntArraySize(initialCapacity); |
| mFieldNumbers = new int[initialCapacity]; |
| mData = new FieldData[initialCapacity]; |
| mSize = 0; |
| } |
| |
| /** |
| * Gets the FieldData mapped from the specified fieldNumber, or <code>null</code> |
| * if no such mapping has been made. |
| */ |
| FieldData get(int fieldNumber) { |
| int i = binarySearch(fieldNumber); |
| |
| if (i < 0 || mData[i] == DELETED) { |
| return null; |
| } else { |
| return mData[i]; |
| } |
| } |
| |
| /** |
| * Removes the data from the specified fieldNumber, if there was any. |
| */ |
| void remove(int fieldNumber) { |
| int i = binarySearch(fieldNumber); |
| |
| if (i >= 0 && mData[i] != DELETED) { |
| mData[i] = DELETED; |
| mGarbage = true; |
| } |
| } |
| |
| private void gc() { |
| int n = mSize; |
| int o = 0; |
| int[] keys = mFieldNumbers; |
| FieldData[] values = mData; |
| |
| for (int i = 0; i < n; i++) { |
| FieldData val = values[i]; |
| |
| if (val != DELETED) { |
| if (i != o) { |
| keys[o] = keys[i]; |
| values[o] = val; |
| values[i] = null; |
| } |
| |
| o++; |
| } |
| } |
| |
| mGarbage = false; |
| mSize = o; |
| } |
| |
| /** |
| * Adds a mapping from the specified fieldNumber to the specified data, |
| * replacing the previous mapping if there was one. |
| */ |
| void put(int fieldNumber, FieldData data) { |
| int i = binarySearch(fieldNumber); |
| |
| if (i >= 0) { |
| mData[i] = data; |
| } else { |
| i = ~i; |
| |
| if (i < mSize && mData[i] == DELETED) { |
| mFieldNumbers[i] = fieldNumber; |
| mData[i] = data; |
| return; |
| } |
| |
| if (mGarbage && mSize >= mFieldNumbers.length) { |
| gc(); |
| |
| // Search again because indices may have changed. |
| i = ~ binarySearch(fieldNumber); |
| } |
| |
| if (mSize >= mFieldNumbers.length) { |
| int n = idealIntArraySize(mSize + 1); |
| |
| int[] nkeys = new int[n]; |
| FieldData[] nvalues = new FieldData[n]; |
| |
| System.arraycopy(mFieldNumbers, 0, nkeys, 0, mFieldNumbers.length); |
| System.arraycopy(mData, 0, nvalues, 0, mData.length); |
| |
| mFieldNumbers = nkeys; |
| mData = nvalues; |
| } |
| |
| if (mSize - i != 0) { |
| System.arraycopy(mFieldNumbers, i, mFieldNumbers, i + 1, mSize - i); |
| System.arraycopy(mData, i, mData, i + 1, mSize - i); |
| } |
| |
| mFieldNumbers[i] = fieldNumber; |
| mData[i] = data; |
| mSize++; |
| } |
| } |
| |
| /** |
| * Returns the number of key-value mappings that this FieldArray |
| * currently stores. |
| */ |
| int size() { |
| if (mGarbage) { |
| gc(); |
| } |
| |
| return mSize; |
| } |
| |
| public boolean isEmpty() { |
| return size() == 0; |
| } |
| |
| /** |
| * 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 |
| * FieldArray stores. |
| */ |
| FieldData dataAt(int index) { |
| if (mGarbage) { |
| gc(); |
| } |
| |
| return mData[index]; |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| if (o == this) { |
| return true; |
| } |
| if (!(o instanceof FieldArray)) { |
| return false; |
| } |
| |
| FieldArray other = (FieldArray) o; |
| if (size() != other.size()) { // size() will call gc() if necessary. |
| return false; |
| } |
| return arrayEquals(mFieldNumbers, other.mFieldNumbers, mSize) && |
| arrayEquals(mData, other.mData, mSize); |
| } |
| |
| @Override |
| public int hashCode() { |
| if (mGarbage) { |
| gc(); |
| } |
| int result = 17; |
| for (int i = 0; i < mSize; i++) { |
| result = 31 * result + mFieldNumbers[i]; |
| result = 31 * result + mData[i].hashCode(); |
| } |
| return result; |
| } |
| |
| private int idealIntArraySize(int need) { |
| return idealByteArraySize(need * 4) / 4; |
| } |
| |
| private int idealByteArraySize(int need) { |
| for (int i = 4; i < 32; i++) |
| if (need <= (1 << i) - 12) |
| return (1 << i) - 12; |
| |
| return need; |
| } |
| |
| private int binarySearch(int value) { |
| int lo = 0; |
| int hi = mSize - 1; |
| |
| while (lo <= hi) { |
| int mid = (lo + hi) >>> 1; |
| int midVal = mFieldNumbers[mid]; |
| |
| if (midVal < value) { |
| lo = mid + 1; |
| } else if (midVal > value) { |
| hi = mid - 1; |
| } else { |
| return mid; // value found |
| } |
| } |
| return ~lo; // value not present |
| } |
| |
| private boolean arrayEquals(int[] a, int[] b, int size) { |
| for (int i = 0; i < size; i++) { |
| if (a[i] != b[i]) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| private boolean arrayEquals(FieldData[] a, FieldData[] b, int size) { |
| for (int i = 0; i < size; i++) { |
| if (!a[i].equals(b[i])) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| @Override |
| public final FieldArray clone() { |
| // Trigger GC so we compact and don't copy DELETED elements. |
| int size = size(); |
| FieldArray clone = new FieldArray(size); |
| System.arraycopy(mFieldNumbers, 0, clone.mFieldNumbers, 0, size); |
| for (int i = 0; i < size; i++) { |
| if (mData[i] != null) { |
| clone.mData[i] = mData[i].clone(); |
| } |
| } |
| clone.mSize = size; |
| return clone; |
| } |
| } |