su 1.12.11devel
|
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