7 htret_t
htable_init(htable_t
*htable
, size_t size
, unsigned int factor
,
8 unsigned int (*myhashf
)(const void *key
),
9 int (*mycmpf
)(const void *arg1
, const void *arg2
),
10 void (*myprintf
)(const void *key
, const void *data
))
14 /* Allocate memory for `size' tailq headers */
15 if ((htable
->ht_table
= malloc(size
* sizeof *htable
->ht_table
)) == NULL
)
18 /* Initialize tailqs */
19 for (i
= 0; i
< size
; i
++)
20 TAILQ_INIT(&htable
->ht_table
[i
]);
22 htable
->ht_size
= size
; /* size must be a power of 2 */
24 htable
->ht_factor
= factor
;
25 htable
->ht_limit
= factor
* size
;
27 /* Setup callback functions */
28 htable
->ht_hashf
= myhashf
;
29 htable
->ht_cmpf
= mycmpf
;
30 htable
->ht_printf
= myprintf
;
35 void htable_free(htable_t
*htable
)
41 for (i
= 0; i
< htable
->ht_size
; i
++) {
42 phead
= &htable
->ht_table
[i
];
43 while (TAILQ_FIRST(phead
) != NULL
) {
44 pnode
= TAILQ_FIRST(phead
);
45 TAILQ_REMOVE(phead
, TAILQ_FIRST(phead
), hn_next
);
50 free(htable
->ht_table
);
53 htret_t
htable_free_obj(htable_t
*htable
, void *key
, htfree_t htfree
)
60 hash
= htable
->ht_hashf(key
);
62 /* Search across chain if there is an entry with the
63 key we are looking. If there is, free its contents. */
64 phead
= &htable
->ht_table
[hash
& (htable
->ht_size
- 1)];
65 TAILQ_FOREACH(pnode
, phead
, hn_next
) {
66 if (htable
->ht_cmpf(pnode
->hn_key
, key
) == 0) {
67 TAILQ_REMOVE(phead
, pnode
, hn_next
);
68 if (htfree
& HT_FREEKEY
)
70 if (htfree
& HT_FREEDATA
)
81 void htable_free_all_obj(htable_t
*htable
, htfree_t htfree
)
87 for (i
= 0; i
< htable
->ht_size
; i
++) {
88 phead
= &htable
->ht_table
[i
];
89 TAILQ_FOREACH(pnode
, phead
, hn_next
) {
90 if (htfree
& HT_FREEKEY
)
92 if (htfree
& HT_FREEDATA
)
98 htret_t
htable_grow(htable_t
*htable
)
100 hhead_t
*pcurhead
, *pnewhead
, *poldhead
;
102 unsigned int i
, newhash
, newsize
;
104 /* Allocate memory for new hash table */
105 newsize
= 2 * htable
->ht_size
;
106 if ((pnewhead
= malloc(newsize
* sizeof *pnewhead
)) == NULL
)
109 /* Initialize tailqs */
110 for (i
= 0; i
< newsize
; i
++)
111 TAILQ_INIT(&pnewhead
[i
]);
113 poldhead
= htable
->ht_table
;
115 for (i
= 0; i
< htable
->ht_size
; i
++) {
116 pcurhead
= &poldhead
[i
];
117 while ((pnode
= TAILQ_FIRST(pcurhead
)) != NULL
) {
118 newhash
= htable
->ht_hashf(pnode
->hn_key
);
119 TAILQ_REMOVE(pcurhead
, pnode
, hn_next
);
120 TAILQ_INSERT_TAIL(&pnewhead
[newhash
& (newsize
- 1)], pnode
, hn_next
);
125 free(htable
->ht_table
);
127 /* Set new table parameters */
128 htable
->ht_table
= pnewhead
;
129 htable
->ht_size
= newsize
;
130 htable
->ht_limit
= htable
->ht_factor
* newsize
;
135 htret_t
htable_insert(htable_t
*htable
, void *key
, void *data
)
142 hash
= htable
->ht_hashf(key
);
144 /* Search across chain if there is already an entry with the same key. */
145 phead
= &htable
->ht_table
[hash
& (htable
->ht_size
- 1)];
146 TAILQ_FOREACH(pnode
, phead
, hn_next
)
147 if (htable
->ht_cmpf(pnode
->hn_key
, key
) == 0)
150 /* Allocate memory for new entry */
151 if ((pnode
= malloc(sizeof *pnode
)) == NULL
)
154 pnode
->hn_data
= data
;
156 TAILQ_INSERT_TAIL(phead
, pnode
, hn_next
);
158 /* If used items exceeds limit, grow the table */
159 if (++htable
->ht_used
> htable
->ht_limit
)
165 htret_t
htable_remove(htable_t
*htable
, const void *key
)
172 hash
= htable
->ht_hashf(key
);
174 /* Search across chain if there is an entry with the
175 key we are looking. If there is, delete it. */
176 phead
= &htable
->ht_table
[hash
& (htable
->ht_size
- 1)];
177 TAILQ_FOREACH(pnode
, phead
, hn_next
) {
178 if (htable
->ht_cmpf(pnode
->hn_key
, key
) == 0) {
179 TAILQ_REMOVE(phead
, pnode
, hn_next
);
189 void *htable_search(const htable_t
*htable
, const void *key
)
191 const hhead_t
*phead
;
192 const hnode_t
*pnode
;
196 hash
= htable
->ht_hashf(key
);
198 phead
= &htable
->ht_table
[hash
& (htable
->ht_size
- 1)];
199 TAILQ_FOREACH(pnode
, phead
, hn_next
)
200 if (htable
->ht_cmpf(pnode
->hn_key
, key
) == 0)
201 return pnode
->hn_data
;
206 void htable_print(const htable_t
*htable
)
208 const hhead_t
*phead
;
209 const hnode_t
*pnode
;
212 for (i
= 0; i
< htable
->ht_size
; i
++) {
213 phead
= &htable
->ht_table
[i
];
214 TAILQ_FOREACH(pnode
, phead
, hn_next
)
215 htable
->ht_printf(pnode
->hn_key
, pnode
->hn_data
);
216 if (TAILQ_FIRST(&htable
->ht_table
[i
]) != NULL
)
221 size_t htable_get_size(const htable_t
*htable
)
223 return htable
->ht_size
;
226 unsigned int htable_get_used(const htable_t
*htable
)
228 return htable
->ht_used
;
231 void htable_traverse(const htable_t
*htable
, void (*pfunc
)(void *data
))
233 const hhead_t
*phead
;
234 const hnode_t
*pnode
;
237 for (i
= 0; i
< htable
->ht_size
; i
++) {
238 phead
= &htable
->ht_table
[i
];
239 TAILQ_FOREACH(pnode
, phead
, hn_next
)
240 pfunc(pnode
->hn_data
);
244 const hnode_t
*htable_get_next_elm(const htable_t
*htable
, unsigned int *pos
, const hnode_t
*pnode
)
246 const hhead_t
*phead
;
249 /* Is pos out of bound ? If yes, return immediately */
250 if (*pos
> (htable
->ht_size
- 1))
253 /* Find first usable element, if we were not supplied with one */
254 if (pos
== 0 || pnode
== NULL
) {
255 for (i
= *pos
; i
< htable
->ht_size
; i
++) {
257 phead
= &htable
->ht_table
[i
];
258 if (TAILQ_FIRST(phead
) != NULL
)
259 return TAILQ_FIRST(phead
);
263 /* Are we on a chain ? */
264 if (TAILQ_NEXT(pnode
, hn_next
) != NULL
) {
265 /* Don't increase pos since we are stack in an horizontal chain,
266 being still at the same 'height' which is what pos represents anyway */
267 return TAILQ_NEXT(pnode
, hn_next
);
270 for (i
= *pos
; i
< htable
->ht_size
; i
++) {
272 phead
= &htable
->ht_table
[i
];
273 if (TAILQ_FIRST(phead
) != NULL
)
274 return TAILQ_FIRST(phead
);
276 /* We have traversed all elements. Nothing left. */