about summary refs log tree commit diff
path: root/Src/hashtable.c
diff options
context:
space:
mode:
Diffstat (limited to 'Src/hashtable.c')
-rw-r--r--Src/hashtable.c506
1 files changed, 367 insertions, 139 deletions
diff --git a/Src/hashtable.c b/Src/hashtable.c
index 4adf3904d..7a881e9f8 100644
--- a/Src/hashtable.c
+++ b/Src/hashtable.c
@@ -77,13 +77,13 @@ static HashTable firstht, lastht;
 /* Generic hash function */
 
 /**/
-unsigned
+mod_export unsigned
 hasher(char *str)
 {
-    unsigned hashval = 0;
+    unsigned hashval = 0, c;
 
-    while (*str)
-	hashval += (hashval << 5) + ((unsigned) *str++);
+    while ((c = *((unsigned char *) str++)))
+	hashval += (hashval << 5) + c;
 
     return hashval;
 }
@@ -91,7 +91,7 @@ hasher(char *str)
 /* Get a new hash table */
 
 /**/
-HashTable
+mod_export HashTable
 newhashtable(int size, char const *name, PrintTableStats printinfo)
 {
     HashTable ht;
@@ -112,6 +112,7 @@ newhashtable(int size, char const *name, PrintTableStats printinfo)
     ht->hsize = size;
     ht->ct = 0;
     ht->scan = NULL;
+    ht->scantab = NULL;
     return ht;
 }
 
@@ -119,7 +120,7 @@ newhashtable(int size, char const *name, PrintTableStats printinfo)
  * existing pointers to the hash table are invalid.             */
 
 /**/
-void
+mod_export void
 deletehashtable(HashTable ht)
 {
     ht->emptytable(ht);
@@ -132,13 +133,14 @@ deletehashtable(HashTable ht)
 	ht->last->next = ht->next;
     else
 	firstht = ht->next;
+    zsfree(ht->tablename);
 #endif /* ZSH_HASH_DEBUG */
     zfree(ht->nodes, ht->hsize * sizeof(HashNode));
     zfree(ht, sizeof(*ht));
 }
 
 /* Add a node to a hash table.                          *
- * nam is the key to use in hashing.  dat is a pointer  *
+ * nam is the key to use in hashing.  nodeptr points    *
  * to the node to add.  If there is already a node in   *
  * the table with the same key, it is first freed, and  *
  * then the new node is added.  If the number of nodes  *
@@ -146,9 +148,20 @@ deletehashtable(HashTable ht)
  * the table is then expanded.                          */
 
 /**/
-void
+mod_export void
 addhashnode(HashTable ht, char *nam, void *nodeptr)
 {
+    HashNode oldnode = addhashnode2(ht, nam, nodeptr);
+    if (oldnode)
+	ht->freenode(oldnode);
+}
+
+/* Add a node to a hash table, returning the old node on replacment. */
+
+/**/
+HashNode
+addhashnode2(HashTable ht, char *nam, void *nodeptr)
+{
     unsigned hashval;
     HashNode hn, hp, hq;
 
@@ -164,15 +177,15 @@ addhashnode(HashTable ht, char *nam, void *nodeptr)
 	ht->nodes[hashval] = hn;
 	if (++ht->ct >= ht->hsize * 2 && !ht->scan)
 	    expandhashtable(ht);
-	return;
+	return NULL;
     }
 
     /* else check if the first node contains the same key */
-    if (!strcmp(hp->nam, hn->nam)) {
+    if (ht->cmpnodes(hp->nam, hn->nam) == 0) {
 	ht->nodes[hashval] = hn;
 	replacing:
 	hn->next = hp->next;
-	if(ht->scan)
+	if(ht->scan) {
 	    if(ht->scan->sorted) {
 		HashNode *tab = ht->scan->u.s.tab;
 		int i;
@@ -181,15 +194,15 @@ addhashnode(HashTable ht, char *nam, void *nodeptr)
 			tab[i] = hn;
 	    } else if(ht->scan->u.u == hp)
 		ht->scan->u.u = hn;
-	ht->freenode(hp);
-	return;
+	}
+	return hp;
     }
 
     /* else run through the list and check all the keys */
     hq = hp;
     hp = hp->next;
     for (; hp; hq = hp, hp = hp->next) {
-	if (!strcmp(hp->nam, hn->nam)) {
+	if (ht->cmpnodes(hp->nam, hn->nam) == 0) {
 	    hq->next = hn;
 	    goto replacing;
 	}
@@ -200,6 +213,7 @@ addhashnode(HashTable ht, char *nam, void *nodeptr)
     ht->nodes[hashval] = hn;
     if (++ht->ct >= ht->hsize * 2 && !ht->scan)
         expandhashtable(ht);
+    return NULL;
 }
 
 /* Get an enabled entry in a hash table.  *
@@ -208,7 +222,7 @@ addhashnode(HashTable ht, char *nam, void *nodeptr)
  * or isn't found, it returns NULL        */
 
 /**/
-HashNode
+mod_export HashNode
 gethashnode(HashTable ht, char *nam)
 {
     unsigned hashval;
@@ -216,7 +230,7 @@ gethashnode(HashTable ht, char *nam)
 
     hashval = ht->hash(nam) % ht->hsize;
     for (hp = ht->nodes[hashval]; hp; hp = hp->next) {
-	if (!strcmp(hp->nam, nam)) {
+	if (ht->cmpnodes(hp->nam, nam) == 0) {
 	    if (hp->flags & DISABLED)
 		return NULL;
 	    else
@@ -232,7 +246,7 @@ gethashnode(HashTable ht, char *nam)
  * it returns NULL.                       */
 
 /**/
-HashNode
+mod_export HashNode
 gethashnode2(HashTable ht, char *nam)
 {
     unsigned hashval;
@@ -240,7 +254,7 @@ gethashnode2(HashTable ht, char *nam)
 
     hashval = ht->hash(nam) % ht->hsize;
     for (hp = ht->nodes[hashval]; hp; hp = hp->next) {
-	if (!strcmp(hp->nam, nam))
+	if (ht->cmpnodes(hp->nam, nam) == 0)
 	    return hp;
     }
     return NULL;
@@ -252,7 +266,7 @@ gethashnode2(HashTable ht, char *nam)
  * is no such node, then it returns NULL        */
 
 /**/
-HashNode
+mod_export HashNode
 removehashnode(HashTable ht, char *nam)
 {
     unsigned hashval;
@@ -266,11 +280,11 @@ removehashnode(HashTable ht, char *nam)
 	return NULL;
 
     /* else check if the key in the first one matches */
-    if (!strcmp(hp->nam, nam)) {
+    if (ht->cmpnodes(hp->nam, nam) == 0) {
 	ht->nodes[hashval] = hp->next;
 	gotit:
 	ht->ct--;
-	if(ht->scan)
+	if(ht->scan) {
 	    if(ht->scan->sorted) {
 		HashNode *tab = ht->scan->u.s.tab;
 		int i;
@@ -279,6 +293,7 @@ removehashnode(HashTable ht, char *nam)
 			tab[i] = NULL;
 	    } else if(ht->scan->u.u == hp)
 		ht->scan->u.u = hp->next;
+	}
 	return hp;
     }
 
@@ -286,7 +301,7 @@ removehashnode(HashTable ht, char *nam)
     hq = hp;
     hp = hp->next;
     for (; hp; hq = hp, hp = hp->next) {
-	if (!strcmp(hp->nam, nam)) {
+	if (ht->cmpnodes(hp->nam, nam) == 0) {
 	    hq->next = hp->next;
 	    goto gotit;
 	}
@@ -314,7 +329,7 @@ enablehashnode(HashNode hn, int flags)
     hn->flags &= ~DISABLED;
 }
 
-/* Compare two hash table entries */
+/* Compare two hash table entries by name */
 
 /**/
 static int
@@ -343,11 +358,15 @@ hnamcmp(const void *ap, const void *bp)
  */
 
 /**/
-void
+mod_export void
 scanhashtable(HashTable ht, int sorted, int flags1, int flags2, ScanFunc scanfunc, int scanflags)
 {
     struct scanstatus st;
 
+    if (ht->scantab) {
+	ht->scantab(ht, scanfunc, scanflags);
+	return;
+    }
     if (sorted) {
 	int i, ct = ht->ct;
 	VARARR(HashNode, hnsorttab, ct);
@@ -399,7 +418,7 @@ scanhashtable(HashTable ht, int sorted, int flags1, int flags2, ScanFunc scanfun
 
 /**/
 int
-scanmatchtable(HashTable ht, Comp com, int flags1, int flags2, ScanFunc scanfunc, int scanflags)
+scanmatchtable(HashTable ht, Patprog pprog, int flags1, int flags2, ScanFunc scanfunc, int scanflags)
 {
     int i, hsize = ht->hsize;
     HashNode *nodes = ht->nodes;
@@ -414,9 +433,10 @@ scanmatchtable(HashTable ht, Comp com, int flags1, int flags2, ScanFunc scanfunc
 	    HashNode hn = st.u.u;
 	    st.u.u = st.u.u->next;
 	    if ((hn->flags & flags1) + !flags1 && !(hn->flags & flags2) &&
-		domatch(hn->nam, com, 0))
+		pattry(pprog, hn->nam)) {
 		scanfunc(hn, scanflags);
 		match++;
+	    }
 	}
 
     ht->scan = NULL;
@@ -489,12 +509,13 @@ resizehashtable(HashTable ht, int newsize)
 /* Generic method to empty a hash table */
 
 /**/
-void
+mod_export void
 emptyhashtable(HashTable ht)
 {
     resizehashtable(ht, ht->hsize);
 }
 
+/**/
 #ifdef ZSH_HASH_DEBUG
 
 /* Print info about hash table */
@@ -547,6 +568,7 @@ bin_hashinfo(char *nam, char **args, char *ops, int func)
     return 0;
 }
 
+/**/
 #endif /* ZSH_HASH_DEBUG */
 
 /********************************/
@@ -556,12 +578,12 @@ bin_hashinfo(char *nam, char **args, char *ops, int func)
 /* hash table containing external commands */
  
 /**/
-HashTable cmdnamtab;
+mod_export HashTable cmdnamtab;
  
 /* how far we've hashed the PATH so far */
  
 /**/
-char **pathchecked;
+mod_export char **pathchecked;
  
 /* Create a new command hash table */
  
@@ -574,6 +596,7 @@ createcmdnamtable(void)
     cmdnamtab->hash        = hasher;
     cmdnamtab->emptytable  = emptycmdnamtable;
     cmdnamtab->filltable   = fillcmdnamtable;
+    cmdnamtab->cmpnodes    = strcmp;
     cmdnamtab->addnode     = addhashnode;
     cmdnamtab->getnode     = gethashnode2;
     cmdnamtab->getnode2    = gethashnode2;
@@ -604,6 +627,9 @@ hashdir(char **dirp)
     Cmdnam cn;
     DIR *dir;
     char *fn;
+#ifdef _WIN32
+    char *exe;
+#endif
 
     if (isrelative(*dirp) || !(dir = opendir(unmeta(*dirp))))
 	return;
@@ -615,6 +641,23 @@ hashdir(char **dirp)
 	    cn->u.name = dirp;
 	    cmdnamtab->addnode(cmdnamtab, ztrdup(fn), cn);
 	}
+#ifdef _WIN32
+	/* Hash foo.exe as foo, since when no real foo exists, foo.exe
+	   will get executed by DOS automatically.  This quiets
+	   spurious corrections when CORRECT or CORRECT_ALL is set. */
+	if ((exe = strrchr(fn, '.')) &&
+	    (exe[1] == 'E' || exe[1] == 'e') &&
+	    (exe[2] == 'X' || exe[2] == 'x') &&
+	    (exe[3] == 'E' || exe[3] == 'e') && exe[4] == 0) {
+	    *exe = 0;
+	    if (!cmdnamtab->getnode(cmdnamtab, fn)) {
+		cn = (Cmdnam) zcalloc(sizeof *cn);
+		cn->flags = 0;
+		cn->u.name = dirp;
+		cmdnamtab->addnode(cmdnamtab, ztrdup(fn), cn);
+	    }
+	}
+#endif /* _WIN32 */
     }
     closedir(dir);
 }
@@ -713,7 +756,7 @@ printcmdnamnode(HashNode hn, int printflags)
 /* hash table containing the shell functions */
 
 /**/
-HashTable shfunctab;
+mod_export HashTable shfunctab;
 
 /**/
 void
@@ -724,6 +767,7 @@ createshfunctable(void)
     shfunctab->hash        = hasher;
     shfunctab->emptytable  = NULL;
     shfunctab->filltable   = NULL;
+    shfunctab->cmpnodes    = strcmp;
     shfunctab->addnode     = addhashnode;
     shfunctab->getnode     = gethashnode;
     shfunctab->getnode2    = gethashnode2;
@@ -798,7 +842,7 @@ freeshfuncnode(HashNode hn)
 
     zsfree(shf->nam);
     if (shf->funcdef)
-	freestruct(shf->funcdef);
+	freeeprog(shf->funcdef);
     zfree(shf, sizeof(struct shfunc));
 }
 
@@ -828,21 +872,34 @@ printshfuncnode(HashNode hn, int printflags)
     }
  
     if (f->flags & PM_UNDEFINED)
-	printf("undefined ");
-    if (f->flags & PM_TAGGED)
-	printf("traced ");
-    if ((f->flags & PM_UNDEFINED) || !f->funcdef) {
-	nicezputs(f->nam, stdout);
-	printf(" () { }\n");
-	return;
+	t = tricat("builtin autoload -X",
+		   ((f->flags & PM_UNALIASED)? "U" : ""),
+		   ((f->flags & PM_TAGGED)? "t" : ""));
+    else {
+	if (!f->funcdef)
+	    t = 0;
+	else
+	    t = getpermtext(f->funcdef, NULL);
     }
- 
-    t = getpermtext((void *) dupstruct((void *) f->funcdef));
+
     quotedzputs(f->nam, stdout);
-    printf(" () {\n\t");
-    zputs(t, stdout);
-    printf("\n}\n");
-    zsfree(t);
+    if (t) {
+	printf(" () {\n\t");
+	if (f->flags & PM_UNDEFINED)
+	    printf("%c undefined\n\t", hashchar);
+	if (f->flags & PM_TAGGED)
+	    printf("%c traced\n\t", hashchar);
+	zputs(t, stdout);
+	if (f->funcdef && (f->funcdef->flags & EF_RUN)) {
+	    printf("\n\t");
+	    quotedzputs(f->nam, stdout);
+	    printf(" \"$@\"");
+	}
+	printf("\n}\n");
+	zsfree(t);
+    } else {
+	printf(" () { }\n");
+    }
 }
 
 /**************************************/
@@ -882,7 +939,7 @@ static struct reswd reswds[] = {
 /* hash table containing the reserved words */
 
 /**/
-HashTable reswdtab;
+mod_export HashTable reswdtab;
 
 /* Build the hash table containing zsh's reserved words. */
 
@@ -897,6 +954,7 @@ createreswdtable(void)
     reswdtab->hash        = hasher;
     reswdtab->emptytable  = NULL;
     reswdtab->filltable   = NULL;
+    reswdtab->cmpnodes    = strcmp;
     reswdtab->addnode     = addhashnode;
     reswdtab->getnode     = gethashnode;
     reswdtab->getnode2    = gethashnode2;
@@ -944,7 +1002,7 @@ printreswdnode(HashNode hn, int printflags)
 /* hash table containing the aliases */
  
 /**/
-HashTable aliastab;
+mod_export HashTable aliastab;
  
 /* Create new hash table for aliases */
 
@@ -957,6 +1015,7 @@ createaliastable(void)
     aliastab->hash        = hasher;
     aliastab->emptytable  = NULL;
     aliastab->filltable   = NULL;
+    aliastab->cmpnodes    = strcmp;
     aliastab->addnode     = addhashnode;
     aliastab->getnode     = gethashnode;
     aliastab->getnode2    = gethashnode2;
@@ -974,7 +1033,7 @@ createaliastable(void)
 /* Create a new alias node */
 
 /**/
-Alias
+mod_export Alias
 createaliasnode(char *txt, int flags)
 {
     Alias al;
@@ -1061,101 +1120,25 @@ printaliasnode(HashNode hn, int printflags)
     putchar('\n');
 }
 
-/**********************************/
-/* Parameter Hash Table Functions */
-/**********************************/
-
-/**/
-void
-freeparamnode(HashNode hn)
-{
-    Param pm = (Param) hn;
- 
-    zsfree(pm->nam);
-    zfree(pm, sizeof(struct param));
-}
-
-/* Print a parameter */
-
-/**/
-void
-printparamnode(HashNode hn, int printflags)
-{
-    Param p = (Param) hn;
-    char *t, **u;
-
-    if (p->flags & PM_UNSET)
-	return;
-
-    /* Print the attributes of the parameter */
-    if (printflags & PRINT_TYPE) {
-	if (p->flags & PM_INTEGER)
-	    printf("integer ");
-	if (p->flags & PM_ARRAY)
-	    printf("array ");
-	if (p->flags & PM_LEFT)
-	    printf("left justified %d ", p->ct);
-	if (p->flags & PM_RIGHT_B)
-	    printf("right justified %d ", p->ct);
-	if (p->flags & PM_RIGHT_Z)
-	    printf("zero filled %d ", p->ct);
-	if (p->flags & PM_LOWER)
-	    printf("lowercase ");
-	if (p->flags & PM_UPPER)
-	    printf("uppercase ");
-	if (p->flags & PM_READONLY)
-	    printf("readonly ");
-	if (p->flags & PM_TAGGED)
-	    printf("tagged ");
-	if (p->flags & PM_EXPORTED)
-	    printf("exported ");
-    }
-
-    if (printflags & PRINT_NAMEONLY) {
-	zputs(p->nam, stdout);
-	putchar('\n');
-	return;
-    }
-
-    /* How the value is displayed depends *
-     * on the type of the parameter       */
-    quotedzputs(p->nam, stdout);
-    putchar('=');
-    switch (PM_TYPE(p->flags)) {
-    case PM_SCALAR:
-	/* string: simple output */
-	if (p->gets.cfn && (t = p->gets.cfn(p)))
-	    quotedzputs(t, stdout);
-	putchar('\n');
-	break;
-    case PM_INTEGER:
-	/* integer */
-	printf("%ld\n", p->gets.ifn(p));
-	break;
-    case PM_ARRAY:
-	/* array */
-	putchar('(');
-	u = p->gets.afn(p);
-	if(*u) {
-	    quotedzputs(*u++, stdout);
-	    while (*u) {
-		putchar(' ');
-		quotedzputs(*u++, stdout);
-	    }
-	}
-	printf(")\n");
-	break;
-    }
-}
-
 /****************************************/
 /* Named Directory Hash Table Functions */
 /****************************************/
 
+#ifdef HAVE_NIS_PLUS
+# include <rpcsvc/nis.h>
+#else
+# ifdef HAVE_NIS
+#  include	<rpc/types.h>
+#  include	<rpc/rpc.h>
+#  include	<rpcsvc/ypclnt.h>
+#  include	<rpcsvc/yp_prot.h>
+# endif
+#endif
+
 /* hash table containing named directories */
 
 /**/
-HashTable nameddirtab;
+mod_export HashTable nameddirtab;
  
 /* != 0 if all the usernames have already been *
  * added to the named directory hash table.    */
@@ -1173,6 +1156,7 @@ createnameddirtable(void)
     nameddirtab->hash        = hasher;
     nameddirtab->emptytable  = emptynameddirtable;
     nameddirtab->filltable   = fillnameddirtable;
+    nameddirtab->cmpnodes    = strcmp;
     nameddirtab->addnode     = addnameddirnode;
     nameddirtab->getnode     = gethashnode;
     nameddirtab->getnode2    = gethashnode2;
@@ -1200,12 +1184,122 @@ emptynameddirtable(HashTable ht)
 /* Add all the usernames in the password file/database *
  * to the named directories table.                     */
 
+#ifdef HAVE_NIS_PLUS
+static int
+add_userdir(nis_name table, nis_object *object, void *userdata)
+{
+    if (object->zo_data.objdata_u.en_data.en_cols.en_cols >= 6) {
+	static char name[40], dir[PATH_MAX + 1];
+	register entry_col *ec =
+	    object->zo_data.objdata_u.en_data.en_cols.en_cols_val;
+	register int nl = minimum(ec[0].ec_value.ec_value_len, 39);
+	register int dl = minimum(ec[5].ec_value.ec_value_len, PATH_MAX);
+
+	memcpy(name, ec[0].ec_value.ec_value_val, nl);
+	name[nl] = '\0';
+	memcpy(dir, ec[5].ec_value.ec_value_val, dl);
+	dir[dl] = '\0';
+
+	adduserdir(name, dir, ND_USERNAME, 1);
+    }
+    return 0;
+}
+#else
+# ifdef HAVE_NIS
+static int
+add_userdir(int status, char *key, int keylen, char *val, int vallen, char *dummy)
+{
+    char *p, *d, *de;
+
+    if (status != YP_TRUE)
+	return 1;
+
+    if (vallen > keylen && *(p = val + keylen) == ':') {
+	*p++ = '\0';
+	if ((de = strrchr(p, ':'))) {
+	    *de = '\0';
+	    if ((d = strrchr(p, ':'))) {
+		if (*++d && val[0])
+		    adduserdir(val, d, ND_USERNAME, 1);
+	    }
+	}
+    }
+    return 0;
+}
+# endif /* HAVE_NIS */
+#endif  /* HAVE_NIS_PLUS */
+
 /**/
 static void
 fillnameddirtable(HashTable ht)
 {
-#ifdef HAVE_GETPWENT
     if (!allusersadded) {
+#if defined(HAVE_NIS) || defined(HAVE_NIS_PLUS)
+	FILE *pwf;
+	char buf[BUFSIZ], *p, *d, *de;
+	int skipping, oldct = nameddirtab->ct, usepwf = 1;
+
+# ifndef HAVE_NIS_PLUS
+	char domain[YPMAXDOMAIN];
+	struct ypall_callback cb;
+
+	/* Get potential matches from NIS and cull those without local accounts */
+	if (getdomainname(domain, YPMAXDOMAIN) == 0) {
+	    cb.foreach = (int (*)()) add_userdir;
+	    cb.data = NULL;
+	    yp_all(domain, PASSWD_MAP, &cb);
+    }
+# else  /* HAVE_NIS_PLUS */
+	/* Maybe we should turn this string into a #define'd constant...? */
+
+	nis_list("passwd.org_dir", EXPAND_NAME|ALL_RESULTS|FOLLOW_LINKS|FOLLOW_PATH,
+		 add_userdir, 0);
+# endif
+	if (nameddirtab->ct == oldct) {
+	    /* Using NIS or NIS+ didn't add any user directories. This seems
+	     * fishy, so we fall back to using getpwent(). If we don't have
+	     * that, we only use the passwd file. */
+#ifdef HAVE_GETPWENT
+	    struct passwd *pw;
+ 
+	    setpwent();
+ 
+	    /* loop through the password file/database *
+	     * and add all entries returned.           */
+	    while ((pw = getpwent()) && !errflag)
+		adduserdir(pw->pw_name, pw->pw_dir, ND_USERNAME, 1);
+ 
+	    endpwent();
+	    usepwf = 0;
+#endif /* HAVE_GETPWENT */
+	}
+	if (usepwf) {
+	    /* Don't forget the non-NIS matches from the flat passwd file */
+	    if ((pwf = fopen(PASSWD_FILE, "r")) != NULL) {
+		skipping = 0;
+		while (fgets(buf, BUFSIZ, pwf) != NULL) {
+		    if (strchr(buf, '\n') != NULL) {
+			if (!skipping) {
+			    if ((p = strchr(buf, ':')) != NULL) {
+				*p++ = '\0';
+				if ((de = strrchr(p, ':'))) {
+				    *de = '\0';
+				    if ((d = strrchr(p, ':'))) {
+					if (*++d && buf[0])
+					    adduserdir(buf, d, ND_USERNAME, 1);
+				    }
+				}
+			    }
+			} else
+			    skipping = 0;
+		    } else
+			skipping = 1;
+		}
+		fclose(pwf);
+	    }
+	}
+#else  /* no NIS or NIS_PLUS */
+#ifdef HAVE_GETPWENT
 	struct passwd *pw;
  
 	setpwent();
@@ -1213,13 +1307,13 @@ fillnameddirtable(HashTable ht)
 	/* loop through the password file/database *
 	 * and add all entries returned.           */
 	while ((pw = getpwent()) && !errflag)
-	    adduserdir(ztrdup(pw->pw_name), pw->pw_dir, ND_USERNAME, 1);
+	    adduserdir(pw->pw_name, pw->pw_dir, ND_USERNAME, 1);
  
 	endpwent();
+#endif /* HAVE_GETPWENT */
+#endif
 	allusersadded = 1;
     }
-    return;
-#endif /* HAVE_GETPWENT */
 }
 
 /* Add an entry to the named directory hash *
@@ -1283,3 +1377,137 @@ printnameddirnode(HashNode hn, int printflags)
     quotedzputs(nd->dir, stdout);
     putchar('\n');
 }
+
+/*************************************/
+/* History Line Hash Table Functions */
+/*************************************/
+
+/**/
+void
+createhisttable(void)
+{
+    histtab = newhashtable(599, "histtab", NULL);
+
+    histtab->hash        = histhasher;
+    histtab->emptytable  = emptyhisttable;
+    histtab->filltable   = NULL;
+    histtab->cmpnodes    = histstrcmp;
+    histtab->addnode     = addhistnode;
+    histtab->getnode     = gethashnode2;
+    histtab->getnode2    = gethashnode2;
+    histtab->removenode  = removehashnode;
+    histtab->disablenode = NULL;
+    histtab->enablenode  = NULL;
+    histtab->freenode    = freehistnode;
+    histtab->printnode   = NULL;
+}
+
+/**/
+unsigned
+histhasher(char *str)
+{
+    unsigned hashval = 0;
+
+    while (inblank(*str)) str++;
+
+    while (*str) {
+	if (inblank(*str)) {
+	    do str++; while (inblank(*str));
+	    if (*str)
+		hashval += (hashval << 5) + ' ';
+	}
+	else
+	    hashval += (hashval << 5) + *(unsigned char *)str++;
+    }
+    return hashval;
+}
+
+/**/
+void
+emptyhisttable(HashTable ht)
+{
+    emptyhashtable(ht);
+    if (hist_ring)
+	histremovedups();
+}
+
+/* Compare two strings with normalized white-space */
+
+/**/
+int
+histstrcmp(const char *str1, const char *str2)
+{
+    while (inblank(*str1)) str1++;
+    while (inblank(*str2)) str2++;
+    while (*str1 && *str2) {
+	if (inblank(*str1)) {
+	    if (!inblank(*str2))
+		break;
+	    do str1++; while (inblank(*str1));
+	    do str2++; while (inblank(*str2));
+	}
+	else {
+	    if (*str1 != *str2)
+		break;
+	    str1++;
+	    str2++;
+	}
+    }
+    return *str1 - *str2;
+}
+
+/**/
+void
+addhistnode(HashTable ht, char *nam, void *nodeptr)
+{
+    HashNode oldnode = addhashnode2(ht, nam, nodeptr);
+    Histent he = (Histent)nodeptr;
+    if (oldnode && oldnode != (HashNode)nodeptr) {
+	if (he->flags & HIST_MAKEUNIQUE
+	 || (he->flags & HIST_FOREIGN && (Histent)oldnode == he->up)) {
+	    he->flags |= HIST_DUP;
+	    addhashnode(ht, oldnode->nam, oldnode); /* Remove the new dup */
+	}
+	else {
+	    oldnode->flags |= HIST_DUP;
+	    if (hist_ignore_all_dups)
+		freehistnode(oldnode); /* Remove the old dup */
+	}
+    }
+    else
+	he->flags &= ~HIST_MAKEUNIQUE;
+}
+
+/**/
+void
+freehistnode(HashNode nodeptr)
+{
+    freehistdata((Histent)nodeptr, 1);
+    zfree(nodeptr, sizeof (struct histent));
+}
+
+/**/
+void
+freehistdata(Histent he, int unlink)
+{
+    if (!he)
+	return;
+
+    if (!(he->flags & HIST_DUP))
+	removehashnode(histtab, he->text);
+
+    zsfree(he->text);
+    if (he->nwords)
+	zfree(he->words, he->nwords*2*sizeof(short));
+
+    if (unlink) {
+	if (!--histlinect)
+	    hist_ring = NULL;
+	else {
+	    if (he == hist_ring)
+		hist_ring = hist_ring->up;
+	    he->up->down = he->down;
+	    he->down->up = he->up;
+	}
+    }
+}