[dpdk-dev] [PATCH 17/20] net/mlx5: add simple hash table

[Viacheslav Ovsiienko <viacheslavo@mellanox.com>]

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 <yskoh@mellanox.com>
Signed-off-by: Viacheslav Ovsiienko <viacheslavo@mellanox.com>
Acked-by: Matan Azrad <matan@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