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 
00078 #define HTABLE2_DECLARE(sname, prefix, pr, entrytype)   \
00079 struct sname { \
00080   unsigned pr##size; \
00081   unsigned pr##used; \
00082   entrytype *pr##table;  \
00083 }
00084 
00085 #ifndef HTABLE2_SCOPE
00086 
00087 #define HTABLE2_SCOPE static inline
00088 #endif
00089 
00101 #define HTABLE2_PROTOS(type, prefix, pr, entrytype)                     \
00102 HTABLE2_SCOPE int prefix##_resize(void *a, type pr[1], unsigned); \
00103 HTABLE2_SCOPE int prefix##_is_full(type const *); \
00104 HTABLE2_SCOPE entrytype *prefix##_hash(type const *, hash_value_t hv); \
00105 HTABLE2_SCOPE entrytype *prefix##_next(type const *, entrytype *ee); \
00106 HTABLE2_SCOPE void prefix##_append(type *pr, entrytype e); \
00107 HTABLE2_SCOPE void prefix##_insert(type *pr, entrytype e); \
00108 HTABLE2_SCOPE int prefix##_remove(type *, entrytype const e)
00109 
00127 #define HTABLE2_BODIES(type, prefix, pr, entrytype,                     \
00128                        hfun, is_used, reclaim, is_equal, halloc)        \
00129  \
00130 HTABLE2_SCOPE \
00131 int prefix##_resize(void *realloc_arg, \
00132                     type pr[1], \
00133                     unsigned new_size) \
00134 { \
00135   entrytype *new_hash; \
00136   entrytype *old_hash = pr->pr##table; \
00137   unsigned old_size; \
00138   unsigned i, j, i0; \
00139   unsigned again = 0, used = 0, collisions = 0; \
00140 \
00141   (void)realloc_arg; \
00142 \
00143   if (new_size == 0) \
00144     new_size = 2 * pr->pr##size + 1; \
00145   if (new_size < HTABLE2_MIN_SIZE) \
00146     new_size = HTABLE2_MIN_SIZE; \
00147 \
00148   if (!(new_hash = halloc(realloc_arg, NULL, sizeof(*new_hash) * new_size))) \
00149     return -1; \
00150 \
00151   memset(new_hash, 0, sizeof(*new_hash) * new_size); \
00152   old_size = pr->pr##size; \
00153 \
00154   do for (j = 0; j < old_size; j++) { \
00155     if (!is_used(old_hash[j])) \
00156       continue; \
00157 \
00158     if (again < 2 && hfun(old_hash[j]) % old_size > j) { \
00159       /* Wrapped, leave entry for second pass */ \
00160       again = 1; continue; \
00161     } \
00162 \
00163     i0 = hfun(old_hash[j]) % new_size; \
00164 \
00165     for (i = i0; is_used(new_hash[i]); \
00166          i = (i + 1) % new_size, assert(i != i0)) \
00167       collisions++; \
00168 \
00169     new_hash[i] = old_hash[j]; reclaim(&old_hash[j]); \
00170     used++; \
00171   } \
00172   while (again++ == 1); \
00173 \
00174   pr->pr##table = new_hash, pr->pr##size = new_size; \
00175 \
00176   if (old_hash) old_hash = halloc(realloc_arg, old_hash, 0);    \
00177 \
00178   assert(pr->pr##used == used);\
00179 \
00180   return 0; \
00181 } \
00182 \
00183 HTABLE2_SCOPE \
00184 int prefix##_is_full(type const *pr) \
00185 { \
00186   return pr->pr##table == NULL || 3 * pr->pr##used > 2 * pr->pr##size; \
00187 } \
00188 \
00189 HTABLE2_SCOPE \
00190 entrytype *prefix##_hash(type const *pr, hash_value_t hv) \
00191 { \
00192   return pr->pr##table + hv % pr->pr##size; \
00193 } \
00194 \
00195 HTABLE2_SCOPE \
00196 entrytype *prefix##_next(type const *pr, entrytype *ee) \
00197 { \
00198   if (++ee < pr->pr##table + pr->pr##size && ee >= pr->pr##table) \
00199     return ee; \
00200   else \
00201     return pr->pr##table; \
00202 }  \
00203 \
00204 HTABLE2_SCOPE \
00205 void prefix##_append(type *pr, entrytype e) \
00206 { \
00207   entrytype *ee; \
00208 \
00209   pr->pr##used++; \
00210   for (ee = prefix##_hash(pr, hfun(e)); \
00211        is_used(*ee); \
00212        ee = prefix##_next(pr, ee)) \
00213    ; \
00214   *ee = e; \
00215 } \
00216 \
00217 HTABLE2_SCOPE \
00218 void prefix##_insert(type *pr, entrytype e) \
00219 { \
00220   entrytype e0; \
00221   entrytype *ee; \
00222 \
00223   pr->pr##used++; \
00224   /* Insert entry into hash table (before other entries with same hash) */ \
00225   for (ee = prefix##_hash(pr, hfun(e));  \
00226        is_used((*ee)); \
00227        ee = prefix##_next(pr, ee)) \
00228     *ee = e, e = e0; \
00229   *ee = e; \
00230 } \
00231 \
00232 HTABLE2_SCOPE \
00233 int prefix##_remove(type *pr, entrytype const e) \
00234 { \
00235   unsigned i, j, k, size = pr->pr##size; \
00236   entrytype *htable = pr->pr##table; \
00237 \
00238   /* Search for entry */ \
00239   for (i = hfun(e) % size; is_used(htable[i]); i = (i + 1) % size) \
00240     if (is_equal(e, htable[i])) \
00241       break; \
00242 \
00243   assert(is_used(htable[i])); if (!is_used(htable[i])) return -1; \
00244 \
00245   /* Move table entries towards their primary place  */ \
00246   for (j = (i + 1) % size; is_used(htable[j]); j = (j + 1) % size) { \
00247     /* k is primary place for entry */ \
00248     k = hfun(htable[j]) % size; \
00249     if (k == j)                 /* entry is in its primary place? */ \
00250       continue; \
00251     /* primary place is between i and j - do not move this to i */ \
00252     if (j > i ? (i < k && k < j) : (i < k || k < j)) \
00253       continue; \
00254 \
00255     htable[i] = htable[j], i = j; \
00256   } \
00257 \
00258   pr->pr##used--; \
00259 \
00260   reclaim(&htable[i]); \
00261 \
00262   return 0; \
00263 } \
00264 extern int const prefix##_dummy
00265 
00266 #endif 

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