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
46 typedef 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
58 struct 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
74 static HashTable firstht, lastht;
75 #endif /* ZSH_HASH_DEBUG */
76
77 /* Generic hash function */
78
79 /**/
80 mod_export unsigned
hasher(const char * str)81 hasher(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 /**/
94 mod_export HashTable
newhashtable(int size,UNUSED (char const * name),UNUSED (PrintTableStats printinfo))95 newhashtable(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 /**/
123 mod_export void
deletehashtable(HashTable ht)124 deletehashtable(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 /**/
151 mod_export void
addhashnode(HashTable ht,char * nam,void * nodeptr)152 addhashnode(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 /**/
162 HashNode
addhashnode2(HashTable ht,char * nam,void * nodeptr)163 addhashnode2(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 /**/
225 mod_export HashNode
gethashnode(HashTable ht,const char * nam)226 gethashnode(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 /**/
249 mod_export HashNode
gethashnode2(HashTable ht,const char * nam)250 gethashnode2(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 /**/
269 mod_export HashNode
removehashnode(HashTable ht,const char * nam)270 removehashnode(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 /**/
317 void
disablehashnode(HashNode hn,UNUSED (int flags))318 disablehashnode(HashNode hn, UNUSED(int flags))
319 {
320 hn->flags |= DISABLED;
321 }
322
323 /* Enable a node in a hash table */
324
325 /**/
326 void
enablehashnode(HashNode hn,UNUSED (int flags))327 enablehashnode(HashNode hn, UNUSED(int flags))
328 {
329 hn->flags &= ~DISABLED;
330 }
331
332 /* Compare two hash table entries by name */
333
334 /**/
335 static int
hnamcmp(const void * ap,const void * bp)336 hnamcmp(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 /**/
367 mod_export int
scanmatchtable(HashTable ht,Patprog pprog,int sorted,int flags1,int flags2,ScanFunc scanfunc,int scanflags)368 scanmatchtable(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 /**/
440 mod_export int
scanhashtable(HashTable ht,int sorted,int flags1,int flags2,ScanFunc scanfunc,int scanflags)441 scanhashtable(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 /**/
452 static void
expandhashtable(HashTable ht)453 expandhashtable(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 /**/
480 static void
resizehashtable(HashTable ht,int newsize)481 resizehashtable(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 /**/
513 mod_export void
emptyhashtable(HashTable ht)514 emptyhashtable(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 /**/
527 static void
printhashtabinfo(HashTable ht)528 printhashtabinfo(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 /**/
560 int
bin_hashinfo(UNUSED (char * nam),UNUSED (char ** args),UNUSED (Options ops),UNUSED (int func))561 bin_hashinfo(UNUSED(char *nam), UNUSED(char **args), UNUSED(Options ops), UNUSED(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 /**/
585 mod_export HashTable cmdnamtab;
586
587 /* how far we've hashed the PATH so far */
588
589 /**/
590 mod_export char **pathchecked;
591
592 /* Create a new command hash table */
593
594 /**/
595 void
createcmdnamtable(void)596 createcmdnamtable(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 /**/
617 static void
emptycmdnamtable(HashTable ht)618 emptycmdnamtable(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 /**/
628 void
hashdir(char ** dirp)629 hashdir(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 /**/
706 static void
fillcmdnamtable(UNUSED (HashTable ht))707 fillcmdnamtable(UNUSED(HashTable ht))
708 {
709 char **pq;
710
711 for (pq = pathchecked; *pq; pq++)
712 hashdir(pq);
713
714 pathchecked = pq;
715 }
716
717 /**/
718 static void
freecmdnamnode(HashNode hn)719 freecmdnamnode(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 /**/
733 static void
printcmdnamnode(HashNode hn,int printflags)734 printcmdnamnode(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 /**/
803 mod_export HashTable shfunctab;
804
805 /**/
806 void
createshfunctable(void)807 createshfunctable(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 /**/
830 static HashNode
removeshfuncnode(UNUSED (HashTable ht),const char * nam)831 removeshfuncnode(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 /**/
849 static void
disableshfuncnode(HashNode hn,UNUSED (int flags))850 disableshfuncnode(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 /**/
867 static void
enableshfuncnode(HashNode hn,UNUSED (int flags))868 enableshfuncnode(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 /**/
882 static void
freeshfuncnode(HashNode hn)883 freeshfuncnode(HashNode hn)
884 {
885 Shfunc shf = (Shfunc) hn;
886
887 zsfree(shf->node.nam);
888 if (shf->funcdef)
889 freeeprog(shf->funcdef);
890 if (shf->redir)
891 freeeprog(shf->redir);
892 dircache_set(&shf->filename, NULL);
893 if (shf->sticky) {
894 if (shf->sticky->n_on_opts)
895 zfree(shf->sticky->on_opts,
896 shf->sticky->n_on_opts * sizeof(*shf->sticky->on_opts));
897 if (shf->sticky->n_off_opts)
898 zfree(shf->sticky->off_opts,
899 shf->sticky->n_off_opts * sizeof(*shf->sticky->off_opts));
900 zfree(shf->sticky, sizeof(*shf->sticky));
901 }
902 zfree(shf, sizeof(struct shfunc));
903 }
904
905 /* Print a shell function */
906
907 /**/
908 static void
printshfuncnode(HashNode hn,int printflags)909 printshfuncnode(HashNode hn, int printflags)
910 {
911 Shfunc f = (Shfunc) hn;
912 char *t = 0;
913
914 if ((printflags & PRINT_NAMEONLY) ||
915 ((printflags & PRINT_WHENCE_SIMPLE) &&
916 !(printflags & PRINT_WHENCE_FUNCDEF))) {
917 zputs(f->node.nam, stdout);
918 putchar('\n');
919 return;
920 }
921
922 if ((printflags & (PRINT_WHENCE_VERBOSE|PRINT_WHENCE_WORD)) &&
923 !(printflags & PRINT_WHENCE_FUNCDEF)) {
924 nicezputs(f->node.nam, stdout);
925 printf((printflags & PRINT_WHENCE_WORD) ? ": function" :
926 (f->node.flags & PM_UNDEFINED) ?
927 " is an autoload shell function" :
928 " is a shell function");
929 if ((printflags & PRINT_WHENCE_VERBOSE) && f->filename) {
930 printf(" from ");
931 quotedzputs(f->filename, stdout);
932 if (f->node.flags & PM_LOADDIR) {
933 printf("/");
934 quotedzputs(f->node.nam, stdout);
935 }
936 }
937 putchar('\n');
938 return;
939 }
940
941 quotedzputs(f->node.nam, stdout);
942 if (f->funcdef || f->node.flags & PM_UNDEFINED) {
943 printf(" () {\n");
944 zoutputtab(stdout);
945 if (f->node.flags & PM_UNDEFINED) {
946 printf("%c undefined\n", hashchar);
947 zoutputtab(stdout);
948 } else
949 t = getpermtext(f->funcdef, NULL, 1);
950 if (f->node.flags & (PM_TAGGED|PM_TAGGED_LOCAL)) {
951 printf("%c traced\n", hashchar);
952 zoutputtab(stdout);
953 }
954 if (!t) {
955 char *fopt = "UtTkzc";
956 int flgs[] = {
957 PM_UNALIASED, PM_TAGGED, PM_TAGGED_LOCAL,
958 PM_KSHSTORED, PM_ZSHSTORED, PM_CUR_FPATH, 0
959 };
960 int fl;;
961
962 zputs("builtin autoload -X", stdout);
963 for (fl=0;fopt[fl];fl++)
964 if (f->node.flags & flgs[fl]) putchar(fopt[fl]);
965 if (f->filename && (f->node.flags & PM_LOADDIR)) {
966 putchar(' ');
967 zputs(f->filename, stdout);
968 }
969 } else {
970 zputs(t, stdout);
971 zsfree(t);
972 if (f->funcdef->flags & EF_RUN) {
973 printf("\n");
974 zoutputtab(stdout);
975 quotedzputs(f->node.nam, stdout);
976 printf(" \"$@\"");
977 }
978 }
979 printf("\n}");
980 } else {
981 printf(" () { }");
982 }
983 if (f->redir) {
984 t = getpermtext(f->redir, NULL, 1);
985 if (t) {
986 zputs(t, stdout);
987 zsfree(t);
988 }
989 }
990
991 putchar('\n');
992 }
993
994 /*
995 * Wrap scanmatchtable for shell functions with optional
996 * expansion of leading tabs.
997 * expand = 0 is standard: use hard tabs.
998 * expand > 0 uses that many spaces.
999 * expand < 0 uses no indentation.
1000 *
1001 * Note this function and the following two are called with
1002 * interrupts queued, so saving and restoring text_expand_tabs
1003 * is safe.
1004 */
1005
1006 /**/
1007 mod_export int
scanmatchshfunc(Patprog pprog,int sorted,int flags1,int flags2,ScanFunc scanfunc,int scanflags,int expand)1008 scanmatchshfunc(Patprog pprog, int sorted, int flags1, int flags2,
1009 ScanFunc scanfunc, int scanflags, int expand)
1010 {
1011 int ret, save_expand;
1012
1013 save_expand = text_expand_tabs;
1014 text_expand_tabs = expand;
1015 ret = scanmatchtable(shfunctab, pprog, sorted, flags1, flags2,
1016 scanfunc, scanflags);
1017 text_expand_tabs = save_expand;
1018
1019 return ret;
1020 }
1021
1022 /* Wrap scanhashtable to expand tabs for shell functions */
1023
1024 /**/
1025 mod_export int
scanshfunc(int sorted,int flags1,int flags2,ScanFunc scanfunc,int scanflags,int expand)1026 scanshfunc(int sorted, int flags1, int flags2,
1027 ScanFunc scanfunc, int scanflags, int expand)
1028 {
1029 return scanmatchshfunc(NULL, sorted, flags1, flags2,
1030 scanfunc, scanflags, expand);
1031 }
1032
1033 /* Wrap shfunctab->printnode to expand tabs */
1034
1035 /**/
1036 mod_export void
printshfuncexpand(HashNode hn,int printflags,int expand)1037 printshfuncexpand(HashNode hn, int printflags, int expand)
1038 {
1039 int save_expand;
1040
1041 save_expand = text_expand_tabs;
1042 text_expand_tabs = expand;
1043 shfunctab->printnode(hn, printflags);
1044 text_expand_tabs = save_expand;
1045 }
1046
1047 /*
1048 * Get a heap-duplicated name of the shell function, for
1049 * use in tracing.
1050 */
1051
1052 /**/
1053 mod_export char *
getshfuncfile(Shfunc shf)1054 getshfuncfile(Shfunc shf)
1055 {
1056 if (shf->node.flags & PM_LOADDIR) {
1057 return zhtricat(shf->filename, "/", shf->node.nam);
1058 } else if (shf->filename) {
1059 return dupstring(shf->filename);
1060 } else {
1061 return NULL;
1062 }
1063 }
1064
1065 /**************************************/
1066 /* Reserved Word Hash Table Functions */
1067 /**************************************/
1068
1069 /* Nodes for reserved word hash table */
1070
1071 static struct reswd reswds[] = {
1072 {{NULL, "!", 0}, BANG},
1073 {{NULL, "[[", 0}, DINBRACK},
1074 {{NULL, "{", 0}, INBRACE},
1075 {{NULL, "}", 0}, OUTBRACE},
1076 {{NULL, "case", 0}, CASE},
1077 {{NULL, "coproc", 0}, COPROC},
1078 {{NULL, "declare", 0}, TYPESET},
1079 {{NULL, "do", 0}, DOLOOP},
1080 {{NULL, "done", 0}, DONE},
1081 {{NULL, "elif", 0}, ELIF},
1082 {{NULL, "else", 0}, ELSE},
1083 {{NULL, "end", 0}, ZEND},
1084 {{NULL, "esac", 0}, ESAC},
1085 {{NULL, "export", 0}, TYPESET},
1086 {{NULL, "fi", 0}, FI},
1087 {{NULL, "float", 0}, TYPESET},
1088 {{NULL, "for", 0}, FOR},
1089 {{NULL, "foreach", 0}, FOREACH},
1090 {{NULL, "function", 0}, FUNC},
1091 {{NULL, "if", 0}, IF},
1092 {{NULL, "integer", 0}, TYPESET},
1093 {{NULL, "local", 0}, TYPESET},
1094 {{NULL, "nocorrect", 0}, NOCORRECT},
1095 {{NULL, "readonly", 0}, TYPESET},
1096 {{NULL, "repeat", 0}, REPEAT},
1097 {{NULL, "select", 0}, SELECT},
1098 {{NULL, "then", 0}, THEN},
1099 {{NULL, "time", 0}, TIME},
1100 {{NULL, "typeset", 0}, TYPESET},
1101 {{NULL, "until", 0}, UNTIL},
1102 {{NULL, "while", 0}, WHILE},
1103 {{NULL, NULL, 0}, 0}
1104 };
1105
1106 /* hash table containing the reserved words */
1107
1108 /**/
1109 mod_export HashTable reswdtab;
1110
1111 /* Build the hash table containing zsh's reserved words. */
1112
1113 /**/
1114 void
createreswdtable(void)1115 createreswdtable(void)
1116 {
1117 Reswd rw;
1118
1119 reswdtab = newhashtable(23, "reswdtab", NULL);
1120
1121 reswdtab->hash = hasher;
1122 reswdtab->emptytable = NULL;
1123 reswdtab->filltable = NULL;
1124 reswdtab->cmpnodes = strcmp;
1125 reswdtab->addnode = addhashnode;
1126 reswdtab->getnode = gethashnode;
1127 reswdtab->getnode2 = gethashnode2;
1128 reswdtab->removenode = NULL;
1129 reswdtab->disablenode = disablehashnode;
1130 reswdtab->enablenode = enablehashnode;
1131 reswdtab->freenode = NULL;
1132 reswdtab->printnode = printreswdnode;
1133
1134 for (rw = reswds; rw->node.nam; rw++)
1135 reswdtab->addnode(reswdtab, rw->node.nam, rw);
1136 }
1137
1138 /* Print a reserved word */
1139
1140 /**/
1141 static void
printreswdnode(HashNode hn,int printflags)1142 printreswdnode(HashNode hn, int printflags)
1143 {
1144 Reswd rw = (Reswd) hn;
1145
1146 if (printflags & PRINT_WHENCE_WORD) {
1147 printf("%s: reserved\n", rw->node.nam);
1148 return;
1149 }
1150
1151 if (printflags & PRINT_WHENCE_CSH) {
1152 printf("%s: shell reserved word\n", rw->node.nam);
1153 return;
1154 }
1155
1156 if (printflags & PRINT_WHENCE_VERBOSE) {
1157 printf("%s is a reserved word\n", rw->node.nam);
1158 return;
1159 }
1160
1161 /* default is name only */
1162 printf("%s\n", rw->node.nam);
1163 }
1164
1165 /********************************/
1166 /* Aliases Hash Table Functions */
1167 /********************************/
1168
1169 /* hash table containing the aliases */
1170
1171 /**/
1172 mod_export HashTable aliastab;
1173
1174 /* has table containing suffix aliases */
1175
1176 /**/
1177 mod_export HashTable sufaliastab;
1178
1179 /* Create new hash tables for aliases */
1180
1181 /**/
1182 void
createaliastable(HashTable ht)1183 createaliastable(HashTable ht)
1184 {
1185 ht->hash = hasher;
1186 ht->emptytable = NULL;
1187 ht->filltable = NULL;
1188 ht->cmpnodes = strcmp;
1189 ht->addnode = addhashnode;
1190 ht->getnode = gethashnode;
1191 ht->getnode2 = gethashnode2;
1192 ht->removenode = removehashnode;
1193 ht->disablenode = disablehashnode;
1194 ht->enablenode = enablehashnode;
1195 ht->freenode = freealiasnode;
1196 ht->printnode = printaliasnode;
1197 }
1198
1199 /**/
1200 void
createaliastables(void)1201 createaliastables(void)
1202 {
1203 /* Table for regular and global aliases */
1204
1205 aliastab = newhashtable(23, "aliastab", NULL);
1206
1207 createaliastable(aliastab);
1208
1209 /* add the default aliases */
1210 aliastab->addnode(aliastab, ztrdup("run-help"), createaliasnode(ztrdup("man"), 0));
1211 aliastab->addnode(aliastab, ztrdup("which-command"), createaliasnode(ztrdup("whence"), 0));
1212
1213
1214 /* Table for suffix aliases --- make this smaller */
1215
1216 sufaliastab = newhashtable(11, "sufaliastab", NULL);
1217
1218 createaliastable(sufaliastab);
1219 }
1220
1221 /* Create a new alias node */
1222
1223 /**/
1224 mod_export Alias
createaliasnode(char * txt,int flags)1225 createaliasnode(char *txt, int flags)
1226 {
1227 Alias al;
1228
1229 al = (Alias) zshcalloc(sizeof *al);
1230 al->node.flags = flags;
1231 al->text = txt;
1232 al->inuse = 0;
1233 return al;
1234 }
1235
1236 /**/
1237 static void
freealiasnode(HashNode hn)1238 freealiasnode(HashNode hn)
1239 {
1240 Alias al = (Alias) hn;
1241
1242 zsfree(al->node.nam);
1243 zsfree(al->text);
1244 zfree(al, sizeof(struct alias));
1245 }
1246
1247 /* Print an alias */
1248
1249 /**/
1250 static void
printaliasnode(HashNode hn,int printflags)1251 printaliasnode(HashNode hn, int printflags)
1252 {
1253 Alias a = (Alias) hn;
1254
1255 if (printflags & PRINT_NAMEONLY) {
1256 zputs(a->node.nam, stdout);
1257 putchar('\n');
1258 return;
1259 }
1260
1261 if (printflags & PRINT_WHENCE_WORD) {
1262 if (a->node.flags & ALIAS_SUFFIX)
1263 printf("%s: suffix alias\n", a->node.nam);
1264 else if (a->node.flags & ALIAS_GLOBAL)
1265 printf("%s: global alias\n", a->node.nam);
1266 else
1267 printf("%s: alias\n", a->node.nam);
1268 return;
1269 }
1270
1271 if (printflags & PRINT_WHENCE_SIMPLE) {
1272 zputs(a->text, stdout);
1273 putchar('\n');
1274 return;
1275 }
1276
1277 if (printflags & PRINT_WHENCE_CSH) {
1278 nicezputs(a->node.nam, stdout);
1279 printf(": ");
1280 if (a->node.flags & ALIAS_SUFFIX)
1281 printf("suffix ");
1282 else if (a->node.flags & ALIAS_GLOBAL)
1283 printf("globally ");
1284 printf ("aliased to ");
1285 nicezputs(a->text, stdout);
1286 putchar('\n');
1287 return;
1288 }
1289
1290 if (printflags & PRINT_WHENCE_VERBOSE) {
1291 nicezputs(a->node.nam, stdout);
1292 printf(" is a");
1293 if (a->node.flags & ALIAS_SUFFIX)
1294 printf(" suffix");
1295 else if (a->node.flags & ALIAS_GLOBAL)
1296 printf(" global");
1297 else
1298 printf("n");
1299 printf(" alias for ");
1300 nicezputs(a->text, stdout);
1301 putchar('\n');
1302 return;
1303 }
1304
1305 if (printflags & PRINT_LIST) {
1306 /* Fast fail on unrepresentable values. */
1307 if (strchr(a->node.nam, '=')) {
1308 zwarn("invalid alias '%s' encountered while printing aliases",
1309 a->node.nam);
1310 /* ### TODO: Return an error status to the C caller */
1311 return;
1312 }
1313
1314 /* Normal path. */
1315 printf("alias ");
1316 if (a->node.flags & ALIAS_SUFFIX)
1317 printf("-s ");
1318 else if (a->node.flags & ALIAS_GLOBAL)
1319 printf("-g ");
1320
1321 /* If an alias begins with `-' or `+', then we must output `-- '
1322 * first, so that it is not interpreted as an option. */
1323 if(a->node.nam[0] == '-' || a->node.nam[0] == '+')
1324 printf("-- ");
1325 }
1326
1327 quotedzputs(a->node.nam, stdout);
1328 putchar('=');
1329 quotedzputs(a->text, stdout);
1330
1331 putchar('\n');
1332 }
1333
1334 /*************************************/
1335 /* History Line Hash Table Functions */
1336 /*************************************/
1337
1338 /**/
1339 void
createhisttable(void)1340 createhisttable(void)
1341 {
1342 histtab = newhashtable(599, "histtab", NULL);
1343
1344 histtab->hash = histhasher;
1345 histtab->emptytable = emptyhisttable;
1346 histtab->filltable = NULL;
1347 histtab->cmpnodes = histstrcmp;
1348 histtab->addnode = addhistnode;
1349 histtab->getnode = gethashnode2;
1350 histtab->getnode2 = gethashnode2;
1351 histtab->removenode = removehashnode;
1352 histtab->disablenode = NULL;
1353 histtab->enablenode = NULL;
1354 histtab->freenode = freehistnode;
1355 histtab->printnode = NULL;
1356 }
1357
1358 /**/
1359 unsigned
histhasher(const char * str)1360 histhasher(const char *str)
1361 {
1362 unsigned hashval = 0;
1363
1364 while (inblank(*str)) str++;
1365
1366 while (*str) {
1367 if (inblank(*str)) {
1368 do str++; while (inblank(*str));
1369 if (*str)
1370 hashval += (hashval << 5) + ' ';
1371 }
1372 else
1373 hashval += (hashval << 5) + *(unsigned char *)str++;
1374 }
1375 return hashval;
1376 }
1377
1378 /**/
1379 void
emptyhisttable(HashTable ht)1380 emptyhisttable(HashTable ht)
1381 {
1382 emptyhashtable(ht);
1383 if (hist_ring)
1384 histremovedups();
1385 }
1386
1387 /* Compare two strings with normalized white-space */
1388
1389 /**/
1390 int
histstrcmp(const char * str1,const char * str2)1391 histstrcmp(const char *str1, const char *str2)
1392 {
1393 while (inblank(*str1)) str1++;
1394 while (inblank(*str2)) str2++;
1395 while (*str1 && *str2) {
1396 if (inblank(*str1)) {
1397 if (!inblank(*str2))
1398 break;
1399 do str1++; while (inblank(*str1));
1400 do str2++; while (inblank(*str2));
1401 }
1402 else {
1403 if (*str1 != *str2)
1404 break;
1405 str1++;
1406 str2++;
1407 }
1408 }
1409 return *str1 - *str2;
1410 }
1411
1412 /**/
1413 void
addhistnode(HashTable ht,char * nam,void * nodeptr)1414 addhistnode(HashTable ht, char *nam, void *nodeptr)
1415 {
1416 HashNode oldnode = addhashnode2(ht, nam, nodeptr);
1417 Histent he = (Histent)nodeptr;
1418 if (oldnode && oldnode != (HashNode)nodeptr) {
1419 if (he->node.flags & HIST_MAKEUNIQUE
1420 || (he->node.flags & HIST_FOREIGN && (Histent)oldnode == he->up)) {
1421 (void) addhashnode2(ht, oldnode->nam, oldnode); /* restore hash */
1422 he->node.flags |= HIST_DUP;
1423 he->node.flags &= ~HIST_MAKEUNIQUE;
1424 }
1425 else {
1426 oldnode->flags |= HIST_DUP;
1427 if (hist_ignore_all_dups)
1428 freehistnode(oldnode); /* Remove the old dup */
1429 }
1430 }
1431 else
1432 he->node.flags &= ~HIST_MAKEUNIQUE;
1433 }
1434
1435 /**/
1436 void
freehistnode(HashNode nodeptr)1437 freehistnode(HashNode nodeptr)
1438 {
1439 freehistdata((Histent)nodeptr, 1);
1440 zfree(nodeptr, sizeof (struct histent));
1441 }
1442
1443 /**/
1444 void
freehistdata(Histent he,int unlink)1445 freehistdata(Histent he, int unlink)
1446 {
1447 if (!he)
1448 return;
1449
1450 if (he == &curline)
1451 return;
1452
1453 if (!(he->node.flags & (HIST_DUP | HIST_TMPSTORE)))
1454 removehashnode(histtab, he->node.nam);
1455
1456 zsfree(he->node.nam);
1457 if (he->nwords)
1458 zfree(he->words, he->nwords*2*sizeof(short));
1459
1460 if (unlink) {
1461 if (!--histlinect)
1462 hist_ring = NULL;
1463 else {
1464 if (he == hist_ring)
1465 hist_ring = hist_ring->up;
1466 he->up->down = he->down;
1467 he->down->up = he->up;
1468 }
1469 }
1470 }
1471
1472
1473 /***********************************************************************
1474 * Directory name cache mechanism
1475 *
1476 * The idea of this is that there are various shell structures,
1477 * notably functions, that record the directories with which they
1478 * are associated. Rather than store the full string each time,
1479 * we store a pointer to the same location and count the references.
1480 * This is optimised so that retrieval is quick at the expense of
1481 * searching the list when setting up the structure, which is a much
1482 * rarer operation.
1483 *
1484 * There is nothing special about the fact that the strings are
1485 * directories, except for the assumptions for efficiency that many
1486 * structures will point to the same one, and that there are not too
1487 * many different directories associated with the shell.
1488 **********************************************************************/
1489
1490 struct dircache_entry
1491 {
1492 /* Name of directory in cache */
1493 char *name;
1494 /* Number of references to it */
1495 int refs;
1496 };
1497
1498 /*
1499 * dircache is the cache, of length dircache_size.
1500 * dircache_lastentry is the last entry used, an optimisation
1501 * for multiple references to the same directory, e.g
1502 * "autoload /blah/blah/\*".
1503 */
1504 static struct dircache_entry *dircache, *dircache_lastentry;
1505 static int dircache_size;
1506
1507 /*
1508 * Set *name to point to a cached version of value.
1509 * value is copied so may come from any source.
1510 *
1511 * If value is NULL, look for the existing value of *name (safe if this
1512 * too is NULL) and remove a reference to it from the cache. If it's
1513 * not found in the cache, it's assumed to be an allocated string and
1514 * freed --- this currently occurs for a shell function that's been
1515 * loaded as the filename is now a full path, not just a directory,
1516 * though we may one day optimise this to a cached directory plus a
1517 * name, too. Note --- the function does *not* otherwise check
1518 * if *name points to something already cached, so this is
1519 * necessary any time *name may already be in the cache.
1520 */
1521
1522 /**/
1523 mod_export void
dircache_set(char ** name,char * value)1524 dircache_set(char **name, char *value)
1525 {
1526 struct dircache_entry *dcptr, *dcnew;
1527
1528 if (!value) {
1529 if (!*name)
1530 return;
1531 if (!dircache_size) {
1532 zsfree(*name);
1533 *name = NULL;
1534 return;
1535 }
1536
1537 for (dcptr = dircache; dcptr < dircache + dircache_size; dcptr++)
1538 {
1539 /* Must be a pointer much, not a string match */
1540 if (*name == dcptr->name)
1541 {
1542 --dcptr->refs;
1543 if (!dcptr->refs) {
1544 ptrdiff_t ind = dcptr - dircache;
1545 zsfree(dcptr->name);
1546 --dircache_size;
1547
1548 if (!dircache_size) {
1549 zfree(dircache, sizeof(*dircache));
1550 dircache = NULL;
1551 dircache_lastentry = NULL;
1552 *name = NULL;
1553 return;
1554 }
1555 dcnew = (struct dircache_entry *)
1556 zalloc(dircache_size * sizeof(*dcnew));
1557 if (ind)
1558 memcpy(dcnew, dircache, ind * sizeof(*dcnew));
1559 if (ind < dircache_size)
1560 memcpy(dcnew + ind, dcptr + 1,
1561 (dircache_size - ind) * sizeof(*dcnew));
1562 zfree(dircache, (dircache_size+1)*sizeof(*dcnew));
1563 dircache = dcnew;
1564 dircache_lastentry = NULL;
1565 }
1566 *name = NULL;
1567 return;
1568 }
1569 }
1570 zsfree(*name);
1571 *name = NULL;
1572 } else {
1573 /*
1574 * As the function path has been resolved to a particular
1575 * location, we'll store it as an absolute path.
1576 */
1577 if (*value != '/') {
1578 value = zhtricat(metafy(zgetcwd(), -1, META_HEAPDUP),
1579 "/", value);
1580 value = xsymlink(value, 1);
1581 }
1582 /*
1583 * We'll maintain the cache at exactly the right size rather
1584 * than overallocating. The rationale here is that typically
1585 * we'll get a lot of functions in a small number of directories
1586 * so the complexity overhead of maintaining a separate count
1587 * isn't really matched by the efficiency gain.
1588 */
1589 if (dircache_lastentry &&
1590 !strcmp(value, dircache_lastentry->name)) {
1591 *name = dircache_lastentry->name;
1592 ++dircache_lastentry->refs;
1593 return;
1594 } else if (!dircache_size) {
1595 dircache_size = 1;
1596 dcptr = dircache =
1597 (struct dircache_entry *)zalloc(sizeof(*dircache));
1598 } else {
1599 for (dcptr = dircache; dcptr < dircache + dircache_size; dcptr++)
1600 {
1601 if (!strcmp(value, dcptr->name)) {
1602 *name = dcptr->name;
1603 ++dcptr->refs;
1604 return;
1605 }
1606 }
1607 ++dircache_size;
1608 dircache = (struct dircache_entry *)
1609 zrealloc(dircache, sizeof(*dircache) * dircache_size);
1610 dcptr = dircache + dircache_size - 1;
1611 }
1612 dcptr->name = ztrdup(value);
1613 *name = dcptr->name;
1614 dcptr->refs = 1;
1615 dircache_lastentry = dcptr;
1616 }
1617 }
1618