home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / news / nn.tar / nn-6.5.1 / hdbm.c < prev    next >
C/C++ Source or Header  |  1996-08-04  |  8KB  |  355 lines
  1. /*******************WARNING*********************
  2.  
  3. This is a *MODIFIED* version of Geoff Coller's proof-of-concept NOV
  4. implementation.
  5.  
  6. It has been modified to support threading directly from a file handle
  7. to a NNTP server without a temporary file.
  8.  
  9. This is not a complete distribution.  We have only distributed enough
  10. to support NN's needs.
  11.  
  12. The original version came from world.std.com:/src/news/nov.dist.tar.Z
  13. and was dated 11 Aug 1993.
  14.  
  15. In any case, bugs you find here are probably my fault, as I've trimmed
  16. a fair bit of unused code.
  17.  
  18. -Peter Wemm  <peter@DIALix.oz.au>
  19. */
  20.  
  21. /*
  22.  * Copyright (c) Geoffrey Collyer 1992, 1993.
  23.  * All rights reserved.
  24.  * Written by Geoffrey Collyer.
  25.  * Thanks to UUNET Communications Services Inc for financial support.
  26.  *
  27.  * This software is not subject to any license of the American Telephone
  28.  * and Telegraph Company, the Regents of the University of California, or
  29.  * the Free Software Foundation.
  30.  *
  31.  * Permission is granted to anyone to use this software for any purpose on
  32.  * any computer system, and to alter it and redistribute it freely, subject
  33.  * to the following restrictions:
  34.  *
  35.  * 1. The authors are not responsible for the consequences of use of this
  36.  *    software, no matter how awful, even if they arise from flaws in it.
  37.  *
  38.  * 2. The origin of this software must not be misrepresented, either by
  39.  *    explicit claim or by omission.  Since few users ever read sources,
  40.  *    credits must appear in the documentation.
  41.  *
  42.  * 3. Altered versions must be plainly marked as such, and must not be
  43.  *    misrepresented as being the original software.  Since few users
  44.  *    ever read sources, credits must appear in the documentation.
  45.  *
  46.  * 4. This notice may not be removed or altered.
  47.  */
  48.  
  49.  
  50. /*
  51.  * general-purpose in-core hashing, dbm interface
  52.  */
  53.  
  54. #include "config.h"
  55. #include "hdbm.h"
  56. #include "hdbmint.h"
  57.  
  58. /* tunable parameters */
  59. #define RETAIN 300        /* retain & recycle this many HASHENTs */
  60.  
  61. /* fundamental constants */
  62. #define YES 1
  63. #define NO 0
  64.  
  65. static HASHENT *hereuse = NULL;
  66. static int reusables = 0;
  67.  
  68. /*
  69.  * Gosling EMACS hash (h = 33*h + *s++) optimized, loop unrolled with
  70.  * "Duff's Device".  Thanks to Chris Torek.
  71.  */
  72. static unsigned
  73. hdbmdef(key)
  74. register HDBMDATUM key;
  75. {
  76.     register unsigned char *s = (unsigned char *)key.dat_ptr;
  77.     register int len = key.dat_len;
  78.     register unsigned h;
  79.     register int loop;
  80.  
  81. #define HASHC   h = (h << 5) + h + *s++;
  82.  
  83.     h = 0;
  84.     if (len > 0) {
  85.         loop = (len + 8 - 1) >> 3;
  86.  
  87.         switch (len & (8 - 1)) {
  88.         case 0:
  89.             do {    /* All fall throughs */
  90.                 HASHC;
  91.         case 7:
  92.                 HASHC;
  93.         case 6:
  94.                 HASHC;
  95.         case 5:
  96.                 HASHC;
  97.         case 4:
  98.                 HASHC;
  99.         case 3:
  100.                 HASHC;
  101.         case 2:
  102.                 HASHC;
  103.         case 1:
  104.                 HASHC;
  105.             } while (--loop);
  106.         }
  107.  
  108.     }
  109.     return (h);
  110. }
  111.  
  112. HASHTABLE *
  113. hdbmcreate(size, hashfunc)
  114. register unsigned size;            /* a crude guide to size */
  115. unsigned (*hashfunc)();
  116. {
  117.     register HASHTABLE *tbl;
  118.     register HASHENT **hepp;
  119.     /*
  120.      * allocate HASHTABLE and (HASHENT *) array together to reduce the
  121.      * number of malloc calls.  this idiom ensures correct alignment of
  122.      * the array.
  123.      * dmr calls the one-element array trick `unwarranted chumminess with
  124.      * the compiler' though.
  125.      */
  126.     register struct alignalloc {
  127.         HASHTABLE ht;
  128.         HASHENT *hepa[1];    /* longer than it looks */
  129.     } *aap;
  130.  
  131.     aap = (struct alignalloc *)
  132.         malloc(sizeof *aap + (size-1)*sizeof(HASHENT *));
  133.     if (aap == NULL)
  134.         return NULL;
  135.     tbl = &aap->ht;
  136.     tbl->ht_size = (size == 0? 1: size);    /* size of 0 is nonsense */
  137.     tbl->ht_magic = HASHMAG;
  138.     tbl->ht_hash = (hashfunc == NULL? hdbmdef: hashfunc);
  139.     tbl->ht_addr = hepp = aap->hepa;
  140.     while (size-- > 0)
  141.         hepp[size] = NULL;
  142.     return tbl;
  143. }
  144.  
  145. static
  146. hefree(hp)                    /* free a hash entry */
  147. register HASHENT *hp;
  148. {
  149.     if (reusables >= RETAIN)        /* compost heap is full? */
  150.         free((char *)hp);        /* yup, just pitch this one */
  151.     else {                    /* no, just stash for reuse */
  152.         ++reusables;
  153.         hp->he_next = hereuse;
  154.         hereuse = hp;
  155.     }
  156. }
  157.  
  158. /*
  159.  * free all the memory associated with tbl, erase the pointers to it, and
  160.  * invalidate tbl to prevent further use via other pointers to it.
  161.  */
  162. hdbmdestroy(tbl)
  163. register HASHTABLE *tbl;
  164. {
  165.     register unsigned idx;
  166.     register HASHENT *hp, *next;
  167.     register HASHENT **hepp;
  168.     register int tblsize;
  169.  
  170.     if (tbl == NULL || BADTBL(tbl))
  171.         return;
  172.     tblsize = tbl->ht_size;
  173.     hepp = tbl->ht_addr;
  174.     for (idx = 0; idx < tblsize; idx++) {
  175.         for (hp = hepp[idx]; hp != NULL; hp = next) {
  176.             next = hp->he_next;
  177.             hp->he_next = NULL;
  178.             hefree(hp);
  179.         }
  180.         hepp[idx] = NULL;
  181.     }
  182.     tbl->ht_magic = 0;        /* de-certify this table */
  183.     tbl->ht_addr = NULL;
  184.     free((char *)tbl);
  185. }
  186.  
  187. /*
  188.  * The returned value is the address of the pointer that refers to the
  189.  * found object.  Said pointer may be NULL if the object was not found;
  190.  * if so, this pointer should be updated with the address of the object
  191.  * to be inserted, if insertion is desired.
  192.  */
  193. static HASHENT **
  194. hdbmfind(tbl, key)
  195. register HASHTABLE *tbl;
  196. HDBMDATUM key;
  197. {
  198.     register HASHENT *hp, *prevhp = NULL;
  199.     register char *hpkeydat, *keydat = key.dat_ptr;
  200.     register int keylen = key.dat_len;
  201.     register HASHENT **hepp;
  202.     register unsigned size; 
  203.  
  204.     if (BADTBL(tbl))
  205.         return NULL;
  206.     size = tbl->ht_size;
  207.     if (size == 0)            /* paranoia: avoid division by zero */
  208.         size = 1;
  209.     hepp = &tbl->ht_addr[(*tbl->ht_hash)(key) % size];
  210.     for (hp = *hepp; hp != NULL; prevhp = hp, hp = hp->he_next) {
  211.         hpkeydat = hp->he_key.dat_ptr;
  212.         if (hp->he_key.dat_len == keylen && hpkeydat[0] == keydat[0] &&
  213.             memcmp(hpkeydat, keydat, keylen) == 0)
  214.             break;
  215.     }
  216.     /* assert: *(returned value) == hp */
  217.     return (prevhp == NULL? hepp: &prevhp->he_next);
  218. }
  219.  
  220. static HASHENT *
  221. healloc()                    /* allocate a hash entry */
  222. {
  223.     register HASHENT *hp;
  224.  
  225.     if (hereuse == NULL)
  226.         return (HASHENT *)malloc(sizeof(HASHENT));
  227.     /* pull the first reusable one off the pile */
  228.     hp = hereuse;
  229.     hereuse = hereuse->he_next;
  230.     hp->he_next = NULL;            /* prevent accidents */
  231.     reusables--;
  232.     return hp;
  233. }
  234.  
  235. int
  236. hdbmstore(tbl, key, data)
  237. register HASHTABLE *tbl;
  238. HDBMDATUM key, data;
  239. {
  240.     register HASHENT *hp;
  241.     register HASHENT **nextp;
  242.  
  243.     if (BADTBL(tbl))
  244.         return NO;
  245.     nextp = hdbmfind(tbl, key);
  246.     if (nextp == NULL)
  247.         return NO;
  248.     hp = *nextp;
  249.     if (hp == NULL) {            /* absent; allocate an entry */
  250.         hp = healloc();
  251.         if (hp == NULL)
  252.             return NO;
  253.         hp->he_next = NULL;
  254.         hp->he_key = key;
  255.         *nextp = hp;            /* append to hash chain */
  256.     }
  257.     hp->he_data = data;    /* supersede any old data for this key */
  258.     return YES;
  259. }
  260.  
  261. /* return any existing entry for key; otherwise call allocator to make one */
  262. HDBMDATUM
  263. hdbmentry(tbl, key, allocator)
  264. register HASHTABLE *tbl;
  265. HDBMDATUM key;
  266. HDBMDATUM (*allocator)();
  267. {
  268.     register HASHENT *hp;
  269.     register HASHENT **nextp;
  270.     static HDBMDATUM errdatum = { NULL, 0 };
  271.  
  272.     if (BADTBL(tbl))
  273.         return errdatum;
  274.     nextp = hdbmfind(tbl, key);
  275.     if (nextp == NULL)
  276.         return errdatum;
  277.     hp = *nextp;
  278.     if (hp == NULL) {            /* absent; allocate an entry */
  279.         hp = healloc();
  280.         if (hp == NULL)
  281.             return errdatum;
  282.         hp->he_next = NULL;
  283.         hp->he_key = key;
  284.         hp->he_data = (*allocator)(key);
  285.         *nextp = hp;            /* append to hash chain */
  286.     }
  287.     return hp->he_data;
  288. }
  289.  
  290. int
  291. hdbmdelete(tbl, key)
  292. register HASHTABLE *tbl;
  293. HDBMDATUM key;
  294. {
  295.     register HASHENT *hp;
  296.     register HASHENT **nextp;
  297.  
  298.     nextp = hdbmfind(tbl, key);
  299.     if (nextp == NULL)
  300.         return NO;
  301.     hp = *nextp;
  302.     if (hp == NULL)                /* absent */
  303.         return NO;
  304.     *nextp = hp->he_next;            /* skip this entry */
  305.     hp->he_next = NULL;
  306.     hp->he_data.dat_ptr = hp->he_key.dat_ptr = NULL;
  307.     hefree(hp);
  308.     return YES;
  309. }
  310.  
  311. HDBMDATUM                    /* data corresponding to key */
  312. hdbmfetch(tbl, key)
  313. register HASHTABLE *tbl;
  314. HDBMDATUM key;
  315. {
  316.     register HASHENT *hp;
  317.     register HASHENT **nextp;
  318.     static HDBMDATUM errdatum = { NULL, 0 };
  319.  
  320.     if (BADTBL(tbl))
  321.         return errdatum;
  322.     nextp = hdbmfind(tbl, key);
  323.     if (nextp == NULL)
  324.         return errdatum;
  325.     hp = *nextp;
  326.     if (hp == NULL)                /* absent */
  327.         return errdatum;
  328.     else
  329.         return hp->he_data;
  330. }
  331.  
  332. /*
  333.  * visit each entry by calling nodefunc at each, with key, data and hook as
  334.  * arguments.  hook is an attempt to allow side-effects and reentrancy at
  335.  * the same time.
  336.  */
  337. hdbmwalk(tbl, nodefunc, hook)
  338. HASHTABLE *tbl;
  339. register int (*nodefunc)();
  340. register char *hook;                /* (void *) really */
  341. {
  342.     register unsigned idx;
  343.     register HASHENT *hp;
  344.     register HASHENT **hepp;
  345.     register int tblsize;
  346.  
  347.     if (BADTBL(tbl))
  348.         return;
  349.     hepp = tbl->ht_addr;
  350.     tblsize = tbl->ht_size;
  351.     for (idx = 0; idx < tblsize; idx++)
  352.         for (hp = hepp[idx]; hp != NULL; hp = hp->he_next)
  353.             (*nodefunc)(hp->he_key, hp->he_data, hook);
  354. }
  355.