HT support for keys with two uint64_t

Add the support in the hashtable abstraction layer to handle a key
composed of a two uint64_t.

The hash function is a simple XOR between the two hashes and the compare
function resolves the eventual collisions by comparing the two values.

Signed-off-by: Julien Desfossez <jdesfossez@efficios.com>
Signed-off-by: David Goulet <dgoulet@efficios.com>

diff --git a/src/common/hashtable/hashtable.c b/src/common/hashtable/hashtable.c
index 07210fa8161e63e41a6ea12c061812b27c94d1c8..b08a57e5cc0a07f53582a3181443d395c8b97765 100644 (file)
--- a/src/common/hashtable/hashtable.c
+++ b/src/common/hashtable/hashtable.c
@@ -65,6 +65,17 @@ static int match_u64(struct cds_lfht_node *node, const void *key)
        return hash_match_key_u64(&match_node->key, (void *) key);
 }
 
+/*
+ * Match function for two uint64_t node.
+ */
+static int match_two_u64(struct cds_lfht_node *node, const void *key)
+{
+       struct lttng_ht_node_two_u64 *match_node =
+               caa_container_of(node, struct lttng_ht_node_two_u64, node);
+
+       return hash_match_key_two_u64((void *) &match_node->key, (void *) key);
+}
+
 /*
  * Return an allocated lttng hashtable.
  */
@@ -103,6 +114,10 @@ struct lttng_ht *lttng_ht_new(unsigned long size, int type)
                ht->match_fct = match_u64;
                ht->hash_fct = hash_key_u64;
                break;
+       case LTTNG_HT_TYPE_TWO_U64:
+               ht->match_fct = match_two_u64;
+               ht->hash_fct = hash_key_two_u64;
+               break;
        default:
                ERR("Unknown lttng hashtable type %d", type);
                lttng_ht_destroy(ht);
@@ -164,6 +179,19 @@ void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node,
        cds_lfht_node_init(&node->node);
 }
 
+/*
+ * Init lttng ht node with two uint64_t.
+ */
+void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node,
+               uint64_t key1, uint64_t key2)
+{
+       assert(node);
+
+       node->key.key1 = key1;
+       node->key.key2 = key2;
+       cds_lfht_node_init(&node->node);
+}
+
 /*
  * Free lttng ht node string.
  */
@@ -191,6 +219,15 @@ void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
        free(node);
 }
 
+/*
+ * Free lttng ht node two uint64_t.
+ */
+void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
+{
+       assert(node);
+       free(node);
+}
+
 /*
  * Lookup function in hashtable.
  */
@@ -295,6 +332,23 @@ void lttng_ht_add_unique_u64(struct lttng_ht *ht,
        assert(node_ptr == &node->node);
 }
 
+/*
+ * Add unique two uint64_t node to hashtable.
+ */
+void lttng_ht_add_unique_two_u64(struct lttng_ht *ht,
+               struct lttng_ht_node_two_u64 *node)
+{
+       struct cds_lfht_node *node_ptr;
+       assert(ht);
+       assert(ht->ht);
+       assert(node);
+
+       node_ptr = cds_lfht_add_unique(ht->ht,
+                       ht->hash_fct((void *) &node->key, lttng_ht_seed), ht->match_fct,
+                       (void *) &node->key, &node->node);
+       assert(node_ptr == &node->node);
+}
+
 /*
  * Add replace unsigned long node to hashtable.
  */
@@ -439,6 +493,22 @@ struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(
        return caa_container_of(node, struct lttng_ht_node_u64, node);
 }
 
+/*
+ * Return lttng ht stream and index id node from iterator.
+ */
+struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64(
+               struct lttng_ht_iter *iter)
+{
+       struct cds_lfht_node *node;
+
+       assert(iter);
+       node = cds_lfht_iter_get_node(&iter->iter);
+       if (!node) {
+               return NULL;
+       }
+       return caa_container_of(node, struct lttng_ht_node_two_u64, node);
+}
+
 /*
  * lib constructor
  */

diff --git a/src/common/hashtable/hashtable.h b/src/common/hashtable/hashtable.h
index 4a8a2bd5c53a184b40ebe5484213816934a80300..826e1207e00b3eb907715ba98299c896f9cbce6e 100644 (file)
--- a/src/common/hashtable/hashtable.h
+++ b/src/common/hashtable/hashtable.h
@@ -33,6 +33,7 @@ enum lttng_ht_type {
        LTTNG_HT_TYPE_STRING,
        LTTNG_HT_TYPE_ULONG,
        LTTNG_HT_TYPE_U64,
+       LTTNG_HT_TYPE_TWO_U64,
 };
 
 struct lttng_ht {
@@ -63,6 +64,17 @@ struct lttng_ht_node_u64 {
        struct rcu_head head;
 };
 
+struct lttng_ht_two_u64 {
+       uint64_t key1;
+       uint64_t key2;
+};
+
+struct lttng_ht_node_two_u64 {
+       struct lttng_ht_two_u64 key;
+       struct cds_lfht_node node;
+       struct rcu_head head;
+};
+
 /* Hashtable new and destroy */
 extern struct lttng_ht *lttng_ht_new(unsigned long size, int type);
 extern void lttng_ht_destroy(struct lttng_ht *ht);
@@ -73,9 +85,12 @@ extern void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
                unsigned long key);
 extern void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node,
                uint64_t key);
+extern void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node,
+               uint64_t key1, uint64_t key2);
 extern void lttng_ht_node_free_str(struct lttng_ht_node_str *node);
 extern void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node);
 extern void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node);
+extern void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node);
 
 extern void lttng_ht_lookup(struct lttng_ht *ht, void *key,
                struct lttng_ht_iter *iter);
@@ -87,6 +102,8 @@ extern void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
                struct lttng_ht_node_ulong *node);
 extern void lttng_ht_add_unique_u64(struct lttng_ht *ht,
                struct lttng_ht_node_u64 *node);
+extern void lttng_ht_add_unique_two_u64(struct lttng_ht *ht,
+               struct lttng_ht_node_two_u64 *node);
 extern struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(
                struct lttng_ht *ht, struct lttng_ht_node_ulong *node);
 extern struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(
@@ -112,5 +129,7 @@ extern struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
                struct lttng_ht_iter *iter);
 extern struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(
                struct lttng_ht_iter *iter);
+extern struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64(
+               struct lttng_ht_iter *iter);
 
 #endif /* _LTT_HT_H */

diff --git a/src/common/hashtable/utils.c b/src/common/hashtable/utils.c
index 8d0e515aecafbb94a347c418f23bf341f719f71c..1ea699d6edb921364a30d3c92e31e9ee538571b4 100644 (file)
--- a/src/common/hashtable/utils.c
+++ b/src/common/hashtable/utils.c
@@ -60,6 +60,7 @@
 #include "utils.h"
 #include <common/compat/endian.h>    /* attempt to define endianness */
 #include <common/common.h>
+#include <common/hashtable/hashtable.h>
 
 /*
  * My best guess at if you are big-endian or little-endian.  This may
@@ -496,6 +497,17 @@ unsigned long hash_key_str(void *key, unsigned long seed)
        return hashlittle(key, strlen((char *) key), seed);
 }
 
+/*
+ * Hash function for two uint64_t.
+ */
+LTTNG_HIDDEN
+unsigned long hash_key_two_u64(void *key, unsigned long seed)
+{
+       struct lttng_ht_two_u64 *k = (struct lttng_ht_two_u64 *) key;
+
+       return hash_key_u64(&k->key1, seed) ^ hash_key_u64(&k->key2, seed);
+}
+
 /*
  * Hash function compare for number value.
  */
@@ -534,3 +546,20 @@ int hash_match_key_str(void *key1, void *key2)
 
        return 0;
 }
+
+/*
+ * Hash function compare two uint64_t.
+ */
+LTTNG_HIDDEN
+int hash_match_key_two_u64(void *key1, void *key2)
+{
+       struct lttng_ht_two_u64 *k1 = (struct lttng_ht_two_u64 *) key1;
+       struct lttng_ht_two_u64 *k2 = (struct lttng_ht_two_u64 *) key2;
+
+       if (hash_match_key_u64(&k1->key1, &k2->key1) &&
+                       hash_match_key_u64(&k1->key2, &k2->key2)) {
+               return 1;
+       }
+
+       return 0;
+}

diff --git a/src/common/hashtable/utils.h b/src/common/hashtable/utils.h
index 38d6121e4ce65cd891e7d1ce6d485515596985dd..9d53e3864f9d7ae54142e24c12d65216b4c327cf 100644 (file)
--- a/src/common/hashtable/utils.h
+++ b/src/common/hashtable/utils.h
@@ -23,8 +23,10 @@
 unsigned long hash_key_ulong(void *_key, unsigned long seed);
 unsigned long hash_key_u64(void *_key, unsigned long seed);
 unsigned long hash_key_str(void *key, unsigned long seed);
+unsigned long hash_key_two_u64(void *key, unsigned long seed);
 int hash_match_key_ulong(void *key1, void *key2);
 int hash_match_key_u64(void *key1, void *key2);
 int hash_match_key_str(void *key1, void *key2);
+int hash_match_key_two_u64(void *key1, void *key2);
 
 #endif /* _LTT_HT_UTILS_H */