home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / z / zsh220.zip / zsh2.2 / src / table.c < prev    next >
C/C++ Source or Header  |  1992-05-07  |  7KB  |  350 lines
  1. /*
  2.  *
  3.  * table.c - linked lists and hash tables
  4.  *
  5.  * This file is part of zsh, the Z shell.
  6.  *
  7.  * This software is Copyright 1992 by Paul Falstad
  8.  *
  9.  * Permission is hereby granted to copy, reproduce, redistribute or otherwise
  10.  * use this software as long as: there is no monetary profit gained
  11.  * specifically from the use or reproduction of this software, it is not
  12.  * sold, rented, traded or otherwise marketed, and this copyright notice is
  13.  * included prominently in any copy made. 
  14.  *
  15.  * The author make no claims as to the fitness or correctness of this software
  16.  * for any use whatsoever, and it is provided as is. Any use of this software
  17.  * is at the user's own risk. 
  18.  *
  19.  */
  20.  
  21. #define TABLE_C
  22. #include "zsh.h"
  23.  
  24. /* get an empty linked list header */
  25.  
  26. Lklist newlist() /**/
  27. {
  28. Lklist list;
  29.  
  30.     list = (Lklist) alloc(sizeof *list);
  31.     list->first = 0;
  32.     list->last = (Lknode) list;
  33.     return list;
  34. }
  35.  
  36. /* get an empty hash table */
  37.  
  38. Hashtab newhtable(size) /**/
  39. int size;
  40. {
  41. Hashtab ret;
  42.  
  43.     ret = (Hashtab) zcalloc(sizeof *ret);
  44.     ret->hsize = size;
  45.     ret->nodes = (Hashnode*) zcalloc(size*sizeof(Hashnode));
  46.     return ret;
  47. }
  48.  
  49. /* Peter Weinberger's hash function */
  50.  
  51. int hasher(s) /**/
  52. char *s;
  53. {
  54. unsigned hash = 0,g;
  55.  
  56.     for (; *s; s++) {
  57.         hash = (hash << 4) + *s;
  58.         if (g = hash & 0xf0000000) {
  59.             hash ^= g;
  60.             hash ^= g >> 24;
  61.         }
  62.     }
  63.     return hash;
  64. }
  65.  
  66. /* add a node to a hash table */
  67.  
  68. void Addhnode(nam,dat,ht,freefunc,canfree) /**/
  69. char *nam;vptr dat;Hashtab ht;FFunc freefunc;int canfree;
  70. {
  71. int hval = hasher(nam) % ht->hsize;
  72. struct hashnode **hp = ht->nodes+hval,*hn;
  73.  
  74.     for (; *hp; hp = &(*hp)->next)
  75.         if (!strcmp((*hp)->nam,nam)) {
  76.             if ((*hp)->canfree) free((*hp)->nam);
  77.             hn = dat;
  78.             hn->next = (*hp)->next;
  79.             if (!freefunc) zerr("attempt to call NULL freefunc",NULL,0);
  80.             else freefunc(*hp);
  81.             *hp = hn;
  82.             hn->nam = nam;
  83.             hn->canfree = canfree;
  84.             return;
  85.         }
  86.     hn = (Hashnode) dat;
  87.     hn->nam = nam;
  88.     hn->canfree = canfree;
  89.     hn->next = ht->nodes[hval];
  90.     ht->nodes[hval] = hn;
  91.     if (++ht->ct == ht->hsize*4) expandhtab(ht);
  92. }
  93.  
  94. /* add a node to command hash table */
  95.  
  96. void addhcmdnode(nam,pnam) /**/
  97. char *nam;char **pnam;
  98. {
  99. int hval = hasher(nam) % cmdnamtab->hsize;
  100. struct hashnode *hp = cmdnamtab->nodes[hval],*hn;
  101. Cmdnam cc;
  102.  
  103.     for (; hp; hp = hp->next) if (!strcmp(hp->nam,nam)) return;
  104.     cc = (Cmdnam) zcalloc(sizeof *cc);
  105.     cc->type = EXCMD;
  106.     cc->u.nam = tricat(*pnam,"/",nam);
  107.     cc->pcomp = pnam;
  108.     hn = (Hashnode) cc;
  109.     hn->nam = ztrdup(nam);
  110.     hn->canfree = 1;
  111.     hn->next = cmdnamtab->nodes[hval];
  112.     cmdnamtab->nodes[hval] = hn;
  113.     if (++cmdnamtab->ct == cmdnamtab->hsize*4) expandhtab(cmdnamtab);
  114. }
  115.  
  116. /* expand hash tables when they get too many entries */
  117.  
  118. void expandhtab(ht) /**/
  119. Hashtab ht;
  120. {
  121. struct hashnode **arr,**ha,*hn,*hp;
  122. int osize = ht->hsize,nsize = osize*8;
  123.  
  124.     ht->hsize = nsize;
  125.     arr = ht->nodes;
  126.     ht->nodes = (Hashnode*) zcalloc(nsize*sizeof(struct hashnode *));
  127.     for (ha = arr; osize; osize--,ha++)
  128.         for (hn = *ha; hn; ) {
  129.             hp = hn->next;
  130.             Addhnode(hn->nam,(vptr)hn,ht,NULL,hn->canfree);
  131.             hn = hp;
  132.         }
  133.     free(arr);
  134. }
  135.  
  136. /* get an entry in a hash table */
  137.  
  138. vptr gethnode(nam,ht) /**/
  139. char *nam;Hashtab ht;
  140. {
  141. int hval = hasher(nam) % ht->hsize;
  142. struct hashnode *hn = ht->nodes[hval];
  143.  
  144.     for (; hn; hn = hn->next) if (!strcmp(hn->nam,nam)) return (vptr)hn;
  145.     return NULL;
  146. }
  147.  
  148. void freehtab(ht,freefunc) /**/
  149. Hashtab ht;FFunc freefunc;
  150. {
  151. int val;
  152. struct hashnode *hn,**hp = &ht->nodes[0],*next;
  153.  
  154.     for (val = ht->hsize; val; val--,hp++)
  155.         for (hn = *hp; hn; ) {
  156.             next = hn->next;
  157.             if (hn->canfree) free(hn->nam);
  158.             freefunc(hn);
  159.             hn = next;
  160.         }
  161.     free(ht->nodes);
  162.     free(ht);
  163. }
  164.  
  165. /* remove a hash table entry and return a pointer to it */
  166.  
  167. vptr remhnode(nam,ht) /**/
  168. char *nam;Hashtab ht;
  169. {
  170. int hval = hasher(nam) % ht->hsize;
  171. struct hashnode *hn = ht->nodes[hval],*hp;
  172.  
  173.     if (!hn) return NULL;
  174.     if (!strcmp(hn->nam,nam)) {
  175.         ht->nodes[hval] = hn->next;
  176.         if (hn->canfree) free(hn->nam);
  177.         ht->ct--;
  178.         return (vptr)hn;
  179.     }
  180.     for (hp = hn, hn = hn->next; hn; hn = (hp = hn)->next)
  181.         if (!strcmp(hn->nam,nam)) {
  182.             hp->next = hn->next;
  183.             if (hn->canfree) free(hn->nam);
  184.             ht->ct--;
  185.             return (vptr)hn;
  186.         }
  187.     return NULL;
  188. }
  189.  
  190. /* insert a node in a linked list after 'llast' */
  191.  
  192. void insnode(list,llast,dat) /**/
  193. Lklist list;Lknode llast;vptr dat;
  194. {
  195. Lknode tmp;
  196.  
  197.     tmp = llast->next;
  198.     llast->next = (Lknode) alloc(sizeof *tmp);
  199.     llast->next->last = llast;
  200.     llast->next->dat = dat;
  201.     llast->next->next = tmp;
  202.     if (tmp) tmp->last = llast->next;
  203.     else list->last = llast->next;
  204. }
  205.  
  206. void addnodeinorder(x,dat) /**/
  207. Lklist x; char *dat;
  208. {
  209. Lknode y, l = NULL;
  210. int val = 123;
  211.  
  212.     for (y = firstnode(x); y; incnode(y)) {
  213.         if ((val = forstrcmp((char **) &y->dat, &dat)) >= 0) break;
  214.         l = y;
  215.     }
  216.     if (!val) return;
  217.     if (l == NULL) insnode(x, (Lknode) x, dat);
  218.     else insnode(x, l, dat);
  219. }
  220.  
  221.  
  222. /* remove a node from a linked list */
  223.  
  224. vptr remnode(list,nd) /**/
  225. Lklist list;Lknode nd;
  226. {
  227. vptr dat;
  228.  
  229.     nd->last->next = nd->next;
  230.     if (nd->next) nd->next->last = nd->last;
  231.     else list->last = nd->last;
  232.     dat = nd->dat;
  233.     free(nd);
  234.     return dat;
  235. }
  236.  
  237. /* remove a node from a linked list */
  238.  
  239. vptr uremnode(list,nd) /**/
  240. Lklist list;Lknode nd;
  241. {
  242. vptr dat;
  243.  
  244.     nd->last->next = nd->next;
  245.     if (nd->next) nd->next->last = nd->last;
  246.     else list->last = nd->last;
  247.     dat = nd->dat;
  248.     return dat;
  249. }
  250.  
  251. /* delete a character in a string */
  252.  
  253. void chuck(str) /**/
  254. char *str;
  255. {
  256.     while (str[0] = str[1]) str++;
  257. }
  258.  
  259. /* get top node in a linked list */
  260.  
  261. vptr getnode(list) /**/
  262. Lklist list;
  263. {
  264. vptr dat;
  265. Lknode node = list->first;
  266.  
  267.     if (!node)
  268.         return NULL;
  269.     dat = node->dat;
  270.     list->first = node->next;
  271.     if (node->next)
  272.         node->next->last = (Lknode) list;
  273.     else
  274.         list->last = (Lknode) list;
  275.     free(node);
  276.     return dat;
  277. }
  278.  
  279. /* get top node in a linked list without freeing */
  280.  
  281. vptr ugetnode(list) /**/
  282. Lklist list;
  283. {
  284. vptr dat;
  285. Lknode node = list->first;
  286.  
  287.     if (!node)
  288.         return NULL;
  289.     dat = node->dat;
  290.     list->first = node->next;
  291.     if (node->next)
  292.         node->next->last = (Lknode) list;
  293.     else
  294.         list->last = (Lknode) list;
  295.     return dat;
  296. }
  297.  
  298. void freetable(tab,freefunc) /**/
  299. Lklist tab;FFunc freefunc;
  300. {
  301. Lknode node = tab->first,next;
  302.  
  303.     while (node) {
  304.         next = node->next;
  305.         if (freefunc) freefunc(node->dat);
  306.         free(node);
  307.         node = next;
  308.     }
  309.     free(tab);
  310. }
  311.  
  312. char *ztrstr(s,t) /**/
  313. char *s;char *t;
  314. {
  315. char *p1,*p2;
  316.  
  317.     for (; *s; s++) {
  318.         for (p1 = s, p2 = t; *p2; p1++,p2++)
  319.             if (*p1 != *p2) break;
  320.         if (!*p2) return (char *) s;
  321.     }
  322.     return NULL;
  323. }
  324.  
  325. /* insert a list in another list */
  326.  
  327. void inslist(l,where,x) /**/
  328. Lklist l;Lknode where;Lklist x;
  329. {
  330. Lknode nx = where->next;
  331.  
  332.     if (!l->first) return;
  333.     where->next = l->first;
  334.     l->last->next = nx;
  335.     l->first->last = where;
  336.     if (nx) nx->last = l->last;
  337.     else x->last = l->last;
  338. }
  339.  
  340. int countnodes(x) /**/
  341. Lklist x;
  342. {
  343. Lknode y;
  344. int ct = 0;
  345.  
  346.     for (y = firstnode(x); y; incnode(y),ct++);
  347.     return ct;
  348. }
  349.  
  350.