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