includes/omapip/hash.h

   1 /* hash.h
   2
   3    Definitions for hashing... */
   4
   5 /*
   6  * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
   7  * Copyright (c) 1995-2003 by Internet Software Consortium
   8  *
   9  * Permission to use, copy, modify, and distribute this software for any
  10  * purpose with or without fee is hereby granted, provided that the above
  11  * copyright notice and this permission notice appear in all copies.
  12  *
  13  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
  14  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  15  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
  16  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  17  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  18  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  19  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  20  *
  21  *   Internet Systems Consortium, Inc.
  22  *   950 Charter Street
  23  *   Redwood City, CA 94063
  24  *   <info@isc.org>
  25  *   http://www.isc.org/
  26  *
  27  * This software has been written for Internet Systems Consortium
  28  * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
  29  * To learn more about Internet Systems Consortium, see
  30  * ``http://www.isc.org/''.  To learn more about Vixie Enterprises,
  31  * see ``http://www.vix.com''.   To learn more about Nominum, Inc., see
  32  * ``http://www.nominum.com''.
  33  */
  34
  35 #ifndef OMAPI_HASH_H
  36 #define OMAPI_HASH_H
  37
  38 #define DEFAULT_HASH_SIZE       9973
  39
  40 /* The purpose of the hashed_object_t struct is to not match anything else. */
  41 typedef struct {
  42         int foo;
  43 } hashed_object_t;
  44
  45 typedef void (*hash_foreach_func) (const unsigned char *,
  46                                    unsigned, hashed_object_t *);
  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 *, unsigned long);
  59
  60 struct hash_table {
  61         unsigned hash_count;
  62         struct hash_bucket *buckets [DEFAULT_HASH_SIZE];
  63         hash_reference referencer;
  64         hash_dereference dereferencer;
  65         hash_comparator_t cmp;
  66         int (*do_hash) (const unsigned char *, unsigned, unsigned);
  67 };
  68
  69 struct named_hash {
  70         struct named_hash *next;
  71         const char *name;
  72         struct hash_table *hash;
  73 };
  74
  75 #define HASH_FUNCTIONS_DECL(name, bufarg, type, hashtype)                     \
  76 void name##_hash_add (hashtype *, bufarg, unsigned, type *,                   \
  77                       const char *, int);                                     \
  78 void name##_hash_delete (hashtype *, bufarg, unsigned,                        \
  79                          const char *, int);                                  \
  80 int name##_hash_lookup (type **, hashtype *, bufarg, unsigned,                \
  81                         const char *, int);                                   \
  82 int name##_hash_foreach (hashtype *,                                          \
  83                          void (*) (bufarg, unsigned, type *));                \
  84 int name##_new_hash (hashtype **, int, const char *, int);                    \
  85 void name##_free_hash_table (hashtype **, const char *, int);
  86
  87
  88 #define HASH_FUNCTIONS(name, bufarg, type, hashtype, ref, deref)              \
  89 void name##_hash_add (hashtype *table,                                        \
  90                       bufarg buf, unsigned len, type *ptr,                    \
  91                       const char *file, int line)                             \
  92 {                                                                             \
  93         add_hash ((struct hash_table *)table,                                 \
  94                   (const unsigned char *)buf,                                 \
  95                   len, (hashed_object_t *)ptr, file, line);                   \
  96 }                                                                             \
  97                                                                               \
  98 void name##_hash_delete (hashtype *table,                                     \
  99                          bufarg buf, unsigned len, const char *file, int line)\
 100 {                                                                             \
 101         delete_hash_entry ((struct hash_table *)table,                        \
 102                            (const unsigned char *)buf,                        \
 103                            len, 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                             (const unsigned char *)buf, len, file, line);     \
 112 }                                                                             \
 113                                                                               \
 114 int name##_hash_foreach (hashtype *table,                                     \
 115                          void (*func) (bufarg, unsigned, type *))             \
 116 {                                                                             \
 117         return hash_foreach ((struct hash_table *)table,                      \
 118                              (hash_foreach_func)func);                        \
 119 }                                                                             \
 120                                                                               \
 121 int name##_new_hash (hashtype **tp, int c, const char *file, int line)        \
 122 {                                                                             \
 123         return new_hash ((struct hash_table **)tp,                            \
 124                          (hash_reference)ref, (hash_dereference)deref, c,     \
 125                          file, line);                                         \
 126 }                                                                             \
 127                                                                               \
 128 void name##_free_hash_table (hashtype **table, const char *file, int line)    \
 129 {                                                                             \
 130         free_hash_table ((struct hash_table **)table, file, line);            \
 131 }
 132
 133 void relinquish_hash_bucket_hunks (void);
 134 int new_hash_table (struct hash_table **, int, const char *, int);
 135 void free_hash_table (struct hash_table **, const char *, int);
 136 struct hash_bucket *new_hash_bucket (const char *, int);
 137 void free_hash_bucket (struct hash_bucket *, const char *, int);
 138 int new_hash (struct hash_table **,
 139               hash_reference, hash_dereference, int, const char *, int);
 140 void add_hash (struct hash_table *,
 141                       const unsigned char *, unsigned, hashed_object_t *,
 142                       const char *, int);
 143 void delete_hash_entry (struct hash_table *, const unsigned char *,
 144                                unsigned, const char *, int);
 145 int hash_lookup (hashed_object_t **, struct hash_table *,
 146                         const unsigned char *, unsigned, const char *, int);
 147 int hash_foreach (struct hash_table *, hash_foreach_func);
 148 int casecmp (const void *s, const void *t, unsigned long len);
 149
 150 #endif /* OMAPI_HASH_H */