1 /* 2 * This file is part of the Sofia-SIP package 3 * 4 * Copyright (C) 2005 Nokia Corporation. 5 * 6 * Contact: Pekka Pessi <pekka.pessi@nokia.com> 7 * 8 * This library is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Lesser General Public License 10 * as published by the Free Software Foundation; either version 2.1 of 11 * the License, or (at your option) any later version. 12 * 13 * This library is distributed in the hope that it will be useful, but 14 * WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with this library; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 21 * 02110-1301 USA 22 * 23 */ 24 25 #ifndef HTABLE_H 26 /** Defined when <sofia-sip/htable.h> has been included. */ 27 #define HTABLE_H 28 29 /**@ingroup su_htable 30 * @file sofia-sip/htable.h 31 * 32 * Hash tables templates. 33 * 34 * This file contain a hash table template for C. The hash tables are 35 * resizeable, and they usually contain pointers to entries. The 36 * declaration for template datatypes is instantiated with macro 37 * HTABLE_DECLARE(). The prototypes for hashing functions are instantiated 38 * with macro HTABLE_PROTOS(). The implementation is instantiated with 39 * macro HTABLE_BODIES(). 40 * 41 * The hash table template is most efficient when the hash value is 42 * precalculated and stored in each entry. The hash "function" given to the 43 * HTABLE_BODIES() would then be something like macro 44 * @code 45 * #define HTABLE_ENTRY_HASH(e) ((e)->e_hash_value) 46 * @endcode 47 * 48 * When a entry with new identical hash key is added to the table, it can be 49 * either @e inserted (before any other entry with same key value) or 50 * @e appended. 51 * 52 * Example code can be found from <htable_test.c>. 53 * 54 * @author Pekka Pessi <Pekka.Pessi@nokia.com> 55 * 56 * @date Created: Tue Sep 25 17:42:40 2001 ppessi 57 */ 58 59 typedef unsigned long hash_value_t; 60 61 /** Minimum size of hash table */ 62 #define HTABLE_MIN_SIZE 31 63 64 /** Declare hash table structure type. 65 * 66 * The macro HTABLE_DECLARE() expands to a declaration for hash table 67 * structure. The its typedef will be <em>prefix</em><code>_t</code>, the 68 * field names start withb @a pr. The entry type is @a entry_t. 69 * 70 * @param prefix hash table type and function prefix 71 * @param pr hash table field prefix 72 * @param entry_t entry type 73 */ 74 #define HTABLE_DECLARE(prefix, pr, entry_t) \ 75 HTABLE_DECLARE_WITH(prefix, pr, entry_t, unsigned, hash_value_t) 76 77 #define HTABLE_DECLARE_WITH(prefix, pr, entry_t, size_t, hash_value_t) \ 78 typedef struct prefix##_s { \ 79 size_t pr##_size; \ 80 size_t pr##_used; \ 81 entry_t**pr##_table; /**< Hash table itself */ \ 82 } prefix##_t 83 84 #ifndef HTABLE_SCOPE 85 /** Default scope for hash table functions. */ 86 #define HTABLE_SCOPE su_inline 87 #endif 88 89 /** Prototypes for hash table 90 * 91 * The macro HTABLE_PROTOS() expands to the prototypes of hash table 92 * functions. The function and type names start with @a prefix, the field 93 * names start with @a pr. The entry type is @a entry_t. 94 * 95 * @param prefix hash table type and function prefix 96 * @param pr hash table field prefix 97 * @param entry_t entry type 98 */ 99 #define HTABLE_PROTOS(prefix, pr, entry_t) \ 100 HTABLE_PROTOS_WITH(prefix, pr, entry_t, unsigned, hash_value_t) 101 102 #define HTABLE_PROTOS_WITH(prefix, pr, entry_t, size_t, hash_value_t) \ 103 HTABLE_SCOPE int prefix##_resize(su_home_t *, prefix##_t pr[1], size_t); \ 104 HTABLE_SCOPE int prefix##_is_full(prefix##_t const *); \ 105 HTABLE_SCOPE entry_t **prefix##_hash(prefix##_t const *, hash_value_t hv); \ 106 HTABLE_SCOPE entry_t **prefix##_next(prefix##_t const *, entry_t * const *ee); \ 107 HTABLE_SCOPE void prefix##_append(prefix##_t *pr, entry_t const *e); \ 108 HTABLE_SCOPE void prefix##_insert(prefix##_t *pr, entry_t const *e); \ 109 HTABLE_SCOPE int prefix##_remove(prefix##_t *, entry_t const *e) 110 111 /** Hash table implementation. 112 * 113 * The macro HTABLE_BODIES() expands the hash table functions. The function 114 * and type names start with @a prefix, the field names start with @a pr. 115 * The entry type is @a entry_t. The function (or macro) name returning 116 * hash value of each entry is given as @a hfun. 117 * 118 * @param prefix hash table type and function prefix 119 * @param pr hash table field prefix 120 * @param entry_t entry type 121 * @param hfun function or macro returning hash value of entry 122 */ 123 #define HTABLE_BODIES(prefix, pr, entry_t, hfun) \ 124 HTABLE_BODIES_WITH(prefix, pr, entry_t, hfun, unsigned, hash_value_t) 125 126 #define HTABLE_BODIES_WITH(prefix, pr, entry_t, hfun, size_t, hash_value_t) \ 127 /** Reallocate new hash table */ \ 128 HTABLE_SCOPE \ 129 int prefix##_resize(su_home_t *home, \ 130 prefix##_t pr[], \ 131 size_t new_size) \ 132 { \ 133 entry_t **new_hash; \ 134 entry_t **old_hash = pr->pr##_table; \ 135 size_t old_size; \ 136 size_t i, j, i0; \ 137 unsigned again = 0; \ 138 size_t used = 0, collisions = 0; \ 139 \ 140 if (new_size == 0) \ 141 new_size = 2 * pr->pr##_size + 1; \ 142 if (new_size < HTABLE_MIN_SIZE) \ 143 new_size = HTABLE_MIN_SIZE; \ 144 if (new_size < 5 * pr->pr##_used / 4) \ 145 new_size = 5 * pr->pr##_used / 4; \ 146 \ 147 if (!(new_hash = su_zalloc(home, sizeof(*new_hash) * new_size))) \ 148 return -1; \ 149 \ 150 old_size = pr->pr##_size; \ 151 \ 152 do for (j = 0; j < old_size; j++) { \ 153 if (!old_hash[j]) \ 154 continue; \ 155 \ 156 if (again < 2 && hfun(old_hash[j]) % old_size > j) { \ 157 /* Wrapped, leave entry for second pass */ \ 158 again = 1; continue; \ 159 } \ 160 \ 161 i0 = hfun(old_hash[j]) % new_size; \ 162 \ 163 for (i = i0; new_hash[i]; i = (i + 1) % new_size, assert(i != i0)) \ 164 collisions++; \ 165 \ 166 new_hash[i] = old_hash[j], old_hash[j] = NULL; \ 167 used++; \ 168 } \ 169 while (again++ == 1); \ 170 \ 171 pr->pr##_table = new_hash, pr->pr##_size = new_size; \ 172 \ 173 assert(pr->pr##_used == used); \ 174 \ 175 su_free(home, old_hash); \ 176 \ 177 return 0; \ 178 } \ 179 \ 180 HTABLE_SCOPE \ 181 int prefix##_is_full(prefix##_t const *pr) \ 182 { \ 183 return pr->pr##_table == NULL || 3 * pr->pr##_used > 2 * pr->pr##_size; \ 184 } \ 185 \ 186 HTABLE_SCOPE \ 187 entry_t **prefix##_hash(prefix##_t const *pr, hash_value_t hv) \ 188 { \ 189 return pr->pr##_table + hv % pr->pr##_size; \ 190 } \ 191 \ 192 HTABLE_SCOPE \ 193 entry_t **prefix##_next(prefix##_t const *pr, entry_t * const *ee) \ 194 { \ 195 if (++ee < pr->pr##_table + pr->pr##_size && ee >= pr->pr##_table) \ 196 return (entry_t **)ee; \ 197 else \ 198 return pr->pr##_table; \ 199 } \ 200 \ 201 HTABLE_SCOPE \ 202 void prefix##_append(prefix##_t *pr, entry_t const *e) \ 203 { \ 204 entry_t **ee; \ 205 \ 206 pr->pr##_used++; \ 207 for (ee = prefix##_hash(pr, hfun(e)); *ee; ee = prefix##_next(pr, ee)) \ 208 ; \ 209 *ee = (entry_t *)e; \ 210 } \ 211 \ 212 HTABLE_SCOPE \ 213 void prefix##_insert(prefix##_t *pr, entry_t const *e) \ 214 { \ 215 entry_t *e0, **ee; \ 216 \ 217 pr->pr##_used++; \ 218 /* Insert entry into hash table (before other entries with same hash) */ \ 219 for (ee = prefix##_hash(pr, hfun(e)); \ 220 (e0 = *ee); \ 221 ee = prefix##_next(pr, ee)) \ 222 *ee = (entry_t *)e, e = e0; \ 223 *ee = (entry_t *)e; \ 224 } \ 225 \ 226 HTABLE_SCOPE \ 227 int prefix##_remove(prefix##_t *pr, entry_t const *e) \ 228 { \ 229 size_t i, j, k; \ 230 size_t size = pr->pr##_size; \ 231 entry_t **htable = pr->pr##_table; \ 232 \ 233 if (!e) return -1; \ 234 \ 235 /* Search for entry */ \ 236 for (i = hfun(e) % size; htable[i]; i = (i + 1) % size) \ 237 if (e == htable[i]) \ 238 break; \ 239 \ 240 /* Entry is not in table? */ \ 241 if (!htable[i]) return -1; \ 242 \ 243 /* Move table entries towards their primary place */ \ 244 for (j = (i + 1) % size; htable[j]; j = (j + 1) % size) { \ 245 /* k is primary place for entry */ \ 246 k = hfun(htable[j]) % size; \ 247 if (k == j) /* entry is in its primary place? */ \ 248 continue; \ 249 /* primary place is between i and j - do not move this to i */ \ 250 if (j > i ? (i < k && k < j) : (i < k || k < j)) \ 251 continue; \ 252 \ 253 htable[i] = htable[j], i = j; \ 254 } \ 255 \ 256 pr->pr##_used--; \ 257 \ 258 htable[i] = NULL; \ 259 \ 260 return 0; \ 261 } \ 262 extern int prefix##_dummy 263 264 #endif /** !defined(HTABLE_H) */ 265