liblttng-ht/lttng-ht.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 <lttng-ht.h>
  25 #include <lttng-share.h>
  26 #include <lttngerr.h>
  27
  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         size != 0 ? : (size = DEFAULT_HT_SIZE);
  66
  67         ht = zmalloc(sizeof(*ht));
  68         if (ht == NULL) {
  69                 PERROR("zmalloc lttng_ht");
  70                 goto error;
  71         }
  72
  73         ht->ht = cds_lfht_new(size, min_hash_alloc_size, max_hash_buckets_size,
  74                         CDS_LFHT_AUTO_RESIZE, NULL);
  75         /*
  76          * There is already an assert in the RCU hashtable code so if the ht is
  77          * NULL here there is a *huge* problem.
  78          */
  79         assert(ht->ht);
  80
  81         switch (type) {
  82         case LTTNG_HT_TYPE_STRING:
  83                 ht->match_fct = match_str;
  84                 ht->hash_fct = hash_key_str;
  85                 break;
  86         case LTTNG_HT_TYPE_ULONG:
  87                 ht->match_fct = match_ulong;
  88                 ht->hash_fct = hash_key_ulong;
  89                 break;
  90         default:
  91                 ERR("Unknown lttng hashtable type %d", type);
  92                 goto error;
  93         }
  94
  95         DBG3("Created hashtable size %lu at %p of type %d", size, ht->ht, type);
  96
  97         return ht;
  98
  99 error:
 100         return NULL;
 101 }
 102
 103 /*
 104  * Free a lttng hashtable.
 105  */
 106 void lttng_ht_destroy(struct lttng_ht *ht)
 107 {
 108         int ret;
 109
 110         ret = cds_lfht_destroy(ht->ht, NULL);
 111         assert(!ret);
 112 }
 113
 114 /*
 115  * Init lttng ht node string.
 116  */
 117 void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
 118 {
 119         assert(node);
 120
 121         node->key = key;
 122         cds_lfht_node_init(&node->node);
 123 }
 124
 125 /*
 126  * Init lttng ht node unsigned long.
 127  */
 128 void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
 129                 unsigned long key)
 130 {
 131         assert(node);
 132
 133         node->key = key;
 134         cds_lfht_node_init(&node->node);
 135 }
 136
 137 /*
 138  * Free lttng ht node string.
 139  */
 140 void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
 141 {
 142         assert(node);
 143         free(node);
 144 }
 145
 146 /*
 147  * Free lttng ht node unsigned long.
 148  */
 149 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
 150 {
 151         assert(node);
 152         free(node);
 153 }
 154
 155 /*
 156  * Lookup function in hashtable.
 157  */
 158 void lttng_ht_lookup(struct lttng_ht *ht, void *key,
 159                 struct lttng_ht_iter *iter)
 160 {
 161         assert(ht);
 162         assert(ht->ht);
 163         assert(key);
 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 }