su 1.12.11devel
Loading...
Searching...
No Matches
htable.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 HTABLE_H
27#define HTABLE_H
28
59typedef unsigned long hash_value_t;
60
62#define HTABLE_MIN_SIZE 31
63
74#define HTABLE_DECLARE(prefix, pr, entry_t) \
75 HTABLE_DECLARE_WITH(prefix, pr, entry_t, unsigned, hash_value_t)
76
77#define HTABLE_DECLARE_WITH(prefix, pr, entry_t, size_t, hash_value_t) \
78 typedef struct prefix##_s { \
79 size_t pr##_size; \
80 size_t pr##_used; \
81 entry_t**pr##_table; \
82 } prefix##_t
83
84#ifndef HTABLE_SCOPE
86#define HTABLE_SCOPE su_inline
87#endif
88
99#define HTABLE_PROTOS(prefix, pr, entry_t) \
100 HTABLE_PROTOS_WITH(prefix, pr, entry_t, unsigned, hash_value_t)
101
102#define HTABLE_PROTOS_WITH(prefix, pr, entry_t, size_t, hash_value_t) \
103HTABLE_SCOPE int prefix##_resize(su_home_t *, prefix##_t pr[1], size_t); \
104HTABLE_SCOPE int prefix##_is_full(prefix##_t const *); \
105HTABLE_SCOPE entry_t **prefix##_hash(prefix##_t const *, hash_value_t hv); \
106HTABLE_SCOPE entry_t **prefix##_next(prefix##_t const *, entry_t * const *ee); \
107HTABLE_SCOPE void prefix##_append(prefix##_t *pr, entry_t const *e); \
108HTABLE_SCOPE void prefix##_insert(prefix##_t *pr, entry_t const *e); \
109HTABLE_SCOPE int prefix##_remove(prefix##_t *, entry_t const *e)
110
123#define HTABLE_BODIES(prefix, pr, entry_t, hfun) \
124 HTABLE_BODIES_WITH(prefix, pr, entry_t, hfun, unsigned, hash_value_t)
125
126#define HTABLE_BODIES_WITH(prefix, pr, entry_t, hfun, size_t, hash_value_t) \
127 \
128HTABLE_SCOPE \
129int prefix##_resize(su_home_t *home, \
130 prefix##_t pr[], \
131 size_t new_size) \
132{ \
133 entry_t **new_hash; \
134 entry_t **old_hash = pr->pr##_table; \
135 size_t old_size; \
136 size_t i, j, i0; \
137 unsigned again = 0; \
138 size_t used = 0, collisions = 0; \
139\
140 if (new_size == 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; \
146\
147 if (!(new_hash = su_zalloc(home, sizeof(*new_hash) * new_size))) \
148 return -1; \
149\
150 old_size = pr->pr##_size; \
151\
152 do for (j = 0; j < old_size; j++) { \
153 if (!old_hash[j]) \
154 continue; \
155\
156 if (again < 2 && hfun(old_hash[j]) % old_size > j) { \
157 /* Wrapped, leave entry for second pass */ \
158 again = 1; continue; \
159 } \
160\
161 i0 = hfun(old_hash[j]) % new_size; \
162\
163 for (i = i0; new_hash[i]; i = (i + 1) % new_size, assert(i != i0)) \
164 collisions++; \
165\
166 new_hash[i] = old_hash[j], old_hash[j] = NULL; \
167 used++; \
168 } \
169 while (again++ == 1); \
170\
171 pr->pr##_table = new_hash, pr->pr##_size = new_size; \
172\
173 assert(pr->pr##_used == used); \
174\
175 su_free(home, old_hash); \
176\
177 return 0; \
178} \
179\
180HTABLE_SCOPE \
181int prefix##_is_full(prefix##_t const *pr) \
182{ \
183 return pr->pr##_table == NULL || 3 * pr->pr##_used > 2 * pr->pr##_size; \
184} \
185\
186HTABLE_SCOPE \
187entry_t **prefix##_hash(prefix##_t const *pr, hash_value_t hv) \
188{ \
189 return pr->pr##_table + hv % pr->pr##_size; \
190} \
191\
192HTABLE_SCOPE \
193entry_t **prefix##_next(prefix##_t const *pr, entry_t * const *ee) \
194{ \
195 if (++ee < pr->pr##_table + pr->pr##_size && ee >= pr->pr##_table) \
196 return (entry_t **)ee; \
197 else \
198 return pr->pr##_table; \
199} \
200\
201HTABLE_SCOPE \
202void prefix##_append(prefix##_t *pr, entry_t const *e) \
203{ \
204 entry_t **ee; \
205\
206 pr->pr##_used++; \
207 for (ee = prefix##_hash(pr, hfun(e)); *ee; ee = prefix##_next(pr, ee)) \
208 ; \
209 *ee = (entry_t *)e; \
210} \
211\
212HTABLE_SCOPE \
213void prefix##_insert(prefix##_t *pr, entry_t const *e) \
214{ \
215 entry_t *e0, **ee; \
216\
217 pr->pr##_used++; \
218 /* Insert entry into hash table (before other entries with same hash) */ \
219 for (ee = prefix##_hash(pr, hfun(e)); \
220 (e0 = *ee); \
221 ee = prefix##_next(pr, ee)) \
222 *ee = (entry_t *)e, e = e0; \
223 *ee = (entry_t *)e; \
224} \
225\
226HTABLE_SCOPE \
227int prefix##_remove(prefix##_t *pr, entry_t const *e) \
228{ \
229 size_t i, j, k; \
230 size_t size = pr->pr##_size; \
231 entry_t **htable = pr->pr##_table; \
232\
233 if (!e) return -1; \
234\
235 /* Search for entry */ \
236 for (i = hfun(e) % size; htable[i]; i = (i + 1) % size) \
237 if (e == htable[i]) \
238 break; \
239\
240 /* Entry is not in table? */ \
241 if (!htable[i]) return -1; \
242\
243 /* Move table entries towards their primary place */ \
244 for (j = (i + 1) % size; htable[j]; j = (j + 1) % size) { \
245 /* k is primary place for entry */ \
246 k = hfun(htable[j]) % size; \
247 if (k == j) /* entry is in its primary place? */ \
248 continue; \
249 /* primary place is between i and j - do not move this to i */ \
250 if (j > i ? (i < k && k < j) : (i < k || k < j)) \
251 continue; \
252\
253 htable[i] = htable[j], i = j; \
254 } \
255\
256 pr->pr##_used--; \
257\
258 htable[i] = NULL; \
259\
260 return 0; \
261} \
262extern int prefix##_dummy
263
264#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.