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