home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / news / cnews.tar / libc / hdbm.c < prev    next >
C/C++ Source or Header  |  1993-03-09  |  6KB  |  281 lines
  1. /*
  2.  * general-purpose in-core hashing, dbm interface
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include "hdbm.h"
  9. #include "hdbmint.h"
  10.  
  11. /* tunable parameters */
  12. #define RETAIN 300        /* retain & recycle this many HASHENTs */
  13.  
  14. /* fundamental constants */
  15. #define YES 1
  16. #define NO 0
  17.  
  18. static HASHENT *hereuse = NULL;
  19. static int reusables = 0;
  20.  
  21. static unsigned                /* not yet taken modulus table size */
  22. hdbmdef(key)
  23. HDBMDATUM key;
  24. {
  25.     register char *s = key.dat_ptr;
  26.     register unsigned len = key.dat_len;
  27.     register unsigned hash = 0;
  28.  
  29.     while (len-- > 0)
  30.         hash += *s++;
  31.     return hash;
  32. }
  33.  
  34. HASHTABLE *
  35. hdbmcreate(size, hashfunc)
  36. register unsigned size;            /* a crude guide to size */
  37. unsigned (*hashfunc)();
  38. {
  39.     register HASHTABLE *tbl;
  40.     register HASHENT **hepp;
  41.     /*
  42.      * allocate HASHTABLE and (HASHENT *) array together to reduce the
  43.      * number of malloc calls.  this idiom ensures correct alignment of
  44.      * the array.
  45.      * dmr calls the one-element array trick `unwarranted chumminess with
  46.      * the compiler' though.
  47.      */
  48.     register struct alignalloc {
  49.         HASHTABLE ht;
  50.         HASHENT *hepa[1];    /* longer than it looks */
  51.     } *aap;
  52.  
  53.     aap = (struct alignalloc *)
  54.         malloc(sizeof *aap + (size-1)*sizeof(HASHENT *));
  55.     if (aap == NULL)
  56.         return NULL;
  57.     tbl = &aap->ht;
  58.     tbl->ht_size = (size == 0? 1: size);    /* size of 0 is nonsense */
  59.     tbl->ht_magic = HASHMAG;
  60.     tbl->ht_hash = (hashfunc == NULL? hdbmdef: hashfunc);
  61.     tbl->ht_addr = hepp = aap->hepa;
  62.     while (size-- > 0)
  63.         hepp[size] = NULL;
  64.     return tbl;
  65. }
  66.  
  67. static
  68. hefree(hp)                    /* free a hash entry */
  69. register HASHENT *hp;
  70. {
  71.     if (reusables >= RETAIN)        /* compost heap is full? */
  72.         free((char *)hp);        /* yup, just pitch this one */
  73.     else {                    /* no, just stash for reuse */
  74.         ++reusables;
  75.         hp->he_next = hereuse;
  76.         hereuse = hp;
  77.     }
  78. }
  79.  
  80. /*
  81.  * free all the memory associated with tbl, erase the pointers to it, and
  82.  * invalidate tbl to prevent further use via other pointers to it.
  83.  */
  84. hdbmdestroy(tbl)
  85. register HASHTABLE *tbl;
  86. {
  87.     register unsigned idx;
  88.     register HASHENT *hp, *next;
  89.     register HASHENT **hepp;
  90.     register int tblsize;
  91.  
  92.     if (tbl == NULL || BADTBL(tbl))
  93.         return;
  94.     tblsize = tbl->ht_size;
  95.     hepp = tbl->ht_addr;
  96.     for (idx = 0; idx < tblsize; idx++) {
  97.         for (hp = hepp[idx]; hp != NULL; hp = next) {
  98.             next = hp->he_next;
  99.             hp->he_next = NULL;
  100.             hefree(hp);
  101.         }
  102.         hepp[idx] = NULL;
  103.     }
  104.     tbl->ht_magic = 0;        /* de-certify this table */
  105.     tbl->ht_addr = NULL;
  106.     free((char *)tbl);
  107. }
  108.  
  109. /*
  110.  * The returned value is the address of the pointer that refers to the
  111.  * found object.  Said pointer may be NULL if the object was not found;
  112.  * if so, this pointer should be updated with the address of the object
  113.  * to be inserted, if insertion is desired.
  114.  */
  115. static HASHENT **
  116. hdbmfind(tbl, key)
  117. register HASHTABLE *tbl;
  118. HDBMDATUM key;
  119. {
  120.     register HASHENT *hp, *prevhp = NULL;
  121.     register char *hpkeydat, *keydat = key.dat_ptr;
  122.     register int keylen = key.dat_len;
  123.     register HASHENT **hepp;
  124.     register unsigned size; 
  125.  
  126.     if (BADTBL(tbl))
  127.         return NULL;
  128.     size = tbl->ht_size;
  129.     if (size == 0)            /* paranoia: avoid division by zero */
  130.         size = 1;
  131.     hepp = &tbl->ht_addr[(*tbl->ht_hash)(key) % size];
  132.     for (hp = *hepp; hp != NULL; prevhp = hp, hp = hp->he_next) {
  133.         hpkeydat = hp->he_key.dat_ptr;
  134.         if (hp->he_key.dat_len == keylen && hpkeydat[0] == keydat[0] &&
  135.             memcmp(hpkeydat, keydat, keylen) == 0)
  136.             break;
  137.     }
  138.     /* assert: *(returned value) == hp */
  139.     return (prevhp == NULL? hepp: &prevhp->he_next);
  140. }
  141.  
  142. static HASHENT *
  143. healloc()                    /* allocate a hash entry */
  144. {
  145.     register HASHENT *hp;
  146.  
  147.     if (hereuse == NULL)
  148.         return (HASHENT *)malloc(sizeof(HASHENT));
  149.     /* pull the first reusable one off the pile */
  150.     hp = hereuse;
  151.     hereuse = hereuse->he_next;
  152.     hp->he_next = NULL;            /* prevent accidents */
  153.     reusables--;
  154.     return hp;
  155. }
  156.  
  157. /*
  158.  * addresses in key and data must point at unmoving data
  159.  * for the life of the table.
  160.  */
  161. int
  162. hdbmstore(tbl, key, data)
  163. register HASHTABLE *tbl;
  164. HDBMDATUM key, data;
  165. {
  166.     register HASHENT *hp;
  167.     register HASHENT **nextp;
  168.  
  169.     if (BADTBL(tbl))
  170.         return NO;
  171.     nextp = hdbmfind(tbl, key);
  172.     if (nextp == NULL)
  173.         return NO;
  174.     hp = *nextp;
  175.     if (hp == NULL) {            /* absent; allocate an entry */
  176.         hp = healloc();
  177.         if (hp == NULL)
  178.             return NO;
  179.         hp->he_next = NULL;
  180.         hp->he_key = key;
  181.         *nextp = hp;            /* append to hash chain */
  182.     }
  183.     hp->he_data = data;    /* supersede any old data for this key */
  184.     return YES;
  185. }
  186.  
  187. /* return any existing entry for key; otherwise call allocator to make one */
  188. HDBMDATUM
  189. hdbmentry(tbl, key, allocator)
  190. register HASHTABLE *tbl;
  191. HDBMDATUM key;
  192. HDBMDATUM (*allocator)();
  193. {
  194.     register HASHENT *hp;
  195.     register HASHENT **nextp;
  196.     static HDBMDATUM errdatum = { NULL, 0 };
  197.  
  198.     if (BADTBL(tbl))
  199.         return errdatum;
  200.     nextp = hdbmfind(tbl, key);
  201.     if (nextp == NULL)
  202.         return errdatum;
  203.     hp = *nextp;
  204.     if (hp == NULL) {            /* absent; allocate an entry */
  205.         hp = healloc();
  206.         if (hp == NULL)
  207.             return errdatum;
  208.         hp->he_next = NULL;
  209.         hp->he_key = key;
  210.         hp->he_data = (*allocator)(key);
  211.         *nextp = hp;            /* append to hash chain */
  212.     }
  213.     return hp->he_data;
  214. }
  215.  
  216. int
  217. hdbmdelete(tbl, key)
  218. register HASHTABLE *tbl;
  219. HDBMDATUM key;
  220. {
  221.     register HASHENT *hp;
  222.     register HASHENT **nextp;
  223.  
  224.     nextp = hdbmfind(tbl, key);
  225.     if (nextp == NULL)
  226.         return NO;
  227.     hp = *nextp;
  228.     if (hp == NULL)                /* absent */
  229.         return NO;
  230.     *nextp = hp->he_next;            /* skip this entry */
  231.     hp->he_next = NULL;
  232.     hp->he_data.dat_ptr = hp->he_key.dat_ptr = NULL;
  233.     hefree(hp);
  234.     return YES;
  235. }
  236.  
  237. HDBMDATUM                    /* data corresponding to key */
  238. hdbmfetch(tbl, key)
  239. register HASHTABLE *tbl;
  240. HDBMDATUM key;
  241. {
  242.     register HASHENT *hp;
  243.     register HASHENT **nextp;
  244.     static HDBMDATUM errdatum = { NULL, 0 };
  245.  
  246.     if (BADTBL(tbl))
  247.         return errdatum;
  248.     nextp = hdbmfind(tbl, key);
  249.     if (nextp == NULL)
  250.         return errdatum;
  251.     hp = *nextp;
  252.     if (hp == NULL)                /* absent */
  253.         return errdatum;
  254.     else
  255.         return hp->he_data;
  256. }
  257.  
  258. /*
  259.  * visit each entry by calling nodefunc at each, with key, data and hook as
  260.  * arguments.  hook is an attempt to allow side-effects and reentrancy at
  261.  * the same time.
  262.  */
  263. hdbmwalk(tbl, nodefunc, hook)
  264. HASHTABLE *tbl;
  265. register int (*nodefunc)();
  266. register char *hook;                /* (void *) really */
  267. {
  268.     register unsigned idx;
  269.     register HASHENT *hp;
  270.     register HASHENT **hepp;
  271.     register int tblsize;
  272.  
  273.     if (BADTBL(tbl))
  274.         return;
  275.     hepp = tbl->ht_addr;
  276.     tblsize = tbl->ht_size;
  277.     for (idx = 0; idx < tblsize; idx++)
  278.         for (hp = hepp[idx]; hp != NULL; hp = hp->he_next)
  279.             (*nodefunc)(hp->he_key, hp->he_data, hook);
  280. }
  281.