UintMap


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