Simple hash table is added. Hash function is modulo operator and no
conflict is allowed. Key must be unique. It would be useful in managing
a resource pool having finite unique keys, e.g. flow table entry with
unique flow ID.
Signed-off-by: Yongseok Koh <ys...@mellanox.com>
Signed-off-by: Viacheslav Ovsiienko <viachesl...@mellanox.com>
Acked-by: Matan Azrad <ma...@mellanox.com>
---
drivers/net/mlx5/mlx5_utils.h | 115 ++++++++++++++++++++++++++++++++++++++++--
1 file changed, 112 insertions(+), 3 deletions(-)
diff --git a/drivers/net/mlx5/mlx5_utils.h b/drivers/net/mlx5/mlx5_utils.h
index 97092c7..5a7de62 100644
--- a/drivers/net/mlx5/mlx5_utils.h
+++ b/drivers/net/mlx5/mlx5_utils.h
@@ -6,12 +6,13 @@
#ifndef RTE_PMD_MLX5_UTILS_H_
#define RTE_PMD_MLX5_UTILS_H_
+#include <assert.h>
+#include <errno.h>
+#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
-#include <limits.h>
-#include <assert.h>
-#include <errno.h>
+#include <sys/queue.h>
#include "mlx5_defs.h"
@@ -150,6 +151,114 @@
\
snprintf(name, sizeof(name), __VA_ARGS__)
+/*
+ * Simple Hash Table for Key-Data pair.
+ *
+ * Key must be unique. No conflict is allowed.
+ *
+ * mlx5_shtable_entry could be a part of the data structure to store, e.g.,
+ *
+ * struct DATA {
+ * struct mlx5_shtable_entry entry;
+ * custom_data_t custom_data;
+ * };
+ *
+ * And the actual hash table should be defined as,
+ *
+ * struct mlx5_shtable_bucket TABLE[TABLE_SZ];
+ *
+ * Hash function is simply modulo (%) operator for now.
+ */
+
+/* Data entry for hash table. */
+struct mlx5_shtable_entry {
+ LIST_ENTRY(mlx5_shtable_entry) next;
+ uint32_t key;
+};
+
+/* Structure for hash bucket. */
+LIST_HEAD(mlx5_shtable_bucket, mlx5_shtable_entry);
+
+/**
+ * Search an entry matching the key.
+ *
+ * @param htable
+ * Pointer to the table.
+ * @param tbl_sz
+ * Size of the table.
+ * @param key
+ * Key for the searching entry.
+ *
+ * @return
+ * Pointer of the table entry if found, NULL otherwise.
+ */
+static inline struct mlx5_shtable_entry *
+mlx5_shtable_search(struct mlx5_shtable_bucket *htable, int tbl_sz,
+ uint32_t key)
+{
+ struct mlx5_shtable_bucket *bucket;
+ struct mlx5_shtable_entry *node;
+ uint32_t idx;
+
+ idx = key % tbl_sz;
+ bucket = &htable[idx];
+ LIST_FOREACH(node, bucket, next) {
+ if (node->key == key)
+ return node;
+ }
+ return NULL;
+}
+
+/**
+ * Insert an entry.
+ *
+ * @param htable
+ * Pointer to the table.
+ * @param tbl_sz
+ * Size of the table.
+ * @param key
+ * Key for the searching entry.
+ *
+ * @return
+ * 0 if succeed, -EEXIST if conflict.
+ */
+static inline int
+mlx5_shtable_insert(struct mlx5_shtable_bucket *htable, int tbl_sz,
+ struct mlx5_shtable_entry *ent)
+{
+ struct mlx5_shtable_bucket *bucket;
+ struct mlx5_shtable_entry *node;
+ uint32_t idx;
+
+ idx = ent->key % tbl_sz;
+ bucket = &htable[idx];
+ LIST_FOREACH(node, bucket, next) {
+ if (node->key == ent->key)
+ return -EEXIST;
+ }
+ LIST_INSERT_HEAD(bucket, ent, next);
+ return 0;
+}
+
+/**
+ * Revmoe an entry from its table.
+ *
+ * @param htable
+ * Pointer to the table.
+ * @param tbl_sz
+ * Size of the table.
+ * @param key
+ * Key for the searching entry.
+ */
+static inline void
+mlx5_shtable_remove(struct mlx5_shtable_entry *ent)
+{
+ /* Check if entry is not attached. */
+ if (!ent->next.le_prev)
+ return;
+ LIST_REMOVE(ent, next);
+}
+
/**
* Return nearest power of two above input value.
*
--
1.8.3.1
