Igt-dev Archive on lore.kernel.org
 help / color / mirror / Atom feed
* [igt-dev] [PATCH i-g-t 1/3] lib/igt_map: Add 32-bit and 64-bit hash helper functions
@ 2023-02-23 10:53 Zbigniew Kempczyński
  2023-02-23 10:53 ` [igt-dev] [PATCH i-g-t 2/3] lib/intel_allocator_*: Use common hash helpers Zbigniew Kempczyński
                   ` (4 more replies)
  0 siblings, 5 replies; 9+ messages in thread
From: Zbigniew Kempczyński @ 2023-02-23 10:53 UTC (permalink / raw)
  To: igt-dev

Creating igt_map requires hashing and comparing function. Common case
is using 32-bit (like fd, etc.) or 64-bit keys (offsets) so adding
such helpers reduces code duplication.

Signed-off-by: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
---
 lib/igt_map.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/igt_map.h |  5 +++++
 2 files changed, 64 insertions(+)

diff --git a/lib/igt_map.c b/lib/igt_map.c
index da8713a186..ffa1e6beaa 100644
--- a/lib/igt_map.c
+++ b/lib/igt_map.c
@@ -196,6 +196,7 @@ igt_map_search(struct igt_map *map, const void *key)
  * Returns: map entry or %NULL if no entry is found.
  * Note that the data pointer may be modified by the user.
  */
+
 struct igt_map_entry *
 igt_map_search_entry(struct igt_map *map, const void *key)
 {
@@ -500,3 +501,61 @@ igt_map_random_entry(struct igt_map *map,
 
 	return NULL;
 }
+
+#define GOLDEN_RATIO_PRIME_32 0x9e370001UL
+/**
+ * igt_map_hash_32:
+ * @key: pointer to 32-bit key
+ *
+ * Function is hashing function for 32-bit keys. Key is pointer to 32-bit
+ * value so it must be dereferenced.
+ */
+uint32_t igt_map_hash_32(const void *key)
+{
+	uint32_t hash = *(uint32_t *)key;
+
+	hash = hash * GOLDEN_RATIO_PRIME_32;
+	return hash;
+}
+
+/**
+ * igt_map_equal_32:
+ * @key1: pointer to first 32-bit key
+ * @key2: pointer to second 32-bit key
+ *
+ * Function compares 32-bit keys.
+ */
+int igt_map_equal_32(const void *key1, const void *key2)
+{
+	return *(uint32_t *)key1 == *(uint32_t *)key2;
+}
+
+/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
+#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
+/**
+ * igt_map_hash_64:
+ * @key: pointer to 64-bit key
+ *
+ * Function is hashing function for 64-bit keys. Key is pointer to 64-bit
+ * value so it must be dereferenced.
+ */
+uint32_t igt_map_hash_64(const void *key)
+{
+	uint64_t hash = *(uint64_t *)key;
+
+	hash = hash * GOLDEN_RATIO_PRIME_64;
+	/* High bits are more random, so use them. */
+	return hash >> 32;
+}
+
+/**
+ * igt_map_equal_64:
+ * @key1: pointer to first 64-bit key
+ * @key2: pointer to second 64-bit key
+ *
+ * Function compares 64-bit keys.
+ */
+int igt_map_equal_64(const void *key1, const void *key2)
+{
+	return *(uint64_t *)key1 == *(uint64_t *)key2;
+}
diff --git a/lib/igt_map.h b/lib/igt_map.h
index cadcd6e35f..a0fbd1419f 100644
--- a/lib/igt_map.h
+++ b/lib/igt_map.h
@@ -171,4 +171,9 @@ igt_map_insert_pre_hashed(struct igt_map *map,
 			     uint32_t hash,
 			     const void *key, void *data);
 
+uint32_t igt_map_hash_32(const void *key);
+int igt_map_equal_32(const void *key1, const void *key2);
+uint32_t igt_map_hash_64(const void *key);
+int igt_map_equal_64(const void *key1, const void *key2);
+
 #endif
-- 
2.34.1

^ permalink raw reply related	[flat|nested] 9+ messages in thread
end of thread, other threads:[~2023-02-23 17:09 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-02-23 10:53 [igt-dev] [PATCH i-g-t 1/3] lib/igt_map: Add 32-bit and 64-bit hash helper functions Zbigniew Kempczyński
2023-02-23 10:53 ` [igt-dev] [PATCH i-g-t 2/3] lib/intel_allocator_*: Use common hash helpers Zbigniew Kempczyński
2023-02-23 11:26   ` Mauro Carvalho Chehab
2023-02-23 10:53 ` [igt-dev] [PATCH i-g-t 3/3] lib/i915/gem_create: Use hash helper for gem bo pool Zbigniew Kempczyński
2023-02-23 11:26   ` Mauro Carvalho Chehab
2023-02-23 11:26 ` [igt-dev] [PATCH i-g-t 1/3] lib/igt_map: Add 32-bit and 64-bit hash helper functions Mauro Carvalho Chehab
2023-02-23 12:28 ` [igt-dev] ✓ Fi.CI.BAT: success for series starting with [i-g-t,1/3] " Patchwork
2023-02-23 15:15 ` [igt-dev] ✗ Fi.CI.IGT: failure " Patchwork
2023-02-23 17:07   ` Zbigniew Kempczyński

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox