Re: GSOC | Extending Common Lisp support

[Per Bothner <per at bothner dot com>]

On 06/26/2012 02:47 PM, Per Bothner wrote:
> Perhaps we should re-implement Namespace so it extends
> AbstractHashTable<SymbolRef, String, Symbol>.
> In that case SymbolRef would have to extend  Map.Entry<String,Symbol>.

Attached is a patch to do this.  What do you think?
(Note this assumes an earlier patch that I checked in a few hours ago.)
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/


Index: gnu/kawa/util/AbstractHashTable.java
===================================================================
--- gnu/kawa/util/AbstractHashTable.java	(revision 7259)
+++ gnu/kawa/util/AbstractHashTable.java	(working copy)
@@ -85,7 +85,11 @@
   /** Find Entry for given key.  Return null if not found. */
   public Entry getNode (Object key)
   {
-    int hash = hash(key);
+    return getNode(key, hash(key)); 
+  }
+
+  public Entry getNode (Object key, int hash)
+  {
     int index = hashToIndex(hash);
     for (Entry node = table[index];
 	 node != null;  node = getEntryNext(node))
Index: gnu/mapping/Namespace.java
===================================================================
--- gnu/mapping/Namespace.java	(revision 7259)
+++ gnu/mapping/Namespace.java	(working copy)
@@ -18,7 +18,7 @@
  */
 
 public class Namespace
-//extends AbstractHashTable<SymbolRef, String, Symbol>
+  extends AbstractHashTable<SymbolRef, String, Symbol>
   implements Externalizable, HasNamedParts
 {
   /** Map namepsace names (and nick-names) to Namespaces. */
@@ -46,12 +46,7 @@
 
   protected Namespace (int capacity)
   {
-    log2Size = 4;
-    while (capacity > (1 << log2Size))
-      log2Size++;
-    capacity = 1 << log2Size;
-    table = new SymbolRef[capacity];
-    mask = capacity - 1;
+    super(capacity);
   }
 
   public static Namespace create (int capacity)
@@ -173,42 +168,13 @@
 
   protected final Symbol lookupInternal(String key, int hash)
   {
-    int index = hash & mask;
-    SymbolRef prev = null;
-    for (SymbolRef ref = table[index];  ref != null;  )
-      {
-	SymbolRef next = ref.next;
-	Symbol sym = ref.getSymbol();
-	if (sym == null)
-	  {
-	    // Weakly referenced object has been collected.
-	    if (prev == null)
-	      table[index] = next;
-	    else
-	      prev.next = next;
-	    num_bindings--;
-	  }
-	else
-	  {
-	    if (sym.getLocalPart().equals(key))
-	      return sym;
-	    prev = ref;
-	  }
-	ref = next;
-      }
-    return null;
+    SymbolRef node = getNode(key, hash);
+    return node == null ? null : node.getValue();
   }
 
   public Symbol add(Symbol sym, int hash)
   {
-    int index = hash & mask;
-    SymbolRef ref = new SymbolRef(sym, this);
-    sym.namespace = this;
-    ref.next = table[index];
-    table[index] = ref;
-    num_bindings++;
-    if (num_bindings >= table.length)
-      rehash();
+    put(sym.getName(), hash, sym);
     return sym;
   }
 
@@ -248,71 +214,22 @@
     synchronized (this)
       {
 	String name = symbol.getLocalPart();
-	int hash = name.hashCode();
-	int index = hash & mask;
-	SymbolRef prev = null;
-	SymbolRef ref = table[index];
-	while (ref != null)
-	  {
-	    SymbolRef next = ref.next;
-	    Symbol refsym = ref.getSymbol();
-	    if (refsym == null || refsym == symbol)
-	      {
-		if (prev == null)
-		  table[index] = next;
-		else
-		  prev.next = next;
-		num_bindings--;
-		if (refsym != null)
-		  return true;
-	      }
-	    else
-	      prev = ref;
-	    ref = next;
-	  }
-	return false;
+        return remove(name) != null;
       }
   }
 
-  protected SymbolRef[] table;
-  int log2Size;
-  private int mask;
-  int num_bindings;
+    protected int getEntryHashCode (SymbolRef entry) { return entry.hashCode(); }
+    /** Extract next Entry in same hash-bucket. */
+    protected SymbolRef getEntryNext (SymbolRef entry) { return entry.next; }
+    /** Set next Entry in same hash-bucket. */
+    protected void setEntryNext (SymbolRef entry, SymbolRef next) { entry.next = next; }
+    /** Allocate Entry[n]. */
+    protected SymbolRef[] allocEntries(int n) { return new SymbolRef[n]; }
 
-  protected void rehash ()
-  {
-    int oldCapacity = table.length;
-    int newCapacity = 2 * oldCapacity;
-    int newMask = newCapacity - 1;
-    int countInserted = 0;
-    SymbolRef[] oldTable = table;
-    SymbolRef[] newTable = new SymbolRef[newCapacity];
+    protected SymbolRef makeEntry (String key, int hash, Symbol value) {
+        return new SymbolRef(value);
+    }
 
-    for (int i = oldCapacity;  --i >= 0;)
-      {
-	for (SymbolRef ref = oldTable[i];  ref != null;  )
-	  {
-	    SymbolRef next = ref.next;
-	    Symbol sym = ref.getSymbol();
-	    if (sym != null)
-	      {
-		String key = sym.getName();
-		int hash = key.hashCode();
-		int index = hash & newMask;
-		countInserted++;
-		ref.next = newTable[index];
-		newTable[index] = ref;
-	      }
-	    ref = next;
-	  }
-      }
-
-    table = newTable;
-    log2Size++;
-    mask = newMask;
-    num_bindings = countInserted;
-  }
-
   public void writeExternal(ObjectOutput out) throws IOException
   {
     out.writeObject(getName());
@@ -372,7 +289,7 @@
         return sym == null ? null : sym.getName();
     }
 
-    SymbolRef (Symbol sym, Namespace ns) {
+    SymbolRef (Symbol sym) {
         super(sym);
     }