2003/09/07 03:04:31
[org.ibex.core.git] / src / org / xwt / util / Hash.java
1 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
2 package org.xwt.util;
3
4 import java.util.*;
5
6 /** Implementation of an unsynchronized hash table, with one or two
7  *  keys, using Radke's quadradic residue linear probing instead of
8  *  buckets to minimize object count (less allocations, faster GC).
9  *  See C. Radke, Communications of the ACM, 1970, 103-105
10  */
11 public class Hash {
12
13     /** this object is inserted as key in a slot when the
14      *  corresponding value is removed -- this ensures that the
15      *  probing sequence for any given key remains the same even if
16      *  other keys are removed.
17      */
18     private static Object placeholder = new Object();
19
20     /** the number of entries with at least one non-null key */
21     private int usedslots = 0;
22
23     /** the number of entries with non-null values */
24     private int size = 0;
25
26     /** when num_slots < loadFactor * size, rehash into a bigger table */
27     private final int loadFactor;
28
29     /** primary keys */
30     private Object[] keys1 = null;
31
32     /** secondary keys; null if no secondary key has ever been added */
33     private Object[] keys2 = null;
34
35     /** the values for the table */
36     private Object[] vals = null;
37     
38     /** the number of entries with a non-null value */
39     public int size() { return size; }
40
41     /** empties the table */
42     public void clear() {
43         size = 0;
44         usedslots = 0;
45         for(int i=0; i<vals.length; i++) {
46             vals[i] = null;
47             keys1[i] = null;
48             if (keys2 != null) keys2[i] = null;
49         }
50     }
51
52     /** returns all the primary keys in the table */
53     public Object[] keys() {
54         int howmany = 0;
55         for(int i=0; i<vals.length; i++) if (keys1[i] != null) howmany++;
56         Object[] ret = new Object[howmany];
57         int where = 0;
58         for(int i=0; i<vals.length; i++) if (keys1[i] != null) ret[where++] = keys1[i];
59         return ret;
60     }
61
62     public Hash() { this(25, 3); }
63     public Hash(int initialcapacity, int loadFactor) {
64         // using a pseudoprime in the form 4x+3 ensures full coverage
65         initialcapacity = initialcapacity / 4;
66         initialcapacity = 4 * initialcapacity + 3;
67         keys1 = new Object[initialcapacity];
68         vals = new Object[initialcapacity];
69         this.loadFactor = loadFactor;
70     }
71     
72     public void remove(Object k1) { remove(k1, null); }
73     public void remove(Object k1, Object k2) { put(k1, k2, null); }
74
75     private void rehash() {
76         Object[] oldkeys1 = keys1;
77         Object[] oldkeys2 = keys2;
78         Object[] oldvals = vals;
79         keys1 = new Object[oldvals.length * 2];
80         keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
81         vals = new Object[oldvals.length * 2];
82         size = 0;
83         usedslots = 0;
84         for(int i=0; i<oldvals.length; i++)
85             if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
86                 put(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
87     }
88
89     public Object get(Object k1) { return get(k1, null); }
90     public Object get(Object k1, Object k2) {
91         if (k2 != null && keys2 == null) return null;
92         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
93         int dest = Math.abs(hash) % vals.length;
94         int odest = dest;
95         int tries = 1;
96         boolean plus = true;
97         while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
98             Object hk1 = keys1[dest];
99             Object hk2 = keys2 == null ? null : keys2[dest];
100             if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
101                 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
102                 return vals[dest];
103             }
104             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
105             if (plus) tries++;
106             plus = !plus;
107         }
108         return null;
109     }
110
111     public void put(Object k1, Object v) { put(k1, null, v); }
112     public void put(Object k1, Object k2, Object v) {
113         if (usedslots * loadFactor > vals.length) rehash();
114         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
115         int dest = Math.abs(hash) % vals.length;
116         int odest = dest;
117         boolean plus = true;
118         int tries = 1;
119         while (true) {
120             Object hk1 = keys1[dest];
121             Object hk2 = keys2 == null ? null : keys2[dest];
122             if (hk1 == null && hk2 == null) {                                         // empty slot
123                 if (v == null) return;
124                 size++;
125                 usedslots++;
126                 break;
127             }
128
129             if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&       // replacing former entry
130                 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
131
132                 // we don't actually remove things from the table; rather, we insert a placeholder
133                 if (v == null) {
134                     k1 = placeholder;
135                     k2 = null;
136                     size--;
137                 }
138                 break;
139             }
140
141             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
142             if (plus) tries++;
143             plus = !plus;
144         }
145
146         keys1[dest] = k1;
147         if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
148         if (keys2 != null) keys2[dest] = k2;
149         vals[dest] = v;
150     }
151
152 }
153
154