v13-0003-Support-intrusive-status-flag-in-simplehash.patch

From 3bbaf8d558e1e405217e17d1a502ff68556b21e3 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Sat, 27 Mar 2021 09:04:56 +1300
Subject: [PATCH v13 3/5] Support intrusive status flag in simplehash.

Before, you had to include a "status" member in the element type, which
simplehash.h could use to detect free space.  Allow the user to specify
a special key value to use instead, for more compact representation.
---
 src/include/lib/simplehash.h | 66 ++++++++++++++++++++++++++----------
 1 file changed, 48 insertions(+), 18 deletions(-)

diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index 32d3fa58fe..05c7ca8a47 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -131,6 +131,8 @@
 #define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash)
 #define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal)
 #define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal)
+#define SH_ENTRY_IS_EMPTY SH_MAKE_NAME(entry_is_empty)
+#define SH_SET_ENTRY_EMPTY SH_MAKE_NAME(set_entry_empty)
 
 /* generate forward declarations necessary to use the hash table */
 #ifdef SH_DECLARE
@@ -172,11 +174,13 @@ typedef struct SH_TYPE
 #endif
 }			SH_TYPE;
 
+#ifndef SH_IS_EMPTY_KEY
 typedef enum SH_STATUS
 {
 	SH_STATUS_EMPTY = 0x00,
 	SH_STATUS_IN_USE = 0x01
 } SH_STATUS;
+#endif
 
 typedef struct SH_ITERATOR
 {
@@ -309,6 +313,26 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb);
 
 #endif
 
+static inline bool
+SH_ENTRY_IS_EMPTY(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
+{
+#ifdef SH_IS_EMPTY_KEY
+	return SH_IS_EMPTY_KEY(tb, entry->SH_KEY);
+#else
+	return entry->status == SH_STATUS_EMPTY;
+#endif
+}
+
+static inline void
+SH_SET_ENTRY_EMPTY(SH_TYPE * tb, SH_ELEMENT_TYPE *entry)
+{
+#ifdef SH_EMPTY_KEY
+	entry->SH_KEY = SH_EMPTY_KEY(tb);
+#else
+	entry->status = SH_STATUS_EMPTY;
+#endif
+}
+
 /*
  * Compute sizing parameters for hashtable. Called when creating and growing
  * the hashtable.
@@ -483,7 +507,7 @@ SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data)
 	SH_COMPUTE_PARAMETERS(tb, size);
 
 #if defined(SH_IN_PLACE)
-	memset(&tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size);
+	SH_RESET(tb);
 #else
 	tb->data = SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size);
 	return tb;
@@ -504,7 +528,12 @@ SH_DESTROY(SH_TYPE * tb)
 SH_SCOPE void
 SH_RESET(SH_TYPE * tb)
 {
+#ifdef SH_EMPTY_KEY
+	for (size_t i = 0; i < tb->size; ++i)
+		tb->data[i].SH_KEY = SH_EMPTY_KEY(tb);
+#else
 	memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size);
+#endif
 	tb->members = 0;
 }
 
@@ -675,14 +704,17 @@ restart:
 		SH_ELEMENT_TYPE *entry = &data[curelem];
 
 		/* any empty bucket can directly be used */
-		if (entry->status == SH_STATUS_EMPTY)
+		if (SH_ENTRY_IS_EMPTY(tb, entry))
 		{
 			tb->members++;
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
 			SH_GET_HASH(tb, entry) = hash;
 #endif
+#ifndef SH_IS_EMPTY_KEY
 			entry->status = SH_STATUS_IN_USE;
+#endif
+			Assert(!SH_ENTRY_IS_EMPTY(tb, entry));
 			*found = false;
 			return entry;
 		}
@@ -697,7 +729,7 @@ restart:
 
 		if (SH_COMPARE_KEYS(tb, hash, key, entry))
 		{
-			Assert(entry->status == SH_STATUS_IN_USE);
+			Assert(!SH_ENTRY_IS_EMPTY(tb, entry));
 			*found = true;
 			return entry;
 		}
@@ -721,7 +753,7 @@ restart:
 				emptyelem = SH_NEXT(tb, emptyelem, startelem);
 				emptyentry = &data[emptyelem];
 
-				if (emptyentry->status == SH_STATUS_EMPTY)
+				if (SH_ENTRY_IS_EMPTY(tb, emptyentry))
 				{
 					lastentry = emptyentry;
 					break;
@@ -770,7 +802,10 @@ restart:
 #ifdef SH_STORE_HASH
 			SH_GET_HASH(tb, entry) = hash;
 #endif
+#ifndef SH_IS_EMPTY_KEY
 			entry->status = SH_STATUS_IN_USE;
+#endif
+			Assert(!SH_ENTRY_IS_EMPTY(tb, entry));
 			*found = false;
 			return entry;
 		}
@@ -833,12 +868,8 @@ SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
 	{
 		SH_ELEMENT_TYPE *entry = &tb->data[curelem];
 
-		if (entry->status == SH_STATUS_EMPTY)
-		{
+		if (SH_ENTRY_IS_EMPTY(tb, entry))
 			return NULL;
-		}
-
-		Assert(entry->status == SH_STATUS_IN_USE);
 
 		if (SH_COMPARE_KEYS(tb, hash, key, entry))
 			return entry;
@@ -891,11 +922,10 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 	{
 		SH_ELEMENT_TYPE *entry = &tb->data[curelem];
 
-		if (entry->status == SH_STATUS_EMPTY)
+		if (SH_ENTRY_IS_EMPTY(tb, entry))
 			return false;
 
-		if (entry->status == SH_STATUS_IN_USE &&
-			SH_COMPARE_KEYS(tb, hash, key, entry))
+		if (SH_COMPARE_KEYS(tb, hash, key, entry))
 		{
 			SH_ELEMENT_TYPE *lastentry = entry;
 
@@ -917,9 +947,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 				curelem = SH_NEXT(tb, curelem, startelem);
 				curentry = &tb->data[curelem];
 
-				if (curentry->status != SH_STATUS_IN_USE)
+				if (SH_ENTRY_IS_EMPTY(tb, curentry))
 				{
-					lastentry->status = SH_STATUS_EMPTY;
+					SH_SET_ENTRY_EMPTY(tb, lastentry);
 					break;
 				}
 
@@ -929,7 +959,7 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 				/* current is at optimal position, done */
 				if (curoptimal == curelem)
 				{
-					lastentry->status = SH_STATUS_EMPTY;
+					SH_SET_ENTRY_EMPTY(tb, lastentry);
 					break;
 				}
 
@@ -966,7 +996,7 @@ SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
 	{
 		SH_ELEMENT_TYPE *entry = &tb->data[i];
 
-		if (entry->status != SH_STATUS_IN_USE)
+		if (SH_ENTRY_IS_EMPTY(tb, entry))
 		{
 			startelem = i;
 			break;
@@ -1027,7 +1057,7 @@ SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
 
 		if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask))
 			iter->done = true;
-		if (elem->status == SH_STATUS_IN_USE)
+		if (!SH_ENTRY_IS_EMPTY(tb, elem))
 		{
 			return elem;
 		}
@@ -1063,7 +1093,7 @@ SH_STAT(SH_TYPE * tb)
 
 		elem = &tb->data[i];
 
-		if (elem->status != SH_STATUS_IN_USE)
+		if (SH_ENTRY_IS_EMPTY(tb, elem))
 			continue;
 
 		hash = SH_ENTRY_HASH(tb, elem);
-- 
2.30.1