Lines Matching refs:head
41 #define HT_EMPTY(head) \
42 ((head)->hth_n_entries == 0)
44 /* How many elements in 'head'? */
45 #define HT_SIZE(head) \
46 ((head)->hth_n_entries)
49 #define HT_MEM_USAGE(head) \
50 (sizeof(*head) + (head)->hth_table_length * sizeof(void*))
52 #define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm))
53 #define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm))
54 #define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm))
55 #define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm))
56 #define HT_START(name, head) name##_HT_START(head)
57 #define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm))
58 #define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm))
59 #define HT_CLEAR(name, head) name##_HT_CLEAR(head)
60 #define HT_INIT(name, head) name##_HT_INIT(head)
121 #define HT_BUCKET_(head, field, elm, hashfn) \
122 ((head)->hth_table[HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length])
124 #define HT_FOREACH(x, name, head) \
125 for ((x) = HT_START(name, head); \
127 (x) = HT_NEXT(name, head, x))
134 name##_HT_INIT(struct name *head) { \
135 head->hth_table_length = 0; \
136 head->hth_table = NULL; \
137 head->hth_n_entries = 0; \
138 head->hth_load_limit = 0; \
139 head->hth_prime_idx = -1; \
142 * 'head' to find or insert the element 'elm'. */ \
144 name##_HT_FIND_P_(struct name *head, struct type *elm) \
147 if (!head->hth_table) \
149 p = &HT_BUCKET_(head, field, elm, hashfn); \
157 /* Return a pointer to the element in the table 'head' matching 'elm', \
160 name##_HT_FIND(const struct name *head, struct type *elm) \
163 struct name *h = (struct name *) head; \
168 /* Insert the element 'elm' into the table 'head'. Do not call this \
171 name##_HT_INSERT(struct name *head, struct type *elm) \
174 if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
175 name##_HT_GROW(head, head->hth_n_entries+1); \
176 ++head->hth_n_entries; \
178 p = &HT_BUCKET_(head, field, elm, hashfn); \
182 /* Insert the element 'elm' into the table 'head'. If there already \
186 name##_HT_REPLACE(struct name *head, struct type *elm) \
189 if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
190 name##_HT_GROW(head, head->hth_n_entries+1); \
192 p = name##_HT_FIND_P_(head, elm); \
200 ++head->hth_n_entries; \
204 /* Remove any element matching 'elm' from the table 'head'. If such \
207 name##_HT_REMOVE(struct name *head, struct type *elm) \
211 p = name##_HT_FIND_P_(head,elm); \
217 --head->hth_n_entries; \
220 /* Invoke the function 'fn' on every element of the table 'head', \
225 name##_HT_FOREACH_FN(struct name *head, \
231 if (!head->hth_table) \
233 for (idx=0; idx < head->hth_table_length; ++idx) { \
234 p = &head->hth_table[idx]; \
239 --head->hth_n_entries; \
247 /* Return a pointer to the first element in the table 'head', under \
251 name##_HT_START(struct name *head) \
254 while (b < head->hth_table_length) { \
255 if (head->hth_table[b]) \
256 return &head->hth_table[b]; \
261 /* Return the next element in 'head' after 'elm', under the arbitrary \
267 name##_HT_NEXT(struct name *head, struct type **elm) \
272 unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) % head->hth_table_length)+1; \
273 while (b < head->hth_table_length) { \
274 if (head->hth_table[b]) \
275 return &head->hth_table[b]; \
282 name##_HT_NEXT_RMV(struct name *head, struct type **elm) \
286 --head->hth_n_entries; \
290 unsigned b = (h % head->hth_table_length)+1; \
291 while (b < head->hth_table_length) { \
292 if (head->hth_table[b]) \
293 return &head->hth_table[b]; \
313 /* Expand the internal table of 'head' until it is large enough to \
317 name##_HT_GROW(struct name *head, unsigned size) \
322 if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \
324 if (head->hth_load_limit > size) \
326 prime_idx = head->hth_prime_idx; \
335 for (b = 0; b < head->hth_table_length; ++b) { \
338 elm = head->hth_table[b]; \
347 if (head->hth_table) \
348 freefn(head->hth_table); \
349 head->hth_table = new_table; \
352 new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \
354 memset(new_table + head->hth_table_length, 0, \
355 (new_len - head->hth_table_length)*sizeof(struct type*)); \
356 for (b=0; b < head->hth_table_length; ++b) { \
369 head->hth_table = new_table; \
371 head->hth_table_length = new_len; \
372 head->hth_prime_idx = prime_idx; \
373 head->hth_load_limit = new_load_limit; \
376 /* Free all storage held by 'head'. Does not free 'head' itself, or \
379 name##_HT_CLEAR(struct name *head) \
381 if (head->hth_table) \
382 freefn(head->hth_table); \
383 name##_HT_INIT(head); \
385 /* Debugging helper: return false iff the representation of 'head' is \
388 name##_HT_REP_IS_BAD_(const struct name *head) \
392 if (!head->hth_table_length) { \
393 if (!head->hth_table && !head->hth_n_entries && \
394 !head->hth_load_limit && head->hth_prime_idx == -1) \
399 if (!head->hth_table || head->hth_prime_idx < 0 || \
400 !head->hth_load_limit) \
402 if (head->hth_n_entries > head->hth_load_limit) \
404 if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \
406 if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \
408 for (n = i = 0; i < head->hth_table_length; ++i) { \
409 for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \
412 if ((HT_ELT_HASH_(elm, field, hashfn) % head->hth_table_length) != i) \
417 if (n != head->hth_n_entries) \
425 #define HT_FIND_OR_INSERT_(name, field, hashfn, head, eltype, elm, var, y, n) \
427 struct name *var##_head_ = head; \
440 #define HT_FOI_INSERT_(field, head, elm, newent, var) \
445 ++((head)->hth_n_entries); \