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