propose-patch

[org.ibex.core.git] / src / org / xwt / util / Hash.java

diff --git a/src/org/xwt/util/Hash.java b/src/org/xwt/util/Hash.java
index 2d73b10..09ed008 100644 (file)
--- a/src/org/xwt/util/Hash.java
+++ b/src/org/xwt/util/Hash.java
@@ -1,4 +1,10 @@
-// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
+// Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
 package org.xwt.util;
 
 import java.util.*;
@@ -7,9 +13,10 @@ import java.util.*;
  *  keys, using Radke's quadradic residue linear probing instead of
  *  buckets to minimize object count (less allocations, faster GC).
  *  See C. Radke, Communications of the ACM, 1970, 103-105
+ *
+ *  Not threadsafe.
  */
 public class Hash {
-
     /** this object is inserted as key in a slot when the
      *  corresponding value is removed -- this ensures that the
      *  probing sequence for any given key remains the same even if
@@ -21,7 +28,7 @@ public class Hash {
     private int usedslots = 0;
 
     /** the number of entries with non-null values */
-    private int size = 0;
+    protected int size = 0;
 
     /** when num_slots < loadFactor * size, rehash into a bigger table */
     private final int loadFactor;
@@ -50,14 +57,7 @@ public class Hash {
     }
 
     /** returns all the primary keys in the table */
-    public Object[] keys() {
-        int howmany = 0;
-        for(int i=0; i<vals.length; i++) if (keys1[i] != null) howmany++;
-        Object[] ret = new Object[howmany];
-        int where = 0;
-        for(int i=0; i<vals.length; i++) if (keys1[i] != null) ret[where++] = keys1[i];
-        return ret;
-    }
+    public Enumeration keys() { return new HashEnum(); }
 
     public Hash() { this(25, 3); }
     public Hash(int initialcapacity, int loadFactor) {
@@ -70,7 +70,7 @@ public class Hash {
     }
     
     public void remove(Object k1) { remove(k1, null); }
-    public void remove(Object k1, Object k2) { put(k1, k2, null); }
+    public void remove(Object k1, Object k2) { put_(k1, k2, null); }
 
     private void rehash() {
         Object[] oldkeys1 = keys1;
@@ -83,7 +83,7 @@ public class Hash {
         usedslots = 0;
         for(int i=0; i<oldvals.length; i++)
             if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
-                put(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
+                put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
     }
 
     public Object get(Object k1) { return get(k1, null); }
@@ -109,7 +109,8 @@ public class Hash {
     }
 
     public void put(Object k1, Object v) { put(k1, null, v); }
-    public void put(Object k1, Object k2, Object v) {
+    public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
+    private void put_(Object k1, Object k2, Object v) {
         if (usedslots * loadFactor > vals.length) rehash();
         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
         int dest = Math.abs(hash) % vals.length;
@@ -149,6 +150,27 @@ public class Hash {
         vals[dest] = v;
     }
 
+    private class HashEnum implements java.util.Enumeration {
+        private int iterator = 0;
+        private int found = 0;
+        
+        public HashEnum () { }
+        
+        public boolean hasMoreElements() {
+            return found < usedslots;
+        }
+
+        public Object nextElement() {
+            if (!hasMoreElements()) throw new java.util.NoSuchElementException();
+
+            Object o = null;
+            while (o == null) o = keys1[iterator++];
+            if (o == null) throw new IllegalStateException("Didn't find an element, when I should have.");
+            found++;
+            
+            return o;
+        }
+    }
 }