su 1.12.11devel
/build/buildd/sofia-sip-1.12.11+20110422/libsofia-sip-ua/su/sofia-sip/htable2.h
Go to the documentation of this file.
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 
 All Data Structures Files Functions Variables Typedefs Enumerator Defines

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