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