001: /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
002: *
003: * ***** BEGIN LICENSE BLOCK *****
004: * Version: MPL 1.1/GPL 2.0
005: *
006: * The contents of this file are subject to the Mozilla Public License Version
007: * 1.1 (the "License"); you may not use this file except in compliance with
008: * the License. You may obtain a copy of the License at
009: * http://www.mozilla.org/MPL/
010: *
011: * Software distributed under the License is distributed on an "AS IS" basis,
012: * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
013: * for the specific language governing rights and limitations under the
014: * License.
015: *
016: * The Original Code is Rhino code, released
017: * May 6, 1999.
018: *
019: * The Initial Developer of the Original Code is
020: * Netscape Communications Corporation.
021: * Portions created by the Initial Developer are Copyright (C) 1997-2000
022: * the Initial Developer. All Rights Reserved.
023: *
024: * Contributor(s):
025: * Igor Bukanov
026: *
027: * Alternatively, the contents of this file may be used under the terms of
028: * the GNU General Public License Version 2 or later (the "GPL"), in which
029: * case the provisions of the GPL are applicable instead of those above. If
030: * you wish to allow use of your version of this file only under the terms of
031: * the GPL and not to allow others to use your version of this file under the
032: * MPL, indicate your decision by deleting the provisions above and replacing
033: * them with the notice and other provisions required by the GPL. If you do
034: * not delete the provisions above, a recipient may use your version of this
035: * file under either the MPL or the GPL.
036: *
037: * ***** END LICENSE BLOCK ***** */
038:
039: package org.mozilla.javascript;
040:
041: import java.io.Serializable;
042: import java.io.IOException;
043: import java.io.ObjectInputStream;
044: import java.io.ObjectOutputStream;
045:
046: /**
047: * Map to associate objects to integers.
048: * The map does not synchronize any of its operation, so either use
049: * it from a single thread or do own synchronization or perform all mutation
050: * operations on one thread before passing the map to others
051: *
052: * @author Igor Bukanov
053: *
054: */
055:
056: public class ObjToIntMap implements Serializable {
057: static final long serialVersionUID = -1542220580748809402L;
058:
059: // Map implementation via hashtable,
060: // follows "The Art of Computer Programming" by Donald E. Knuth
061:
062: // ObjToIntMap is a copy cat of ObjToIntMap with API adjusted to object keys
063:
064: public static class Iterator {
065:
066: Iterator(ObjToIntMap master) {
067: this .master = master;
068: }
069:
070: final void init(Object[] keys, int[] values, int keyCount) {
071: this .keys = keys;
072: this .values = values;
073: this .cursor = -1;
074: this .remaining = keyCount;
075: }
076:
077: public void start() {
078: master.initIterator(this );
079: next();
080: }
081:
082: public boolean done() {
083: return remaining < 0;
084: }
085:
086: public void next() {
087: if (remaining == -1)
088: Kit.codeBug();
089: if (remaining == 0) {
090: remaining = -1;
091: cursor = -1;
092: } else {
093: for (++cursor;; ++cursor) {
094: Object key = keys[cursor];
095: if (key != null && key != DELETED) {
096: --remaining;
097: break;
098: }
099: }
100: }
101: }
102:
103: public Object getKey() {
104: Object key = keys[cursor];
105: if (key == UniqueTag.NULL_VALUE) {
106: key = null;
107: }
108: return key;
109: }
110:
111: public int getValue() {
112: return values[cursor];
113: }
114:
115: public void setValue(int value) {
116: values[cursor] = value;
117: }
118:
119: ObjToIntMap master;
120: private int cursor;
121: private int remaining;
122: private Object[] keys;
123: private int[] values;
124: }
125:
126: public ObjToIntMap() {
127: this (4);
128: }
129:
130: public ObjToIntMap(int keyCountHint) {
131: if (keyCountHint < 0)
132: Kit.codeBug();
133: // Table grow when number of stored keys >= 3/4 of max capacity
134: int minimalCapacity = keyCountHint * 4 / 3;
135: int i;
136: for (i = 2; (1 << i) < minimalCapacity; ++i) {
137: }
138: power = i;
139: if (check && power < 2)
140: Kit.codeBug();
141: }
142:
143: public boolean isEmpty() {
144: return keyCount == 0;
145: }
146:
147: public int size() {
148: return keyCount;
149: }
150:
151: public boolean has(Object key) {
152: if (key == null) {
153: key = UniqueTag.NULL_VALUE;
154: }
155: return 0 <= findIndex(key);
156: }
157:
158: /**
159: * Get integer value assigned with key.
160: * @return key integer value or defaultValue if key is absent
161: */
162: public int get(Object key, int defaultValue) {
163: if (key == null) {
164: key = UniqueTag.NULL_VALUE;
165: }
166: int index = findIndex(key);
167: if (0 <= index) {
168: return values[index];
169: }
170: return defaultValue;
171: }
172:
173: /**
174: * Get integer value assigned with key.
175: * @return key integer value
176: * @throws RuntimeException if key does not exist
177: */
178: public int getExisting(Object key) {
179: if (key == null) {
180: key = UniqueTag.NULL_VALUE;
181: }
182: int index = findIndex(key);
183: if (0 <= index) {
184: return values[index];
185: }
186: // Key must exist
187: Kit.codeBug();
188: return 0;
189: }
190:
191: public void put(Object key, int value) {
192: if (key == null) {
193: key = UniqueTag.NULL_VALUE;
194: }
195: int index = ensureIndex(key);
196: values[index] = value;
197: }
198:
199: /**
200: * If table already contains a key that equals to keyArg, return that key
201: * while setting its value to zero, otherwise add keyArg with 0 value to
202: * the table and return it.
203: */
204: public Object intern(Object keyArg) {
205: boolean nullKey = false;
206: if (keyArg == null) {
207: nullKey = true;
208: keyArg = UniqueTag.NULL_VALUE;
209: }
210: int index = ensureIndex(keyArg);
211: values[index] = 0;
212: return (nullKey) ? null : keys[index];
213: }
214:
215: public void remove(Object key) {
216: if (key == null) {
217: key = UniqueTag.NULL_VALUE;
218: }
219: int index = findIndex(key);
220: if (0 <= index) {
221: keys[index] = DELETED;
222: --keyCount;
223: }
224: }
225:
226: public void clear() {
227: int i = keys.length;
228: while (i != 0) {
229: keys[--i] = null;
230: }
231: keyCount = 0;
232: occupiedCount = 0;
233: }
234:
235: public Iterator newIterator() {
236: return new Iterator(this );
237: }
238:
239: // The sole purpose of the method is to avoid accessing private fields
240: // from the Iterator inner class to workaround JDK 1.1 compiler bug which
241: // generates code triggering VerifierError on recent JVMs
242: final void initIterator(Iterator i) {
243: i.init(keys, values, keyCount);
244: }
245:
246: /** Return array of present keys */
247: public Object[] getKeys() {
248: Object[] array = new Object[keyCount];
249: getKeys(array, 0);
250: return array;
251: }
252:
253: public void getKeys(Object[] array, int offset) {
254: int count = keyCount;
255: for (int i = 0; count != 0; ++i) {
256: Object key = keys[i];
257: if (key != null && key != DELETED) {
258: if (key == UniqueTag.NULL_VALUE) {
259: key = null;
260: }
261: array[offset] = key;
262: ++offset;
263: --count;
264: }
265: }
266: }
267:
268: private static int tableLookupStep(int fraction, int mask, int power) {
269: int shift = 32 - 2 * power;
270: if (shift >= 0) {
271: return ((fraction >>> shift) & mask) | 1;
272: } else {
273: return (fraction & (mask >>> -shift)) | 1;
274: }
275: }
276:
277: private int findIndex(Object key) {
278: if (keys != null) {
279: int hash = key.hashCode();
280: int fraction = hash * A;
281: int index = fraction >>> (32 - power);
282: Object test = keys[index];
283: if (test != null) {
284: int N = 1 << power;
285: if (test == key
286: || (values[N + index] == hash && test
287: .equals(key))) {
288: return index;
289: }
290: // Search in table after first failed attempt
291: int mask = N - 1;
292: int step = tableLookupStep(fraction, mask, power);
293: int n = 0;
294: for (;;) {
295: if (check) {
296: if (n >= occupiedCount)
297: Kit.codeBug();
298: ++n;
299: }
300: index = (index + step) & mask;
301: test = keys[index];
302: if (test == null) {
303: break;
304: }
305: if (test == key
306: || (values[N + index] == hash && test
307: .equals(key))) {
308: return index;
309: }
310: }
311: }
312: }
313: return -1;
314: }
315:
316: // Insert key that is not present to table without deleted entries
317: // and enough free space
318: private int insertNewKey(Object key, int hash) {
319: if (check && occupiedCount != keyCount)
320: Kit.codeBug();
321: if (check && keyCount == 1 << power)
322: Kit.codeBug();
323: int fraction = hash * A;
324: int index = fraction >>> (32 - power);
325: int N = 1 << power;
326: if (keys[index] != null) {
327: int mask = N - 1;
328: int step = tableLookupStep(fraction, mask, power);
329: int firstIndex = index;
330: do {
331: if (check && keys[index] == DELETED)
332: Kit.codeBug();
333: index = (index + step) & mask;
334: if (check && firstIndex == index)
335: Kit.codeBug();
336: } while (keys[index] != null);
337: }
338: keys[index] = key;
339: values[N + index] = hash;
340: ++occupiedCount;
341: ++keyCount;
342:
343: return index;
344: }
345:
346: private void rehashTable() {
347: if (keys == null) {
348: if (check && keyCount != 0)
349: Kit.codeBug();
350: if (check && occupiedCount != 0)
351: Kit.codeBug();
352: int N = 1 << power;
353: keys = new Object[N];
354: values = new int[2 * N];
355: } else {
356: // Check if removing deleted entries would free enough space
357: if (keyCount * 2 >= occupiedCount) {
358: // Need to grow: less then half of deleted entries
359: ++power;
360: }
361: int N = 1 << power;
362: Object[] oldKeys = keys;
363: int[] oldValues = values;
364: int oldN = oldKeys.length;
365: keys = new Object[N];
366: values = new int[2 * N];
367:
368: int remaining = keyCount;
369: occupiedCount = keyCount = 0;
370: for (int i = 0; remaining != 0; ++i) {
371: Object key = oldKeys[i];
372: if (key != null && key != DELETED) {
373: int keyHash = oldValues[oldN + i];
374: int index = insertNewKey(key, keyHash);
375: values[index] = oldValues[i];
376: --remaining;
377: }
378: }
379: }
380: }
381:
382: // Ensure key index creating one if necessary
383: private int ensureIndex(Object key) {
384: int hash = key.hashCode();
385: int index = -1;
386: int firstDeleted = -1;
387: if (keys != null) {
388: int fraction = hash * A;
389: index = fraction >>> (32 - power);
390: Object test = keys[index];
391: if (test != null) {
392: int N = 1 << power;
393: if (test == key
394: || (values[N + index] == hash && test
395: .equals(key))) {
396: return index;
397: }
398: if (test == DELETED) {
399: firstDeleted = index;
400: }
401:
402: // Search in table after first failed attempt
403: int mask = N - 1;
404: int step = tableLookupStep(fraction, mask, power);
405: int n = 0;
406: for (;;) {
407: if (check) {
408: if (n >= occupiedCount)
409: Kit.codeBug();
410: ++n;
411: }
412: index = (index + step) & mask;
413: test = keys[index];
414: if (test == null) {
415: break;
416: }
417: if (test == key
418: || (values[N + index] == hash && test
419: .equals(key))) {
420: return index;
421: }
422: if (test == DELETED && firstDeleted < 0) {
423: firstDeleted = index;
424: }
425: }
426: }
427: }
428: // Inserting of new key
429: if (check && keys != null && keys[index] != null)
430: Kit.codeBug();
431: if (firstDeleted >= 0) {
432: index = firstDeleted;
433: } else {
434: // Need to consume empty entry: check occupation level
435: if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {
436: // Too litle unused entries: rehash
437: rehashTable();
438: return insertNewKey(key, hash);
439: }
440: ++occupiedCount;
441: }
442: keys[index] = key;
443: values[(1 << power) + index] = hash;
444: ++keyCount;
445: return index;
446: }
447:
448: private void writeObject(ObjectOutputStream out) throws IOException {
449: out.defaultWriteObject();
450:
451: int count = keyCount;
452: for (int i = 0; count != 0; ++i) {
453: Object key = keys[i];
454: if (key != null && key != DELETED) {
455: --count;
456: out.writeObject(key);
457: out.writeInt(values[i]);
458: }
459: }
460: }
461:
462: private void readObject(ObjectInputStream in) throws IOException,
463: ClassNotFoundException {
464: in.defaultReadObject();
465:
466: int writtenKeyCount = keyCount;
467: if (writtenKeyCount != 0) {
468: keyCount = 0;
469: int N = 1 << power;
470: keys = new Object[N];
471: values = new int[2 * N];
472: for (int i = 0; i != writtenKeyCount; ++i) {
473: Object key = in.readObject();
474: int hash = key.hashCode();
475: int index = insertNewKey(key, hash);
476: values[index] = in.readInt();
477: }
478: }
479: }
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) Kit.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: }
|