v5-0002-Allow-users-of-simplehash.h-to-perform-direct-del.patch

From 8e5c88965df0953b0233ace87fdbc67cc6c211c1 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Thu, 2 Jul 2020 19:07:34 +1200
Subject: [PATCH v5 2/3] Allow users of simplehash.h to perform direct
 deletions

Previously simplehash.h only exposed a method to perform a hash table
delete by the key.  This required performing a hash table lookup in order
to find the element which belongs to that key.  Having the code this way
made sense for the existing callers, but in an up-coming commit, a caller
already has the element which it would like to delete, so can do so
without performing a lookup.
---
 src/include/lib/simplehash.h | 116 +++++++++++++++++++----------------
 1 file changed, 62 insertions(+), 54 deletions(-)

diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index 90dfa8a695..8c74c467ac 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -79,6 +79,7 @@
 #define SH_RESET SH_MAKE_NAME(reset)
 #define SH_INSERT SH_MAKE_NAME(insert)
 #define SH_INSERT_HASH SH_MAKE_NAME(insert_hash)
+#define SH_DELETE_ITEM SH_MAKE_NAME(delete_item)
 #define SH_DELETE SH_MAKE_NAME(delete)
 #define SH_LOOKUP SH_MAKE_NAME(lookup)
 #define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash)
@@ -163,6 +164,7 @@ SH_SCOPE	SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
 SH_SCOPE	SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key);
 SH_SCOPE	SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
 											uint32 hash);
+SH_SCOPE void SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry);
 SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key);
 SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
 SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at);
@@ -763,75 +765,81 @@ SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
 }
 
 /*
- * Delete entry from hash table.  Returns whether to-be-deleted key was
- * present.
+ * Delete 'entry' from hash table.
  */
-SH_SCOPE bool
-SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
+SH_SCOPE void
+SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 {
-	uint32		hash = SH_HASH_KEY(tb, key);
-	uint32		startelem = SH_INITIAL_BUCKET(tb, hash);
-	uint32		curelem = startelem;
-
-	while (true)
-	{
-		SH_ELEMENT_TYPE *entry = &tb->data[curelem];
-
-		if (entry->status == SH_STATUS_EMPTY)
-			return false;
+	SH_ELEMENT_TYPE *lastentry = entry;
+	uint32		curelem;
+	uint32		startelem;
 
-		if (entry->status == SH_STATUS_IN_USE &&
-			SH_COMPARE_KEYS(tb, hash, key, entry))
-		{
-			SH_ELEMENT_TYPE *lastentry = entry;
+	Assert(entry >= &tb->data[0] && entry < &tb->data[tb->size]);
 
-			tb->members--;
+	/* Calculate the index of 'entry' */
+	startelem = curelem = entry - &tb->data[0];
 
-			/*
-			 * Backward shift following elements till either an empty element
-			 * or an element at its optimal position is encountered.
-			 *
-			 * While that sounds expensive, the average chain length is short,
-			 * and deletions would otherwise require tombstones.
-			 */
-			while (true)
-			{
-				SH_ELEMENT_TYPE *curentry;
-				uint32		curhash;
-				uint32		curoptimal;
+	tb->members--;
 
-				curelem = SH_NEXT(tb, curelem, startelem);
-				curentry = &tb->data[curelem];
+	/*
+	 * Backward shift following elements till either an empty element
+	 * or an element at its optimal position is encountered.
+	 *
+	 * While that sounds expensive, the average chain length is short,
+	 * and deletions would otherwise require tombstones.
+	 */
+	while (true)
+	{
+		SH_ELEMENT_TYPE *curentry;
+		uint32		curhash;
+		uint32		curoptimal;
 
-				if (curentry->status != SH_STATUS_IN_USE)
-				{
-					lastentry->status = SH_STATUS_EMPTY;
-					break;
-				}
+		curelem = SH_NEXT(tb, curelem, startelem);
+		curentry = &tb->data[curelem];
 
-				curhash = SH_ENTRY_HASH(tb, curentry);
-				curoptimal = SH_INITIAL_BUCKET(tb, curhash);
+		if (curentry->status != SH_STATUS_IN_USE)
+		{
+			lastentry->status = SH_STATUS_EMPTY;
+			break;
+		}
 
-				/* current is at optimal position, done */
-				if (curoptimal == curelem)
-				{
-					lastentry->status = SH_STATUS_EMPTY;
-					break;
-				}
+		curhash = SH_ENTRY_HASH(tb, curentry);
+		curoptimal = SH_INITIAL_BUCKET(tb, curhash);
 
-				/* shift */
-				memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));
+		/* current is at optimal position, done */
+		if (curoptimal == curelem)
+		{
+			lastentry->status = SH_STATUS_EMPTY;
+			break;
+		}
 
-				lastentry = curentry;
-			}
+		/* shift */
+		memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));
 
-			return true;
-		}
+		lastentry = curentry;
+	}
+}
 
-		/* TODO: return false; if distance too big */
+/*
+ * Perform hash table lookup on 'key', delete the entry belonging to it and
+ * return true.  Returns false if no item could be found relating to 'key'.
+ */
+SH_SCOPE bool
+SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
+{
+	SH_ELEMENT_TYPE *entry = SH_LOOKUP(tb, key);
 
-		curelem = SH_NEXT(tb, curelem, startelem);
+	if (likely(entry != NULL))
+	{
+		/*
+		 * Perform deletion and also the relocation of subsequent items which
+		 * are not in their optimal position but can now be moved up.
+		 */
+		SH_DELETE_ITEM(tb, entry);
+		return true;
 	}
+
+	return false;		/* Can't find 'key' */
 }
 
 /*
-- 
2.25.1