Add support for non unique add string in hashtable
[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 _GNU_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 unsigned long lttng_ht_seed;
31
32 static unsigned long min_hash_alloc_size = 1;
33 static unsigned long max_hash_buckets_size = 0;
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
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
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 */
76 if (!size)
77 size = DEFAULT_HT_SIZE;
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,
86 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
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;
102 case LTTNG_HT_TYPE_U64:
103 ht->match_fct = match_u64;
104 ht->hash_fct = hash_key_u64;
105 break;
106 default:
107 ERR("Unknown lttng hashtable type %d", type);
108 lttng_ht_destroy(ht);
109 goto error;
110 }
111
112 DBG3("Created hashtable size %lu at %p of type %d", size, ht->ht, type);
113
114 return ht;
115
116 error:
117 return NULL;
118 }
119
120 /*
121 * Free a lttng hashtable.
122 */
123 void lttng_ht_destroy(struct lttng_ht *ht)
124 {
125 int ret;
126
127 ret = cds_lfht_destroy(ht->ht, NULL);
128 assert(!ret);
129 free(ht);
130 }
131
132 /*
133 * Init lttng ht node string.
134 */
135 void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
136 {
137 assert(node);
138
139 node->key = key;
140 cds_lfht_node_init(&node->node);
141 }
142
143 /*
144 * Init lttng ht node unsigned long.
145 */
146 void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
147 unsigned long key)
148 {
149 assert(node);
150
151 node->key = key;
152 cds_lfht_node_init(&node->node);
153 }
154
155 /*
156 * Init lttng ht node uint64_t.
157 */
158 void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node,
159 uint64_t key)
160 {
161 assert(node);
162
163 node->key = key;
164 cds_lfht_node_init(&node->node);
165 }
166
167 /*
168 * Free lttng ht node string.
169 */
170 void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
171 {
172 assert(node);
173 free(node);
174 }
175
176 /*
177 * Free lttng ht node unsigned long.
178 */
179 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
180 {
181 assert(node);
182 free(node);
183 }
184
185 /*
186 * Free lttng ht node uint64_t.
187 */
188 void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
189 {
190 assert(node);
191 free(node);
192 }
193
194 /*
195 * Lookup function in hashtable.
196 */
197 void lttng_ht_lookup(struct lttng_ht *ht, void *key,
198 struct lttng_ht_iter *iter)
199 {
200 assert(ht);
201 assert(ht->ht);
202
203 cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
204 ht->match_fct, key, &iter->iter);
205 }
206
207 /*
208 * Add unique string node to hashtable.
209 */
210 void lttng_ht_add_unique_str(struct lttng_ht *ht,
211 struct lttng_ht_node_str *node)
212 {
213 struct cds_lfht_node *node_ptr;
214 assert(ht);
215 assert(ht->ht);
216 assert(node);
217
218 node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
219 ht->match_fct, node->key, &node->node);
220 assert(node_ptr == &node->node);
221 }
222
223 /*
224 * Add string node to hashtable.
225 */
226 void lttng_ht_add_str(struct lttng_ht *ht,
227 struct lttng_ht_node_str *node)
228 {
229 assert(ht);
230 assert(ht->ht);
231 assert(node);
232
233 cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
234 &node->node);
235 }
236
237 /*
238 * Add unsigned long node to hashtable.
239 */
240 void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
241 {
242 assert(ht);
243 assert(ht->ht);
244 assert(node);
245
246 cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
247 &node->node);
248 }
249
250 /*
251 * Add uint64_t node to hashtable.
252
253 */
254 void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
255 {
256 assert(ht);
257 assert(ht->ht);
258 assert(node);
259
260 cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
261 &node->node);
262 }
263
264 /*
265 * Add unique unsigned long node to hashtable.
266 */
267 void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
268 struct lttng_ht_node_ulong *node)
269 {
270 struct cds_lfht_node *node_ptr;
271 assert(ht);
272 assert(ht->ht);
273 assert(node);
274
275 node_ptr = cds_lfht_add_unique(ht->ht,
276 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
277 (void *) node->key, &node->node);
278 assert(node_ptr == &node->node);
279 }
280
281 /*
282 * Add unique uint64_t node to hashtable.
283 */
284 void lttng_ht_add_unique_u64(struct lttng_ht *ht,
285 struct lttng_ht_node_u64 *node)
286 {
287 struct cds_lfht_node *node_ptr;
288 assert(ht);
289 assert(ht->ht);
290 assert(node);
291
292 node_ptr = cds_lfht_add_unique(ht->ht,
293 ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
294 &node->key, &node->node);
295 assert(node_ptr == &node->node);
296 }
297
298 /*
299 * Add replace unsigned long node to hashtable.
300 */
301 struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
302 struct lttng_ht_node_ulong *node)
303 {
304 struct cds_lfht_node *node_ptr;
305 assert(ht);
306 assert(ht->ht);
307 assert(node);
308
309 node_ptr = cds_lfht_add_replace(ht->ht,
310 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
311 (void *) node->key, &node->node);
312 if (!node_ptr) {
313 return NULL;
314 } else {
315 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
316 }
317 assert(node_ptr == &node->node);
318 }
319
320 /*
321 * Add replace unsigned long node to hashtable.
322 */
323 struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht,
324 struct lttng_ht_node_u64 *node)
325 {
326 struct cds_lfht_node *node_ptr;
327 assert(ht);
328 assert(ht->ht);
329 assert(node);
330
331 node_ptr = cds_lfht_add_replace(ht->ht,
332 ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
333 &node->key, &node->node);
334 if (!node_ptr) {
335 return NULL;
336 } else {
337 return caa_container_of(node_ptr, struct lttng_ht_node_u64, node);
338 }
339 assert(node_ptr == &node->node);
340 }
341
342 /*
343 * Delete node from hashtable.
344 */
345 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
346 {
347 assert(ht);
348 assert(ht->ht);
349 assert(iter);
350
351 return cds_lfht_del(ht->ht, iter->iter.node);
352 }
353
354 /*
355 * Get first node in the hashtable.
356 */
357 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
358 {
359 assert(ht);
360 assert(ht->ht);
361 assert(iter);
362
363 cds_lfht_first(ht->ht, &iter->iter);
364 }
365
366 /*
367 * Get next node in the hashtable.
368 */
369 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
370 {
371 assert(ht);
372 assert(ht->ht);
373 assert(iter);
374
375 cds_lfht_next(ht->ht, &iter->iter);
376 }
377
378 /*
379 * Return the number of nodes in the hashtable.
380 */
381 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
382 {
383 long scb, sca;
384 unsigned long count;
385
386 assert(ht);
387 assert(ht->ht);
388
389 cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
390
391 return count;
392 }
393
394 /*
395 * Return lttng ht string node from iterator.
396 */
397 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
398 struct lttng_ht_iter *iter)
399 {
400 struct cds_lfht_node *node;
401
402 assert(iter);
403 node = cds_lfht_iter_get_node(&iter->iter);
404 if (!node) {
405 return NULL;
406 }
407 return caa_container_of(node, struct lttng_ht_node_str, node);
408 }
409
410 /*
411 * Return lttng ht unsigned long node from iterator.
412 */
413 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
414 struct lttng_ht_iter *iter)
415 {
416 struct cds_lfht_node *node;
417
418 assert(iter);
419 node = cds_lfht_iter_get_node(&iter->iter);
420 if (!node) {
421 return NULL;
422 }
423 return caa_container_of(node, struct lttng_ht_node_ulong, node);
424 }
425
426 /*
427 * Return lttng ht unsigned long node from iterator.
428 */
429 struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(
430 struct lttng_ht_iter *iter)
431 {
432 struct cds_lfht_node *node;
433
434 assert(iter);
435 node = cds_lfht_iter_get_node(&iter->iter);
436 if (!node) {
437 return NULL;
438 }
439 return caa_container_of(node, struct lttng_ht_node_u64, node);
440 }
441
442 /*
443 * lib constructor
444 */
445 static void __attribute__((constructor)) _init(void)
446 {
447 /* Init hash table seed */
448 lttng_ht_seed = (unsigned long) time(NULL);
449 }
This page took 0.05881 seconds and 4 git commands to generate.