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 unsigned long node to hashtable.
 225  */
 226 void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
 227 {
 228         assert(ht);
 229         assert(ht->ht);
 230         assert(node);
 231
 232         cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
 233                         &node->node);
 234 }
 235
 236 /*
 237  * Add uint64_t node to hashtable.
 238
 239  */
 240 void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
 241 {
 242         assert(ht);
 243         assert(ht->ht);
 244         assert(node);
 245
 246         cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
 247                         &node->node);
 248 }
 249
 250 /*
 251  * Add unique unsigned long node to hashtable.
 252  */
 253 void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
 254                 struct lttng_ht_node_ulong *node)
 255 {
 256         struct cds_lfht_node *node_ptr;
 257         assert(ht);
 258         assert(ht->ht);
 259         assert(node);
 260
 261         node_ptr = cds_lfht_add_unique(ht->ht,
 262                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 263                         (void *) node->key, &node->node);
 264         assert(node_ptr == &node->node);
 265 }
 266
 267 /*
 268  * Add unique uint64_t node to hashtable.
 269  */
 270 void lttng_ht_add_unique_u64(struct lttng_ht *ht,
 271                 struct lttng_ht_node_u64 *node)
 272 {
 273         struct cds_lfht_node *node_ptr;
 274         assert(ht);
 275         assert(ht->ht);
 276         assert(node);
 277
 278         node_ptr = cds_lfht_add_unique(ht->ht,
 279                         ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
 280                         &node->key, &node->node);
 281         assert(node_ptr == &node->node);
 282 }
 283
 284 /*
 285  * Add replace unsigned long node to hashtable.
 286  */
 287 struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
 288                 struct lttng_ht_node_ulong *node)
 289 {
 290         struct cds_lfht_node *node_ptr;
 291         assert(ht);
 292         assert(ht->ht);
 293         assert(node);
 294
 295         node_ptr = cds_lfht_add_replace(ht->ht,
 296                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 297                         (void *) node->key, &node->node);
 298         if (!node_ptr) {
 299                 return NULL;
 300         } else {
 301                 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
 302         }
 303         assert(node_ptr == &node->node);
 304 }
 305
 306 /*
 307  * Add replace unsigned long node to hashtable.
 308  */
 309 struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht,
 310                 struct lttng_ht_node_u64 *node)
 311 {
 312         struct cds_lfht_node *node_ptr;
 313         assert(ht);
 314         assert(ht->ht);
 315         assert(node);
 316
 317         node_ptr = cds_lfht_add_replace(ht->ht,
 318                         ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
 319                         &node->key, &node->node);
 320         if (!node_ptr) {
 321                 return NULL;
 322         } else {
 323                 return caa_container_of(node_ptr, struct lttng_ht_node_u64, node);
 324         }
 325         assert(node_ptr == &node->node);
 326 }
 327
 328 /*
 329  * Delete node from hashtable.
 330  */
 331 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 332 {
 333         assert(ht);
 334         assert(ht->ht);
 335         assert(iter);
 336
 337         return cds_lfht_del(ht->ht, iter->iter.node);
 338 }
 339
 340 /*
 341  * Get first node in the hashtable.
 342  */
 343 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 344 {
 345         assert(ht);
 346         assert(ht->ht);
 347         assert(iter);
 348
 349         cds_lfht_first(ht->ht, &iter->iter);
 350 }
 351
 352 /*
 353  * Get next node in the hashtable.
 354  */
 355 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 356 {
 357         assert(ht);
 358         assert(ht->ht);
 359         assert(iter);
 360
 361         cds_lfht_next(ht->ht, &iter->iter);
 362 }
 363
 364 /*
 365  * Return the number of nodes in the hashtable.
 366  */
 367 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
 368 {
 369         long scb, sca;
 370         unsigned long count;
 371
 372         assert(ht);
 373         assert(ht->ht);
 374
 375         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 376
 377         return count;
 378 }
 379
 380 /*
 381  * Return lttng ht string node from iterator.
 382  */
 383 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
 384                 struct lttng_ht_iter *iter)
 385 {
 386         struct cds_lfht_node *node;
 387
 388         assert(iter);
 389         node = cds_lfht_iter_get_node(&iter->iter);
 390         if (!node) {
 391                 return NULL;
 392         }
 393         return caa_container_of(node, struct lttng_ht_node_str, node);
 394 }
 395
 396 /*
 397  * Return lttng ht unsigned long node from iterator.
 398  */
 399 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
 400                 struct lttng_ht_iter *iter)
 401 {
 402         struct cds_lfht_node *node;
 403
 404         assert(iter);
 405         node = cds_lfht_iter_get_node(&iter->iter);
 406         if (!node) {
 407                 return NULL;
 408         }
 409         return caa_container_of(node, struct lttng_ht_node_ulong, node);
 410 }
 411
 412 /*
 413  * Return lttng ht unsigned long node from iterator.
 414  */
 415 struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(
 416                 struct lttng_ht_iter *iter)
 417 {
 418         struct cds_lfht_node *node;
 419
 420         assert(iter);
 421         node = cds_lfht_iter_get_node(&iter->iter);
 422         if (!node) {
 423                 return NULL;
 424         }
 425         return caa_container_of(node, struct lttng_ht_node_u64, node);
 426 }
 427
 428 /*
 429  * lib constructor
 430  */
 431 static void __attribute__((constructor)) _init(void)
 432 {
 433         /* Init hash table seed */
 434         lttng_ht_seed = (unsigned long) time(NULL);
 435 }