Rename C++ header files to .hpp
[lttng-tools.git] / src / common / hashtable / hashtable.cpp
... / ...
CommitLineData
1/*
2 * Copyright (C) 2011 EfficiOS Inc.
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 */
7
8#define _LGPL_SOURCE
9#include <string.h>
10#include <urcu.h>
11#include <urcu/compiler.h>
12
13#include <common/common.hpp>
14#include <common/defaults.hpp>
15
16#include "hashtable.hpp"
17#include "utils.hpp"
18
19/* seed_lock protects both seed_init and lttng_ht_seed. */
20static pthread_mutex_t seed_lock = PTHREAD_MUTEX_INITIALIZER;
21static bool seed_init;
22
23static unsigned long min_hash_alloc_size = 1;
24static unsigned long max_hash_buckets_size = 0;
25
26/*
27 * Getter/lookup functions need to be called with RCU read-side lock
28 * held. However, modification functions (add, add_unique, replace, del)
29 * take the RCU lock internally, so it does not matter whether the
30 * caller hold the RCU lock or not.
31 */
32
33/*
34 * Match function for string node.
35 */
36static int match_str(struct cds_lfht_node *node, const void *key)
37{
38 struct lttng_ht_node_str *match_node =
39 caa_container_of(node, struct lttng_ht_node_str, node);
40
41 return hash_match_key_str(match_node->key, (void *) key);
42}
43
44/*
45 * Match function for ulong node.
46 */
47static int match_ulong(struct cds_lfht_node *node, const void *key)
48{
49 struct lttng_ht_node_ulong *match_node =
50 caa_container_of(node, struct lttng_ht_node_ulong, node);
51
52 return hash_match_key_ulong((void *) match_node->key, (void *) key);
53}
54
55/*
56 * Match function for u64 node.
57 */
58static int match_u64(struct cds_lfht_node *node, const void *key)
59{
60 struct lttng_ht_node_u64 *match_node =
61 caa_container_of(node, struct lttng_ht_node_u64, node);
62
63 return hash_match_key_u64(&match_node->key, (void *) key);
64}
65
66/*
67 * Match function for two uint64_t node.
68 */
69static int match_two_u64(struct cds_lfht_node *node, const void *key)
70{
71 struct lttng_ht_node_two_u64 *match_node =
72 caa_container_of(node, struct lttng_ht_node_two_u64, node);
73
74 return hash_match_key_two_u64((void *) &match_node->key, (void *) key);
75}
76
77static inline
78const char *lttng_ht_type_str(enum lttng_ht_type type)
79{
80 switch (type) {
81 case LTTNG_HT_TYPE_STRING:
82 return "STRING";
83 case LTTNG_HT_TYPE_ULONG:
84 return "ULONG";
85 case LTTNG_HT_TYPE_U64:
86 return "U64";
87 case LTTNG_HT_TYPE_TWO_U64:
88 return "TWO_U64";
89 default:
90 ERR("Unknown lttng hashtable type %d", type);
91 abort();
92 }
93}
94
95/*
96 * Return an allocated lttng hashtable.
97 */
98struct lttng_ht *lttng_ht_new(unsigned long size, lttng_ht_type type)
99{
100 struct lttng_ht *ht;
101
102 /* Test size */
103 if (!size)
104 size = DEFAULT_HT_SIZE;
105
106 pthread_mutex_lock(&seed_lock);
107 if (!seed_init) {
108 lttng_ht_seed = (unsigned long) time(NULL);
109 seed_init = true;
110 }
111 pthread_mutex_unlock(&seed_lock);
112
113 ht = (lttng_ht *) zmalloc(sizeof(*ht));
114 if (ht == NULL) {
115 PERROR("zmalloc lttng_ht");
116 goto error;
117 }
118
119 ht->ht = cds_lfht_new(size, min_hash_alloc_size, max_hash_buckets_size,
120 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
121 /*
122 * There is already an assert in the RCU hashtable code so if the ht is
123 * NULL here there is a *huge* problem.
124 */
125 LTTNG_ASSERT(ht->ht);
126
127 switch (type) {
128 case LTTNG_HT_TYPE_STRING:
129 ht->match_fct = match_str;
130 ht->hash_fct = hash_key_str;
131 break;
132 case LTTNG_HT_TYPE_ULONG:
133 ht->match_fct = match_ulong;
134 ht->hash_fct = hash_key_ulong;
135 break;
136 case LTTNG_HT_TYPE_U64:
137 ht->match_fct = match_u64;
138 ht->hash_fct = hash_key_u64;
139 break;
140 case LTTNG_HT_TYPE_TWO_U64:
141 ht->match_fct = match_two_u64;
142 ht->hash_fct = hash_key_two_u64;
143 break;
144 default:
145 ERR("Unknown lttng hashtable type %d", type);
146 lttng_ht_destroy(ht);
147 goto error;
148 }
149
150 DBG3("Created hashtable size %lu at %p of type %s", size, ht->ht,
151 lttng_ht_type_str(type));
152
153 return ht;
154
155error:
156 return NULL;
157}
158
159/*
160 * Free a lttng hashtable.
161 */
162void lttng_ht_destroy(struct lttng_ht *ht)
163{
164 int ret;
165
166 ret = cds_lfht_destroy(ht->ht, NULL);
167 LTTNG_ASSERT(!ret);
168 free(ht);
169}
170
171/*
172 * Init lttng ht node string.
173 */
174void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
175{
176 LTTNG_ASSERT(node);
177
178 node->key = key;
179 cds_lfht_node_init(&node->node);
180}
181
182/*
183 * Init lttng ht node unsigned long.
184 */
185void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
186 unsigned long key)
187{
188 LTTNG_ASSERT(node);
189
190 node->key = key;
191 cds_lfht_node_init(&node->node);
192}
193
194/*
195 * Init lttng ht node uint64_t.
196 */
197void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node,
198 uint64_t key)
199{
200 LTTNG_ASSERT(node);
201
202 node->key = key;
203 cds_lfht_node_init(&node->node);
204}
205
206/*
207 * Init lttng ht node with two uint64_t.
208 */
209void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node,
210 uint64_t key1, uint64_t key2)
211{
212 LTTNG_ASSERT(node);
213
214 node->key.key1 = key1;
215 node->key.key2 = key2;
216 cds_lfht_node_init(&node->node);
217}
218
219/*
220 * Free lttng ht node string.
221 */
222void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
223{
224 LTTNG_ASSERT(node);
225 free(node);
226}
227
228/*
229 * Free lttng ht node unsigned long.
230 */
231void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
232{
233 LTTNG_ASSERT(node);
234 free(node);
235}
236
237/*
238 * Free lttng ht node uint64_t.
239 */
240void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
241{
242 LTTNG_ASSERT(node);
243 free(node);
244}
245
246/*
247 * Free lttng ht node two uint64_t.
248 */
249void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
250{
251 LTTNG_ASSERT(node);
252 free(node);
253}
254
255/*
256 * Lookup function in hashtable.
257 */
258void lttng_ht_lookup(struct lttng_ht *ht, const void *key,
259 struct lttng_ht_iter *iter)
260{
261 LTTNG_ASSERT(ht);
262 LTTNG_ASSERT(ht->ht);
263
264 cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
265 ht->match_fct, key, &iter->iter);
266}
267
268/*
269 * Add unique string node to hashtable.
270 */
271void lttng_ht_add_unique_str(struct lttng_ht *ht,
272 struct lttng_ht_node_str *node)
273{
274 struct cds_lfht_node *node_ptr;
275 LTTNG_ASSERT(ht);
276 LTTNG_ASSERT(ht->ht);
277 LTTNG_ASSERT(node);
278
279 /* RCU read lock protects from ABA. */
280 rcu_read_lock();
281 node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
282 ht->match_fct, node->key, &node->node);
283 rcu_read_unlock();
284 LTTNG_ASSERT(node_ptr == &node->node);
285}
286
287/*
288 * Add string node to hashtable.
289 */
290void lttng_ht_add_str(struct lttng_ht *ht,
291 struct lttng_ht_node_str *node)
292{
293 LTTNG_ASSERT(ht);
294 LTTNG_ASSERT(ht->ht);
295 LTTNG_ASSERT(node);
296
297 /* RCU read lock protects from ABA. */
298 rcu_read_lock();
299 cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
300 &node->node);
301 rcu_read_unlock();
302}
303
304/*
305 * Add unsigned long node to hashtable.
306 */
307void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
308{
309 LTTNG_ASSERT(ht);
310 LTTNG_ASSERT(ht->ht);
311 LTTNG_ASSERT(node);
312
313 /* RCU read lock protects from ABA. */
314 rcu_read_lock();
315 cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
316 &node->node);
317 rcu_read_unlock();
318}
319
320/*
321 * Add uint64_t node to hashtable.
322 */
323void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
324{
325 LTTNG_ASSERT(ht);
326 LTTNG_ASSERT(ht->ht);
327 LTTNG_ASSERT(node);
328
329 /* RCU read lock protects from ABA. */
330 rcu_read_lock();
331 cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
332 &node->node);
333 rcu_read_unlock();
334}
335
336/*
337 * Add unique unsigned long node to hashtable.
338 */
339void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
340 struct lttng_ht_node_ulong *node)
341{
342 struct cds_lfht_node *node_ptr;
343 LTTNG_ASSERT(ht);
344 LTTNG_ASSERT(ht->ht);
345 LTTNG_ASSERT(node);
346
347 /* RCU read lock protects from ABA. */
348 rcu_read_lock();
349 node_ptr = cds_lfht_add_unique(ht->ht,
350 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
351 (void *) node->key, &node->node);
352 rcu_read_unlock();
353 LTTNG_ASSERT(node_ptr == &node->node);
354}
355
356/*
357 * Add unique uint64_t node to hashtable.
358 */
359void lttng_ht_add_unique_u64(struct lttng_ht *ht,
360 struct lttng_ht_node_u64 *node)
361{
362 struct cds_lfht_node *node_ptr;
363 LTTNG_ASSERT(ht);
364 LTTNG_ASSERT(ht->ht);
365 LTTNG_ASSERT(node);
366
367 /* RCU read lock protects from ABA. */
368 rcu_read_lock();
369 node_ptr = cds_lfht_add_unique(ht->ht,
370 ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
371 &node->key, &node->node);
372 rcu_read_unlock();
373 LTTNG_ASSERT(node_ptr == &node->node);
374}
375
376/*
377 * Add unique two uint64_t node to hashtable.
378 */
379void lttng_ht_add_unique_two_u64(struct lttng_ht *ht,
380 struct lttng_ht_node_two_u64 *node)
381{
382 struct cds_lfht_node *node_ptr;
383 LTTNG_ASSERT(ht);
384 LTTNG_ASSERT(ht->ht);
385 LTTNG_ASSERT(node);
386
387 /* RCU read lock protects from ABA. */
388 rcu_read_lock();
389 node_ptr = cds_lfht_add_unique(ht->ht,
390 ht->hash_fct((void *) &node->key, lttng_ht_seed), ht->match_fct,
391 (void *) &node->key, &node->node);
392 rcu_read_unlock();
393 LTTNG_ASSERT(node_ptr == &node->node);
394}
395
396/*
397 * Add replace unsigned long node to hashtable.
398 */
399struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
400 struct lttng_ht_node_ulong *node)
401{
402 struct cds_lfht_node *node_ptr;
403 LTTNG_ASSERT(ht);
404 LTTNG_ASSERT(ht->ht);
405 LTTNG_ASSERT(node);
406
407 /* RCU read lock protects from ABA. */
408 rcu_read_lock();
409 node_ptr = cds_lfht_add_replace(ht->ht,
410 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
411 (void *) node->key, &node->node);
412 rcu_read_unlock();
413 if (!node_ptr) {
414 return NULL;
415 } else {
416 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
417 }
418 LTTNG_ASSERT(node_ptr == &node->node);
419}
420
421/*
422 * Add replace unsigned long node to hashtable.
423 */
424struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht,
425 struct lttng_ht_node_u64 *node)
426{
427 struct cds_lfht_node *node_ptr;
428 LTTNG_ASSERT(ht);
429 LTTNG_ASSERT(ht->ht);
430 LTTNG_ASSERT(node);
431
432 /* RCU read lock protects from ABA. */
433 rcu_read_lock();
434 node_ptr = cds_lfht_add_replace(ht->ht,
435 ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
436 &node->key, &node->node);
437 rcu_read_unlock();
438 if (!node_ptr) {
439 return NULL;
440 } else {
441 return caa_container_of(node_ptr, struct lttng_ht_node_u64, node);
442 }
443 LTTNG_ASSERT(node_ptr == &node->node);
444}
445
446/*
447 * Delete node from hashtable.
448 */
449int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
450{
451 int ret;
452
453 LTTNG_ASSERT(ht);
454 LTTNG_ASSERT(ht->ht);
455 LTTNG_ASSERT(iter);
456
457 /* RCU read lock protects from ABA. */
458 rcu_read_lock();
459 ret = cds_lfht_del(ht->ht, iter->iter.node);
460 rcu_read_unlock();
461 return ret;
462}
463
464/*
465 * Get first node in the hashtable.
466 */
467void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
468{
469 LTTNG_ASSERT(ht);
470 LTTNG_ASSERT(ht->ht);
471 LTTNG_ASSERT(iter);
472
473 cds_lfht_first(ht->ht, &iter->iter);
474}
475
476/*
477 * Get next node in the hashtable.
478 */
479void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
480{
481 LTTNG_ASSERT(ht);
482 LTTNG_ASSERT(ht->ht);
483 LTTNG_ASSERT(iter);
484
485 cds_lfht_next(ht->ht, &iter->iter);
486}
487
488/*
489 * Return the number of nodes in the hashtable.
490 */
491unsigned long lttng_ht_get_count(struct lttng_ht *ht)
492{
493 long scb, sca;
494 unsigned long count;
495
496 LTTNG_ASSERT(ht);
497 LTTNG_ASSERT(ht->ht);
498
499 /* RCU read lock protects from ABA and allows RCU traversal. */
500 rcu_read_lock();
501 cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
502 rcu_read_unlock();
503
504 return count;
505}
506
507/*
508 * Return lttng ht string node from iterator.
509 */
510struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
511 struct lttng_ht_iter *iter)
512{
513 struct cds_lfht_node *node;
514
515 LTTNG_ASSERT(iter);
516 node = cds_lfht_iter_get_node(&iter->iter);
517 if (!node) {
518 return NULL;
519 }
520 return caa_container_of(node, struct lttng_ht_node_str, node);
521}
522
523/*
524 * Return lttng ht unsigned long node from iterator.
525 */
526struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
527 struct lttng_ht_iter *iter)
528{
529 struct cds_lfht_node *node;
530
531 LTTNG_ASSERT(iter);
532 node = cds_lfht_iter_get_node(&iter->iter);
533 if (!node) {
534 return NULL;
535 }
536 return caa_container_of(node, struct lttng_ht_node_ulong, node);
537}
538
539/*
540 * Return lttng ht unsigned long node from iterator.
541 */
542struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(
543 struct lttng_ht_iter *iter)
544{
545 struct cds_lfht_node *node;
546
547 LTTNG_ASSERT(iter);
548 node = cds_lfht_iter_get_node(&iter->iter);
549 if (!node) {
550 return NULL;
551 }
552 return caa_container_of(node, struct lttng_ht_node_u64, node);
553}
554
555/*
556 * Return lttng ht stream and index id node from iterator.
557 */
558struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64(
559 struct lttng_ht_iter *iter)
560{
561 struct cds_lfht_node *node;
562
563 LTTNG_ASSERT(iter);
564 node = cds_lfht_iter_get_node(&iter->iter);
565 if (!node) {
566 return NULL;
567 }
568 return caa_container_of(node, struct lttng_ht_node_two_u64, node);
569}
This page took 0.024231 seconds and 4 git commands to generate.