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
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 su_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 \
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 \
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 \
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 if (!is_used(htable[i])) return -1; \
00244 \
00245 \
00246 for (j = (i + 1) % size; is_used(htable[j]); j = (j + 1) % size) { \
00247 \
00248 k = hfun(htable[j]) % size; \
00249 if (k == j) \
00250 continue; \
00251 \
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