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 #define HASH_SEED            0x42UL             /* The answer to life */
  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  * Return an allocated lttng hashtable.
  59  */
  60 struct lttng_ht *lttng_ht_new(unsigned long size, int type)
  61 {
  62         struct lttng_ht *ht;
  63
  64         /* Test size */
  65         if (!size)
  66                 size = DEFAULT_HT_SIZE;
  67
  68         ht = zmalloc(sizeof(*ht));
  69         if (ht == NULL) {
  70                 PERROR("zmalloc lttng_ht");
  71                 goto error;
  72         }
  73
  74         ht->ht = cds_lfht_new(size, min_hash_alloc_size, max_hash_buckets_size,
  75                         CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
  76         /*
  77          * There is already an assert in the RCU hashtable code so if the ht is
  78          * NULL here there is a *huge* problem.
  79          */
  80         assert(ht->ht);
  81
  82         switch (type) {
  83         case LTTNG_HT_TYPE_STRING:
  84                 ht->match_fct = match_str;
  85                 ht->hash_fct = hash_key_str;
  86                 break;
  87         case LTTNG_HT_TYPE_ULONG:
  88                 ht->match_fct = match_ulong;
  89                 ht->hash_fct = hash_key_ulong;
  90                 break;
  91         default:
  92                 ERR("Unknown lttng hashtable type %d", type);
  93                 goto error;
  94         }
  95
  96         DBG3("Created hashtable size %lu at %p of type %d", size, ht->ht, type);
  97
  98         return ht;
  99
 100 error:
 101         return NULL;
 102 }
 103
 104 /*
 105  * Free a lttng hashtable.
 106  */
 107 void lttng_ht_destroy(struct lttng_ht *ht)
 108 {
 109         int ret;
 110
 111         ret = cds_lfht_destroy(ht->ht, NULL);
 112         assert(!ret);
 113         free(ht);
 114 }
 115
 116 /*
 117  * Init lttng ht node string.
 118  */
 119 void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
 120 {
 121         assert(node);
 122
 123         node->key = key;
 124         cds_lfht_node_init(&node->node);
 125 }
 126
 127 /*
 128  * Init lttng ht node unsigned long.
 129  */
 130 void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
 131                 unsigned long key)
 132 {
 133         assert(node);
 134
 135         node->key = key;
 136         cds_lfht_node_init(&node->node);
 137 }
 138
 139 /*
 140  * Free lttng ht node string.
 141  */
 142 void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
 143 {
 144         assert(node);
 145         free(node);
 146 }
 147
 148 /*
 149  * Free lttng ht node unsigned long.
 150  */
 151 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
 152 {
 153         assert(node);
 154         free(node);
 155 }
 156
 157 /*
 158  * Lookup function in hashtable.
 159  */
 160 void lttng_ht_lookup(struct lttng_ht *ht, void *key,
 161                 struct lttng_ht_iter *iter)
 162 {
 163         assert(ht);
 164         assert(ht->ht);
 165
 166         cds_lfht_lookup(ht->ht, ht->hash_fct(key, HASH_SEED),
 167                         ht->match_fct, key, &iter->iter);
 168 }
 169
 170 /*
 171  * Add unique string node to hashtable.
 172  */
 173 void lttng_ht_add_unique_str(struct lttng_ht *ht,
 174                 struct lttng_ht_node_str *node)
 175 {
 176         struct cds_lfht_node *node_ptr;
 177         assert(ht);
 178         assert(ht->ht);
 179         assert(node);
 180
 181         node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, HASH_SEED),
 182                         ht->match_fct, node->key, &node->node);
 183         assert(node_ptr == &node->node);
 184 }
 185
 186 /*
 187  * Add unsigned long node to hashtable.
 188  */
 189 void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
 190 {
 191         assert(ht);
 192         assert(ht->ht);
 193         assert(node);
 194
 195         cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, HASH_SEED),
 196                         &node->node);
 197 }
 198
 199 /*
 200  * Add unique unsigned long node to hashtable.
 201  */
 202 void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
 203                 struct lttng_ht_node_ulong *node)
 204 {
 205         struct cds_lfht_node *node_ptr;
 206         assert(ht);
 207         assert(ht->ht);
 208         assert(node);
 209
 210         node_ptr = cds_lfht_add_unique(ht->ht,
 211                         ht->hash_fct((void *) node->key, HASH_SEED), ht->match_fct,
 212                         (void *) node->key, &node->node);
 213         assert(node_ptr == &node->node);
 214 }
 215
 216 /*
 217  * Add replace unsigned long node to hashtable.
 218  */
 219 struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
 220                 struct lttng_ht_node_ulong *node)
 221 {
 222         struct cds_lfht_node *node_ptr;
 223         assert(ht);
 224         assert(ht->ht);
 225         assert(node);
 226
 227         node_ptr = cds_lfht_add_replace(ht->ht,
 228                         ht->hash_fct((void *) node->key, HASH_SEED), ht->match_fct,
 229                         (void *) node->key, &node->node);
 230         if (!node_ptr) {
 231                 return NULL;
 232         } else {
 233                 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
 234         }
 235         assert(node_ptr == &node->node);
 236 }
 237
 238 /*
 239  * Delete node from hashtable.
 240  */
 241 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 242 {
 243         assert(ht);
 244         assert(ht->ht);
 245         assert(iter);
 246
 247         return cds_lfht_del(ht->ht, iter->iter.node);
 248 }
 249
 250 /*
 251  * Get first node in the hashtable.
 252  */
 253 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 254 {
 255         assert(ht);
 256         assert(ht->ht);
 257         assert(iter);
 258
 259         cds_lfht_first(ht->ht, &iter->iter);
 260 }
 261
 262 /*
 263  * Get next node in the hashtable.
 264  */
 265 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 266 {
 267         assert(ht);
 268         assert(ht->ht);
 269         assert(iter);
 270
 271         cds_lfht_next(ht->ht, &iter->iter);
 272 }
 273
 274 /*
 275  * Return the number of nodes in the hashtable.
 276  */
 277 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
 278 {
 279         long scb, sca;
 280         unsigned long count;
 281
 282         assert(ht);
 283         assert(ht->ht);
 284
 285         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 286
 287         return count;
 288 }
 289
 290 /*
 291  * Return lttng ht string node from iterator.
 292  */
 293 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
 294                 struct lttng_ht_iter *iter)
 295 {
 296         struct cds_lfht_node *node;
 297
 298         assert(iter);
 299         node = cds_lfht_iter_get_node(&iter->iter);
 300         if (!node) {
 301                 return NULL;
 302         }
 303         return caa_container_of(node, struct lttng_ht_node_str, node);
 304 }
 305
 306 /*
 307  * Return lttng ht unsigned long node from iterator.
 308  */
 309 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
 310                 struct lttng_ht_iter *iter)
 311 {
 312         struct cds_lfht_node *node;
 313
 314         assert(iter);
 315         node = cds_lfht_iter_get_node(&iter->iter);
 316         if (!node) {
 317                 return NULL;
 318         }
 319         return caa_container_of(node, struct lttng_ht_node_ulong, node);
 320 }