su 1.12.10
|
00001 /* 00002 * This file is part of the Sofia-SIP package 00003 * 00004 * Copyright (C) 2005 Nokia Corporation. 00005 * 00006 * Contact: Pekka Pessi <pekka.pessi@nokia-email.address.hidden> 00007 * 00008 * This library is free software; you can redistribute it and/or 00009 * modify it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation; either version 2.1 of 00011 * the License, or (at your option) any later version. 00012 * 00013 * This library is distributed in the hope that it will be useful, but 00014 * WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00016 * Lesser General Public License for more details. 00017 * 00018 * You should have received a copy of the GNU Lesser General Public 00019 * License along with this library; if not, write to the Free Software 00020 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 00021 * 02110-1301 USA 00022 * 00023 */ 00024 00025 #ifndef HTABLE2_H 00026 00027 #define HTABLE2_H 00028 00062 typedef unsigned long hash_value_t; 00063 00065 #define HTABLE2_MIN_SIZE 31 00066 00081 #define HTABLE2_DECLARE2(type, sname, pr, entrytype, sizetype) \ 00082 typedef struct sname { \ 00083 sizetype pr##size; \ 00084 sizetype pr##used; \ 00085 entrytype *pr##table; \ 00086 } type 00087 00088 #define HTABLE2_DECLARE(sname, prefix, pr, entrytype) \ 00089 HTABLE2_DECLARE2(prefix##t, sname, pr, entrytype, unsigned) 00090 00091 #ifndef HTABLE2_SCOPE 00092 00093 #define HTABLE2_SCOPE su_inline 00094 #endif 00095 00110 #define HTABLE2_PROTOS2(type, prefix, pr, entrytype, sizetype) \ 00111 HTABLE2_SCOPE int prefix##_resize(void *a, type *, sizetype); \ 00112 HTABLE2_SCOPE int prefix##_is_full(type const *); \ 00113 HTABLE2_SCOPE entrytype *prefix##_hash(type const *, hash_value_t); \ 00114 HTABLE2_SCOPE entrytype *prefix##_next(type const *, entrytype *); \ 00115 HTABLE2_SCOPE entrytype *prefix##_append(type *, entrytype); \ 00116 HTABLE2_SCOPE entrytype *prefix##_insert(type *, entrytype); \ 00117 HTABLE2_SCOPE int prefix##_remove(type *, entrytype const) 00118 00119 #define HTABLE2_PROTOS(type, prefix, pr, entrytype) \ 00120 HTABLE2_PROTOS2(type, prefix, pr, entrytype, unsigned) 00121 00142 #define HTABLE2_BODIES2(type, prefix, pr, entrytype, sizetype, \ 00143 hfun, is_used, reclaim, is_equal, halloc) \ 00144 \ 00145 HTABLE2_SCOPE \ 00146 int prefix##_resize(void *realloc_arg, \ 00147 type pr[1], \ 00148 sizetype new_size) \ 00149 { \ 00150 entrytype *new_hash; \ 00151 entrytype *old_hash = pr->pr##table; \ 00152 sizetype old_size; \ 00153 sizetype i, j, i0; \ 00154 sizetype again = 0, used = 0, collisions = 0; \ 00155 \ 00156 (void)realloc_arg; \ 00157 \ 00158 if (new_size == 0) \ 00159 new_size = 2 * pr->pr##size + 1; \ 00160 if (new_size < HTABLE2_MIN_SIZE) \ 00161 new_size = HTABLE2_MIN_SIZE; \ 00162 if (new_size < 5 * pr->pr##used / 4) \ 00163 new_size = 5 * pr->pr##used / 4; \ 00164 \ 00165 if (!(new_hash = halloc(realloc_arg, NULL, sizeof(*new_hash) * new_size))) \ 00166 return -1; \ 00167 \ 00168 for (i = 0; i < new_size; i++) { \ 00169 (reclaim(&new_hash[i])); \ 00170 } \ 00171 old_size = pr->pr##size; \ 00172 \ 00173 do for (j = 0; j < old_size; j++) { \ 00174 if (!is_used(old_hash[j])) \ 00175 continue; \ 00176 \ 00177 if (again < 2 && hfun(old_hash[j]) % old_size > j) { \ 00178 /* Wrapped, leave entry for second pass */ \ 00179 again = 1; continue; \ 00180 } \ 00181 \ 00182 i0 = hfun(old_hash[j]) % new_size; \ 00183 \ 00184 for (i = i0; is_used(new_hash[i]); \ 00185 i = (i + 1) % new_size, assert(i != i0)) \ 00186 collisions++; \ 00187 \ 00188 new_hash[i] = old_hash[j]; reclaim(&old_hash[j]); \ 00189 used++; \ 00190 } \ 00191 while (again++ == 1); \ 00192 \ 00193 pr->pr##table = new_hash, pr->pr##size = new_size; \ 00194 \ 00195 if (old_hash) old_hash = halloc(realloc_arg, old_hash, 0); \ 00196 \ 00197 assert(pr->pr##used == used);\ 00198 \ 00199 return 0; \ 00200 } \ 00201 \ 00202 HTABLE2_SCOPE \ 00203 int prefix##_is_full(type const *pr) \ 00204 { \ 00205 return pr->pr##table == NULL || 3 * pr->pr##used > 2 * pr->pr##size; \ 00206 } \ 00207 \ 00208 HTABLE2_SCOPE \ 00209 entrytype *prefix##_hash(type const *pr, hash_value_t hv) \ 00210 { \ 00211 return pr->pr##table + hv % pr->pr##size; \ 00212 } \ 00213 \ 00214 HTABLE2_SCOPE \ 00215 entrytype *prefix##_next(type const *pr, entrytype *ee) \ 00216 { \ 00217 if (++ee < pr->pr##table + pr->pr##size && ee >= pr->pr##table) \ 00218 return ee; \ 00219 else \ 00220 return pr->pr##table; \ 00221 } \ 00222 \ 00223 HTABLE2_SCOPE \ 00224 entrytype *prefix##_append(type *pr, entrytype e) \ 00225 { \ 00226 entrytype *ee; \ 00227 \ 00228 assert(pr->pr##used < pr->pr##size); \ 00229 if (pr->pr##used == pr->pr##size) \ 00230 return (entrytype *)0; \ 00231 \ 00232 pr->pr##used++; \ 00233 for (ee = prefix##_hash(pr, hfun(e)); \ 00234 is_used(*ee); \ 00235 ee = prefix##_next(pr, ee)) \ 00236 ; \ 00237 *ee = e; \ 00238 \ 00239 return ee; \ 00240 } \ 00241 \ 00242 HTABLE2_SCOPE \ 00243 entrytype *prefix##_insert(type *pr, entrytype e) \ 00244 { \ 00245 entrytype e0; \ 00246 entrytype *ee; \ 00247 \ 00248 assert(pr->pr##used < pr->pr##size); \ 00249 if (pr->pr##used == pr->pr##size) \ 00250 return (entrytype *)0; \ 00251 \ 00252 pr->pr##used++; \ 00253 /* Insert entry into hash table (before other entries with same hash) */ \ 00254 for (ee = prefix##_hash(pr, hfun(e)); \ 00255 is_used((*ee)); \ 00256 ee = prefix##_next(pr, ee)) \ 00257 *ee = e, e = e0; \ 00258 *ee = e; \ 00259 \ 00260 return ee; \ 00261 } \ 00262 \ 00263 HTABLE2_SCOPE \ 00264 int prefix##_remove(type *pr, entrytype const e) \ 00265 { \ 00266 sizetype i, j, k, size = pr->pr##size; \ 00267 entrytype *htable = pr->pr##table; \ 00268 \ 00269 /* Search for entry */ \ 00270 for (i = hfun(e) % size; is_used(htable[i]); i = (i + 1) % size) \ 00271 if (is_equal(e, htable[i])) \ 00272 break; \ 00273 \ 00274 if (!is_used(htable[i])) return -1; \ 00275 \ 00276 /* Move table entries towards their primary place */ \ 00277 for (j = (i + 1) % size; is_used(htable[j]); j = (j + 1) % size) { \ 00278 /* k is primary place for entry */ \ 00279 k = hfun(htable[j]) % size; \ 00280 if (k == j) /* entry is in its primary place? */ \ 00281 continue; \ 00282 /* primary place is between i and j - do not move this to i */ \ 00283 if (j > i ? (i < k && k < j) : (i < k || k < j)) \ 00284 continue; \ 00285 \ 00286 htable[i] = htable[j], i = j; \ 00287 } \ 00288 \ 00289 pr->pr##used--; \ 00290 \ 00291 reclaim(&htable[i]); \ 00292 \ 00293 return 0; \ 00294 } \ 00295 extern int const prefix##_dummy 00296 00297 #define HTABLE2_BODIES(type, prefix, pr, entrytype, \ 00298 hfun, is_used, reclaim, is_equal, halloc) \ 00299 HTABLE2_BODIES2(type, prefix, pr, entrytype, unsigned, \ 00300 hfun, is_used, reclaim, is_equal, halloc) 00301 00302 00303 #endif