libexec/bootpd/hash.h

   1 #ifndef HASH_H
   2 #define HASH_H
   3 /* hash.h */
   4 /************************************************************************
   5           Copyright 1988, 1991 by Carnegie Mellon University
   6
   7                           All Rights Reserved
   8
   9 Permission to use, copy, modify, and distribute this software and its
  10 documentation for any purpose and without fee is hereby granted, provided
  11 that the above copyright notice appear in all copies and that both that
  12 copyright notice and this permission notice appear in supporting
  13 documentation, and that the name of Carnegie Mellon University not be used
  14 in advertising or publicity pertaining to distribution of the software
  15 without specific, written prior permission.
  16
  17 CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  18 SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
  19 IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  20 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  21 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  22 ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  23 SOFTWARE.
  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.
  34  */
  35
  36
  37 /*
  38  * The user must supply the following:
  39  *
  40  *      1.  A comparison function which is declared as:
  41  *
  42  *              int compare(data1, data2)
  43  *              hash_datum *data1, *data2;
  44  *
  45  *          This function must compare the desired fields of data1 and
  46  *          data2 and return TRUE (1) if the data should be considered
  47  *          equivalent (i.e. have the same key value) or FALSE (0)
  48  *          otherwise.  This function is called through a pointer passed to
  49  *          the various hashtable functions (thus pointers to different
  50  *          functions may be passed to effect different tests on different
  51  *          hash tables).
  52  *
  53  *          Internally, all the functions of this package always call the
  54  *          compare function with the "key" parameter as the first parameter,
  55  *          and a full data element as the second parameter.  Thus, the key
  56  *          and element arguments to functions such as hash_Lookup() may
  57  *          actually be of different types and the programmer may provide a
  58  *          compare function which compares the two different object types
  59  *          as desired.
  60  *
  61  *          Example:
  62  *
  63  *              int compare(key, element)
  64  *              char *key;
  65  *              struct some_complex_structure *element;
  66  *              {
  67  *                  return !strcmp(key, element->name);
  68  *              }
  69  *
  70  *              key = "John C. Doe"
  71  *              element = &some_complex_structure
  72  *              hash_Lookup(table, hashcode, compare, key);
  73  *
  74  *      2.  A hash function yielding an unsigned integer value to be used
  75  *          as the hashcode (index into the hashtable).  Thus, the user
  76  *          may hash on whatever data is desired and may use several
  77  *          different hash functions for various different hash tables.
  78  *          The actual hash table index will be the passed hashcode modulo
  79  *          the hash table size.
  80  *
  81  *          A generalized hash function, hash_HashFunction(), is included
  82  *          with this package to make things a little easier.  It is not
  83  *          guarenteed to use the best hash algorithm in existence. . . .
  84  */
  85
  86 \f
  87
  88 /*
  89  * Various hash table definitions
  90  */
  91
  92
  93 /*
  94  * Define "hash_datum" as a universal data type
  95  */
  96 #ifdef __STDC__
  97 typedef void hash_datum;
  98 #else
  99 typedef char hash_datum;
 100 #endif
 101
 102 typedef struct hash_memberstruct  hash_member;
 103 typedef struct hash_tblstruct     hash_tbl;
 104 typedef struct hash_tblstruct_hdr hash_tblhdr;
 105
 106 struct hash_memberstruct {
 107     hash_member *next;
 108     hash_datum  *data;
 109 };
 110
 111 struct hash_tblstruct_hdr {
 112     unsigned    size, bucketnum;
 113     hash_member *member;
 114 };
 115
 116 struct hash_tblstruct {
 117     unsigned    size, bucketnum;
 118     hash_member *member;                /* Used for linear dump */
 119     hash_member *table[1];              /* Dynamically extended */
 120 };
 121
 122 /* ANSI function prototypes or empty arg list? */
 123 #ifdef  __STDC__
 124 #define P(args) args
 125 #else
 126 #define P(args) ()
 127 #endif
 128
 129 typedef int (*hash_cmpfp) P((hash_datum *, hash_datum *));
 130 typedef void (*hash_freefp) P((hash_datum *));
 131
 132 extern hash_tbl   *hash_Init P((u_int tablesize));
 133
 134 extern void        hash_Reset P((hash_tbl *tbl, hash_freefp));
 135
 136 extern unsigned    hash_HashFunction P((u_char *str, u_int len));
 137
 138 extern int         hash_Exists P((hash_tbl *, u_int code,
 139                                   hash_cmpfp, hash_datum *key));
 140
 141 extern int         hash_Insert P((hash_tbl *, u_int code,
 142                                   hash_cmpfp, hash_datum *key,
 143                                   hash_datum *element));
 144
 145 extern int         hash_Delete P((hash_tbl *, u_int code,
 146                                   hash_cmpfp, hash_datum *key,
 147                                   hash_freefp));
 148
 149 extern hash_datum *hash_Lookup P((hash_tbl *, u_int code,
 150                                   hash_cmpfp, hash_datum *key));
 151
 152 extern hash_datum *hash_FirstEntry P((hash_tbl *));
 153
 154 extern hash_datum *hash_NextEntry P((hash_tbl *));
 155
 156 #undef P
 157
 158 #endif  /* HASH_H */