su 1.12.10

sofia-sip/htable.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 HTABLE_H
00026 
00027 #define HTABLE_H
00028 
00059 typedef unsigned long hash_value_t;
00060 
00062 #define HTABLE_MIN_SIZE 31
00063 
00074 #define HTABLE_DECLARE(prefix, pr, entry_t)             \
00075   HTABLE_DECLARE_WITH(prefix, pr, entry_t, unsigned, hash_value_t)
00076 
00077 #define HTABLE_DECLARE_WITH(prefix, pr, entry_t, size_t, hash_value_t)  \
00078   typedef struct prefix##_s {                                           \
00079     size_t pr##_size;                                                   \
00080     size_t pr##_used;                                                   \
00081     entry_t**pr##_table;                        \
00082   } prefix##_t
00083 
00084 #ifndef HTABLE_SCOPE
00085 
00086 #define HTABLE_SCOPE su_inline
00087 #endif
00088 
00099 #define HTABLE_PROTOS(prefix, pr, entry_t) \
00100   HTABLE_PROTOS_WITH(prefix, pr, entry_t, unsigned, hash_value_t)
00101 
00102 #define HTABLE_PROTOS_WITH(prefix, pr, entry_t, size_t, hash_value_t)   \
00103 HTABLE_SCOPE int prefix##_resize(su_home_t *, prefix##_t pr[1], size_t); \
00104 HTABLE_SCOPE int prefix##_is_full(prefix##_t const *); \
00105 HTABLE_SCOPE entry_t **prefix##_hash(prefix##_t const *, hash_value_t hv); \
00106 HTABLE_SCOPE entry_t **prefix##_next(prefix##_t const *, entry_t * const *ee); \
00107 HTABLE_SCOPE void prefix##_append(prefix##_t *pr, entry_t const *e); \
00108 HTABLE_SCOPE void prefix##_insert(prefix##_t *pr, entry_t const *e); \
00109 HTABLE_SCOPE int prefix##_remove(prefix##_t *, entry_t const *e)
00110 
00123 #define HTABLE_BODIES(prefix, pr, entry_t, hfun) \
00124   HTABLE_BODIES_WITH(prefix, pr, entry_t, hfun, unsigned, hash_value_t)
00125 
00126 #define HTABLE_BODIES_WITH(prefix, pr, entry_t, hfun, size_t, hash_value_t) \
00127  \
00128 HTABLE_SCOPE \
00129 int prefix##_resize(su_home_t *home, \
00130                     prefix##_t pr[], \
00131                     size_t new_size) \
00132 { \
00133   entry_t **new_hash; \
00134   entry_t **old_hash = pr->pr##_table; \
00135   size_t old_size; \
00136   size_t i, j, i0; \
00137   unsigned again = 0; \
00138   size_t used = 0, collisions = 0; \
00139 \
00140   if (new_size == 0) \
00141     new_size = 2 * pr->pr##_size + 1; \
00142   if (new_size < HTABLE_MIN_SIZE) \
00143     new_size = HTABLE_MIN_SIZE; \
00144   if (new_size < 5 * pr->pr##_used / 4) \
00145     new_size = 5 * pr->pr##_used / 4; \
00146 \
00147   if (!(new_hash = su_zalloc(home, sizeof(*new_hash) * new_size))) \
00148     return -1; \
00149 \
00150   old_size = pr->pr##_size; \
00151 \
00152   do for (j = 0; j < old_size; j++) { \
00153     if (!old_hash[j]) \
00154       continue; \
00155 \
00156     if (again < 2 && hfun(old_hash[j]) % old_size > j) { \
00157       /* Wrapped, leave entry for second pass */ \
00158       again = 1; continue; \
00159     } \
00160 \
00161     i0 = hfun(old_hash[j]) % new_size; \
00162 \
00163     for (i = i0; new_hash[i]; i = (i + 1) % new_size, assert(i != i0)) \
00164       collisions++; \
00165 \
00166     new_hash[i] = old_hash[j], old_hash[j] = NULL; \
00167     used++; \
00168   } \
00169   while (again++ == 1); \
00170 \
00171   pr->pr##_table = new_hash, pr->pr##_size = new_size; \
00172 \
00173   assert(pr->pr##_used == used); \
00174 \
00175   su_free(home, old_hash); \
00176 \
00177   return 0; \
00178 } \
00179 \
00180 HTABLE_SCOPE \
00181 int prefix##_is_full(prefix##_t const *pr) \
00182 { \
00183   return pr->pr##_table == NULL || 3 * pr->pr##_used > 2 * pr->pr##_size; \
00184 } \
00185 \
00186 HTABLE_SCOPE \
00187 entry_t **prefix##_hash(prefix##_t const *pr, hash_value_t hv) \
00188 { \
00189   return pr->pr##_table + hv % pr->pr##_size; \
00190 } \
00191 \
00192 HTABLE_SCOPE \
00193 entry_t **prefix##_next(prefix##_t const *pr, entry_t * const *ee) \
00194 { \
00195   if (++ee < pr->pr##_table + pr->pr##_size && ee >= pr->pr##_table) \
00196     return (entry_t **)ee; \
00197   else \
00198     return pr->pr##_table; \
00199 }  \
00200 \
00201 HTABLE_SCOPE \
00202 void prefix##_append(prefix##_t *pr, entry_t const *e) \
00203 { \
00204   entry_t **ee; \
00205 \
00206   pr->pr##_used++; \
00207   for (ee = prefix##_hash(pr, hfun(e)); *ee; ee = prefix##_next(pr, ee)) \
00208    ; \
00209   *ee = (entry_t *)e; \
00210 } \
00211 \
00212 HTABLE_SCOPE \
00213 void prefix##_insert(prefix##_t *pr, entry_t const *e) \
00214 { \
00215   entry_t *e0, **ee; \
00216 \
00217   pr->pr##_used++; \
00218   /* Insert entry into hash table (before other entries with same hash) */ \
00219   for (ee = prefix##_hash(pr, hfun(e));  \
00220        (e0 = *ee); \
00221        ee = prefix##_next(pr, ee)) \
00222     *ee = (entry_t *)e, e = e0; \
00223   *ee = (entry_t *)e; \
00224 } \
00225 \
00226 HTABLE_SCOPE \
00227 int prefix##_remove(prefix##_t *pr, entry_t const *e) \
00228 { \
00229   size_t i, j, k; \
00230   size_t size = pr->pr##_size; \
00231   entry_t **htable = pr->pr##_table; \
00232 \
00233   if (!e) return -1; \
00234 \
00235   /* Search for entry */ \
00236   for (i = hfun(e) % size; htable[i]; i = (i + 1) % size) \
00237     if (e == htable[i]) \
00238       break; \
00239 \
00240   /* Entry is not in table? */ \
00241   if (!htable[i]) return -1; \
00242 \
00243   /* Move table entries towards their primary place  */ \
00244   for (j = (i + 1) % size; htable[j]; j = (j + 1) % size) { \
00245     /* k is primary place for entry */ \
00246     k = hfun(htable[j]) % size; \
00247     if (k == j)                 /* entry is in its primary place? */ \
00248       continue; \
00249     /* primary place is between i and j - do not move this to i */ \
00250     if (j > i ? (i < k && k < j) : (i < k || k < j)) \
00251       continue; \
00252 \
00253     htable[i] = htable[j], i = j; \
00254   } \
00255 \
00256   pr->pr##_used--; \
00257 \
00258   htable[i] = NULL; \
00259 \
00260   return 0; \
00261 } \
00262 extern int prefix##_dummy
00263 
00264 #endif 
 All Data Structures Files Functions Variables Typedefs Enumerator Defines

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