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 }