aboutsummaryrefslogtreecommitdiffstats
path: root/trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java
diff options
context:
space:
mode:
Diffstat (limited to 'trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java')
-rw-r--r--trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java697
1 files changed, 0 insertions, 697 deletions
diff --git a/trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java b/trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java
deleted file mode 100644
index 4aa7d23..0000000
--- a/trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java
+++ /dev/null
@@ -1,697 +0,0 @@
-/* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
- *
- * ***** BEGIN LICENSE BLOCK *****
- * Version: MPL 1.1/GPL 2.0
- *
- * The contents of this file are subject to the Mozilla Public License Version
- * 1.1 (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- * http://www.mozilla.org/MPL/
- *
- * Software distributed under the License is distributed on an "AS IS" basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the
- * License.
- *
- * The Original Code is Rhino code, released
- * May 6, 1999.
- *
- * The Initial Developer of the Original Code is
- * Netscape Communications Corporation.
- * Portions created by the Initial Developer are Copyright (C) 1997-2000
- * the Initial Developer. All Rights Reserved.
- *
- * Contributor(s):
- * Igor Bukanov
- *
- * Alternatively, the contents of this file may be used under the terms of
- * the GNU General Public License Version 2 or later (the "GPL"), in which
- * case the provisions of the GPL are applicable instead of those above. If
- * you wish to allow use of your version of this file only under the terms of
- * the GPL and not to allow others to use your version of this file under the
- * MPL, indicate your decision by deleting the provisions above and replacing
- * them with the notice and other provisions required by the GPL. If you do
- * not delete the provisions above, a recipient may use your version of this
- * file under either the MPL or the GPL.
- *
- * ***** END LICENSE BLOCK ***** */
-
-package org.mozilla.javascript;
-
-import java.io.Serializable;
-import java.io.IOException;
-import java.io.ObjectInputStream;
-import java.io.ObjectOutputStream;
-
-/**
- * Map to associate objects to integers.
- * The map does not synchronize any of its operation, so either use
- * it from a single thread or do own synchronization or perform all mutation
- * operations on one thread before passing the map to others
- *
- * @author Igor Bukanov
- *
- */
-
-public class ObjToIntMap implements Serializable
-{
- static final long serialVersionUID = -1542220580748809402L;
-
-// Map implementation via hashtable,
-// follows "The Art of Computer Programming" by Donald E. Knuth
-
-// ObjToIntMap is a copy cat of ObjToIntMap with API adjusted to object keys
-
- public static class Iterator {
-
- Iterator(ObjToIntMap master) {
- this.master = master;
- }
-
- final void init(Object[] keys, int[] values, int keyCount) {
- this.keys = keys;
- this.values = values;
- this.cursor = -1;
- this.remaining = keyCount;
- }
-
- public void start() {
- master.initIterator(this);
- next();
- }
-
- public boolean done() {
- return remaining < 0;
- }
-
- public void next() {
- if (remaining == -1) Kit.codeBug();
- if (remaining == 0) {
- remaining = -1;
- cursor = -1;
- }else {
- for (++cursor; ; ++cursor) {
- Object key = keys[cursor];
- if (key != null && key != DELETED) {
- --remaining;
- break;
- }
- }
- }
- }
-
- public Object getKey() {
- Object key = keys[cursor];
- if (key == UniqueTag.NULL_VALUE) { key = null; }
- return key;
- }
-
- public int getValue() {
- return values[cursor];
- }
-
- public void setValue(int value) {
- values[cursor] = value;
- }
-
- ObjToIntMap master;
- private int cursor;
- private int remaining;
- private Object[] keys;
- private int[] values;
- }
-
- public ObjToIntMap() {
- this(4);
- }
-
- public ObjToIntMap(int keyCountHint) {
- if (keyCountHint < 0) Kit.codeBug();
- // Table grow when number of stored keys >= 3/4 of max capacity
- int minimalCapacity = keyCountHint * 4 / 3;
- int i;
- for (i = 2; (1 << i) < minimalCapacity; ++i) { }
- power = i;
- if (check && power < 2) Kit.codeBug();
- }
-
- public boolean isEmpty() {
- return keyCount == 0;
- }
-
- public int size() {
- return keyCount;
- }
-
- public boolean has(Object key) {
- if (key == null) { key = UniqueTag.NULL_VALUE; }
- return 0 <= findIndex(key);
- }
-
- /**
- * Get integer value assigned with key.
- * @return key integer value or defaultValue if key is absent
- */
- public int get(Object key, int defaultValue) {
- if (key == null) { key = UniqueTag.NULL_VALUE; }
- int index = findIndex(key);
- if (0 <= index) {
- return values[index];
- }
- return defaultValue;
- }
-
- /**
- * Get integer value assigned with key.
- * @return key integer value
- * @throws RuntimeException if key does not exist
- */
- public int getExisting(Object key) {
- if (key == null) { key = UniqueTag.NULL_VALUE; }
- int index = findIndex(key);
- if (0 <= index) {
- return values[index];
- }
- // Key must exist
- Kit.codeBug();
- return 0;
- }
-
- public void put(Object key, int value) {
- if (key == null) { key = UniqueTag.NULL_VALUE; }
- int index = ensureIndex(key);
- values[index] = value;
- }
-
- /**
- * If table already contains a key that equals to keyArg, return that key
- * while setting its value to zero, otherwise add keyArg with 0 value to
- * the table and return it.
- */
- public Object intern(Object keyArg) {
- boolean nullKey = false;
- if (keyArg == null) {
- nullKey = true;
- keyArg = UniqueTag.NULL_VALUE;
- }
- int index = ensureIndex(keyArg);
- values[index] = 0;
- return (nullKey) ? null : keys[index];
- }
-
- public void remove(Object key) {
- if (key == null) { key = UniqueTag.NULL_VALUE; }
- int index = findIndex(key);
- if (0 <= index) {
- keys[index] = DELETED;
- --keyCount;
- }
- }
-
- public void clear() {
- int i = keys.length;
- while (i != 0) {
- keys[--i] = null;
- }
- keyCount = 0;
- occupiedCount = 0;
- }
-
- public Iterator newIterator() {
- return new Iterator(this);
- }
-
- // The sole purpose of the method is to avoid accessing private fields
- // from the Iterator inner class to workaround JDK 1.1 compiler bug which
- // generates code triggering VerifierError on recent JVMs
- final void initIterator(Iterator i) {
- i.init(keys, values, keyCount);
- }
-
- /** Return array of present keys */
- public Object[] getKeys() {
- Object[] array = new Object[keyCount];
- getKeys(array, 0);
- return array;
- }
-
- public void getKeys(Object[] array, int offset) {
- int count = keyCount;
- for (int i = 0; count != 0; ++i) {
- Object key = keys[i];
- if (key != null && key != DELETED) {
- if (key == UniqueTag.NULL_VALUE) { key = null; }
- array[offset] = key;
- ++offset;
- --count;
- }
- }
- }
-
- private static int tableLookupStep(int fraction, int mask, int power) {
- int shift = 32 - 2 * power;
- if (shift >= 0) {
- return ((fraction >>> shift) & mask) | 1;
- }
- else {
- return (fraction & (mask >>> -shift)) | 1;
- }
- }
-
- private int findIndex(Object key) {
- if (keys != null) {
- int hash = key.hashCode();
- int fraction = hash * A;
- int index = fraction >>> (32 - power);
- Object test = keys[index];
- if (test != null) {
- int N = 1 << power;
- if (test == key
- || (values[N + index] == hash && test.equals(key)))
- {
- return index;
- }
- // Search in table after first failed attempt
- int mask = N - 1;
- int step = tableLookupStep(fraction, mask, power);
- int n = 0;
- for (;;) {
- if (check) {
- if (n >= occupiedCount) Kit.codeBug();
- ++n;
- }
- index = (index + step) & mask;
- test = keys[index];
- if (test == null) {
- break;
- }
- if (test == key
- || (values[N + index] == hash && test.equals(key)))
- {
- return index;
- }
- }
- }
- }
- return -1;
- }
-
-// Insert key that is not present to table without deleted entries
-// and enough free space
- private int insertNewKey(Object key, int hash) {
- if (check && occupiedCount != keyCount) Kit.codeBug();
- if (check && keyCount == 1 << power) Kit.codeBug();
- int fraction = hash * A;
- int index = fraction >>> (32 - power);
- int N = 1 << power;
- if (keys[index] != null) {
- int mask = N - 1;
- int step = tableLookupStep(fraction, mask, power);
- int firstIndex = index;
- do {
- if (check && keys[index] == DELETED) Kit.codeBug();
- index = (index + step) & mask;
- if (check && firstIndex == index) Kit.codeBug();
- } while (keys[index] != null);
- }
- keys[index] = key;
- values[N + index] = hash;
- ++occupiedCount;
- ++keyCount;
-
- return index;
- }
-
- private void rehashTable() {
- if (keys == null) {
- if (check && keyCount != 0) Kit.codeBug();
- if (check && occupiedCount != 0) Kit.codeBug();
- int N = 1 << power;
- keys = new Object[N];
- values = new int[2 * N];
- }
- else {
- // Check if removing deleted entries would free enough space
- if (keyCount * 2 >= occupiedCount) {
- // Need to grow: less then half of deleted entries
- ++power;
- }
- int N = 1 << power;
- Object[] oldKeys = keys;
- int[] oldValues = values;
- int oldN = oldKeys.length;
- keys = new Object[N];
- values = new int[2 * N];
-
- int remaining = keyCount;
- occupiedCount = keyCount = 0;
- for (int i = 0; remaining != 0; ++i) {
- Object key = oldKeys[i];
- if (key != null && key != DELETED) {
- int keyHash = oldValues[oldN + i];
- int index = insertNewKey(key, keyHash);
- values[index] = oldValues[i];
- --remaining;
- }
- }
- }
- }
-
-// Ensure key index creating one if necessary
- private int ensureIndex(Object key) {
- int hash = key.hashCode();
- int index = -1;
- int firstDeleted = -1;
- if (keys != null) {
- int fraction = hash * A;
- index = fraction >>> (32 - power);
- Object test = keys[index];
- if (test != null) {
- int N = 1 << power;
- if (test == key
- || (values[N + index] == hash && test.equals(key)))
- {
- return index;
- }
- if (test == DELETED) {
- firstDeleted = index;
- }
-
- // Search in table after first failed attempt
- int mask = N - 1;
- int step = tableLookupStep(fraction, mask, power);
- int n = 0;
- for (;;) {
- if (check) {
- if (n >= occupiedCount) Kit.codeBug();
- ++n;
- }
- index = (index + step) & mask;
- test = keys[index];
- if (test == null) {
- break;
- }
- if (test == key
- || (values[N + index] == hash && test.equals(key)))
- {
- return index;
- }
- if (test == DELETED && firstDeleted < 0) {
- firstDeleted = index;
- }
- }
- }
- }
- // Inserting of new key
- if (check && keys != null && keys[index] != null)
- Kit.codeBug();
- if (firstDeleted >= 0) {
- index = firstDeleted;
- }
- else {
- // Need to consume empty entry: check occupation level
- if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {
- // Too litle unused entries: rehash
- rehashTable();
- return insertNewKey(key, hash);
- }
- ++occupiedCount;
- }
- keys[index] = key;
- values[(1 << power) + index] = hash;
- ++keyCount;
- return index;
- }
-
- private void writeObject(ObjectOutputStream out)
- throws IOException
- {
- out.defaultWriteObject();
-
- int count = keyCount;
- for (int i = 0; count != 0; ++i) {
- Object key = keys[i];
- if (key != null && key != DELETED) {
- --count;
- out.writeObject(key);
- out.writeInt(values[i]);
- }
- }
- }
-
- private void readObject(ObjectInputStream in)
- throws IOException, ClassNotFoundException
- {
- in.defaultReadObject();
-
- int writtenKeyCount = keyCount;
- if (writtenKeyCount != 0) {
- keyCount = 0;
- int N = 1 << power;
- keys = new Object[N];
- values = new int[2 * N];
- for (int i = 0; i != writtenKeyCount; ++i) {
- Object key = in.readObject();
- int hash = key.hashCode();
- int index = insertNewKey(key, hash);
- values[index] = in.readInt();
- }
- }
- }
-
-// A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)
-// See Knuth etc.
- private static final int A = 0x9e3779b9;
-
- private static final Object DELETED = new Object();
-
-// Structure of kyes and values arrays (N == 1 << power):
-// keys[0 <= i < N]: key value or null or DELETED mark
-// values[0 <= i < N]: value of key at keys[i]
-// values[N <= i < 2*N]: hash code of key at keys[i-N]
-
- private transient Object[] keys;
- private transient int[] values;
-
- private int power;
- private int keyCount;
- private transient int occupiedCount; // == keyCount + deleted_count
-
-// If true, enables consitency checks
- private static final boolean check = false;
-
-/* TEST START
-
- public static void main(String[] args) {
- if (!check) {
- System.err.println("Set check to true and re-run");
- throw new RuntimeException("Set check to true and re-run");
- }
-
- ObjToIntMap map;
- map = new ObjToIntMap(0);
- testHash(map, 3);
- map = new ObjToIntMap(0);
- testHash(map, 10 * 1000);
- map = new ObjToIntMap();
- testHash(map, 10 * 1000);
- map = new ObjToIntMap(30 * 1000);
- testHash(map, 10 * 100);
- map.clear();
- testHash(map, 4);
- map = new ObjToIntMap(0);
- testHash(map, 10 * 100);
- }
-
- private static void testHash(ObjToIntMap map, int N) {
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i);
- check(-1 == map.get(key, -1));
- map.put(key, i);
- check(i == map.get(key, -1));
- }
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i);
- map.put(key, i);
- check(i == map.get(key, -1));
- }
-
- check(map.size() == N);
-
- System.out.print("."); System.out.flush();
- Object[] keys = map.getKeys();
- check(keys.length == N);
- for (int i = 0; i != N; ++i) {
- Object key = keys[i];
- check(map.has(key));
- }
-
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i);
- check(i == map.get(key, -1));
- }
-
- int Nsqrt = -1;
- for (int i = 0; ; ++i) {
- if (i * i >= N) {
- Nsqrt = i;
- break;
- }
- }
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i * i);
- map.put(key, i);
- check(i == map.get(key, -1));
- }
-
- check(map.size() == 2 * N - Nsqrt);
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i * i);
- check(i == map.get(key, -1));
- }
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(-1 - i * i);
- map.put(key, i);
- check(i == map.get(key, -1));
- }
-
- check(map.size() == 3 * N - Nsqrt);
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(-1 - i * i);
- map.remove(key);
- check(!map.has(key));
- }
-
- check(map.size() == 2 * N - Nsqrt);
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i * i);
- check(i == map.get(key, -1));
- }
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i);
- int j = intSqrt(i);
- if (j * j == i) {
- check(j == map.get(key, -1));
- }else {
- check(i == map.get(key, -1));
- }
- }
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i * i);
- map.remove(key);
- check(-2 == map.get(key, -2));
- }
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i);
- map.put(key, i);
- check(i == map.get(key, -2));
- }
-
- check(map.size() == N);
-
- System.out.print("."); System.out.flush();
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i);
- check(i == map.get(key, -1));
- }
-
- System.out.print("."); System.out.flush();
- ObjToIntMap copy = (ObjToIntMap)writeAndRead(map);
- check(copy.size() == N);
-
- for (int i = 0; i != N; ++i) {
- Object key = testKey(i);
- check(i == copy.get(key, -1));
- }
-
- System.out.print("."); System.out.flush();
- checkSameMaps(copy, map);
-
- System.out.println(); System.out.flush();
- }
-
- private static void checkSameMaps(ObjToIntMap map1, ObjToIntMap map2) {
- check(map1.size() == map2.size());
- Object[] keys = map1.getKeys();
- check(keys.length == map1.size());
- for (int i = 0; i != keys.length; ++i) {
- check(map1.get(keys[i], -1) == map2.get(keys[i], -1));
- }
- }
-
- private static void check(boolean condition) {
- if (!condition) Kit.codeBug();
- }
-
- private static Object[] testPool;
-
- private static Object testKey(int i) {
- int MAX_POOL = 100;
- if (0 <= i && i < MAX_POOL) {
- if (testPool != null && testPool[i] != null) {
- return testPool[i];
- }
- }
- Object x = new Double(i + 0.5);
- if (0 <= i && i < MAX_POOL) {
- if (testPool == null) {
- testPool = new Object[MAX_POOL];
- }
- testPool[i] = x;
- }
- return x;
- }
-
- private static int intSqrt(int i) {
- int approx = (int)Math.sqrt(i) + 1;
- while (approx * approx > i) {
- --approx;
- }
- return approx;
- }
-
- private static Object writeAndRead(Object obj) {
- try {
- java.io.ByteArrayOutputStream
- bos = new java.io.ByteArrayOutputStream();
- java.io.ObjectOutputStream
- out = new java.io.ObjectOutputStream(bos);
- out.writeObject(obj);
- out.close();
- byte[] data = bos.toByteArray();
- java.io.ByteArrayInputStream
- bis = new java.io.ByteArrayInputStream(data);
- java.io.ObjectInputStream
- in = new java.io.ObjectInputStream(bis);
- Object result = in.readObject();
- in.close();
- return result;
- }catch (Exception ex) {
- throw new RuntimeException("Unexpected");
- }
- }
-
-// TEST END */
-
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-05 00:43:31 +0000