A patch with hashtable optimization, which doesn't work

[Sebastian Gniazdowski <psprint@zdharma.org>]

[-- Attachment #1: Type: text/plain, Size: 1217 bytes --]

Hello,
it is really simple to keep collision lists sorted. However, I get error about typeset not being found. Debugged that typeset is inserted into builtintab. I am pretty exhausted, maybe someone will have a revelation on this. Debugged that typeset is being searched in:

exec.c:729 if ((cn = (Cmdnam) cmdnamtab->getnode(cmdnamtab, arg0))) {

at final stage, so it apparently misses builtintab search before. Below is the main idea, attached is full patch.

-       if (ht->cmpnodes(hp->nam, hn->nam) == 0) {
+        cres = ht->cmpnodes(hp->nam, hn->nam);
+       if ( cres == 0 ) {
            hq->next = hn;
            goto replacing;
-       }
+       } else if ( cres > 0 ) {
+            /* Pointer `hp` is at 'right' position - it points
+             * to a greater element than `hn`, so we should
+             * insert at one-before, that is after `hq` */
+            hq->next = hn;
+            hn->next = hp;
+            if (++ht->ct >= ht->hsize * 2 && !ht->scan)
+                expandhashtable(ht);
+            return NULL;
+        }

--
Sebastian Gniazdowski
psprint /at/ zdharma.org

[-- Attachment #2: hashopt.diff.txt --]
[-- Type: text/plain, Size: 3148 bytes --]

diff --git a/Src/hashtable.c b/Src/hashtable.c
index ba5faad..d820efd 100644
--- a/Src/hashtable.c
+++ b/Src/hashtable.c
@@ -162,6 +162,7 @@ addhashnode(HashTable ht, char *nam, void *nodeptr)
 HashNode
 addhashnode2(HashTable ht, char *nam, void *nodeptr)
 {
+    int cres;
     unsigned hashval;
     HashNode hn, hp, hq;
 
@@ -181,7 +182,8 @@ addhashnode2(HashTable ht, char *nam, void *nodeptr)
     }
 
     /* else check if the first node contains the same key */
-    if (ht->cmpnodes(hp->nam, hn->nam) == 0) {
+    cres = ht->cmpnodes(hp->nam, hn->nam);
+    if ( cres == 0 ) {
 	ht->nodes[hashval] = hn;
 	replacing:
 	hn->next = hp->next;
@@ -196,21 +198,39 @@ addhashnode2(HashTable ht, char *nam, void *nodeptr)
 		ht->scan->u.u = hn;
 	}
 	return hp;
+    } else if ( cres > 0 ) {
+        /* Insert in front of the list, because first
+         * element, nodes[hashval], is larger, so new
+         * element has to be before it */
+        hn->next = hp;
+        ht->nodes[hashval] = hn;
+	if (++ht->ct >= ht->hsize * 2 && !ht->scan)
+	    expandhashtable(ht);
     }
 
     /* else run through the list and check all the keys */
     hq = hp;
     hp = hp->next;
     for (; hp; hq = hp, hp = hp->next) {
-	if (ht->cmpnodes(hp->nam, hn->nam) == 0) {
+        cres = ht->cmpnodes(hp->nam, hn->nam);
+	if ( cres == 0 ) {
 	    hq->next = hn;
 	    goto replacing;
-	}
+	} else if ( cres > 0 ) {
+            /* Pointer `hp` is at 'right' position - it points
+             * to a greater element than `hn`, so we should
+             * insert at one-before, that is after `hq` */
+            hq->next = hn;
+            hn->next = hp;
+            if (++ht->ct >= ht->hsize * 2 && !ht->scan)
+                expandhashtable(ht);
+            return NULL;
+        }
     }
 
-    /* else just add it at the front of the list */
-    hn->next = ht->nodes[hashval];
-    ht->nodes[hashval] = hn;
+    /* else just add it at the end of the list */
+    hq->next = hn;
+    hn->next = NULL;
     if (++ht->ct >= ht->hsize * 2 && !ht->scan)
         expandhashtable(ht);
     return NULL;
@@ -225,17 +245,20 @@ addhashnode2(HashTable ht, char *nam, void *nodeptr)
 mod_export HashNode
 gethashnode(HashTable ht, const char *nam)
 {
+    int cres;
     unsigned hashval;
     HashNode hp;
 
     hashval = ht->hash(nam) % ht->hsize;
     for (hp = ht->nodes[hashval]; hp; hp = hp->next) {
-	if (ht->cmpnodes(hp->nam, nam) == 0) {
+        cres = ht->cmpnodes(hp->nam, nam);
+	if (cres == 0) {
 	    if (hp->flags & DISABLED)
 		return NULL;
 	    else
 		return hp;
-	}
+	} else if (cres > 0)
+            return NULL;
     }
     return NULL;
 }
@@ -249,13 +272,17 @@ gethashnode(HashTable ht, const char *nam)
 mod_export HashNode
 gethashnode2(HashTable ht, const char *nam)
 {
+    int cres;
     unsigned hashval;
     HashNode hp;
 
     hashval = ht->hash(nam) % ht->hsize;
     for (hp = ht->nodes[hashval]; hp; hp = hp->next) {
-	if (ht->cmpnodes(hp->nam, nam) == 0)
+        cres = ht->cmpnodes(hp->nam, nam);
+	if (cres == 0)
 	    return hp;
+        else if (cres > 0)
+            return NULL;
     }
     return NULL;
 }