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