1 /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
\r
3 * The contents of this file are subject to the Netscape Public
\r
4 * License Version 1.1 (the "License"); you may not use this file
\r
5 * except in compliance with the License. You may obtain a copy of
\r
6 * the License at http://www.mozilla.org/NPL/
\r
8 * Software distributed under the License is distributed on an "AS
\r
9 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express oqr
\r
10 * implied. See the License for the specific language governing
\r
11 * rights and limitations under the License.
\r
13 * The Original Code is Rhino code, released
\r
16 * The Initial Developer of the Original Code is Netscape
\r
17 * Communications Corporation. Portions created by Netscape are
\r
18 * Copyright (C) 1997-2000 Netscape Communications Corporation. All
\r
24 * Alternatively, the contents of this file may be used under the
\r
25 * terms of the GNU Public License (the "GPL"), in which case the
\r
26 * provisions of the GPL are applicable instead of those above.
\r
27 * If you wish to allow use of your version of this file only
\r
28 * under the terms of the GPL and not to allow others to use your
\r
29 * version of this file under the NPL, indicate your decision by
\r
30 * deleting the provisions above and replace them with the notice
\r
31 * and other provisions required by the GPL. If you do not delete
\r
32 * the provisions above, a recipient may use your version of this
\r
33 * file under either the NPL or the GPL.
\r
36 package org.mozilla.javascript;
\r
39 * Map to associate non-negative integers to objects or integers.
\r
40 * The map does not synchronize any of its operation, so either use
\r
41 * it from a single thread or do own synchronization or perform all mutation
\r
42 * operations on one thread before passing the map to others
\r
44 * @author Igor Bukanov
\r
50 // Map implementation via hashtable,
\r
51 // follows "The Art of Computer Programming" by Donald E. Knuth
\r
57 public UintMap(int initialCapacity) {
\r
58 if (checkWorld) check(initialCapacity >= 0);
\r
59 // Table grow when number of stored keys >= 3/4 of max capacity
\r
60 int minimalCapacity = initialCapacity * 4 / 3;
\r
62 for (i = 2; (1 << i) < minimalCapacity; ++i) { }
\r
64 if (checkSelf) check(minimalPower >= 2);
\r
67 public boolean isEmpty() {
\r
68 return keyCount == 0;
\r
75 public boolean has(int key) {
\r
76 if (checkWorld) check(key >= 0);
\r
77 return 0 <= findIndex(key);
\r
80 public boolean isObjectType(int key) {
\r
81 if (checkWorld) check(key >= 0);
\r
82 int index = findIndex(key);
\r
83 return index >= 0 && isObjectTypeValue(index);
\r
86 public boolean isIntType(int key) {
\r
87 if (checkWorld) check(key >= 0);
\r
88 int index = findIndex(key);
\r
89 return index >= 0 && !isObjectTypeValue(index);
\r
93 * Get object value assigned with key.
\r
94 * @return key object value or null if key is absent or does
\r
95 * not have object value
\r
97 public Object getObject(int key) {
\r
98 if (checkWorld) check(key >= 0);
\r
99 if (values != null) {
\r
100 int index = findIndex(key);
\r
102 return values[index];
\r
109 * Get integer value assigned with key.
\r
110 * @return key integer value or defaultValue if key is absent or does
\r
111 * not have int value
\r
113 public int getInt(int key, int defaultValue) {
\r
114 if (checkWorld) check(key >= 0);
\r
115 if (ivaluesShift != 0) {
\r
116 int index = findIndex(key);
\r
118 if (!isObjectTypeValue(index)) {
\r
119 return keys[ivaluesShift + index];
\r
123 return defaultValue;
\r
127 * Get integer value assigned with key.
\r
128 * @return key integer value or defaultValue if key does not exist or does
\r
129 * not have int value
\r
130 * @throws RuntimeException if key does not exist or does
\r
131 * not have int value
\r
133 public int getExistingInt(int key) {
\r
134 if (checkWorld) check(key >= 0);
\r
135 if (ivaluesShift != 0) {
\r
136 int index = findIndex(key);
\r
138 if (!isObjectTypeValue(index)) {
\r
139 return keys[ivaluesShift + index];
\r
144 if (checkWorld) check(false);
\r
148 public void put(int key, Object value) {
\r
149 if (checkWorld) check(key >= 0 && value != null);
\r
150 int index = ensureIndex(key, false);
\r
151 if (values == null) {
\r
152 values = new Object[1 << power];
\r
154 values[index] = value;
\r
157 public void put(int key, int value) {
\r
158 if (checkWorld) check(key >= 0);
\r
159 int index = ensureIndex(key, true);
\r
160 if (ivaluesShift == 0) {
\r
161 int N = 1 << power;
\r
162 int[] tmp = new int[N * 2];
\r
163 System.arraycopy(keys, 0, tmp, 0, N);
\r
167 keys[ivaluesShift + index] = value;
\r
168 if (values != null) { values[index] = null; }
\r
171 public void remove(int key) {
\r
172 if (checkWorld) check(key >= 0);
\r
173 int index = findIndex(key);
\r
175 keys[index] = DELETED;
\r
177 if (values != null) { values[index] = null; }
\r
181 public void clear() {
\r
190 /** Return array of present keys */
\r
191 public int[] getKeys() {
\r
192 int[] keys = this.keys;
\r
194 int[] result = new int[n];
\r
195 for (int i = 0; n != 0; ++i) {
\r
196 int entry = keys[i];
\r
197 if (entry != EMPTY && entry != DELETED) {
\r
198 result[--n] = entry;
\r
204 private static int tableLookupStep(int fraction, int mask, int power) {
\r
205 int shift = 32 - 2 * power;
\r
207 return ((fraction >>> shift) & mask) | 1;
\r
210 return (fraction & (mask >>> -shift)) | 1;
\r
214 private int findIndex(int key) {
\r
215 int[] keys = this.keys;
\r
216 if (keys != null) {
\r
217 int fraction = key * A;
\r
218 int index = fraction >>> (32 - power);
\r
219 int entry = keys[index];
\r
220 if (entry == key) { return index; }
\r
221 if (entry != EMPTY) {
\r
222 // Search in table after first failed attempt
\r
223 int mask = (1 << power) - 1;
\r
224 int step = tableLookupStep(fraction, mask, power);
\r
227 if (checkSelf) check(n++ < occupiedCount);
\r
228 index = (index + step) & mask;
\r
229 entry = keys[index];
\r
230 if (entry == key) { return index; }
\r
231 } while (entry != EMPTY);
\r
237 private int getFreeIndex(int key) {
\r
238 int[] keys = this.keys;
\r
239 int fraction = key * A;
\r
240 int index = fraction >>> (32 - power);
\r
241 if (keys[index] != EMPTY) {
\r
242 int mask = (1 << power) - 1;
\r
243 int step = tableLookupStep(fraction, mask, power);
\r
244 int firstIndex = index;
\r
246 if (checkSelf) check(keys[index] != DELETED);
\r
247 index = (index + step) & mask;
\r
248 if (checkSelf) check(firstIndex != index);
\r
249 } while (keys[index] != EMPTY);
\r
254 private void rehashTable(boolean ensureIntSpace) {
\r
255 if (keys == null) { power = minimalPower; }
\r
257 // Check if removing deleted entries would free enough space
\r
258 if (keyCount * 2 >= occupiedCount) {
\r
259 // Need to grow: less then half of deleted entries
\r
263 int N = 1 << power;
\r
265 int oldShift = ivaluesShift;
\r
266 if (oldShift == 0 && !ensureIntSpace) {
\r
270 ivaluesShift = N; keys = new int[N * 2];
\r
272 for (int i = 0; i != N; ++i) { keys[i] = EMPTY; }
\r
274 Object[] oldValues = values;
\r
275 if (oldValues != null) { values = new Object[N]; }
\r
278 for (int i = 0, remaining = keyCount; remaining != 0; ++i) {
\r
279 int entry = old[i];
\r
280 if (entry != EMPTY && entry != DELETED) {
\r
281 int index = getFreeIndex(entry);
\r
282 keys[index] = entry;
\r
283 if (oldValues != null) {
\r
284 values[index] = oldValues[i];
\r
286 if (oldShift != 0) {
\r
287 keys[ivaluesShift + index] = old[oldShift + i];
\r
293 occupiedCount = keyCount;
\r
296 // Ensure key index creating one if necessary
\r
297 private int ensureIndex(int key, boolean intType) {
\r
299 int firstDeleted = -1;
\r
300 int[] keys = this.keys;
\r
301 if (keys != null) {
\r
302 int fraction = key * A;
\r
303 index = fraction >>> (32 - power);
\r
304 int entry = keys[index];
\r
305 if (entry == key) { return index; }
\r
306 if (entry != EMPTY) {
\r
307 if (entry == DELETED) { firstDeleted = index; }
\r
308 // Search in table after first failed attempt
\r
309 int mask = (1 << power) - 1;
\r
310 int step = tableLookupStep(fraction, mask, power);
\r
313 if (checkSelf) check(n++ < occupiedCount);
\r
314 index = (index + step) & mask;
\r
315 entry = keys[index];
\r
316 if (entry == key) { return index; }
\r
317 if (entry == DELETED && firstDeleted < 0) {
\r
318 firstDeleted = index;
\r
320 } while (entry != EMPTY);
\r
323 // Inserting of new key
\r
324 if (checkSelf) check(keys == null || keys[index] == EMPTY);
\r
325 if (firstDeleted >= 0) {
\r
326 index = firstDeleted;
\r
329 // Need to consume empty entry: check occupation level
\r
330 if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {
\r
331 // Too litle unused entries: rehash
\r
332 rehashTable(intType);
\r
334 index = getFreeIndex(key);
\r
343 private boolean isObjectTypeValue(int index) {
\r
344 if (checkSelf) check(index >= 0 && index < (1 << power));
\r
345 return values != null && values[index] != null;
\r
348 private static void check(boolean condition) {
\r
349 if (!condition) { throw new RuntimeException(); }
\r
352 // Rudimentary support for Design-by-Contract
\r
353 private static final boolean checkWorld = true;
\r
354 private static final boolean checkSelf = checkWorld && false;
\r
356 // A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)
\r
358 private static final int A = 0x9e3779b9;
\r
360 private static final int EMPTY = -1;
\r
361 private static final int DELETED = -2;
\r
363 // Structure of kyes and values arrays (N == 1 << power):
\r
364 // keys[0 <= i < N]: key value or EMPTY or DELETED mark
\r
365 // values[0 <= i < N]: value of key at keys[i]
\r
366 // keys[N <= i < 2N]: int values of keys at keys[i - N]
\r
368 private int[] keys;
\r
369 private Object[] values;
\r
371 private int minimalPower;
\r
373 private int keyCount;
\r
374 private int occupiedCount; // == keyCount + deleted_count
\r
376 // If ivaluesShift != 0, keys[ivaluesShift + index] contains integer
\r
377 // values associated with keys
\r
378 private int ivaluesShift;
\r
381 public static void main(String[] args) {
\r
383 map = new UintMap();
\r
384 testHash(map, 10 * 1000);
\r
385 map = new UintMap(30 * 1000);
\r
386 testHash(map, 10 * 100);
\r
389 map = new UintMap(0);
\r
390 testHash(map, 10 * 100);
\r
393 private static void testHash(UintMap map, int N) {
\r
394 System.out.print("."); System.out.flush();
\r
395 for (int i = 0; i != N; ++i) {
\r
397 check(i == map.getInt(i, -1));
\r
400 System.out.print("."); System.out.flush();
\r
401 for (int i = 0; i != N; ++i) {
\r
403 check(i == map.getInt(i, -1));
\r
406 System.out.print("."); System.out.flush();
\r
407 for (int i = 0; i != N; ++i) {
\r
408 map.put(i, new Integer(i));
\r
409 check(-1 == map.getInt(i, -1));
\r
410 Integer obj = (Integer)map.getObject(i);
\r
411 check(obj != null && i == obj.intValue());
\r
414 check(map.size() == N);
\r
416 System.out.print("."); System.out.flush();
\r
417 int[] keys = map.getKeys();
\r
418 check(keys.length == N);
\r
419 for (int i = 0; i != N; ++i) {
\r
421 check(map.has(key));
\r
422 check(!map.isIntType(key));
\r
423 check(map.isObjectType(key));
\r
424 Integer obj = (Integer) map.getObject(key);
\r
425 check(obj != null && key == obj.intValue());
\r
429 System.out.print("."); System.out.flush();
\r
430 for (int i = 0; i != N; ++i) {
\r
431 check(-1 == map.getInt(i, -1));
\r
434 System.out.print("."); System.out.flush();
\r
435 for (int i = 0; i != N; ++i) {
\r
437 check(i == map.getInt(i * i, -1));
\r
440 System.out.print("."); System.out.flush();
\r
441 for (int i = 0; i != N; ++i) {
\r
442 check(i == map.getInt(i * i, -1));
\r
445 System.out.print("."); System.out.flush();
\r
446 for (int i = 0; i != N; ++i) {
\r
447 map.put(i * i, new Integer(i));
\r
448 check(-1 == map.getInt(i * i, -1));
\r
450 check(!map.has(i * i));
\r
452 check(map.isIntType(i * i));
\r
453 check(null == map.getObject(i * i));
\r
455 check(!map.isObjectType(i * i));
\r
456 check(!map.isIntType(i * i));
\r
459 int old_size = map.size();
\r
460 for (int i = 0; i != N; ++i) {
\r
462 check(map.size() == old_size);
\r
465 System.out.println(); System.out.flush();
\r