00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
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 \
00145 if (!(new_hash = su_zalloc(home, sizeof(*new_hash) * new_size))) \
00146 return -1; \
00147 \
00148 old_size = pr->pr##_size; \
00149 \
00150 do for (j = 0; j < old_size; j++) { \
00151 if (!old_hash[j]) \
00152 continue; \
00153 \
00154 if (again < 2 && hfun(old_hash[j]) % old_size > j) { \
00155 \
00156 again = 1; continue; \
00157 } \
00158 \
00159 i0 = hfun(old_hash[j]) % new_size; \
00160 \
00161 for (i = i0; new_hash[i]; i = (i + 1) % new_size, assert(i != i0)) \
00162 collisions++; \
00163 \
00164 new_hash[i] = old_hash[j], old_hash[j] = NULL; \
00165 used++; \
00166 } \
00167 while (again++ == 1); \
00168 \
00169 pr->pr##_table = new_hash, pr->pr##_size = new_size; \
00170 \
00171 assert(pr->pr##_used == used); \
00172 \
00173 return 0; \
00174 } \
00175 \
00176 HTABLE_SCOPE \
00177 int prefix##_is_full(prefix##_t const *pr) \
00178 { \
00179 return pr->pr##_table == NULL || 3 * pr->pr##_used > 2 * pr->pr##_size; \
00180 } \
00181 \
00182 HTABLE_SCOPE \
00183 entry_t **prefix##_hash(prefix##_t const *pr, hash_value_t hv) \
00184 { \
00185 return pr->pr##_table + hv % pr->pr##_size; \
00186 } \
00187 \
00188 HTABLE_SCOPE \
00189 entry_t **prefix##_next(prefix##_t const *pr, entry_t * const *ee) \
00190 { \
00191 if (++ee < pr->pr##_table + pr->pr##_size && ee >= pr->pr##_table) \
00192 return (entry_t **)ee; \
00193 else \
00194 return pr->pr##_table; \
00195 } \
00196 \
00197 HTABLE_SCOPE \
00198 void prefix##_append(prefix##_t *pr, entry_t const *e) \
00199 { \
00200 entry_t **ee; \
00201 \
00202 pr->pr##_used++; \
00203 for (ee = prefix##_hash(pr, hfun(e)); *ee; ee = prefix##_next(pr, ee)) \
00204 ; \
00205 *ee = (entry_t *)e; \
00206 } \
00207 \
00208 HTABLE_SCOPE \
00209 void prefix##_insert(prefix##_t *pr, entry_t const *e) \
00210 { \
00211 entry_t *e0, **ee; \
00212 \
00213 pr->pr##_used++; \
00214 \
00215 for (ee = prefix##_hash(pr, hfun(e)); \
00216 (e0 = *ee); \
00217 ee = prefix##_next(pr, ee)) \
00218 *ee = (entry_t *)e, e = e0; \
00219 *ee = (entry_t *)e; \
00220 } \
00221 \
00222 HTABLE_SCOPE \
00223 int prefix##_remove(prefix##_t *pr, entry_t const *e) \
00224 { \
00225 size_t i, j, k; \
00226 size_t size = pr->pr##_size; \
00227 entry_t **htable = pr->pr##_table; \
00228 \
00229 if (!e) return -1; \
00230 \
00231 \
00232 for (i = hfun(e) % size; htable[i]; i = (i + 1) % size) \
00233 if (e == htable[i]) \
00234 break; \
00235 \
00236 \
00237 if (!htable[i]) return -1; \
00238 \
00239 \
00240 for (j = (i + 1) % size; htable[j]; j = (j + 1) % size) { \
00241 \
00242 k = hfun(htable[j]) % size; \
00243 if (k == j) \
00244 continue; \
00245 \
00246 if (j > i ? (i < k && k < j) : (i < k || k < j)) \
00247 continue; \
00248 \
00249 htable[i] = htable[j], i = j; \
00250 } \
00251 \
00252 pr->pr##_used--; \
00253 \
00254 htable[i] = NULL; \
00255 \
00256 return 0; \
00257 } \
00258 extern int prefix##_dummy
00259
00260 #endif