aboutsummaryrefslogtreecommitdiffstats
path: root/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java
diff options
context:
space:
mode:
Diffstat (limited to 'infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java')
-rw-r--r--infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java697
1 files changed, 697 insertions, 0 deletions
diff --git a/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java b/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java
new file mode 100644
index 0000000..4aa7d23
--- /dev/null
+++ b/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java
@@ -0,0 +1,697 @@
+/* -*- 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-01 01:05:04 +0000