libexec/bootpd/hash.c

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