[17/20] net/mlx5: add simple hash table
Checks
Commit Message
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(-)
@@ -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.
*