src/org/ibex/util/Hash.java

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