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/lttng-share.h>
  25 #include <common/lttngerr.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  * Delete node from hashtable.
 204  */
 205 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 206 {
 207         assert(ht);
 208         assert(ht->ht);
 209         assert(iter);
 210
 211         return cds_lfht_del(ht->ht, iter->iter.node);
 212 }
 213
 214 /*
 215  * Get first node in the hashtable.
 216  */
 217 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 218 {
 219         assert(ht);
 220         assert(ht->ht);
 221         assert(iter);
 222
 223         cds_lfht_first(ht->ht, &iter->iter);
 224 }
 225
 226 /*
 227  * Get next node in the hashtable.
 228  */
 229 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 230 {
 231         assert(ht);
 232         assert(ht->ht);
 233         assert(iter);
 234
 235         cds_lfht_next(ht->ht, &iter->iter);
 236 }
 237
 238 /*
 239  * Return the number of nodes in the hashtable.
 240  */
 241 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
 242 {
 243         long scb, sca;
 244         unsigned long count;
 245
 246         assert(ht);
 247         assert(ht->ht);
 248
 249         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 250
 251         return count;
 252 }
 253
 254 /*
 255  * Return lttng ht string node from iterator.
 256  */
 257 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
 258                 struct lttng_ht_iter *iter)
 259 {
 260         struct cds_lfht_node *node;
 261
 262         assert(iter);
 263         node = cds_lfht_iter_get_node(&iter->iter);
 264         if (!node) {
 265                 return NULL;
 266         }
 267         return caa_container_of(node, struct lttng_ht_node_str, node);
 268 }
 269
 270 /*
 271  * Return lttng ht unsigned long node from iterator.
 272  */
 273 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
 274                 struct lttng_ht_iter *iter)
 275 {
 276         struct cds_lfht_node *node;
 277
 278         assert(iter);
 279         node = cds_lfht_iter_get_node(&iter->iter);
 280         if (!node) {
 281                 return NULL;
 282         }
 283         return caa_container_of(node, struct lttng_ht_node_ulong, node);
 284 }