Rename C++ header files to .hpp
[lttng-tools.git] / src / common / hashtable / hashtable.cpp
CommitLineData
bec39940 1/*
21cf9b6b 2 * Copyright (C) 2011 EfficiOS Inc.
bec39940 3 *
ab5be9fa 4 * SPDX-License-Identifier: GPL-2.0-only
bec39940 5 *
bec39940
DG
6 */
7
6c1c0768 8#define _LGPL_SOURCE
bec39940
DG
9#include <string.h>
10#include <urcu.h>
11#include <urcu/compiler.h>
12
c9e313bc
SM
13#include <common/common.hpp>
14#include <common/defaults.hpp>
bec39940 15
c9e313bc
SM
16#include "hashtable.hpp"
17#include "utils.hpp"
bec39940 18
6dcd74cf
JG
19/* seed_lock protects both seed_init and lttng_ht_seed. */
20static pthread_mutex_t seed_lock = PTHREAD_MUTEX_INITIALIZER;
21static bool seed_init;
bec39940
DG
22
23static unsigned long min_hash_alloc_size = 1;
13fe1164 24static unsigned long max_hash_buckets_size = 0;
bec39940 25
42ce408e
MD
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
bec39940
DG
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
d88aee68
DG
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
3c4599b9
JD
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
e2530e2b
FD
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
bec39940
DG
95/*
96 * Return an allocated lttng hashtable.
97 */
6dca8ba7 98struct lttng_ht *lttng_ht_new(unsigned long size, lttng_ht_type type)
bec39940
DG
99{
100 struct lttng_ht *ht;
101
102 /* Test size */
dc78d159
MD
103 if (!size)
104 size = DEFAULT_HT_SIZE;
bec39940 105
6dcd74cf
JG
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
6dca8ba7 113 ht = (lttng_ht *) zmalloc(sizeof(*ht));
bec39940
DG
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,
13fe1164 120 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
bec39940
DG
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 */
a0377dfe 125 LTTNG_ASSERT(ht->ht);
bec39940
DG
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;
d88aee68
DG
136 case LTTNG_HT_TYPE_U64:
137 ht->match_fct = match_u64;
138 ht->hash_fct = hash_key_u64;
139 break;
3c4599b9
JD
140 case LTTNG_HT_TYPE_TWO_U64:
141 ht->match_fct = match_two_u64;
142 ht->hash_fct = hash_key_two_u64;
143 break;
bec39940
DG
144 default:
145 ERR("Unknown lttng hashtable type %d", type);
42305b36 146 lttng_ht_destroy(ht);
bec39940
DG
147 goto error;
148 }
149
e2530e2b
FD
150 DBG3("Created hashtable size %lu at %p of type %s", size, ht->ht,
151 lttng_ht_type_str(type));
bec39940
DG
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);
a0377dfe 167 LTTNG_ASSERT(!ret);
cf5280ea 168 free(ht);
bec39940
DG
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{
a0377dfe 176 LTTNG_ASSERT(node);
bec39940
DG
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{
a0377dfe 188 LTTNG_ASSERT(node);
bec39940
DG
189
190 node->key = key;
191 cds_lfht_node_init(&node->node);
192}
193
d88aee68
DG
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{
a0377dfe 200 LTTNG_ASSERT(node);
d88aee68
DG
201
202 node->key = key;
203 cds_lfht_node_init(&node->node);
204}
205
3c4599b9
JD
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{
a0377dfe 212 LTTNG_ASSERT(node);
3c4599b9
JD
213
214 node->key.key1 = key1;
215 node->key.key2 = key2;
216 cds_lfht_node_init(&node->node);
217}
218
bec39940
DG
219/*
220 * Free lttng ht node string.
221 */
222void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
223{
a0377dfe 224 LTTNG_ASSERT(node);
bec39940
DG
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{
a0377dfe 233 LTTNG_ASSERT(node);
bec39940
DG
234 free(node);
235}
236
d88aee68
DG
237/*
238 * Free lttng ht node uint64_t.
239 */
7972aab2 240void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
d88aee68 241{
a0377dfe 242 LTTNG_ASSERT(node);
d88aee68
DG
243 free(node);
244}
245
3c4599b9
JD
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{
a0377dfe 251 LTTNG_ASSERT(node);
3c4599b9
JD
252 free(node);
253}
254
bec39940
DG
255/*
256 * Lookup function in hashtable.
257 */
fb9a95c4 258void lttng_ht_lookup(struct lttng_ht *ht, const void *key,
bec39940
DG
259 struct lttng_ht_iter *iter)
260{
a0377dfe
FD
261 LTTNG_ASSERT(ht);
262 LTTNG_ASSERT(ht->ht);
bec39940 263
b6314938 264 cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
bec39940
DG
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;
a0377dfe
FD
275 LTTNG_ASSERT(ht);
276 LTTNG_ASSERT(ht->ht);
277 LTTNG_ASSERT(node);
bec39940 278
42ce408e
MD
279 /* RCU read lock protects from ABA. */
280 rcu_read_lock();
b6314938 281 node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
bec39940 282 ht->match_fct, node->key, &node->node);
42ce408e 283 rcu_read_unlock();
a0377dfe 284 LTTNG_ASSERT(node_ptr == &node->node);
bec39940
DG
285}
286
efa116c6
JD
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{
a0377dfe
FD
293 LTTNG_ASSERT(ht);
294 LTTNG_ASSERT(ht->ht);
295 LTTNG_ASSERT(node);
efa116c6 296
42ce408e
MD
297 /* RCU read lock protects from ABA. */
298 rcu_read_lock();
efa116c6
JD
299 cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
300 &node->node);
42ce408e 301 rcu_read_unlock();
efa116c6
JD
302}
303
aefea3b7
DG
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{
a0377dfe
FD
309 LTTNG_ASSERT(ht);
310 LTTNG_ASSERT(ht->ht);
311 LTTNG_ASSERT(node);
aefea3b7 312
42ce408e
MD
313 /* RCU read lock protects from ABA. */
314 rcu_read_lock();
b6314938 315 cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
aefea3b7 316 &node->node);
42ce408e 317 rcu_read_unlock();
aefea3b7
DG
318}
319
d88aee68
DG
320/*
321 * Add uint64_t node to hashtable.
d88aee68
DG
322 */
323void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
324{
a0377dfe
FD
325 LTTNG_ASSERT(ht);
326 LTTNG_ASSERT(ht->ht);
327 LTTNG_ASSERT(node);
d88aee68 328
42ce408e
MD
329 /* RCU read lock protects from ABA. */
330 rcu_read_lock();
d88aee68
DG
331 cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
332 &node->node);
42ce408e 333 rcu_read_unlock();
d88aee68
DG
334}
335
bec39940
DG
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;
a0377dfe
FD
343 LTTNG_ASSERT(ht);
344 LTTNG_ASSERT(ht->ht);
345 LTTNG_ASSERT(node);
bec39940 346
42ce408e
MD
347 /* RCU read lock protects from ABA. */
348 rcu_read_lock();
bec39940 349 node_ptr = cds_lfht_add_unique(ht->ht,
b6314938 350 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
bec39940 351 (void *) node->key, &node->node);
42ce408e 352 rcu_read_unlock();
a0377dfe 353 LTTNG_ASSERT(node_ptr == &node->node);
bec39940
DG
354}
355
d88aee68
DG
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;
a0377dfe
FD
363 LTTNG_ASSERT(ht);
364 LTTNG_ASSERT(ht->ht);
365 LTTNG_ASSERT(node);
d88aee68 366
42ce408e
MD
367 /* RCU read lock protects from ABA. */
368 rcu_read_lock();
d88aee68
DG
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);
42ce408e 372 rcu_read_unlock();
a0377dfe 373 LTTNG_ASSERT(node_ptr == &node->node);
d88aee68
DG
374}
375
3c4599b9
JD
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;
a0377dfe
FD
383 LTTNG_ASSERT(ht);
384 LTTNG_ASSERT(ht->ht);
385 LTTNG_ASSERT(node);
3c4599b9 386
42ce408e
MD
387 /* RCU read lock protects from ABA. */
388 rcu_read_lock();
3c4599b9
JD
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);
42ce408e 392 rcu_read_unlock();
a0377dfe 393 LTTNG_ASSERT(node_ptr == &node->node);
3c4599b9
JD
394}
395
702b1ea4
MD
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;
a0377dfe
FD
403 LTTNG_ASSERT(ht);
404 LTTNG_ASSERT(ht->ht);
405 LTTNG_ASSERT(node);
702b1ea4 406
42ce408e
MD
407 /* RCU read lock protects from ABA. */
408 rcu_read_lock();
702b1ea4 409 node_ptr = cds_lfht_add_replace(ht->ht,
b6314938 410 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
702b1ea4 411 (void *) node->key, &node->node);
42ce408e 412 rcu_read_unlock();
702b1ea4
MD
413 if (!node_ptr) {
414 return NULL;
415 } else {
416 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
417 }
a0377dfe 418 LTTNG_ASSERT(node_ptr == &node->node);
702b1ea4
MD
419}
420
d88aee68
DG
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;
a0377dfe
FD
428 LTTNG_ASSERT(ht);
429 LTTNG_ASSERT(ht->ht);
430 LTTNG_ASSERT(node);
d88aee68 431
42ce408e
MD
432 /* RCU read lock protects from ABA. */
433 rcu_read_lock();
d88aee68
DG
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);
42ce408e 437 rcu_read_unlock();
d88aee68
DG
438 if (!node_ptr) {
439 return NULL;
440 } else {
441 return caa_container_of(node_ptr, struct lttng_ht_node_u64, node);
442 }
a0377dfe 443 LTTNG_ASSERT(node_ptr == &node->node);
d88aee68
DG
444}
445
bec39940
DG
446/*
447 * Delete node from hashtable.
448 */
449int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
450{
42ce408e
MD
451 int ret;
452
a0377dfe
FD
453 LTTNG_ASSERT(ht);
454 LTTNG_ASSERT(ht->ht);
455 LTTNG_ASSERT(iter);
bec39940 456
42ce408e
MD
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;
bec39940
DG
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{
a0377dfe
FD
469 LTTNG_ASSERT(ht);
470 LTTNG_ASSERT(ht->ht);
471 LTTNG_ASSERT(iter);
bec39940
DG
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{
a0377dfe
FD
481 LTTNG_ASSERT(ht);
482 LTTNG_ASSERT(ht->ht);
483 LTTNG_ASSERT(iter);
bec39940
DG
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
a0377dfe
FD
496 LTTNG_ASSERT(ht);
497 LTTNG_ASSERT(ht->ht);
bec39940 498
42ce408e
MD
499 /* RCU read lock protects from ABA and allows RCU traversal. */
500 rcu_read_lock();
bec39940 501 cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
42ce408e 502 rcu_read_unlock();
bec39940
DG
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
a0377dfe 515 LTTNG_ASSERT(iter);
bec39940
DG
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
a0377dfe 531 LTTNG_ASSERT(iter);
bec39940
DG
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}
b6314938 538
d88aee68
DG
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
a0377dfe 547 LTTNG_ASSERT(iter);
d88aee68
DG
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
3c4599b9
JD
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
a0377dfe 563 LTTNG_ASSERT(iter);
3c4599b9
JD
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.092403 seconds and 4 git commands to generate.