ojluni/src/main/java/sun/text/IntHashtable.java - platform/libcore - Git at Google

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