home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / k / ksh48.zip / sh / table.c < prev    next >
C/C++ Source or Header  |  1992-05-03  |  4KB  |  202 lines
  1. #ifndef lint
  2. static char *RCSid = "$Id: table.c,v 1.2 1992/04/25 08:33:28 sjg Exp $";
  3. #endif
  4.  
  5. /*
  6.  * dynamic hashed associative table for commands and variables
  7.  */
  8.  
  9. #include "stdh.h"
  10. #include <errno.h>
  11. #include <setjmp.h>
  12. #include "sh.h"
  13.  
  14. #define    INIT_TBLS    8    /* initial table size (power of 2) */
  15.  
  16. static struct tstate {
  17.     int left;
  18.     struct tbl **next;
  19. } tstate;
  20.  
  21. static void     texpand     ARGS((struct table *tp, int nsize));
  22. static int      tnamecmp    ARGS((void *p1, void *p2));
  23.  
  24.  
  25. unsigned int
  26. hash(n)
  27.     register char * n;
  28. {
  29.     register unsigned int h = 0;
  30.  
  31.     while (*n != '\0')
  32.         h = 2*h + *n++;
  33.     return h * 32821;    /* scatter bits */
  34. }
  35.  
  36. #if 0
  37. phash(s) char *s; {
  38.     printf("%2d: %s\n", hash(s)%32, s);
  39. }
  40. #endif
  41.  
  42. void
  43. tinit(tp, ap)
  44.     register struct table *tp;
  45.     register Area *ap;
  46. {
  47.     tp->areap = ap;
  48.     tp->size = tp->free = 0;
  49.     tp->tbls = NULL;
  50. }
  51.  
  52. static void
  53. texpand(tp, nsize)
  54.     register struct table *tp;
  55.     int nsize;
  56. {
  57.     register int i;
  58.     register struct tbl *tblp, **p;
  59.     register struct tbl **ntblp, **otblp = tp->tbls;
  60.     int osize = tp->size;
  61.  
  62.     ntblp = (struct tbl**) alloc(sizeofN(struct tbl *, nsize), tp->areap);
  63.     for (i = 0; i < nsize; i++)
  64.         ntblp[i] = NULL;
  65.     tp->size = nsize;
  66.     tp->free = 8*nsize/10;    /* table can get 80% full */
  67.     tp->tbls = ntblp;
  68.     if (otblp == NULL)
  69.         return;
  70.     for (i = 0; i < osize; i++)
  71.         if ((tblp = otblp[i]) != NULL)
  72.             if ((tblp->flag&DEFINED)) {
  73.                 for (p = &ntblp[hash(tblp->name) &
  74.                         (tp->size-1)];
  75.                      *p != NULL; p--)
  76.                     if (p == ntblp) /* wrap */
  77.                         p += tp->size;
  78.                 *p = tblp;
  79.                 tp->free--;
  80.             } else {
  81.                 afree((void*)tblp, tp->areap);
  82.             }
  83.     afree((void*)otblp, tp->areap);
  84. }
  85.  
  86. struct tbl *
  87. tsearch(tp, n, h)
  88.     register struct table *tp;    /* table */
  89.     register char *n;        /* name to enter */
  90.     unsigned int h;            /* hash(n) */
  91. {
  92.     register struct tbl **pp, *p;
  93.  
  94.     if (tp->size == 0)
  95.         return NULL;
  96.  
  97.     /* search for name in hashed table */
  98.     for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
  99.         if (*p->name == *n && strcmp(p->name, n) == 0
  100.             && (p->flag&DEFINED))
  101.             return p;
  102.         if (pp == tp->tbls) /* wrap */
  103.             pp += tp->size;
  104.     }
  105.  
  106.     return NULL;
  107. }
  108.  
  109. struct tbl *
  110. tenter(tp, n, h)
  111.     register struct table *tp;    /* table */
  112.     register char *n;        /* name to enter */
  113.     unsigned int h;            /* hash(n) */
  114. {
  115.     register struct tbl **pp, *p;
  116.     register char *cp;
  117.  
  118.     if (tp->size == 0)
  119.         texpand(tp, INIT_TBLS);
  120.   Search:
  121.     /* search for name in hashed table */
  122.     for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
  123.         if (*p->name == *n && strcmp(p->name, n) == 0)
  124.             return p;     /* found */
  125.         if (pp == tp->tbls) /* wrap */
  126.             pp += tp->size;
  127.     }
  128.  
  129.     if (tp->free <= 0) {    /* too full */
  130.         texpand(tp, 2*tp->size);
  131.         goto Search;
  132.     }
  133.  
  134.     /* create new tbl entry */
  135.     for (cp = n; *cp != '\0'; cp++)
  136.         ;
  137.     p = (struct tbl *) alloc(offsetof(struct tbl, name[(cp-n)+1]), tp->areap);
  138.     p->flag = 0;
  139.     p->type = 0;
  140.     for (cp = p->name; *n != '\0';)
  141.         *cp++ = *n++;
  142.     *cp = '\0';
  143.  
  144.     /* enter in tp->tbls */
  145.     tp->free--;
  146.     *pp = p;
  147.     return p;
  148. }
  149.  
  150. void
  151. tdelete(p)
  152.     register struct tbl *p;
  153. {
  154.     p->flag = 0;
  155. }
  156.  
  157. void
  158. twalk(tp)
  159.     register struct table *tp;
  160. {
  161.     tstate.left = tp->size;
  162.     tstate.next = tp->tbls;
  163. }
  164.  
  165. struct tbl *
  166. tnext()
  167. {
  168.     while (--tstate.left >= 0) {
  169.         struct tbl *p = *tstate.next++;
  170.         if (p != NULL && (p->flag&DEFINED))
  171.             return p;
  172.     }
  173.     return NULL;
  174. }
  175.  
  176. static int
  177. tnamecmp(p1, p2)
  178.     void *p1, *p2;
  179. {
  180.     return strcmp(((struct tbl *)p1)->name, ((struct tbl *)p2)->name);
  181. }
  182.  
  183. struct tbl **
  184. tsort(tp)
  185.     register struct table *tp;
  186. {
  187.     register int i;
  188.     register struct tbl **p, **sp, **dp;
  189.  
  190.     p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP);
  191.     sp = tp->tbls;        /* source */
  192.     dp = p;            /* dest */
  193.     for (i = 0; i < tp->size; i++)
  194.         if ((*dp = *sp++) != NULL && ((*dp)->flag&DEFINED))
  195.             dp++;
  196.     i = dp - p;
  197.     qsortp((void**)p, (size_t)i, tnamecmp);
  198.     p[i] = NULL;
  199.     return p;
  200. }
  201.  
  202.