Lines Matching full:head
41 #define HT_EMPTY(head) \ argument
42 ((head)->hth_n_entries == 0)
44 /* How many elements in 'head'? */
45 #define HT_SIZE(head) \ argument
46 ((head)->hth_n_entries)
48 #define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm)) argument
49 #define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm)) argument
50 #define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm)) argument
51 #define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm)) argument
52 #define HT_START(name, head) name##_HT_START(head) argument
53 #define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm)) argument
54 #define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm)) argument
55 #define HT_CLEAR(name, head) name##_HT_CLEAR(head) argument
56 #define HT_INIT(name, head) name##_HT_INIT(head) argument
117 #define _HT_BUCKET(head, field, elm, hashfn) \ argument
118 ((head)->hth_table[_HT_ELT_HASH(elm,field,hashfn) % head->hth_table_length])
120 #define HT_FOREACH(x, name, head) \ argument
121 for ((x) = HT_START(name, head); \
123 (x) = HT_NEXT(name, head, x))
130 name##_HT_INIT(struct name *head) { \
131 head->hth_table_length = 0; \
132 head->hth_table = NULL; \
133 head->hth_n_entries = 0; \
134 head->hth_load_limit = 0; \
135 head->hth_prime_idx = -1; \
138 * 'head' to find or insert the element 'elm'. */ \
140 _##name##_HT_FIND_P(struct name *head, struct type *elm) \
143 if (!head->hth_table) \
145 p = &_HT_BUCKET(head, field, elm, hashfn); \
153 /* Return a pointer to the element in the table 'head' matching 'elm', \
156 name##_HT_FIND(const struct name *head, struct type *elm) \
159 struct name *h = (struct name *) head; \
164 /* Insert the element 'elm' into the table 'head'. Do not call this \
167 name##_HT_INSERT(struct name *head, struct type *elm) \
170 if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
171 name##_HT_GROW(head, head->hth_n_entries+1); \
172 ++head->hth_n_entries; \
174 p = &_HT_BUCKET(head, field, elm, hashfn); \
178 /* Insert the element 'elm' into the table 'head'. If there already \
182 name##_HT_REPLACE(struct name *head, struct type *elm) \
185 if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
186 name##_HT_GROW(head, head->hth_n_entries+1); \
188 p = _##name##_HT_FIND_P(head, elm); \
196 ++head->hth_n_entries; \
200 /* Remove any element matching 'elm' from the table 'head'. If such \
203 name##_HT_REMOVE(struct name *head, struct type *elm) \
207 p = _##name##_HT_FIND_P(head,elm); \
213 --head->hth_n_entries; \
216 /* Invoke the function 'fn' on every element of the table 'head', \
221 name##_HT_FOREACH_FN(struct name *head, \
227 if (!head->hth_table) \
229 for (idx=0; idx < head->hth_table_length; ++idx) { \
230 p = &head->hth_table[idx]; \
235 --head->hth_n_entries; \
243 /* Return a pointer to the first element in the table 'head', under \
247 name##_HT_START(struct name *head) \
250 while (b < head->hth_table_length) { \
251 if (head->hth_table[b]) \
252 return &head->hth_table[b]; \
257 /* Return the next element in 'head' after 'elm', under the arbitrary \
263 name##_HT_NEXT(struct name *head, struct type **elm) \
268 unsigned b = (_HT_ELT_HASH(*elm, field, hashfn) % head->hth_table_length)+1; \
269 while (b < head->hth_table_length) { \
270 if (head->hth_table[b]) \
271 return &head->hth_table[b]; \
278 name##_HT_NEXT_RMV(struct name *head, struct type **elm) \
282 --head->hth_n_entries; \
286 unsigned b = (h % head->hth_table_length)+1; \
287 while (b < head->hth_table_length) { \
288 if (head->hth_table[b]) \
289 return &head->hth_table[b]; \
309 /* Expand the internal table of 'head' until it is large enough to \
313 name##_HT_GROW(struct name *head, unsigned size) \
318 if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \
320 if (head->hth_load_limit > size) \
322 prime_idx = head->hth_prime_idx; \
331 for (b = 0; b < head->hth_table_length; ++b) { \
334 elm = head->hth_table[b]; \
343 if (head->hth_table) \
344 freefn(head->hth_table); \
345 head->hth_table = new_table; \
348 new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \
350 memset(new_table + head->hth_table_length, 0, \
351 (new_len - head->hth_table_length)*sizeof(struct type*)); \
352 for (b=0; b < head->hth_table_length; ++b) { \
365 head->hth_table = new_table; \
367 head->hth_table_length = new_len; \
368 head->hth_prime_idx = prime_idx; \
369 head->hth_load_limit = new_load_limit; \
372 /* Free all storage held by 'head'. Does not free 'head' itself, or \
375 name##_HT_CLEAR(struct name *head) \
377 if (head->hth_table) \
378 freefn(head->hth_table); \
379 head->hth_table_length = 0; \
380 name##_HT_INIT(head); \
382 /* Debugging helper: return false iff the representation of 'head' is \
385 _##name##_HT_REP_IS_BAD(const struct name *head) \
389 if (!head->hth_table_length) { \
390 if (!head->hth_table && !head->hth_n_entries && \
391 !head->hth_load_limit && head->hth_prime_idx == -1) \
396 if (!head->hth_table || head->hth_prime_idx < 0 || \
397 !head->hth_load_limit) \
399 if (head->hth_n_entries > head->hth_load_limit) \
401 if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \
403 if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \
405 for (n = i = 0; i < head->hth_table_length; ++i) { \
406 for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \
409 if ((_HT_ELT_HASH(elm, field, hashfn) % head->hth_table_length) != i) \
414 if (n != head->hth_n_entries) \
422 #define _HT_FIND_OR_INSERT(name, field, hashfn, head, eltype, elm, var, y, n) \ argument
424 struct name *_##var##_head = head; \
437 #define _HT_FOI_INSERT(field, head, elm, newent, var) \ argument
442 ++((head)->hth_n_entries); \