Add doubly linked count list implementation

We have various requirements when using a dlist_head to keep track of the
number of items in the list.  This, traditionally, has been done by
maintaining a counter variable in the calling code.  Here we tidy this up
by adding "dclist", which is very similar to dlist but also keeps track of
the number of items stored in the list.

Callers may use the new dclist_count() function when they need to know how
many items are stored. Obtaining the count is an O(1) operation.

For simplicity reasons, dclist and dlist both use dlist_node as their node
type and dlist_iter/dlist_mutable_iter as their iterator type. dclists
have all of the same functionality as dlists except there is no function
named dclist_delete().  To remove an item from a list dclist_delete_from()
must be used.  This requires knowing which dclist the given item is stored
in.

Additionally, here we also convert some dlists where additional code
exists to keep track of the number of items stored and to make these use
dclists instead.

Author: David Rowley
Reviewed-by: Bharath Rupireddy, Aleksander Alekseev
Discussion: https://postgr.es/m/CAApHDvrtVxr+FXEX0VbViCFKDGxA3tWDgw9oFewNXCJMmwLjLg@mail.gmail.com

7 files changed, 81 insertions, 91 deletions

diff --git a/src/backend/access/heap/rewriteheap.c b/src/backend/access/heap/rewriteheap.c
index b01b39b008c..a34e9b352dc 100644
--- a/src/backend/access/heap/rewriteheap.c
+++ b/src/backend/access/heap/rewriteheap.c
@@ -196,8 +196,7 @@ typedef struct RewriteMappingFile
 	TransactionId xid;			/* xid that might need to see the row */
 	int			vfd;			/* fd of mappings file */
 	off_t		off;			/* how far have we written yet */
-	uint32		num_mappings;	/* number of in-memory mappings */
-	dlist_head	mappings;		/* list of in-memory mappings */
+	dclist_head mappings;		/* list of in-memory mappings */
 	char		path[MAXPGPATH];	/* path, for error messages */
 } RewriteMappingFile;
 
@@ -864,9 +863,10 @@ logical_heap_rewrite_flush_mappings(RewriteState state)
 		Oid			dboid;
 		uint32		len;
 		int			written;
+		uint32		num_mappings = dclist_count(&src->mappings);
 
 		/* this file hasn't got any new mappings */
-		if (src->num_mappings == 0)
+		if (num_mappings == 0)
 			continue;
 
 		if (state->rs_old_rel->rd_rel->relisshared)
@@ -874,7 +874,7 @@ logical_heap_rewrite_flush_mappings(RewriteState state)
 		else
 			dboid = MyDatabaseId;
 
-		xlrec.num_mappings = src->num_mappings;
+		xlrec.num_mappings = num_mappings;
 		xlrec.mapped_rel = RelationGetRelid(state->rs_old_rel);
 		xlrec.mapped_xid = src->xid;
 		xlrec.mapped_db = dboid;
@@ -882,31 +882,30 @@ logical_heap_rewrite_flush_mappings(RewriteState state)
 		xlrec.start_lsn = state->rs_begin_lsn;
 
 		/* write all mappings consecutively */
-		len = src->num_mappings * sizeof(LogicalRewriteMappingData);
+		len = num_mappings * sizeof(LogicalRewriteMappingData);
 		waldata_start = waldata = palloc(len);
 
 		/*
 		 * collect data we need to write out, but don't modify ondisk data yet
 		 */
-		dlist_foreach_modify(iter, &src->mappings)
+		dclist_foreach_modify(iter, &src->mappings)
 		{
 			RewriteMappingDataEntry *pmap;
 
-			pmap = dlist_container(RewriteMappingDataEntry, node, iter.cur);
+			pmap = dclist_container(RewriteMappingDataEntry, node, iter.cur);
 
 			memcpy(waldata, &pmap->map, sizeof(pmap->map));
 			waldata += sizeof(pmap->map);
 
 			/* remove from the list and free */
-			dlist_delete(&pmap->node);
+			dclist_delete_from(&src->mappings, &pmap->node);
 			pfree(pmap);
 
 			/* update bookkeeping */
 			state->rs_num_rewrite_mappings--;
-			src->num_mappings--;
 		}
 
-		Assert(src->num_mappings == 0);
+		Assert(dclist_count(&src->mappings) == 0);
 		Assert(waldata == waldata_start + len);
 
 		/*
@@ -1002,8 +1001,7 @@ logical_rewrite_log_mapping(RewriteState state, TransactionId xid,
 				 LSN_FORMAT_ARGS(state->rs_begin_lsn),
 				 xid, GetCurrentTransactionId());
 
-		dlist_init(&src->mappings);
-		src->num_mappings = 0;
+		dclist_init(&src->mappings);
 		src->off = 0;
 		memcpy(src->path, path, sizeof(path));
 		src->vfd = PathNameOpenFile(path,
@@ -1017,8 +1015,7 @@ logical_rewrite_log_mapping(RewriteState state, TransactionId xid,
 	pmap = MemoryContextAlloc(state->rs_cxt,
 							  sizeof(RewriteMappingDataEntry));
 	memcpy(&pmap->map, map, sizeof(LogicalRewriteMappingData));
-	dlist_push_tail(&src->mappings, &pmap->node);
-	src->num_mappings++;
+	dclist_push_tail(&src->mappings, &pmap->node);
 	state->rs_num_rewrite_mappings++;
 
 	/*
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 5eff87665be..204aa950456 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -319,8 +319,7 @@ typedef struct mXactCacheEnt
 } mXactCacheEnt;
 
 #define MAX_CACHE_ENTRIES	256
-static dlist_head MXactCache = DLIST_STATIC_INIT(MXactCache);
-static int	MXactCacheMembers = 0;
+static dclist_head MXactCache = DCLIST_STATIC_INIT(MXactCache);
 static MemoryContext MXactContext = NULL;
 
 #ifdef MULTIXACT_DEBUG
@@ -1504,9 +1503,10 @@ mXactCacheGetBySet(int nmembers, MultiXactMember *members)
 	/* sort the array so comparison is easy */
 	qsort(members, nmembers, sizeof(MultiXactMember), mxactMemberComparator);
 
-	dlist_foreach(iter, &MXactCache)
+	dclist_foreach(iter, &MXactCache)
 	{
-		mXactCacheEnt *entry = dlist_container(mXactCacheEnt, node, iter.cur);
+		mXactCacheEnt *entry = dclist_container(mXactCacheEnt, node,
+												iter.cur);
 
 		if (entry->nmembers != nmembers)
 			continue;
@@ -1518,7 +1518,7 @@ mXactCacheGetBySet(int nmembers, MultiXactMember *members)
 		if (memcmp(members, entry->members, nmembers * sizeof(MultiXactMember)) == 0)
 		{
 			debug_elog3(DEBUG2, "CacheGet: found %u", entry->multi);
-			dlist_move_head(&MXactCache, iter.cur);
+			dclist_move_head(&MXactCache, iter.cur);
 			return entry->multi;
 		}
 	}
@@ -1542,9 +1542,10 @@ mXactCacheGetById(MultiXactId multi, MultiXactMember **members)
 
 	debug_elog3(DEBUG2, "CacheGet: looking for %u", multi);
 
-	dlist_foreach(iter, &MXactCache)
+	dclist_foreach(iter, &MXactCache)
 	{
-		mXactCacheEnt *entry = dlist_container(mXactCacheEnt, node, iter.cur);
+		mXactCacheEnt *entry = dclist_container(mXactCacheEnt, node,
+												iter.cur);
 
 		if (entry->multi == multi)
 		{
@@ -1566,7 +1567,7 @@ mXactCacheGetById(MultiXactId multi, MultiXactMember **members)
 			 * This is acceptable only because we exit the iteration
 			 * immediately afterwards.
 			 */
-			dlist_move_head(&MXactCache, iter.cur);
+			dclist_move_head(&MXactCache, iter.cur);
 
 			*members = ptr;
 			return entry->nmembers;
@@ -1610,16 +1611,15 @@ mXactCachePut(MultiXactId multi, int nmembers, MultiXactMember *members)
 	/* mXactCacheGetBySet assumes the entries are sorted, so sort them */
 	qsort(entry->members, nmembers, sizeof(MultiXactMember), mxactMemberComparator);
 
-	dlist_push_head(&MXactCache, &entry->node);
-	if (MXactCacheMembers++ >= MAX_CACHE_ENTRIES)
+	dclist_push_head(&MXactCache, &entry->node);
+	if (dclist_count(&MXactCache) > MAX_CACHE_ENTRIES)
 	{
 		dlist_node *node;
 
-		node = dlist_tail_node(&MXactCache);
-		dlist_delete(node);
-		MXactCacheMembers--;
+		node = dclist_tail_node(&MXactCache);
+		dclist_delete_from(&MXactCache, node);
 
-		entry = dlist_container(mXactCacheEnt, node, node);
+		entry = dclist_container(mXactCacheEnt, node, node);
 		debug_elog3(DEBUG2, "CachePut: pruning cached multi %u",
 					entry->multi);
 
@@ -1699,8 +1699,7 @@ AtEOXact_MultiXact(void)
 	 * a child of TopTransactionContext, we needn't delete it explicitly.
 	 */
 	MXactContext = NULL;
-	dlist_init(&MXactCache);
-	MXactCacheMembers = 0;
+	dclist_init(&MXactCache);
 }
 
 /*
@@ -1766,8 +1765,7 @@ PostPrepare_MultiXact(TransactionId xid)
 	 * Discard the local MultiXactId cache like in AtEOXact_MultiXact.
 	 */
 	MXactContext = NULL;
-	dlist_init(&MXactCache);
-	MXactCacheMembers = 0;
+	dclist_init(&MXactCache);
 }
 
 /*
diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c
index 29ef2162124..e8ea9811764 100644
--- a/src/backend/lib/ilist.c
+++ b/src/backend/lib/ilist.c
@@ -53,6 +53,23 @@ slist_delete(slist_head *head, slist_node *node)
 
 #ifdef ILIST_DEBUG
 /*
+ * dlist_member_check
+ *		Validate that 'node' is a member of 'head'
+ */
+void
+dlist_member_check(dlist_head *head, dlist_node *node)
+{
+	dlist_iter	iter;
+
+	dlist_foreach(iter, head)
+	{
+		if (iter.cur == node)
+			return;
+	}
+	elog(ERROR, "double linked list member check failure");
+}
+
+/*
  * Verify integrity of a doubly linked list
  */
 void
diff --git a/src/backend/replication/logical/reorderbuffer.c b/src/backend/replication/logical/reorderbuffer.c
index 20c9cd139ab..22a15a482ab 100644
--- a/src/backend/replication/logical/reorderbuffer.c
+++ b/src/backend/replication/logical/reorderbuffer.c
@@ -349,8 +349,6 @@ ReorderBufferAllocate(void)
 	buffer->by_txn_last_xid = InvalidTransactionId;
 	buffer->by_txn_last_txn = NULL;
 
-	buffer->catchange_ntxns = 0;
-
 	buffer->outbuf = NULL;
 	buffer->outbufsize = 0;
 	buffer->size = 0;
@@ -368,7 +366,7 @@ ReorderBufferAllocate(void)
 
 	dlist_init(&buffer->toplevel_by_lsn);
 	dlist_init(&buffer->txns_by_base_snapshot_lsn);
-	dlist_init(&buffer->catchange_txns);
+	dclist_init(&buffer->catchange_txns);
 
 	/*
 	 * Ensure there's no stale data from prior uses of this slot, in case some
@@ -1553,12 +1551,7 @@ ReorderBufferCleanupTXN(ReorderBuffer *rb, ReorderBufferTXN *txn)
 	 */
 	dlist_delete(&txn->node);
 	if (rbtxn_has_catalog_changes(txn))
-	{
-		dlist_delete(&txn->catchange_node);
-		rb->catchange_ntxns--;
-
-		Assert(rb->catchange_ntxns >= 0);
-	}
+		dclist_delete_from(&rb->catchange_txns, &txn->catchange_node);
 
 	/* now remove reference from buffer */
 	hash_search(rb->by_txn,
@@ -3309,8 +3302,7 @@ ReorderBufferXidSetCatalogChanges(ReorderBuffer *rb, TransactionId xid,
 	if (!rbtxn_has_catalog_changes(txn))
 	{
 		txn->txn_flags |= RBTXN_HAS_CATALOG_CHANGES;
-		dlist_push_tail(&rb->catchange_txns, &txn->catchange_node);
-		rb->catchange_ntxns++;
+		dclist_push_tail(&rb->catchange_txns, &txn->catchange_node);
 	}
 
 	/*
@@ -3323,8 +3315,7 @@ ReorderBufferXidSetCatalogChanges(ReorderBuffer *rb, TransactionId xid,
 	if (toptxn != NULL && !rbtxn_has_catalog_changes(toptxn))
 	{
 		toptxn->txn_flags |= RBTXN_HAS_CATALOG_CHANGES;
-		dlist_push_tail(&rb->catchange_txns, &toptxn->catchange_node);
-		rb->catchange_ntxns++;
+		dclist_push_tail(&rb->catchange_txns, &toptxn->catchange_node);
 	}
 }
 
@@ -3342,19 +3333,17 @@ ReorderBufferGetCatalogChangesXacts(ReorderBuffer *rb)
 	size_t		xcnt = 0;
 
 	/* Quick return if the list is empty */
-	if (rb->catchange_ntxns == 0)
-	{
-		Assert(dlist_is_empty(&rb->catchange_txns));
+	if (dclist_count(&rb->catchange_txns) == 0)
 		return NULL;
-	}
 
 	/* Initialize XID array */
-	xids = (TransactionId *) palloc(sizeof(TransactionId) * rb->catchange_ntxns);
-	dlist_foreach(iter, &rb->catchange_txns)
+	xids = (TransactionId *) palloc(sizeof(TransactionId) *
+									dclist_count(&rb->catchange_txns));
+	dclist_foreach(iter, &rb->catchange_txns)
 	{
-		ReorderBufferTXN *txn = dlist_container(ReorderBufferTXN,
-												catchange_node,
-												iter.cur);
+		ReorderBufferTXN *txn = dclist_container(ReorderBufferTXN,
+												 catchange_node,
+												 iter.cur);
 
 		Assert(rbtxn_has_catalog_changes(txn));
 
@@ -3363,7 +3352,7 @@ ReorderBufferGetCatalogChangesXacts(ReorderBuffer *rb)
 
 	qsort(xids, xcnt, sizeof(TransactionId), xidComparator);
 
-	Assert(xcnt == rb->catchange_ntxns);
+	Assert(xcnt == dclist_count(&rb->catchange_txns));
 	return xids;
 }
 
diff --git a/src/backend/replication/logical/snapbuild.c b/src/backend/replication/logical/snapbuild.c
index f892d19bfb0..5006a5c464f 100644
--- a/src/backend/replication/logical/snapbuild.c
+++ b/src/backend/replication/logical/snapbuild.c
@@ -1688,7 +1688,7 @@ SnapBuildSerialize(SnapBuild *builder, XLogRecPtr lsn)
 
 	/* Get the catalog modifying transactions that are yet not committed */
 	catchange_xip = ReorderBufferGetCatalogChangesXacts(builder->reorder);
-	catchange_xcnt = builder->reorder->catchange_ntxns;
+	catchange_xcnt = dclist_count(&builder->reorder->catchange_txns);
 
 	needed_length = sizeof(SnapBuildOnDisk) +
 		sizeof(TransactionId) * (builder->committed.xcnt + catchange_xcnt);
diff --git a/src/backend/utils/activity/pgstat_xact.c b/src/backend/utils/activity/pgstat_xact.c
index d6f660edf7b..5a3aca4aefd 100644
--- a/src/backend/utils/activity/pgstat_xact.c
+++ b/src/backend/utils/activity/pgstat_xact.c
@@ -70,16 +70,13 @@ AtEOXact_PgStat_DroppedStats(PgStat_SubXactStatus *xact_state, bool isCommit)
 	dlist_mutable_iter iter;
 	int			not_freed_count = 0;
 
-	if (xact_state->pending_drops_count == 0)
-	{
-		Assert(dlist_is_empty(&xact_state->pending_drops));
+	if (dclist_count(&xact_state->pending_drops) == 0)
 		return;
-	}
 
-	dlist_foreach_modify(iter, &xact_state->pending_drops)
+	dclist_foreach_modify(iter, &xact_state->pending_drops)
 	{
 		PgStat_PendingDroppedStatsItem *pending =
-		dlist_container(PgStat_PendingDroppedStatsItem, node, iter.cur);
+		dclist_container(PgStat_PendingDroppedStatsItem, node, iter.cur);
 		xl_xact_stats_item *it = &pending->item;
 
 		if (isCommit && !pending->is_create)
@@ -101,8 +98,7 @@ AtEOXact_PgStat_DroppedStats(PgStat_SubXactStatus *xact_state, bool isCommit)
 				not_freed_count++;
 		}
 
-		dlist_delete(&pending->node);
-		xact_state->pending_drops_count--;
+		dclist_delete_from(&xact_state->pending_drops, &pending->node);
 		pfree(pending);
 	}
 
@@ -144,19 +140,18 @@ AtEOSubXact_PgStat_DroppedStats(PgStat_SubXactStatus *xact_state,
 	dlist_mutable_iter iter;
 	int			not_freed_count = 0;
 
-	if (xact_state->pending_drops_count == 0)
+	if (dclist_count(&xact_state->pending_drops) == 0)
 		return;
 
 	parent_xact_state = pgstat_get_xact_stack_level(nestDepth - 1);
 
-	dlist_foreach_modify(iter, &xact_state->pending_drops)
+	dclist_foreach_modify(iter, &xact_state->pending_drops)
 	{
 		PgStat_PendingDroppedStatsItem *pending =
-		dlist_container(PgStat_PendingDroppedStatsItem, node, iter.cur);
+		dclist_container(PgStat_PendingDroppedStatsItem, node, iter.cur);
 		xl_xact_stats_item *it = &pending->item;
 
-		dlist_delete(&pending->node);
-		xact_state->pending_drops_count--;
+		dclist_delete_from(&xact_state->pending_drops, &pending->node);
 
 		if (!isCommit && pending->is_create)
 		{
@@ -175,8 +170,7 @@ AtEOSubXact_PgStat_DroppedStats(PgStat_SubXactStatus *xact_state,
 			 * remove the stats object, the surrounding transaction might
 			 * still abort. Pass it on to the parent.
 			 */
-			dlist_push_tail(&parent_xact_state->pending_drops, &pending->node);
-			parent_xact_state->pending_drops_count++;
+			dclist_push_tail(&parent_xact_state->pending_drops, &pending->node);
 		}
 		else
 		{
@@ -184,7 +178,7 @@ AtEOSubXact_PgStat_DroppedStats(PgStat_SubXactStatus *xact_state,
 		}
 	}
 
-	Assert(xact_state->pending_drops_count == 0);
+	Assert(dclist_count(&xact_state->pending_drops) == 0);
 	if (not_freed_count > 0)
 		pgstat_request_entry_refs_gc();
 }
@@ -250,8 +244,7 @@ pgstat_get_xact_stack_level(int nest_level)
 		xact_state = (PgStat_SubXactStatus *)
 			MemoryContextAlloc(TopTransactionContext,
 							   sizeof(PgStat_SubXactStatus));
-		dlist_init(&xact_state->pending_drops);
-		xact_state->pending_drops_count = 0;
+		dclist_init(&xact_state->pending_drops);
 		xact_state->nest_level = nest_level;
 		xact_state->prev = pgStatXactStack;
 		xact_state->first = NULL;
@@ -291,20 +284,20 @@ pgstat_get_transactional_drops(bool isCommit, xl_xact_stats_item **items)
 	Assert(!isCommit || xact_state->nest_level == 1);
 	Assert(!isCommit || xact_state->prev == NULL);
 
-	*items = palloc(xact_state->pending_drops_count
+	*items = palloc(dclist_count(&xact_state->pending_drops)
 					* sizeof(xl_xact_stats_item));
 
-	dlist_foreach(iter, &xact_state->pending_drops)
+	dclist_foreach(iter, &xact_state->pending_drops)
 	{
 		PgStat_PendingDroppedStatsItem *pending =
-		dlist_container(PgStat_PendingDroppedStatsItem, node, iter.cur);
+		dclist_container(PgStat_PendingDroppedStatsItem, node, iter.cur);
 
 		if (isCommit && pending->is_create)
 			continue;
 		if (!isCommit && !pending->is_create)
 			continue;
 
-		Assert(nitems < xact_state->pending_drops_count);
+		Assert(nitems < dclist_count(&xact_state->pending_drops));
 		(*items)[nitems++] = pending->item;
 	}
 
@@ -351,8 +344,7 @@ create_drop_transactional_internal(PgStat_Kind kind, Oid dboid, Oid objoid, bool
 	drop->item.dboid = dboid;
 	drop->item.objoid = objoid;
 
-	dlist_push_tail(&xact_state->pending_drops, &drop->node);
-	xact_state->pending_drops_count++;
+	dclist_push_tail(&xact_state->pending_drops, &drop->node);
 }
 
 /*
diff --git a/src/backend/utils/adt/ri_triggers.c b/src/backend/utils/adt/ri_triggers.c
index 1d503e7e011..61c2eecacaa 100644
--- a/src/backend/utils/adt/ri_triggers.c
+++ b/src/backend/utils/adt/ri_triggers.c
@@ -176,8 +176,7 @@ typedef struct RI_CompareHashEntry
 static HTAB *ri_constraint_cache = NULL;
 static HTAB *ri_query_cache = NULL;
 static HTAB *ri_compare_cache = NULL;
-static dlist_head ri_constraint_cache_valid_list;
-static int	ri_constraint_cache_valid_count = 0;
+static dclist_head ri_constraint_cache_valid_list;
 
 
 /*
@@ -2172,10 +2171,9 @@ ri_LoadConstraintInfo(Oid constraintOid)
 
 	/*
 	 * For efficient processing of invalidation messages below, we keep a
-	 * doubly-linked list, and a count, of all currently valid entries.
+	 * doubly-linked count list of all currently valid entries.
 	 */
-	dlist_push_tail(&ri_constraint_cache_valid_list, &riinfo->valid_link);
-	ri_constraint_cache_valid_count++;
+	dclist_push_tail(&ri_constraint_cache_valid_list, &riinfo->valid_link);
 
 	riinfo->valid = true;
 
@@ -2233,13 +2231,13 @@ InvalidateConstraintCacheCallBack(Datum arg, int cacheid, uint32 hashvalue)
 	 * O(N^2) behavior in situations where a session touches many foreign keys
 	 * and also does many ALTER TABLEs, such as a restore from pg_dump.
 	 */
-	if (ri_constraint_cache_valid_count > 1000)
+	if (dclist_count(&ri_constraint_cache_valid_list) > 1000)
 		hashvalue = 0;			/* pretend it's a cache reset */
 
-	dlist_foreach_modify(iter, &ri_constraint_cache_valid_list)
+	dclist_foreach_modify(iter, &ri_constraint_cache_valid_list)
 	{
-		RI_ConstraintInfo *riinfo = dlist_container(RI_ConstraintInfo,
-													valid_link, iter.cur);
+		RI_ConstraintInfo *riinfo = dclist_container(RI_ConstraintInfo,
+													 valid_link, iter.cur);
 
 		/*
 		 * We must invalidate not only entries directly matching the given
@@ -2252,8 +2250,7 @@ InvalidateConstraintCacheCallBack(Datum arg, int cacheid, uint32 hashvalue)
 		{
 			riinfo->valid = false;
 			/* Remove invalidated entries from the list, too */
-			dlist_delete(iter.cur);
-			ri_constraint_cache_valid_count--;
+			dclist_delete_from(&ri_constraint_cache_valid_list, iter.cur);
 		}
 	}
 }