Commit | Line | Data |
---|---|---|
bec39940 DG |
1 | /* |
2 | * Copyright (C) 2011 - David Goulet <david.goulet@polymtl.ca> | |
3 | * | |
d14d33bf AM |
4 | * This program is free software; you can redistribute it and/or modify |
5 | * it under the terms of the GNU General Public License, version 2 only, | |
6 | * as published by the Free Software Foundation. | |
bec39940 DG |
7 | * |
8 | * This program is distributed in the hope that it will be useful, but WITHOUT | |
9 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
d14d33bf | 10 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for |
bec39940 DG |
11 | * more details. |
12 | * | |
d14d33bf AM |
13 | * You should have received a copy of the GNU General Public License along |
14 | * with this program; if not, write to the Free Software Foundation, Inc., | |
15 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. | |
bec39940 DG |
16 | */ |
17 | ||
18 | #define _GNU_SOURCE | |
19 | #include <assert.h> | |
20 | #include <string.h> | |
21 | #include <urcu.h> | |
22 | #include <urcu/compiler.h> | |
23 | ||
990570ed DG |
24 | #include <common/common.h> |
25 | #include <common/defaults.h> | |
bec39940 | 26 | |
10a8a223 | 27 | #include "hashtable.h" |
bec39940 DG |
28 | #include "utils.h" |
29 | ||
b6314938 | 30 | unsigned long lttng_ht_seed; |
bec39940 DG |
31 | |
32 | static unsigned long min_hash_alloc_size = 1; | |
13fe1164 | 33 | static unsigned long max_hash_buckets_size = 0; |
bec39940 DG |
34 | |
35 | /* | |
36 | * Match function for string node. | |
37 | */ | |
38 | static int match_str(struct cds_lfht_node *node, const void *key) | |
39 | { | |
40 | struct lttng_ht_node_str *match_node = | |
41 | caa_container_of(node, struct lttng_ht_node_str, node); | |
42 | ||
43 | return hash_match_key_str(match_node->key, (void *) key); | |
44 | } | |
45 | ||
46 | /* | |
47 | * Match function for ulong node. | |
48 | */ | |
49 | static int match_ulong(struct cds_lfht_node *node, const void *key) | |
50 | { | |
51 | struct lttng_ht_node_ulong *match_node = | |
52 | caa_container_of(node, struct lttng_ht_node_ulong, node); | |
53 | ||
54 | return hash_match_key_ulong((void *) match_node->key, (void *) key); | |
55 | } | |
56 | ||
d88aee68 DG |
57 | /* |
58 | * Match function for u64 node. | |
59 | */ | |
60 | static int match_u64(struct cds_lfht_node *node, const void *key) | |
61 | { | |
62 | struct lttng_ht_node_u64 *match_node = | |
63 | caa_container_of(node, struct lttng_ht_node_u64, node); | |
64 | ||
65 | return hash_match_key_u64(&match_node->key, (void *) key); | |
66 | } | |
67 | ||
bec39940 DG |
68 | /* |
69 | * Return an allocated lttng hashtable. | |
70 | */ | |
71 | struct lttng_ht *lttng_ht_new(unsigned long size, int type) | |
72 | { | |
73 | struct lttng_ht *ht; | |
74 | ||
75 | /* Test size */ | |
dc78d159 MD |
76 | if (!size) |
77 | size = DEFAULT_HT_SIZE; | |
bec39940 DG |
78 | |
79 | ht = zmalloc(sizeof(*ht)); | |
80 | if (ht == NULL) { | |
81 | PERROR("zmalloc lttng_ht"); | |
82 | goto error; | |
83 | } | |
84 | ||
85 | ht->ht = cds_lfht_new(size, min_hash_alloc_size, max_hash_buckets_size, | |
13fe1164 | 86 | CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL); |
bec39940 DG |
87 | /* |
88 | * There is already an assert in the RCU hashtable code so if the ht is | |
89 | * NULL here there is a *huge* problem. | |
90 | */ | |
91 | assert(ht->ht); | |
92 | ||
93 | switch (type) { | |
94 | case LTTNG_HT_TYPE_STRING: | |
95 | ht->match_fct = match_str; | |
96 | ht->hash_fct = hash_key_str; | |
97 | break; | |
98 | case LTTNG_HT_TYPE_ULONG: | |
99 | ht->match_fct = match_ulong; | |
100 | ht->hash_fct = hash_key_ulong; | |
101 | break; | |
d88aee68 DG |
102 | case LTTNG_HT_TYPE_U64: |
103 | ht->match_fct = match_u64; | |
104 | ht->hash_fct = hash_key_u64; | |
105 | break; | |
bec39940 DG |
106 | default: |
107 | ERR("Unknown lttng hashtable type %d", type); | |
108 | goto error; | |
109 | } | |
110 | ||
111 | DBG3("Created hashtable size %lu at %p of type %d", size, ht->ht, type); | |
112 | ||
113 | return ht; | |
114 | ||
115 | error: | |
116 | return NULL; | |
117 | } | |
118 | ||
119 | /* | |
120 | * Free a lttng hashtable. | |
121 | */ | |
122 | void lttng_ht_destroy(struct lttng_ht *ht) | |
123 | { | |
124 | int ret; | |
125 | ||
126 | ret = cds_lfht_destroy(ht->ht, NULL); | |
127 | assert(!ret); | |
cf5280ea | 128 | free(ht); |
bec39940 DG |
129 | } |
130 | ||
131 | /* | |
132 | * Init lttng ht node string. | |
133 | */ | |
134 | void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key) | |
135 | { | |
136 | assert(node); | |
137 | ||
138 | node->key = key; | |
139 | cds_lfht_node_init(&node->node); | |
140 | } | |
141 | ||
142 | /* | |
143 | * Init lttng ht node unsigned long. | |
144 | */ | |
145 | void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node, | |
146 | unsigned long key) | |
147 | { | |
148 | assert(node); | |
149 | ||
150 | node->key = key; | |
151 | cds_lfht_node_init(&node->node); | |
152 | } | |
153 | ||
d88aee68 DG |
154 | /* |
155 | * Init lttng ht node uint64_t. | |
156 | */ | |
157 | void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node, | |
158 | uint64_t key) | |
159 | { | |
160 | assert(node); | |
161 | ||
162 | node->key = key; | |
163 | cds_lfht_node_init(&node->node); | |
164 | } | |
165 | ||
bec39940 DG |
166 | /* |
167 | * Free lttng ht node string. | |
168 | */ | |
169 | void lttng_ht_node_free_str(struct lttng_ht_node_str *node) | |
170 | { | |
171 | assert(node); | |
172 | free(node); | |
173 | } | |
174 | ||
175 | /* | |
176 | * Free lttng ht node unsigned long. | |
177 | */ | |
178 | void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node) | |
179 | { | |
180 | assert(node); | |
181 | free(node); | |
182 | } | |
183 | ||
d88aee68 DG |
184 | /* |
185 | * Free lttng ht node uint64_t. | |
186 | */ | |
187 | void lttng_ht_node_free_u64(struct lttng_ht_node_ulong *node) | |
188 | { | |
189 | assert(node); | |
190 | free(node); | |
191 | } | |
192 | ||
bec39940 DG |
193 | /* |
194 | * Lookup function in hashtable. | |
195 | */ | |
196 | void lttng_ht_lookup(struct lttng_ht *ht, void *key, | |
197 | struct lttng_ht_iter *iter) | |
198 | { | |
199 | assert(ht); | |
200 | assert(ht->ht); | |
bec39940 | 201 | |
b6314938 | 202 | cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed), |
bec39940 DG |
203 | ht->match_fct, key, &iter->iter); |
204 | } | |
205 | ||
206 | /* | |
207 | * Add unique string node to hashtable. | |
208 | */ | |
209 | void lttng_ht_add_unique_str(struct lttng_ht *ht, | |
210 | struct lttng_ht_node_str *node) | |
211 | { | |
212 | struct cds_lfht_node *node_ptr; | |
213 | assert(ht); | |
214 | assert(ht->ht); | |
215 | assert(node); | |
216 | ||
b6314938 | 217 | node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed), |
bec39940 DG |
218 | ht->match_fct, node->key, &node->node); |
219 | assert(node_ptr == &node->node); | |
220 | } | |
221 | ||
aefea3b7 DG |
222 | /* |
223 | * Add unsigned long node to hashtable. | |
224 | */ | |
225 | void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node) | |
226 | { | |
227 | assert(ht); | |
228 | assert(ht->ht); | |
229 | assert(node); | |
230 | ||
b6314938 | 231 | cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed), |
aefea3b7 DG |
232 | &node->node); |
233 | } | |
234 | ||
d88aee68 DG |
235 | /* |
236 | * Add uint64_t node to hashtable. | |
237 | ||
238 | */ | |
239 | void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node) | |
240 | { | |
241 | assert(ht); | |
242 | assert(ht->ht); | |
243 | assert(node); | |
244 | ||
245 | cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed), | |
246 | &node->node); | |
247 | } | |
248 | ||
bec39940 DG |
249 | /* |
250 | * Add unique unsigned long node to hashtable. | |
251 | */ | |
252 | void lttng_ht_add_unique_ulong(struct lttng_ht *ht, | |
253 | struct lttng_ht_node_ulong *node) | |
254 | { | |
255 | struct cds_lfht_node *node_ptr; | |
256 | assert(ht); | |
257 | assert(ht->ht); | |
258 | assert(node); | |
259 | ||
260 | node_ptr = cds_lfht_add_unique(ht->ht, | |
b6314938 | 261 | ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct, |
bec39940 DG |
262 | (void *) node->key, &node->node); |
263 | assert(node_ptr == &node->node); | |
264 | } | |
265 | ||
d88aee68 DG |
266 | /* |
267 | * Add unique uint64_t node to hashtable. | |
268 | */ | |
269 | void lttng_ht_add_unique_u64(struct lttng_ht *ht, | |
270 | struct lttng_ht_node_u64 *node) | |
271 | { | |
272 | struct cds_lfht_node *node_ptr; | |
273 | assert(ht); | |
274 | assert(ht->ht); | |
275 | assert(node); | |
276 | ||
277 | node_ptr = cds_lfht_add_unique(ht->ht, | |
278 | ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct, | |
279 | &node->key, &node->node); | |
280 | assert(node_ptr == &node->node); | |
281 | } | |
282 | ||
702b1ea4 MD |
283 | /* |
284 | * Add replace unsigned long node to hashtable. | |
285 | */ | |
286 | struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht, | |
287 | struct lttng_ht_node_ulong *node) | |
288 | { | |
289 | struct cds_lfht_node *node_ptr; | |
290 | assert(ht); | |
291 | assert(ht->ht); | |
292 | assert(node); | |
293 | ||
294 | node_ptr = cds_lfht_add_replace(ht->ht, | |
b6314938 | 295 | ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct, |
702b1ea4 MD |
296 | (void *) node->key, &node->node); |
297 | if (!node_ptr) { | |
298 | return NULL; | |
299 | } else { | |
300 | return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node); | |
301 | } | |
302 | assert(node_ptr == &node->node); | |
303 | } | |
304 | ||
d88aee68 DG |
305 | /* |
306 | * Add replace unsigned long node to hashtable. | |
307 | */ | |
308 | struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht, | |
309 | struct lttng_ht_node_u64 *node) | |
310 | { | |
311 | struct cds_lfht_node *node_ptr; | |
312 | assert(ht); | |
313 | assert(ht->ht); | |
314 | assert(node); | |
315 | ||
316 | node_ptr = cds_lfht_add_replace(ht->ht, | |
317 | ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct, | |
318 | &node->key, &node->node); | |
319 | if (!node_ptr) { | |
320 | return NULL; | |
321 | } else { | |
322 | return caa_container_of(node_ptr, struct lttng_ht_node_u64, node); | |
323 | } | |
324 | assert(node_ptr == &node->node); | |
325 | } | |
326 | ||
bec39940 DG |
327 | /* |
328 | * Delete node from hashtable. | |
329 | */ | |
330 | int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter) | |
331 | { | |
332 | assert(ht); | |
333 | assert(ht->ht); | |
334 | assert(iter); | |
335 | ||
336 | return cds_lfht_del(ht->ht, iter->iter.node); | |
337 | } | |
338 | ||
339 | /* | |
340 | * Get first node in the hashtable. | |
341 | */ | |
342 | void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter) | |
343 | { | |
344 | assert(ht); | |
345 | assert(ht->ht); | |
346 | assert(iter); | |
347 | ||
348 | cds_lfht_first(ht->ht, &iter->iter); | |
349 | } | |
350 | ||
351 | /* | |
352 | * Get next node in the hashtable. | |
353 | */ | |
354 | void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter) | |
355 | { | |
356 | assert(ht); | |
357 | assert(ht->ht); | |
358 | assert(iter); | |
359 | ||
360 | cds_lfht_next(ht->ht, &iter->iter); | |
361 | } | |
362 | ||
363 | /* | |
364 | * Return the number of nodes in the hashtable. | |
365 | */ | |
366 | unsigned long lttng_ht_get_count(struct lttng_ht *ht) | |
367 | { | |
368 | long scb, sca; | |
369 | unsigned long count; | |
370 | ||
371 | assert(ht); | |
372 | assert(ht->ht); | |
373 | ||
374 | cds_lfht_count_nodes(ht->ht, &scb, &count, &sca); | |
375 | ||
376 | return count; | |
377 | } | |
378 | ||
379 | /* | |
380 | * Return lttng ht string node from iterator. | |
381 | */ | |
382 | struct lttng_ht_node_str *lttng_ht_iter_get_node_str( | |
383 | struct lttng_ht_iter *iter) | |
384 | { | |
385 | struct cds_lfht_node *node; | |
386 | ||
387 | assert(iter); | |
388 | node = cds_lfht_iter_get_node(&iter->iter); | |
389 | if (!node) { | |
390 | return NULL; | |
391 | } | |
392 | return caa_container_of(node, struct lttng_ht_node_str, node); | |
393 | } | |
394 | ||
395 | /* | |
396 | * Return lttng ht unsigned long node from iterator. | |
397 | */ | |
398 | struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong( | |
399 | struct lttng_ht_iter *iter) | |
400 | { | |
401 | struct cds_lfht_node *node; | |
402 | ||
403 | assert(iter); | |
404 | node = cds_lfht_iter_get_node(&iter->iter); | |
405 | if (!node) { | |
406 | return NULL; | |
407 | } | |
408 | return caa_container_of(node, struct lttng_ht_node_ulong, node); | |
409 | } | |
b6314938 | 410 | |
d88aee68 DG |
411 | /* |
412 | * Return lttng ht unsigned long node from iterator. | |
413 | */ | |
414 | struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64( | |
415 | struct lttng_ht_iter *iter) | |
416 | { | |
417 | struct cds_lfht_node *node; | |
418 | ||
419 | assert(iter); | |
420 | node = cds_lfht_iter_get_node(&iter->iter); | |
421 | if (!node) { | |
422 | return NULL; | |
423 | } | |
424 | return caa_container_of(node, struct lttng_ht_node_u64, node); | |
425 | } | |
426 | ||
b6314938 DG |
427 | /* |
428 | * lib constructor | |
429 | */ | |
d88aee68 | 430 | static void __attribute__((constructor)) _init(void) |
b6314938 DG |
431 | { |
432 | /* Init hash table seed */ | |
433 | lttng_ht_seed = (unsigned long) time(NULL); | |
434 | } |