Fix: hide internal libcommon time utilities
[lttng-tools.git] / src / common / hashtable / hashtable.c
1 /*
2 * Copyright (C) 2011 - David Goulet <david.goulet@polymtl.ca>
3 *
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.
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
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
11 * more details.
12 *
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.
16 */
17
18 #define _LGPL_SOURCE
19 #include <assert.h>
20 #include <string.h>
21 #include <urcu.h>
22 #include <urcu/compiler.h>
23
24 #include <common/common.h>
25 #include <common/defaults.h>
26
27 #include "hashtable.h"
28 #include "utils.h"
29
30 /* seed_lock protects both seed_init and lttng_ht_seed. */
31 static pthread_mutex_t seed_lock = PTHREAD_MUTEX_INITIALIZER;
32 static bool seed_init;
33 unsigned long lttng_ht_seed;
34
35 static unsigned long min_hash_alloc_size = 1;
36 static unsigned long max_hash_buckets_size = 0;
37
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
45 /*
46 * Match function for string node.
47 */
48 static 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 */
59 static 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
67 /*
68 * Match function for u64 node.
69 */
70 static 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
78 /*
79 * Match function for two uint64_t node.
80 */
81 static 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
89 /*
90 * Return an allocated lttng hashtable.
91 */
92 LTTNG_HIDDEN
93 struct lttng_ht *lttng_ht_new(unsigned long size, int type)
94 {
95 struct lttng_ht *ht;
96
97 /* Test size */
98 if (!size)
99 size = DEFAULT_HT_SIZE;
100
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
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,
115 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
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;
131 case LTTNG_HT_TYPE_U64:
132 ht->match_fct = match_u64;
133 ht->hash_fct = hash_key_u64;
134 break;
135 case LTTNG_HT_TYPE_TWO_U64:
136 ht->match_fct = match_two_u64;
137 ht->hash_fct = hash_key_two_u64;
138 break;
139 default:
140 ERR("Unknown lttng hashtable type %d", type);
141 lttng_ht_destroy(ht);
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
149 error:
150 return NULL;
151 }
152
153 /*
154 * Free a lttng hashtable.
155 */
156 LTTNG_HIDDEN
157 void lttng_ht_destroy(struct lttng_ht *ht)
158 {
159 int ret;
160
161 ret = cds_lfht_destroy(ht->ht, NULL);
162 assert(!ret);
163 free(ht);
164 }
165
166 /*
167 * Init lttng ht node string.
168 */
169 LTTNG_HIDDEN
170 void 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 */
181 LTTNG_HIDDEN
182 void 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
191 /*
192 * Init lttng ht node uint64_t.
193 */
194 LTTNG_HIDDEN
195 void 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
204 /*
205 * Init lttng ht node with two uint64_t.
206 */
207 LTTNG_HIDDEN
208 void 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
218 /*
219 * Free lttng ht node string.
220 */
221 LTTNG_HIDDEN
222 void 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 */
231 LTTNG_HIDDEN
232 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
233 {
234 assert(node);
235 free(node);
236 }
237
238 /*
239 * Free lttng ht node uint64_t.
240 */
241 LTTNG_HIDDEN
242 void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
243 {
244 assert(node);
245 free(node);
246 }
247
248 /*
249 * Free lttng ht node two uint64_t.
250 */
251 LTTNG_HIDDEN
252 void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
253 {
254 assert(node);
255 free(node);
256 }
257
258 /*
259 * Lookup function in hashtable.
260 */
261 LTTNG_HIDDEN
262 void lttng_ht_lookup(struct lttng_ht *ht, void *key,
263 struct lttng_ht_iter *iter)
264 {
265 assert(ht);
266 assert(ht->ht);
267
268 cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
269 ht->match_fct, key, &iter->iter);
270 }
271
272 /*
273 * Add unique string node to hashtable.
274 */
275 LTTNG_HIDDEN
276 void 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
284 /* RCU read lock protects from ABA. */
285 rcu_read_lock();
286 node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
287 ht->match_fct, node->key, &node->node);
288 rcu_read_unlock();
289 assert(node_ptr == &node->node);
290 }
291
292 /*
293 * Add string node to hashtable.
294 */
295 LTTNG_HIDDEN
296 void 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
303 /* RCU read lock protects from ABA. */
304 rcu_read_lock();
305 cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
306 &node->node);
307 rcu_read_unlock();
308 }
309
310 /*
311 * Add unsigned long node to hashtable.
312 */
313 LTTNG_HIDDEN
314 void 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
320 /* RCU read lock protects from ABA. */
321 rcu_read_lock();
322 cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
323 &node->node);
324 rcu_read_unlock();
325 }
326
327 /*
328 * Add uint64_t node to hashtable.
329 */
330 LTTNG_HIDDEN
331 void 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
337 /* RCU read lock protects from ABA. */
338 rcu_read_lock();
339 cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
340 &node->node);
341 rcu_read_unlock();
342 }
343
344 /*
345 * Add unique unsigned long node to hashtable.
346 */
347 LTTNG_HIDDEN
348 void 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
356 /* RCU read lock protects from ABA. */
357 rcu_read_lock();
358 node_ptr = cds_lfht_add_unique(ht->ht,
359 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
360 (void *) node->key, &node->node);
361 rcu_read_unlock();
362 assert(node_ptr == &node->node);
363 }
364
365 /*
366 * Add unique uint64_t node to hashtable.
367 */
368 LTTNG_HIDDEN
369 void 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
377 /* RCU read lock protects from ABA. */
378 rcu_read_lock();
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);
382 rcu_read_unlock();
383 assert(node_ptr == &node->node);
384 }
385
386 /*
387 * Add unique two uint64_t node to hashtable.
388 */
389 LTTNG_HIDDEN
390 void 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
398 /* RCU read lock protects from ABA. */
399 rcu_read_lock();
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);
403 rcu_read_unlock();
404 assert(node_ptr == &node->node);
405 }
406
407 /*
408 * Add replace unsigned long node to hashtable.
409 */
410 LTTNG_HIDDEN
411 struct 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
419 /* RCU read lock protects from ABA. */
420 rcu_read_lock();
421 node_ptr = cds_lfht_add_replace(ht->ht,
422 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
423 (void *) node->key, &node->node);
424 rcu_read_unlock();
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
433 /*
434 * Add replace unsigned long node to hashtable.
435 */
436 LTTNG_HIDDEN
437 struct 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
445 /* RCU read lock protects from ABA. */
446 rcu_read_lock();
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);
450 rcu_read_unlock();
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
459 /*
460 * Delete node from hashtable.
461 */
462 LTTNG_HIDDEN
463 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
464 {
465 int ret;
466
467 assert(ht);
468 assert(ht->ht);
469 assert(iter);
470
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;
476 }
477
478 /*
479 * Get first node in the hashtable.
480 */
481 LTTNG_HIDDEN
482 void 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 */
494 LTTNG_HIDDEN
495 void 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 */
507 LTTNG_HIDDEN
508 unsigned 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
516 /* RCU read lock protects from ABA and allows RCU traversal. */
517 rcu_read_lock();
518 cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
519 rcu_read_unlock();
520
521 return count;
522 }
523
524 /*
525 * Return lttng ht string node from iterator.
526 */
527 LTTNG_HIDDEN
528 struct 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 */
544 LTTNG_HIDDEN
545 struct 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 }
557
558 /*
559 * Return lttng ht unsigned long node from iterator.
560 */
561 LTTNG_HIDDEN
562 struct 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
575 /*
576 * Return lttng ht stream and index id node from iterator.
577 */
578 LTTNG_HIDDEN
579 struct 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.052368 seconds and 4 git commands to generate.