[igt-dev] [PATCH i-g-t v10 02/31] lib/igt_map: Introduce igt_map

["Zbigniew Kempczyński" <zbigniew.kempczynski@intel.com>]

From: Dominik Grzegorzek <dominik.grzegorzek@intel.com>

Implementation of generic, non-thread safe, dynamic size hash map.

Signed-off-by: Dominik Grzegorzek <dominik.grzegorzek@intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
---
 .../igt-gpu-tools/igt-gpu-tools-docs.xml      |   1 +
 lib/Makefile.sources                          |   2 +
 lib/igt_map.c                                 | 150 ++++++++++++++++++
 lib/igt_map.h                                 | 121 ++++++++++++++
 lib/meson.build                               |   1 +
 5 files changed, 275 insertions(+)
 create mode 100644 lib/igt_map.c
 create mode 100644 lib/igt_map.h

diff --git a/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml b/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
index 9c9aa8f1..bf5ac542 100644
--- a/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
+++ b/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
@@ -33,6 +33,7 @@
     <xi:include href="xml/igt_kmod.xml"/>
     <xi:include href="xml/igt_kms.xml"/>
     <xi:include href="xml/igt_list.xml"/>
+    <xi:include href="xml/igt_map.xml"/>
     <xi:include href="xml/igt_pm.xml"/>
     <xi:include href="xml/igt_primes.xml"/>
     <xi:include href="xml/igt_rand.xml"/>
diff --git a/lib/Makefile.sources b/lib/Makefile.sources
index 67b38645..27019a77 100644
--- a/lib/Makefile.sources
+++ b/lib/Makefile.sources
@@ -47,6 +47,8 @@ lib_source_list =	 	\
 	igt_infoframe.h		\
 	igt_list.c		\
 	igt_list.h		\
+	igt_map.c		\
+	igt_map.h		\
 	igt_matrix.c		\
 	igt_matrix.h		\
 	igt_params.c		\
diff --git a/lib/igt_map.c b/lib/igt_map.c
new file mode 100644
index 00000000..aa330dbf
--- /dev/null
+++ b/lib/igt_map.c
@@ -0,0 +1,150 @@
+/*
+ * Copyright © 2020 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+#include <sys/ioctl.h>
+#include <stdlib.h>
+#include "igt_map.h"
+#include "igt.h"
+#include "igt_x86.h"
+
+#define MIN_CAPACITY_BITS 2
+
+static bool igt_map_filled(struct igt_map *map)
+{
+	return map->capacity_bits == 0 ||
+			(IGT_MAP_CAPACITY(map) * 4 / 5 < map->size);
+}
+
+static void igt_map_extend(struct igt_map *map)
+{
+	struct igt_hlist_head *new_heads;
+	struct igt_map_entry *pos;
+	struct igt_hlist_node *tmp;
+	uint32_t new_bits = map->capacity_bits + 1;
+	int i;
+
+	new_heads = calloc(1ULL << new_bits,
+			   sizeof(struct igt_hlist_head));
+	igt_assert(new_heads);
+
+	igt_map_for_each_safe(map, i, tmp, pos)
+		igt_hlist_add_head(&pos->link, &new_heads[map->hash_fn(pos->key, new_bits)]);
+
+	free(map->heads);
+	map->capacity_bits++;
+
+	map->heads = new_heads;
+}
+
+static bool equal_4bytes(const void *key1, const void *key2)
+{
+	const uint32_t *k1 = key1, *k2 = key2;
+	return *k1 == *k2;
+}
+
+/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
+#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL
+
+static inline uint64_t hash_64_4bytes(const void *val, unsigned int bits)
+{
+	uint64_t hash = *(uint32_t *)val;
+
+	hash = hash * GOLDEN_RATIO_PRIME_64;
+	/* High bits are more random, so use them. */
+	return hash >> (64 - bits);
+}
+
+void igt_map_init(struct igt_map *map, igt_map_equal_fn eq_fn,
+		  igt_map_hash_fn hash_fn, uint32_t initial_bits)
+{
+	map->equal_fn = eq_fn == NULL ? equal_4bytes : eq_fn;
+	map->hash_fn = hash_fn == NULL ? hash_64_4bytes : hash_fn;
+	map->capacity_bits = initial_bits > 0 ? initial_bits
+					      : MIN_CAPACITY_BITS;
+	map->heads = calloc(IGT_MAP_CAPACITY(map),
+			    sizeof(struct igt_hlist_head));
+
+	igt_assert(map->heads);
+	map->size = 0;
+}
+
+void igt_map_add(struct igt_map *map, const void *key, void *value)
+{
+	struct igt_map_entry *entry;
+
+	if (igt_map_filled(map))
+		igt_map_extend(map);
+
+	entry = calloc(1, sizeof(struct igt_map_entry));
+	entry->value = value;
+	entry->key = key;
+	igt_hlist_add_head(&entry->link,
+			   &map->heads[map->hash_fn(key, map->capacity_bits)]);
+	map->size++;
+}
+
+void *igt_map_del(struct igt_map *map, const void *key)
+{
+	struct igt_map_entry *pos;
+	struct igt_hlist_node *tmp;
+	void *val = NULL;
+
+	igt_map_for_each_possible_safe(map, pos, tmp, key) {
+		if (map->equal_fn(pos->key, key)) {
+			igt_hlist_del(&pos->link);
+			val = pos->value;
+			free(pos);
+		}
+	}
+	return val;
+}
+
+void *igt_map_find(struct igt_map *map, const void *key)
+{
+	struct igt_map_entry *pos = NULL;
+
+	igt_map_for_each_possible(map, pos, key)
+		if (pos && map->equal_fn(pos->key, key))
+			break;
+
+	return pos ? pos->value : NULL;
+}
+
+void igt_map_free(struct igt_map *map)
+{
+	struct igt_map_entry *pos;
+	struct igt_hlist_node *tmp;
+	int i;
+
+	igt_map_for_each_safe(map, i, tmp, pos) {
+		igt_hlist_del(&pos->link);
+		free(pos);
+	}
+
+	free(map->heads);
+}
+
+bool igt_map_empty(struct igt_map *map)
+{
+	return !!map->size;
+}
diff --git a/lib/igt_map.h b/lib/igt_map.h
new file mode 100644
index 00000000..5c767afa
--- /dev/null
+++ b/lib/igt_map.h
@@ -0,0 +1,121 @@
+/*
+ * Copyright © 2020 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ */
+
+#ifndef IGT_MAP_H
+#define IGT_MAP_H
+
+#include <stdint.h>
+#include "igt_list.h"
+
+/**
+ * SECTION:igt_map
+ * @short_description: a dynamic sized hashmap implementation
+ * @title: IGT Map
+ * @include: igt_map.h
+ *
+ * igt_map is a dynamic sized, non-thread-safe implementation of a hashmap.
+ * This map grows exponentially when it's over 80% filled. The structure allows
+ * indexing records by any key through the hash and equal functions.
+ * By default, hashmap compares and hashes the first four bytes of a key.
+ *
+ * Example usage:
+ *
+ * |[<!-- language="C" -->
+ * struct igt_map *map;
+ *
+ * struct record {
+ * 	int foo;
+ * 	uint32_t unique_identifier;
+ * };
+ *
+ * struct record r1, r2, *r_ptr;
+ *
+ * map = malloc(sizeof(*map));
+ * igt_map_init(map, NULL, NULL, 4); // initiaize the map with size (1 << 4)
+ * igt_map_add(map, &r1.unique_identifier, &r1);
+ * igt_map_add(map, &r2.unique_identifier, &r2);
+ *
+ * struct igt_map_entry *pos; int i;
+ * igt_map_for_each(map, i, pos) {
+ * 	r_ptr = pos->value;
+ * 	printf("key: %u, foo: %d\n", *(uint32_t*) pos->key, r_ptr->foo);
+ * }
+ *
+ * uint32_t key = r1.unique_identifier;
+ * r_ptr = igt_map_find(map, &key); // get r1
+ *
+ * r_ptr = igt_map_del(map, &r2.unique_identifier);
+ * if (r_ptr)
+ * 	printf("record with key %u deleted\n", r_ptr->unique_identifier);
+ *
+ * igt_map_free(map);
+ * free(map);
+ * ]|
+ */
+
+typedef bool (*igt_map_equal_fn)(const void *key1, const void *key2);
+typedef uint64_t (*igt_map_hash_fn)(const void *val, unsigned int bits);
+struct igt_map {
+	uint32_t size;
+	uint32_t capacity_bits;
+	igt_map_equal_fn equal_fn;
+	igt_map_hash_fn hash_fn;
+	struct igt_hlist_head *heads;
+};
+
+struct igt_map_entry {
+	const void *key;
+	void *value;
+	struct igt_hlist_node link;
+};
+
+void igt_map_init(struct igt_map *map, igt_map_equal_fn eq_fn,
+		  igt_map_hash_fn hash_fn, uint32_t initial_bits);
+void igt_map_add(struct igt_map *map, const void *key, void *value);
+void *igt_map_del(struct igt_map *map, const void *key);
+void *igt_map_find(struct igt_map *map, const void *key);
+void igt_map_free(struct igt_map *map);
+bool igt_map_empty(struct igt_map *map);
+
+#define IGT_MAP_CAPACITY(map) (1ULL << map->capacity_bits)
+
+#define igt_map_for_each_safe(map, bkt, tmp, obj) \
+	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < IGT_MAP_CAPACITY(map); \
+	(bkt)++)\
+	igt_hlist_for_each_entry_safe(obj, tmp, &map->heads[bkt], link)
+
+#define igt_map_for_each(map, bkt, obj) \
+	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < IGT_MAP_CAPACITY(map); \
+	(bkt)++)\
+	igt_hlist_for_each_entry(obj, &map->heads[bkt], link)
+
+#define igt_map_for_each_possible(map, obj, key) \
+	igt_hlist_for_each_entry(obj, \
+		&map->heads[map->hash_fn(key, map->capacity_bits)], link)
+
+#define igt_map_for_each_possible_safe(map, obj, tmp, key) \
+	igt_hlist_for_each_entry_safe(obj, tmp, \
+		&map->heads[map->hash_fn(key, map->capacity_bits)], link)
+
+#endif /* IGT_MAP_H */
diff --git a/lib/meson.build b/lib/meson.build
index 090a10cd..484d3c7b 100644
--- a/lib/meson.build
+++ b/lib/meson.build
@@ -59,6 +59,7 @@ lib_sources = [
 	'igt_core.c',
 	'igt_draw.c',
 	'igt_list.c',
+	'igt_map.c',
 	'igt_pm.c',
 	'igt_dummyload.c',
 	'uwildmat/uwildmat.c',
-- 
2.26.0

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev