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 
00080 #define HTABLE2_DECLARE2(type, sname, pr, entrytype, size_t)    \
00081 typedef struct sname { \
00082   size_t pr##size; \
00083   size_t pr##used; \
00084   entrytype *pr##table; \
00085 } type
00086 
00087 #define HTABLE2_DECLARE(sname, prefix, pr, entrytype)   \
00088   HTABLE2_DECLARE2(prefix##t, sname, pr, entrytype, unsigned)
00089 
00090 #ifndef HTABLE2_SCOPE
00091 
00092 #define HTABLE2_SCOPE su_inline
00093 #endif
00094 
00108 #define HTABLE2_PROTOS2(type, prefix, pr, entrytype, size_t)        \
00109 HTABLE2_SCOPE int prefix##_resize(void *a, type *, size_t); \
00110 HTABLE2_SCOPE int prefix##_is_full(type const *); \
00111 HTABLE2_SCOPE entrytype *prefix##_hash(type const *, hash_value_t); \
00112 HTABLE2_SCOPE entrytype *prefix##_next(type const *, entrytype *); \
00113 HTABLE2_SCOPE entrytype *prefix##_append(type *, entrytype); \
00114 HTABLE2_SCOPE entrytype *prefix##_insert(type *, entrytype); \
00115 HTABLE2_SCOPE int prefix##_remove(type *, entrytype const)
00116 
00117 #define HTABLE2_PROTOS(type, prefix, pr, entrytype) \
00118   HTABLE2_PROTOS2(type, prefix, pr, entrytype, unsigned)
00119 
00140 #define HTABLE2_BODIES2(type, prefix, pr, entrytype, size_t,            \
00141                         hfun, is_used, reclaim, is_equal, halloc)       \
00142  \
00143 HTABLE2_SCOPE \
00144 int prefix##_resize(void *realloc_arg, \
00145                     type pr[1], \
00146                     size_t new_size) \
00147 { \
00148   entrytype *new_hash; \
00149   entrytype *old_hash = pr->pr##table; \
00150   size_t old_size; \
00151   size_t i, j, i0; \
00152   size_t again = 0, used = 0, collisions = 0; \
00153 \
00154   (void)realloc_arg; \
00155 \
00156   if (new_size == 0) \
00157     new_size = 2 * pr->pr##size + 1; \
00158   if (new_size < HTABLE2_MIN_SIZE) \
00159     new_size = HTABLE2_MIN_SIZE; \
00160   if (new_size < 5 * pr->pr##used / 4) \
00161     new_size = 5 * pr->pr##used / 4; \
00162 \
00163   if (!(new_hash = halloc(realloc_arg, NULL, sizeof(*new_hash) * new_size))) \
00164     return -1; \
00165 \
00166   for (i = 0; i < new_size; i++) { \
00167     (reclaim(&new_hash[i])); \
00168   } \
00169   old_size = pr->pr##size; \
00170 \
00171   do for (j = 0; j < old_size; j++) { \
00172     if (!is_used(old_hash[j])) \
00173       continue; \
00174 \
00175     if (again < 2 && hfun(old_hash[j]) % old_size > j) { \
00176       /* Wrapped, leave entry for second pass */ \
00177       again = 1; continue; \
00178     } \
00179 \
00180     i0 = hfun(old_hash[j]) % new_size; \
00181 \
00182     for (i = i0; is_used(new_hash[i]); \
00183          i = (i + 1) % new_size, assert(i != i0)) \
00184       collisions++; \
00185 \
00186     new_hash[i] = old_hash[j]; reclaim(&old_hash[j]); \
00187     used++; \
00188   } \
00189   while (again++ == 1); \
00190 \
00191   pr->pr##table = new_hash, pr->pr##size = new_size; \
00192 \
00193   if (old_hash) old_hash = halloc(realloc_arg, old_hash, 0);    \
00194 \
00195   assert(pr->pr##used == used);\
00196 \
00197   return 0; \
00198 } \
00199 \
00200 HTABLE2_SCOPE \
00201 int prefix##_is_full(type const *pr) \
00202 { \
00203   return pr->pr##table == NULL || 3 * pr->pr##used > 2 * pr->pr##size; \
00204 } \
00205 \
00206 HTABLE2_SCOPE \
00207 entrytype *prefix##_hash(type const *pr, hash_value_t hv) \
00208 { \
00209   return pr->pr##table + hv % pr->pr##size; \
00210 } \
00211 \
00212 HTABLE2_SCOPE \
00213 entrytype *prefix##_next(type const *pr, entrytype *ee) \
00214 { \
00215   if (++ee < pr->pr##table + pr->pr##size && ee >= pr->pr##table) \
00216     return ee; \
00217   else \
00218     return pr->pr##table; \
00219 }  \
00220 \
00221 HTABLE2_SCOPE \
00222 entrytype *prefix##_append(type *pr, entrytype e) \
00223 { \
00224   entrytype *ee; \
00225 \
00226   assert(pr->pr##used < pr->pr##size); \
00227   if (pr->pr##used == pr->pr##size) \
00228     return (entrytype *)0; \
00229 \
00230   pr->pr##used++; \
00231   for (ee = prefix##_hash(pr, hfun(e)); \
00232        is_used(*ee); \
00233        ee = prefix##_next(pr, ee)) \
00234    ; \
00235   *ee = e; \
00236 \
00237   return ee; \
00238 } \
00239 \
00240 HTABLE2_SCOPE \
00241 entrytype *prefix##_insert(type *pr, entrytype e) \
00242 { \
00243   entrytype e0; \
00244   entrytype *ee; \
00245 \
00246   assert(pr->pr##used < pr->pr##size); \
00247   if (pr->pr##used == pr->pr##size) \
00248     return (entrytype *)0; \
00249 \
00250   pr->pr##used++; \
00251   /* Insert entry into hash table (before other entries with same hash) */ \
00252   for (ee = prefix##_hash(pr, hfun(e));  \
00253        is_used((*ee)); \
00254        ee = prefix##_next(pr, ee)) \
00255     *ee = e, e = e0; \
00256   *ee = e; \
00257 \
00258   return ee; \
00259 } \
00260 \
00261 HTABLE2_SCOPE \
00262 int prefix##_remove(type *pr, entrytype const e) \
00263 { \
00264   size_t i, j, k, size = pr->pr##size; \
00265   entrytype *htable = pr->pr##table; \
00266 \
00267   /* Search for entry */ \
00268   for (i = hfun(e) % size; is_used(htable[i]); i = (i + 1) % size) \
00269     if (is_equal(e, htable[i])) \
00270       break; \
00271 \
00272   if (!is_used(htable[i])) return -1; \
00273 \
00274   /* Move table entries towards their primary place  */ \
00275   for (j = (i + 1) % size; is_used(htable[j]); j = (j + 1) % size) { \
00276     /* k is primary place for entry */ \
00277     k = hfun(htable[j]) % size; \
00278     if (k == j)                 /* entry is in its primary place? */ \
00279       continue; \
00280     /* primary place is between i and j - do not move this to i */ \
00281     if (j > i ? (i < k && k < j) : (i < k || k < j)) \
00282       continue; \
00283 \
00284     htable[i] = htable[j], i = j; \
00285   } \
00286 \
00287   pr->pr##used--; \
00288 \
00289   reclaim(&htable[i]); \
00290 \
00291   return 0; \
00292 } \
00293 extern int const prefix##_dummy
00294 
00295 #define HTABLE2_BODIES(type, prefix, pr, entrytype, \
00296                         hfun, is_used, reclaim, is_equal, halloc) \
00297   HTABLE2_BODIES2(type, prefix, pr, entrytype, unsigned, \
00298                         hfun, is_used, reclaim, is_equal, halloc) 
00299 
00300 
00301 #endif 

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