Go to the documentation of this file. 62 typedef unsigned long hash_value_t;
65 #define HTABLE2_MIN_SIZE 31 81 #define HTABLE2_DECLARE2(type, sname, pr, entrytype, sizetype) \ 82 typedef struct sname { \ 85 entrytype *pr##table; \ 88 #define HTABLE2_DECLARE(sname, prefix, pr, entrytype) \ 89 HTABLE2_DECLARE2(prefix##t, sname, pr, entrytype, unsigned) 93 #define HTABLE2_SCOPE su_inline 110 #define HTABLE2_PROTOS2(type, prefix, pr, entrytype, sizetype) \ 111 HTABLE2_SCOPE int prefix##_resize(void *a, type *, sizetype); \ 112 HTABLE2_SCOPE int prefix##_is_full(type const *); \ 113 HTABLE2_SCOPE entrytype *prefix##_hash(type const *, hash_value_t); \ 114 HTABLE2_SCOPE entrytype *prefix##_next(type const *, entrytype *); \ 115 HTABLE2_SCOPE entrytype *prefix##_append(type *, entrytype); \ 116 HTABLE2_SCOPE entrytype *prefix##_insert(type *, entrytype); \ 117 HTABLE2_SCOPE int prefix##_remove(type *, entrytype const) 119 #define HTABLE2_PROTOS(type, prefix, pr, entrytype) \ 120 HTABLE2_PROTOS2(type, prefix, pr, entrytype, unsigned) 142 #define HTABLE2_BODIES2(type, prefix, pr, entrytype, sizetype, \ 143 hfun, is_used, reclaim, is_equal, halloc) \ 146 int prefix##_resize(void *realloc_arg, \ 150 entrytype *new_hash; \ 151 entrytype *old_hash = pr->pr##table; \ 154 sizetype again = 0, used = 0, collisions = 0; \ 159 new_size = 2 * pr->pr##size + 1; \ 160 if (new_size < HTABLE2_MIN_SIZE) \ 161 new_size = HTABLE2_MIN_SIZE; \ 162 if (new_size < 5 * pr->pr##used / 4) \ 163 new_size = 5 * pr->pr##used / 4; \ 165 if (!(new_hash = halloc(realloc_arg, NULL, sizeof(*new_hash) * new_size))) \ 168 for (i = 0; i < new_size; i++) { \ 169 (reclaim(&new_hash[i])); \ 171 old_size = pr->pr##size; \ 173 do for (j = 0; j < old_size; j++) { \ 174 if (!is_used(old_hash[j])) \ 177 if (again < 2 && hfun(old_hash[j]) % old_size > j) { \ 179 again = 1; continue; \ 182 i0 = hfun(old_hash[j]) % new_size; \ 184 for (i = i0; is_used(new_hash[i]); \ 185 i = (i + 1) % new_size, assert(i != i0)) \ 188 new_hash[i] = old_hash[j]; reclaim(&old_hash[j]); \ 191 while (again++ == 1); \ 193 pr->pr##table = new_hash, pr->pr##size = new_size; \ 195 if (old_hash) old_hash = halloc(realloc_arg, old_hash, 0); \ 197 assert(pr->pr##used == used);\ 203 int prefix##_is_full(type const *pr) \ 205 return pr->pr##table == NULL || 3 * pr->pr##used > 2 * pr->pr##size; \ 209 entrytype *prefix##_hash(type const *pr, hash_value_t hv) \ 211 return pr->pr##table + hv % pr->pr##size; \ 215 entrytype *prefix##_next(type const *pr, entrytype *ee) \ 217 if (++ee < pr->pr##table + pr->pr##size && ee >= pr->pr##table) \ 220 return pr->pr##table; \ 224 entrytype *prefix##_append(type *pr, entrytype e) \ 228 assert(pr->pr##used < pr->pr##size); \ 229 if (pr->pr##used == pr->pr##size) \ 230 return (entrytype *)0; \ 233 for (ee = prefix##_hash(pr, hfun(e)); \ 235 ee = prefix##_next(pr, ee)) \ 243 entrytype *prefix##_insert(type *pr, entrytype e) \ 248 assert(pr->pr##used < pr->pr##size); \ 249 if (pr->pr##used == pr->pr##size) \ 250 return (entrytype *)0; \ 254 for (ee = prefix##_hash(pr, hfun(e)); \ 256 ee = prefix##_next(pr, ee)) \ 264 int prefix##_remove(type *pr, entrytype const e) \ 266 sizetype i, j, k, size = pr->pr##size; \ 267 entrytype *htable = pr->pr##table; \ 270 for (i = hfun(e) % size; is_used(htable[i]); i = (i + 1) % size) \ 271 if (is_equal(e, htable[i])) \ 274 if (!is_used(htable[i])) return -1; \ 277 for (j = (i + 1) % size; is_used(htable[j]); j = (j + 1) % size) { \ 279 k = hfun(htable[j]) % size; \ 283 if (j > i ? (i < k && k < j) : (i < k || k < j)) \ 286 htable[i] = htable[j], i = j; \ 291 reclaim(&htable[i]); \ 295 extern int const prefix##_dummy 297 #define HTABLE2_BODIES(type, prefix, pr, entrytype, \ 298 hfun, is_used, reclaim, is_equal, halloc) \ 299 HTABLE2_BODIES2(type, prefix, pr, entrytype, unsigned, \ 300 hfun, is_used, reclaim, is_equal, halloc)
Sofia-SIP 1.12.11devel -
Copyright (C) 2006 Nokia Corporation. All rights reserved.
Licensed under the terms of the GNU Lesser General Public License.