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 or
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 non-negative integers to objects or 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: class UintMap implements Serializable {
054:
055: // Map implementation via hashtable,
056: // follows "The Art of Computer Programming" by Donald E. Knuth
057:
058: public UintMap() {
059: this (4);
060: }
061:
062: public UintMap(int initialCapacity) {
063: if (initialCapacity < 0)
064: Context.codeBug();
065: // Table grow when number of stored keys >= 3/4 of max capacity
066: int minimalCapacity = initialCapacity * 4 / 3;
067: int i;
068: for (i = 2; (1 << i) < minimalCapacity; ++i) {
069: }
070: power = i;
071: if (check && power < 2)
072: Context.codeBug();
073: }
074:
075: public boolean isEmpty() {
076: return keyCount == 0;
077: }
078:
079: public int size() {
080: return keyCount;
081: }
082:
083: public boolean has(int key) {
084: if (key < 0)
085: Context.codeBug();
086: return 0 <= findIndex(key);
087: }
088:
089: /**
090: * Get object value assigned with key.
091: * @return key object value or null if key is absent
092: */
093: public Object getObject(int key) {
094: if (key < 0)
095: Context.codeBug();
096: if (values != null) {
097: int index = findIndex(key);
098: if (0 <= index) {
099: return values[index];
100: }
101: }
102: return null;
103: }
104:
105: /**
106: * Get integer value assigned with key.
107: * @return key integer value or defaultValue if key is absent
108: */
109: public int getInt(int key, int defaultValue) {
110: if (key < 0)
111: Context.codeBug();
112: int index = findIndex(key);
113: if (0 <= index) {
114: if (ivaluesShift != 0) {
115: return keys[ivaluesShift + index];
116: }
117: return 0;
118: }
119: return defaultValue;
120: }
121:
122: /**
123: * Get integer value assigned with key.
124: * @return key integer value or defaultValue if key does not exist or does
125: * not have int value
126: * @throws RuntimeException if key does not exist
127: */
128: public int getExistingInt(int key) {
129: if (key < 0)
130: Context.codeBug();
131: int index = findIndex(key);
132: if (0 <= index) {
133: if (ivaluesShift != 0) {
134: return keys[ivaluesShift + index];
135: }
136: return 0;
137: }
138: // Key must exist
139: Context.codeBug();
140: return 0;
141: }
142:
143: /**
144: * Set object value of the key.
145: * If key does not exist, also set its int value to 0.
146: */
147: public void put(int key, Object value) {
148: if (key < 0)
149: Context.codeBug();
150: int index = ensureIndex(key, false);
151: if (values == null) {
152: values = new Object[1 << power];
153: }
154: values[index] = value;
155: }
156:
157: /**
158: * Set int value of the key.
159: * If key does not exist, also set its object value to null.
160: */
161: public void put(int key, int value) {
162: if (key < 0)
163: Context.codeBug();
164: int index = ensureIndex(key, true);
165: if (ivaluesShift == 0) {
166: int N = 1 << power;
167: // keys.length can be N * 2 after clear which set ivaluesShift to 0
168: if (keys.length != N * 2) {
169: int[] tmp = new int[N * 2];
170: System.arraycopy(keys, 0, tmp, 0, N);
171: keys = tmp;
172: }
173: ivaluesShift = N;
174: }
175: keys[ivaluesShift + index] = value;
176: }
177:
178: public void remove(int key) {
179: if (key < 0)
180: Context.codeBug();
181: int index = findIndex(key);
182: if (0 <= index) {
183: keys[index] = DELETED;
184: --keyCount;
185: // Allow to GC value and make sure that new key with the deleted
186: // slot shall get proper default values
187: if (values != null) {
188: values[index] = null;
189: }
190: if (ivaluesShift != 0) {
191: keys[ivaluesShift + index] = 0;
192: }
193: }
194: }
195:
196: public void clear() {
197: int N = 1 << power;
198: if (keys != null) {
199: for (int i = 0; i != N; ++i) {
200: keys[i] = EMPTY;
201: }
202: if (values != null) {
203: for (int i = 0; i != N; ++i) {
204: values[i] = null;
205: }
206: }
207: }
208: ivaluesShift = 0;
209: keyCount = 0;
210: occupiedCount = 0;
211: }
212:
213: /** Return array of present keys */
214: public int[] getKeys() {
215: int[] keys = this .keys;
216: int n = keyCount;
217: int[] result = new int[n];
218: for (int i = 0; n != 0; ++i) {
219: int entry = keys[i];
220: if (entry != EMPTY && entry != DELETED) {
221: result[--n] = entry;
222: }
223: }
224: return result;
225: }
226:
227: private static int tableLookupStep(int fraction, int mask, int power) {
228: int shift = 32 - 2 * power;
229: if (shift >= 0) {
230: return ((fraction >>> shift) & mask) | 1;
231: } else {
232: return (fraction & (mask >>> -shift)) | 1;
233: }
234: }
235:
236: private int findIndex(int key) {
237: int[] keys = this .keys;
238: if (keys != null) {
239: int fraction = key * A;
240: int index = fraction >>> (32 - power);
241: int entry = keys[index];
242: if (entry == key) {
243: return index;
244: }
245: if (entry != EMPTY) {
246: // Search in table after first failed attempt
247: int mask = (1 << power) - 1;
248: int step = tableLookupStep(fraction, mask, power);
249: int n = 0;
250: do {
251: if (check) {
252: if (n >= occupiedCount)
253: Context.codeBug();
254: ++n;
255: }
256: index = (index + step) & mask;
257: entry = keys[index];
258: if (entry == key) {
259: return index;
260: }
261: } while (entry != EMPTY);
262: }
263: }
264: return -1;
265: }
266:
267: // Insert key that is not present to table without deleted entries
268: // and enough free space
269: private int insertNewKey(int key) {
270: if (check && occupiedCount != keyCount)
271: Context.codeBug();
272: if (check && keyCount == 1 << power)
273: Context.codeBug();
274: int[] keys = this .keys;
275: int fraction = key * A;
276: int index = fraction >>> (32 - power);
277: if (keys[index] != EMPTY) {
278: int mask = (1 << power) - 1;
279: int step = tableLookupStep(fraction, mask, power);
280: int firstIndex = index;
281: do {
282: if (check && keys[index] == DELETED)
283: Context.codeBug();
284: index = (index + step) & mask;
285: if (check && firstIndex == index)
286: Context.codeBug();
287: } while (keys[index] != EMPTY);
288: }
289: keys[index] = key;
290: ++occupiedCount;
291: ++keyCount;
292: return index;
293: }
294:
295: private void rehashTable(boolean ensureIntSpace) {
296: if (keys != null) {
297: // Check if removing deleted entries would free enough space
298: if (keyCount * 2 >= occupiedCount) {
299: // Need to grow: less then half of deleted entries
300: ++power;
301: }
302: }
303: int N = 1 << power;
304: int[] old = keys;
305: int oldShift = ivaluesShift;
306: if (oldShift == 0 && !ensureIntSpace) {
307: keys = new int[N];
308: } else {
309: ivaluesShift = N;
310: keys = new int[N * 2];
311: }
312: for (int i = 0; i != N; ++i) {
313: keys[i] = EMPTY;
314: }
315:
316: Object[] oldValues = values;
317: if (oldValues != null) {
318: values = new Object[N];
319: }
320:
321: int oldCount = keyCount;
322: occupiedCount = 0;
323: if (oldCount != 0) {
324: keyCount = 0;
325: for (int i = 0, remaining = oldCount; remaining != 0; ++i) {
326: int key = old[i];
327: if (key != EMPTY && key != DELETED) {
328: int index = insertNewKey(key);
329: if (oldValues != null) {
330: values[index] = oldValues[i];
331: }
332: if (oldShift != 0) {
333: keys[ivaluesShift + index] = old[oldShift + i];
334: }
335: --remaining;
336: }
337: }
338: }
339: }
340:
341: // Ensure key index creating one if necessary
342: private int ensureIndex(int key, boolean intType) {
343: int index = -1;
344: int firstDeleted = -1;
345: int[] keys = this .keys;
346: if (keys != null) {
347: int fraction = key * A;
348: index = fraction >>> (32 - power);
349: int entry = keys[index];
350: if (entry == key) {
351: return index;
352: }
353: if (entry != EMPTY) {
354: if (entry == DELETED) {
355: firstDeleted = index;
356: }
357: // Search in table after first failed attempt
358: int mask = (1 << power) - 1;
359: int step = tableLookupStep(fraction, mask, power);
360: int n = 0;
361: do {
362: if (check) {
363: if (n >= occupiedCount)
364: Context.codeBug();
365: ++n;
366: }
367: index = (index + step) & mask;
368: entry = keys[index];
369: if (entry == key) {
370: return index;
371: }
372: if (entry == DELETED && firstDeleted < 0) {
373: firstDeleted = index;
374: }
375: } while (entry != EMPTY);
376: }
377: }
378: // Inserting of new key
379: if (check && keys != null && keys[index] != EMPTY)
380: Context.codeBug();
381: if (firstDeleted >= 0) {
382: index = firstDeleted;
383: } else {
384: // Need to consume empty entry: check occupation level
385: if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {
386: // Too litle unused entries: rehash
387: rehashTable(intType);
388: keys = this .keys;
389: return insertNewKey(key);
390: }
391: ++occupiedCount;
392: }
393: keys[index] = key;
394: ++keyCount;
395: return index;
396: }
397:
398: private void writeObject(ObjectOutputStream out) throws IOException {
399: out.defaultWriteObject();
400:
401: int count = keyCount;
402: if (count != 0) {
403: boolean hasIntValues = (ivaluesShift != 0);
404: boolean hasObjectValues = (values != null);
405: out.writeBoolean(hasIntValues);
406: out.writeBoolean(hasObjectValues);
407:
408: for (int i = 0; count != 0; ++i) {
409: int key = keys[i];
410: if (key != EMPTY && key != DELETED) {
411: --count;
412: out.writeInt(key);
413: if (hasIntValues) {
414: out.writeInt(keys[ivaluesShift + i]);
415: }
416: if (hasObjectValues) {
417: out.writeObject(values[i]);
418: }
419: }
420: }
421: }
422: }
423:
424: private void readObject(ObjectInputStream in) throws IOException,
425: ClassNotFoundException {
426: in.defaultReadObject();
427:
428: int writtenKeyCount = keyCount;
429: if (writtenKeyCount != 0) {
430: keyCount = 0;
431: boolean hasIntValues = in.readBoolean();
432: boolean hasObjectValues = in.readBoolean();
433:
434: int N = 1 << power;
435: if (hasIntValues) {
436: keys = new int[2 * N];
437: ivaluesShift = N;
438: } else {
439: keys = new int[N];
440: }
441: for (int i = 0; i != N; ++i) {
442: keys[i] = EMPTY;
443: }
444: if (hasObjectValues) {
445: values = new Object[N];
446: }
447: for (int i = 0; i != writtenKeyCount; ++i) {
448: int key = in.readInt();
449: int index = insertNewKey(key);
450: if (hasIntValues) {
451: int ivalue = in.readInt();
452: keys[ivaluesShift + index] = ivalue;
453: }
454: if (hasObjectValues) {
455: values[index] = in.readObject();
456: }
457: }
458: }
459: }
460:
461: static final long serialVersionUID = -6916326879143724506L;
462:
463: // A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)
464: // See Knuth etc.
465: private static final int A = 0x9e3779b9;
466:
467: private static final int EMPTY = -1;
468: private static final int DELETED = -2;
469:
470: // Structure of kyes and values arrays (N == 1 << power):
471: // keys[0 <= i < N]: key value or EMPTY or DELETED mark
472: // values[0 <= i < N]: value of key at keys[i]
473: // keys[N <= i < 2N]: int values of keys at keys[i - N]
474:
475: private transient int[] keys;
476: private transient Object[] values;
477:
478: private int power;
479: private int keyCount;
480: private transient int occupiedCount; // == keyCount + deleted_count
481:
482: // If ivaluesShift != 0, keys[ivaluesShift + index] contains integer
483: // values associated with keys
484: private transient int ivaluesShift;
485:
486: // If true, enables consitency checks
487: private static final boolean check = false;
488:
489: /* TEST START
490:
491: public static void main(String[] args) {
492: if (!check) {
493: System.err.println("Set check to true and re-run");
494: throw new RuntimeException("Set check to true and re-run");
495: }
496:
497: UintMap map;
498: map = new UintMap();
499: testHash(map, 2);
500: map = new UintMap();
501: testHash(map, 10 * 1000);
502: map = new UintMap(30 * 1000);
503: testHash(map, 10 * 100);
504: map.clear();
505: testHash(map, 4);
506: map = new UintMap(0);
507: testHash(map, 10 * 100);
508: }
509:
510: private static void testHash(UintMap map, int N) {
511: System.out.print("."); System.out.flush();
512: for (int i = 0; i != N; ++i) {
513: map.put(i, i);
514: check(i == map.getInt(i, -1));
515: }
516:
517: System.out.print("."); System.out.flush();
518: for (int i = 0; i != N; ++i) {
519: map.put(i, i);
520: check(i == map.getInt(i, -1));
521: }
522:
523: System.out.print("."); System.out.flush();
524: for (int i = 0; i != N; ++i) {
525: map.put(i, new Integer(i));
526: check(-1 == map.getInt(i, -1));
527: Integer obj = (Integer)map.getObject(i);
528: check(obj != null && i == obj.intValue());
529: }
530:
531: check(map.size() == N);
532:
533: System.out.print("."); System.out.flush();
534: int[] keys = map.getKeys();
535: check(keys.length == N);
536: for (int i = 0; i != N; ++i) {
537: int key = keys[i];
538: check(map.has(key));
539: check(!map.isIntType(key));
540: check(map.isObjectType(key));
541: Integer obj = (Integer) map.getObject(key);
542: check(obj != null && key == obj.intValue());
543: }
544:
545:
546: System.out.print("."); System.out.flush();
547: for (int i = 0; i != N; ++i) {
548: check(-1 == map.getInt(i, -1));
549: }
550:
551: System.out.print("."); System.out.flush();
552: for (int i = 0; i != N; ++i) {
553: map.put(i * i, i);
554: check(i == map.getInt(i * i, -1));
555: }
556:
557: System.out.print("."); System.out.flush();
558: for (int i = 0; i != N; ++i) {
559: check(i == map.getInt(i * i, -1));
560: }
561:
562: System.out.print("."); System.out.flush();
563: for (int i = 0; i != N; ++i) {
564: map.put(i * i, new Integer(i));
565: check(-1 == map.getInt(i * i, -1));
566: map.remove(i * i);
567: check(!map.has(i * i));
568: map.put(i * i, i);
569: check(map.isIntType(i * i));
570: check(null == map.getObject(i * i));
571: map.remove(i * i);
572: check(!map.isObjectType(i * i));
573: check(!map.isIntType(i * i));
574: }
575:
576: int old_size = map.size();
577: for (int i = 0; i != N; ++i) {
578: map.remove(i * i);
579: check(map.size() == old_size);
580: }
581:
582: System.out.print("."); System.out.flush();
583: map.clear();
584: check(map.size() == 0);
585: for (int i = 0; i != N; ++i) {
586: map.put(i * i, i);
587: map.put(i * i + 1, new Double(i+0.5));
588: }
589: checkSameMaps(map, (UintMap)writeAndRead(map));
590:
591: System.out.print("."); System.out.flush();
592: map = new UintMap(0);
593: checkSameMaps(map, (UintMap)writeAndRead(map));
594: map = new UintMap(1);
595: checkSameMaps(map, (UintMap)writeAndRead(map));
596: map = new UintMap(1000);
597: checkSameMaps(map, (UintMap)writeAndRead(map));
598:
599: System.out.print("."); System.out.flush();
600: map = new UintMap(N / 10);
601: for (int i = 0; i != N; ++i) {
602: map.put(2*i+1, i);
603: }
604: checkSameMaps(map, (UintMap)writeAndRead(map));
605:
606: System.out.print("."); System.out.flush();
607: map = new UintMap(N / 10);
608: for (int i = 0; i != N; ++i) {
609: map.put(2*i+1, i);
610: }
611: for (int i = 0; i != N / 2; ++i) {
612: map.remove(2*i+1);
613: }
614: checkSameMaps(map, (UintMap)writeAndRead(map));
615:
616: System.out.print("."); System.out.flush();
617: map = new UintMap();
618: for (int i = 0; i != N; ++i) {
619: map.put(2*i+1, new Double(i + 10));
620: }
621: for (int i = 0; i != N / 2; ++i) {
622: map.remove(2*i+1);
623: }
624: checkSameMaps(map, (UintMap)writeAndRead(map));
625:
626: System.out.println(); System.out.flush();
627:
628: }
629:
630: private static void checkSameMaps(UintMap map1, UintMap map2) {
631: check(map1.size() == map2.size());
632: int[] keys = map1.getKeys();
633: check(keys.length == map1.size());
634: for (int i = 0; i != keys.length; ++i) {
635: int key = keys[i];
636: check(map2.has(key));
637: check(map1.isObjectType(key) == map2.isObjectType(key));
638: check(map1.isIntType(key) == map2.isIntType(key));
639: Object o1 = map1.getObject(key);
640: Object o2 = map2.getObject(key);
641: if (map1.isObjectType(key)) {
642: check(o1.equals(o2));
643: }else {
644: check(map1.getObject(key) == null);
645: check(map2.getObject(key) == null);
646: }
647: if (map1.isIntType(key)) {
648: check(map1.getExistingInt(key) == map2.getExistingInt(key));
649: }else {
650: check(map1.getInt(key, -10) == -10);
651: check(map1.getInt(key, -11) == -11);
652: check(map2.getInt(key, -10) == -10);
653: check(map2.getInt(key, -11) == -11);
654: }
655: }
656: }
657:
658: private static void check(boolean condition) {
659: if (!condition) Context.codeBug();
660: }
661:
662: private static Object writeAndRead(Object obj) {
663: try {
664: java.io.ByteArrayOutputStream
665: bos = new java.io.ByteArrayOutputStream();
666: java.io.ObjectOutputStream
667: out = new java.io.ObjectOutputStream(bos);
668: out.writeObject(obj);
669: out.close();
670: byte[] data = bos.toByteArray();
671: java.io.ByteArrayInputStream
672: bis = new java.io.ByteArrayInputStream(data);
673: java.io.ObjectInputStream
674: in = new java.io.ObjectInputStream(bis);
675: Object result = in.readObject();
676: in.close();
677: return result;
678: }catch (Exception ex) {
679: ex.printStackTrace();
680: throw new RuntimeException("Unexpected");
681: }
682: }
683:
684: // TEST END */
685: }
|