001: /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
002: *
003: * The contents of this file are subject to the Netscape Public
004: * License Version 1.1 (the "License"); you may not use this file
005: * except in compliance with the License. You may obtain a copy of
006: * the License at http://www.mozilla.org/NPL/
007: *
008: * Software distributed under the License is distributed on an "AS
009: * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express oqr
010: * implied. See the License for the specific language governing
011: * rights and limitations under the License.
012: *
013: * The Original Code is Rhino code, released
014: * May 6, 1999.
015: *
016: * The Initial Developer of the Original Code is Netscape
017: * Communications Corporation. Portions created by Netscape are
018: * Copyright (C) 1997-2000 Netscape Communications Corporation. All
019: * Rights Reserved.
020: *
021: * Contributor(s):
022: * Igor Bukanov
023: *
024: * Alternatively, the contents of this file may be used under the
025: * terms of the GNU Public License (the "GPL"), in which case the
026: * provisions of the GPL are applicable instead of those above.
027: * If you wish to allow use of your version of this file only
028: * under the terms of the GPL and not to allow others to use your
029: * version of this file under the NPL, indicate your decision by
030: * deleting the provisions above and replace them with the notice
031: * and other provisions required by the GPL. If you do not delete
032: * the provisions above, a recipient may use your version of this
033: * file under either the NPL or the GPL.
034: */
035: // Modified by Google
036: package com.google.gwt.dev.js.rhino;
037:
038: import java.io.Serializable;
039: import java.io.IOException;
040: import java.io.ObjectInputStream;
041: import java.io.ObjectOutputStream;
042:
043: /**
044: * Map to associate objects to integers.
045: * The map does not synchronize any of its operation, so either use
046: * it from a single thread or do own synchronization or perform all mutation
047: * operations on one thread before passing the map to others
048: *
049: * @author Igor Bukanov
050: *
051: */
052:
053: public class ObjToIntMap implements Serializable {
054:
055: public static final Object NULL_VALUE = new String("");
056:
057: // Map implementation via hashtable,
058: // follows "The Art of Computer Programming" by Donald E. Knuth
059:
060: // ObjToIntMap is a copy cat of ObjToIntMap with API adjusted to object keys
061:
062: public static class Iterator {
063:
064: Iterator(ObjToIntMap master) {
065: this .master = master;
066: }
067:
068: final void init(Object[] keys, int[] values, int keyCount) {
069: this .keys = keys;
070: this .values = values;
071: this .cursor = -1;
072: this .remaining = keyCount;
073: }
074:
075: public void start() {
076: master.initIterator(this );
077: next();
078: }
079:
080: public boolean done() {
081: return remaining < 0;
082: }
083:
084: public void next() {
085: if (remaining == -1)
086: Context.codeBug();
087: if (remaining == 0) {
088: remaining = -1;
089: cursor = -1;
090: } else {
091: for (++cursor;; ++cursor) {
092: Object key = keys[cursor];
093: if (key != null && key != DELETED) {
094: --remaining;
095: break;
096: }
097: }
098: }
099: }
100:
101: public Object getKey() {
102: Object key = keys[cursor];
103: if (key == NULL_VALUE) {
104: key = null;
105: }
106: return key;
107: }
108:
109: public int getValue() {
110: return values[cursor];
111: }
112:
113: public void setValue(int value) {
114: values[cursor] = value;
115: }
116:
117: ObjToIntMap master;
118: private int cursor;
119: private int remaining;
120: private Object[] keys;
121: private int[] values;
122: }
123:
124: public ObjToIntMap() {
125: this (4);
126: }
127:
128: public ObjToIntMap(int keyCountHint) {
129: if (keyCountHint < 0)
130: Context.codeBug();
131: // Table grow when number of stored keys >= 3/4 of max capacity
132: int minimalCapacity = keyCountHint * 4 / 3;
133: int i;
134: for (i = 2; (1 << i) < minimalCapacity; ++i) {
135: }
136: power = i;
137: if (check && power < 2)
138: Context.codeBug();
139: }
140:
141: public boolean isEmpty() {
142: return keyCount == 0;
143: }
144:
145: public int size() {
146: return keyCount;
147: }
148:
149: public boolean has(Object key) {
150: if (key == null) {
151: key = NULL_VALUE;
152: }
153: return 0 <= findIndex(key);
154: }
155:
156: /**
157: * Get integer value assigned with key.
158: * @return key integer value or defaultValue if key is absent
159: */
160: public int get(Object key, int defaultValue) {
161: if (key == null) {
162: key = NULL_VALUE;
163: }
164: int index = findIndex(key);
165: if (0 <= index) {
166: return values[index];
167: }
168: return defaultValue;
169: }
170:
171: /**
172: * Get integer value assigned with key.
173: * @return key integer value
174: * @throws RuntimeException if key does not exist
175: */
176: public int getExisting(Object key) {
177: if (key == null) {
178: key = NULL_VALUE;
179: }
180: int index = findIndex(key);
181: if (0 <= index) {
182: return values[index];
183: }
184: // Key must exist
185: Context.codeBug();
186: return 0;
187: }
188:
189: public void put(Object key, int value) {
190: if (key == null) {
191: key = NULL_VALUE;
192: }
193: int index = ensureIndex(key);
194: values[index] = value;
195: }
196:
197: /**
198: * If table already contains a key that equals to keyArg, return that key
199: * while setting its value to zero, otherwise add keyArg with 0 value to
200: * the table and return it.
201: */
202: public Object intern(Object keyArg) {
203: boolean nullKey = false;
204: if (keyArg == null) {
205: nullKey = true;
206: keyArg = NULL_VALUE;
207: }
208: int index = ensureIndex(keyArg);
209: values[index] = 0;
210: return (nullKey) ? null : keys[index];
211: }
212:
213: public void remove(Object key) {
214: if (key == null) {
215: key = NULL_VALUE;
216: }
217: int index = findIndex(key);
218: if (0 <= index) {
219: keys[index] = DELETED;
220: --keyCount;
221: }
222: }
223:
224: public void clear() {
225: int i = keys.length;
226: while (i != 0) {
227: keys[--i] = null;
228: }
229: keyCount = 0;
230: occupiedCount = 0;
231: }
232:
233: public Iterator newIterator() {
234: return new Iterator(this );
235: }
236:
237: // The sole purpose of the method is to avoid accessing private fields
238: // from the Iterator inner class to workaround JDK 1.1 compiler bug which
239: // generates code triggering VerifierError on recent JVMs
240: final void initIterator(Iterator i) {
241: i.init(keys, values, keyCount);
242: }
243:
244: /** Return array of present keys */
245: public Object[] getKeys() {
246: Object[] array = new Object[keyCount];
247: getKeys(array, 0);
248: return array;
249: }
250:
251: public void getKeys(Object[] array, int offset) {
252: int count = keyCount;
253: for (int i = 0; count != 0; ++i) {
254: Object key = keys[i];
255: if (key != null && key != DELETED) {
256: if (key == NULL_VALUE) {
257: key = null;
258: }
259: array[offset] = key;
260: ++offset;
261: --count;
262: }
263: }
264: }
265:
266: private static int tableLookupStep(int fraction, int mask, int power) {
267: int shift = 32 - 2 * power;
268: if (shift >= 0) {
269: return ((fraction >>> shift) & mask) | 1;
270: } else {
271: return (fraction & (mask >>> -shift)) | 1;
272: }
273: }
274:
275: private int findIndex(Object key) {
276: if (keys != null) {
277: int hash = key.hashCode();
278: int fraction = hash * A;
279: int index = fraction >>> (32 - power);
280: Object test = keys[index];
281: if (test != null) {
282: int N = 1 << power;
283: if (test == key
284: || (values[N + index] == hash && test
285: .equals(key))) {
286: return index;
287: }
288: // Search in table after first failed attempt
289: int mask = N - 1;
290: int step = tableLookupStep(fraction, mask, power);
291: int n = 0;
292: for (;;) {
293: if (check) {
294: if (n >= occupiedCount)
295: Context.codeBug();
296: ++n;
297: }
298: index = (index + step) & mask;
299: test = keys[index];
300: if (test == null) {
301: break;
302: }
303: if (test == key
304: || (values[N + index] == hash && test
305: .equals(key))) {
306: return index;
307: }
308: }
309: }
310: }
311: return -1;
312: }
313:
314: // Insert key that is not present to table without deleted entries
315: // and enough free space
316: private int insertNewKey(Object key, int hash) {
317: if (check && occupiedCount != keyCount)
318: Context.codeBug();
319: if (check && keyCount == 1 << power)
320: Context.codeBug();
321: int fraction = hash * A;
322: int index = fraction >>> (32 - power);
323: int N = 1 << power;
324: if (keys[index] != null) {
325: int mask = N - 1;
326: int step = tableLookupStep(fraction, mask, power);
327: int firstIndex = index;
328: do {
329: if (check && keys[index] == DELETED)
330: Context.codeBug();
331: index = (index + step) & mask;
332: if (check && firstIndex == index)
333: Context.codeBug();
334: } while (keys[index] != null);
335: }
336: keys[index] = key;
337: values[N + index] = hash;
338: ++occupiedCount;
339: ++keyCount;
340:
341: return index;
342: }
343:
344: private void rehashTable() {
345: if (keys == null) {
346: if (check && keyCount != 0)
347: Context.codeBug();
348: if (check && occupiedCount != 0)
349: Context.codeBug();
350: int N = 1 << power;
351: keys = new Object[N];
352: values = new int[2 * N];
353: } else {
354: // Check if removing deleted entries would free enough space
355: if (keyCount * 2 >= occupiedCount) {
356: // Need to grow: less then half of deleted entries
357: ++power;
358: }
359: int N = 1 << power;
360: Object[] oldKeys = keys;
361: int[] oldValues = values;
362: int oldN = oldKeys.length;
363: keys = new Object[N];
364: values = new int[2 * N];
365:
366: int remaining = keyCount;
367: occupiedCount = keyCount = 0;
368: for (int i = 0; remaining != 0; ++i) {
369: Object key = oldKeys[i];
370: if (key != null && key != DELETED) {
371: int keyHash = oldValues[oldN + i];
372: int index = insertNewKey(key, keyHash);
373: values[index] = oldValues[i];
374: --remaining;
375: }
376: }
377: }
378: }
379:
380: // Ensure key index creating one if necessary
381: private int ensureIndex(Object key) {
382: int hash = key.hashCode();
383: int index = -1;
384: int firstDeleted = -1;
385: if (keys != null) {
386: int fraction = hash * A;
387: index = fraction >>> (32 - power);
388: Object test = keys[index];
389: if (test != null) {
390: int N = 1 << power;
391: if (test == key
392: || (values[N + index] == hash && test
393: .equals(key))) {
394: return index;
395: }
396: if (test == DELETED) {
397: firstDeleted = index;
398: }
399:
400: // Search in table after first failed attempt
401: int mask = N - 1;
402: int step = tableLookupStep(fraction, mask, power);
403: int n = 0;
404: for (;;) {
405: if (check) {
406: if (n >= occupiedCount)
407: Context.codeBug();
408: ++n;
409: }
410: index = (index + step) & mask;
411: test = keys[index];
412: if (test == null) {
413: break;
414: }
415: if (test == key
416: || (values[N + index] == hash && test
417: .equals(key))) {
418: return index;
419: }
420: if (test == DELETED && firstDeleted < 0) {
421: firstDeleted = index;
422: }
423: }
424: }
425: }
426: // Inserting of new key
427: if (check && keys != null && keys[index] != null)
428: Context.codeBug();
429: if (firstDeleted >= 0) {
430: index = firstDeleted;
431: } else {
432: // Need to consume empty entry: check occupation level
433: if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {
434: // Too litle unused entries: rehash
435: rehashTable();
436: return insertNewKey(key, hash);
437: }
438: ++occupiedCount;
439: }
440: keys[index] = key;
441: values[(1 << power) + index] = hash;
442: ++keyCount;
443: return index;
444: }
445:
446: private void writeObject(ObjectOutputStream out) throws IOException {
447: out.defaultWriteObject();
448:
449: int count = keyCount;
450: for (int i = 0; count != 0; ++i) {
451: Object key = keys[i];
452: if (key != null && key != DELETED) {
453: --count;
454: out.writeObject(key);
455: out.writeInt(values[i]);
456: }
457: }
458: }
459:
460: private void readObject(ObjectInputStream in) throws IOException,
461: ClassNotFoundException {
462: in.defaultReadObject();
463:
464: int writtenKeyCount = keyCount;
465: if (writtenKeyCount != 0) {
466: keyCount = 0;
467: int N = 1 << power;
468: keys = new Object[N];
469: values = new int[2 * N];
470: for (int i = 0; i != writtenKeyCount; ++i) {
471: Object key = in.readObject();
472: int hash = key.hashCode();
473: int index = insertNewKey(key, hash);
474: values[index] = in.readInt();
475: }
476: }
477: }
478:
479: static final long serialVersionUID = 3396438333234169727L;
480:
481: // A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)
482: // See Knuth etc.
483: private static final int A = 0x9e3779b9;
484:
485: private static final Object DELETED = new Object();
486:
487: // Structure of kyes and values arrays (N == 1 << power):
488: // keys[0 <= i < N]: key value or null or DELETED mark
489: // values[0 <= i < N]: value of key at keys[i]
490: // values[N <= i < 2*N]: hash code of key at keys[i-N]
491:
492: private transient Object[] keys;
493: private transient int[] values;
494:
495: private int power;
496: private int keyCount;
497: private transient int occupiedCount; // == keyCount + deleted_count
498:
499: // If true, enables consitency checks
500: private static final boolean check = false;
501:
502: /* TEST START
503:
504: public static void main(String[] args) {
505: if (!check) {
506: System.err.println("Set check to true and re-run");
507: throw new RuntimeException("Set check to true and re-run");
508: }
509:
510: ObjToIntMap map;
511: map = new ObjToIntMap(0);
512: testHash(map, 3);
513: map = new ObjToIntMap(0);
514: testHash(map, 10 * 1000);
515: map = new ObjToIntMap();
516: testHash(map, 10 * 1000);
517: map = new ObjToIntMap(30 * 1000);
518: testHash(map, 10 * 100);
519: map.clear();
520: testHash(map, 4);
521: map = new ObjToIntMap(0);
522: testHash(map, 10 * 100);
523: }
524:
525: private static void testHash(ObjToIntMap map, int N) {
526: System.out.print("."); System.out.flush();
527: for (int i = 0; i != N; ++i) {
528: Object key = testKey(i);
529: check(-1 == map.get(key, -1));
530: map.put(key, i);
531: check(i == map.get(key, -1));
532: }
533:
534: System.out.print("."); System.out.flush();
535: for (int i = 0; i != N; ++i) {
536: Object key = testKey(i);
537: map.put(key, i);
538: check(i == map.get(key, -1));
539: }
540:
541: check(map.size() == N);
542:
543: System.out.print("."); System.out.flush();
544: Object[] keys = map.getKeys();
545: check(keys.length == N);
546: for (int i = 0; i != N; ++i) {
547: Object key = keys[i];
548: check(map.has(key));
549: }
550:
551:
552: System.out.print("."); System.out.flush();
553: for (int i = 0; i != N; ++i) {
554: Object key = testKey(i);
555: check(i == map.get(key, -1));
556: }
557:
558: int Nsqrt = -1;
559: for (int i = 0; ; ++i) {
560: if (i * i >= N) {
561: Nsqrt = i;
562: break;
563: }
564: }
565:
566: System.out.print("."); System.out.flush();
567: for (int i = 0; i != N; ++i) {
568: Object key = testKey(i * i);
569: map.put(key, i);
570: check(i == map.get(key, -1));
571: }
572:
573: check(map.size() == 2 * N - Nsqrt);
574:
575: System.out.print("."); System.out.flush();
576: for (int i = 0; i != N; ++i) {
577: Object key = testKey(i * i);
578: check(i == map.get(key, -1));
579: }
580:
581: System.out.print("."); System.out.flush();
582: for (int i = 0; i != N; ++i) {
583: Object key = testKey(-1 - i * i);
584: map.put(key, i);
585: check(i == map.get(key, -1));
586: }
587:
588: check(map.size() == 3 * N - Nsqrt);
589:
590: System.out.print("."); System.out.flush();
591: for (int i = 0; i != N; ++i) {
592: Object key = testKey(-1 - i * i);
593: map.remove(key);
594: check(!map.has(key));
595: }
596:
597: check(map.size() == 2 * N - Nsqrt);
598:
599: System.out.print("."); System.out.flush();
600: for (int i = 0; i != N; ++i) {
601: Object key = testKey(i * i);
602: check(i == map.get(key, -1));
603: }
604:
605: System.out.print("."); System.out.flush();
606: for (int i = 0; i != N; ++i) {
607: Object key = testKey(i);
608: int j = intSqrt(i);
609: if (j * j == i) {
610: check(j == map.get(key, -1));
611: }else {
612: check(i == map.get(key, -1));
613: }
614: }
615:
616: System.out.print("."); System.out.flush();
617: for (int i = 0; i != N; ++i) {
618: Object key = testKey(i * i);
619: map.remove(key);
620: check(-2 == map.get(key, -2));
621: }
622:
623: System.out.print("."); System.out.flush();
624: for (int i = 0; i != N; ++i) {
625: Object key = testKey(i);
626: map.put(key, i);
627: check(i == map.get(key, -2));
628: }
629:
630: check(map.size() == N);
631:
632: System.out.print("."); System.out.flush();
633: for (int i = 0; i != N; ++i) {
634: Object key = testKey(i);
635: check(i == map.get(key, -1));
636: }
637:
638: System.out.print("."); System.out.flush();
639: ObjToIntMap copy = (ObjToIntMap)writeAndRead(map);
640: check(copy.size() == N);
641:
642: for (int i = 0; i != N; ++i) {
643: Object key = testKey(i);
644: check(i == copy.get(key, -1));
645: }
646:
647: System.out.print("."); System.out.flush();
648: checkSameMaps(copy, map);
649:
650: System.out.println(); System.out.flush();
651: }
652:
653: private static void checkSameMaps(ObjToIntMap map1, ObjToIntMap map2) {
654: check(map1.size() == map2.size());
655: Object[] keys = map1.getKeys();
656: check(keys.length == map1.size());
657: for (int i = 0; i != keys.length; ++i) {
658: check(map1.get(keys[i], -1) == map2.get(keys[i], -1));
659: }
660: }
661:
662: private static void check(boolean condition) {
663: if (!condition) Context.codeBug();
664: }
665:
666: private static Object[] testPool;
667:
668: private static Object testKey(int i) {
669: int MAX_POOL = 100;
670: if (0 <= i && i < MAX_POOL) {
671: if (testPool != null && testPool[i] != null) {
672: return testPool[i];
673: }
674: }
675: Object x = new Double(i + 0.5);
676: if (0 <= i && i < MAX_POOL) {
677: if (testPool == null) {
678: testPool = new Object[MAX_POOL];
679: }
680: testPool[i] = x;
681: }
682: return x;
683: }
684:
685: private static int intSqrt(int i) {
686: int approx = (int)Math.sqrt(i) + 1;
687: while (approx * approx > i) {
688: --approx;
689: }
690: return approx;
691: }
692:
693: private static Object writeAndRead(Object obj) {
694: try {
695: java.io.ByteArrayOutputStream
696: bos = new java.io.ByteArrayOutputStream();
697: java.io.ObjectOutputStream
698: out = new java.io.ObjectOutputStream(bos);
699: out.writeObject(obj);
700: out.close();
701: byte[] data = bos.toByteArray();
702: java.io.ByteArrayInputStream
703: bis = new java.io.ByteArrayInputStream(data);
704: java.io.ObjectInputStream
705: in = new java.io.ObjectInputStream(bis);
706: Object result = in.readObject();
707: in.close();
708: return result;
709: }catch (Exception ex) {
710: throw new RuntimeException("Unexpected");
711: }
712: }
713:
714: // TEST END */
715:
716: }
|