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