home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / perlkt40.zip / HASH.C < prev    next >
C/C++ Source or Header  |  1996-06-13  |  5KB  |  248 lines
  1. /* $RCSfile: hash.c,v $$Revision: 4.0.1.1 $$Date: 91/06/07 12:15:55 $
  2.  *
  3.  *    Copyright (c) 1991, Larry Wall
  4.  *
  5.  *    You may distribute under the terms of either the GNU General Public
  6.  *    License or the Artistic License, as specified in the README file.
  7.  *
  8.  * $Log:    hash.c,v $
  9.  * Revision 4.0.1.1  91/06/07  12:15:55  lwall
  10.  * patch4: new copyright notice
  11.  * 
  12.  * Revision 4.0  91/03/20  01:57:49  lwall
  13.  * 4.0 baseline.
  14.  * 
  15.  */
  16.  
  17. #include <stdio.h>
  18. #include "EXTERN.h"
  19. #include "handy.h"
  20. #include "util.h"
  21. #include "a2p.h"
  22.  
  23. STR *
  24. hfetch(tb,key)
  25. register HASH *tb;
  26. char *key;
  27. {
  28.     register char *s;
  29.     register int i;
  30.     register int hash;
  31.     register HENT *entry;
  32.  
  33.     if (!tb)
  34.     return Nullstr;
  35.     for (s=key,        i=0,    hash = 0;
  36.       /* while */ *s;
  37.      s++,        i++,    hash *= 5) {
  38.     hash += *s * coeff[i];
  39.     }
  40.     entry = tb->tbl_array[hash & tb->tbl_max];
  41.     for (; entry; entry = entry->hent_next) {
  42.     if (entry->hent_hash != hash)        /* strings can't be equal */
  43.         continue;
  44.     if (strNE(entry->hent_key,key))    /* is this it? */
  45.         continue;
  46.     return entry->hent_val;
  47.     }
  48.     return Nullstr;
  49. }
  50.  
  51. bool
  52. hstore(tb,key,val)
  53. register HASH *tb;
  54. char *key;
  55. STR *val;
  56. {
  57.     register char *s;
  58.     register int i;
  59.     register int hash;
  60.     register HENT *entry;
  61.     register HENT **oentry;
  62.  
  63.     if (!tb)
  64.     return FALSE;
  65.     for (s=key,        i=0,    hash = 0;
  66.       /* while */ *s;
  67.      s++,        i++,    hash *= 5) {
  68.     hash += *s * coeff[i];
  69.     }
  70.  
  71.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  72.     i = 1;
  73.  
  74.     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  75.     if (entry->hent_hash != hash)        /* strings can't be equal */
  76.         continue;
  77.     if (strNE(entry->hent_key,key))    /* is this it? */
  78.         continue;
  79.     /*NOSTRICT*/
  80.     safefree((char*)entry->hent_val);
  81.     entry->hent_val = val;
  82.     return TRUE;
  83.     }
  84.     /*NOSTRICT*/
  85.     entry = (HENT*) safemalloc(sizeof(HENT));
  86.  
  87.     entry->hent_key = savestr(key);
  88.     entry->hent_val = val;
  89.     entry->hent_hash = hash;
  90.     entry->hent_next = *oentry;
  91.     *oentry = entry;
  92.  
  93.     if (i) {                /* initial entry? */
  94.     tb->tbl_fill++;
  95.     if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  96.         hsplit(tb);
  97.     }
  98.  
  99.     return FALSE;
  100. }
  101.  
  102. #ifdef NOTUSED
  103. bool
  104. hdelete(tb,key)
  105. register HASH *tb;
  106. char *key;
  107. {
  108.     register char *s;
  109.     register int i;
  110.     register int hash;
  111.     register HENT *entry;
  112.     register HENT **oentry;
  113.  
  114.     if (!tb)
  115.     return FALSE;
  116.     for (s=key,        i=0,    hash = 0;
  117.       /* while */ *s;
  118.      s++,        i++,    hash *= 5) {
  119.     hash += *s * coeff[i];
  120.     }
  121.  
  122.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  123.     entry = *oentry;
  124.     i = 1;
  125.     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
  126.     if (entry->hent_hash != hash)        /* strings can't be equal */
  127.         continue;
  128.     if (strNE(entry->hent_key,key))    /* is this it? */
  129.         continue;
  130.     safefree((char*)entry->hent_val);
  131.     safefree(entry->hent_key);
  132.     *oentry = entry->hent_next;
  133.     safefree((char*)entry);
  134.     if (i)
  135.         tb->tbl_fill--;
  136.     return TRUE;
  137.     }
  138.     return FALSE;
  139. }
  140. #endif
  141.  
  142. hsplit(tb)
  143. HASH *tb;
  144. {
  145.     int oldsize = tb->tbl_max + 1;
  146.     register int newsize = oldsize * 2;
  147.     register int i;
  148.     register HENT **a;
  149.     register HENT **b;
  150.     register HENT *entry;
  151.     register HENT **oentry;
  152.  
  153.     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
  154.     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
  155.     tb->tbl_max = --newsize;
  156.     tb->tbl_array = a;
  157.  
  158.     for (i=0; i<oldsize; i++,a++) {
  159.     if (!*a)                /* non-existent */
  160.         continue;
  161.     b = a+oldsize;
  162.     for (oentry = a, entry = *a; entry; entry = *oentry) {
  163.         if ((entry->hent_hash & newsize) != i) {
  164.         *oentry = entry->hent_next;
  165.         entry->hent_next = *b;
  166.         if (!*b)
  167.             tb->tbl_fill++;
  168.         *b = entry;
  169.         continue;
  170.         }
  171.         else
  172.         oentry = &entry->hent_next;
  173.     }
  174.     if (!*a)                /* everything moved */
  175.         tb->tbl_fill--;
  176.     }
  177. }
  178.  
  179. HASH *
  180. hnew()
  181. {
  182.     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
  183.  
  184.     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
  185.     tb->tbl_fill = 0;
  186.     tb->tbl_max = 7;
  187.     hiterinit(tb);    /* so each() will start off right */
  188.     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
  189.     return tb;
  190. }
  191.  
  192. #ifdef NOTUSED
  193. hshow(tb)
  194. register HASH *tb;
  195. {
  196.     fprintf(stderr,"%5d %4d (%2d%%)\n",
  197.     tb->tbl_max+1,
  198.     tb->tbl_fill,
  199.     tb->tbl_fill * 100 / (tb->tbl_max+1));
  200. }
  201. #endif
  202.  
  203. hiterinit(tb)
  204. register HASH *tb;
  205. {
  206.     tb->tbl_riter = -1;
  207.     tb->tbl_eiter = Null(HENT*);
  208.     return tb->tbl_fill;
  209. }
  210.  
  211. HENT *
  212. hiternext(tb)
  213. register HASH *tb;
  214. {
  215.     register HENT *entry;
  216.  
  217.     entry = tb->tbl_eiter;
  218.     do {
  219.     if (entry)
  220.         entry = entry->hent_next;
  221.     if (!entry) {
  222.         tb->tbl_riter++;
  223.         if (tb->tbl_riter > tb->tbl_max) {
  224.         tb->tbl_riter = -1;
  225.         break;
  226.         }
  227.         entry = tb->tbl_array[tb->tbl_riter];
  228.     }
  229.     } while (!entry);
  230.  
  231.     tb->tbl_eiter = entry;
  232.     return entry;
  233. }
  234.  
  235. char *
  236. hiterkey(entry)
  237. register HENT *entry;
  238. {
  239.     return entry->hent_key;
  240. }
  241.  
  242. STR *
  243. hiterval(entry)
  244. register HENT *entry;
  245. {
  246.     return entry->hent_val;
  247. }
  248.