src/third_party/protobuf-3/javanano/src/main/java/com/google/protobuf/nano/FieldArray.java - cobalt - Git at Google

 // 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;
     }
 }
	// 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;
	}
	}