X-Git-Url: https://tinc-vpn.org/git/browse?a=blobdiff_plain;f=src%2Fhash.h;h=531c6639827a512f639f94fb918c56326cdbf5f3;hb=7be02138580c6821145405fd55def976dfde4998;hp=e4b149957050b2d015de73d3bdfd9f4c2ade4db1;hpb=f6e87ab476a0faf8b124ecaaa27f967d825e6457;p=tinc

diff --git a/src/hash.h b/src/hash.h
index e4b14995..531c6639 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -3,7 +3,7 @@
 
 /*
     hash.h -- header file for hash.c
-    Copyright (C) 2012 Guus Sliepen <guus@tinc-vpn.org>
+    Copyright (C) 2012-2022 Guus Sliepen <guus@tinc-vpn.org>
 
     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
@@ -20,23 +20,66 @@
     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
-typedef struct hash_t {
-	size_t n;
-	size_t size;
-	char *keys;
-	const void **values;
-} hash_t;
 
-extern hash_t *hash_alloc(size_t n, size_t size) __attribute__((__malloc__));
-extern void hash_free(hash_t *);
+/* Map 32 bits int onto 0..n-1, without throwing away too many bits if n is 2^8 or 2^16 */
 
-extern void hash_insert(hash_t *, const void *key, const void *value);
-extern void hash_delete(hash_t *, const void *key);
+uint32_t modulo(uint32_t hash, size_t n);
 
-extern void *hash_search(const hash_t *, const void *key);
-extern void *hash_search_or_insert(hash_t *, const void *key, const void *value);
+#define HASH_SEARCH_ITERATIONS 4
 
-extern void hash_clear(hash_t *);
-extern void hash_resize(hash_t *, size_t n);
+#define hash_insert(t, ...) hash_insert_ ## t (__VA_ARGS__)
+#define hash_delete(t, ...) hash_delete_ ## t (__VA_ARGS__)
+#define hash_search(t, ...) hash_search_ ## t (__VA_ARGS__)
+#define hash_clear(t, n) hash_clear_ ## t ((n))
+
+#define hash_define(t, n) \
+	typedef struct hash_ ## t { \
+		t keys[n]; \
+		const void *values[n]; \
+	} hash_ ## t; \
+	static inline uint32_t hash_modulo_ ## t(uint32_t hash) { \
+		return hash & (n - 1); \
+	} \
+	static inline void hash_insert_ ## t (hash_ ##t *hash, const t *key, const void *value) { \
+		uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \
+		for(uint8_t f=0; f< (HASH_SEARCH_ITERATIONS - 1); f++){ \
+			if(hash->values[i] == NULL || !memcmp(key, &hash->keys[i], sizeof(t))) { \
+				memcpy(&hash->keys[i], key, sizeof(t)); \
+				hash->values[i] = value; \
+				return; \
+			} \
+			if(++i == n) i = 0; \
+		} \
+		/* We always pick the last slot. It's unfair. But thats life */ \
+		memcpy(&hash->keys[i], key, sizeof(t)); \
+		hash->values[i] = value; \
+	} \
+	static inline void *hash_search_ ## t (const hash_ ##t *hash, const t *key) { \
+		uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \
+		for(uint8_t f=0; f<HASH_SEARCH_ITERATIONS; f++){ \
+			if(!memcmp(key, &hash->keys[i], sizeof(t))) { \
+				return (void *)hash->values[i]; \
+			} \
+			if(++i == n) i = 0; \
+		} \
+		return NULL; \
+	} \
+	static inline void hash_delete_ ## t (hash_ ##t *hash, const t *key) { \
+		uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \
+		for(uint8_t f=0; f<HASH_SEARCH_ITERATIONS; f++){ \
+			if(!memcmp(key, &hash->keys[i], sizeof(t))) { \
+				hash->values[i] = NULL; \
+				return; \
+			} \
+			if(++i == n) i = 0; \
+		} \
+	} \
+	static inline void hash_clear_ ## t(hash_ ##t *hash) { \
+		memset(hash->values, 0, n * sizeof(*hash->values)); \
+		memset(hash->keys, 0, n * sizeof(*hash->keys)); \
+	}
+
+
+#define hash_new(t, name) static hash_ ## t name
 
 #endif