From bcf9f74d1ac44f857f2601b734bdb59baa2afe2a Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Wed, 25 Jul 2012 17:10:29 -0400
Subject: [PATCH] First attempt at CHashDelete - slightly incomplete, and
 untested.

---
 src/backend/utils/hash/chash.c | 100 +++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)

diff --git a/src/backend/utils/hash/chash.c b/src/backend/utils/hash/chash.c
index dd40413694..6893a36d81 100644
--- a/src/backend/utils/hash/chash.c
+++ b/src/backend/utils/hash/chash.c
@@ -548,6 +548,106 @@ retry:
 	return !found;
 }
 
+/*
+ * Delete from a concurrent hash table.  entry need only contain the key field.
+ * Returns true if we find and delete a matching key and false otherwise.
+ */
+bool
+CHashDelete(CHashTable table, void *entry)
+{
+	uint32	hashcode = hash_any(entry, table->desc.key_size);
+	uint32	bucket = hashcode & table->bucket_mask;
+	CHashPtr	c;
+	volatile CHashPtr   *p;
+	volatile CHashNode  *n;
+	bool		found = false;
+
+	/* Suppress garbage collection for target bucket. */
+	CHashTableSuppressGC(table, bucket);
+
+	/* Scan bucket. */
+retry:
+	p = &table->bucket[bucket].head;
+	c = *p;
+	while (c != InvalidCHashPtr)
+	{
+		int		cmp;
+		uint32	h;
+
+		/* Compare current node by hashcode, then by memcmp. */
+		n = CHashTableGetNode(table, c);
+		pg_read_barrier_depends();
+		h = n->un.hashcode;
+		if (h == hashcode)
+			cmp = memcmp(CHashNodeGetItem(n), entry, table->desc.key_size);
+		else if (h > hashcode)
+			cmp = 1;
+		else
+			cmp = -1;
+
+		/* If we found the key, or passed where it should be, we're done. */
+		if (cmp >= 0)
+		{
+			found = (cmp == 0);
+			break;
+		}
+
+		/* Move to next node. */
+		p = &n->next;
+		c = *p;
+
+		/*
+		 * We can't safely update a delete-marked pointer, so remove any
+		 * such pointers we find from the bucket chain.  Sometimes, concurrent
+		 * activity may force us to restart the whole scan, but that should
+		 * be rare.
+		 */
+		if (CHashPtrIsMarked(c) && CHashRemoveMarked(table, bucket, &c, p))
+			goto retry;
+	}
+
+	if (found)
+	{
+		CHashPtr	cc;
+		bool		needs_cleanup = false;
+
+		/*
+		 * Really do the deletion.  Since we've held no lock up to this
+		 * point, it may well be that someone else has deleted the item out
+		 * from under us, so we recheck that after taking the lock.
+		 */
+		SpinLockAcquire(&table->bucket[bucket].mutex);
+		cc = n->next;
+		if (CHashPtrIsMarked(cc))
+			found = false;
+		else
+		{
+			n->next = CHashPtrMark(cc);
+			if (*p == c)
+				*p = cc;
+			else
+				needs_cleanup = true;
+		}
+		SpinLockRelease(&table->bucket[bucket].mutex);
+
+		/*
+		 * At this point the deletion is done.  However, it's possible that
+		 * we weren't able to redirect the pointer that formerly addressed the
+		 * deleted item.  If so, rescan the bucket chain and excise any deleted
+		 * items in the chain.  We don't have to worry about not finding it;
+		 * that just means someone else did the work for us.
+		 */
+		if (needs_cleanup)
+		{
+			/* XXX */
+		}
+	}
+
+	/* We're done. */
+	CHashTableUnsuppressGC();
+	return found;
+}
+
 /*
  * Allocate an arena slot for a new item to be inserted into a hash table.
  *
-- 
2.39.5