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