su  1.12.11devel
 All Data Structures Files Functions Variables Typedefs Enumerator Macros Groups Pages
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
26 
27 #define HTABLE_H
28 
59 typedef 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
85 
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) \
103 HTABLE_SCOPE int prefix##_resize(su_home_t *, prefix##_t pr[1], size_t); \
104 HTABLE_SCOPE int prefix##_is_full(prefix##_t const *); \
105 HTABLE_SCOPE entry_t **prefix##_hash(prefix##_t const *, hash_value_t hv); \
106 HTABLE_SCOPE entry_t **prefix##_next(prefix##_t const *, entry_t * const *ee); \
107 HTABLE_SCOPE void prefix##_append(prefix##_t *pr, entry_t const *e); \
108 HTABLE_SCOPE void prefix##_insert(prefix##_t *pr, entry_t const *e); \
109 HTABLE_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  \
128 HTABLE_SCOPE \
129 int 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 \
180 HTABLE_SCOPE \
181 int prefix##_is_full(prefix##_t const *pr) \
182 { \
183  return pr->pr##_table == NULL || 3 * pr->pr##_used > 2 * pr->pr##_size; \
184 } \
185 \
186 HTABLE_SCOPE \
187 entry_t **prefix##_hash(prefix##_t const *pr, hash_value_t hv) \
188 { \
189  return pr->pr##_table + hv % pr->pr##_size; \
190 } \
191 \
192 HTABLE_SCOPE \
193 entry_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 \
201 HTABLE_SCOPE \
202 void 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 \
212 HTABLE_SCOPE \
213 void 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 \
226 HTABLE_SCOPE \
227 int 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 } \
262 extern 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.