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