1af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes/* 2af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * Copyright (C) 2010 The Android Open Source Project 3af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * 4af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * Licensed under the Apache License, Version 2.0 (the "License"); 5af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * you may not use this file except in compliance with the License. 6af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * You may obtain a copy of the License at 7af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * 8af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * http://www.apache.org/licenses/LICENSE-2.0 9af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * 10af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * Unless required by applicable law or agreed to in writing, software 11af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * distributed under the License is distributed on an "AS IS" BASIS, 12af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * See the License for the specific language governing permissions and 14af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * limitations under the License. 15af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes */ 16af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 17af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughespackage java.io; 18af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 19af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes/** 20af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * A specialization of IdentityHashMap<Object, int> for use when serializing objects. 21af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * We need to assign each object we write an int 'handle' (densely packed but not starting 22af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * at zero), and use the same handle any time we write the same object again. 23af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes */ 24af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughesfinal class SerializationHandleMap { 25af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes /* Default load factor of 0.75; */ 26af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private static final int LOAD_FACTOR = 7500; 27af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 28af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private Object[] keys; 29af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private int[] values; 30af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 31af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes /* Actual number of key-value pairs. */ 32af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private int size; 33af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 34af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes /* Maximum number of elements that can be put in this map before having to rehash. */ 35af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private int threshold; 36af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 37af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes public SerializationHandleMap() { 38af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes this.size = 0; 39af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes this.threshold = 21; // Copied from IdentityHashMap. 40af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int arraySize = (int) (((long) threshold * 10000) / LOAD_FACTOR); 41af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes resizeArrays(arraySize); 42af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 43af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 44af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private void resizeArrays(int newSize) { 45af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes Object[] oldKeys = keys; 46af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int[] oldValues = values; 47af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 48af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes this.keys = new Object[newSize]; 49af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes this.values = new int[newSize]; 50af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 51af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (oldKeys != null) { 52af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes for (int i = 0; i < oldKeys.length; ++i) { 53af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes Object key = oldKeys[i]; 54af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int value = oldValues[i]; 55af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int index = findIndex(key, keys); 56af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes keys[index] = key; 57af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes values[index] = value; 58af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 59af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 60af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 61af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 62af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes public int get(Object key) { 63af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int index = findIndex(key, keys); 64af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (keys[index] == key) { 65af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes return values[index]; 66af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 67af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes return -1; 68af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 69af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 70af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes /** 71af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * Returns the index where the key is found at, or the index of the next 72af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * empty spot if the key is not found in this table. 73af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes */ 74af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private int findIndex(Object key, Object[] array) { 75af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int length = array.length; 76af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int index = getModuloHash(key, length); 77af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int last = (index + length - 1) % length; 78af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes while (index != last) { 79af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (array[index] == key || array[index] == null) { 80af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes /* 81af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * Found the key, or the next empty spot (which means key is not 82af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes * in the table) 83af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes */ 84af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes break; 85af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 86af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes index = (index + 1) % length; 87af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 88af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes return index; 89af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 90af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 91af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private int getModuloHash(Object key, int length) { 92af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes return (System.identityHashCode(key) & 0x7FFFFFFF) % length; 93af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 94af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 95af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes public int put(Object key, int value) { 96af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes Object _key = key; 97af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int _value = value; 98af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 99af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int index = findIndex(_key, keys); 100af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 101af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes // if the key doesn't exist in the table 102af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (keys[index] != _key) { 103af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (++size > threshold) { 104af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes rehash(); 105af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes index = findIndex(_key, keys); 106af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 107af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes // insert the key and assign the value to -1 initially 108af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes keys[index] = _key; 109af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes values[index] = -1; 110af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 111af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 112af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes // insert value to where it needs to go, return the old value 113af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int result = values[index]; 114af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes values[index] = _value; 115af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes return result; 116af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 117af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 118af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes private void rehash() { 119af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int newSize = keys.length * 2; 120af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes resizeArrays(newSize); 121af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes threshold = (int) ((long) (keys.length) * LOAD_FACTOR / 10000); 122af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 123af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 124af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes public int remove(Object key) { 125af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes boolean hashedOk; 126af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int index, next, hash; 127af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int result; 128af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes Object object; 129af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes index = next = findIndex(key, keys); 130af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 131af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (keys[index] != key) { 132af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes return -1; 133af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 134af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 135af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes // store the value for this key 136af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes result = values[index]; 137af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 138af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes // shift the following elements up if needed 139af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes // until we reach an empty spot 140af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes int length = keys.length; 141af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes while (true) { 142af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes next = (next + 2) % length; 143af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes object = keys[next]; 144af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (object == null) { 145af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes break; 146af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 147af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 148af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes hash = getModuloHash(object, length); 149af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes hashedOk = hash > index; 150af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (next < index) { 151af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes hashedOk = hashedOk || (hash <= next); 152af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } else { 153af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes hashedOk = hashedOk && (hash <= next); 154af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 155af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes if (!hashedOk) { 156af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes keys[index] = object; 157af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes values[index] = values[next]; 158af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes index = next; 159af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 160af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 161af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes size--; 162af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 163af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes // clear both the key and the value 164af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes keys[index] = null; 165af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes values[index] = -1; 166af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 167af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes return result; 168af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 169af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes 170af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes public boolean isEmpty() { 171af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes return size == 0; 172af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes } 173af338385e1cfb40a856bf11d8ddd682ea7602164Elliott Hughes} 174