Java > Open Source Codes > com > google > gwt > dev > js > rhino > ObjToIntMap


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags