From 1a5e3c2d64be1c05a422fd78b23a31de155eca64 Mon Sep 17 00:00:00 2001 From: "alexanders@b2ef00c0-3703-41da-baef-cfe82387ac0c" Date: Wed, 3 Feb 2010 00:48:31 +0000 Subject: removed duplicate trunk directory --HG-- extra : convert_revision : svn%3Ab2ef00c0-3703-41da-baef-cfe82387ac0c/trunk%404 --- .../src/org/mozilla/javascript/UintMap.java | 659 +++++++++++++++++++++ 1 file changed, 659 insertions(+) create mode 100644 trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/UintMap.java (limited to 'trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/UintMap.java') diff --git a/trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/UintMap.java b/trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/UintMap.java new file mode 100644 index 0000000..0027819 --- /dev/null +++ b/trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/UintMap.java @@ -0,0 +1,659 @@ +/* -*- 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 non-negative integers to objects or 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 UintMap implements Serializable +{ + static final long serialVersionUID = 4242698212885848444L; + +// Map implementation via hashtable, +// follows "The Art of Computer Programming" by Donald E. Knuth + + public UintMap() { + this(4); + } + + public UintMap(int initialCapacity) { + if (initialCapacity < 0) Kit.codeBug(); + // Table grow when number of stored keys >= 3/4 of max capacity + int minimalCapacity = initialCapacity * 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(int key) { + if (key < 0) Kit.codeBug(); + return 0 <= findIndex(key); + } + + /** + * Get object value assigned with key. + * @return key object value or null if key is absent + */ + public Object getObject(int key) { + if (key < 0) Kit.codeBug(); + if (values != null) { + int index = findIndex(key); + if (0 <= index) { + return values[index]; + } + } + return null; + } + + /** + * Get integer value assigned with key. + * @return key integer value or defaultValue if key is absent + */ + public int getInt(int key, int defaultValue) { + if (key < 0) Kit.codeBug(); + int index = findIndex(key); + if (0 <= index) { + if (ivaluesShift != 0) { + return keys[ivaluesShift + index]; + } + return 0; + } + return defaultValue; + } + + /** + * Get integer value assigned with key. + * @return key integer value or defaultValue if key does not exist or does + * not have int value + * @throws RuntimeException if key does not exist + */ + public int getExistingInt(int key) { + if (key < 0) Kit.codeBug(); + int index = findIndex(key); + if (0 <= index) { + if (ivaluesShift != 0) { + return keys[ivaluesShift + index]; + } + return 0; + } + // Key must exist + Kit.codeBug(); + return 0; + } + + /** + * Set object value of the key. + * If key does not exist, also set its int value to 0. + */ + public void put(int key, Object value) { + if (key < 0) Kit.codeBug(); + int index = ensureIndex(key, false); + if (values == null) { + values = new Object[1 << power]; + } + values[index] = value; + } + + /** + * Set int value of the key. + * If key does not exist, also set its object value to null. + */ + public void put(int key, int value) { + if (key < 0) Kit.codeBug(); + int index = ensureIndex(key, true); + if (ivaluesShift == 0) { + int N = 1 << power; + // keys.length can be N * 2 after clear which set ivaluesShift to 0 + if (keys.length != N * 2) { + int[] tmp = new int[N * 2]; + System.arraycopy(keys, 0, tmp, 0, N); + keys = tmp; + } + ivaluesShift = N; + } + keys[ivaluesShift + index] = value; + } + + public void remove(int key) { + if (key < 0) Kit.codeBug(); + int index = findIndex(key); + if (0 <= index) { + keys[index] = DELETED; + --keyCount; + // Allow to GC value and make sure that new key with the deleted + // slot shall get proper default values + if (values != null) { values[index] = null; } + if (ivaluesShift != 0) { keys[ivaluesShift + index] = 0; } + } + } + + public void clear() { + int N = 1 << power; + if (keys != null) { + for (int i = 0; i != N; ++i) { + keys[i] = EMPTY; + } + if (values != null) { + for (int i = 0; i != N; ++i) { + values[i] = null; + } + } + } + ivaluesShift = 0; + keyCount = 0; + occupiedCount = 0; + } + + /** Return array of present keys */ + public int[] getKeys() { + int[] keys = this.keys; + int n = keyCount; + int[] result = new int[n]; + for (int i = 0; n != 0; ++i) { + int entry = keys[i]; + if (entry != EMPTY && entry != DELETED) { + result[--n] = entry; + } + } + return result; + } + + 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(int key) { + int[] keys = this.keys; + if (keys != null) { + int fraction = key * A; + int index = fraction >>> (32 - power); + int entry = keys[index]; + if (entry == key) { return index; } + if (entry != EMPTY) { + // Search in table after first failed attempt + int mask = (1 << power) - 1; + int step = tableLookupStep(fraction, mask, power); + int n = 0; + do { + if (check) { + if (n >= occupiedCount) Kit.codeBug(); + ++n; + } + index = (index + step) & mask; + entry = keys[index]; + if (entry == key) { return index; } + } while (entry != EMPTY); + } + } + return -1; + } + +// Insert key that is not present to table without deleted entries +// and enough free space + private int insertNewKey(int key) { + if (check && occupiedCount != keyCount) Kit.codeBug(); + if (check && keyCount == 1 << power) Kit.codeBug(); + int[] keys = this.keys; + int fraction = key * A; + int index = fraction >>> (32 - power); + if (keys[index] != EMPTY) { + int mask = (1 << power) - 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] != EMPTY); + } + keys[index] = key; + ++occupiedCount; + ++keyCount; + return index; + } + + private void rehashTable(boolean ensureIntSpace) { + if (keys != null) { + // 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; + int[] old = keys; + int oldShift = ivaluesShift; + if (oldShift == 0 && !ensureIntSpace) { + keys = new int[N]; + } + else { + ivaluesShift = N; keys = new int[N * 2]; + } + for (int i = 0; i != N; ++i) { keys[i] = EMPTY; } + + Object[] oldValues = values; + if (oldValues != null) { values = new Object[N]; } + + int oldCount = keyCount; + occupiedCount = 0; + if (oldCount != 0) { + keyCount = 0; + for (int i = 0, remaining = oldCount; remaining != 0; ++i) { + int key = old[i]; + if (key != EMPTY && key != DELETED) { + int index = insertNewKey(key); + if (oldValues != null) { + values[index] = oldValues[i]; + } + if (oldShift != 0) { + keys[ivaluesShift + index] = old[oldShift + i]; + } + --remaining; + } + } + } + } + +// Ensure key index creating one if necessary + private int ensureIndex(int key, boolean intType) { + int index = -1; + int firstDeleted = -1; + int[] keys = this.keys; + if (keys != null) { + int fraction = key * A; + index = fraction >>> (32 - power); + int entry = keys[index]; + if (entry == key) { return index; } + if (entry != EMPTY) { + if (entry == DELETED) { firstDeleted = index; } + // Search in table after first failed attempt + int mask = (1 << power) - 1; + int step = tableLookupStep(fraction, mask, power); + int n = 0; + do { + if (check) { + if (n >= occupiedCount) Kit.codeBug(); + ++n; + } + index = (index + step) & mask; + entry = keys[index]; + if (entry == key) { return index; } + if (entry == DELETED && firstDeleted < 0) { + firstDeleted = index; + } + } while (entry != EMPTY); + } + } + // Inserting of new key + if (check && keys != null && keys[index] != EMPTY) + 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(intType); + keys = this.keys; + return insertNewKey(key); + } + ++occupiedCount; + } + keys[index] = key; + ++keyCount; + return index; + } + + private void writeObject(ObjectOutputStream out) + throws IOException + { + out.defaultWriteObject(); + + int count = keyCount; + if (count != 0) { + boolean hasIntValues = (ivaluesShift != 0); + boolean hasObjectValues = (values != null); + out.writeBoolean(hasIntValues); + out.writeBoolean(hasObjectValues); + + for (int i = 0; count != 0; ++i) { + int key = keys[i]; + if (key != EMPTY && key != DELETED) { + --count; + out.writeInt(key); + if (hasIntValues) { + out.writeInt(keys[ivaluesShift + i]); + } + if (hasObjectValues) { + out.writeObject(values[i]); + } + } + } + } + } + + private void readObject(ObjectInputStream in) + throws IOException, ClassNotFoundException + { + in.defaultReadObject(); + + int writtenKeyCount = keyCount; + if (writtenKeyCount != 0) { + keyCount = 0; + boolean hasIntValues = in.readBoolean(); + boolean hasObjectValues = in.readBoolean(); + + int N = 1 << power; + if (hasIntValues) { + keys = new int[2 * N]; + ivaluesShift = N; + }else { + keys = new int[N]; + } + for (int i = 0; i != N; ++i) { + keys[i] = EMPTY; + } + if (hasObjectValues) { + values = new Object[N]; + } + for (int i = 0; i != writtenKeyCount; ++i) { + int key = in.readInt(); + int index = insertNewKey(key); + if (hasIntValues) { + int ivalue = in.readInt(); + keys[ivaluesShift + index] = ivalue; + } + if (hasObjectValues) { + values[index] = in.readObject(); + } + } + } + } + +// A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32) +// See Knuth etc. + private static final int A = 0x9e3779b9; + + private static final int EMPTY = -1; + private static final int DELETED = -2; + +// Structure of kyes and values arrays (N == 1 << power): +// keys[0 <= i < N]: key value or EMPTY or DELETED mark +// values[0 <= i < N]: value of key at keys[i] +// keys[N <= i < 2N]: int values of keys at keys[i - N] + + private transient int[] keys; + private transient Object[] values; + + private int power; + private int keyCount; + private transient int occupiedCount; // == keyCount + deleted_count + + // If ivaluesShift != 0, keys[ivaluesShift + index] contains integer + // values associated with keys + private transient int ivaluesShift; + +// 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"); + } + + UintMap map; + map = new UintMap(); + testHash(map, 2); + map = new UintMap(); + testHash(map, 10 * 1000); + map = new UintMap(30 * 1000); + testHash(map, 10 * 100); + map.clear(); + testHash(map, 4); + map = new UintMap(0); + testHash(map, 10 * 100); + } + + private static void testHash(UintMap map, int N) { + System.out.print("."); System.out.flush(); + for (int i = 0; i != N; ++i) { + map.put(i, i); + check(i == map.getInt(i, -1)); + } + + System.out.print("."); System.out.flush(); + for (int i = 0; i != N; ++i) { + map.put(i, i); + check(i == map.getInt(i, -1)); + } + + System.out.print("."); System.out.flush(); + for (int i = 0; i != N; ++i) { + map.put(i, new Integer(i)); + check(-1 == map.getInt(i, -1)); + Integer obj = (Integer)map.getObject(i); + check(obj != null && i == obj.intValue()); + } + + check(map.size() == N); + + System.out.print("."); System.out.flush(); + int[] keys = map.getKeys(); + check(keys.length == N); + for (int i = 0; i != N; ++i) { + int key = keys[i]; + check(map.has(key)); + check(!map.isIntType(key)); + check(map.isObjectType(key)); + Integer obj = (Integer) map.getObject(key); + check(obj != null && key == obj.intValue()); + } + + + System.out.print("."); System.out.flush(); + for (int i = 0; i != N; ++i) { + check(-1 == map.getInt(i, -1)); + } + + System.out.print("."); System.out.flush(); + for (int i = 0; i != N; ++i) { + map.put(i * i, i); + check(i == map.getInt(i * i, -1)); + } + + System.out.print("."); System.out.flush(); + for (int i = 0; i != N; ++i) { + check(i == map.getInt(i * i, -1)); + } + + System.out.print("."); System.out.flush(); + for (int i = 0; i != N; ++i) { + map.put(i * i, new Integer(i)); + check(-1 == map.getInt(i * i, -1)); + map.remove(i * i); + check(!map.has(i * i)); + map.put(i * i, i); + check(map.isIntType(i * i)); + check(null == map.getObject(i * i)); + map.remove(i * i); + check(!map.isObjectType(i * i)); + check(!map.isIntType(i * i)); + } + + int old_size = map.size(); + for (int i = 0; i != N; ++i) { + map.remove(i * i); + check(map.size() == old_size); + } + + System.out.print("."); System.out.flush(); + map.clear(); + check(map.size() == 0); + for (int i = 0; i != N; ++i) { + map.put(i * i, i); + map.put(i * i + 1, new Double(i+0.5)); + } + checkSameMaps(map, (UintMap)writeAndRead(map)); + + System.out.print("."); System.out.flush(); + map = new UintMap(0); + checkSameMaps(map, (UintMap)writeAndRead(map)); + map = new UintMap(1); + checkSameMaps(map, (UintMap)writeAndRead(map)); + map = new UintMap(1000); + checkSameMaps(map, (UintMap)writeAndRead(map)); + + System.out.print("."); System.out.flush(); + map = new UintMap(N / 10); + for (int i = 0; i != N; ++i) { + map.put(2*i+1, i); + } + checkSameMaps(map, (UintMap)writeAndRead(map)); + + System.out.print("."); System.out.flush(); + map = new UintMap(N / 10); + for (int i = 0; i != N; ++i) { + map.put(2*i+1, i); + } + for (int i = 0; i != N / 2; ++i) { + map.remove(2*i+1); + } + checkSameMaps(map, (UintMap)writeAndRead(map)); + + System.out.print("."); System.out.flush(); + map = new UintMap(); + for (int i = 0; i != N; ++i) { + map.put(2*i+1, new Double(i + 10)); + } + for (int i = 0; i != N / 2; ++i) { + map.remove(2*i+1); + } + checkSameMaps(map, (UintMap)writeAndRead(map)); + + System.out.println(); System.out.flush(); + + } + + private static void checkSameMaps(UintMap map1, UintMap map2) { + check(map1.size() == map2.size()); + int[] keys = map1.getKeys(); + check(keys.length == map1.size()); + for (int i = 0; i != keys.length; ++i) { + int key = keys[i]; + check(map2.has(key)); + check(map1.isObjectType(key) == map2.isObjectType(key)); + check(map1.isIntType(key) == map2.isIntType(key)); + Object o1 = map1.getObject(key); + Object o2 = map2.getObject(key); + if (map1.isObjectType(key)) { + check(o1.equals(o2)); + }else { + check(map1.getObject(key) == null); + check(map2.getObject(key) == null); + } + if (map1.isIntType(key)) { + check(map1.getExistingInt(key) == map2.getExistingInt(key)); + }else { + check(map1.getInt(key, -10) == -10); + check(map1.getInt(key, -11) == -11); + check(map2.getInt(key, -10) == -10); + check(map2.getInt(key, -11) == -11); + } + } + } + + private static void check(boolean condition) { + if (!condition) Kit.codeBug(); + } + + 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) { + ex.printStackTrace(); + throw new RuntimeException("Unexpected"); + } + } + +// TEST END */ +} -- cgit v1.2.3