home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume27 / bootp-2.2.B / part01 / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-11  |  10.0 KB  |  393 lines
  1. #ifndef _BLURB_
  2. #define _BLURB_
  3. /************************************************************************
  4.           Copyright 1988, 1991 by Carnegie Mellon University
  5.  
  6.                           All Rights Reserved
  7.  
  8. Permission to use, copy, modify, and distribute this software and its
  9. documentation for any purpose and without fee is hereby granted, provided
  10. that the above copyright notice appear in all copies and that both that
  11. copyright notice and this permission notice appear in supporting
  12. documentation, and that the name of Carnegie Mellon University not be used
  13. in advertising or publicity pertaining to distribution of the software
  14. without specific, written prior permission.
  15.  
  16. CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  17. SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
  18. IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  19. DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  20. PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  21. ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  22. SOFTWARE.
  23. ************************************************************************/
  24. #endif /* _BLURB_ */
  25.  
  26.  
  27. #ifndef lint
  28. static char rcsid[] = "$Header: /afs/andrew.cmu.edu/netdev/src/cmu/bootp-public/RCS/hash.c,v 1.3 1991/11/01 10:02:29 ww0n Exp ww0n $";
  29. #endif
  30.  
  31.  
  32. /*
  33.  * Generalized hash table ADT
  34.  *
  35.  * Provides multiple, dynamically-allocated, variable-sized hash tables on
  36.  * various data and keys.
  37.  *
  38.  * This package attempts to follow some of the coding conventions suggested
  39.  * by Bob Sidebotham and the AFS Clean Code Committee of the
  40.  * Information Technology Center at Carnegie Mellon.
  41.  */
  42.  
  43.  
  44. #include "hash.h"
  45.  
  46. #ifdef SVR4
  47. #define bcopy(a,b,c)    memcpy(b,a,c)
  48. #define bzero(p,l)      memset(p,0,l)
  49. #define bcmp(a,b,c)     memcmp(a,b,c)
  50. #endif
  51.  
  52. #define TRUE        1
  53. #define FALSE        0
  54. #define NULL        0
  55.  
  56. /*
  57.  * This can be changed to make internal routines visible to debuggers, etc.
  58.  */
  59. #define PRIVATE static
  60.  
  61.  
  62.  
  63. /*
  64.  * Hash table initialization routine.
  65.  *
  66.  * This routine creates and intializes a hash table of size "tablesize"
  67.  * entries.  Successful calls return a pointer to the hash table (which must
  68.  * be passed to other hash routines to identify the hash table).  Failed
  69.  * calls return NULL.
  70.  */
  71.  
  72. hash_tbl *hash_Init(tablesize)
  73. unsigned tablesize;
  74. {
  75.     register hash_tbl *hashtblptr;
  76.     register unsigned totalsize;
  77.  
  78.     if (tablesize > 0) {
  79.     totalsize = sizeof(hash_tbl)
  80.             + sizeof(hash_member *) * (tablesize - 1);
  81.     hashtblptr = (hash_tbl *) malloc(totalsize);
  82.     if (hashtblptr) {
  83.         bzero((char *) hashtblptr, totalsize);
  84.         hashtblptr->size = tablesize;        /* Success! */
  85.         hashtblptr->bucketnum = 0;
  86.         hashtblptr->member = (hashtblptr->table)[0];
  87.     }
  88.     } else {
  89.     hashtblptr = NULL;    /* Disallow zero-length tables */
  90.     }
  91.     return hashtblptr;        /* NULL if failure */
  92. }
  93.  
  94.  
  95.  
  96. /*
  97.  * Recursively frees an entire linked list of bucket members (used in the open
  98.  * hashing scheme).  Does nothing if the passed pointer is NULL.
  99.  */
  100.  
  101. PRIVATE void hashi_FreeMember(bucketptr, free_data)
  102. hash_member *bucketptr;
  103. void (*free_data)();
  104. {
  105.     if (bucketptr) {
  106.     /*
  107.      * Free next member if necessary
  108.      */
  109.     hashi_FreeMember(bucketptr->next, free_data);
  110.     (*free_data)(bucketptr->data);
  111.     free((char *) bucketptr);
  112.     }
  113. }
  114.  
  115.  
  116.  
  117.  
  118. /*
  119.  * This routine re-initializes the hash table.  It frees all the allocated
  120.  * memory and resets all bucket pointers to NULL.
  121.  */
  122.  
  123. void hash_Reset(hashtable, free_data)
  124. hash_tbl *hashtable;
  125. void (*free_data)();
  126. {
  127.     hash_member **bucketptr;
  128.     unsigned i;
  129.  
  130.     bucketptr = hashtable->table;
  131.     for (i = 0; i < hashtable->size; i++) {
  132.     hashi_FreeMember(*bucketptr, free_data);
  133.     *bucketptr++ = NULL;
  134.     }    
  135.     hashtable->bucketnum = 0;
  136.     hashtable->member = (hashtable->table)[0];
  137. }
  138.  
  139.  
  140.  
  141. /*
  142.  * Generic hash function to calculate a hash code from the given string.
  143.  *
  144.  * For each byte of the string, this function left-shifts the value in an
  145.  * accumulator and then adds the byte into the accumulator.  The contents of
  146.  * the accumulator is returned after the entire string has been processed.
  147.  * It is assumed that this result will be used as the "hashcode" parameter in
  148.  * calls to other functions in this package.  These functions automatically
  149.  * adjust the hashcode for the size of each hashtable.
  150.  *
  151.  * This algorithm probably works best when the hash table size is a prime
  152.  * number.
  153.  *
  154.  * Hopefully, this function is better than the previous one which returned
  155.  * the sum of the squares of all the bytes.  I'm still open to other
  156.  * suggestions for a default hash function.  The programmer is more than
  157.  * welcome to supply his/her own hash function as that is one of the design
  158.  * features of this package.
  159.  */
  160.  
  161. unsigned hash_HashFunction(string, len)
  162. unsigned char *string;
  163. register unsigned len;
  164. {
  165.     register unsigned accum;
  166.  
  167.     accum = 0;
  168.     for (; len > 0; len--) {
  169.     accum <<= 1;
  170.     accum += (unsigned) (*string++ & 0xFF);
  171.     }
  172.     return accum;
  173. }
  174.  
  175.  
  176.  
  177. /*
  178.  * Returns TRUE if at least one entry for the given key exists; FALSE
  179.  * otherwise.
  180.  */
  181.  
  182. int hash_Exists(hashtable, hashcode, compare, key)
  183. hash_tbl *hashtable;
  184. unsigned hashcode;
  185. int (*compare)();
  186. hash_datum *key;
  187. {
  188.     register hash_member *memberptr;
  189.  
  190.     memberptr = (hashtable->table)[hashcode % (hashtable->size)];
  191.     while (memberptr) {
  192.     if ((*compare)(key, memberptr->data)) {
  193.         return TRUE;        /* Entry does exist */
  194.     }
  195.     memberptr = memberptr->next;
  196.     }
  197.     return FALSE;            /* Entry does not exist */
  198. }
  199.  
  200.  
  201.  
  202. /*
  203.  * Insert the data item "element" into the hash table using "hashcode"
  204.  * to determine the bucket number, and "compare" and "key" to determine
  205.  * its uniqueness.
  206.  *
  207.  * If the insertion is successful 0 is returned.  If a matching entry
  208.  * already exists in the given bucket of the hash table, or some other error
  209.  * occurs, -1 is returned and the insertion is not done.
  210.  */
  211.  
  212. int hash_Insert(hashtable, hashcode, compare, key, element)
  213. hash_tbl *hashtable;
  214. unsigned hashcode;
  215. int (*compare)();
  216. hash_datum *key, *element;
  217. {
  218.     hash_member *memberptr, *temp;
  219.     
  220.     hashcode %= hashtable->size;
  221.     if (hash_Exists(hashtable, hashcode, compare, key)) {
  222.     return -1;    /* At least one entry already exists */
  223.     }
  224.     memberptr = (hashtable->table)[hashcode];
  225.     temp = (hash_member *) malloc(sizeof(hash_member));
  226.     if (temp) {
  227.     (hashtable->table)[hashcode] = temp;
  228.     temp->data = element;
  229.     temp->next = memberptr;
  230.     return 0;    /* Success */
  231.     } else {
  232.     return -1;    /* malloc failed! */
  233.     }
  234. }
  235.  
  236.  
  237.  
  238. /*
  239.  * Delete all data elements which match the given key.  If at least one
  240.  * element is found and the deletion is successful, 0 is returned.
  241.  * If no matching elements can be found in the hash table, -1 is returned.
  242.  */
  243.  
  244. int hash_Delete(hashtable, hashcode, compare, key, free_data)
  245. hash_tbl *hashtable;
  246. unsigned hashcode;
  247. int (*compare)();
  248. hash_datum *key;
  249. void (*free_data)();
  250. {
  251.     hash_member *memberptr, *previous, *tempptr;
  252.     int retval;
  253.  
  254.     retval = -1;
  255.     hashcode %= hashtable->size;
  256.  
  257.     /*
  258.      * Delete the first member of the list if it matches.  Since this moves
  259.      * the second member into the first position we have to keep doing this
  260.      * over and over until it no longer matches.
  261.      */
  262.     memberptr = (hashtable->table)[hashcode];
  263.     while (memberptr && (*compare)(key, memberptr->data)) {
  264.     (hashtable->table)[hashcode] = memberptr->next;
  265.     /*
  266.      * Stop hashi_FreeMember() from recursively deleting the whole list!
  267.      */
  268.     memberptr->next = NULL;
  269.     hashi_FreeMember(memberptr, free_data);
  270.     memberptr = (hashtable->table)[hashcode];
  271.     retval = 0;
  272.     }
  273.  
  274.     /*
  275.      * Now traverse the rest of the list
  276.      */
  277.     if (memberptr) {
  278.     previous = memberptr;
  279.     memberptr = memberptr->next;
  280.     }
  281.     while (memberptr) {
  282.     if ((*compare)(key, memberptr->data)) {
  283.         tempptr = memberptr;
  284.         previous->next = memberptr = memberptr->next;
  285.         /*
  286.          * Put the brakes on hashi_FreeMember(). . . .
  287.          */
  288.         tempptr->next = NULL;
  289.         hashi_FreeMember(tempptr, free_data);
  290.         retval = 0;
  291.     } else {
  292.         previous = memberptr;
  293.         memberptr = memberptr->next;
  294.     }
  295.     }
  296.     return retval;
  297. }
  298.  
  299.  
  300.  
  301. /*
  302.  * Locate and return the data entry associated with the given key.
  303.  *
  304.  * If the data entry is found, a pointer to it is returned.  Otherwise,
  305.  * NULL is returned.
  306.  */
  307.  
  308. hash_datum *hash_Lookup(hashtable, hashcode, compare, key)
  309. hash_tbl *hashtable;
  310. unsigned hashcode;
  311. int (*compare)();
  312. hash_datum *key;
  313. {
  314.     hash_member *memberptr;
  315.  
  316.     memberptr = (hashtable->table)[hashcode % (hashtable->size)];
  317.     while (memberptr) {
  318.     if ((*compare)(key, memberptr->data)) {
  319.         return (memberptr->data);
  320.     }
  321.     memberptr = memberptr->next;
  322.     }
  323.     return NULL;
  324. }
  325.  
  326.  
  327.  
  328. /*
  329.  * Return the next available entry in the hashtable for a linear search
  330.  */
  331.  
  332. hash_datum *hash_NextEntry(hashtable)
  333. hash_tbl *hashtable;
  334. {
  335.     register unsigned bucket;
  336.     register hash_member *memberptr;
  337.  
  338.     /*
  339.      * First try to pick up where we left off.
  340.      */
  341.     memberptr = hashtable->member;
  342.     if (memberptr) {
  343.     hashtable->member = memberptr->next;    /* Set up for next call */
  344.     return memberptr->data;            /* Return the data */
  345.     }
  346.  
  347.     /*
  348.      * We hit the end of a chain, so look through the array of buckets
  349.      * until we find a new chain (non-empty bucket) or run out of buckets.
  350.      */
  351.     bucket = hashtable->bucketnum + 1;
  352.     while ((bucket < hashtable->size) && 
  353.        !(memberptr = (hashtable->table)[bucket])) {
  354.     bucket++;
  355.     }
  356.  
  357.     /*
  358.      * Check to see if we ran out of buckets.
  359.      */
  360.     if (bucket >= hashtable->size) {
  361.     /*
  362.      * Reset to top of table for next call.
  363.      */
  364.     hashtable->bucketnum = 0;
  365.     hashtable->member = (hashtable->table)[0];
  366.     /*
  367.      * But return end-of-table indication to the caller this time.
  368.      */
  369.     return NULL;
  370.     }
  371.  
  372.     /*
  373.      * Must have found a non-empty bucket.
  374.      */
  375.     hashtable->bucketnum = bucket;
  376.     hashtable->member = memberptr->next;    /* Set up for next call */
  377.     return memberptr->data;            /* Return the data */
  378. }
  379.  
  380.  
  381.  
  382. /*
  383.  * Return the first entry in a hash table for a linear search
  384.  */
  385.  
  386. hash_datum *hash_FirstEntry(hashtable)
  387. hash_tbl *hashtable;
  388. {
  389.     hashtable->bucketnum = 0;
  390.     hashtable->member = (hashtable->table)[0];
  391.     return hash_NextEntry(hashtable);
  392. }
  393.