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