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 = (1UL << 20);
  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, 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 unique unsigned long node to hashtable.
 188  */
 189 void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
 190                 struct lttng_ht_node_ulong *node)
 191 {
 192         struct cds_lfht_node *node_ptr;
 193         assert(ht);
 194         assert(ht->ht);
 195         assert(node);
 196
 197         node_ptr = cds_lfht_add_unique(ht->ht,
 198                         ht->hash_fct((void *) node->key, HASH_SEED), ht->match_fct,
 199                         (void *) node->key, &node->node);
 200         assert(node_ptr == &node->node);
 201 }
 202
 203 /*
 204  * Add replace unsigned long node to hashtable.
 205  */
 206 struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
 207                 struct lttng_ht_node_ulong *node)
 208 {
 209         struct cds_lfht_node *node_ptr;
 210         assert(ht);
 211         assert(ht->ht);
 212         assert(node);
 213
 214         node_ptr = cds_lfht_add_replace(ht->ht,
 215                         ht->hash_fct((void *) node->key, HASH_SEED), ht->match_fct,
 216                         (void *) node->key, &node->node);
 217         if (!node_ptr) {
 218                 return NULL;
 219         } else {
 220                 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
 221         }
 222         assert(node_ptr == &node->node);
 223 }
 224
 225 /*
 226  * Delete node from hashtable.
 227  */
 228 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 229 {
 230         assert(ht);
 231         assert(ht->ht);
 232         assert(iter);
 233
 234         return cds_lfht_del(ht->ht, iter->iter.node);
 235 }
 236
 237 /*
 238  * Get first node in the hashtable.
 239  */
 240 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 241 {
 242         assert(ht);
 243         assert(ht->ht);
 244         assert(iter);
 245
 246         cds_lfht_first(ht->ht, &iter->iter);
 247 }
 248
 249 /*
 250  * Get next node in the hashtable.
 251  */
 252 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 253 {
 254         assert(ht);
 255         assert(ht->ht);
 256         assert(iter);
 257
 258         cds_lfht_next(ht->ht, &iter->iter);
 259 }
 260
 261 /*
 262  * Return the number of nodes in the hashtable.
 263  */
 264 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
 265 {
 266         long scb, sca;
 267         unsigned long count;
 268
 269         assert(ht);
 270         assert(ht->ht);
 271
 272         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 273
 274         return count;
 275 }
 276
 277 /*
 278  * Return lttng ht string node from iterator.
 279  */
 280 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
 281                 struct lttng_ht_iter *iter)
 282 {
 283         struct cds_lfht_node *node;
 284
 285         assert(iter);
 286         node = cds_lfht_iter_get_node(&iter->iter);
 287         if (!node) {
 288                 return NULL;
 289         }
 290         return caa_container_of(node, struct lttng_ht_node_str, node);
 291 }
 292
 293 /*
 294  * Return lttng ht unsigned long node from iterator.
 295  */
 296 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
 297                 struct lttng_ht_iter *iter)
 298 {
 299         struct cds_lfht_node *node;
 300
 301         assert(iter);
 302         node = cds_lfht_iter_get_node(&iter->iter);
 303         if (!node) {
 304                 return NULL;
 305         }
 306         return caa_container_of(node, struct lttng_ht_node_ulong, node);
 307 }