home *** CD-ROM | disk | FTP | other *** search
/ ftptest.leeds.ac.uk / 2015.02.ftptest.leeds.ac.uk.tar / ftptest.leeds.ac.uk / bionet / CAE-GROUP / SCL-WIN3x / SCL.EXE / SCL_HASH.C < prev    next >
C/C++ Source or Header  |  1994-10-14  |  10KB  |  403 lines
  1. static char rcsid[] = "$Id: scl_hash.c,v 2.0.1.0 1994/02/04 21:32:27 sauderd Exp $";
  2.  
  3. /*
  4.  * Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson.
  5.  * Coded into C, with minor code improvements, and with hsearch(3) interface, 
  6.  * by ejp@ausmelb.oz, Jul 26, 1988: 13:16;
  7.  * also, hcreate/hdestroy routines added to simulate hsearch(3).
  8.  */
  9.  
  10. #include <scl_hash.h>
  11. #include <stdio.h> 
  12. #include <malloc.h>
  13. #include <string.h>
  14. #include <stdlib.h>
  15.  
  16. /*************/
  17. /* constants */
  18. /*************/
  19.  
  20. #define NULL            0
  21. #define HASH_NULL        (Hash_Table)NULL
  22.  
  23. #define SEGMENT_SIZE        256
  24. #define SEGMENT_SIZE_SHIFT    8    /* log2(SEGMENT_SIZE)    */
  25. #define PRIME1            37
  26. #define PRIME2            1048583
  27. #define MAX_LOAD_FACTOR    5
  28.  
  29. void *malloc(unsigned);
  30. void *calloc(unsigned,unsigned);
  31.  
  32. /************/
  33. /* typedefs */
  34. /************/
  35.  
  36. typedef unsigned long Address;
  37.  
  38. /******************************/
  39. /* macro function definitions */
  40. /******************************/
  41.  
  42. /*
  43. ** Fast arithmetic, relying on powers of 2
  44. */
  45.  
  46. #define MUL(x,y)        ((x) << (y##_SHIFT))
  47. #define DIV(x,y)        ((x) >> (y##_SHIFT))
  48. #define MOD(x,y)        ((x) & ((y)-1))
  49.  
  50. #define HASH_Table_new()    malloc(sizeof(struct Hash_Table))
  51. #define HASH_Table_destroy(x)    free(x)
  52. #define HASH_Element_new()    malloc(sizeof(struct Element))
  53. #define HASH_Element_destroy(x)    free(x)
  54.  
  55. typedef struct Element *Element;
  56. typedef struct Hash_Table *Hash_Table;
  57.  
  58. /*
  59. ** Internal routines
  60. */
  61.  
  62. Address        HASHhash(char*, Hash_Table);
  63. static void    HASHexpand_table(Hash_Table);
  64.  
  65. # if HASH_STATISTICS
  66. static long        HashAccesses, HashCollisions;
  67. # endif
  68.  
  69. void *
  70. HASHfind(Hash_Table t,char *s)
  71. {
  72.     struct Element e;
  73.     struct Element *ep;
  74.  
  75.     e.key = s;
  76.     ep = HASHsearch(t,&e,HASH_FIND);
  77.     return(ep?ep->data:0);
  78. }
  79.  
  80. void
  81. HASHinsert(Hash_Table t,char *s,void *data)
  82. {
  83.     struct Element e, *e2;
  84.  
  85.     e.key = s;
  86.     e.data = data;
  87.     e2 = HASHsearch(t,&e,HASH_INSERT);
  88.     
  89. }
  90.  
  91. Hash_Table
  92. HASHcreate(unsigned count)
  93. {
  94.     register int        i;
  95.     Hash_Table    table;
  96.  
  97.     /*
  98.     ** Adjust Count to be nearest higher power of 2, 
  99.     ** minimum SEGMENT_SIZE, then convert into segments.
  100.     */
  101.     i = SEGMENT_SIZE;
  102.     while (i < count)
  103.     i <<= 1;
  104.     count = DIV(i, SEGMENT_SIZE);
  105.  
  106.     table = HASH_Table_new();
  107.     table->SegmentCount = table->p = table->KeyCount = 0;
  108.     /*
  109.     ** Allocate initial 'i' segments of buckets
  110.     */
  111.     for (i = 0; i < count; i++)
  112.     table->Directory[i] = calloc(SEGMENT_SIZE,sizeof(Element));
  113.  
  114.     table->SegmentCount = count;
  115.     table->maxp = MUL(count, SEGMENT_SIZE);
  116.     table->MinLoadFactor = 1;
  117.     table->MaxLoadFactor = MAX_LOAD_FACTOR;
  118.  
  119. # if HASH_STATISTICS
  120.     HashAccesses = HashCollisions = 0;
  121. # endif
  122.     return(table);
  123. }
  124.  
  125. /* initialize pointer to beginning of hash table so we can step through it */
  126. /* on repeated calls to HASHlist - DEL */
  127. void
  128. HASHlistinit(Hash_Table table,HashEntry *he)
  129. {
  130.     he->i = he->j = 0;
  131.     he->p = 0;
  132.     he->table = table;
  133.     he->type = '*';
  134. }
  135.  
  136. void
  137. HASHlistinit_by_type(Hash_Table table,HashEntry *he,char type)
  138. {
  139.     he->i = he->j = 0;
  140.     he->p = 0;
  141.     he->table = table;
  142.     he->type = type;
  143. }
  144.  
  145. /* provide a way to step through the hash */
  146. struct Element *
  147. HASHlist(HashEntry *he)
  148. {
  149.     register int i2 = he->i;
  150.     register int j2 = he->j;
  151.     struct Element **s;
  152.  
  153.     he->e = 0;
  154.  
  155.     for (he->i = i2; he->i < he->table->SegmentCount; he->i++) {
  156.         /* test probably unnecessary    */
  157.         if ((s = he->table->Directory[he->i]) != NULL) {
  158.         for (he->j = j2; he->j < SEGMENT_SIZE; he->j++) {
  159.             if (!he->p) he->p = s[he->j];
  160.  
  161.             /* if he->p is defined, prepare to return it (by
  162.                setting it to he->e) and begin looking for a new value
  163.                for he->p
  164.              */
  165.         retry:
  166.             if (he->p) {
  167.                 if ((he->type != '*') &&
  168.                     (he->type != he->p->type)) {
  169.                     he->p = he->p->next;
  170.                     goto retry;
  171.                 }
  172.                 if (he->e) return(he->e);
  173.                 he->e = he->p;
  174.                 he->p = he->p->next;
  175.             }
  176.  
  177.             /* avoid incrementing he->j by returning here */
  178.             if (he->p) return(he->e);
  179.             }
  180.         j2 = 0;
  181.        }
  182.     }
  183.     /* if he->e was set then it is last one */
  184.     return(he->e);
  185. }
  186.  
  187. void
  188. HASHdestroy(Hash_Table table)
  189. {
  190.     register int        i, j;
  191.     struct Element **s;
  192.     struct Element *p, *q;
  193.  
  194.     if (table != HASH_NULL) {
  195.     for (i = 0; i < table->SegmentCount; i++) {
  196.         /* test probably unnecessary    */
  197.         if ((s = table->Directory[i]) != NULL) {
  198.         for (j = 0; j < SEGMENT_SIZE; j++) {
  199.             p = s[j];
  200.             while (p != NULL) {
  201.             q = p->next;
  202.             HASH_Element_destroy(p);
  203.             p = q;
  204.             }
  205.             free(table->Directory[i]);
  206.         }
  207.         }
  208.     }
  209.     HASH_Table_destroy(table);
  210.     }
  211. }
  212.  
  213. struct Element *
  214. HASHsearch(Hash_Table table, struct Element *item, Action action)
  215. {
  216.     Address    h;
  217.     struct Element **CurrentSegment;
  218.     int        SegmentIndex;
  219.     int        SegmentDir;
  220.     struct Element **p;
  221.     struct Element *q;
  222.     struct Element *deleteme;
  223.  
  224. # if HASH_STATISTICS
  225.     HashAccesses++;
  226. # endif
  227.     h = HASHhash(item->key, table);
  228.     SegmentDir = DIV(h, SEGMENT_SIZE);
  229.     SegmentIndex = MOD(h, SEGMENT_SIZE);
  230.     /*
  231.     ** valid segment ensured by HASHhash()
  232.     */
  233.     CurrentSegment = table->Directory[SegmentDir];
  234.     p = CurrentSegment + SegmentIndex;
  235.     q = *p;
  236.     /*
  237.     ** Follow collision chain
  238.     ** Now and after we finish this loop
  239.     **    p = &element, and
  240.     **    q = element
  241.     */
  242.     while (q != NULL && strcmp(q->key, item->key))
  243.     {
  244.     p = &q->next;
  245.     q = *p;
  246. # if HASH_STATISTICS
  247.     HashCollisions++;
  248. # endif
  249.     }
  250.     /* at this point, we have either found the element or it doesn't exist */
  251.   switch (action) {
  252.   case HASH_FIND:
  253.     return((struct Element *)q);
  254.   case HASH_DELETE:
  255.     if (!q) return(0);
  256.     /* at this point, element exists and action == DELETE */
  257.     deleteme = q;
  258.     *p = q->next;
  259.     /*STRINGfree(deleteme->key);*/
  260.     HASH_Element_destroy(deleteme);
  261.     --table->KeyCount;
  262.     return(deleteme);    /* of course, user shouldn't deref this! */
  263.   case HASH_INSERT:
  264.     /* if trying to insert it (twice), let them know */
  265.     if (q != NULL) return(q); /* was return(0);!!!!!?!?! */
  266.  
  267.     /* at this point, element does not exist and action == INSERT */
  268.     q = HASH_Element_new();
  269.     *p = q;                /* link into chain    */
  270.     /*
  271.     ** Initialize new element
  272.     */
  273. /* I don't see the point of copying the key!!!! */
  274. /*    q->key = STRINGcopy(item->key);*/
  275.     q->key = item->key;
  276.     q->data = item->data;
  277.     q->symbol = item->symbol;
  278.     q->type = item->type;
  279.     q->next = NULL;
  280.     /*
  281.     ** table over-full?
  282.     */
  283.     if (++table->KeyCount / MUL(table->SegmentCount, SEGMENT_SIZE) > table->MaxLoadFactor)
  284.     HASHexpand_table(table);        /* doesn't affect q    */
  285.   }
  286.   return((struct Element *)0);    /* was return (Element)q */
  287. }
  288.  
  289. /*
  290. ** Internal routines
  291. */
  292.  
  293. Address
  294. HASHhash(char* Key, Hash_Table table)
  295. {
  296.     Address        h, address;
  297.     register unsigned char    *k = (unsigned char*)Key;
  298.  
  299.     h = 0;
  300.     /*
  301.     ** Convert string to integer
  302.     */
  303.     /*SUPPRESS 112*/
  304.     while (*k)
  305.     /*SUPPRESS 8*/    /*SUPPRESS 112*/
  306.     h = h*PRIME1 ^ (*k++ - ' ');
  307.     h %= PRIME2;
  308.     address = MOD(h, table->maxp);
  309.     if (address < table->p)
  310.     address = MOD(h, (table->maxp << 1));    /* h % (2*table->maxp)    */
  311.     return(address);
  312. }
  313.  
  314. static
  315. void
  316. HASHexpand_table(Hash_Table table)
  317. {
  318.     Address    NewAddress;
  319.     int        OldSegmentIndex, NewSegmentIndex;
  320.     int        OldSegmentDir, NewSegmentDir;
  321.     struct Element **OldSegment, **NewSegment;
  322.     struct Element *Current, **Previous, **LastOfNew;
  323.  
  324.     if (table->maxp + table->p < MUL(DIRECTORY_SIZE, SEGMENT_SIZE)) {
  325.     /*
  326.     ** Locate the bucket to be split
  327.     */
  328.     OldSegmentDir = DIV(table->p, SEGMENT_SIZE);
  329.     OldSegment = table->Directory[OldSegmentDir];
  330.     OldSegmentIndex = MOD(table->p, SEGMENT_SIZE);
  331.     /*
  332.     ** Expand address space; if necessary create a new segment
  333.     */
  334.     NewAddress = table->maxp + table->p;
  335.     NewSegmentDir = DIV(NewAddress, SEGMENT_SIZE);
  336.     NewSegmentIndex = MOD(NewAddress, SEGMENT_SIZE);
  337.     if (NewSegmentIndex == 0)
  338.         table->Directory[NewSegmentDir] = calloc(SEGMENT_SIZE,sizeof(struct Element));
  339.     NewSegment = table->Directory[NewSegmentDir];
  340.     /*
  341.     ** Adjust state variables
  342.     */
  343.     table->p++;
  344.     if (table->p == table->maxp) {
  345.         table->maxp <<= 1;    /* table->maxp *= 2    */
  346.         table->p = 0;
  347.     }
  348.     table->SegmentCount++;
  349.     /*
  350.     ** Relocate records to the new bucket
  351.     */
  352.     Previous = &OldSegment[OldSegmentIndex];
  353.     Current = *Previous;
  354.     LastOfNew = &NewSegment[NewSegmentIndex];
  355.     *LastOfNew = NULL;
  356.     while (Current != NULL) {
  357.         if (HASHhash(Current->key, table) == NewAddress) {
  358.         /*
  359.         ** Attach it to the end of the new chain
  360.         */
  361.         *LastOfNew = Current;
  362.         /*
  363.         ** Remove it from old chain
  364.         */
  365.         *Previous = Current->next;
  366.         LastOfNew = &Current->next;
  367.         Current = Current->next;
  368.         *LastOfNew = NULL;
  369.         } else {
  370.         /*
  371.         ** leave it on the old chain
  372.         */
  373.         Previous = &Current->next;
  374.         Current = Current->next;
  375.         }
  376.     }
  377.     }
  378. }
  379.  
  380. /* following code is for testing hash package */
  381. #ifdef HASHTEST
  382. struct Element e1, e2, e3, *e;
  383. struct Hash_Table *t;
  384. HashEntry he;
  385.  
  386. main()
  387. {
  388.     e1.key = "foo";        e1.data = (char *)1;
  389.     e2.key = "bar";        e2.data = (char *)2;
  390.     e3.key = "herschel";    e3.data = (char *)3;
  391.  
  392.     t = HASHcreate(100);
  393.     e = HASHsearch(t,&e1,HASH_INSERT);
  394.     e = HASHsearch(t,&e2,HASH_INSERT);
  395.     e = HASHsearch(t,&e3,HASH_INSERT);
  396.     HASHlistinit(t,&he);
  397.     for (;;) {
  398.         e = HASHlist(&he);
  399.         
  400.     }
  401. }
  402. #endif
  403.