1/*
2 * hashtable.c - hash tables
3 *
4 * This file is part of zsh, the Z shell.
5 *
6 * Copyright (c) 1992-1997 Paul Falstad
7 * All rights reserved.
8 *
9 * Permission is hereby granted, without written agreement and without
10 * license or royalty fees, to use, copy, modify, and distribute this
11 * software and to distribute modified versions of this software for any
12 * purpose, provided that the above copyright notice and the following
13 * two paragraphs appear in all copies of this software.
14 *
15 * In no event shall Paul Falstad or the Zsh Development Group be liable
16 * to any party for direct, indirect, special, incidental, or consequential
17 * damages arising out of the use of this software and its documentation,
18 * even if Paul Falstad and the Zsh Development Group have been advised of
19 * the possibility of such damage.
20 *
21 * Paul Falstad and the Zsh Development Group specifically disclaim any
22 * warranties, including, but not limited to, the implied warranties of
23 * merchantability and fitness for a particular purpose.  The software
24 * provided hereunder is on an "as is" basis, and Paul Falstad and the
25 * Zsh Development Group have no obligation to provide maintenance,
26 * support, updates, enhancements, or modifications.
27 *
28 */
29
30#include "../config.h"
31
32#ifdef ZSH_HASH_DEBUG
33# define HASHTABLE_DEBUG_MEMBERS \
34    /* Members of struct hashtable used for debugging hash tables */ \
35    HashTable next, last;	/* linked list of all hash tables           */ \
36    char *tablename;		/* string containing name of the hash table */ \
37    PrintTableStats printinfo;	/* pointer to function to print table stats */
38#else /* !ZSH_HASH_DEBUG */
39# define HASHTABLE_DEBUG_MEMBERS
40#endif /* !ZSH_HASH_DEBUG */
41
42#define HASHTABLE_INTERNAL_MEMBERS \
43    ScanStatus scan;		/* status of a scan over this hashtable     */ \
44    HASHTABLE_DEBUG_MEMBERS
45
46typedef struct scanstatus *ScanStatus;
47
48#include "zsh.mdh"
49#include "hashtable.pro"
50
51/* Structure for recording status of a hashtable scan in progress.  When a *
52 * scan starts, the .scan member of the hashtable structure points to one  *
53 * of these.  That member being non-NULL disables resizing of the          *
54 * hashtable (when adding elements).  When elements are deleted, the       *
55 * contents of this structure is used to make sure the scan won't stumble  *
56 * into the deleted element.                                               */
57
58struct scanstatus {
59    int sorted;
60    union {
61	struct {
62	    HashNode *hashtab;
63	    int ct;
64	} s;
65	HashNode u;
66    } u;
67};
68
69/********************************/
70/* Generic Hash Table functions */
71/********************************/
72
73#ifdef ZSH_HASH_DEBUG
74static HashTable firstht, lastht;
75#endif /* ZSH_HASH_DEBUG */
76
77/* Generic hash function */
78
79/**/
80mod_export unsigned
81hasher(const char *str)
82{
83    unsigned hashval = 0, c;
84
85    while ((c = *((unsigned char *) str++)))
86	hashval += (hashval << 5) + c;
87
88    return hashval;
89}
90
91/* Get a new hash table */
92
93/**/
94mod_export HashTable
95newhashtable(int size, UNUSED(char const *name), UNUSED(PrintTableStats printinfo))
96{
97    HashTable ht;
98
99    ht = (HashTable) zshcalloc(sizeof *ht);
100#ifdef ZSH_HASH_DEBUG
101    ht->next = NULL;
102    if(!firstht)
103	firstht = ht;
104    ht->last = lastht;
105    if(lastht)
106	lastht->next = ht;
107    lastht = ht;
108    ht->printinfo = printinfo ? printinfo : printhashtabinfo;
109    ht->tablename = ztrdup(name);
110#endif /* ZSH_HASH_DEBUG */
111    ht->nodes = (HashNode *) zshcalloc(size * sizeof(HashNode));
112    ht->hsize = size;
113    ht->ct = 0;
114    ht->scan = NULL;
115    ht->scantab = NULL;
116    return ht;
117}
118
119/* Delete a hash table.  After this function has been used, any *
120 * existing pointers to the hash table are invalid.             */
121
122/**/
123mod_export void
124deletehashtable(HashTable ht)
125{
126    ht->emptytable(ht);
127#ifdef ZSH_HASH_DEBUG
128    if(ht->next)
129	ht->next->last = ht->last;
130    else
131	lastht = ht->last;
132    if(ht->last)
133	ht->last->next = ht->next;
134    else
135	firstht = ht->next;
136    zsfree(ht->tablename);
137#endif /* ZSH_HASH_DEBUG */
138    zfree(ht->nodes, ht->hsize * sizeof(HashNode));
139    zfree(ht, sizeof(*ht));
140}
141
142/* Add a node to a hash table.                          *
143 * nam is the key to use in hashing.  nodeptr points    *
144 * to the node to add.  If there is already a node in   *
145 * the table with the same key, it is first freed, and  *
146 * then the new node is added.  If the number of nodes  *
147 * is now greater than twice the number of hash values, *
148 * the table is then expanded.                          */
149
150/**/
151mod_export void
152addhashnode(HashTable ht, char *nam, void *nodeptr)
153{
154    HashNode oldnode = addhashnode2(ht, nam, nodeptr);
155    if (oldnode)
156	ht->freenode(oldnode);
157}
158
159/* Add a node to a hash table, returning the old node on replacement. */
160
161/**/
162HashNode
163addhashnode2(HashTable ht, char *nam, void *nodeptr)
164{
165    unsigned hashval;
166    HashNode hn, hp, hq;
167
168    hn = (HashNode) nodeptr;
169    hn->nam = nam;
170
171    hashval = ht->hash(hn->nam) % ht->hsize;
172    hp = ht->nodes[hashval];
173
174    /* check if this is the first node for this hash value */
175    if (!hp) {
176	hn->next = NULL;
177	ht->nodes[hashval] = hn;
178	if (++ht->ct >= ht->hsize * 2 && !ht->scan)
179	    expandhashtable(ht);
180	return NULL;
181    }
182
183    /* else check if the first node contains the same key */
184    if (ht->cmpnodes(hp->nam, hn->nam) == 0) {
185	ht->nodes[hashval] = hn;
186	replacing:
187	hn->next = hp->next;
188	if(ht->scan) {
189	    if(ht->scan->sorted) {
190		HashNode *hashtab = ht->scan->u.s.hashtab;
191		int i;
192		for(i = ht->scan->u.s.ct; i--; )
193		    if(hashtab[i] == hp)
194			hashtab[i] = hn;
195	    } else if(ht->scan->u.u == hp)
196		ht->scan->u.u = hn;
197	}
198	return hp;
199    }
200
201    /* else run through the list and check all the keys */
202    hq = hp;
203    hp = hp->next;
204    for (; hp; hq = hp, hp = hp->next) {
205	if (ht->cmpnodes(hp->nam, hn->nam) == 0) {
206	    hq->next = hn;
207	    goto replacing;
208	}
209    }
210
211    /* else just add it at the front of the list */
212    hn->next = ht->nodes[hashval];
213    ht->nodes[hashval] = hn;
214    if (++ht->ct >= ht->hsize * 2 && !ht->scan)
215        expandhashtable(ht);
216    return NULL;
217}
218
219/* Get an enabled entry in a hash table.  *
220 * If successful, it returns a pointer to *
221 * the hashnode.  If the node is DISABLED *
222 * or isn't found, it returns NULL        */
223
224/**/
225mod_export HashNode
226gethashnode(HashTable ht, const char *nam)
227{
228    unsigned hashval;
229    HashNode hp;
230
231    hashval = ht->hash(nam) % ht->hsize;
232    for (hp = ht->nodes[hashval]; hp; hp = hp->next) {
233	if (ht->cmpnodes(hp->nam, nam) == 0) {
234	    if (hp->flags & DISABLED)
235		return NULL;
236	    else
237		return hp;
238	}
239    }
240    return NULL;
241}
242
243/* Get an entry in a hash table.  It will *
244 * ignore the DISABLED flag and return a  *
245 * pointer to the hashnode if found, else *
246 * it returns NULL.                       */
247
248/**/
249mod_export HashNode
250gethashnode2(HashTable ht, const char *nam)
251{
252    unsigned hashval;
253    HashNode hp;
254
255    hashval = ht->hash(nam) % ht->hsize;
256    for (hp = ht->nodes[hashval]; hp; hp = hp->next) {
257	if (ht->cmpnodes(hp->nam, nam) == 0)
258	    return hp;
259    }
260    return NULL;
261}
262
263/* Remove an entry from a hash table.           *
264 * If successful, it removes the node from the  *
265 * table and returns a pointer to it.  If there *
266 * is no such node, then it returns NULL        */
267
268/**/
269mod_export HashNode
270removehashnode(HashTable ht, const char *nam)
271{
272    unsigned hashval;
273    HashNode hp, hq;
274
275    hashval = ht->hash(nam) % ht->hsize;
276    hp = ht->nodes[hashval];
277
278    /* if no nodes at this hash value, return NULL */
279    if (!hp)
280	return NULL;
281
282    /* else check if the key in the first one matches */
283    if (ht->cmpnodes(hp->nam, nam) == 0) {
284	ht->nodes[hashval] = hp->next;
285	gotit:
286	ht->ct--;
287	if(ht->scan) {
288	    if(ht->scan->sorted) {
289		HashNode *hashtab = ht->scan->u.s.hashtab;
290		int i;
291		for(i = ht->scan->u.s.ct; i--; )
292		    if(hashtab[i] == hp)
293			hashtab[i] = NULL;
294	    } else if(ht->scan->u.u == hp)
295		ht->scan->u.u = hp->next;
296	}
297	return hp;
298    }
299
300    /* else run through the list and check the rest of the keys */
301    hq = hp;
302    hp = hp->next;
303    for (; hp; hq = hp, hp = hp->next) {
304	if (ht->cmpnodes(hp->nam, nam) == 0) {
305	    hq->next = hp->next;
306	    goto gotit;
307	}
308    }
309
310    /* else it is not in the list, so return NULL */
311    return NULL;
312}
313
314/* Disable a node in a hash table */
315
316/**/
317void
318disablehashnode(HashNode hn, UNUSED(int flags))
319{
320    hn->flags |= DISABLED;
321}
322
323/* Enable a node in a hash table */
324
325/**/
326void
327enablehashnode(HashNode hn, UNUSED(int flags))
328{
329    hn->flags &= ~DISABLED;
330}
331
332/* Compare two hash table entries by name */
333
334/**/
335static int
336hnamcmp(const void *ap, const void *bp)
337{
338    HashNode a = *(HashNode *)ap;
339    HashNode b = *(HashNode *)bp;
340    return ztrcmp(a->nam, b->nam);
341}
342
343/* Scan the nodes in a hash table and execute scanfunc on nodes based on
344 * the flags that are set/unset.  scanflags is passed unchanged to
345 * scanfunc (if executed).
346 *
347 * If sorted != 0, then sort entries of hash table before scanning.
348 * If flags1 > 0, then execute scanfunc on a node only if at least one of
349 *                these flags is set.
350 * If flags2 > 0, then execute scanfunc on a node only if all of
351 *                these flags are NOT set.
352 * The conditions above for flags1/flags2 must both be true.
353 *
354 * It is safe to add, remove or replace hash table elements from within
355 * the scanfunc.  Replaced elements will appear in the scan exactly once,
356 * the new version if it was not scanned before the replacement was made.
357 * Added elements might or might not appear in the scan.
358 *
359 * pprog, if non-NULL, is a pattern that must match the name
360 * of the node.
361 *
362 * The function returns the number of matches, as reduced by pprog, flags1
363 * and flags2.
364 */
365
366/**/
367mod_export int
368scanmatchtable(HashTable ht, Patprog pprog, int sorted,
369	       int flags1, int flags2, ScanFunc scanfunc, int scanflags)
370{
371    int match = 0;
372    struct scanstatus st;
373
374    /*
375     * scantab is currently only used by modules to scan
376     * tables where the contents are generated on the fly from
377     * other objects.  Note the fact that in this case pprog,
378     * sorted, flags1 and flags2 are ignore.
379     */
380    if (!pprog && ht->scantab) {
381	ht->scantab(ht, scanfunc, scanflags);
382	return ht->ct;
383    }
384    if (sorted) {
385	int i, ct = ht->ct;
386	VARARR(HashNode, hnsorttab, ct);
387	HashNode *htp, hn;
388
389	/*
390	 * Because the structure might change under our feet,
391	 * we can't apply the flags and the pattern before sorting,
392	 * tempting though that is.
393	 */
394	for (htp = hnsorttab, i = 0; i < ht->hsize; i++)
395	    for (hn = ht->nodes[i]; hn; hn = hn->next)
396		*htp++ = hn;
397	qsort((void *)hnsorttab, ct, sizeof(HashNode), hnamcmp);
398
399	st.sorted = 1;
400	st.u.s.hashtab = hnsorttab;
401	st.u.s.ct = ct;
402	ht->scan = &st;
403
404	for (htp = hnsorttab, i = 0; i < ct; i++, htp++) {
405	    if ((!flags1 || ((*htp)->flags & flags1)) &&
406		!((*htp)->flags & flags2) &&
407		(!pprog || pattry(pprog, (*htp)->nam))) {
408		match++;
409		scanfunc(*htp, scanflags);
410	    }
411	}
412
413	ht->scan = NULL;
414    } else {
415	int i, hsize = ht->hsize;
416	HashNode *nodes = ht->nodes;
417
418	st.sorted = 0;
419	ht->scan = &st;
420
421	for (i = 0; i < hsize; i++)
422	    for (st.u.u = nodes[i]; st.u.u; ) {
423		HashNode hn = st.u.u;
424		st.u.u = st.u.u->next;
425		if ((!flags1 || (hn->flags & flags1)) && !(hn->flags & flags2)
426		    && (!pprog || pattry(pprog, hn->nam))) {
427		    match++;
428		    scanfunc(hn, scanflags);
429		}
430	    }
431
432	ht->scan = NULL;
433    }
434
435    return match;
436}
437
438
439/**/
440mod_export int
441scanhashtable(HashTable ht, int sorted, int flags1, int flags2,
442	      ScanFunc scanfunc, int scanflags)
443{
444    return scanmatchtable(ht, NULL, sorted, flags1, flags2,
445			  scanfunc, scanflags);
446}
447
448/* Expand hash tables when they get too many entries. *
449 * The new size is 4 times the previous size.         */
450
451/**/
452static void
453expandhashtable(HashTable ht)
454{
455    struct hashnode **onodes, **ha, *hn, *hp;
456    int i, osize;
457
458    osize = ht->hsize;
459    onodes = ht->nodes;
460
461    ht->hsize = osize * 4;
462    ht->nodes = (HashNode *) zshcalloc(ht->hsize * sizeof(HashNode));
463    ht->ct = 0;
464
465    /* scan through the old list of nodes, and *
466     * rehash them into the new list of nodes  */
467    for (i = 0, ha = onodes; i < osize; i++, ha++) {
468	for (hn = *ha; hn;) {
469	    hp = hn->next;
470	    ht->addnode(ht, hn->nam, hn);
471	    hn = hp;
472	}
473    }
474    zfree(onodes, osize * sizeof(HashNode));
475}
476
477/* Empty the hash table and resize it if necessary */
478
479/**/
480static void
481resizehashtable(HashTable ht, int newsize)
482{
483    struct hashnode **ha, *hn, *hp;
484    int i;
485
486    /* free all the hash nodes */
487    ha = ht->nodes;
488    for (i = 0; i < ht->hsize; i++, ha++) {
489	for (hn = *ha; hn;) {
490	    hp = hn->next;
491	    ht->freenode(hn);
492	    hn = hp;
493	}
494    }
495
496    /* If new size desired is different from current size, *
497     * we free it and allocate a new nodes array.          */
498    if (ht->hsize != newsize) {
499	zfree(ht->nodes, ht->hsize * sizeof(HashNode));
500	ht->nodes = (HashNode *) zshcalloc(newsize * sizeof(HashNode));
501	ht->hsize = newsize;
502    } else {
503	/* else we just re-zero the current nodes array */
504	memset(ht->nodes, 0, newsize * sizeof(HashNode));
505    }
506
507    ht->ct = 0;
508}
509
510/* Generic method to empty a hash table */
511
512/**/
513mod_export void
514emptyhashtable(HashTable ht)
515{
516    resizehashtable(ht, ht->hsize);
517}
518
519/**/
520#ifdef ZSH_HASH_DEBUG
521
522/* Print info about hash table */
523
524#define MAXDEPTH 7
525
526/**/
527static void
528printhashtabinfo(HashTable ht)
529{
530    HashNode hn;
531    int chainlen[MAXDEPTH + 1];
532    int i, tmpcount, total;
533
534    printf("name of table   : %s\n",   ht->tablename);
535    printf("size of nodes[] : %d\n",   ht->hsize);
536    printf("number of nodes : %d\n\n", ht->ct);
537
538    memset(chainlen, 0, sizeof(chainlen));
539
540    /* count the number of nodes just to be sure */
541    total = 0;
542    for (i = 0; i < ht->hsize; i++) {
543	tmpcount = 0;
544	for (hn = ht->nodes[i]; hn; hn = hn->next)
545	    tmpcount++;
546	if (tmpcount >= MAXDEPTH)
547	    chainlen[MAXDEPTH]++;
548	else
549	    chainlen[tmpcount]++;
550	total += tmpcount;
551    }
552
553    for (i = 0; i < MAXDEPTH; i++)
554	printf("number of hash values with chain of length %d  : %4d\n", i, chainlen[i]);
555    printf("number of hash values with chain of length %d+ : %4d\n", MAXDEPTH, chainlen[MAXDEPTH]);
556    printf("total number of nodes                         : %4d\n", total);
557}
558
559/**/
560int
561bin_hashinfo(char *nam, char **args, Options ops, int func)
562{
563    HashTable ht;
564
565    printf("----------------------------------------------------\n");
566    queue_signals();
567    for(ht = firstht; ht; ht = ht->next) {
568	ht->printinfo(ht);
569	printf("----------------------------------------------------\n");
570    }
571    unqueue_signals();
572    return 0;
573}
574
575/**/
576#endif /* ZSH_HASH_DEBUG */
577
578/********************************/
579/* Command Hash Table Functions */
580/********************************/
581
582/* hash table containing external commands */
583
584/**/
585mod_export HashTable cmdnamtab;
586
587/* how far we've hashed the PATH so far */
588
589/**/
590mod_export char **pathchecked;
591
592/* Create a new command hash table */
593
594/**/
595void
596createcmdnamtable(void)
597{
598    cmdnamtab = newhashtable(201, "cmdnamtab", NULL);
599
600    cmdnamtab->hash        = hasher;
601    cmdnamtab->emptytable  = emptycmdnamtable;
602    cmdnamtab->filltable   = fillcmdnamtable;
603    cmdnamtab->cmpnodes    = strcmp;
604    cmdnamtab->addnode     = addhashnode;
605    cmdnamtab->getnode     = gethashnode2;
606    cmdnamtab->getnode2    = gethashnode2;
607    cmdnamtab->removenode  = removehashnode;
608    cmdnamtab->disablenode = NULL;
609    cmdnamtab->enablenode  = NULL;
610    cmdnamtab->freenode    = freecmdnamnode;
611    cmdnamtab->printnode   = printcmdnamnode;
612
613    pathchecked = path;
614}
615
616/**/
617static void
618emptycmdnamtable(HashTable ht)
619{
620    emptyhashtable(ht);
621    pathchecked = path;
622}
623
624/* Add all commands in a given directory *
625 * to the command hashtable.             */
626
627/**/
628void
629hashdir(char **dirp)
630{
631    Cmdnam cn;
632    DIR *dir;
633    char *fn, *unmetadir, *pathbuf, *pathptr;
634    int dirlen;
635#if defined(_WIN32) || defined(__CYGWIN__)
636    char *exe;
637#endif /* _WIN32 || _CYGWIN__ */
638
639    if (isrelative(*dirp))
640	return;
641    unmetadir = unmeta(*dirp);
642    if (!(dir = opendir(unmetadir)))
643	return;
644
645    dirlen = strlen(unmetadir);
646    pathbuf = (char *)zalloc(dirlen + PATH_MAX + 2);
647    sprintf(pathbuf, "%s/", unmetadir);
648    pathptr = pathbuf + dirlen + 1;
649
650    while ((fn = zreaddir(dir, 1))) {
651	if (!cmdnamtab->getnode(cmdnamtab, fn)) {
652	    char *fname = ztrdup(fn);
653	    struct stat statbuf;
654	    int add = 0, dummylen;
655
656	    unmetafy(fn, &dummylen);
657	    if (strlen(fn) > PATH_MAX) {
658		/* Too heavy to do all the allocation */
659		add = 1;
660	    } else {
661		strcpy(pathptr, fn);
662		/*
663		 * This is the same test as for the glob qualifier for
664		 * executable plain files.
665		 */
666		if (unset(HASHEXECUTABLESONLY) ||
667		    (access(pathbuf, X_OK) == 0 &&
668		     stat(pathbuf, &statbuf) == 0 &&
669		     S_ISREG(statbuf.st_mode) && (statbuf.st_mode & S_IXUGO)))
670		    add = 1;
671	    }
672	    if (add) {
673		cn = (Cmdnam) zshcalloc(sizeof *cn);
674		cn->node.flags = 0;
675		cn->u.name = dirp;
676		cmdnamtab->addnode(cmdnamtab, fname, cn);
677	    } else
678		zsfree(fname);
679	}
680#if defined(_WIN32) || defined(__CYGWIN__)
681	/* Hash foo.exe as foo, since when no real foo exists, foo.exe
682	   will get executed by DOS automatically.  This quiets
683	   spurious corrections when CORRECT or CORRECT_ALL is set. */
684	if ((exe = strrchr(fn, '.')) &&
685	    (exe[1] == 'E' || exe[1] == 'e') &&
686	    (exe[2] == 'X' || exe[2] == 'x') &&
687	    (exe[3] == 'E' || exe[3] == 'e') && exe[4] == 0) {
688	    *exe = 0;
689	    if (!cmdnamtab->getnode(cmdnamtab, fn)) {
690		cn = (Cmdnam) zshcalloc(sizeof *cn);
691		cn->node.flags = 0;
692		cn->u.name = dirp;
693		cmdnamtab->addnode(cmdnamtab, ztrdup(fn), cn);
694	    }
695	}
696#endif /* _WIN32 || __CYGWIN__ */
697    }
698    closedir(dir);
699    zfree(pathbuf, dirlen + PATH_MAX + 2);
700}
701
702/* Go through user's PATH and add everything to *
703 * the command hashtable.                       */
704
705/**/
706static void
707fillcmdnamtable(UNUSED(HashTable ht))
708{
709    char **pq;
710
711    for (pq = pathchecked; *pq; pq++)
712	hashdir(pq);
713
714    pathchecked = pq;
715}
716
717/**/
718static void
719freecmdnamnode(HashNode hn)
720{
721    Cmdnam cn = (Cmdnam) hn;
722
723    zsfree(cn->node.nam);
724    if (cn->node.flags & HASHED)
725	zsfree(cn->u.cmd);
726
727    zfree(cn, sizeof(struct cmdnam));
728}
729
730/* Print an element of the cmdnamtab hash table (external command) */
731
732/**/
733static void
734printcmdnamnode(HashNode hn, int printflags)
735{
736    Cmdnam cn = (Cmdnam) hn;
737
738    if (printflags & PRINT_WHENCE_WORD) {
739	printf("%s: %s\n", cn->node.nam, (cn->node.flags & HASHED) ?
740	       "hashed" : "command");
741	return;
742    }
743
744    if ((printflags & PRINT_WHENCE_CSH) || (printflags & PRINT_WHENCE_SIMPLE)) {
745	if (cn->node.flags & HASHED) {
746	    zputs(cn->u.cmd, stdout);
747	    putchar('\n');
748	} else {
749	    zputs(*(cn->u.name), stdout);
750	    putchar('/');
751	    zputs(cn->node.nam, stdout);
752	    putchar('\n');
753	}
754	return;
755    }
756
757    if (printflags & PRINT_WHENCE_VERBOSE) {
758	if (cn->node.flags & HASHED) {
759	    nicezputs(cn->node.nam, stdout);
760	    printf(" is hashed to ");
761	    nicezputs(cn->u.cmd, stdout);
762	    putchar('\n');
763	} else {
764	    nicezputs(cn->node.nam, stdout);
765	    printf(" is ");
766	    nicezputs(*(cn->u.name), stdout);
767	    putchar('/');
768	    nicezputs(cn->node.nam, stdout);
769	    putchar('\n');
770	}
771	return;
772    }
773
774    if (printflags & PRINT_LIST) {
775	printf("hash ");
776
777	if(cn->node.nam[0] == '-')
778	    printf("-- ");
779    }
780
781    if (cn->node.flags & HASHED) {
782	quotedzputs(cn->node.nam, stdout);
783	putchar('=');
784	quotedzputs(cn->u.cmd, stdout);
785	putchar('\n');
786    } else {
787	quotedzputs(cn->node.nam, stdout);
788	putchar('=');
789	quotedzputs(*(cn->u.name), stdout);
790	putchar('/');
791	quotedzputs(cn->node.nam, stdout);
792	putchar('\n');
793    }
794}
795
796/***************************************/
797/* Shell Function Hash Table Functions */
798/***************************************/
799
800/* hash table containing the shell functions */
801
802/**/
803mod_export HashTable shfunctab;
804
805/**/
806void
807createshfunctable(void)
808{
809    shfunctab = newhashtable(7, "shfunctab", NULL);
810
811    shfunctab->hash        = hasher;
812    shfunctab->emptytable  = NULL;
813    shfunctab->filltable   = NULL;
814    shfunctab->cmpnodes    = strcmp;
815    shfunctab->addnode     = addhashnode;
816    shfunctab->getnode     = gethashnode;
817    shfunctab->getnode2    = gethashnode2;
818    shfunctab->removenode  = removeshfuncnode;
819    shfunctab->disablenode = disableshfuncnode;
820    shfunctab->enablenode  = enableshfuncnode;
821    shfunctab->freenode    = freeshfuncnode;
822    shfunctab->printnode   = printshfuncnode;
823}
824
825/* Remove an entry from the shell function hash table.   *
826 * It checks if the function is a signal trap and if so, *
827 * it will disable the trapping of that signal.          */
828
829/**/
830static HashNode
831removeshfuncnode(UNUSED(HashTable ht), const char *nam)
832{
833    HashNode hn;
834    int signum;
835
836    if (!strncmp(nam, "TRAP", 4) && (signum = getsignum(nam + 4)) != -1)
837	hn = removetrap(signum);
838    else
839	hn = removehashnode(shfunctab, nam);
840
841    return hn;
842}
843
844/* Disable an entry in the shell function hash table.    *
845 * It checks if the function is a signal trap and if so, *
846 * it will disable the trapping of that signal.          */
847
848/**/
849static void
850disableshfuncnode(HashNode hn, UNUSED(int flags))
851{
852    hn->flags |= DISABLED;
853    if (!strncmp(hn->nam, "TRAP", 4)) {
854	int signum = getsignum(hn->nam + 4);
855	if (signum != -1) {
856	    sigtrapped[signum] &= ~ZSIG_FUNC;
857	    unsettrap(signum);
858	}
859    }
860}
861
862/* Re-enable an entry in the shell function hash table.  *
863 * It checks if the function is a signal trap and if so, *
864 * it will re-enable the trapping of that signal.        */
865
866/**/
867static void
868enableshfuncnode(HashNode hn, UNUSED(int flags))
869{
870    Shfunc shf = (Shfunc) hn;
871
872    shf->node.flags &= ~DISABLED;
873    if (!strncmp(shf->node.nam, "TRAP", 4)) {
874	int signum = getsignum(shf->node.nam + 4);
875	if (signum != -1) {
876	    settrap(signum, NULL, ZSIG_FUNC);
877	}
878    }
879}
880
881/**/
882static void
883freeshfuncnode(HashNode hn)
884{
885    Shfunc shf = (Shfunc) hn;
886
887    zsfree(shf->node.nam);
888    if (shf->funcdef)
889	freeeprog(shf->funcdef);
890    zsfree(shf->filename);
891    if (shf->sticky) {
892	if (shf->sticky->n_on_opts)
893	    zfree(shf->sticky->on_opts,
894		  shf->sticky->n_on_opts * sizeof(*shf->sticky->on_opts));
895	if (shf->sticky->n_off_opts)
896	    zfree(shf->sticky->off_opts,
897		  shf->sticky->n_off_opts * sizeof(*shf->sticky->off_opts));
898	zfree(shf->sticky, sizeof(*shf->sticky));
899    }
900    zfree(shf, sizeof(struct shfunc));
901}
902
903/* Print a shell function */
904
905/**/
906static void
907printshfuncnode(HashNode hn, int printflags)
908{
909    Shfunc f = (Shfunc) hn;
910    char *t = 0;
911
912    if ((printflags & PRINT_NAMEONLY) ||
913	((printflags & PRINT_WHENCE_SIMPLE) &&
914	!(printflags & PRINT_WHENCE_FUNCDEF))) {
915	zputs(f->node.nam, stdout);
916	putchar('\n');
917	return;
918    }
919
920    if ((printflags & (PRINT_WHENCE_VERBOSE|PRINT_WHENCE_WORD)) &&
921	!(printflags & PRINT_WHENCE_FUNCDEF)) {
922	nicezputs(f->node.nam, stdout);
923	printf((printflags & PRINT_WHENCE_WORD) ? ": function\n" :
924	       " is a shell function\n");
925	return;
926    }
927
928    quotedzputs(f->node.nam, stdout);
929    if (f->funcdef || f->node.flags & PM_UNDEFINED) {
930	printf(" () {\n\t");
931	if (f->node.flags & PM_UNDEFINED)
932	    printf("%c undefined\n\t", hashchar);
933	else
934	    t = getpermtext(f->funcdef, NULL, 1);
935	if (f->node.flags & (PM_TAGGED|PM_TAGGED_LOCAL))
936	    printf("%c traced\n\t", hashchar);
937	if (!t) {
938	    char *fopt = "UtTkz";
939	    int flgs[] = {
940		PM_UNALIASED, PM_TAGGED, PM_TAGGED_LOCAL,
941		PM_KSHSTORED, PM_ZSHSTORED, 0
942	    };
943	    int fl;;
944
945	    zputs("builtin autoload -X", stdout);
946	    for (fl=0;fopt[fl];fl++)
947		if (f->node.flags & flgs[fl]) putchar(fopt[fl]);
948	} else {
949	    zputs(t, stdout);
950	    zsfree(t);
951	    if (f->funcdef->flags & EF_RUN) {
952		printf("\n\t");
953		quotedzputs(f->node.nam, stdout);
954		printf(" \"$@\"");
955	    }
956	}
957	printf("\n}\n");
958    } else {
959	printf(" () { }\n");
960    }
961}
962
963/**************************************/
964/* Reserved Word Hash Table Functions */
965/**************************************/
966
967/* Nodes for reserved word hash table */
968
969static struct reswd reswds[] = {
970    {{NULL, "!", 0}, BANG},
971    {{NULL, "[[", 0}, DINBRACK},
972    {{NULL, "{", 0}, INBRACE},
973    {{NULL, "}", 0}, OUTBRACE},
974    {{NULL, "case", 0}, CASE},
975    {{NULL, "coproc", 0}, COPROC},
976    {{NULL, "do", 0}, DOLOOP},
977    {{NULL, "done", 0}, DONE},
978    {{NULL, "elif", 0}, ELIF},
979    {{NULL, "else", 0}, ELSE},
980    {{NULL, "end", 0}, ZEND},
981    {{NULL, "esac", 0}, ESAC},
982    {{NULL, "fi", 0}, FI},
983    {{NULL, "for", 0}, FOR},
984    {{NULL, "foreach", 0}, FOREACH},
985    {{NULL, "function", 0}, FUNC},
986    {{NULL, "if", 0}, IF},
987    {{NULL, "nocorrect", 0}, NOCORRECT},
988    {{NULL, "repeat", 0}, REPEAT},
989    {{NULL, "select", 0}, SELECT},
990    {{NULL, "then", 0}, THEN},
991    {{NULL, "time", 0}, TIME},
992    {{NULL, "until", 0}, UNTIL},
993    {{NULL, "while", 0}, WHILE},
994    {{NULL, NULL, 0}, 0}
995};
996
997/* hash table containing the reserved words */
998
999/**/
1000mod_export HashTable reswdtab;
1001
1002/* Build the hash table containing zsh's reserved words. */
1003
1004/**/
1005void
1006createreswdtable(void)
1007{
1008    Reswd rw;
1009
1010    reswdtab = newhashtable(23, "reswdtab", NULL);
1011
1012    reswdtab->hash        = hasher;
1013    reswdtab->emptytable  = NULL;
1014    reswdtab->filltable   = NULL;
1015    reswdtab->cmpnodes    = strcmp;
1016    reswdtab->addnode     = addhashnode;
1017    reswdtab->getnode     = gethashnode;
1018    reswdtab->getnode2    = gethashnode2;
1019    reswdtab->removenode  = NULL;
1020    reswdtab->disablenode = disablehashnode;
1021    reswdtab->enablenode  = enablehashnode;
1022    reswdtab->freenode    = NULL;
1023    reswdtab->printnode   = printreswdnode;
1024
1025    for (rw = reswds; rw->node.nam; rw++)
1026	reswdtab->addnode(reswdtab, rw->node.nam, rw);
1027}
1028
1029/* Print a reserved word */
1030
1031/**/
1032static void
1033printreswdnode(HashNode hn, int printflags)
1034{
1035    Reswd rw = (Reswd) hn;
1036
1037    if (printflags & PRINT_WHENCE_WORD) {
1038	printf("%s: reserved\n", rw->node.nam);
1039	return;
1040    }
1041
1042    if (printflags & PRINT_WHENCE_CSH) {
1043	printf("%s: shell reserved word\n", rw->node.nam);
1044	return;
1045    }
1046
1047    if (printflags & PRINT_WHENCE_VERBOSE) {
1048	printf("%s is a reserved word\n", rw->node.nam);
1049	return;
1050    }
1051
1052    /* default is name only */
1053    printf("%s\n", rw->node.nam);
1054}
1055
1056/********************************/
1057/* Aliases Hash Table Functions */
1058/********************************/
1059
1060/* hash table containing the aliases */
1061
1062/**/
1063mod_export HashTable aliastab;
1064
1065/* has table containing suffix aliases */
1066
1067/**/
1068mod_export HashTable sufaliastab;
1069
1070/* Create new hash tables for aliases */
1071
1072/**/
1073void
1074createaliastable(HashTable ht)
1075{
1076    ht->hash        = hasher;
1077    ht->emptytable  = NULL;
1078    ht->filltable   = NULL;
1079    ht->cmpnodes    = strcmp;
1080    ht->addnode     = addhashnode;
1081    ht->getnode     = gethashnode;
1082    ht->getnode2    = gethashnode2;
1083    ht->removenode  = removehashnode;
1084    ht->disablenode = disablehashnode;
1085    ht->enablenode  = enablehashnode;
1086    ht->freenode    = freealiasnode;
1087    ht->printnode   = printaliasnode;
1088}
1089
1090/**/
1091void
1092createaliastables(void)
1093{
1094    /* Table for regular and global aliases */
1095
1096    aliastab = newhashtable(23, "aliastab", NULL);
1097
1098    createaliastable(aliastab);
1099
1100    /* add the default aliases */
1101    aliastab->addnode(aliastab, ztrdup("run-help"), createaliasnode(ztrdup("man"), 0));
1102    aliastab->addnode(aliastab, ztrdup("which-command"), createaliasnode(ztrdup("whence"), 0));
1103
1104
1105    /* Table for suffix aliases --- make this smaller */
1106
1107    sufaliastab = newhashtable(11, "sufaliastab", NULL);
1108
1109    createaliastable(sufaliastab);
1110}
1111
1112/* Create a new alias node */
1113
1114/**/
1115mod_export Alias
1116createaliasnode(char *txt, int flags)
1117{
1118    Alias al;
1119
1120    al = (Alias) zshcalloc(sizeof *al);
1121    al->node.flags = flags;
1122    al->text = txt;
1123    al->inuse = 0;
1124    return al;
1125}
1126
1127/**/
1128static void
1129freealiasnode(HashNode hn)
1130{
1131    Alias al = (Alias) hn;
1132
1133    zsfree(al->node.nam);
1134    zsfree(al->text);
1135    zfree(al, sizeof(struct alias));
1136}
1137
1138/* Print an alias */
1139
1140/**/
1141static void
1142printaliasnode(HashNode hn, int printflags)
1143{
1144    Alias a = (Alias) hn;
1145
1146    if (printflags & PRINT_NAMEONLY) {
1147	zputs(a->node.nam, stdout);
1148	putchar('\n');
1149	return;
1150    }
1151
1152    if (printflags & PRINT_WHENCE_WORD) {
1153	printf("%s: alias\n", a->node.nam);
1154	return;
1155    }
1156
1157    if (printflags & PRINT_WHENCE_SIMPLE) {
1158	zputs(a->text, stdout);
1159	putchar('\n');
1160	return;
1161    }
1162
1163    if (printflags & PRINT_WHENCE_CSH) {
1164	nicezputs(a->node.nam, stdout);
1165	printf(": ");
1166	if (a->node.flags & ALIAS_SUFFIX)
1167	    printf("suffix ");
1168	else if (a->node.flags & ALIAS_GLOBAL)
1169	    printf("globally ");
1170	printf ("aliased to ");
1171	nicezputs(a->text, stdout);
1172	putchar('\n');
1173	return;
1174    }
1175
1176    if (printflags & PRINT_WHENCE_VERBOSE) {
1177	nicezputs(a->node.nam, stdout);
1178	printf(" is a");
1179	if (a->node.flags & ALIAS_SUFFIX)
1180	    printf(" suffix");
1181	else if (a->node.flags & ALIAS_GLOBAL)
1182	    printf(" global");
1183	else
1184	    printf("n");
1185	printf(" alias for ");
1186	nicezputs(a->text, stdout);
1187	putchar('\n');
1188	return;
1189    }
1190
1191    if (printflags & PRINT_LIST) {
1192	printf("alias ");
1193	if (a->node.flags & ALIAS_SUFFIX)
1194	    printf("-s ");
1195	else if (a->node.flags & ALIAS_GLOBAL)
1196	    printf("-g ");
1197
1198	/* If an alias begins with `-', then we must output `-- ' *
1199	 * first, so that it is not interpreted as an option.     */
1200	if(a->node.nam[0] == '-')
1201	    printf("-- ");
1202    }
1203
1204    quotedzputs(a->node.nam, stdout);
1205    putchar('=');
1206    quotedzputs(a->text, stdout);
1207
1208    putchar('\n');
1209}
1210
1211/*************************************/
1212/* History Line Hash Table Functions */
1213/*************************************/
1214
1215/**/
1216void
1217createhisttable(void)
1218{
1219    histtab = newhashtable(599, "histtab", NULL);
1220
1221    histtab->hash        = histhasher;
1222    histtab->emptytable  = emptyhisttable;
1223    histtab->filltable   = NULL;
1224    histtab->cmpnodes    = histstrcmp;
1225    histtab->addnode     = addhistnode;
1226    histtab->getnode     = gethashnode2;
1227    histtab->getnode2    = gethashnode2;
1228    histtab->removenode  = removehashnode;
1229    histtab->disablenode = NULL;
1230    histtab->enablenode  = NULL;
1231    histtab->freenode    = freehistnode;
1232    histtab->printnode   = NULL;
1233}
1234
1235/**/
1236unsigned
1237histhasher(const char *str)
1238{
1239    unsigned hashval = 0;
1240
1241    while (inblank(*str)) str++;
1242
1243    while (*str) {
1244	if (inblank(*str)) {
1245	    do str++; while (inblank(*str));
1246	    if (*str)
1247		hashval += (hashval << 5) + ' ';
1248	}
1249	else
1250	    hashval += (hashval << 5) + *(unsigned char *)str++;
1251    }
1252    return hashval;
1253}
1254
1255/**/
1256void
1257emptyhisttable(HashTable ht)
1258{
1259    emptyhashtable(ht);
1260    if (hist_ring)
1261	histremovedups();
1262}
1263
1264/* Compare two strings with normalized white-space */
1265
1266/**/
1267int
1268histstrcmp(const char *str1, const char *str2)
1269{
1270    while (inblank(*str1)) str1++;
1271    while (inblank(*str2)) str2++;
1272    while (*str1 && *str2) {
1273	if (inblank(*str1)) {
1274	    if (!inblank(*str2))
1275		break;
1276	    do str1++; while (inblank(*str1));
1277	    do str2++; while (inblank(*str2));
1278	}
1279	else {
1280	    if (*str1 != *str2)
1281		break;
1282	    str1++;
1283	    str2++;
1284	}
1285    }
1286    return *str1 - *str2;
1287}
1288
1289/**/
1290void
1291addhistnode(HashTable ht, char *nam, void *nodeptr)
1292{
1293    HashNode oldnode = addhashnode2(ht, nam, nodeptr);
1294    Histent he = (Histent)nodeptr;
1295    if (oldnode && oldnode != (HashNode)nodeptr) {
1296	if (he->node.flags & HIST_MAKEUNIQUE
1297	 || (he->node.flags & HIST_FOREIGN && (Histent)oldnode == he->up)) {
1298	    (void) addhashnode2(ht, oldnode->nam, oldnode); /* restore hash */
1299	    he->node.flags |= HIST_DUP;
1300	    he->node.flags &= ~HIST_MAKEUNIQUE;
1301	}
1302	else {
1303	    oldnode->flags |= HIST_DUP;
1304	    if (hist_ignore_all_dups)
1305		freehistnode(oldnode); /* Remove the old dup */
1306	}
1307    }
1308    else
1309	he->node.flags &= ~HIST_MAKEUNIQUE;
1310}
1311
1312/**/
1313void
1314freehistnode(HashNode nodeptr)
1315{
1316    freehistdata((Histent)nodeptr, 1);
1317    zfree(nodeptr, sizeof (struct histent));
1318}
1319
1320/**/
1321void
1322freehistdata(Histent he, int unlink)
1323{
1324    if (!he)
1325	return;
1326
1327    if (!(he->node.flags & (HIST_DUP | HIST_TMPSTORE)))
1328	removehashnode(histtab, he->node.nam);
1329
1330    zsfree(he->node.nam);
1331    if (he->nwords)
1332	zfree(he->words, he->nwords*2*sizeof(short));
1333
1334    if (unlink) {
1335	if (!--histlinect)
1336	    hist_ring = NULL;
1337	else {
1338	    if (he == hist_ring)
1339		hist_ring = hist_ring->up;
1340	    he->up->down = he->down;
1341	    he->down->up = he->up;
1342	}
1343    }
1344}
1345