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