1 //hashtable.c - hash tables

     2 //

     3 // © Portions Copyright (c) Symbian Software Ltd 2007. All rights reserved.

     4 //

     5 /*

     6  * This file is part of zsh, the Z shell.

     7  *

     8  * Copyright (c) 1992-1997 Paul Falstad

     9  * All rights reserved.

    10  *

    11  * Permission is hereby granted, without written agreement and without

    12  * license or royalty fees, to use, copy, modify, and distribute this

    13  * software and to distribute modified versions of this software for any

    14  * purpose, provided that the above copyright notice and the following

    15  * two paragraphs appear in all copies of this software.

    16  *

    17  * In no event shall Paul Falstad or the Zsh Development Group be liable

    18  * to any party for direct, indirect, special, incidental, or consequential

    19  * damages arising out of the use of this software and its documentation,

    20  * even if Paul Falstad and the Zsh Development Group have been advised of

    21  * the possibility of such damage.

    22  *

    23  * Paul Falstad and the Zsh Development Group specifically disclaim any

    24  * warranties, including, but not limited to, the implied warranties of

    25  * merchantability and fitness for a particular purpose.  The software

    26  * provided hereunder is on an "as is" basis, and Paul Falstad and the

    27  * Zsh Development Group have no obligation to provide maintenance,

    28  * support, updates, enhancements, or modifications.

    29  *

    30  */

    31 #include "config.h"

    32 

    33 #ifdef __SYMBIAN32__

    34 #ifdef __WINSCW__

    35 #pragma warn_unusedarg off

    36 #endif//__WINSCW__

    37 #endif//__SYMBIAN32__

    38 

    39 #ifdef ZSH_HASH_DEBUG

    40 # define HASHTABLE_DEBUG_MEMBERS \

    41     /* Members of struct hashtable used for debugging hash tables */ \

    42     HashTable next, last;	/* linked list of all hash tables           */ \

    43     char *tablename;		/* string containing name of the hash table */ \

    44     PrintTableStats printinfo;	/* pointer to function to print table stats */

    45 #else /* !ZSH_HASH_DEBUG */

    46 # define HASHTABLE_DEBUG_MEMBERS

    47 #endif /* !ZSH_HASH_DEBUG */

    48 

    49 #define HASHTABLE_INTERNAL_MEMBERS \

    50     ScanStatus scan;		/* status of a scan over this hashtable     */ \

    51     HASHTABLE_DEBUG_MEMBERS

    52 

    53 typedef struct scanstatus *ScanStatus;

    54 

    55 #include "zsh.mdh"

    56 #include "hashtable.pro"

    57 

    58 /* Structure for recording status of a hashtable scan in progress.  When a *

    59  * scan starts, the .scan member of the hashtable structure points to one  *

    60  * of these.  That member being non-NULL disables resizing of the          *

    61  * hashtable (when adding elements).  When elements are deleted, the       *

    62  * contents of this structure is used to make sure the scan won't stumble  *

    63  * into the deleted element.                                               */

    64 

    65 struct scanstatus {

    66     int sorted;

    67     union {

    68 	struct {

    69 	    HashNode *tab;

    70 	    int ct;

    71 	} s;

    72 	HashNode u;

    73     } u;

    74 };

    75 

    76 /********************************/

    77 /* Generic Hash Table functions */

    78 /********************************/

    79 

    80 #ifdef ZSH_HASH_DEBUG

    81 static HashTable firstht, lastht;

    82 #endif /* ZSH_HASH_DEBUG */

    83 

    84 /* Generic hash function */

    85 

    86 /**/

    87 mod_export unsigned

    88 hasher(char *str)

    89 {

    90     unsigned hashval = 0, c;

    91 

    92     while ((c = *((unsigned char *) str++)))

    93 	hashval += (hashval << 5) + c;

    94 

    95     return hashval;

    96 }

    97 

    98 /* Get a new hash table */

    99 

   100 /**/

   101 mod_export HashTable

   102 newhashtable(int size, UNUSED(char const *name), UNUSED(PrintTableStats printinfo))

   103 {

   104     HashTable ht;

   105 

   106     ht = (HashTable) zshcalloc(sizeof *ht);

   107 #ifdef ZSH_HASH_DEBUG

   108     ht->next = NULL;

   109     if(!firstht)

   110 	firstht = ht;

   111     ht->last = lastht;

   112     if(lastht)

   113 	lastht->next = ht;

   114     lastht = ht;

   115     ht->printinfo = printinfo ? printinfo : printhashtabinfo;

   116     ht->tablename = ztrdup(name);

   117 #endif /* ZSH_HASH_DEBUG */

   118     ht->nodes = (HashNode *) zshcalloc(size * sizeof(HashNode));

   119     ht->hsize = size;

   120     ht->ct = 0;

   121     ht->scan = NULL;

   122     ht->scantab = NULL;

   123     return ht;

   124 }

   125 

   126 /* Delete a hash table.  After this function has been used, any *

   127  * existing pointers to the hash table are invalid.             */

   128 

   129 /**/

   130 mod_export void

   131 deletehashtable(HashTable ht)

   132 {

   133     ht->emptytable(ht);

   134 #ifdef ZSH_HASH_DEBUG

   135     if(ht->next)

   136 	ht->next->last = ht->last;

   137     else

   138 	lastht = ht->last;

   139     if(ht->last)

   140 	ht->last->next = ht->next;

   141     else

   142 	firstht = ht->next;

   143     zsfree(ht->tablename);

   144 #endif /* ZSH_HASH_DEBUG */

   145     zfree(ht->nodes, ht->hsize * sizeof(HashNode));

   146     zfree(ht, sizeof(*ht));

   147 }

   148 

   149 /* Add a node to a hash table.                          *

   150  * nam is the key to use in hashing.  nodeptr points    *

   151  * to the node to add.  If there is already a node in   *

   152  * the table with the same key, it is first freed, and  *

   153  * then the new node is added.  If the number of nodes  *

   154  * is now greater than twice the number of hash values, *

   155  * the table is then expanded.                          */

   156 

   157 /**/

   158 mod_export void

   159 addhashnode(HashTable ht, char *nam, void *nodeptr)

   160 {

   161     HashNode oldnode = addhashnode2(ht, nam, nodeptr);

   162     if (oldnode)

   163 	ht->freenode(oldnode);

   164 }

   165 

   166 /* Add a node to a hash table, returning the old node on replacement. */

   167 

   168 /**/

   169 HashNode

   170 addhashnode2(HashTable ht, char *nam, void *nodeptr)

   171 {

   172     unsigned hashval;

   173     HashNode hn, hp, hq;

   174 

   175     hn = (HashNode) nodeptr;

   176     hn->nam = nam;

   177 

   178     hashval = ht->hash(hn->nam) % ht->hsize;

   179     hp = ht->nodes[hashval];

   180 

   181     /* check if this is the first node for this hash value */

   182     if (!hp) {

   183 	hn->next = NULL;

   184 	ht->nodes[hashval] = hn;

   185 	if (++ht->ct >= ht->hsize * 2 && !ht->scan)

   186 	    expandhashtable(ht);

   187 	return NULL;

   188     }

   189 

   190     /* else check if the first node contains the same key */

   191     if (ht->cmpnodes(hp->nam, hn->nam) == 0) {

   192 	ht->nodes[hashval] = hn;

   193 	replacing:

   194 	hn->next = hp->next;

   195 	if(ht->scan) {

   196 	    if(ht->scan->sorted) {

   197 		HashNode *tab = ht->scan->u.s.tab;

   198 		int i;

   199 		for(i = ht->scan->u.s.ct; i--; )

   200 		    if(tab[i] == hp)

   201 			tab[i] = hn;

   202 	    } else if(ht->scan->u.u == hp)

   203 		ht->scan->u.u = hn;

   204 	}

   205 	return hp;

   206     }

   207 

   208     /* else run through the list and check all the keys */

   209     hq = hp;

   210     hp = hp->next;

   211     for (; hp; hq = hp, hp = hp->next) {

   212 	if (ht->cmpnodes(hp->nam, hn->nam) == 0) {

   213 	    hq->next = hn;

   214 	    goto replacing;

   215 	}

   216     }

   217 

   218     /* else just add it at the front of the list */

   219     hn->next = ht->nodes[hashval];

   220     ht->nodes[hashval] = hn;

   221     if (++ht->ct >= ht->hsize * 2 && !ht->scan)

   222         expandhashtable(ht);

   223     return NULL;

   224 }

   225 

   226 /* Get an enabled entry in a hash table.  *

   227  * If successful, it returns a pointer to *

   228  * the hashnode.  If the node is DISABLED *

   229  * or isn't found, it returns NULL        */

   230 

   231 /**/

   232 mod_export HashNode

   233 gethashnode(HashTable ht, char *nam)

   234 {

   235     unsigned hashval;

   236     HashNode hp;

   237 

   238     hashval = ht->hash(nam) % ht->hsize;

   239     for (hp = ht->nodes[hashval]; hp; hp = hp->next) {

   240 	if (ht->cmpnodes(hp->nam, nam) == 0) {

   241 	    if (hp->flags & DISABLED)

   242 		return NULL;

   243 	    else

   244 		return hp;

   245 	}

   246     }

   247     return NULL;

   248 }

   249 

   250 /* Get an entry in a hash table.  It will *

   251  * ignore the DISABLED flag and return a  *

   252  * pointer to the hashnode if found, else *

   253  * it returns NULL.                       */

   254 

   255 /**/

   256 mod_export HashNode

   257 gethashnode2(HashTable ht, char *nam)

   258 {

   259     unsigned hashval;

   260     HashNode hp;

   261 

   262     hashval = ht->hash(nam) % ht->hsize;

   263     for (hp = ht->nodes[hashval]; hp; hp = hp->next) {

   264 	if (ht->cmpnodes(hp->nam, nam) == 0)

   265 	    return hp;

   266     }

   267     return NULL;

   268 }

   269 

   270 /* Remove an entry from a hash table.           *

   271  * If successful, it removes the node from the  *

   272  * table and returns a pointer to it.  If there *

   273  * is no such node, then it returns NULL        */

   274 

   275 /**/

   276 mod_export HashNode

   277 removehashnode(HashTable ht, char *nam)

   278 {

   279     unsigned hashval;

   280     HashNode hp, hq;

   281 

   282     hashval = ht->hash(nam) % ht->hsize;

   283     hp = ht->nodes[hashval];

   284 

   285     /* if no nodes at this hash value, return NULL */

   286     if (!hp)

   287 	return NULL;

   288 

   289     /* else check if the key in the first one matches */

   290     if (ht->cmpnodes(hp->nam, nam) == 0) {

   291 	ht->nodes[hashval] = hp->next;

   292 	gotit:

   293 	ht->ct--;

   294 	if(ht->scan) {

   295 	    if(ht->scan->sorted) {

   296 		HashNode *tab = ht->scan->u.s.tab;

   297 		int i;

   298 		for(i = ht->scan->u.s.ct; i--; )

   299 		    if(tab[i] == hp)

   300 			tab[i] = NULL;

   301 	    } else if(ht->scan->u.u == hp)

   302 		ht->scan->u.u = hp->next;

   303 	}

   304 	return hp;

   305     }

   306 

   307     /* else run through the list and check the rest of the keys */

   308     hq = hp;

   309     hp = hp->next;

   310     for (; hp; hq = hp, hp = hp->next) {

   311 	if (ht->cmpnodes(hp->nam, nam) == 0) {

   312 	    hq->next = hp->next;

   313 	    goto gotit;

   314 	}

   315     }

   316 

   317     /* else it is not in the list, so return NULL */

   318     return NULL;

   319 }

   320 

   321 /* Disable a node in a hash table */

   322 

   323 /**/

   324 void

   325 disablehashnode(HashNode hn, UNUSED(int flags))

   326 {

   327     hn->flags |= DISABLED;

   328 }

   329 

   330 /* Enable a node in a hash table */

   331 

   332 /**/

   333 void

   334 enablehashnode(HashNode hn, UNUSED(int flags))

   335 {

   336     hn->flags &= ~DISABLED;

   337 }

   338 

   339 /* Compare two hash table entries by name */

   340 

   341 /**/

   342 static int

   343 hnamcmp(const void *ap, const void *bp)

   344 {

   345     HashNode a = *(HashNode *)ap;

   346     HashNode b = *(HashNode *)bp;

   347     return ztrcmp((unsigned char *) a->nam, (unsigned char *) b->nam);

   348 }

   349 

   350 /* Scan the nodes in a hash table and execute scanfunc on nodes based on

   351  * the flags that are set/unset.  scanflags is passed unchanged to

   352  * scanfunc (if executed).

   353  *

   354  * If sorted != 0, then sort entries of hash table before scanning.

   355  * If flags1 > 0, then execute scanfunc on a node only if at least one of

   356  *                these flags is set.

   357  * If flags2 > 0, then execute scanfunc on a node only if all of

   358  *                these flags are NOT set.

   359  * The conditions above for flags1/flags2 must both be true.

   360  *

   361  * It is safe to add, remove or replace hash table elements from within

   362  * the scanfunc.  Replaced elements will appear in the scan exactly once,

   363  * the new version if it was not scanned before the replacement was made.

   364  * Added elements might or might not appear in the scan.

   365  */

   366 

   367 /**/

   368 mod_export void

   369 scanhashtable(HashTable ht, int sorted, int flags1, int flags2, ScanFunc scanfunc, int scanflags)

   370 {

   371     struct scanstatus st;

   372 

   373     if (ht->scantab) {

   374 	ht->scantab(ht, scanfunc, scanflags);

   375 	return;

   376     }

   377     if (sorted) {

   378 	int i, ct = ht->ct;

   379 	VARARR(HashNode, hnsorttab, ct);

   380 	HashNode *htp, hn;

   381 

   382 	for (htp = hnsorttab, i = 0; i < ht->hsize; i++)

   383 	    for (hn = ht->nodes[i]; hn; hn = hn->next)

   384 		*htp++ = hn;

   385 	qsort((void *)hnsorttab, ct, sizeof(HashNode), hnamcmp);

   386 

   387 	st.sorted = 1;

   388 	st.u.s.tab = hnsorttab;

   389 	st.u.s.ct = ct;

   390 	ht->scan = &st;

   391 

   392 	for (htp = hnsorttab, i = 0; i < ct; i++, htp++)

   393 	    if (*htp && ((*htp)->flags & flags1) + !flags1 &&

   394 		!((*htp)->flags & flags2))

   395 		scanfunc(*htp, scanflags);

   396 

   397 	ht->scan = NULL;

   398     } else {

   399 	int i, hsize = ht->hsize;

   400 	HashNode *nodes = ht->nodes;

   401 

   402 	st.sorted = 0;

   403 	ht->scan = &st;

   404 

   405 	for (i = 0; i < hsize; i++)

   406 	    for (st.u.u = nodes[i]; st.u.u; ) {

   407 		HashNode hn = st.u.u;

   408 		st.u.u = st.u.u->next;

   409 		if ((hn->flags & flags1) + !flags1 && !(hn->flags & flags2))

   410 		    scanfunc(hn, scanflags);

   411 	    }

   412 

   413 	ht->scan = NULL;

   414     }

   415 }

   416 

   417 /* Scan all nodes in a hash table and executes scanfunc on the *

   418  * nodes which meet all the following criteria:                *

   419  * The hash key must match the glob pattern given by `com'.    *

   420  * If (flags1 > 0), then any flag in flags1 must be set.       *

   421  * If (flags2 > 0), then all flags in flags2 must NOT be set.  *

   422  *                                                             *

   423  * scanflags is passed unchanged to scanfunc (if executed).    *

   424  * The return value is the number of matches.                  */

   425 

   426 /**/

   427 int

   428 scanmatchtable(HashTable ht, Patprog pprog, int flags1, int flags2, ScanFunc scanfunc, int scanflags)

   429 {

   430     int i, hsize = ht->hsize;

   431     HashNode *nodes = ht->nodes;

   432     int match = 0;

   433     struct scanstatus st;

   434 

   435     st.sorted = 0;

   436     ht->scan = &st;

   437 

   438     for (i = 0; i < hsize; i++)

   439 	for (st.u.u = nodes[i]; st.u.u; ) {

   440 	    HashNode hn = st.u.u;

   441 	    st.u.u = st.u.u->next;

   442 	    if ((hn->flags & flags1) + !flags1 && !(hn->flags & flags2) &&

   443 		pattry(pprog, hn->nam)) {

   444 		scanfunc(hn, scanflags);

   445 		match++;

   446 	    }

   447 	}

   448 

   449     ht->scan = NULL;

   450 

   451     return match;

   452 }

   453 

   454 /* Expand hash tables when they get too many entries. *

   455  * The new size is 4 times the previous size.         */

   456 

   457 /**/

   458 static void

   459 expandhashtable(HashTable ht)

   460 {

   461     struct hashnode **onodes, **ha, *hn, *hp;

   462     int i, osize;

   463 

   464     osize = ht->hsize;

   465     onodes = ht->nodes;

   466 

   467     ht->hsize = osize * 4;

   468     ht->nodes = (HashNode *) zshcalloc(ht->hsize * sizeof(HashNode));

   469     ht->ct = 0;

   470 

   471     /* scan through the old list of nodes, and *

   472      * rehash them into the new list of nodes  */

   473     for (i = 0, ha = onodes; i < osize; i++, ha++) {

   474 	for (hn = *ha; hn;) {

   475 	    hp = hn->next;

   476 	    ht->addnode(ht, hn->nam, hn);

   477 	    hn = hp;

   478 	}

   479     }

   480     zfree(onodes, osize * sizeof(HashNode));

   481 }

   482 

   483 /* Empty the hash table and resize it if necessary */

   484 

   485 /**/

   486 static void

   487 resizehashtable(HashTable ht, int newsize)

   488 {

   489     struct hashnode **ha, *hn, *hp;

   490     int i;

   491 

   492     /* free all the hash nodes */

   493     ha = ht->nodes;

   494     for (i = 0; i < ht->hsize; i++, ha++) {

   495 	for (hn = *ha; hn;) {

   496 	    hp = hn->next;

   497 	    ht->freenode(hn);

   498 	    hn = hp;

   499 	}

   500     }

   501 

   502     /* If new size desired is different from current size, *

   503      * we free it and allocate a new nodes array.          */

   504     if (ht->hsize != newsize) {

   505 	zfree(ht->nodes, ht->hsize * sizeof(HashNode));

   506 	ht->nodes = (HashNode *) zshcalloc(newsize * sizeof(HashNode));

   507 	ht->hsize = newsize;

   508     } else {

   509 	/* else we just re-zero the current nodes array */

   510 	memset(ht->nodes, 0, newsize * sizeof(HashNode));

   511     }

   512 

   513     ht->ct = 0;

   514 }

   515 

   516 /* Generic method to empty a hash table */

   517 

   518 /**/

   519 mod_export void

   520 emptyhashtable(HashTable ht)

   521 {

   522     resizehashtable(ht, ht->hsize);

   523 }

   524 

   525 /**/

   526 #ifdef ZSH_HASH_DEBUG

   527 

   528 /* Print info about hash table */

   529 

   530 #define MAXDEPTH 7

   531 

   532 /**/

   533 static void

   534 printhashtabinfo(HashTable ht)

   535 {

   536     HashNode hn;

   537     int chainlen[MAXDEPTH + 1];

   538     int i, tmpcount, total;

   539 

   540     printf("name of table   : %s\n",   ht->tablename);

   541     printf("size of nodes[] : %d\n",   ht->hsize);

   542     printf("number of nodes : %d\n\n", ht->ct);

   543 

   544     memset(chainlen, 0, sizeof(chainlen));

   545 

   546     /* count the number of nodes just to be sure */

   547     total = 0;

   548     for (i = 0; i < ht->hsize; i++) {

   549 	tmpcount = 0;

   550 	for (hn = ht->nodes[i]; hn; hn = hn->next)

   551 	    tmpcount++;

   552 	if (tmpcount >= MAXDEPTH)

   553 	    chainlen[MAXDEPTH]++;

   554 	else

   555 	    chainlen[tmpcount]++;

   556 	total += tmpcount;

   557     }

   558 

   559     for (i = 0; i < MAXDEPTH; i++)

   560 	printf("number of hash values with chain of length %d  : %4d\n", i, chainlen[i]);

   561     printf("number of hash values with chain of length %d+ : %4d\n", MAXDEPTH, chainlen[MAXDEPTH]);

   562     printf("total number of nodes                         : %4d\n", total);

   563 }

   564 

   565 /**/

   566 int

   567 bin_hashinfo(char *nam, char **args, Options ops, int func)

   568 {

   569     HashTable ht;

   570 

   571     printf("----------------------------------------------------\n");

   572     queue_signals();

   573     for(ht = firstht; ht; ht = ht->next) {

   574 	ht->printinfo(ht);

   575 	printf("----------------------------------------------------\n");

   576     }

   577     unqueue_signals();

   578     return 0;

   579 }

   580 

   581 /**/

   582 #endif /* ZSH_HASH_DEBUG */

   583 

   584 /********************************/

   585 /* Command Hash Table Functions */

   586 /********************************/

   587 

   588 /* hash table containing external commands */

   589  

   590 /**/

   591 mod_export HashTable cmdnamtab;

   592  

   593 /* how far we've hashed the PATH so far */

   594  

   595 /**/

   596 mod_export char **pathchecked;

   597  

   598 /* Create a new command hash table */

   599  

   600 /**/

   601 void

   602 createcmdnamtable(void)

   603 {

   604     cmdnamtab = newhashtable(201, "cmdnamtab", NULL);

   605 

   606     cmdnamtab->hash        = hasher;

   607     cmdnamtab->emptytable  = emptycmdnamtable;

   608     cmdnamtab->filltable   = fillcmdnamtable;

   609     cmdnamtab->cmpnodes    = strcmp;

   610     cmdnamtab->addnode     = addhashnode;

   611     cmdnamtab->getnode     = gethashnode2;

   612     cmdnamtab->getnode2    = gethashnode2;

   613     cmdnamtab->removenode  = removehashnode;

   614     cmdnamtab->disablenode = NULL;

   615     cmdnamtab->enablenode  = NULL;

   616     cmdnamtab->freenode    = freecmdnamnode;

   617     cmdnamtab->printnode   = printcmdnamnode;

   618 

   619     pathchecked = path;

   620 }

   621 

   622 /**/

   623 static void

   624 emptycmdnamtable(HashTable ht)

   625 {

   626     emptyhashtable(ht);

   627     pathchecked = path;

   628 }

   629 

   630 /* Add all commands in a given directory *

   631  * to the command hashtable.             */

   632 

   633 /**/

   634 void

   635 hashdir(char **dirp)

   636 {

   637     Cmdnam cn;

   638     DIR *dir;

   639     char *fn;

   640 #if defined(_WIN32) || defined(__CYGWIN__)

   641     char *exe;

   642 #endif /* _WIN32 || _CYGWIN__ */

   643 

   644     if (isrelative(*dirp) || !(dir = opendir(unmeta(*dirp))))

   645 	return;

   646 

   647     while ((fn = zreaddir(dir, 1))) {

   648 	if (!cmdnamtab->getnode(cmdnamtab, fn)) {

   649 	    cn = (Cmdnam) zshcalloc(sizeof *cn);

   650 	    cn->flags = 0;

   651 	    cn->u.name = dirp;

   652 	    cmdnamtab->addnode(cmdnamtab, ztrdup(fn), cn);

   653 	}

   654 #if defined(_WIN32) || defined(__CYGWIN__)

   655 	/* Hash foo.exe as foo, since when no real foo exists, foo.exe

   656 	   will get executed by DOS automatically.  This quiets

   657 	   spurious corrections when CORRECT or CORRECT_ALL is set. */

   658 	if ((exe = strrchr(fn, '.')) &&

   659 	    (exe[1] == 'E' || exe[1] == 'e') &&

   660 	    (exe[2] == 'X' || exe[2] == 'x') &&

   661 	    (exe[3] == 'E' || exe[3] == 'e') && exe[4] == 0) {

   662 	    *exe = 0;

   663 	    if (!cmdnamtab->getnode(cmdnamtab, fn)) {

   664 		cn = (Cmdnam) zshcalloc(sizeof *cn);

   665 		cn->flags = 0;

   666 		cn->u.name = dirp;

   667 		cmdnamtab->addnode(cmdnamtab, ztrdup(fn), cn);

   668 	    }

   669 	}

   670 #endif /* _WIN32 || __CYGWIN__ */

   671     }

   672     closedir(dir);

   673 }

   674 

   675 /* Go through user's PATH and add everything to *

   676  * the command hashtable.                       */

   677 

   678 /**/

   679 static void

   680 fillcmdnamtable(UNUSED(HashTable ht))

   681 {

   682     char **pq;

   683  

   684     for (pq = pathchecked; *pq; pq++)

   685 	hashdir(pq);

   686 

   687     pathchecked = pq;

   688 }

   689 

   690 /**/

   691 static void

   692 freecmdnamnode(HashNode hn)

   693 {

   694     Cmdnam cn = (Cmdnam) hn;

   695  

   696     zsfree(cn->nam);

   697     if (cn->flags & HASHED)

   698 	zsfree(cn->u.cmd);

   699  

   700     zfree(cn, sizeof(struct cmdnam));

   701 }

   702 

   703 /* Print an element of the cmdnamtab hash table (external command) */

   704  

   705 /**/

   706 static void

   707 printcmdnamnode(HashNode hn, int printflags)

   708 {

   709     Cmdnam cn = (Cmdnam) hn;

   710 

   711     if (printflags & PRINT_WHENCE_WORD) {

   712 	printf("%s: %s\n", cn->nam, (cn->flags & HASHED) ? 

   713 	       "hashed" : "command");

   714 	return;

   715     }

   716 

   717     if ((printflags & PRINT_WHENCE_CSH) || (printflags & PRINT_WHENCE_SIMPLE)) {

   718 	if (cn->flags & HASHED) {

   719 	    zputs(cn->u.cmd, stdout);

   720 	    putchar('\n');

   721 	} else {

   722 	    zputs(*(cn->u.name), stdout);

   723 	    putchar('/');

   724 	    zputs(cn->nam, stdout);

   725 	    putchar('\n');

   726 	}

   727 	return;

   728     }

   729 

   730     if (printflags & PRINT_WHENCE_VERBOSE) {

   731 	if (cn->flags & HASHED) {

   732 	    nicezputs(cn->nam, stdout);

   733 	    printf(" is hashed to ");

   734 	    nicezputs(cn->u.cmd, stdout);

   735 	    putchar('\n');

   736 	} else {

   737 	    nicezputs(cn->nam, stdout);

   738 	    printf(" is ");

   739 	    nicezputs(*(cn->u.name), stdout);

   740 	    putchar('/');

   741 	    nicezputs(cn->nam, stdout);

   742 	    putchar('\n');

   743 	}

   744 	return;

   745     }

   746 

   747     if (printflags & PRINT_LIST) {

   748 	printf("hash ");

   749 

   750 	if(cn->nam[0] == '-')

   751 	    printf("-- ");

   752     }

   753 

   754     if (cn->flags & HASHED) {

   755 	quotedzputs(cn->nam, stdout);

   756 	putchar('=');

   757 	quotedzputs(cn->u.cmd, stdout);

   758 	putchar('\n');

   759     } else {

   760 	quotedzputs(cn->nam, stdout);

   761 	putchar('=');

   762 	quotedzputs(*(cn->u.name), stdout);

   763 	putchar('/');

   764 	quotedzputs(cn->nam, stdout);

   765 	putchar('\n');

   766     }

   767 }

   768 

   769 /***************************************/

   770 /* Shell Function Hash Table Functions */

   771 /***************************************/

   772 

   773 /* hash table containing the shell functions */

   774 

   775 /**/

   776 mod_export HashTable shfunctab;

   777 

   778 /**/

   779 void

   780 createshfunctable(void)

   781 {

   782     shfunctab = newhashtable(7, "shfunctab", NULL);

   783 

   784     shfunctab->hash        = hasher;

   785     shfunctab->emptytable  = NULL;

   786     shfunctab->filltable   = NULL;

   787     shfunctab->cmpnodes    = strcmp;

   788     shfunctab->addnode     = addhashnode;

   789     shfunctab->getnode     = gethashnode;

   790     shfunctab->getnode2    = gethashnode2;

   791     shfunctab->removenode  = removeshfuncnode;

   792     shfunctab->disablenode = disableshfuncnode;

   793     shfunctab->enablenode  = enableshfuncnode;

   794     shfunctab->freenode    = freeshfuncnode;

   795     shfunctab->printnode   = printshfuncnode;

   796 }

   797 

   798 /* Remove an entry from the shell function hash table.   *

   799  * It checks if the function is a signal trap and if so, *

   800  * it will disable the trapping of that signal.          */

   801 

   802 /**/

   803 static HashNode

   804 removeshfuncnode(UNUSED(HashTable ht), char *nam)

   805 {

   806     HashNode hn;

   807     int signum;

   808 

   809     if (!strncmp(nam, "TRAP", 4) && (signum = getsignum(nam + 4)) != -1)

   810 	hn = removetrap(signum);

   811     else

   812 	hn = removehashnode(shfunctab, nam);

   813 

   814     return hn;

   815 }

   816 

   817 /* Disable an entry in the shell function hash table.    *

   818  * It checks if the function is a signal trap and if so, *

   819  * it will disable the trapping of that signal.          */

   820 

   821 /**/

   822 static void

   823 disableshfuncnode(HashNode hn, UNUSED(int flags))

   824 {

   825     hn->flags |= DISABLED;

   826     if (!strncmp(hn->nam, "TRAP", 4)) {

   827 	int signum = getsignum(hn->nam + 4);

   828 	sigtrapped[signum] &= ~ZSIG_FUNC;

   829 	sigfuncs[signum] = NULL;

   830 	unsettrap(signum);

   831     }

   832 }

   833 

   834 /* Re-enable an entry in the shell function hash table.  *

   835  * It checks if the function is a signal trap and if so, *

   836  * it will re-enable the trapping of that signal.        */

   837 

   838 /**/

   839 static void

   840 enableshfuncnode(HashNode hn, UNUSED(int flags))

   841 {

   842     Shfunc shf = (Shfunc) hn;

   843 

   844     shf->flags &= ~DISABLED;

   845     if (!strncmp(shf->nam, "TRAP", 4)) {

   846 	int signum = getsignum(shf->nam + 4);

   847 	if (signum != -1) {

   848 	    settrap(signum, shf->funcdef);

   849 	    sigtrapped[signum] |= ZSIG_FUNC;

   850 	}

   851     }

   852 }

   853 

   854 /**/

   855 static void

   856 freeshfuncnode(HashNode hn)

   857 {

   858     Shfunc shf = (Shfunc) hn;

   859 

   860     zsfree(shf->nam);

   861     if (shf->funcdef)

   862 	freeeprog(shf->funcdef);

   863     zfree(shf, sizeof(struct shfunc));

   864 }

   865 

   866 /* Print a shell function */

   867  

   868 /**/

   869 static void

   870 printshfuncnode(HashNode hn, int printflags)

   871 {

   872     Shfunc f = (Shfunc) hn;

   873     char *t = 0;

   874  

   875     if ((printflags & PRINT_NAMEONLY) ||

   876 	((printflags & PRINT_WHENCE_SIMPLE) &&

   877 	!(printflags & PRINT_WHENCE_FUNCDEF))) {

   878 	zputs(f->nam, stdout);

   879 	putchar('\n');

   880 	return;

   881     }

   882  

   883     if ((printflags & (PRINT_WHENCE_VERBOSE|PRINT_WHENCE_WORD)) &&

   884 	!(printflags & PRINT_WHENCE_FUNCDEF)) {

   885 	nicezputs(f->nam, stdout);

   886 	printf((printflags & PRINT_WHENCE_WORD) ? ": function\n" :

   887 	       " is a shell function\n");

   888 	return;

   889     }

   890  

   891     quotedzputs(f->nam, stdout);

   892     if (f->funcdef || f->flags & PM_UNDEFINED) {

   893 	printf(" () {\n\t");

   894 	if (f->flags & PM_UNDEFINED)

   895 	    printf("%c undefined\n\t", hashchar);

   896 	else

   897 	    t = getpermtext(f->funcdef, NULL);

   898 	if (f->flags & PM_TAGGED)

   899 	    printf("%c traced\n\t", hashchar);

   900 	if (!t) {

   901 	    char *fopt = "Utkz";

   902 	    int flgs[] = {

   903 		PM_UNALIASED, PM_TAGGED, PM_KSHSTORED, PM_ZSHSTORED, 0

   904 	    };

   905 	    int fl;;

   906 

   907 	    zputs("builtin autoload -X", stdout);

   908 	    for (fl=0;fopt[fl];fl++)

   909 		if (f->flags & flgs[fl]) putchar(fopt[fl]);

   910 	} else {

   911 	    zputs(t, stdout);

   912 	    zsfree(t);

   913 	    if (f->funcdef->flags & EF_RUN) {

   914 		printf("\n\t");

   915 		quotedzputs(f->nam, stdout);

   916 		printf(" \"$@\"");

   917 	    }

   918 	}   

   919 	printf("\n}\n");

   920     } else {

   921 	printf(" () { }\n");

   922     }

   923 }

   924 

   925 /**************************************/

   926 /* Reserved Word Hash Table Functions */

   927 /**************************************/

   928 

   929 /* Nodes for reserved word hash table */

   930 

   931 static struct reswd reswds[] = {

   932     {NULL, "!", 0, BANG},

   933     {NULL, "[[", 0, DINBRACK},

   934     {NULL, "{", 0, INBRACE},

   935     {NULL, "}", 0, OUTBRACE},

   936     {NULL, "case", 0, CASE},

   937     {NULL, "coproc", 0, COPROC},

   938     {NULL, "do", 0, DOLOOP},

   939     {NULL, "done", 0, DONE},

   940     {NULL, "elif", 0, ELIF},

   941     {NULL, "else", 0, ELSE},

   942     {NULL, "end", 0, ZEND},

   943     {NULL, "esac", 0, ESAC},

   944     {NULL, "fi", 0, FI},

   945     {NULL, "for", 0, FOR},

   946     {NULL, "foreach", 0, FOREACH},

   947     {NULL, "function", 0, FUNC},

   948     {NULL, "if", 0, IF},

   949     {NULL, "nocorrect", 0, NOCORRECT},

   950     {NULL, "repeat", 0, REPEAT},

   951     {NULL, "select", 0, SELECT},

   952     {NULL, "then", 0, THEN},

   953     {NULL, "time", 0, TIME},

   954     {NULL, "until", 0, UNTIL},

   955     {NULL, "while", 0, WHILE},

   956     {NULL, NULL, 0, 0}

   957 };

   958 

   959 /* hash table containing the reserved words */

   960 

   961 /**/

   962 mod_export HashTable reswdtab;

   963 

   964 /* Build the hash table containing zsh's reserved words. */

   965 

   966 /**/

   967 void

   968 createreswdtable(void)

   969 {

   970     Reswd rw;

   971 

   972     reswdtab = newhashtable(23, "reswdtab", NULL);

   973 

   974     reswdtab->hash        = hasher;

   975     reswdtab->emptytable  = NULL;

   976     reswdtab->filltable   = NULL;

   977     reswdtab->cmpnodes    = strcmp;

   978     reswdtab->addnode     = addhashnode;

   979     reswdtab->getnode     = gethashnode;

   980     reswdtab->getnode2    = gethashnode2;

   981     reswdtab->removenode  = NULL;

   982     reswdtab->disablenode = disablehashnode;

   983     reswdtab->enablenode  = enablehashnode;

   984     reswdtab->freenode    = NULL;

   985     reswdtab->printnode   = printreswdnode;

   986 

   987     for (rw = reswds; rw->nam; rw++)

   988 	reswdtab->addnode(reswdtab, rw->nam, rw);

   989 }

   990 

   991 /* Print a reserved word */

   992 

   993 /**/

   994 static void

   995 printreswdnode(HashNode hn, int printflags)

   996 {

   997     Reswd rw = (Reswd) hn;

   998 

   999     if (printflags & PRINT_WHENCE_WORD) {

  1000 	printf("%s: reserved\n", rw->nam);

  1001 	return;

  1002     }

  1003 

  1004     if (printflags & PRINT_WHENCE_CSH) {

  1005 	printf("%s: shell reserved word\n", rw->nam);

  1006 	return;

  1007     }

  1008 

  1009     if (printflags & PRINT_WHENCE_VERBOSE) {

  1010 	printf("%s is a reserved word\n", rw->nam);

  1011 	return;

  1012     }

  1013 

  1014     /* default is name only */

  1015     printf("%s\n", rw->nam);

  1016 }

  1017 

  1018 /********************************/

  1019 /* Aliases Hash Table Functions */

  1020 /********************************/

  1021 

  1022 /* hash table containing the aliases */

  1023  

  1024 /**/

  1025 mod_export HashTable aliastab;

  1026  

  1027 /* has table containing suffix aliases */

  1028 

  1029 /**/

  1030 mod_export HashTable sufaliastab;

  1031  

  1032 /* Create new hash tables for aliases */

  1033 

  1034 /**/

  1035 void

  1036 createaliastable(HashTable ht)

  1037 {

  1038     ht->hash        = hasher;

  1039     ht->emptytable  = NULL;

  1040     ht->filltable   = NULL;

  1041     ht->cmpnodes    = strcmp;

  1042     ht->addnode     = addhashnode;

  1043     ht->getnode     = gethashnode;

  1044     ht->getnode2    = gethashnode2;

  1045     ht->removenode  = removehashnode;

  1046     ht->disablenode = disablehashnode;

  1047     ht->enablenode  = enablehashnode;

  1048     ht->freenode    = freealiasnode;

  1049     ht->printnode   = printaliasnode;

  1050 }

  1051 

  1052 /**/

  1053 void

  1054 createaliastables(void)

  1055 {

  1056     /* Table for regular and global aliases */

  1057 

  1058     aliastab = newhashtable(23, "aliastab", NULL);

  1059 

  1060     createaliastable(aliastab);

  1061 

  1062     /* add the default aliases */

  1063     aliastab->addnode(aliastab, ztrdup("run-help"), createaliasnode(ztrdup("man"), 0));

  1064     aliastab->addnode(aliastab, ztrdup("which-command"), createaliasnode(ztrdup("whence"), 0));

  1065 

  1066 

  1067     /* Table for suffix aliases --- make this smaller */

  1068 

  1069     sufaliastab = newhashtable(11, "sufaliastab", NULL);

  1070 

  1071     createaliastable(sufaliastab);

  1072 }

  1073 

  1074 /* Create a new alias node */

  1075 

  1076 /**/

  1077 mod_export Alias

  1078 createaliasnode(char *txt, int flags)

  1079 {

  1080     Alias al;

  1081 

  1082     al = (Alias) zshcalloc(sizeof *al);

  1083     al->flags = flags;

  1084     al->text = txt;

  1085     al->inuse = 0;

  1086     return al;

  1087 }

  1088 

  1089 /**/

  1090 static void

  1091 freealiasnode(HashNode hn)

  1092 {

  1093     Alias al = (Alias) hn;

  1094  

  1095     zsfree(al->nam);

  1096     zsfree(al->text);

  1097     zfree(al, sizeof(struct alias));

  1098 }

  1099 

  1100 /* Print an alias */

  1101 

  1102 /**/

  1103 static void

  1104 printaliasnode(HashNode hn, int printflags)

  1105 {

  1106     Alias a = (Alias) hn;

  1107 

  1108     if (printflags & PRINT_NAMEONLY) {

  1109 	zputs(a->nam, stdout);

  1110 	putchar('\n');

  1111 	return;

  1112     }

  1113 

  1114     if (printflags & PRINT_WHENCE_WORD) {

  1115 	printf("%s: alias\n", a->nam);

  1116 	return;

  1117     }

  1118 

  1119     if (printflags & PRINT_WHENCE_SIMPLE) {

  1120 	zputs(a->text, stdout);

  1121 	putchar('\n');

  1122 	return;

  1123     }

  1124 

  1125     if (printflags & PRINT_WHENCE_CSH) {

  1126 	nicezputs(a->nam, stdout);

  1127 	printf(": ");

  1128 	if (a->flags & ALIAS_SUFFIX)

  1129 	    printf("suffix ");

  1130 	else if (a->flags & ALIAS_GLOBAL)

  1131 	    printf("globally ");

  1132 	printf ("aliased to ");

  1133 	nicezputs(a->text, stdout);

  1134 	putchar('\n');