src/org/mozilla/javascript/UintMap.java

   1 /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-\r
   2  *\r
   3  * The contents of this file are subject to the Netscape Public\r
   4  * License Version 1.1 (the "License"); you may not use this file\r
   5  * except in compliance with the License. You may obtain a copy of\r
   6  * the License at http://www.mozilla.org/NPL/\r
   7  *\r
   8  * Software distributed under the License is distributed on an "AS\r
   9  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express oqr\r
  10  * implied. See the License for the specific language governing\r
  11  * rights and limitations under the License.\r
  12  *\r
  13  * The Original Code is Rhino code, released\r
  14  * May 6, 1999.\r
  15  *\r
  16  * The Initial Developer of the Original Code is Netscape\r
  17  * Communications Corporation.  Portions created by Netscape are\r
  18  * Copyright (C) 1997-2000 Netscape Communications Corporation. All\r
  19  * Rights Reserved.\r
  20  *\r
  21  * Contributor(s):\r
  22  * Igor Bukanov\r
  23  *\r
  24  * Alternatively, the contents of this file may be used under the\r
  25  * terms of the GNU Public License (the "GPL"), in which case the\r
  26  * provisions of the GPL are applicable instead of those above.\r
  27  * If you wish to allow use of your version of this file only\r
  28  * under the terms of the GPL and not to allow others to use your\r
  29  * version of this file under the NPL, indicate your decision by\r
  30  * deleting the provisions above and replace them with the notice\r
  31  * and other provisions required by the GPL.  If you do not delete\r
  32  * the provisions above, a recipient may use your version of this\r
  33  * file under either the NPL or the GPL.\r
  34  */\r
  35 \r
  36 package org.mozilla.javascript;\r
  37 \r
  38 /**\r
  39  * Map to associate non-negative integers to objects or integers.\r
  40  * The map does not synchronize any of its operation, so either use\r
  41  * it from a single thread or do own synchronization or perform all mutation\r
  42  * operations on one thread before passing the map to others\r
  43  *\r
  44  * @author Igor Bukanov\r
  45  *\r
  46  */\r
  47 \r
  48 class UintMap {\r
  49 \r
  50 // Map implementation via hashtable,\r
  51 // follows "The Art of Computer Programming" by Donald E. Knuth\r
  52 \r
  53     public UintMap() {\r
  54         this(4);\r
  55     }\r
  56 \r
  57     public UintMap(int initialCapacity) {\r
  58         if (checkWorld) check(initialCapacity >= 0);\r
  59         // Table grow when number of stored keys >= 3/4 of max capacity\r
  60         int minimalCapacity = initialCapacity * 4 / 3;\r
  61         int i;\r
  62         for (i = 2; (1 << i) < minimalCapacity; ++i) { }\r
  63         minimalPower = i;\r
  64         if (checkSelf) check(minimalPower >= 2);\r
  65     }\r
  66 \r
  67     public boolean isEmpty() {\r
  68         return keyCount == 0;\r
  69     }\r
  70 \r
  71     public int size() {\r
  72         return keyCount;\r
  73     }\r
  74 \r
  75     public boolean has(int key) {\r
  76         if (checkWorld) check(key >= 0);\r
  77         return 0 <= findIndex(key);\r
  78     }\r
  79 \r
  80     public boolean isObjectType(int key) {\r
  81         if (checkWorld) check(key >= 0);\r
  82         int index = findIndex(key);\r
  83         return index >= 0 && isObjectTypeValue(index);\r
  84     }\r
  85 \r
  86     public boolean isIntType(int key) {\r
  87         if (checkWorld) check(key >= 0);\r
  88         int index = findIndex(key);\r
  89         return index >= 0 && !isObjectTypeValue(index);\r
  90     }\r
  91 \r
  92     /**\r
  93      * Get object value assigned with key.\r
  94      * @return key object value or null if key is absent or does\r
  95      * not have object value\r
  96      */\r
  97     public Object getObject(int key) {\r
  98         if (checkWorld) check(key >= 0);\r
  99         if (values != null) {\r
 100             int index = findIndex(key);\r
 101             if (0 <= index) {\r
 102                 return values[index];\r
 103             }\r
 104         }\r
 105         return null;\r
 106     }\r
 107 \r
 108     /**\r
 109      * Get integer value assigned with key.\r
 110      * @return key integer value or defaultValue if key is absent or does\r
 111      * not have int value\r
 112      */\r
 113     public int getInt(int key, int defaultValue) {\r
 114         if (checkWorld) check(key >= 0);\r
 115         if (ivaluesShift != 0) {\r
 116             int index = findIndex(key);\r
 117             if (0 <= index) {\r
 118                 if (!isObjectTypeValue(index)) {\r
 119                     return keys[ivaluesShift + index];\r
 120                 }\r
 121             }\r
 122         }\r
 123         return defaultValue;\r
 124     }\r
 125 \r
 126     /**\r
 127      * Get integer value assigned with key.\r
 128      * @return key integer value or defaultValue if key does not exist or does\r
 129      * not have int value\r
 130      * @throws RuntimeException if key does not exist or does\r
 131      * not have int value\r
 132      */\r
 133     public int getExistingInt(int key) {\r
 134         if (checkWorld) check(key >= 0);\r
 135         if (ivaluesShift != 0) {\r
 136             int index = findIndex(key);\r
 137             if (0 <= index) {\r
 138                 if (!isObjectTypeValue(index)) {\r
 139                     return keys[ivaluesShift + index];\r
 140                 }\r
 141             }\r
 142         }\r
 143         // Key must exist\r
 144         if (checkWorld) check(false);\r
 145         return 0;\r
 146     }\r
 147 \r
 148     public void put(int key, Object value) {\r
 149         if (checkWorld) check(key >= 0 && value != null);\r
 150         int index = ensureIndex(key, false);\r
 151         if (values == null) {\r
 152             values = new Object[1 << power];\r
 153         }\r
 154         values[index] = value;\r
 155     }\r
 156 \r
 157     public void put(int key, int value) {\r
 158         if (checkWorld) check(key >= 0);\r
 159         int index = ensureIndex(key, true);\r
 160         if (ivaluesShift == 0) {\r
 161             int N = 1 << power;\r
 162             int[] tmp = new int[N * 2];\r
 163             System.arraycopy(keys, 0, tmp, 0, N);\r
 164             keys = tmp;\r
 165             ivaluesShift = N;\r
 166         }\r
 167         keys[ivaluesShift + index] = value;\r
 168         if (values != null) { values[index] = null; }\r
 169     }\r
 170 \r
 171     public void remove(int key) {\r
 172         if (checkWorld) check(key >= 0);\r
 173         int index = findIndex(key);\r
 174         if (0 <= index) {\r
 175             keys[index] = DELETED;\r
 176             --keyCount;\r
 177             if (values != null) { values[index] = null; }\r
 178         }\r
 179     }\r
 180 \r
 181     public void clear() {\r
 182         power = 0;\r
 183         keys = null;\r
 184         values = null;\r
 185         ivaluesShift = 0;\r
 186         keyCount = 0;\r
 187         occupiedCount = 0;\r
 188     }\r
 189 \r
 190     /** Return array of present keys */\r
 191     public int[] getKeys() {\r
 192         int[] keys = this.keys;\r
 193         int n = keyCount;\r
 194         int[] result = new int[n];\r
 195         for (int i = 0; n != 0; ++i) {\r
 196             int entry = keys[i];\r
 197             if (entry != EMPTY && entry != DELETED) {\r
 198                 result[--n] = entry;\r
 199             }\r
 200         }\r
 201         return result;\r
 202     }\r
 203 \r
 204     private static int tableLookupStep(int fraction, int mask, int power) {\r
 205         int shift = 32 - 2 * power;\r
 206         if (shift >= 0) {\r
 207             return ((fraction >>> shift) & mask) | 1;\r
 208         }\r
 209         else {\r
 210             return (fraction & (mask >>> -shift)) | 1;\r
 211         }\r
 212     }\r
 213 \r
 214     private int findIndex(int key) {\r
 215         int[] keys = this.keys;\r
 216         if (keys != null) {\r
 217             int fraction = key * A;\r
 218             int index = fraction >>> (32 - power);\r
 219             int entry = keys[index];\r
 220             if (entry == key) { return index; }\r
 221             if (entry != EMPTY) {\r
 222                 // Search in table after first failed attempt\r
 223                 int mask = (1 << power) - 1;\r
 224                 int step = tableLookupStep(fraction, mask, power);\r
 225                 int n = 0;\r
 226                 do {\r
 227                     if (checkSelf) check(n++ < occupiedCount);\r
 228                     index = (index + step) & mask;\r
 229                     entry = keys[index];\r
 230                     if (entry == key) { return index; }\r
 231                 } while (entry != EMPTY);\r
 232             }\r
 233         }\r
 234         return -1;\r
 235     }\r
 236 \r
 237     private int getFreeIndex(int key) {\r
 238         int[] keys = this.keys;\r
 239         int fraction = key * A;\r
 240         int index = fraction >>> (32 - power);\r
 241         if (keys[index] != EMPTY) {\r
 242             int mask = (1 << power) - 1;\r
 243             int step = tableLookupStep(fraction, mask, power);\r
 244             int firstIndex = index;\r
 245             do {\r
 246                 if (checkSelf) check(keys[index] != DELETED);\r
 247                 index = (index + step) & mask;\r
 248                 if (checkSelf) check(firstIndex != index);\r
 249             } while (keys[index] != EMPTY);\r
 250         }\r
 251         return index;\r
 252     }\r
 253 \r
 254     private void rehashTable(boolean ensureIntSpace) {\r
 255         if (keys == null) { power = minimalPower; }\r
 256         else {\r
 257             // Check if removing deleted entries would free enough space\r
 258             if (keyCount * 2 >= occupiedCount) {\r
 259                 // Need to grow: less then half of deleted entries\r
 260                 ++power;\r
 261             }\r
 262         }\r
 263         int N = 1 << power;\r
 264         int[] old = keys;\r
 265         int oldShift = ivaluesShift;\r
 266         if (oldShift == 0 && !ensureIntSpace) {\r
 267             keys = new int[N];\r
 268         }\r
 269         else {\r
 270             ivaluesShift = N; keys = new int[N * 2];\r
 271         }\r
 272         for (int i = 0; i != N; ++i) { keys[i] = EMPTY; }\r
 273 \r
 274         Object[] oldValues = values;\r
 275         if (oldValues != null) { values = new Object[N]; }\r
 276 \r
 277         if (old != null) {\r
 278             for (int i = 0, remaining = keyCount; remaining != 0; ++i) {\r
 279                 int entry = old[i];\r
 280                 if (entry != EMPTY && entry != DELETED) {\r
 281                     int index = getFreeIndex(entry);\r
 282                     keys[index] = entry;\r
 283                     if (oldValues != null) {\r
 284                         values[index] = oldValues[i];\r
 285                     }\r
 286                     if (oldShift != 0) {\r
 287                         keys[ivaluesShift + index] = old[oldShift + i];\r
 288                     }\r
 289                     --remaining;\r
 290                 }\r
 291             }\r
 292         }\r
 293         occupiedCount = keyCount;\r
 294     }\r
 295 \r
 296 // Ensure key index creating one if necessary\r
 297     private int ensureIndex(int key, boolean intType) {\r
 298         int index = -1;\r
 299         int firstDeleted = -1;\r
 300         int[] keys = this.keys;\r
 301         if (keys != null) {\r
 302             int fraction = key * A;\r
 303             index = fraction >>> (32 - power);\r
 304             int entry = keys[index];\r
 305             if (entry == key) { return index; }\r
 306             if (entry != EMPTY) {\r
 307                 if (entry == DELETED) { firstDeleted = index; }\r
 308                 // Search in table after first failed attempt\r
 309                 int mask = (1 << power) - 1;\r
 310                 int step = tableLookupStep(fraction, mask, power);\r
 311                 int n = 0;\r
 312                 do {\r
 313                     if (checkSelf) check(n++ < occupiedCount);\r
 314                     index = (index + step) & mask;\r
 315                     entry = keys[index];\r
 316                     if (entry == key) { return index; }\r
 317                     if (entry == DELETED && firstDeleted < 0) {\r
 318                         firstDeleted = index;\r
 319                     }\r
 320                 } while (entry != EMPTY);\r
 321             }\r
 322         }\r
 323         // Inserting of new key\r
 324         if (checkSelf) check(keys == null || keys[index] == EMPTY);\r
 325         if (firstDeleted >= 0) {\r
 326             index = firstDeleted;\r
 327         }\r
 328         else {\r
 329             // Need to consume empty entry: check occupation level\r
 330             if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {\r
 331                 // Too litle unused entries: rehash\r
 332                 rehashTable(intType);\r
 333                 keys = this.keys;\r
 334                 index = getFreeIndex(key);\r
 335             }\r
 336             ++occupiedCount;\r
 337         }\r
 338         keys[index] = key;\r
 339         ++keyCount;\r
 340         return index;\r
 341     }\r
 342 \r
 343     private boolean isObjectTypeValue(int index) {\r
 344         if (checkSelf) check(index >= 0 && index < (1 << power));\r
 345         return values != null && values[index] != null;\r
 346     }\r
 347 \r
 348     private static void check(boolean condition) {\r
 349         if (!condition) { throw new RuntimeException(); }\r
 350     }\r
 351 \r
 352 // Rudimentary support for Design-by-Contract\r
 353     private static final boolean checkWorld = true;\r
 354     private static final boolean checkSelf = checkWorld && false;\r
 355 \r
 356 // A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)\r
 357 // See Knuth etc.\r
 358     private static final int A = 0x9e3779b9;\r
 359 \r
 360     private static final int EMPTY = -1;\r
 361     private static final int DELETED = -2;\r
 362 \r
 363 // Structure of kyes and values arrays (N == 1 << power):\r
 364 // keys[0 <= i < N]: key value or EMPTY or DELETED mark\r
 365 // values[0 <= i < N]: value of key at keys[i]\r
 366 // keys[N <= i < 2N]: int values of keys at keys[i - N]\r
 367 \r
 368     private int[] keys;\r
 369     private Object[] values;\r
 370 \r
 371     private int minimalPower;\r
 372     private int power;\r
 373     private int keyCount;\r
 374     private int occupiedCount; // == keyCount + deleted_count\r
 375 \r
 376     // If ivaluesShift != 0, keys[ivaluesShift + index] contains integer\r
 377     // values associated with keys\r
 378     private int ivaluesShift;\r
 379 \r
 380 /*\r
 381     public static void main(String[] args) {\r
 382         UintMap map;\r
 383         map = new UintMap();\r
 384         testHash(map, 10 * 1000);\r
 385         map = new UintMap(30 * 1000);\r
 386         testHash(map, 10 * 100);\r
 387         map.clear();\r
 388         testHash(map, 4);\r
 389         map = new UintMap(0);\r
 390         testHash(map, 10 * 100);\r
 391     }\r
 392 \r
 393     private static void testHash(UintMap map, int N) {\r
 394         System.out.print("."); System.out.flush();\r
 395         for (int i = 0; i != N; ++i) {\r
 396             map.put(i, i);\r
 397             check(i == map.getInt(i, -1));\r
 398         }\r
 399 \r
 400         System.out.print("."); System.out.flush();\r
 401         for (int i = 0; i != N; ++i) {\r
 402             map.put(i, i);\r
 403             check(i == map.getInt(i, -1));\r
 404         }\r
 405 \r
 406         System.out.print("."); System.out.flush();\r
 407         for (int i = 0; i != N; ++i) {\r
 408             map.put(i, new Integer(i));\r
 409             check(-1 == map.getInt(i, -1));\r
 410             Integer obj = (Integer)map.getObject(i);\r
 411             check(obj != null && i == obj.intValue());\r
 412         }\r
 413 \r
 414         check(map.size() == N);\r
 415 \r
 416         System.out.print("."); System.out.flush();\r
 417         int[] keys = map.getKeys();\r
 418         check(keys.length == N);\r
 419         for (int i = 0; i != N; ++i) {\r
 420             int key = keys[i];\r
 421             check(map.has(key));\r
 422             check(!map.isIntType(key));\r
 423             check(map.isObjectType(key));\r
 424             Integer obj = (Integer) map.getObject(key);\r
 425             check(obj != null && key == obj.intValue());\r
 426         }\r
 427 \r
 428 \r
 429         System.out.print("."); System.out.flush();\r
 430         for (int i = 0; i != N; ++i) {\r
 431             check(-1 == map.getInt(i, -1));\r
 432         }\r
 433 \r
 434         System.out.print("."); System.out.flush();\r
 435         for (int i = 0; i != N; ++i) {\r
 436             map.put(i * i, i);\r
 437             check(i == map.getInt(i * i, -1));\r
 438         }\r
 439 \r
 440         System.out.print("."); System.out.flush();\r
 441         for (int i = 0; i != N; ++i) {\r
 442             check(i == map.getInt(i * i, -1));\r
 443         }\r
 444 \r
 445         System.out.print("."); System.out.flush();\r
 446         for (int i = 0; i != N; ++i) {\r
 447             map.put(i * i, new Integer(i));\r
 448             check(-1 == map.getInt(i * i, -1));\r
 449             map.remove(i * i);\r
 450             check(!map.has(i * i));\r
 451             map.put(i * i, i);\r
 452             check(map.isIntType(i * i));\r
 453             check(null == map.getObject(i * i));\r
 454             map.remove(i * i);\r
 455             check(!map.isObjectType(i * i));\r
 456             check(!map.isIntType(i * i));\r
 457         }\r
 458 \r
 459         int old_size = map.size();\r
 460         for (int i = 0; i != N; ++i) {\r
 461             map.remove(i * i);\r
 462             check(map.size() == old_size);\r
 463         }\r
 464 \r
 465         System.out.println(); System.out.flush();\r
 466     }\r
 467 //*/\r
 468 }\r