001: /*
002: * Copyright 1998-2002 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: /*
027: * (C) Copyright Taligent, Inc. 1996,1997 - All Rights Reserved
028: * (C) Copyright IBM Corp. 1996, 1997 - All Rights Reserved
029: */
030:
031: package sun.text;
032:
033: /** Simple internal class for doing hash mapping. Much, much faster than the
034: * standard Hashtable for integer to integer mappings,
035: * and doesn't require object creation.<br>
036: * If a key is not found, the defaultValue is returned.
037: * Note: the keys are limited to values above Integer.MIN_VALUE+1.<br>
038: */
039: public final class IntHashtable {
040:
041: public IntHashtable() {
042: initialize(3);
043: }
044:
045: public IntHashtable(int initialSize) {
046: initialize(leastGreaterPrimeIndex((int) (initialSize / HIGH_WATER_FACTOR)));
047: }
048:
049: public int size() {
050: return count;
051: }
052:
053: public boolean isEmpty() {
054: return count == 0;
055: }
056:
057: public void put(int key, int value) {
058: if (count > highWaterMark) {
059: rehash();
060: }
061: int index = find(key);
062: if (keyList[index] <= MAX_UNUSED) { // deleted or empty
063: keyList[index] = key;
064: ++count;
065: }
066: values[index] = value; // reset value
067: }
068:
069: public int get(int key) {
070: return values[find(key)];
071: }
072:
073: public void remove(int key) {
074: int index = find(key);
075: if (keyList[index] > MAX_UNUSED) { // neither deleted nor empty
076: keyList[index] = DELETED; // set to deleted
077: values[index] = defaultValue; // set to default
078: --count;
079: if (count < lowWaterMark) {
080: rehash();
081: }
082: }
083: }
084:
085: public int getDefaultValue() {
086: return defaultValue;
087: }
088:
089: public void setDefaultValue(int newValue) {
090: defaultValue = newValue;
091: rehash();
092: }
093:
094: public boolean equals(Object that) {
095: if (that.getClass() != this .getClass())
096: return false;
097:
098: IntHashtable other = (IntHashtable) that;
099: if (other.size() != count || other.defaultValue != defaultValue) {
100: return false;
101: }
102: for (int i = 0; i < keyList.length; ++i) {
103: int key = keyList[i];
104: if (key > MAX_UNUSED && other.get(key) != values[i])
105: return false;
106: }
107: return true;
108: }
109:
110: public int hashCode() {
111: // NOTE: This function isn't actually used anywhere in this package, but it's here
112: // in case this class is ever used to make sure we uphold the invariants about
113: // hashCode() and equals()
114:
115: // WARNING: This function hasn't undergone rigorous testing to make sure it actually
116: // gives good distribution. We've eyeballed the results, and they appear okay, but
117: // you copy this algorithm (or these seed and multiplier values) at your own risk.
118: // --rtg 8/17/99
119:
120: int result = 465; // an arbitrary seed value
121: int scrambler = 1362796821; // an arbitrary multiplier.
122: for (int i = 0; i < keyList.length; ++i) {
123: // this line just scrambles the bits as each value is added into the
124: // has value. This helps to make sure we affect all the bits and that
125: // the same values in a different order will produce a different hash value
126: result = (int) (result * scrambler + 1);
127: result += keyList[i];
128: }
129: for (int i = 0; i < values.length; ++i) {
130: result = (int) (result * scrambler + 1);
131: result += values[i];
132: }
133: return result;
134: }
135:
136: public Object clone() 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(
221: "key can't be less than 0xFFFFFFFE");
222: int firstDeleted = -1; // assume invalid index
223: int index = (key ^ 0x4000000) % keyList.length;
224: if (index < 0)
225: index = -index; // positive only
226: int jump = 0; // lazy evaluate
227: while (true) {
228: int tableHash = keyList[index];
229: if (tableHash == key) { // quick check
230: return index;
231: } else if (tableHash > MAX_UNUSED) { // neither correct nor unused
232: // ignore
233: } else if (tableHash == EMPTY) { // empty, end o' the line
234: if (firstDeleted >= 0) {
235: index = firstDeleted; // reset if had deleted slot
236: }
237: return index;
238: } else if (firstDeleted < 0) { // remember first deleted
239: firstDeleted = index;
240: }
241: if (jump == 0) { // lazy compute jump
242: jump = (key % (keyList.length - 1));
243: if (jump < 0)
244: jump = -jump;
245: ++jump;
246: }
247:
248: index = (index + jump) % keyList.length;
249: if (index == firstDeleted) {
250: // We've searched all entries for the given key.
251: return index;
252: }
253: }
254: }
255:
256: private static int leastGreaterPrimeIndex(int source) {
257: int i;
258: for (i = 0; i < PRIMES.length; ++i) {
259: if (source < PRIMES[i]) {
260: break;
261: }
262: }
263: return (i == 0) ? 0 : (i - 1);
264: }
265:
266: // This list is the result of buildList below. Can be tuned for different
267: // performance/storage characteristics.
268: private static final int[] PRIMES = { 17, 37, 67, 131, 257, 521,
269: 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101,
270: 262147, 524309, 1048583, 2097169, 4194319, 8388617,
271: 16777259, 33554467, 67108879, 134217757, 268435459,
272: 536870923, 1073741827, 2147483647 };
273: }
|