usr.sbin/bootp/common/hash.h

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