src/org/ibex/util/Hash.java

   1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
   2 // Licensed under the Apache Public Source License 2.0 ("the License").
   3 // You may not use this file except in compliance with the License.
   4
   5 package org.ibex.util;
   6
   7 import java.util.*;
   8
   9 /** Implementation of an unsynchronized hash table, with one or two
  10  *  keys, using Radke's quadradic residue linear probing instead of
  11  *  buckets to minimize object count (less allocations, faster GC).
  12  *  See C. Radke, Communications of the ACM, 1970, 103-105
  13  *
  14  *  Not threadsafe.
  15  */
  16 public class Hash implements java.io.Serializable {
  17
  18     public static final long serialVersionUID = 8177551301264350283L;
  19
  20     /** this object is inserted as key in a slot when the
  21      *  corresponding value is removed -- this ensures that the
  22      *  probing sequence for any given key remains the same even if
  23      *  other keys are removed.
  24      */
  25     // FIXME: this should have been static except that that makes it nonserializable
  26     private Object placeholder = new java.io.Serializable() { };
  27
  28     /** the number of entries with at least one non-null key */
  29     private int usedslots = 0;
  30
  31     /** the number of entries with non-null values */
  32     protected int size = 0;
  33
  34     /** when num_slots < loadFactor * size, rehash into a bigger table */
  35     private final int loadFactor;
  36
  37     /** primary keys */
  38     private Object[] keys1 = null;
  39
  40     /** secondary keys; null if no secondary key has ever been added */
  41     private Object[] keys2 = null;
  42
  43     /** the values for the table */
  44     private Object[] vals = null;
  45
  46     /** the number of entries with a non-null value */
  47     public int size() { return size; }
  48
  49     public Object[] dumpkeys() {
  50         return dumpkeys(new Object[size]);
  51     }
  52     public Object[] dumpkeys(Object[] ret) {
  53         int j = 0;
  54         for(int i=0; i<keys1.length; i++)
  55             if (keys1[i]!=null)
  56                 ret[j++] = keys1[i];
  57         return ret;
  58     }
  59
  60     public Object[] vals() {
  61         Object[] ret = new Object[size()];
  62         int j = 0;
  63         for(int i=0; i<vals.length; i++)
  64             if (vals[i] != null && vals[i] != placeholder)
  65                 ret[j++] = vals[i];
  66         return ret;
  67     }
  68
  69     /** empties the table */
  70     public void clear() {
  71         size = 0;
  72         usedslots = 0;
  73         for(int i=0; i<vals.length; i++) {
  74             vals[i] = null;
  75             keys1[i] = null;
  76             if (keys2 != null) keys2[i] = null;
  77         }
  78     }
  79
  80     /** returns all the primary keys in the table */
  81     public java.util.Enumeration enumerateKeys() { return new HashEnum(); }
  82
  83     public Hash() { this(25, 3); }
  84     public Hash(int initialcapacity, int loadFactor) {
  85         // using a pseudoprime in the form 4x+3 ensures full coverage
  86         initialcapacity = initialcapacity / 4;
  87         initialcapacity = 4 * initialcapacity + 3;
  88         keys1 = new Object[initialcapacity];
  89         vals = new Object[initialcapacity];
  90         this.loadFactor = loadFactor;
  91     }
  92
  93     public void remove(Object k1) { remove(k1, null); }
  94     public void remove(Object k1, Object k2) { put_(k1, k2, null); }
  95
  96     private void rehash() {
  97         Object[] oldkeys1 = keys1;
  98         Object[] oldkeys2 = keys2;
  99         Object[] oldvals = vals;
 100         keys1 = new Object[oldvals.length * 2];
 101         keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
 102         vals = new Object[oldvals.length * 2];
 103         size = 0;
 104         usedslots = 0;
 105         for(int i=0; i<oldvals.length; i++)
 106             if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
 107                 put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
 108     }
 109
 110     public Object get(Object k1) { return get(k1, null); }
 111     public Object get(Object k1, Object k2) {
 112         if (k2 != null && keys2 == null) return null;
 113         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
 114         int dest = Math.abs(hash) % vals.length;
 115         int odest = dest;
 116         int tries = 1;
 117         boolean plus = true;
 118         while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
 119             Object hk1 = keys1[dest];
 120             Object hk2 = keys2 == null ? null : keys2[dest];
 121             if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
 122                 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
 123                 return vals[dest];
 124             }
 125             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
 126             if (plus) tries++;
 127             plus = !plus;
 128         }
 129         return null;
 130     }
 131
 132     public void put(Object k1, Object v) { put(k1, null, v); }
 133     public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
 134     private void put_(Object k1, Object k2, Object v) {
 135         if (usedslots * loadFactor > vals.length) rehash();
 136         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
 137         int dest = Math.abs(hash) % vals.length;
 138         int odest = dest;
 139         boolean plus = true;
 140         int tries = 1;
 141         while (true) {
 142             Object hk1 = keys1[dest];
 143             Object hk2 = keys2 == null ? null : keys2[dest];
 144             if (hk1 == null && hk2 == null) {                                         // empty slot
 145                 if (v == null) return;
 146                 size++;
 147                 usedslots++;
 148                 break;
 149             }
 150
 151             if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&       // replacing former entry
 152                 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
 153
 154                 // we don't actually remove things from the table; rather, we insert a placeholder
 155                 if (v == null) {
 156                     k1 = placeholder;
 157                     k2 = null;
 158                     size--;
 159                 }
 160                 break;
 161             }
 162
 163             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
 164             if (plus) tries++;
 165             plus = !plus;
 166         }
 167
 168         keys1[dest] = k1;
 169         if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
 170         if (keys2 != null) keys2[dest] = k2;
 171         vals[dest] = v;
 172     }
 173
 174     private class HashEnum implements java.util.Enumeration {
 175         private int iterator = 0;
 176         private int found = 0;
 177
 178         public boolean hasMoreElements() {
 179             return found < usedslots;
 180         }
 181
 182         public Object nextElement() {
 183             if (!hasMoreElements()) throw new java.util.NoSuchElementException();
 184
 185             Object o = null;
 186             while (o == null) o = keys1[iterator++];
 187             if (o == null) throw new IllegalStateException("Didn't find an element, when I should have.");
 188             found++;
 189
 190             return o;
 191         }
 192     }
 193 }
 194
 195