From d7c5ad7d6263fd1baf9bfdbaa4c50b70ef2fbdb2 Mon Sep 17 00:00:00 2001 From: Alexander Sulfrian Date: Tue, 8 Jun 2010 08:22:05 +0200 Subject: reverted folder structure change for better mergeing with upstream --- .../src/org/mozilla/javascript/ObjToIntMap.java | 697 --------------------- 1 file changed, 697 deletions(-) delete mode 100644 infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java (limited to 'infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java') diff --git a/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java b/infrastructure/rhino1_7R1/src/org/mozilla/javascript/ObjToIntMap.java deleted file mode 100644 index 4aa7d23..0000000 --- a/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 */ - -} -- cgit v1.2.3