su  1.12.11devel
 All Data Structures Files Functions Variables Typedefs Enumerator Macros Groups Pages
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
26 
27 #define HTABLE2_H
28 
62 typedef unsigned long hash_value_t;
63 
65 #define HTABLE2_MIN_SIZE 31
66 
81 #define HTABLE2_DECLARE2(type, sname, pr, entrytype, sizetype) \
82 typedef 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
92 
93 #define HTABLE2_SCOPE su_inline
94 #endif
95 
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)
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  \
145 HTABLE2_SCOPE \
146 int 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 \
202 HTABLE2_SCOPE \
203 int prefix##_is_full(type const *pr) \
204 { \
205  return pr->pr##table == NULL || 3 * pr->pr##used > 2 * pr->pr##size; \
206 } \
207 \
208 HTABLE2_SCOPE \
209 entrytype *prefix##_hash(type const *pr, hash_value_t hv) \
210 { \
211  return pr->pr##table + hv % pr->pr##size; \
212 } \
213 \
214 HTABLE2_SCOPE \
215 entrytype *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 \
223 HTABLE2_SCOPE \
224 entrytype *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 \
242 HTABLE2_SCOPE \
243 entrytype *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 \
263 HTABLE2_SCOPE \
264 int 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 } \
295 extern 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.