home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / c / 18323 < prev    next >
Encoding:
Text File  |  1992-12-14  |  8.0 KB  |  333 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!europa.asd.contel.com!howland.reston.ans.net!usc!cs.utexas.edu!torn!newshub.ccs.yorku.ca!newshub.ccs.yorku.ca!oz
  3. From: oz@ursa.sis.yorku.ca (Ozan Yigit)
  4. Subject: Re: Need good hashing functions
  5. In-Reply-To: torek@horse.ee.lbl.gov's message of 10 Dec 1992 18: 31:03 GMT
  6. Message-ID: <OZ.92Dec14115806@ursa.sis.yorku.ca>
  7. Sender: news@newshub.ccs.yorku.ca (USENET News System)
  8. Organization: York U. Student Information Systems Project
  9. References: <1992Dec9.213041.16259@netcom.com> <1992Dec10.113732.4889@si.hhs.nl>
  10.     <27911@dog.ee.lbl.gov>
  11. Date: Mon, 14 Dec 1992 16:58:06 GMT
  12. Lines: 319
  13.  
  14. Chris Torek writes:
  15.     [most of the interesting hashing article elided]
  16.  
  17.    Incidentally, the same expansion technique can be used for any hash
  18.    method: it simply corresponds to moving all the entries from the old
  19.    hash table to the new, larger one.  This particular version has the
  20.    advantage of being compact.
  21.  
  22. Alternatively, one can use an algorithm that expands without re-hashing
  23. the entire table. Here is one based on the Larson article in CACM, that
  24. can be used instead of the inferior sV hsearch. [please share any fixes
  25. and improvements to this code]
  26.  
  27. enjoy...    oz
  28. ---
  29. With diligence, it is possible to | electric: oz@sis.yorku.ca
  30. make anything run slowly. -T.Duff | ph:[416] 736 2100 x 33976
  31. ----- snap here ----
  32. /*
  33.  * Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson.
  34.  * Coded into C, with minor code improvements, and with hsearch(3) interface,
  35.  * by ejp@ausmelb.oz, Jul 26, 1988: 13:16;
  36.  * also, hcreate/hdestroy routines added to simulate hsearch(3).
  37.  *
  38.  * These routines simulate hsearch(3) and family, with the important
  39.  * difference that the hash table is dynamic - can grow indefinitely
  40.  * beyond its original size (as supplied to hcreate()).
  41.  *
  42.  * Performance appears to be comparable to that of hsearch(3).
  43.  * The 'source-code' options referred to in hsearch(3)'s 'man' page
  44.  * are not implemented; otherwise functionality is identical.
  45.  *
  46.  * Compilation controls:
  47.  * DEBUG controls some informative traces, mainly for debugging.
  48.  * HASH_STATISTICS causes hashaccesses and hashcollisions to be maintained;
  49.  * when combined with DEBUG, these are displayed by hdestroy().
  50.  */
  51.  
  52. #include <stdio.h>
  53. #include <assert.h>
  54. #include <string.h>
  55. #include <search.h>
  56.  
  57. /* Constants */
  58. # define SEGSIZE    256    /* should be power of 2 for speed */
  59. # define DIRSIZE    256    /* should be power of 2 for speed */
  60. # define PRIME1        37
  61. # define PRIME2        1048583
  62. # define DEFMAXLD    5    /* default maximum load factor */
  63.  
  64. /* local data templates */
  65.  
  66. /*
  67.  * The user only sees the first two fields, as we pretend to pass
  68.  * back only a pointer to ENTRY. {S}he doesn't know what else is in here.
  69.  */
  70. typedef struct element {
  71.     char    *ekey;
  72.     char    *edata;
  73.     struct element *next;           /* secret from user */
  74. } element_t, *segment_t;
  75.  
  76. typedef struct {
  77.     unsigned short    p;        /* next bucket to be split */
  78.     unsigned short    maxp;        /* upper bound on p during expansion */
  79.     unsigned long    keycount;    /* current # keys */
  80.     unsigned short    segcount;    /* current # segments */
  81.     unsigned short    minload;    /* minimum load factor */
  82.     unsigned short    maxload;    /* maximum load factor */
  83.     segment_t * dir[DIRSIZE];
  84. } hashtbl;
  85.  
  86. typedef unsigned long addr_t;
  87.  
  88. /* external routines */
  89. extern char *calloc();
  90.  
  91. /* Entry points */
  92. extern int hcreate();
  93. extern void hdestroy();
  94. extern ENTRY *hsearch();
  95.  
  96. /* Internal routines */
  97. static addr_t hash();
  98. static void expandtbl();
  99.  
  100. /* Local data */
  101. static hashtbl *tbl = NULL;
  102. #if HASH_STATISTICS
  103. static long hashaccesses, hashcollisions, hashexpansions;
  104. #endif
  105.  
  106. int
  107. hcreate(count)
  108. unsigned count;
  109. {
  110.     register unsigned i;
  111.  
  112. /*
  113.  * Adjust count to be nearest higher power of 2, minimum SEGSIZE,
  114.  * then convert into segments.
  115.  */
  116.     for (i = SEGSIZE; i < count; i <<= 1)
  117.         ;
  118.  
  119.     count = i / SEGSIZE;
  120.  
  121.     tbl = (hashtbl *)calloc(1, sizeof(hashtbl));
  122.     if (tbl == NULL)
  123.         return 0;
  124.  
  125.     tbl->segcount = 0;
  126.     tbl->p = 0;
  127.     tbl->keycount = 0;
  128.  
  129. /* 
  130.  * Allocate initial 'i' segments of buckets 
  131.  */
  132.     for (i = 0; i < count; i++) {
  133.         tbl->dir[i] = (segment_t *)calloc(SEGSIZE, sizeof(segment_t));
  134.         if (tbl->dir[i] == NULL) {
  135.             hdestroy();
  136.             return 0;
  137.         }
  138.         tbl->segcount++;
  139.     }
  140.     tbl->maxp = count * SEGSIZE;
  141.     tbl->minload = 1;
  142.     tbl->maxload = DEFMAXLD;
  143.  
  144. # if DEBUG
  145.     fprintf(stderr, "hcreate: table %x count %d maxp %d segcount %d\n",
  146.         tbl, count, tbl->maxp, tbl->segcount);
  147. # endif
  148. # if HASH_STATISTICS
  149.     hashaccesses = hashcollisions = hashexpansions = 0;
  150. # endif
  151.     return 1;
  152. }
  153.  
  154. void
  155. hdestroy()
  156. {
  157.     int i, j;
  158.     segment_t * s;
  159.     element_t * p, *q;
  160.  
  161.     if (tbl != NULL) {
  162.         for (i = 0; i < tbl->segcount; i++) {
  163.             /* test probably unnecessary */
  164.             s = tbl->dir[i];
  165.             if (s != NULL)
  166.                 for (j = 0; j < SEGSIZE; j++) {
  167.                     p = s[j];
  168.                     while (p != NULL) {
  169.                         q = p->next;
  170.                         free((char *)p);
  171.                         p = q;
  172.                     }
  173.                     free(tbl->dir[i]);
  174.                 }
  175.         }
  176. # if HASH_STATISTICS && DEBUG
  177.         fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
  178.             hashaccesses, hashcollisions);
  179.         fprintf(stderr, "hdestroy: expansions %ld\n", hashexpansions);
  180.         fprintf(stderr, "keys %ld maxp %d segcount %d\n",
  181.             tbl->keycount, tbl->maxp, tbl->segcount);
  182. # endif
  183.         free(tbl);
  184.         tbl = NULL;
  185.     }
  186. }
  187.  
  188. ENTRY *
  189. hsearch(item, action)
  190. ENTRY item;
  191. ACTION action;                   /* FIND/ENTER */
  192. {
  193.     register addr_t h;
  194.     addr_t segidx, segdir;
  195.     segment_t * currseg;
  196.     segment_t * p, q;
  197.  
  198.     assert(tbl != NULL);           /* Kinder really than return(NULL); */
  199.  
  200. # if HASH_STATISTICS
  201.     hashaccesses++;
  202. # endif
  203.  
  204.     h = hash(item.key);
  205.     segdir = h / SEGSIZE;
  206.     segidx = h % SEGSIZE;
  207. /*
  208.  * valid segment_t ensured by hash()
  209.  */
  210.     currseg = tbl->dir[segdir];
  211.     assert(currseg != NULL);    /* bad failure if tripped */
  212.     p = &currseg[segidx];
  213.     q = *p;
  214. /*
  215.  * Follow collision chain
  216.  */
  217.     while (q != NULL && strcmp(q->ekey, item.key) != 0) {
  218.         p = &q->next;
  219.         q = *p;
  220. # if HASH_STATISTICS
  221.         hashcollisions++;
  222. # endif
  223.     }
  224.  
  225.     if (q != NULL ||            /* found */
  226.         action == FIND ||            /* not found, search only */
  227.         (q = (element_t *)calloc(1, sizeof(element_t))) == NULL) /* not found, no room */
  228.         return (ENTRY *)q;
  229.     *p = q;                    /* link into chain */
  230. /*
  231.  * Initialize new element
  232.  */
  233.     q->ekey = item.key;
  234.     q->edata = item.data;
  235.     /* cleared by calloc(3) q->next = NULL; */
  236.  
  237.     /* tbl over-full? */
  238.     if (++tbl->keycount / (tbl->segcount * SEGSIZE) > tbl->maxload)
  239.         expandtbl();            /* doesn't affect q */
  240.     return (ENTRY *)q;
  241. }
  242.  
  243. /*
  244.  * Internal routines
  245.  */
  246.  
  247. static addr_t
  248. hash(ekey)
  249. char *ekey;
  250. {
  251.     register unsigned char *k = (unsigned char *) ekey;
  252.     register addr_t h, address;
  253.  
  254.     h = 0;
  255. /*
  256.  * Convert string to integer
  257.  */
  258.     while (*k != '\0')
  259.         h = h * PRIME1 ^ (*k++ - ' ');
  260.     h %= PRIME2;
  261.     address = h % tbl->maxp;
  262.     if (address < tbl->p)
  263.         address = h % (2*tbl->maxp);
  264.     return address;
  265. }
  266.  
  267. static void
  268. expandtbl()
  269. {
  270.     register addr_t newaddr;
  271.     addr_t oldsegidx, newsegidx;
  272.     addr_t oldsegdir, newsegdir;
  273.     segment_t * oldseg, *newseg;
  274.     element_t * curr, **prev, **lastnew;
  275.  
  276. #ifdef HASH_STATISTICS
  277.     hashexpansions++;
  278. #endif
  279.     if (tbl->maxp + tbl->p < DIRSIZE * SEGSIZE) {
  280. /*
  281.  * Locate the bucket to be split
  282.  */
  283.         oldsegdir = tbl->p / SEGSIZE;
  284.         oldseg = tbl->dir[oldsegdir];
  285.         oldsegidx = tbl->p % SEGSIZE;
  286. /*
  287.  * Expand address space; if necessary create a new segment_t
  288.  */
  289.         newaddr = tbl->maxp + tbl->p;
  290.         newsegdir = newaddr / SEGSIZE;
  291.         newsegidx = newaddr % SEGSIZE;
  292.         if (newsegidx == 0)
  293.             tbl->dir[newsegdir] =
  294.                 (segment_t *)calloc(SEGSIZE, sizeof(segment_t));
  295.         newseg = tbl->dir[newsegdir];
  296. /*
  297.  * Adjust state variables
  298.  */
  299.         tbl->p++;
  300.         if (tbl->p == tbl->maxp) {
  301.             tbl->maxp <<= 1;    /* tbl->maxp *= 2 */
  302.             tbl->p = 0;
  303.         }
  304.         tbl->segcount++;
  305. /*
  306.  * Relocate records to the new bucket
  307.  */
  308.         prev = &oldseg[oldsegidx];
  309.         curr = *prev;
  310.         lastnew = &newseg[newsegidx];
  311.         *lastnew = NULL;
  312.         while (curr != NULL)
  313.             if (hash(curr->ekey) == newaddr) {
  314.                 /* Attach it to the end of the new chain */
  315.                 *lastnew = curr;
  316.         /*
  317.          * Remove it from old chain
  318.          */
  319.                 *prev = curr->next;
  320.                 lastnew = &curr->next;
  321.                 curr = curr->next;
  322.                 *lastnew = NULL;
  323.             } else {
  324.         /*
  325.          * leave it on the old chain
  326.          */
  327.                 prev = &curr->next;
  328.                 curr = curr->next;
  329.             }
  330.     }
  331. }
  332.  
  333.