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 */ 163