external/bsd/dhcp/dist/includes/omapip/hash.h

   1 /*      $NetBSD: hash.h,v 1.1.1.3 2014/07/12 11:57:57 spz Exp $ */
   2 /* hash.h
   3
   4    Definitions for hashing... */
   5
   6 /*
   7  * Copyright (c) 2004,2009,2014 by Internet Systems Consortium, Inc. ("ISC")
   8  * Copyright (c) 1995-2003 by Internet Software Consortium
   9  *
  10  * Permission to use, copy, modify, and distribute this software for any
  11  * purpose with or without fee is hereby granted, provided that the above
  12  * copyright notice and this permission notice appear in all copies.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
  15  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  16  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
  17  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  18  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  19  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  20  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  21  *
  22  *   Internet Systems Consortium, Inc.
  23  *   950 Charter Street
  24  *   Redwood City, CA 94063
  25  *   <info@isc.org>
  26  *   https://www.isc.org/
  27  *
  28  */
  29
  30 #ifndef OMAPI_HASH_H
  31 #define OMAPI_HASH_H
  32
  33 #if !defined (DEFAULT_HASH_SIZE)
  34 # define DEFAULT_HASH_SIZE      9973
  35 #endif
  36
  37 #if !defined (KEY_HASH_SIZE)
  38 # define KEY_HASH_SIZE          1009
  39 #endif
  40
  41 /* The purpose of the hashed_object_t struct is to not match anything else. */
  42 typedef struct {
  43         int foo;
  44 } hashed_object_t;
  45
  46 typedef isc_result_t (*hash_foreach_func)(const void *, unsigned, void *);
  47 typedef int (*hash_reference) (hashed_object_t **, hashed_object_t *,
  48                                const char *, int);
  49 typedef int (*hash_dereference) (hashed_object_t **, const char *, int);
  50
  51 struct hash_bucket {
  52         struct hash_bucket *next;
  53         const unsigned char *name;
  54         unsigned len;
  55         hashed_object_t *value;
  56 };
  57
  58 typedef int (*hash_comparator_t)(const void *, const void *, size_t);
  59
  60 struct hash_table {
  61         unsigned hash_count;
  62         hash_reference referencer;
  63         hash_dereference dereferencer;
  64         hash_comparator_t cmp;
  65         unsigned (*do_hash)(const void *, unsigned, unsigned);
  66
  67         /* This must remain the last entry in this table. */
  68         struct hash_bucket *buckets [1];
  69 };
  70
  71 struct named_hash {
  72         struct named_hash *next;
  73         const char *name;
  74         struct hash_table *hash;
  75 };
  76
  77 #define HASH_FUNCTIONS_DECL(name, bufarg, type, hashtype)                     \
  78 void name##_hash_add (hashtype *, bufarg, unsigned, type *,                   \
  79                       const char *, int);                                     \
  80 void name##_hash_delete (hashtype *, bufarg, unsigned,                        \
  81                          const char *, int);                                  \
  82 int name##_hash_lookup (type **, hashtype *, bufarg, unsigned,                \
  83                         const char *, int);                                   \
  84 unsigned char * name##_hash_report(hashtype *);                               \
  85 int name##_hash_foreach (hashtype *, hash_foreach_func);                      \
  86 int name##_new_hash (hashtype **, unsigned, const char *, int);               \
  87 void name##_free_hash_table (hashtype **, const char *, int);
  88
  89
  90 #define HASH_FUNCTIONS(name, bufarg, type, hashtype, ref, deref, hasher)      \
  91 void name##_hash_add (hashtype *table,                                        \
  92                       bufarg buf, unsigned len, type *ptr,                    \
  93                       const char *file, int line)                             \
  94 {                                                                             \
  95         add_hash ((struct hash_table *)table, buf,                            \
  96                   len, (hashed_object_t *)ptr, file, line);                   \
  97 }                                                                             \
  98                                                                               \
  99 void name##_hash_delete (hashtype *table, bufarg buf, unsigned len,           \
 100                          const char *file, int line)                          \
 101 {                                                                             \
 102         delete_hash_entry ((struct hash_table *)table, buf, len,              \
 103                            file, line);                                       \
 104 }                                                                             \
 105                                                                               \
 106 int name##_hash_lookup (type **ptr, hashtype *table,                          \
 107                         bufarg buf, unsigned len, const char *file, int line) \
 108 {                                                                             \
 109         return hash_lookup ((hashed_object_t **)ptr,                          \
 110                             (struct hash_table *)table,                       \
 111                             buf, len, file, line);                            \
 112 }                                                                             \
 113                                                                               \
 114 unsigned char * name##_hash_report(hashtype *table)                           \
 115 {                                                                             \
 116         return hash_report((struct hash_table *)table);                       \
 117 }                                                                             \
 118                                                                               \
 119 int name##_hash_foreach (hashtype *table, hash_foreach_func func)             \
 120 {                                                                             \
 121         return hash_foreach ((struct hash_table *)table,                      \
 122                              func);                                           \
 123 }                                                                             \
 124                                                                               \
 125 int name##_new_hash (hashtype **tp, unsigned c, const char *file, int line)   \
 126 {                                                                             \
 127         return new_hash ((struct hash_table **)tp,                            \
 128                          (hash_reference)ref, (hash_dereference)deref, c,     \
 129                          hasher, file, line);                                 \
 130 }                                                                             \
 131                                                                               \
 132 void name##_free_hash_table (hashtype **table, const char *file, int line)    \
 133 {                                                                             \
 134         free_hash_table ((struct hash_table **)table, file, line);            \
 135 }
 136
 137 void relinquish_hash_bucket_hunks (void);
 138 int new_hash_table (struct hash_table **, unsigned, const char *, int);
 139 void free_hash_table (struct hash_table **, const char *, int);
 140 struct hash_bucket *new_hash_bucket (const char *, int);
 141 void free_hash_bucket (struct hash_bucket *, const char *, int);
 142 int new_hash(struct hash_table **,
 143              hash_reference, hash_dereference, unsigned,
 144              unsigned (*do_hash)(const void *, unsigned, unsigned),
 145              const char *, int);
 146 unsigned do_string_hash(const void *, unsigned, unsigned);
 147 unsigned do_case_hash(const void *, unsigned, unsigned);
 148 unsigned do_id_hash(const void *, unsigned, unsigned);
 149 unsigned do_number_hash(const void *, unsigned, unsigned);
 150 unsigned do_ip4_hash(const void *, unsigned, unsigned);
 151 unsigned char *hash_report(struct hash_table *);
 152 void add_hash (struct hash_table *,
 153                       const void *, unsigned, hashed_object_t *,
 154                       const char *, int);
 155 void delete_hash_entry (struct hash_table *, const void *,
 156                                unsigned, const char *, int);
 157 int hash_lookup (hashed_object_t **, struct hash_table *,
 158                         const void *, unsigned, const char *, int);
 159 int hash_foreach (struct hash_table *, hash_foreach_func);
 160 int casecmp (const void *s, const void *t, size_t len);
 161
 162 #endif /* OMAPI_HASH_H */