From 98e2821b38a775737e42a2479a6bc65107210859 Mon Sep 17 00:00:00 2001 From: Elliot Kroo Date: Thu, 11 Mar 2010 15:21:30 -0800 Subject: reorganizing the first level of folders (trunk/branch folders are not the git way :) --- .../src/org/mozilla/javascript/UintMap.java | 659 --------------------- 1 file changed, 659 deletions(-) delete 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 deleted file mode 100644 index 0027819..0000000 --- a/trunk/infrastructure/rhino1_7R1/src/org/mozilla/javascript/UintMap.java +++ /dev/null @@ -1,659 +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 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