core/java/com/android/internal/app/procstats/SparseMappingTable.java - platform/frameworks/base - Git at Google

 /*
  * Copyright (C) 2013 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.app.procstats;

 import android.os.Build;
 import android.os.Parcel;
 import android.util.EventLog;
 import android.util.Slog;
 import libcore.util.EmptyArray;

 import java.util.ArrayList;
 import java.util.Arrays;

 import com.android.internal.util.GrowingArrayUtils;

 /**
  * Class that contains a set of tables mapping byte ids to long values.
  *
  * This class is used to store the ProcessStats data.  This data happens to be
  * a set of very sparse tables, that is mostly append or overwrite, with infrequent
  * resets of the data.
  *
  * Data is stored as a list of large long[] arrays containing the actual values.  There are a
  * set of Table objects that each contain a small array mapping the byte IDs to a position
  * in the larger arrays.
  *
  * The data itself is either a single long value or a range of long values which are always
  * stored continguously in one of the long arrays. When the caller allocates a slot with
  * getOrAddKey, an int key is returned.  That key can be re-retreived with getKey without
  * allocating the value.  The data can then be set or retrieved with that key.
  */
 public class SparseMappingTable {
     private static final String TAG = "SparseMappingTable";

     // How big each array is.
     public static final int ARRAY_SIZE = 4096;

     public static final int INVALID_KEY = 0xffffffff;

     // Where the "type"/"state" part of the data appears in an offset integer.
     private static final int ID_SHIFT = 0;
     private static final int ID_MASK = 0xff;
     // Where the "which array" part of the data appears in an offset integer.
     private static final int ARRAY_SHIFT = 8;
     private static final int ARRAY_MASK = 0xff;
     // Where the "index into array" part of the data appears in an offset integer.
     private static final int INDEX_SHIFT = 16;
     private static final int INDEX_MASK = 0xffff;

     private int mSequence;
     private int mNextIndex;
     private final ArrayList<long[]> mLongs = new ArrayList<long[]>();

     /**
      * A table of data as stored in a SparseMappingTable.
      */
     public static class Table {
         private SparseMappingTable mParent;
         private int mSequence = 1;
         private int[] mTable;
         private int mSize;

         public Table(SparseMappingTable parent) {
             mParent = parent;
             mSequence = parent.mSequence;
         }

         /**
          * Pulls the data from 'copyFrom' and stores it in our own longs table.
          *
          * @param copyFrom   The Table to copy from
          * @param valueCount The number of values to copy for each key
          */
         public void copyFrom(Table copyFrom, int valueCount) {
             mTable = null;
             mSize = 0;

             final int N = copyFrom.getKeyCount();
             for (int i=0; i<N; i++) {
                 final int theirKey = copyFrom.getKeyAt(i);
                 final long[] theirLongs = copyFrom.mParent.mLongs.get(getArrayFromKey(theirKey));

                 final byte id = SparseMappingTable.getIdFromKey(theirKey);

                 final int myKey = this.getOrAddKey((byte)id, valueCount);
                 final long[] myLongs = mParent.mLongs.get(getArrayFromKey(myKey));

                 System.arraycopy(theirLongs, getIndexFromKey(theirKey),
                         myLongs, getIndexFromKey(myKey), valueCount);
             }
         }

         /**
          * Allocates data in the buffer, and stores that key in the mapping for this
          * table.
          *
          * @param id    The id of the item (will be used in making the key)
          * @param count The number of bytes to allocate.  Must be less than
          *              SparseMappingTable.ARRAY_SIZE.
          *
          * @return The 'key' for this data value, which contains both the id itself
          *         and the location in the long arrays that the data is actually stored
          *         but should be considered opaque to the caller.
          */
         public int getOrAddKey(byte id, int count) {
             assertConsistency();

             final int idx = binarySearch(id);
             if (idx >= 0) {
                 // Found
                 return mTable[idx];
             } else {
                 // Not found. Need to allocate it.

                 // Get an array with enough space to store 'count' values.
                 final ArrayList<long[]> list = mParent.mLongs;
                 int whichArray = list.size()-1;
                 long[] array = list.get(whichArray);
                 if (mParent.mNextIndex + count > array.length) {
                     // if it won't fit then make a new array.
                     array = new long[ARRAY_SIZE];
                     list.add(array);
                     whichArray++;
                     mParent.mNextIndex = 0;
                 }

                 // The key is a combination of whichArray, which index in that array, and
                 // the table value itself, which will be used for lookup
                 final int key = (whichArray << ARRAY_SHIFT)
                         | (mParent.mNextIndex << INDEX_SHIFT)
                         | (((int)id) << ID_SHIFT);

                 mParent.mNextIndex += count;

                 // Store the key in the sparse lookup table for this Table object.
                 mTable = GrowingArrayUtils.insert(mTable != null ? mTable : EmptyArray.INT,
                         mSize, ~idx, key);
                 mSize++;

                 return key;
             }
         }

         /**
          * Looks up a key in the table.
          *
          * @return The key from this table or INVALID_KEY if the id is not found.
          */
         public int getKey(byte id) {
             assertConsistency();

             final int idx = binarySearch(id);
             if (idx >= 0) {
                 return mTable[idx];
             } else {
                 return INVALID_KEY;
             }
         }

         /**
          * Get the value for the given key and offset from that key.
          *
          * @param key   A key as obtained from getKey or getOrAddKey.
          * @param value The value to set.
          */
         public long getValue(int key) {
             return getValue(key, 0);
         }

         /**
          * Get the value for the given key and offset from that key.
          *
          * @param key   A key as obtained from getKey or getOrAddKey.
          * @param index The offset from that key.  Must be less than the count
          *              provided to getOrAddKey when the space was allocated.
          * @param value The value to set.
          *
          * @return the value, or 0 in case of an error
          */
         public long getValue(int key, int index) {
             assertConsistency();

             try {
                 final long[] array = mParent.mLongs.get(getArrayFromKey(key));
                 return array[getIndexFromKey(key) + index];
             } catch (IndexOutOfBoundsException ex) {
                 logOrThrow("key=0x" + Integer.toHexString(key)
                         + " index=" + index + " -- " + dumpInternalState(), ex);
                 return 0;
             }
         }

         /**
          * Set the value for the given id at offset 0 from that id.
          * If the id is not found, return 0 instead.
          *
          * @param id    The id of the item.
          */
         public long getValueForId(byte id) {
             return getValueForId(id, 0);
         }

         /**
          * Set the value for the given id and index offset from that id.
          * If the id is not found, return 0 instead.
          *
          * @param id    The id of the item.
          * @param index The offset from that key.  Must be less than the count
          *              provided to getOrAddKey when the space was allocated.
          */
         public long getValueForId(byte id, int index) {
             assertConsistency();

             final int idx = binarySearch(id);
             if (idx >= 0) {
                 final int key = mTable[idx];
                 try {
                     final long[] array = mParent.mLongs.get(getArrayFromKey(key));
                     return array[getIndexFromKey(key) + index];
                 } catch (IndexOutOfBoundsException ex) {
                     logOrThrow("id=0x" + Integer.toHexString(id) + " idx=" + idx
                             + " key=0x" + Integer.toHexString(key) + " index=" + index
                             + " -- " + dumpInternalState(), ex);
                     return 0;
                 }
             } else {
                 return 0;
             }
         }

         /**
          * Return the raw storage long[] for the given key.
          */
         public long[] getArrayForKey(int key) {
             assertConsistency();

             return mParent.mLongs.get(getArrayFromKey(key));
         }

         /**
          * Set the value for the given key and offset from that key.
          *
          * @param key   A key as obtained from getKey or getOrAddKey.
          * @param value The value to set.
          */
         public void setValue(int key, long value) {
             setValue(key, 0, value);
         }

         /**
          * Set the value for the given key and offset from that key.
          *
          * @param key   A key as obtained from getKey or getOrAddKey.
          * @param index The offset from that key.  Must be less than the count
          *              provided to getOrAddKey when the space was allocated.
          * @param value The value to set.
          */
         public void setValue(int key, int index, long value) {
             assertConsistency();

             if (value < 0) {
                 logOrThrow("can't store negative values"
                         + " key=0x" + Integer.toHexString(key)
                         + " index=" + index + " value=" + value
                         + " -- " + dumpInternalState());
                 return;
             }

             try {
                 final long[] array = mParent.mLongs.get(getArrayFromKey(key));
                 array[getIndexFromKey(key) + index] = value;
             } catch (IndexOutOfBoundsException ex) {
                 logOrThrow("key=0x" + Integer.toHexString(key)
                         + " index=" + index + " value=" + value
                         + " -- " + dumpInternalState(), ex);
                 return;
             }
         }

         /**
          * Clear out the table, and reset the sequence numbers so future writes
          * without allocations will assert.
          */
         public void resetTable() {
             // Clear out our table.
             mTable = null;
             mSize = 0;

             // Reset our sequence number.  This will make all read/write calls
             // start to fail, and then when we re-allocate it will be re-synced
             // to that of mParent.
             mSequence = mParent.mSequence;
         }

         /**
          * Write the keys stored in the table to the parcel. The parent must
          * be separately written. Does not save the actual data.
          */
         public void writeToParcel(Parcel out) {
             out.writeInt(mSequence);
             out.writeInt(mSize);
             for (int i=0; i<mSize; i++) {
                 out.writeInt(mTable[i]);
             }
         }

         /**
          * Read the keys from the parcel. The parent (with its long array) must
          * have been previously initialized.
          */
         public boolean readFromParcel(Parcel in) {
             // Read the state
             mSequence = in.readInt();
             mSize = in.readInt();
             if (mSize != 0) {
                 mTable = new int[mSize];
                 for (int i=0; i<mSize; i++) {
                     mTable[i] = in.readInt();
                 }
             } else {
                 mTable = null;
             }

             // Make sure we're all healthy
             if (validateKeys(true)) {
                 return true;
             } else {
                 // Clear it out
                 mSize = 0;
                 mTable = null;
                 return false;
             }
         }

         /**
          * Return the number of keys that have been added to this Table.
          */
         public int getKeyCount() {
             return mSize;
         }

         /**
          * Get the key at the given index in our table.
          */
         public int getKeyAt(int i) {
             return mTable[i];
         }

         /**
          * Throw an exception if one of a variety of internal consistency checks fails.
          */
         private void assertConsistency() {
             // Something with this checking isn't working and is triggering
             // more problems than it's helping to debug.
             //   Original bug: b/27045736
             //   New bug: b/27960286
             if (false) {
                 // Assert that our sequence number matches mParent's.  If it isn't that means
                 // we have been reset and our.  If our sequence is UNITIALIZED_SEQUENCE, then
                 // it's possible that everything is working fine and we just haven't been
                 // written to since the last resetTable().
                 if (mSequence != mParent.mSequence) {
                     if (mSequence < mParent.mSequence) {
                         logOrThrow("Sequence mismatch. SparseMappingTable.reset()"
                                 + " called but not Table.resetTable() -- "
                                 + dumpInternalState());
                         return;
                     } else if (mSequence > mParent.mSequence) {
                         logOrThrow("Sequence mismatch. Table.resetTable()"
                                 + " called but not SparseMappingTable.reset() -- "
                                 + dumpInternalState());
                         return;
                     }
                 }
             }
         }

         /**
          * Finds the 'id' inside the array of length size (physical size of the array
          * is not used).
          *
          * @return The index of the array, or the bitwise not (~index) of where it
          * would go if you wanted to insert 'id' into the array.
          */
         private int binarySearch(byte id) {
             int lo = 0;
             int hi = mSize - 1;

             while (lo <= hi) {
                 int mid = (lo + hi) >>> 1;
                 byte midId = (byte)((mTable[mid] >> ID_SHIFT) & ID_MASK);

                 if (midId < id) {
                     lo = mid + 1;
                 } else if (midId > id) {
                     hi = mid - 1;
                 } else {
                     return mid;  // id found
                 }
             }
             return ~lo;  // id not present
         }

         /**
          * Check that all the keys are valid locations in the long arrays.
          *
          * If any aren't, log it and return false. Else return true.
          */
         private boolean validateKeys(boolean log) {
             ArrayList<long[]> longs = mParent.mLongs;
             final int longsSize = longs.size();

             final int N = mSize;
             for (int i=0; i<N; i++) {
                 final int key = mTable[i];
                 final int arrayIndex = getArrayFromKey(key);
                 final int index = getIndexFromKey(key);
                 if (arrayIndex >= longsSize || index >= longs.get(arrayIndex).length) {
                     if (log) {
                         Slog.w(TAG, "Invalid stats at index " + i + " -- " + dumpInternalState());
                     }
                     return false;
                 }
             }

             return true;
         }

         public String dumpInternalState() {
             StringBuilder sb = new StringBuilder();
             sb.append("SparseMappingTable.Table{mSequence=");
             sb.append(mSequence);
             sb.append(" mParent.mSequence=");
             sb.append(mParent.mSequence);
             sb.append(" mParent.mLongs.size()=");
             sb.append(mParent.mLongs.size());
             sb.append(" mSize=");
             sb.append(mSize);
             sb.append(" mTable=");
             if (mTable == null) {
                 sb.append("null");
             } else {
                 final int N = mTable.length;
                 sb.append('[');
                 for (int i=0; i<N; i++) {
                     final int key = mTable[i];
                     sb.append("0x");
                     sb.append(Integer.toHexString((key >> ID_SHIFT) & ID_MASK));
                     sb.append("/0x");
                     sb.append(Integer.toHexString((key >> ARRAY_SHIFT) & ARRAY_MASK));
                     sb.append("/0x");
                     sb.append(Integer.toHexString((key >> INDEX_SHIFT) & INDEX_MASK));
                     if (i != N-1) {
                         sb.append(", ");
                     }
                 }
                 sb.append(']');
             }
             sb.append(" clazz=");
             sb.append(getClass().getName());
             sb.append('}');

             return sb.toString();
         }
     }

     public SparseMappingTable() {
         mLongs.add(new long[ARRAY_SIZE]);
     }

     /**
      * Wipe out all the data.
      */
     public void reset() {
         // Clear out mLongs, and prime it with a new array of data
         mLongs.clear();
         mLongs.add(new long[ARRAY_SIZE]);
         mNextIndex = 0;

         // Increment out sequence counter, because all of the tables will
         // now be out of sync with the data.
         mSequence++;
     }

     /**
      * Write the data arrays to the parcel.
      */
     public void writeToParcel(Parcel out) {
         out.writeInt(mSequence);
         out.writeInt(mNextIndex);
         final int N = mLongs.size();
         out.writeInt(N);
         for (int i=0; i<N-1; i++) {
             final long[] array = mLongs.get(i);
             out.writeInt(array.length);
             writeCompactedLongArray(out, array, array.length);
         }
         // save less for the last one. upon re-loading they'll just start a new array.
         final long[] lastLongs = mLongs.get(N-1);
         out.writeInt(mNextIndex);
         writeCompactedLongArray(out, lastLongs, mNextIndex);
     }

     /**
      * Read the data arrays from the parcel.
      */
     public void readFromParcel(Parcel in) {
         mSequence = in.readInt();
         mNextIndex = in.readInt();

         mLongs.clear();
         final int N = in.readInt();
         for (int i=0; i<N; i++) {
             final int size = in.readInt();
             final long[] array = new long[size];
             readCompactedLongArray(in, array, size);
             mLongs.add(array);
         }
         // Verify that last array's length is consistent with writeToParcel
         if (N > 0 && mLongs.get(N - 1).length != mNextIndex) {
             EventLog.writeEvent(0x534e4554, "73252178", -1, "");
             throw new IllegalStateException("Expected array of length " + mNextIndex + " but was "
                     + mLongs.get(N - 1).length);
         }
     }

     /**
      * Return a string for debugging.
      */
     public String dumpInternalState(boolean includeData) {
         final StringBuilder sb = new StringBuilder();
         sb.append("SparseMappingTable{");
         sb.append("mSequence=");
         sb.append(mSequence);
         sb.append(" mNextIndex=");
         sb.append(mNextIndex);
         sb.append(" mLongs.size=");
         final int N = mLongs.size();
         sb.append(N);
         sb.append("\n");
         if (includeData) {
             for (int i=0; i<N; i++) {
                 final long[] array = mLongs.get(i);
                 for (int j=0; j<array.length; j++) {
                     if (i == N-1 && j == mNextIndex) {
                         break;
                     }
                     sb.append(String.format(" %4d %d 0x%016x %-19d\n", i, j, array[j], array[j]));
                 }
             }
         }
         sb.append("}");
         return sb.toString();
     }

     /**
      * Write the long array to the parcel in a compacted form.  Does not allow negative
      * values in the array.
      */
     private static void writeCompactedLongArray(Parcel out, long[] array, int num) {
         for (int i=0; i<num; i++) {
             long val = array[i];
             if (val < 0) {
                 Slog.w(TAG, "Time val negative: " + val);
                 val = 0;
             }
             if (val <= Integer.MAX_VALUE) {
                 out.writeInt((int)val);
             } else {
                 int top = ~((int)((val>>32)&0x7fffffff));
                 int bottom = (int)(val&0x0ffffffffL);
                 out.writeInt(top);
                 out.writeInt(bottom);
             }
         }
     }

     /**
      * Read the compacted array into the long[].
      */
     private static void readCompactedLongArray(Parcel in, long[] array, int num) {
         final int alen = array.length;
         if (num > alen) {
             logOrThrow("bad array lengths: got " + num + " array is " + alen);
             return;
         }
         int i;
         for (i=0; i<num; i++) {
             int val = in.readInt();
             if (val >= 0) {
                 array[i] = val;
             } else {
                 int bottom = in.readInt();
                 array[i] = (((long)~val)<<32) | bottom;
             }
         }
         while (i < alen) {
             array[i] = 0;
             i++;
         }
     }

     /**
      * Extract the id from a key.
      */
     public static byte getIdFromKey(int key) {
         return (byte)((key >> ID_SHIFT) & ID_MASK);
     }

     /**
      * Gets the index of the array in the list of arrays.
      *
      * Not to be confused with getIndexFromKey.
      */
     public static int getArrayFromKey(int key) {
         return (key >> ARRAY_SHIFT) & ARRAY_MASK;
     }

     /**
      * Gets the index of a value in a long[].
      *
      * Not to be confused with getArrayFromKey.
      */
     public static int getIndexFromKey(int key) {
         return (key >> INDEX_SHIFT) & INDEX_MASK;
     }

     /**
      * Do a Slog.wtf or throw an exception (thereby crashing the system process if
      * this is a debug build.)
      */
     private static void logOrThrow(String message) {
         logOrThrow(message, new RuntimeException("Stack trace"));
     }

     /**
      * Do a Slog.wtf or throw an exception (thereby crashing the system process if
      * this is an eng build.)
      */
     private static void logOrThrow(String message, Throwable th) {
         Slog.e(TAG, message, th);
         if (Build.TYPE.equals("eng")) {
             throw new RuntimeException(message, th);
         }
     }
 }
	/*
	* Copyright (C) 2013 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.app.procstats;

	import android.os.Build;
	import android.os.Parcel;
	import android.util.EventLog;
	import android.util.Slog;
	import libcore.util.EmptyArray;

	import java.util.ArrayList;
	import java.util.Arrays;

	import com.android.internal.util.GrowingArrayUtils;

	/**
	* Class that contains a set of tables mapping byte ids to long values.
	*
	* This class is used to store the ProcessStats data. This data happens to be
	* a set of very sparse tables, that is mostly append or overwrite, with infrequent
	* resets of the data.
	*
	* Data is stored as a list of large long[] arrays containing the actual values. There are a
	* set of Table objects that each contain a small array mapping the byte IDs to a position
	* in the larger arrays.
	*
	* The data itself is either a single long value or a range of long values which are always
	* stored continguously in one of the long arrays. When the caller allocates a slot with
	* getOrAddKey, an int key is returned. That key can be re-retreived with getKey without
	* allocating the value. The data can then be set or retrieved with that key.
	*/
	public class SparseMappingTable {
	private static final String TAG = "SparseMappingTable";

	// How big each array is.
	public static final int ARRAY_SIZE = 4096;

	public static final int INVALID_KEY = 0xffffffff;

	// Where the "type"/"state" part of the data appears in an offset integer.
	private static final int ID_SHIFT = 0;
	private static final int ID_MASK = 0xff;
	// Where the "which array" part of the data appears in an offset integer.
	private static final int ARRAY_SHIFT = 8;
	private static final int ARRAY_MASK = 0xff;
	// Where the "index into array" part of the data appears in an offset integer.
	private static final int INDEX_SHIFT = 16;
	private static final int INDEX_MASK = 0xffff;

	private int mSequence;
	private int mNextIndex;
	private final ArrayList<long[]> mLongs = new ArrayList<long[]>();

	/**
	* A table of data as stored in a SparseMappingTable.
	*/
	public static class Table {
	private SparseMappingTable mParent;
	private int mSequence = 1;
	private int[] mTable;
	private int mSize;

	public Table(SparseMappingTable parent) {
	mParent = parent;
	mSequence = parent.mSequence;
	}

	/**
	* Pulls the data from 'copyFrom' and stores it in our own longs table.
	*
	* @param copyFrom The Table to copy from
	* @param valueCount The number of values to copy for each key
	*/
	public void copyFrom(Table copyFrom, int valueCount) {
	mTable = null;
	mSize = 0;

	final int N = copyFrom.getKeyCount();
	for (int i=0; i<N; i++) {
	final int theirKey = copyFrom.getKeyAt(i);
	final long[] theirLongs = copyFrom.mParent.mLongs.get(getArrayFromKey(theirKey));

	final byte id = SparseMappingTable.getIdFromKey(theirKey);

	final int myKey = this.getOrAddKey((byte)id, valueCount);
	final long[] myLongs = mParent.mLongs.get(getArrayFromKey(myKey));

	System.arraycopy(theirLongs, getIndexFromKey(theirKey),
	myLongs, getIndexFromKey(myKey), valueCount);
	}
	}

	/**
	* Allocates data in the buffer, and stores that key in the mapping for this
	* table.
	*
	* @param id The id of the item (will be used in making the key)
	* @param count The number of bytes to allocate. Must be less than
	* SparseMappingTable.ARRAY_SIZE.
	*
	* @return The 'key' for this data value, which contains both the id itself
	* and the location in the long arrays that the data is actually stored
	* but should be considered opaque to the caller.
	*/
	public int getOrAddKey(byte id, int count) {
	assertConsistency();

	final int idx = binarySearch(id);
	if (idx >= 0) {
	// Found
	return mTable[idx];
	} else {
	// Not found. Need to allocate it.

	// Get an array with enough space to store 'count' values.
	final ArrayList<long[]> list = mParent.mLongs;
	int whichArray = list.size()-1;
	long[] array = list.get(whichArray);
	if (mParent.mNextIndex + count > array.length) {
	// if it won't fit then make a new array.
	array = new long[ARRAY_SIZE];
	list.add(array);
	whichArray++;
	mParent.mNextIndex = 0;
	}

	// The key is a combination of whichArray, which index in that array, and
	// the table value itself, which will be used for lookup
	final int key = (whichArray << ARRAY_SHIFT)
	\| (mParent.mNextIndex << INDEX_SHIFT)
	\| (((int)id) << ID_SHIFT);

	mParent.mNextIndex += count;

	// Store the key in the sparse lookup table for this Table object.
	mTable = GrowingArrayUtils.insert(mTable != null ? mTable : EmptyArray.INT,
	mSize, ~idx, key);
	mSize++;

	return key;
	}
	}

	/**
	* Looks up a key in the table.
	*
	* @return The key from this table or INVALID_KEY if the id is not found.
	*/
	public int getKey(byte id) {
	assertConsistency();

	final int idx = binarySearch(id);
	if (idx >= 0) {
	return mTable[idx];
	} else {
	return INVALID_KEY;
	}
	}

	/**
	* Get the value for the given key and offset from that key.
	*
	* @param key A key as obtained from getKey or getOrAddKey.
	* @param value The value to set.
	*/
	public long getValue(int key) {
	return getValue(key, 0);
	}

	/**
	* Get the value for the given key and offset from that key.
	*
	* @param key A key as obtained from getKey or getOrAddKey.
	* @param index The offset from that key. Must be less than the count
	* provided to getOrAddKey when the space was allocated.
	* @param value The value to set.
	*
	* @return the value, or 0 in case of an error
	*/
	public long getValue(int key, int index) {
	assertConsistency();

	try {
	final long[] array = mParent.mLongs.get(getArrayFromKey(key));
	return array[getIndexFromKey(key) + index];
	} catch (IndexOutOfBoundsException ex) {
	logOrThrow("key=0x" + Integer.toHexString(key)
	+ " index=" + index + " -- " + dumpInternalState(), ex);
	return 0;
	}
	}

	/**
	* Set the value for the given id at offset 0 from that id.
	* If the id is not found, return 0 instead.
	*
	* @param id The id of the item.
	*/
	public long getValueForId(byte id) {
	return getValueForId(id, 0);
	}

	/**
	* Set the value for the given id and index offset from that id.
	* If the id is not found, return 0 instead.
	*
	* @param id The id of the item.
	* @param index The offset from that key. Must be less than the count
	* provided to getOrAddKey when the space was allocated.
	*/
	public long getValueForId(byte id, int index) {
	assertConsistency();

	final int idx = binarySearch(id);
	if (idx >= 0) {
	final int key = mTable[idx];
	try {
	final long[] array = mParent.mLongs.get(getArrayFromKey(key));
	return array[getIndexFromKey(key) + index];
	} catch (IndexOutOfBoundsException ex) {
	logOrThrow("id=0x" + Integer.toHexString(id) + " idx=" + idx
	+ " key=0x" + Integer.toHexString(key) + " index=" + index
	+ " -- " + dumpInternalState(), ex);
	return 0;
	}
	} else {
	return 0;
	}
	}

	/**
	* Return the raw storage long[] for the given key.
	*/
	public long[] getArrayForKey(int key) {
	assertConsistency();

	return mParent.mLongs.get(getArrayFromKey(key));
	}

	/**
	* Set the value for the given key and offset from that key.
	*
	* @param key A key as obtained from getKey or getOrAddKey.
	* @param value The value to set.
	*/
	public void setValue(int key, long value) {
	setValue(key, 0, value);
	}

	/**
	* Set the value for the given key and offset from that key.
	*
	* @param key A key as obtained from getKey or getOrAddKey.
	* @param index The offset from that key. Must be less than the count
	* provided to getOrAddKey when the space was allocated.
	* @param value The value to set.
	*/
	public void setValue(int key, int index, long value) {
	assertConsistency();

	if (value < 0) {
	logOrThrow("can't store negative values"
	+ " key=0x" + Integer.toHexString(key)
	+ " index=" + index + " value=" + value
	+ " -- " + dumpInternalState());
	return;
	}

	try {
	final long[] array = mParent.mLongs.get(getArrayFromKey(key));
	array[getIndexFromKey(key) + index] = value;
	} catch (IndexOutOfBoundsException ex) {
	logOrThrow("key=0x" + Integer.toHexString(key)
	+ " index=" + index + " value=" + value
	+ " -- " + dumpInternalState(), ex);
	return;
	}
	}

	/**
	* Clear out the table, and reset the sequence numbers so future writes
	* without allocations will assert.
	*/
	public void resetTable() {
	// Clear out our table.
	mTable = null;
	mSize = 0;

	// Reset our sequence number. This will make all read/write calls
	// start to fail, and then when we re-allocate it will be re-synced
	// to that of mParent.
	mSequence = mParent.mSequence;
	}

	/**
	* Write the keys stored in the table to the parcel. The parent must
	* be separately written. Does not save the actual data.
	*/
	public void writeToParcel(Parcel out) {
	out.writeInt(mSequence);
	out.writeInt(mSize);
	for (int i=0; i<mSize; i++) {
	out.writeInt(mTable[i]);
	}
	}

	/**
	* Read the keys from the parcel. The parent (with its long array) must
	* have been previously initialized.
	*/
	public boolean readFromParcel(Parcel in) {
	// Read the state
	mSequence = in.readInt();
	mSize = in.readInt();
	if (mSize != 0) {
	mTable = new int[mSize];
	for (int i=0; i<mSize; i++) {
	mTable[i] = in.readInt();
	}
	} else {
	mTable = null;
	}

	// Make sure we're all healthy
	if (validateKeys(true)) {
	return true;
	} else {
	// Clear it out
	mSize = 0;
	mTable = null;
	return false;
	}
	}

	/**
	* Return the number of keys that have been added to this Table.
	*/
	public int getKeyCount() {
	return mSize;
	}

	/**
	* Get the key at the given index in our table.
	*/
	public int getKeyAt(int i) {
	return mTable[i];
	}

	/**
	* Throw an exception if one of a variety of internal consistency checks fails.
	*/
	private void assertConsistency() {
	// Something with this checking isn't working and is triggering
	// more problems than it's helping to debug.
	// Original bug: b/27045736
	// New bug: b/27960286
	if (false) {
	// Assert that our sequence number matches mParent's. If it isn't that means
	// we have been reset and our. If our sequence is UNITIALIZED_SEQUENCE, then
	// it's possible that everything is working fine and we just haven't been
	// written to since the last resetTable().
	if (mSequence != mParent.mSequence) {
	if (mSequence < mParent.mSequence) {
	logOrThrow("Sequence mismatch. SparseMappingTable.reset()"
	+ " called but not Table.resetTable() -- "
	+ dumpInternalState());
	return;
	} else if (mSequence > mParent.mSequence) {
	logOrThrow("Sequence mismatch. Table.resetTable()"
	+ " called but not SparseMappingTable.reset() -- "
	+ dumpInternalState());
	return;
	}
	}
	}
	}

	/**
	* Finds the 'id' inside the array of length size (physical size of the array
	* is not used).
	*
	* @return The index of the array, or the bitwise not (~index) of where it
	* would go if you wanted to insert 'id' into the array.
	*/
	private int binarySearch(byte id) {
	int lo = 0;
	int hi = mSize - 1;

	while (lo <= hi) {
	int mid = (lo + hi) >>> 1;
	byte midId = (byte)((mTable[mid] >> ID_SHIFT) & ID_MASK);

	if (midId < id) {
	lo = mid + 1;
	} else if (midId > id) {
	hi = mid - 1;
	} else {
	return mid; // id found
	}
	}
	return ~lo; // id not present
	}

	/**
	* Check that all the keys are valid locations in the long arrays.
	*
	* If any aren't, log it and return false. Else return true.
	*/
	private boolean validateKeys(boolean log) {
	ArrayList<long[]> longs = mParent.mLongs;
	final int longsSize = longs.size();

	final int N = mSize;
	for (int i=0; i<N; i++) {
	final int key = mTable[i];
	final int arrayIndex = getArrayFromKey(key);
	final int index = getIndexFromKey(key);
	if (arrayIndex >= longsSize \|\| index >= longs.get(arrayIndex).length) {
	if (log) {
	Slog.w(TAG, "Invalid stats at index " + i + " -- " + dumpInternalState());
	}
	return false;
	}
	}

	return true;
	}

	public String dumpInternalState() {
	StringBuilder sb = new StringBuilder();
	sb.append("SparseMappingTable.Table{mSequence=");
	sb.append(mSequence);
	sb.append(" mParent.mSequence=");
	sb.append(mParent.mSequence);
	sb.append(" mParent.mLongs.size()=");
	sb.append(mParent.mLongs.size());
	sb.append(" mSize=");
	sb.append(mSize);
	sb.append(" mTable=");
	if (mTable == null) {
	sb.append("null");
	} else {
	final int N = mTable.length;
	sb.append('[');
	for (int i=0; i<N; i++) {
	final int key = mTable[i];
	sb.append("0x");
	sb.append(Integer.toHexString((key >> ID_SHIFT) & ID_MASK));
	sb.append("/0x");
	sb.append(Integer.toHexString((key >> ARRAY_SHIFT) & ARRAY_MASK));
	sb.append("/0x");
	sb.append(Integer.toHexString((key >> INDEX_SHIFT) & INDEX_MASK));
	if (i != N-1) {
	sb.append(", ");
	}
	}
	sb.append(']');
	}
	sb.append(" clazz=");
	sb.append(getClass().getName());
	sb.append('}');

	return sb.toString();
	}
	}

	public SparseMappingTable() {
	mLongs.add(new long[ARRAY_SIZE]);
	}

	/**
	* Wipe out all the data.
	*/
	public void reset() {
	// Clear out mLongs, and prime it with a new array of data
	mLongs.clear();
	mLongs.add(new long[ARRAY_SIZE]);
	mNextIndex = 0;

	// Increment out sequence counter, because all of the tables will
	// now be out of sync with the data.
	mSequence++;
	}

	/**
	* Write the data arrays to the parcel.
	*/
	public void writeToParcel(Parcel out) {
	out.writeInt(mSequence);
	out.writeInt(mNextIndex);
	final int N = mLongs.size();
	out.writeInt(N);
	for (int i=0; i<N-1; i++) {
	final long[] array = mLongs.get(i);
	out.writeInt(array.length);
	writeCompactedLongArray(out, array, array.length);
	}
	// save less for the last one. upon re-loading they'll just start a new array.
	final long[] lastLongs = mLongs.get(N-1);
	out.writeInt(mNextIndex);
	writeCompactedLongArray(out, lastLongs, mNextIndex);
	}

	/**
	* Read the data arrays from the parcel.
	*/
	public void readFromParcel(Parcel in) {
	mSequence = in.readInt();
	mNextIndex = in.readInt();

	mLongs.clear();
	final int N = in.readInt();
	for (int i=0; i<N; i++) {
	final int size = in.readInt();
	final long[] array = new long[size];
	readCompactedLongArray(in, array, size);
	mLongs.add(array);
	}
	// Verify that last array's length is consistent with writeToParcel
	if (N > 0 && mLongs.get(N - 1).length != mNextIndex) {
	EventLog.writeEvent(0x534e4554, "73252178", -1, "");
	throw new IllegalStateException("Expected array of length " + mNextIndex + " but was "
	+ mLongs.get(N - 1).length);
	}
	}

	/**
	* Return a string for debugging.
	*/
	public String dumpInternalState(boolean includeData) {
	final StringBuilder sb = new StringBuilder();
	sb.append("SparseMappingTable{");
	sb.append("mSequence=");
	sb.append(mSequence);
	sb.append(" mNextIndex=");
	sb.append(mNextIndex);
	sb.append(" mLongs.size=");
	final int N = mLongs.size();
	sb.append(N);
	sb.append("\n");
	if (includeData) {
	for (int i=0; i<N; i++) {
	final long[] array = mLongs.get(i);
	for (int j=0; j<array.length; j++) {
	if (i == N-1 && j == mNextIndex) {
	break;
	}
	sb.append(String.format(" %4d %d 0x%016x %-19d\n", i, j, array[j], array[j]));
	}
	}
	}
	sb.append("}");
	return sb.toString();
	}

	/**
	* Write the long array to the parcel in a compacted form. Does not allow negative
	* values in the array.
	*/
	private static void writeCompactedLongArray(Parcel out, long[] array, int num) {
	for (int i=0; i<num; i++) {
	long val = array[i];
	if (val < 0) {
	Slog.w(TAG, "Time val negative: " + val);
	val = 0;
	}
	if (val <= Integer.MAX_VALUE) {
	out.writeInt((int)val);
	} else {
	int top = ~((int)((val>>32)&0x7fffffff));
	int bottom = (int)(val&0x0ffffffffL);
	out.writeInt(top);
	out.writeInt(bottom);
	}
	}
	}

	/**
	* Read the compacted array into the long[].
	*/
	private static void readCompactedLongArray(Parcel in, long[] array, int num) {
	final int alen = array.length;
	if (num > alen) {
	logOrThrow("bad array lengths: got " + num + " array is " + alen);
	return;
	}
	int i;
	for (i=0; i<num; i++) {
	int val = in.readInt();
	if (val >= 0) {
	array[i] = val;
	} else {
	int bottom = in.readInt();
	array[i] = (((long)~val)<<32) \| bottom;
	}
	}
	while (i < alen) {
	array[i] = 0;
	i++;
	}
	}

	/**
	* Extract the id from a key.
	*/
	public static byte getIdFromKey(int key) {
	return (byte)((key >> ID_SHIFT) & ID_MASK);
	}

	/**
	* Gets the index of the array in the list of arrays.
	*
	* Not to be confused with getIndexFromKey.
	*/
	public static int getArrayFromKey(int key) {
	return (key >> ARRAY_SHIFT) & ARRAY_MASK;
	}

	/**
	* Gets the index of a value in a long[].
	*
	* Not to be confused with getArrayFromKey.
	*/
	public static int getIndexFromKey(int key) {
	return (key >> INDEX_SHIFT) & INDEX_MASK;
	}

	/**
	* Do a Slog.wtf or throw an exception (thereby crashing the system process if
	* this is a debug build.)
	*/
	private static void logOrThrow(String message) {
	logOrThrow(message, new RuntimeException("Stack trace"));
	}

	/**
	* Do a Slog.wtf or throw an exception (thereby crashing the system process if
	* this is an eng build.)
	*/
	private static void logOrThrow(String message, Throwable th) {
	Slog.e(TAG, message, th);
	if (Build.TYPE.equals("eng")) {
	throw new RuntimeException(message, th);
	}
	}
	}