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 it
   5  * under the terms of the GNU General Public License as published by the Free
   6  * Software Foundation; only version 2 of the License.
   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 with
  14  * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
  15  * Place - Suite 330, Boston, MA  02111-1307, 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 }
 114
 115 /*
 116  * Init lttng ht node string.
 117  */
 118 void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
 119 {
 120         assert(node);
 121
 122         node->key = key;
 123         cds_lfht_node_init(&node->node);
 124 }
 125
 126 /*
 127  * Init lttng ht node unsigned long.
 128  */
 129 void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
 130                 unsigned long key)
 131 {
 132         assert(node);
 133
 134         node->key = key;
 135         cds_lfht_node_init(&node->node);
 136 }
 137
 138 /*
 139  * Free lttng ht node string.
 140  */
 141 void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
 142 {
 143         assert(node);
 144         free(node);
 145 }
 146
 147 /*
 148  * Free lttng ht node unsigned long.
 149  */
 150 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
 151 {
 152         assert(node);
 153         free(node);
 154 }
 155
 156 /*
 157  * Lookup function in hashtable.
 158  */
 159 void lttng_ht_lookup(struct lttng_ht *ht, void *key,
 160                 struct lttng_ht_iter *iter)
 161 {
 162         assert(ht);
 163         assert(ht->ht);
 164
 165         cds_lfht_lookup(ht->ht, ht->hash_fct(key, HASH_SEED),
 166                         ht->match_fct, key, &iter->iter);
 167 }
 168
 169 /*
 170  * Add unique string node to hashtable.
 171  */
 172 void lttng_ht_add_unique_str(struct lttng_ht *ht,
 173                 struct lttng_ht_node_str *node)
 174 {
 175         struct cds_lfht_node *node_ptr;
 176         assert(ht);
 177         assert(ht->ht);
 178         assert(node);
 179
 180         node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, HASH_SEED),
 181                         ht->match_fct, node->key, &node->node);
 182         assert(node_ptr == &node->node);
 183 }
 184
 185 /*
 186  * Add unique unsigned long node to hashtable.
 187  */
 188 void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
 189                 struct lttng_ht_node_ulong *node)
 190 {
 191         struct cds_lfht_node *node_ptr;
 192         assert(ht);
 193         assert(ht->ht);
 194         assert(node);
 195
 196         node_ptr = cds_lfht_add_unique(ht->ht,
 197                         ht->hash_fct((void *) node->key, HASH_SEED), ht->match_fct,
 198                         (void *) node->key, &node->node);
 199         assert(node_ptr == &node->node);
 200 }
 201
 202 /*
 203  * Add replace unsigned long node to hashtable.
 204  */
 205 struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
 206                 struct lttng_ht_node_ulong *node)
 207 {
 208         struct cds_lfht_node *node_ptr;
 209         assert(ht);
 210         assert(ht->ht);
 211         assert(node);
 212
 213         node_ptr = cds_lfht_add_replace(ht->ht,
 214                         ht->hash_fct((void *) node->key, HASH_SEED), ht->match_fct,
 215                         (void *) node->key, &node->node);
 216         if (!node_ptr) {
 217                 return NULL;
 218         } else {
 219                 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
 220         }
 221         assert(node_ptr == &node->node);
 222 }
 223
 224 /*
 225  * Delete node from hashtable.
 226  */
 227 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 228 {
 229         assert(ht);
 230         assert(ht->ht);
 231         assert(iter);
 232
 233         return cds_lfht_del(ht->ht, iter->iter.node);
 234 }
 235
 236 /*
 237  * Get first node in the hashtable.
 238  */
 239 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 240 {
 241         assert(ht);
 242         assert(ht->ht);
 243         assert(iter);
 244
 245         cds_lfht_first(ht->ht, &iter->iter);
 246 }
 247
 248 /*
 249  * Get next node in the hashtable.
 250  */
 251 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 252 {
 253         assert(ht);
 254         assert(ht->ht);
 255         assert(iter);
 256
 257         cds_lfht_next(ht->ht, &iter->iter);
 258 }
 259
 260 /*
 261  * Return the number of nodes in the hashtable.
 262  */
 263 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
 264 {
 265         long scb, sca;
 266         unsigned long count;
 267
 268         assert(ht);
 269         assert(ht->ht);
 270
 271         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 272
 273         return count;
 274 }
 275
 276 /*
 277  * Return lttng ht string node from iterator.
 278  */
 279 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
 280                 struct lttng_ht_iter *iter)
 281 {
 282         struct cds_lfht_node *node;
 283
 284         assert(iter);
 285         node = cds_lfht_iter_get_node(&iter->iter);
 286         if (!node) {
 287                 return NULL;
 288         }
 289         return caa_container_of(node, struct lttng_ht_node_str, node);
 290 }
 291
 292 /*
 293  * Return lttng ht unsigned long node from iterator.
 294  */
 295 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
 296                 struct lttng_ht_iter *iter)
 297 {
 298         struct cds_lfht_node *node;
 299
 300         assert(iter);
 301         node = cds_lfht_iter_get_node(&iter->iter);
 302         if (!node) {
 303                 return NULL;
 304         }
 305         return caa_container_of(node, struct lttng_ht_node_ulong, node);
 306 }