home *** CD-ROM | disk | FTP | other *** search
/ ftp.uv.es / 2014.11.ftp.uv.es.tar / ftp.uv.es / pub / unix / bootp.2.2+FdC.tar.Z / bootp.2.2+FdC.tar / hash.c < prev    next >
C/C++ Source or Header  |  1992-03-23  |  10KB  |  387 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: /d/backup/src4/sun4.bin/bootpd/2.2alpha/RCS/hash.c,v 1.1 92/03/23 15:57:07 alan Exp $";
  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. #define TRUE        1
  47. #define FALSE        0
  48. #define NULL        0
  49.  
  50. /*
  51.  * This can be changed to make internal routines visible to debuggers, etc.
  52.  */
  53. #define PRIVATE static
  54.  
  55.  
  56.  
  57. /*
  58.  * Hash table initialization routine.
  59.  *
  60.  * This routine creates and intializes a hash table of size "tablesize"
  61.  * entries.  Successful calls return a pointer to the hash table (which must
  62.  * be passed to other hash routines to identify the hash table).  Failed
  63.  * calls return NULL.
  64.  */
  65.  
  66. hash_tbl *hash_Init(tablesize)
  67. unsigned tablesize;
  68. {
  69.     register hash_tbl *hashtblptr;
  70.     register unsigned totalsize;
  71.  
  72.     if (tablesize > 0) {
  73.     totalsize = sizeof(hash_tbl)
  74.             + sizeof(hash_member *) * (tablesize - 1);
  75.     hashtblptr = (hash_tbl *) malloc(totalsize);
  76.     if (hashtblptr) {
  77.         bzero((char *) hashtblptr, totalsize);
  78.         hashtblptr->size = tablesize;        /* Success! */
  79.         hashtblptr->bucketnum = 0;
  80.         hashtblptr->member = (hashtblptr->table)[0];
  81.     }
  82.     } else {
  83.     hashtblptr = NULL;    /* Disallow zero-length tables */
  84.     }
  85.     return hashtblptr;        /* NULL if failure */
  86. }
  87.  
  88.  
  89.  
  90. /*
  91.  * Recursively frees an entire linked list of bucket members (used in the open
  92.  * hashing scheme).  Does nothing if the passed pointer is NULL.
  93.  */
  94.  
  95. PRIVATE void hashi_FreeMember(bucketptr, free_data)
  96. hash_member *bucketptr;
  97. void (*free_data)();
  98. {
  99.     if (bucketptr) {
  100.     /*
  101.      * Free next member if necessary
  102.      */
  103.     hashi_FreeMember(bucketptr->next, free_data);
  104.     (*free_data)(bucketptr->data);
  105.     free((char *) bucketptr);
  106.     }
  107. }
  108.  
  109.  
  110.  
  111.  
  112. /*
  113.  * This routine re-initializes the hash table.  It frees all the allocated
  114.  * memory and resets all bucket pointers to NULL.
  115.  */
  116.  
  117. void hash_Reset(hashtable, free_data)
  118. hash_tbl *hashtable;
  119. void (*free_data)();
  120. {
  121.     hash_member **bucketptr;
  122.     unsigned i;
  123.  
  124.     bucketptr = hashtable->table;
  125.     for (i = 0; i < hashtable->size; i++) {
  126.     hashi_FreeMember(*bucketptr, free_data);
  127.     *bucketptr++ = NULL;
  128.     }    
  129.     hashtable->bucketnum = 0;
  130.     hashtable->member = (hashtable->table)[0];
  131. }
  132.  
  133.  
  134.  
  135. /*
  136.  * Generic hash function to calculate a hash code from the given string.
  137.  *
  138.  * For each byte of the string, this function left-shifts the value in an
  139.  * accumulator and then adds the byte into the accumulator.  The contents of
  140.  * the accumulator is returned after the entire string has been processed.
  141.  * It is assumed that this result will be used as the "hashcode" parameter in
  142.  * calls to other functions in this package.  These functions automatically
  143.  * adjust the hashcode for the size of each hashtable.
  144.  *
  145.  * This algorithm probably works best when the hash table size is a prime
  146.  * number.
  147.  *
  148.  * Hopefully, this function is better than the previous one which returned
  149.  * the sum of the squares of all the bytes.  I'm still open to other
  150.  * suggestions for a default hash function.  The programmer is more than
  151.  * welcome to supply his/her own hash function as that is one of the design
  152.  * features of this package.
  153.  */
  154.  
  155. unsigned hash_HashFunction(string, len)
  156. unsigned char *string;
  157. register unsigned len;
  158. {
  159.     register unsigned accum;
  160.  
  161.     accum = 0;
  162.     for (; len > 0; len--) {
  163.     accum <<= 1;
  164.     accum += (unsigned) (*string++ & 0xFF);
  165.     }
  166.     return accum;
  167. }
  168.  
  169.  
  170.  
  171. /*
  172.  * Returns TRUE if at least one entry for the given key exists; FALSE
  173.  * otherwise.
  174.  */
  175.  
  176. int hash_Exists(hashtable, hashcode, compare, key)
  177. hash_tbl *hashtable;
  178. unsigned hashcode;
  179. int (*compare)();
  180. hash_datum *key;
  181. {
  182.     register hash_member *memberptr;
  183.  
  184.     memberptr = (hashtable->table)[hashcode % (hashtable->size)];
  185.     while (memberptr) {
  186.     if ((*compare)(key, memberptr->data)) {
  187.         return TRUE;        /* Entry does exist */
  188.     }
  189.     memberptr = memberptr->next;
  190.     }
  191.     return FALSE;            /* Entry does not exist */
  192. }
  193.  
  194.  
  195.  
  196. /*
  197.  * Insert the data item "element" into the hash table using "hashcode"
  198.  * to determine the bucket number, and "compare" and "key" to determine
  199.  * its uniqueness.
  200.  *
  201.  * If the insertion is successful 0 is returned.  If a matching entry
  202.  * already exists in the given bucket of the hash table, or some other error
  203.  * occurs, -1 is returned and the insertion is not done.
  204.  */
  205.  
  206. int hash_Insert(hashtable, hashcode, compare, key, element)
  207. hash_tbl *hashtable;
  208. unsigned hashcode;
  209. int (*compare)();
  210. hash_datum *key, *element;
  211. {
  212.     hash_member *memberptr, *temp;
  213.     
  214.     hashcode %= hashtable->size;
  215.     if (hash_Exists(hashtable, hashcode, compare, key)) {
  216.     return -1;    /* At least one entry already exists */
  217.     }
  218.     memberptr = (hashtable->table)[hashcode];
  219.     temp = (hash_member *) malloc(sizeof(hash_member));
  220.     if (temp) {
  221.     (hashtable->table)[hashcode] = temp;
  222.     temp->data = element;
  223.     temp->next = memberptr;
  224.     return 0;    /* Success */
  225.     } else {
  226.     return -1;    /* malloc failed! */
  227.     }
  228. }
  229.  
  230.  
  231.  
  232. /*
  233.  * Delete all data elements which match the given key.  If at least one
  234.  * element is found and the deletion is successful, 0 is returned.
  235.  * If no matching elements can be found in the hash table, -1 is returned.
  236.  */
  237.  
  238. int hash_Delete(hashtable, hashcode, compare, key, free_data)
  239. hash_tbl *hashtable;
  240. unsigned hashcode;
  241. int (*compare)();
  242. hash_datum *key;
  243. void (*free_data)();
  244. {
  245.     hash_member *memberptr, *previous, *tempptr;
  246.     int retval;
  247.  
  248.     retval = -1;
  249.     hashcode %= hashtable->size;
  250.  
  251.     /*
  252.      * Delete the first member of the list if it matches.  Since this moves
  253.      * the second member into the first position we have to keep doing this
  254.      * over and over until it no longer matches.
  255.      */
  256.     memberptr = (hashtable->table)[hashcode];
  257.     while (memberptr && (*compare)(key, memberptr->data)) {
  258.     (hashtable->table)[hashcode] = memberptr->next;
  259.     /*
  260.      * Stop hashi_FreeMember() from recursively deleting the whole list!
  261.      */
  262.     memberptr->next = NULL;
  263.     hashi_FreeMember(memberptr, free_data);
  264.     memberptr = (hashtable->table)[hashcode];
  265.     retval = 0;
  266.     }
  267.  
  268.     /*
  269.      * Now traverse the rest of the list
  270.      */
  271.     if (memberptr) {
  272.     previous = memberptr;
  273.     memberptr = memberptr->next;
  274.     }
  275.     while (memberptr) {
  276.     if ((*compare)(key, memberptr->data)) {
  277.         tempptr = memberptr;
  278.         previous->next = memberptr = memberptr->next;
  279.         /*
  280.          * Put the brakes on hashi_FreeMember(). . . .
  281.          */
  282.         tempptr->next = NULL;
  283.         hashi_FreeMember(tempptr, free_data);
  284.         retval = 0;
  285.     } else {
  286.         previous = memberptr;
  287.         memberptr = memberptr->next;
  288.     }
  289.     }
  290.     return retval;
  291. }
  292.  
  293.  
  294.  
  295. /*
  296.  * Locate and return the data entry associated with the given key.
  297.  *
  298.  * If the data entry is found, a pointer to it is returned.  Otherwise,
  299.  * NULL is returned.
  300.  */
  301.  
  302. hash_datum *hash_Lookup(hashtable, hashcode, compare, key)
  303. hash_tbl *hashtable;
  304. unsigned hashcode;
  305. int (*compare)();
  306. hash_datum *key;
  307. {
  308.     hash_member *memberptr;
  309.  
  310.     memberptr = (hashtable->table)[hashcode % (hashtable->size)];
  311.     while (memberptr) {
  312.     if ((*compare)(key, memberptr->data)) {
  313.         return (memberptr->data);
  314.     }
  315.     memberptr = memberptr->next;
  316.     }
  317.     return NULL;
  318. }
  319.  
  320.  
  321.  
  322. /*
  323.  * Return the next available entry in the hashtable for a linear search
  324.  */
  325.  
  326. hash_datum *hash_NextEntry(hashtable)
  327. hash_tbl *hashtable;
  328. {
  329.     register unsigned bucket;
  330.     register hash_member *memberptr;
  331.  
  332.     /*
  333.      * First try to pick up where we left off.
  334.      */
  335.     memberptr = hashtable->member;
  336.     if (memberptr) {
  337.     hashtable->member = memberptr->next;    /* Set up for next call */
  338.     return memberptr->data;            /* Return the data */
  339.     }
  340.  
  341.     /*
  342.      * We hit the end of a chain, so look through the array of buckets
  343.      * until we find a new chain (non-empty bucket) or run out of buckets.
  344.      */
  345.     bucket = hashtable->bucketnum + 1;
  346.     while ((bucket < hashtable->size) && 
  347.        !(memberptr = (hashtable->table)[bucket])) {
  348.     bucket++;
  349.     }
  350.  
  351.     /*
  352.      * Check to see if we ran out of buckets.
  353.      */
  354.     if (bucket >= hashtable->size) {
  355.     /*
  356.      * Reset to top of table for next call.
  357.      */
  358.     hashtable->bucketnum = 0;
  359.     hashtable->member = (hashtable->table)[0];
  360.     /*
  361.      * But return end-of-table indication to the caller this time.
  362.      */
  363.     return NULL;
  364.     }
  365.  
  366.     /*
  367.      * Must have found a non-empty bucket.
  368.      */
  369.     hashtable->bucketnum = bucket;
  370.     hashtable->member = memberptr->next;    /* Set up for next call */
  371.     return memberptr->data;            /* Return the data */
  372. }
  373.  
  374.  
  375.  
  376. /*
  377.  * Return the first entry in a hash table for a linear search
  378.  */
  379.  
  380. hash_datum *hash_FirstEntry(hashtable)
  381. hash_tbl *hashtable;
  382. {
  383.     hashtable->bucketnum = 0;
  384.     hashtable->member = (hashtable->table)[0];
  385.     return hash_NextEntry(hashtable);
  386. }
  387.