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