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