J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 1998-2002 Sun Microsystems, Inc. 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. Sun designates this |
| 8 | * particular file as subject to the "Classpath" exception as provided |
| 9 | * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 | * have any 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 | |
| 31 | package 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 | */ |
| 39 | public 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 = (int)(result * scrambler + 1); |
| 126 | result += keyList[i]; |
| 127 | } |
| 128 | for (int i = 0; i < values.length; ++i) { |
| 129 | result = (int)(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 = (int[]) values.clone(); |
| 139 | keyList = (int[])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 | } |