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