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