/* * Copyright (c) 1998, 2002, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ /* * (C) Copyright Taligent, Inc. 1996,1997 - All Rights Reserved * (C) Copyright IBM Corp. 1996, 1997 - All Rights Reserved */ package sun.text; /** Simple internal class for doing hash mapping. Much, much faster than the * standard Hashtable for integer to integer mappings, * and doesn't require object creation.<br> * If a key is not found, the defaultValue is returned. * Note: the keys are limited to values above Integer.MIN_VALUE+1.<br> */public final class IntHashtable { public IntHashtable () { initialize(3); } public IntHashtable (int initialSize) { initialize(leastGreaterPrimeIndex((int)(initialSize/HIGH_WATER_FACTOR))); } public int size() { return count; } public boolean isEmpty() { return count == 0; } public void put(int key, int value) { if (count > highWaterMark) { rehash(); } int index = find(key); if (keyList[index] <= MAX_UNUSED) { // deleted or empty keyList[index] = key; ++count; } values[index] = value; // reset value } public int get(int key) { return values[find(key)]; } public void remove(int key) { int index = find(key); if (keyList[index] > MAX_UNUSED) { // neither deleted nor empty keyList[index] = DELETED; // set to deleted values[index] = defaultValue; // set to default --count; if (count < lowWaterMark) { rehash(); } } } public int getDefaultValue() { return defaultValue; } public void setDefaultValue(int newValue) { defaultValue = newValue; rehash(); } public boolean equals (Object that) { if (that.getClass() != this.getClass()) return false; IntHashtable other = (IntHashtable) that; if (other.size() != count || other.defaultValue != defaultValue) { return false; } for (int i = 0; i < keyList.length; ++i) { int key = keyList[i]; if (key > MAX_UNUSED && other.get(key) != values[i]) return false; } return true; } public int hashCode() { // NOTE: This function isn't actually used anywhere in this package, but it's here // in case this class is ever used to make sure we uphold the invariants about // hashCode() and equals() // WARNING: This function hasn't undergone rigorous testing to make sure it actually // gives good distribution. We've eyeballed the results, and they appear okay, but // you copy this algorithm (or these seed and multiplier values) at your own risk. // --rtg 8/17/99 int result = 465; // an arbitrary seed value int scrambler = 1362796821; // an arbitrary multiplier. for (int i = 0; i < keyList.length; ++i) { // this line just scrambles the bits as each value is added into the // has value. This helps to make sure we affect all the bits and that // the same values in a different order will produce a different hash value result = (int)(result * scrambler + 1); result += keyList[i]; } for (int i = 0; i < values.length; ++i) { result = (int)(result * scrambler + 1); result += values[i]; } return result; } public Object clone () throws CloneNotSupportedException { IntHashtable result = (IntHashtable) super.clone(); values = (int[]) values.clone(); keyList = (int[])keyList.clone(); return result; } // =======================PRIVATES============================ private int defaultValue = 0; // the tables have to have prime-number lengths. Rather than compute // primes, we just keep a table, with the current index we are using. private int primeIndex; // highWaterFactor determines the maximum number of elements before // a rehash. Can be tuned for different performance/storage characteristics. private static final float HIGH_WATER_FACTOR = 0.4F; private int highWaterMark; // lowWaterFactor determines the minimum number of elements before // a rehash. Can be tuned for different performance/storage characteristics. private static final float LOW_WATER_FACTOR = 0.0F; private int lowWaterMark; private int count; // we use two arrays to minimize allocations private int[] values; private int[] keyList; private static final int EMPTY = Integer.MIN_VALUE; private static final int DELETED = EMPTY + 1; private static final int MAX_UNUSED = DELETED; private void initialize (int primeIndex) { if (primeIndex < 0) { primeIndex = 0; } else if (primeIndex >= PRIMES.length) { System.out.println("TOO BIG"); primeIndex = PRIMES.length - 1; // throw new java.util.IllegalArgumentError(); } this.primeIndex = primeIndex; int initialSize = PRIMES[primeIndex]; values = new int[initialSize]; keyList = new int[initialSize]; for (int i = 0; i < initialSize; ++i) { keyList[i] = EMPTY; values[i] = defaultValue; } count = 0; lowWaterMark = (int)(initialSize * LOW_WATER_FACTOR); highWaterMark = (int)(initialSize * HIGH_WATER_FACTOR); } private void rehash() { int[] oldValues = values; int[] oldkeyList = keyList; int newPrimeIndex = primeIndex; if (count > highWaterMark) { ++newPrimeIndex; } else if (count < lowWaterMark) { newPrimeIndex -= 2; } initialize(newPrimeIndex); for (int i = oldValues.length - 1; i >= 0; --i) { int key = oldkeyList[i]; if (key > MAX_UNUSED) { putInternal(key, oldValues[i]); } } } public void putInternal (int key, int value) { int index = find(key); if (keyList[index] < MAX_UNUSED) { // deleted or empty keyList[index] = key; ++count; } values[index] = value; // reset value } private int find (int key) { if (key <= MAX_UNUSED) throw new IllegalArgumentException("key can't be less than 0xFFFFFFFE"); int firstDeleted = -1; // assume invalid index int index = (key ^ 0x4000000) % keyList.length; if (index < 0) index = -index; // positive only int jump = 0; // lazy evaluate while (true) { int tableHash = keyList[index]; if (tableHash == key) { // quick check return index; } else if (tableHash > MAX_UNUSED) { // neither correct nor unused // ignore } else if (tableHash == EMPTY) { // empty, end o' the line if (firstDeleted >= 0) { index = firstDeleted; // reset if had deleted slot } return index; } else if (firstDeleted < 0) { // remember first deleted firstDeleted = index; } if (jump == 0) { // lazy compute jump jump = (key % (keyList.length - 1)); if (jump < 0) jump = -jump; ++jump; } index = (index + jump) % keyList.length; if (index == firstDeleted) { // We've searched all entries for the given key. return index; } } } private static int leastGreaterPrimeIndex(int source) { int i; for (i = 0; i < PRIMES.length; ++i) { if (source < PRIMES[i]) { break; } } return (i == 0) ? 0 : (i - 1); } // This list is the result of buildList below. Can be tuned for different // performance/storage characteristics. private static final int[] PRIMES = { 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459, 536870923, 1073741827, 2147483647 };}
/*
* Copyright (c) 1998, 2002, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
/*
* (C) Copyright Taligent, Inc. 1996,1997 - All Rights Reserved
* (C) Copyright IBM Corp. 1996, 1997 - All Rights Reserved
*/
package sun.text;
/** Simple internal class for doing hash mapping. Much, much faster than the
* standard Hashtable for integer to integer mappings,
* and doesn't require object creation.<br>
* If a key is not found, the defaultValue is returned.
* Note: the keys are limited to values above Integer.MIN_VALUE+1.<br>
*/
public final class IntHashtable {
public IntHashtable () {
initialize(3);
}
public IntHashtable (int initialSize) {
initialize(leastGreaterPrimeIndex((int)(initialSize/HIGH_WATER_FACTOR)));
}
public int size() {
return count;
}
public boolean isEmpty() {
return count == 0;
}
public void put(int key, int value) {
if (count > highWaterMark) {
rehash();
}
int index = find(key);
if (keyList[index] <= MAX_UNUSED) { // deleted or empty
keyList[index] = key;
++count;
}
values[index] = value; // reset value
}
public int get(int key) {
return values[find(key)];
}
public void remove(int key) {
int index = find(key);
if (keyList[index] > MAX_UNUSED) { // neither deleted nor empty
keyList[index] = DELETED; // set to deleted
values[index] = defaultValue; // set to default
--count;
if (count < lowWaterMark) {
rehash();
}
}
}
public int getDefaultValue() {
return defaultValue;
}
public void setDefaultValue(int newValue) {
defaultValue = newValue;
rehash();
}
public boolean equals (Object that) {
if (that.getClass() != this.getClass()) return false;
IntHashtable other = (IntHashtable) that;
if (other.size() != count || other.defaultValue != defaultValue) {
return false;
}
for (int i = 0; i < keyList.length; ++i) {
int key = keyList[i];
if (key > MAX_UNUSED && other.get(key) != values[i])
return false;
}
return true;
}
public int hashCode() {
// NOTE: This function isn't actually used anywhere in this package, but it's here
// in case this class is ever used to make sure we uphold the invariants about
// hashCode() and equals()
// WARNING: This function hasn't undergone rigorous testing to make sure it actually
// gives good distribution. We've eyeballed the results, and they appear okay, but
// you copy this algorithm (or these seed and multiplier values) at your own risk.
// --rtg 8/17/99
int result = 465; // an arbitrary seed value
int scrambler = 1362796821; // an arbitrary multiplier.
for (int i = 0; i < keyList.length; ++i) {
// this line just scrambles the bits as each value is added into the
// has value. This helps to make sure we affect all the bits and that
// the same values in a different order will produce a different hash value
result = (int)(result * scrambler + 1);
result += keyList[i];
}
for (int i = 0; i < values.length; ++i) {
result = (int)(result * scrambler + 1);
result += values[i];
}
return result;
}
public Object clone ()
throws CloneNotSupportedException {
IntHashtable result = (IntHashtable) super.clone();
values = (int[]) values.clone();
keyList = (int[])keyList.clone();
return result;
}
// =======================PRIVATES============================
private int defaultValue = 0;
// the tables have to have prime-number lengths. Rather than compute
// primes, we just keep a table, with the current index we are using.
private int primeIndex;
// highWaterFactor determines the maximum number of elements before
// a rehash. Can be tuned for different performance/storage characteristics.
private static final float HIGH_WATER_FACTOR = 0.4F;
private int highWaterMark;
// lowWaterFactor determines the minimum number of elements before
// a rehash. Can be tuned for different performance/storage characteristics.
private static final float LOW_WATER_FACTOR = 0.0F;
private int lowWaterMark;
private int count;
// we use two arrays to minimize allocations
private int[] values;
private int[] keyList;
private static final int EMPTY = Integer.MIN_VALUE;
private static final int DELETED = EMPTY + 1;
private static final int MAX_UNUSED = DELETED;
private void initialize (int primeIndex) {
if (primeIndex < 0) {
primeIndex = 0;
} else if (primeIndex >= PRIMES.length) {
System.out.println("TOO BIG");
primeIndex = PRIMES.length - 1;
// throw new java.util.IllegalArgumentError();
}
this.primeIndex = primeIndex;
int initialSize = PRIMES[primeIndex];
values = new int[initialSize];
keyList = new int[initialSize];
for (int i = 0; i < initialSize; ++i) {
keyList[i] = EMPTY;
values[i] = defaultValue;
}
count = 0;
lowWaterMark = (int)(initialSize * LOW_WATER_FACTOR);
highWaterMark = (int)(initialSize * HIGH_WATER_FACTOR);
}
private void rehash() {
int[] oldValues = values;
int[] oldkeyList = keyList;
int newPrimeIndex = primeIndex;
if (count > highWaterMark) {
++newPrimeIndex;
} else if (count < lowWaterMark) {
newPrimeIndex -= 2;
}
initialize(newPrimeIndex);
for (int i = oldValues.length - 1; i >= 0; --i) {
int key = oldkeyList[i];
if (key > MAX_UNUSED) {
putInternal(key, oldValues[i]);
}
}
}
public void putInternal (int key, int value) {
int index = find(key);
if (keyList[index] < MAX_UNUSED) { // deleted or empty
keyList[index] = key;
++count;
}
values[index] = value; // reset value
}
private int find (int key) {
if (key <= MAX_UNUSED)
throw new IllegalArgumentException("key can't be less than 0xFFFFFFFE");
int firstDeleted = -1; // assume invalid index
int index = (key ^ 0x4000000) % keyList.length;
if (index < 0) index = -index; // positive only
int jump = 0; // lazy evaluate
while (true) {
int tableHash = keyList[index];
if (tableHash == key) { // quick check
return index;
} else if (tableHash > MAX_UNUSED) { // neither correct nor unused
// ignore
} else if (tableHash == EMPTY) { // empty, end o' the line
if (firstDeleted >= 0) {
index = firstDeleted; // reset if had deleted slot
}
return index;
} else if (firstDeleted < 0) { // remember first deleted
firstDeleted = index;
}
if (jump == 0) { // lazy compute jump
jump = (key % (keyList.length - 1));
if (jump < 0) jump = -jump;
++jump;
}
index = (index + jump) % keyList.length;
if (index == firstDeleted) {
// We've searched all entries for the given key.
return index;
}
}
}
private static int leastGreaterPrimeIndex(int source) {
int i;
for (i = 0; i < PRIMES.length; ++i) {
if (source < PRIMES[i]) {
break;
}
}
return (i == 0) ? 0 : (i - 1);
}
// This list is the result of buildList below. Can be tuned for different
// performance/storage characteristics.
private static final int[] PRIMES = {
17, 37, 67, 131, 257,
521, 1031, 2053, 4099, 8209, 16411, 32771, 65537,
131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259,
33554467, 67108879, 134217757, 268435459, 536870923, 1073741827, 2147483647
};
}