Go to the documentation of this file. 59 typedef unsigned long hash_value_t;
62 #define HTABLE_MIN_SIZE 31 74 #define HTABLE_DECLARE(prefix, pr, entry_t) \ 75 HTABLE_DECLARE_WITH(prefix, pr, entry_t, unsigned, hash_value_t) 77 #define HTABLE_DECLARE_WITH(prefix, pr, entry_t, size_t, hash_value_t) \ 78 typedef struct prefix##_s { \ 81 entry_t**pr##_table; \ 86 #define HTABLE_SCOPE su_inline 99 #define HTABLE_PROTOS(prefix, pr, entry_t) \ 100 HTABLE_PROTOS_WITH(prefix, pr, entry_t, unsigned, hash_value_t) 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) 123 #define HTABLE_BODIES(prefix, pr, entry_t, hfun) \ 124 HTABLE_BODIES_WITH(prefix, pr, entry_t, hfun, unsigned, hash_value_t) 126 #define HTABLE_BODIES_WITH(prefix, pr, entry_t, hfun, size_t, hash_value_t) \ 129 int prefix##_resize(su_home_t *home, \ 133 entry_t **new_hash; \ 134 entry_t **old_hash = pr->pr##_table; \ 137 unsigned again = 0; \ 138 size_t used = 0, collisions = 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; \ 147 if (!(new_hash = su_zalloc(home, sizeof(*new_hash) * new_size))) \ 150 old_size = pr->pr##_size; \ 152 do for (j = 0; j < old_size; j++) { \ 156 if (again < 2 && hfun(old_hash[j]) % old_size > j) { \ 158 again = 1; continue; \ 161 i0 = hfun(old_hash[j]) % new_size; \ 163 for (i = i0; new_hash[i]; i = (i + 1) % new_size, assert(i != i0)) \ 166 new_hash[i] = old_hash[j], old_hash[j] = NULL; \ 169 while (again++ == 1); \ 171 pr->pr##_table = new_hash, pr->pr##_size = new_size; \ 173 assert(pr->pr##_used == used); \ 175 su_free(home, old_hash); \ 181 int prefix##_is_full(prefix##_t const *pr) \ 183 return pr->pr##_table == NULL || 3 * pr->pr##_used > 2 * pr->pr##_size; \ 187 entry_t **prefix##_hash(prefix##_t const *pr, hash_value_t hv) \ 189 return pr->pr##_table + hv % pr->pr##_size; \ 193 entry_t **prefix##_next(prefix##_t const *pr, entry_t * const *ee) \ 195 if (++ee < pr->pr##_table + pr->pr##_size && ee >= pr->pr##_table) \ 196 return (entry_t **)ee; \ 198 return pr->pr##_table; \ 202 void prefix##_append(prefix##_t *pr, entry_t const *e) \ 207 for (ee = prefix##_hash(pr, hfun(e)); *ee; ee = prefix##_next(pr, ee)) \ 209 *ee = (entry_t *)e; \ 213 void prefix##_insert(prefix##_t *pr, entry_t const *e) \ 219 for (ee = prefix##_hash(pr, hfun(e)); \ 221 ee = prefix##_next(pr, ee)) \ 222 *ee = (entry_t *)e, e = e0; \ 223 *ee = (entry_t *)e; \ 227 int prefix##_remove(prefix##_t *pr, entry_t const *e) \ 230 size_t size = pr->pr##_size; \ 231 entry_t **htable = pr->pr##_table; \ 236 for (i = hfun(e) % size; htable[i]; i = (i + 1) % size) \ 237 if (e == htable[i]) \ 241 if (!htable[i]) return -1; \ 244 for (j = (i + 1) % size; htable[j]; j = (j + 1) % size) { \ 246 k = hfun(htable[j]) % size; \ 250 if (j > i ? (i < k && k < j) : (i < k || k < j)) \ 253 htable[i] = htable[j], i = j; \ 262 extern int prefix##_dummy
Sofia-SIP 1.12.11devel -
Copyright (C) 2006 Nokia Corporation. All rights reserved.
Licensed under the terms of the GNU Lesser General Public License.