Loading...
Searching...
No Matches
Go to the documentation of this file.
62typedef unsigned long hash_value_t;
65#define HTABLE2_MIN_SIZE 31
81#define HTABLE2_DECLARE2(type, sname, pr, entrytype, sizetype) \
82typedef 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) \
111HTABLE2_SCOPE int prefix##_resize(void *a, type *, sizetype); \
112HTABLE2_SCOPE int prefix##_is_full(type const *); \
113HTABLE2_SCOPE entrytype *prefix##_hash(type const *, hash_value_t); \
114HTABLE2_SCOPE entrytype *prefix##_next(type const *, entrytype *); \
115HTABLE2_SCOPE entrytype *prefix##_append(type *, entrytype); \
116HTABLE2_SCOPE entrytype *prefix##_insert(type *, entrytype); \
117HTABLE2_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) \
146int 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);\
203int prefix##_is_full(type const *pr) \
205 return pr->pr##table == NULL || 3 * pr->pr##used > 2 * pr->pr##size; \
209entrytype *prefix##_hash(type const *pr, hash_value_t hv) \
211 return pr->pr##table + hv % pr->pr##size; \
215entrytype *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; \
224entrytype *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)) \
243entrytype *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)) \
264int 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]); \
295extern 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.