1/* 2 * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26/* 27 * (C) Copyright Taligent, Inc. 1996,1997 - All Rights Reserved 28 * (C) Copyright IBM Corp. 1996, 1997 - All Rights Reserved 29 */ 30 31package sun.text; 32 33/** Simple internal class for doing hash mapping. Much, much faster than the 34 * standard Hashtable for integer to integer mappings, 35 * and doesn't require object creation.<br> 36 * If a key is not found, the defaultValue is returned. 37 * Note: the keys are limited to values above Integer.MIN_VALUE+1.<br> 38 */ 39public final class IntHashtable { 40 41 public IntHashtable () { 42 initialize(3); 43 } 44 45 public IntHashtable (int initialSize) { 46 initialize(leastGreaterPrimeIndex((int)(initialSize/HIGH_WATER_FACTOR))); 47 } 48 49 public int size() { 50 return count; 51 } 52 53 public boolean isEmpty() { 54 return count == 0; 55 } 56 57 public void put(int key, int value) { 58 if (count > highWaterMark) { 59 rehash(); 60 } 61 int index = find(key); 62 if (keyList[index] <= MAX_UNUSED) { // deleted or empty 63 keyList[index] = key; 64 ++count; 65 } 66 values[index] = value; // reset value 67 } 68 69 public int get(int key) { 70 return values[find(key)]; 71 } 72 73 public void remove(int key) { 74 int index = find(key); 75 if (keyList[index] > MAX_UNUSED) { // neither deleted nor empty 76 keyList[index] = DELETED; // set to deleted 77 values[index] = defaultValue; // set to default 78 --count; 79 if (count < lowWaterMark) { 80 rehash(); 81 } 82 } 83 } 84 85 public int getDefaultValue() { 86 return defaultValue; 87 } 88 89 public void setDefaultValue(int newValue) { 90 defaultValue = newValue; 91 rehash(); 92 } 93 94 public boolean equals (Object that) { 95 if (that.getClass() != this.getClass()) return false; 96 97 IntHashtable other = (IntHashtable) that; 98 if (other.size() != count || other.defaultValue != defaultValue) { 99 return false; 100 } 101 for (int i = 0; i < keyList.length; ++i) { 102 int key = keyList[i]; 103 if (key > MAX_UNUSED && other.get(key) != values[i]) 104 return false; 105 } 106 return true; 107 } 108 109 public int hashCode() { 110 // NOTE: This function isn't actually used anywhere in this package, but it's here 111 // in case this class is ever used to make sure we uphold the invariants about 112 // hashCode() and equals() 113 114 // WARNING: This function hasn't undergone rigorous testing to make sure it actually 115 // gives good distribution. We've eyeballed the results, and they appear okay, but 116 // you copy this algorithm (or these seed and multiplier values) at your own risk. 117 // --rtg 8/17/99 118 119 int result = 465; // an arbitrary seed value 120 int scrambler = 1362796821; // an arbitrary multiplier. 121 for (int i = 0; i < keyList.length; ++i) { 122 // this line just scrambles the bits as each value is added into the 123 // has value. This helps to make sure we affect all the bits and that 124 // the same values in a different order will produce a different hash value 125 result = result * scrambler + 1; 126 result += keyList[i]; 127 } 128 for (int i = 0; i < values.length; ++i) { 129 result = result * scrambler + 1; 130 result += values[i]; 131 } 132 return result; 133 } 134 135 public Object clone () 136 throws CloneNotSupportedException { 137 IntHashtable result = (IntHashtable) super.clone(); 138 values = values.clone(); 139 keyList = keyList.clone(); 140 return result; 141 } 142 143 // =======================PRIVATES============================ 144 private int defaultValue = 0; 145 146 // the tables have to have prime-number lengths. Rather than compute 147 // primes, we just keep a table, with the current index we are using. 148 private int primeIndex; 149 150 // highWaterFactor determines the maximum number of elements before 151 // a rehash. Can be tuned for different performance/storage characteristics. 152 private static final float HIGH_WATER_FACTOR = 0.4F; 153 private int highWaterMark; 154 155 // lowWaterFactor determines the minimum number of elements before 156 // a rehash. Can be tuned for different performance/storage characteristics. 157 private static final float LOW_WATER_FACTOR = 0.0F; 158 private int lowWaterMark; 159 160 private int count; 161 162 // we use two arrays to minimize allocations 163 private int[] values; 164 private int[] keyList; 165 166 private static final int EMPTY = Integer.MIN_VALUE; 167 private static final int DELETED = EMPTY + 1; 168 private static final int MAX_UNUSED = DELETED; 169 170 private void initialize (int primeIndex) { 171 if (primeIndex < 0) { 172 primeIndex = 0; 173 } else if (primeIndex >= PRIMES.length) { 174 System.out.println("TOO BIG"); 175 primeIndex = PRIMES.length - 1; 176 // throw new java.util.IllegalArgumentError(); 177 } 178 this.primeIndex = primeIndex; 179 int initialSize = PRIMES[primeIndex]; 180 values = new int[initialSize]; 181 keyList = new int[initialSize]; 182 for (int i = 0; i < initialSize; ++i) { 183 keyList[i] = EMPTY; 184 values[i] = defaultValue; 185 } 186 count = 0; 187 lowWaterMark = (int)(initialSize * LOW_WATER_FACTOR); 188 highWaterMark = (int)(initialSize * HIGH_WATER_FACTOR); 189 } 190 191 private void rehash() { 192 int[] oldValues = values; 193 int[] oldkeyList = keyList; 194 int newPrimeIndex = primeIndex; 195 if (count > highWaterMark) { 196 ++newPrimeIndex; 197 } else if (count < lowWaterMark) { 198 newPrimeIndex -= 2; 199 } 200 initialize(newPrimeIndex); 201 for (int i = oldValues.length - 1; i >= 0; --i) { 202 int key = oldkeyList[i]; 203 if (key > MAX_UNUSED) { 204 putInternal(key, oldValues[i]); 205 } 206 } 207 } 208 209 public void putInternal (int key, int value) { 210 int index = find(key); 211 if (keyList[index] < MAX_UNUSED) { // deleted or empty 212 keyList[index] = key; 213 ++count; 214 } 215 values[index] = value; // reset value 216 } 217 218 private int find (int key) { 219 if (key <= MAX_UNUSED) 220 throw new IllegalArgumentException("key can't be less than 0xFFFFFFFE"); 221 int firstDeleted = -1; // assume invalid index 222 int index = (key ^ 0x4000000) % keyList.length; 223 if (index < 0) index = -index; // positive only 224 int jump = 0; // lazy evaluate 225 while (true) { 226 int tableHash = keyList[index]; 227 if (tableHash == key) { // quick check 228 return index; 229 } else if (tableHash > MAX_UNUSED) { // neither correct nor unused 230 // ignore 231 } else if (tableHash == EMPTY) { // empty, end o' the line 232 if (firstDeleted >= 0) { 233 index = firstDeleted; // reset if had deleted slot 234 } 235 return index; 236 } else if (firstDeleted < 0) { // remember first deleted 237 firstDeleted = index; 238 } 239 if (jump == 0) { // lazy compute jump 240 jump = (key % (keyList.length - 1)); 241 if (jump < 0) jump = -jump; 242 ++jump; 243 } 244 245 index = (index + jump) % keyList.length; 246 if (index == firstDeleted) { 247 // We've searched all entries for the given key. 248 return index; 249 } 250 } 251 } 252 253 private static int leastGreaterPrimeIndex(int source) { 254 int i; 255 for (i = 0; i < PRIMES.length; ++i) { 256 if (source < PRIMES[i]) { 257 break; 258 } 259 } 260 return (i == 0) ? 0 : (i - 1); 261 } 262 263 // This list is the result of buildList below. Can be tuned for different 264 // performance/storage characteristics. 265 private static final int[] PRIMES = { 266 17, 37, 67, 131, 257, 267 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 268 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259, 269 33554467, 67108879, 134217757, 268435459, 536870923, 1073741827, 2147483647 270 }; 271} 272