| Frames | No Frames |
1: /* ObjectIdentityMapToInt.java -- Helper class for faster serialization 2: Copyright (C) 2006 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package gnu.java.io; 40: 41: /** 42: * This class provides a map from Object to non-negative int values. 43: * Objects are considered equal only if their references are equal. 44: * 45: * This can be used to equip objects with an integer id. This class 46: * is implemented to use as little memory as possible, particularly 47: * not to create hashtable buckets and Integer instances for each 48: * mapping. 49: * 50: * @author Fridtjof Siebert (siebert@aicas.com) 51: */ 52: public class ObjectIdentityMap2Int 53: { 54: 55: 56: /** 57: * Prime numbers used as size of array. We need the size to be a 58: * prime number since the delta used for conflict resulution must 59: * not have any common divisors with the length. 60: */ 61: private static final int[] PRIMES = { 62: 0x1f, 63: 0x3d, 64: 0x7f, 65: 0xfb, 66: 0x1fd, 67: 0x3fd, 68: 0x7f7, 69: 0xffd, 70: 0x1fff, 71: 0x3ffd, 72: 0x7fed, 73: 0xfff1, 74: 0x1ffff, 75: 0x3fffb, 76: 0x7ffff, 77: 0xffffd, 78: 0x1ffff7, 79: 0x3ffffd, 80: 0x7ffff1, 81: 0xfffffd, 82: 0x1ffffd9, 83: 0x3fffffb, 84: 0x7ffffd9, 85: 0xfffffc7, 86: 0x1ffffffd, 87: 0x3fffffdd, 88: 0x7fffffff}; 89: 90: 91: /** 92: * Object to be used instead of "null" 93: */ 94: private static final Object NIL = new Object(); 95: 96: 97: /** 98: * The objects in this map: 99: * 100: * invariant 101: * objectTable.size == PRIMES[cap] 102: */ 103: private Object[] objectTable; 104: 105: 106: /** 107: * The corresponding integer ids. 108: * 109: * invariant 110: * intTable.size == PRIMES[cap] 111: */ 112: private int[] intTable; 113: 114: 115: /** 116: * The number of entries in this map. 117: * 118: * invariant 119: * size < limit 120: */ 121: private int size = 0; 122: 123: 124: /** 125: * The index in primes of the size of the tables. 126: */ 127: private int cap = 0; 128: 129: 130: /** 131: * The limit for size at which the table size is increased. 132: * 133: * invariant 134: * limit = PRIMES[cap] / 4 * 3; 135: */ 136: private int limit = 0; 137: 138: 139: /** 140: * Constructs an empty <code>ObjectIdentityMap2Int</code>. 141: */ 142: public ObjectIdentityMap2Int() 143: { 144: alloc(0); 145: } 146: 147: 148: /** 149: * Helper function to alloc the object and int array for the given 150: * capacity. Set limit, reset size to 0. 151: * 152: * No elements will be stored in the newly allocated arrays. 153: * 154: * @param c the capacity: this is an index in PRIMES, PRIMES[c] 155: * gives the size of the arrays. 156: * 157: * @throws InternalError if c >= PRIMES.length (in this case, a 158: * normal Hashtable would throw an OutOfMemoryError or a 159: * NegativeArraySizeException since the array size exceeds the range 160: * of positive integers). 161: */ 162: private void alloc(int c) 163: { 164: if (c >= PRIMES.length) 165: throw new InternalError("Hash table size overflow"); 166: 167: cap = c; 168: int len = PRIMES[c]; 169: objectTable = new Object[len]; 170: intTable = new int[len]; 171: limit = len / 4 * 3; 172: 173: size = 0; 174: } 175: 176: 177: /** 178: * Add a mapping to this Map. 179: * 180: * ensures 181: * (get(o) == i); 182: * 183: * @param o object reference or null that is to be mapped. 184: * 185: * @param i the integer id to be associated with o 186: * 187: * @throws IllegalArgumentException if i<0 188: * 189: * @throws InternalError if hash tables has grown to more then 190: * 0x7fffffff entries (ie., size >= 0x7fffffff*3/4). 191: */ 192: public void put(Object o, int i) 193: { 194: if (i < 0) 195: throw new IllegalArgumentException("int argument must be postive: "+i); 196: 197: o = (o == null) ? NIL : o; 198: int s = slot(o); 199: Object[] ot = objectTable; 200: intTable[s] = i; 201: if (objectTable[s] == null) 202: { 203: objectTable[s] = o; 204: size++; 205: if (size >= limit) 206: { 207: rehash(); 208: } 209: } 210: } 211: 212: 213: /** 214: * Helper function to find the index of a free or existing slot for 215: * object o 216: * 217: * ensure 218: * ((objectTable[result] != null) IMPLIES (objectTable[result] == o)); 219: * 220: * @param o an object, must not be null. 221: * 222: * @return an index of o 223: */ 224: private int slot(Object o) 225: { 226: Object[] ot = objectTable; 227: int hc = System.identityHashCode(o); 228: int len = ot.length; 229: int result = hc % len; 230: result = result < 0 ? -result : result; 231: int delta = 16 - (hc & 15); 232: Object existing = ot[result]; 233: while ((existing != null) && (existing != o)) 234: { 235: result += delta; 236: if (result >= len) 237: result -= len; 238: existing = ot[result]; 239: } 240: return result; 241: } 242: 243: 244: /** 245: * Helper function for put() to increaes the capacity of this table 246: * to the next size (approx. double the size). Keep the mapping and 247: * the size unchanged. 248: * 249: * ensure 250: * (cap == \old cap+1); 251: */ 252: private void rehash() 253: { 254: Object[] ot = objectTable; 255: int [] it = intTable; 256: alloc(cap + 1); 257: 258: for (int i = 0; i < ot.length; i++) 259: put(ot[i], it[i]); 260: } 261: 262: 263: /** 264: * Obtain an element from this map 265: * 266: * @param o an object or null 267: * 268: * @return the corresponding integer id for o or -1 if o has not 269: * been put into this map. 270: */ 271: public int get(Object o) 272: { 273: o = (o == null) ? NIL : o; 274: int s = slot(o); 275: return objectTable[s] == null ? -1 : intTable[s]; 276: } 277: 278: /** 279: * Clear this map 280: * 281: * ensures 282: * ((size == 0) && \forall Object o: get(o) == -1) 283: */ 284: public void clear() 285: { 286: Object[] ot = objectTable; 287: size = 0; 288: for (int i = 0; i < ot.length; i++) 289: ot[i] = null; 290: } 291: 292: }