home *** CD-ROM | disk | FTP | other *** search
/ Apple Developer Connection Student Program / ADC Tools Sampler CD Disk 3 1999.iso / Metrowerks CodeWarrior / Java Support / Java_Source / IFC_112 / netscape / util / IdHashtable.java < prev    next >
Encoding:
Text File  |  1999-05-28  |  3.6 KB  |  145 lines  |  [TEXT/CWIE]
  1. // IdHashtable.java
  2. // By Ned Etcode
  3. // Copyright 1995, 1996, 1997 Netscape Communications Corp.  All rights reserved.
  4.  
  5. package netscape.util;
  6.  
  7. /** @private
  8.   */
  9. public class IdHashtable {
  10.     /** For the multiplicative hash choose A = ((sqrt(5) - 1) / 2) * (1 << 32)
  11.       */
  12.     static final int A = 0x9e3779b9;
  13.  
  14.     /** You cannot store this value in the table.  This value should
  15.       * probably change to -1 if this class is made public.
  16.       */
  17.     static final int NOT_FOUND = 0;
  18.  
  19.     int power;
  20.     int count;
  21.     int maxCount;
  22.     int indexMask;
  23.     Object keys[];
  24.     int values[];
  25.     boolean equals;
  26.  
  27.     /** We have two different uses of this class: one wants equals()
  28.       * comparisons, the other wants == comparisons.
  29.       */
  30.     IdHashtable(boolean equals) {
  31.         super();
  32.  
  33.         this.equals = equals;
  34.         power = 5;
  35.         count = 0;
  36.         indexMask = (1 << power) - 1;
  37.         maxCount = (3 * (1 << power)) / 4;
  38.         keys = new Object[1 << power];
  39.         values = new int[1 << power];
  40.     }
  41.  
  42.     private boolean equalKeys(Object keyA, Object keyB) {
  43.         if (keyA == keyB)
  44.             return true;
  45.  
  46.         if (equals)
  47.             return keyA.equals(keyB);
  48.  
  49.         return false;
  50.     }
  51.  
  52.     private void rehash() {
  53.         int i, oldLength, oldValues[];
  54.         Object oldKeys[];
  55.  
  56.         oldLength = keys.length;
  57.         oldKeys = keys;
  58.         oldValues = values;
  59.  
  60.         power++;
  61.         count = 0;
  62.         indexMask = (1 << power) - 1;
  63.         maxCount = (3 * (1 << power)) / 4;
  64.         keys = new Object[1 << power];
  65.         values = new int[1 << power];
  66.  
  67.         for (i = 0; i < oldLength; i++) {
  68.             if (oldKeys[i] != null)
  69.                 putKnownAbsent(oldKeys[i], oldValues[i]);
  70.         }
  71.     }
  72.  
  73.     int get(Object object) {
  74.         int product, index, step, probeCount;
  75.         Object key;
  76.  
  77.         // On sparc it appears that the last 3 bits of Object.hashCode() are
  78.         // insignificant!  ALERT!
  79.  
  80.         product = object.hashCode() * A;
  81.         index = product >>> (32 - power);
  82.  
  83.         key = keys[index];
  84.         if (key == null)
  85.             return NOT_FOUND;
  86.         else if (equalKeys(key, object))
  87.             return values[index];
  88.  
  89.         step = ((product >>> (32 - 2 * power)) & indexMask) | 1;
  90.         probeCount = 1;
  91.  
  92.         do {
  93.             probeCount++;
  94.             index = (index + step) & indexMask;
  95.  
  96.             key = keys[index];
  97.             if (key == null)
  98.                 return NOT_FOUND;
  99.             else if (equalKeys(key, object))
  100.                 return values[index];
  101.  
  102.         } while (probeCount <= count);
  103.  
  104.         throw new InconsistencyException("IdHashtable overflow");
  105.     }
  106.  
  107.     void putKnownAbsent(Object object, int id) {
  108.         int product, index, step, probeCount;
  109.         Object key;
  110.  
  111.         if (count >= maxCount)
  112.             rehash();
  113.  
  114.         // On sparc it appears that the last 3 bits of Object.hashCode() are
  115.         // insignificant!  ALERT!
  116.  
  117.         product = object.hashCode() * A;
  118.         index = product >>> (32 - power);
  119.  
  120.         if (keys[index] == null) {
  121.             keys[index] = object;
  122.             values[index] = id;
  123.             count++;
  124.             return;
  125.         }
  126.  
  127.         step = ((product >>> (32 - 2 * power)) & indexMask) | 1;
  128.         probeCount = 1;
  129.  
  130.         do {
  131.             probeCount++;
  132.             index = (index + step) & indexMask;
  133.  
  134.             if (keys[index] == null) {
  135.                 keys[index] = object;
  136.                 values[index] = id;
  137.                 count++;
  138.                 return;
  139.             }
  140.         } while (probeCount <= count);
  141.  
  142.         throw new InconsistencyException("IdHashtable overflow");
  143.     }
  144. }
  145.