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 / FED_PLUS.EXE / HASH.C < prev    next >
C/C++ Source or Header  |  1994-07-23  |  14KB  |  549 lines
  1. static char rcsid[] = "$Id: hash.c,v 1.6 1994/03/23 20:06:51 libes 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.  * move to local hash table, cleanup abstraction and storage allocation;
  10.  * convert to ANSII C.
  11.  * by snc (clark@cme.nbs.gov), 10-Mar-1989
  12.  *
  13.  * these routines simulate hsearch(3) and family, with the important
  14.  * difference that the hash table is dynamic - can grow indefinitely
  15.  * beyond its original size (as supplied to hcreate()).
  16.  *
  17.  * Performance appears to be comparable to that of hsearch(3).
  18.  * The 'source-code' options referred to in hsearch(3)'s 'man' page
  19.  * are not implemented; otherwise functionality is identical.
  20.  *
  21.  * Compilation controls:
  22.  * HASH_DEBUG controls some informative traces, mainly for debugging.
  23.  * HASH_STATISTICS causes HashAccesses and HashCollisions to be maintained;
  24.  * when combined with HASH_DEBUG, these are displayed by hdestroy().
  25.  *
  26.  * Problems & fixes to ejp@ausmelb.oz. WARNING: relies on pre-processor
  27.  * concatenation property, in probably unnecessary code 'optimisation'.
  28.  *
  29.  * snc: fixed concatenation for ANSII C, 10-Mar-1989
  30.  *
  31.  * $Log: hash.c,v $
  32.  * Revision 1.6  1994/03/23  20:06:51  libes
  33.  * botched free in hash destroy
  34.  *
  35.  * Revision 1.5  1993/10/15  18:49:55  libes
  36.  * CADDETC certified
  37.  *
  38.  * Revision 1.4  1992/08/18  18:27:10  libes
  39.  * changed DEBUG to HASH_DEBUG
  40.  *
  41.  * Revision 1.3  1992/08/18  17:16:22  libes
  42.  * rm'd extraneous error messages
  43.  *
  44.  * Revision 1.2  1992/05/31  08:37:18  libes
  45.  * multiple files
  46.  *
  47.  * Revision 1.1  1992/05/28  03:56:55  libes
  48.  * Initial revision
  49.  *
  50.  * Revision 1.4  1992/05/14  10:15:04  libes
  51.  * don't remember
  52.  *
  53.  * Revision 1.3  1992/02/12  07:06:49  libes
  54.  * y
  55.  * y
  56.  * do sub/supertype
  57.  *
  58.  * Revision 1.2  1992/02/09  00:51:02  libes
  59.  * does ref/use correctly
  60.  *
  61.  * Revision 1.1  1992/02/05  08:34:24  libes
  62.  * Initial revision
  63.  *
  64.  * Revision 1.0.1.1  1992/01/22  02:40:04  libes
  65.  * copied from ~pdes
  66.  *
  67.  * Revision 1.9  1992/01/22  02:26:58  libes
  68.  * added code to test hash package
  69.  *
  70.  * Revision 1.8  1991/09/17  02:53:23  libes
  71.  * fixed bug in HASHcopy (new hash tables were coming out empty)
  72.  *
  73.  * Revision 1.7  1991/08/30  16:34:36  libes
  74.  * fixed HASHlist to use state from parameter instead of static
  75.  *
  76.  * Revision 1.6  1991/08/13  22:19:39  libes
  77.  * forgot to declare s, s2, pp, and q.  Oops.
  78.  *
  79.  * Revision 1.5  1991/08/06  19:03:07  libes
  80.  * fixed bugs relating to my previous addition (delete function)
  81.  * added HASHcopy to support DICT_copy via OBJcopy
  82.  *
  83.  * Revision 1.4  1991/07/19  03:57:46  libes
  84.  * added action HASH_DELETE
  85.  * made action HASH_INSERT return failure upon duplicate entry
  86.  *
  87.  * Revision 1.3  1991/02/26  19:40:45  libes
  88.  * Added functions for visiting every member of the hash table, to duplicate
  89.  * similar functionality of linked lists.  Note that current implementation
  90.  * can only walk through one hash table at a time.  This can be improved, but
  91.  * the application code doesn't currently need such a feature.
  92.  *
  93.  * Revision 1.2  1990/09/06  11:06:56  clark
  94.  * BPR 2.1 alpha
  95.  *
  96.  * Revision 1.1  90/06/11  16:44:43  clark
  97.  * Initial revision
  98.  * 
  99.  */
  100.  
  101. #define HASH_C
  102. #include "hash.h"
  103. #include <string.h>
  104. /*
  105. ** Internal routines
  106. */
  107.  
  108. static_inline Address    HASHhash(char*, Hash_Table);
  109. static void        HASHexpand_table(Hash_Table);
  110.  
  111. /*
  112. ** Local data
  113. */
  114.  
  115. # if HASH_STATISTICS
  116. static long        HashAccesses, HashCollisions;
  117. # endif
  118.  
  119. /*
  120. ** Code
  121. */
  122.  
  123. void
  124. HASHinitialize()
  125. {
  126.     MEMinitialize(&HASH_Table_fl,sizeof(struct Hash_Table),50,50);
  127.     MEMinitialize(&HASH_Element_fl,sizeof(struct Element),500,100);
  128. }
  129.  
  130. Hash_Table
  131. HASHcreate(unsigned count)
  132. {
  133.     int        i;
  134.     Hash_Table    table;
  135.  
  136.     /*
  137.     ** Adjust Count to be nearest higher power of 2, 
  138.     ** minimum SEGMENT_SIZE, then convert into segments.
  139.     */
  140.     i = SEGMENT_SIZE;
  141.     while (i < count)
  142.     i <<= 1;
  143.     count = DIV(i, SEGMENT_SIZE);
  144.  
  145.     table = HASH_Table_new();
  146. #if 0
  147.     table->in_use = 0;
  148. #endif
  149.     table->SegmentCount = table->p = table->KeyCount = 0;
  150.     /*
  151.     ** Allocate initial 'i' segments of buckets
  152.     */
  153.     for (i = 0; i < count; i++)
  154.     CALLOC(table->Directory[i], SEGMENT_SIZE, Element)
  155.         /*,   "segment in HASHcreate");*/
  156.  
  157.     table->SegmentCount = count;
  158.     table->maxp = MUL(count, SEGMENT_SIZE);
  159.     table->MinLoadFactor = 1;
  160.     table->MaxLoadFactor = MAX_LOAD_FACTOR;
  161. # if HASH_DEBUG
  162.     fprintf(stderr, 
  163.         "[HASHcreate] table %x count %d maxp %d SegmentCount %d\n", 
  164.         table, 
  165.         count, 
  166.         table->maxp, 
  167.         table->SegmentCount);
  168. # endif
  169. # if HASH_STATISTICS
  170.     HashAccesses = HashCollisions = 0;
  171. # endif
  172.     return(table);
  173. }
  174.  
  175. /* initialize pointer to beginning of hash table so we can step through it */
  176. /* on repeated calls to HASHlist - DEL */
  177. void
  178. HASHlistinit(Hash_Table table,HashEntry *he)
  179. {
  180.     he->i = he->j = 0;
  181.     he->p = 0;
  182.     he->table = table;
  183.     he->type = '*';
  184. #if 0
  185.     table->in_use = 1;
  186. #endif
  187. }
  188.  
  189. void
  190. HASHlistinit_by_type(Hash_Table table,HashEntry *he,char type)
  191. {
  192.     he->i = he->j = 0;
  193.     he->p = 0;
  194.     he->table = table;
  195.     he->type = type;
  196. #if 0
  197.     table->in_use = 1;
  198. #endif
  199. }
  200.  
  201. #if 0
  202. /* if you don't step to the end, you can clear the flag this way */
  203. void
  204. HASHlistend(HashEntry *he)
  205. {
  206.     he->table->in_use = 0;
  207. }
  208. #endif
  209.  
  210. /* provide a way to step through the hash */
  211. Element
  212. HASHlist(HashEntry *he)
  213. {
  214.     int i2 = he->i;
  215.     int j2 = he->j;
  216.     Segment s;
  217.  
  218.     he->e = 0;
  219.  
  220.     for (he->i = i2; he->i < he->table->SegmentCount; he->i++) {
  221.         /* test probably unnecessary    */
  222.         if ((s = he->table->Directory[he->i]) != NULL) {
  223.         for (he->j = j2; he->j < SEGMENT_SIZE; he->j++) {
  224.             if (!he->p) he->p = s[he->j];
  225.  
  226.             /* if he->p is defined, prepare to return it (by
  227.                setting it to he->e) and begin looking for a new value
  228.                for he->p
  229.              */
  230.         retry:
  231.             if (he->p) {
  232.                 if ((he->type != '*') &&
  233.                     (he->type != he->p->type)) {
  234.                     he->p = he->p->next;
  235.                     goto retry;
  236.                 }
  237.                 if (he->e) return(he->e);
  238.                 he->e = he->p;
  239.                 he->p = he->p->next;
  240.             }
  241.  
  242.             /* avoid incrementing he->j by returning here */
  243.             if (he->p) return(he->e);
  244.             }
  245.         j2 = 0;
  246.        }
  247.     }
  248.     /* if he->e was set then it is last one */
  249. #if 0
  250.     he->table->in_use = 0;
  251. #endif
  252.     return(he->e);
  253. }
  254.  
  255. #if 0
  256. /* this verifies no one else is walking through the table that we might screw up */
  257. /* it should be called before adding, deleting or destroying a table */
  258. HASH_in_use(Hash_Table table,char *action)
  259. {
  260.     fprintf(stderr,"HASH: attempted to %s but hash table in use\n",action);
  261. }
  262. #endif
  263.  
  264. void
  265. HASHdestroy(Hash_Table table)
  266. {
  267.     int        i, j;
  268.     Segment    s;
  269.     Element    p, q;
  270.  
  271.     if (table != HASH_NULL) {
  272. #if 0
  273.     if (table->in_use) HASH_in_use(table,"destroy hash table");
  274. #endif
  275.     for (i = 0; i < table->SegmentCount; i++) {
  276.         /* test probably unnecessary    */
  277.         if ((s = table->Directory[i]) != NULL) {
  278.         for (j = 0; j < SEGMENT_SIZE; j++) {
  279.             p = s[j];
  280.             while (p != NULL) {
  281.             q = p->next;
  282.             HASH_Element_destroy(p);
  283.             p = q;
  284.             }
  285.         }
  286.         free(table->Directory[i]);
  287.         }
  288.     }
  289.     HASH_Table_destroy(table);
  290. # if HASH_STATISTICS && HASH_DEBUG
  291.     fprintf(stderr, 
  292.         "[hdestroy] Accesses %ld Collisions %ld\n", 
  293.         HashAccesses, 
  294.         HashCollisions);
  295. # endif
  296.     }
  297. }
  298.  
  299. Element
  300. HASHsearch(Hash_Table table, Element item, Action action)
  301. {
  302.     Address    h;
  303.     Segment    CurrentSegment;
  304.     int        SegmentIndex;
  305.     int        SegmentDir;
  306.     Segment    p;
  307.     Element    q;
  308.     Element    deleteme;
  309.  
  310.     assert(table != HASH_NULL);    /* Kinder really than return(NULL); */
  311. # if HASH_STATISTICS
  312.     HashAccesses++;
  313. # endif
  314.     h = HASHhash(item->key, table);
  315.     SegmentDir = DIV(h, SEGMENT_SIZE);
  316.     SegmentIndex = MOD(h, SEGMENT_SIZE);
  317.     /*
  318.     ** valid segment ensured by HASHhash()
  319.     */
  320.     CurrentSegment = table->Directory[SegmentDir];
  321.     assert(CurrentSegment != NULL);    /* bad failure if tripped    */
  322.     p = CurrentSegment + SegmentIndex;
  323.     q = *p;
  324.     /*
  325.     ** Follow collision chain
  326.     ** Now and after we finish this loop
  327.     **    p = &element, and
  328.     **    q = element
  329.     */
  330.     while (q != NULL && strcmp(q->key, item->key))
  331.     {
  332.     p = &q->next;
  333.     q = *p;
  334. # if HASH_STATISTICS
  335.     HashCollisions++;
  336. # endif
  337.     }
  338.     /* at this point, we have either found the element or it doesn't exist */
  339.   switch (action) {
  340.   case HASH_FIND:
  341.     return((Element)q);
  342.   case HASH_DELETE:
  343.     if (!q) return(0);
  344.     /* at this point, element exists and action == DELETE */
  345. #if 0
  346.     if (table->in_use) HASH_in_use(table,"insert element");
  347. #endif
  348.     deleteme = q;
  349.     *p = q->next;
  350.     /*STRINGfree(deleteme->key);*/
  351.     HASH_Element_destroy(deleteme);
  352.     --table->KeyCount;
  353.     return(deleteme);    /* of course, user shouldn't deref this! */
  354.   case HASH_INSERT:
  355.     /* if trying to insert it (twice), let them know */
  356.     if (q != NULL) return(q); /* was return(0);!!!!!?!?! */
  357.  
  358. #if 0
  359.     if (table->in_use) HASH_in_use(table,"delete element");
  360. #endif
  361.     /* at this point, element does not exist and action == INSERT */
  362.     q = HASH_Element_new();
  363.     *p = q;                /* link into chain    */
  364.     /*
  365.     ** Initialize new element
  366.     */
  367. /* I don't see the point of copying the key!!!! */
  368. /*    q->key = STRINGcopy(item->key);*/
  369.     q->key = item->key;
  370.     q->data = item->data;
  371.     q->symbol = item->symbol;
  372.     q->type = item->type;
  373.     q->next = NULL;
  374.     /*
  375.     ** table over-full?
  376.     */
  377.     if (++table->KeyCount / MUL(table->SegmentCount, SEGMENT_SIZE) > table->MaxLoadFactor)
  378.     HASHexpand_table(table);        /* doesn't affect q    */
  379.   }
  380.   return((Element)0);    /* was return (Element)q */
  381. }
  382.  
  383. /*
  384. ** Internal routines
  385. */
  386.  
  387. static_inline
  388. Address
  389. HASHhash(char* Key, Hash_Table table)
  390. {
  391.     Address        h, address;
  392.     register unsigned char    *k = (unsigned char*)Key;
  393.  
  394.     h = 0;
  395.     /*
  396.     ** Convert string to integer
  397.     */
  398.     /*SUPPRESS 112*/
  399.     while (*k)
  400.     /*SUPPRESS 8*/    /*SUPPRESS 112*/
  401.     h = h*PRIME1 ^ (*k++ - ' ');
  402.     h %= PRIME2;
  403.     address = MOD(h, table->maxp);
  404.     if (address < table->p)
  405.     address = MOD(h, (table->maxp << 1));    /* h % (2*table->maxp)    */
  406.     return(address);
  407. }
  408.  
  409. static
  410. void
  411. HASHexpand_table(Hash_Table table)
  412. {
  413.     Address    NewAddress;
  414.     int        OldSegmentIndex, NewSegmentIndex;
  415.     int        OldSegmentDir, NewSegmentDir;
  416.     Segment    OldSegment, NewSegment;
  417.     Element    Current, *Previous, *LastOfNew;
  418.  
  419.     if (table->maxp + table->p < MUL(DIRECTORY_SIZE, SEGMENT_SIZE)) {
  420.     /*
  421.     ** Locate the bucket to be split
  422.     */
  423.     OldSegmentDir = DIV(table->p, SEGMENT_SIZE);
  424.     OldSegment = table->Directory[OldSegmentDir];
  425.     OldSegmentIndex = MOD(table->p, SEGMENT_SIZE);
  426.     /*
  427.     ** Expand address space; if necessary create a new segment
  428.     */
  429.     NewAddress = table->maxp + table->p;
  430.     NewSegmentDir = DIV(NewAddress, SEGMENT_SIZE);
  431.     NewSegmentIndex = MOD(NewAddress, SEGMENT_SIZE);
  432.     if (NewSegmentIndex == 0)
  433.         CALLOC(table->Directory[NewSegmentDir], SEGMENT_SIZE, Element);
  434.          /*  "segment in HASHexpand_table");*/
  435.     NewSegment = table->Directory[NewSegmentDir];
  436.     /*
  437.     ** Adjust state variables
  438.     */
  439.     table->p++;
  440.     if (table->p == table->maxp) {
  441.         table->maxp <<= 1;    /* table->maxp *= 2    */
  442.         table->p = 0;
  443.     }
  444.     table->SegmentCount++;
  445.     /*
  446.     ** Relocate records to the new bucket
  447.     */
  448.     Previous = &OldSegment[OldSegmentIndex];
  449.     Current = *Previous;
  450.     LastOfNew = &NewSegment[NewSegmentIndex];
  451.     *LastOfNew = NULL;
  452.     while (Current != NULL) {
  453.         if (HASHhash(Current->key, table) == NewAddress) {
  454.         /*
  455.         ** Attach it to the end of the new chain
  456.         */
  457.         *LastOfNew = Current;
  458.         /*
  459.         ** Remove it from old chain
  460.         */
  461.         *Previous = Current->next;
  462.         LastOfNew = &Current->next;
  463.         Current = Current->next;
  464.         *LastOfNew = NULL;
  465.         } else {
  466.         /*
  467.         ** leave it on the old chain
  468.         */
  469.         Previous = &Current->next;
  470.         Current = Current->next;
  471.         }
  472.     }
  473.     }
  474. }
  475.  
  476. /* make a complete copy of a hash table */
  477. /* Note that individual objects are shallow-copied.  OBJcopy is not called! */
  478. /* But then, it isn't called when objects are inserted/deleted so this seems */
  479. /* reasonable - DEL */
  480. Hash_Table
  481. HASHcopy(Hash_Table oldtable)
  482. {
  483.     Hash_Table newtable;
  484.     Segment s, s2;
  485.     Element *pp;    /* old element */
  486.     Element    *qq;    /* new element */
  487.     int i, j;
  488.  
  489.     newtable = HASH_Table_new();
  490.     for (i = 0; i < oldtable->SegmentCount; i++) {
  491.         CALLOC(newtable->Directory[i], SEGMENT_SIZE, Element);
  492.            /*    "segment in HASHcopy");*/
  493.     }
  494.  
  495.     newtable->p        = oldtable->p;
  496.     newtable->SegmentCount    = oldtable->SegmentCount;
  497.     newtable->maxp        = oldtable->maxp;
  498.     newtable->MinLoadFactor    = oldtable->MinLoadFactor;
  499.     newtable->MaxLoadFactor    = oldtable->MaxLoadFactor;
  500.     newtable->KeyCount    = oldtable->KeyCount;
  501.  
  502.     for (i=0; i<oldtable->SegmentCount; i++) {
  503.       /* test probably unnecessary */
  504.       if ((s = oldtable->Directory[i]) != NULL) {
  505.         s2 = newtable->Directory[i];
  506.         for (j = 0; j < SEGMENT_SIZE; j++) {
  507.           qq = &s2[j];
  508.           for (pp = &s[j];*pp;pp = &(*pp)->next) {
  509.         *qq = HASH_Element_new();
  510. /*        (*qq)->key = STRINGcopy((*pp)->key);*/
  511.         /* I really doubt it is necessary to copy the key!!! */
  512.         (*qq)->key = (*pp)->key;
  513.         (*qq)->data = (*pp)->data;
  514.         (*qq)->symbol = (*pp)->symbol;
  515.         (*qq)->type = (*pp)->type;
  516.         (*qq)->next = NULL;
  517.         qq = &((*qq)->next);
  518.           }
  519.             }
  520.           }
  521.         }
  522.     return(newtable);
  523. }
  524.  
  525. /* following code is for testing hash package */
  526. #ifdef HASHTEST
  527. struct Element e1, e2, e3, *e;
  528. struct Hash_Table *t;
  529. HashEntry he;
  530.  
  531. main()
  532. {
  533.     e1.key = "foo";        e1.data = (char *)1;
  534.     e2.key = "bar";        e2.data = (char *)2;
  535.     e3.key = "herschel";    e3.data = (char *)3;
  536.  
  537.     t = HASHcreate(100);
  538.     e = HASHsearch(t,&e1,HASH_INSERT);
  539.     e = HASHsearch(t,&e2,HASH_INSERT);
  540.     e = HASHsearch(t,&e3,HASH_INSERT);
  541.     HASHlistinit(t,&he);
  542.     for (;;) {
  543.         e = HASHlist(&he);
  544.         if (!e) exit(0);
  545.         printf("found key %s, data %d\n",e->key,(int)e->data);
  546.     }
  547. }
  548. #endif
  549.