| /* |
| * 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 |
| }; |
| } |