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 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 \
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 \
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 \
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 \
00275 for (j = (i + 1) % size; is_used(htable[j]); j = (j + 1) % size) { \
00276 \
00277 k = hfun(htable[j]) % size; \
00278 if (k == j) \
00279 continue; \
00280 \
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