su 1.12.11devel
Loading...
Searching...
No Matches
htable2.h
Go to the documentation of this file.
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-email.address.hidden>
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 HTABLE2_H
27#define HTABLE2_H
28
62typedef unsigned long hash_value_t;
63
65#define HTABLE2_MIN_SIZE 31
66
81#define HTABLE2_DECLARE2(type, sname, pr, entrytype, sizetype) \
82typedef struct sname { \
83 sizetype pr##size; \
84 sizetype pr##used; \
85 entrytype *pr##table; \
86} type
87
88#define HTABLE2_DECLARE(sname, prefix, pr, entrytype) \
89 HTABLE2_DECLARE2(prefix##t, sname, pr, entrytype, unsigned)
90
91#ifndef HTABLE2_SCOPE
93#define HTABLE2_SCOPE su_inline
94#endif
95
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)
118
119#define HTABLE2_PROTOS(type, prefix, pr, entrytype) \
120 HTABLE2_PROTOS2(type, prefix, pr, entrytype, unsigned)
121
142#define HTABLE2_BODIES2(type, prefix, pr, entrytype, sizetype, \
143 hfun, is_used, reclaim, is_equal, halloc) \
144 \
145HTABLE2_SCOPE \
146int prefix##_resize(void *realloc_arg, \
147 type pr[1], \
148 sizetype new_size) \
149{ \
150 entrytype *new_hash; \
151 entrytype *old_hash = pr->pr##table; \
152 sizetype old_size; \
153 sizetype i, j, i0; \
154 sizetype again = 0, used = 0, collisions = 0; \
155\
156 (void)realloc_arg; \
157\
158 if (new_size == 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; \
164\
165 if (!(new_hash = halloc(realloc_arg, NULL, sizeof(*new_hash) * new_size))) \
166 return -1; \
167\
168 for (i = 0; i < new_size; i++) { \
169 (reclaim(&new_hash[i])); \
170 } \
171 old_size = pr->pr##size; \
172\
173 do for (j = 0; j < old_size; j++) { \
174 if (!is_used(old_hash[j])) \
175 continue; \
176\
177 if (again < 2 && hfun(old_hash[j]) % old_size > j) { \
178 /* Wrapped, leave entry for second pass */ \
179 again = 1; continue; \
180 } \
181\
182 i0 = hfun(old_hash[j]) % new_size; \
183\
184 for (i = i0; is_used(new_hash[i]); \
185 i = (i + 1) % new_size, assert(i != i0)) \
186 collisions++; \
187\
188 new_hash[i] = old_hash[j]; reclaim(&old_hash[j]); \
189 used++; \
190 } \
191 while (again++ == 1); \
192\
193 pr->pr##table = new_hash, pr->pr##size = new_size; \
194\
195 if (old_hash) old_hash = halloc(realloc_arg, old_hash, 0); \
196\
197 assert(pr->pr##used == used);\
198\
199 return 0; \
200} \
201\
202HTABLE2_SCOPE \
203int prefix##_is_full(type const *pr) \
204{ \
205 return pr->pr##table == NULL || 3 * pr->pr##used > 2 * pr->pr##size; \
206} \
207\
208HTABLE2_SCOPE \
209entrytype *prefix##_hash(type const *pr, hash_value_t hv) \
210{ \
211 return pr->pr##table + hv % pr->pr##size; \
212} \
213\
214HTABLE2_SCOPE \
215entrytype *prefix##_next(type const *pr, entrytype *ee) \
216{ \
217 if (++ee < pr->pr##table + pr->pr##size && ee >= pr->pr##table) \
218 return ee; \
219 else \
220 return pr->pr##table; \
221} \
222\
223HTABLE2_SCOPE \
224entrytype *prefix##_append(type *pr, entrytype e) \
225{ \
226 entrytype *ee; \
227\
228 assert(pr->pr##used < pr->pr##size); \
229 if (pr->pr##used == pr->pr##size) \
230 return (entrytype *)0; \
231\
232 pr->pr##used++; \
233 for (ee = prefix##_hash(pr, hfun(e)); \
234 is_used(*ee); \
235 ee = prefix##_next(pr, ee)) \
236 ; \
237 *ee = e; \
238\
239 return ee; \
240} \
241\
242HTABLE2_SCOPE \
243entrytype *prefix##_insert(type *pr, entrytype e) \
244{ \
245 entrytype e0; \
246 entrytype *ee; \
247\
248 assert(pr->pr##used < pr->pr##size); \
249 if (pr->pr##used == pr->pr##size) \
250 return (entrytype *)0; \
251\
252 pr->pr##used++; \
253 /* Insert entry into hash table (before other entries with same hash) */ \
254 for (ee = prefix##_hash(pr, hfun(e)); \
255 is_used((*ee)); \
256 ee = prefix##_next(pr, ee)) \
257 *ee = e, e = e0; \
258 *ee = e; \
259\
260 return ee; \
261} \
262\
263HTABLE2_SCOPE \
264int prefix##_remove(type *pr, entrytype const e) \
265{ \
266 sizetype i, j, k, size = pr->pr##size; \
267 entrytype *htable = pr->pr##table; \
268\
269 /* Search for entry */ \
270 for (i = hfun(e) % size; is_used(htable[i]); i = (i + 1) % size) \
271 if (is_equal(e, htable[i])) \
272 break; \
273\
274 if (!is_used(htable[i])) return -1; \
275\
276 /* Move table entries towards their primary place */ \
277 for (j = (i + 1) % size; is_used(htable[j]); j = (j + 1) % size) { \
278 /* k is primary place for entry */ \
279 k = hfun(htable[j]) % size; \
280 if (k == j) /* entry is in its primary place? */ \
281 continue; \
282 /* primary place is between i and j - do not move this to i */ \
283 if (j > i ? (i < k && k < j) : (i < k || k < j)) \
284 continue; \
285\
286 htable[i] = htable[j], i = j; \
287 } \
288\
289 pr->pr##used--; \
290\
291 reclaim(&htable[i]); \
292\
293 return 0; \
294} \
295extern int const prefix##_dummy
296
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)
301
302
303#endif

Sofia-SIP 1.12.11devel - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.