Embedded list interface

Provide a common implementation of embedded singly-linked and
doubly-linked lists.  "Embedded" in the sense that the nodes'
next/previous pointers exist within some larger struct; this design
choice reduces memory allocation overhead.

Most of the implementation uses inlineable functions (where supported),
for performance.

Some existing uses of both types of lists have been converted to the new
code, for demonstration purposes.  Other uses can (and probably will) be
converted in the future.  Since dllist.c is unused after this conversion,
it has been removed.

Author: Andres Freund
Some tweaks by me
Reviewed by Tom Lane, Peter Geoghegan

1 files changed, 0 insertions, 214 deletions

diff --git a/src/backend/lib/dllist.c b/src/backend/lib/dllist.c
deleted file mode 100644
index 52af56a0795..00000000000
--- a/src/backend/lib/dllist.c
+++ /dev/null
@@ -1,214 +0,0 @@
-/*-------------------------------------------------------------------------
- *
- * dllist.c
- *	  this is a simple doubly linked list implementation
- *	  the elements of the lists are void*
- *
- * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
- * Portions Copyright (c) 1994, Regents of the University of California
- *
- *
- * IDENTIFICATION
- *	  src/backend/lib/dllist.c
- *
- *-------------------------------------------------------------------------
- */
-#include "postgres.h"
-
-#include "lib/dllist.h"
-
-
-Dllist *
-DLNewList(void)
-{
-	Dllist	   *l;
-
-	l = (Dllist *) palloc(sizeof(Dllist));
-
-	l->dll_head = NULL;
-	l->dll_tail = NULL;
-
-	return l;
-}
-
-void
-DLInitList(Dllist *list)
-{
-	list->dll_head = NULL;
-	list->dll_tail = NULL;
-}
-
-/*
- * free up a list and all the nodes in it --- but *not* whatever the nodes
- * might point to!
- */
-void
-DLFreeList(Dllist *list)
-{
-	Dlelem	   *curr;
-
-	while ((curr = DLRemHead(list)) != NULL)
-		pfree(curr);
-
-	pfree(list);
-}
-
-Dlelem *
-DLNewElem(void *val)
-{
-	Dlelem	   *e;
-
-	e = (Dlelem *) palloc(sizeof(Dlelem));
-
-	e->dle_next = NULL;
-	e->dle_prev = NULL;
-	e->dle_val = val;
-	e->dle_list = NULL;
-	return e;
-}
-
-void
-DLInitElem(Dlelem *e, void *val)
-{
-	e->dle_next = NULL;
-	e->dle_prev = NULL;
-	e->dle_val = val;
-	e->dle_list = NULL;
-}
-
-void
-DLFreeElem(Dlelem *e)
-{
-	pfree(e);
-}
-
-void
-DLRemove(Dlelem *e)
-{
-	Dllist	   *l = e->dle_list;
-
-	if (e->dle_prev)
-		e->dle_prev->dle_next = e->dle_next;
-	else
-	{
-		/* must be the head element */
-		Assert(e == l->dll_head);
-		l->dll_head = e->dle_next;
-	}
-	if (e->dle_next)
-		e->dle_next->dle_prev = e->dle_prev;
-	else
-	{
-		/* must be the tail element */
-		Assert(e == l->dll_tail);
-		l->dll_tail = e->dle_prev;
-	}
-
-	e->dle_next = NULL;
-	e->dle_prev = NULL;
-	e->dle_list = NULL;
-}
-
-void
-DLAddHead(Dllist *l, Dlelem *e)
-{
-	e->dle_list = l;
-
-	if (l->dll_head)
-		l->dll_head->dle_prev = e;
-	e->dle_next = l->dll_head;
-	e->dle_prev = NULL;
-	l->dll_head = e;
-
-	if (l->dll_tail == NULL)	/* if this is first element added */
-		l->dll_tail = e;
-}
-
-void
-DLAddTail(Dllist *l, Dlelem *e)
-{
-	e->dle_list = l;
-
-	if (l->dll_tail)
-		l->dll_tail->dle_next = e;
-	e->dle_prev = l->dll_tail;
-	e->dle_next = NULL;
-	l->dll_tail = e;
-
-	if (l->dll_head == NULL)	/* if this is first element added */
-		l->dll_head = e;
-}
-
-Dlelem *
-DLRemHead(Dllist *l)
-{
-	/* remove and return the head */
-	Dlelem	   *result = l->dll_head;
-
-	if (result == NULL)
-		return result;
-
-	if (result->dle_next)
-		result->dle_next->dle_prev = NULL;
-
-	l->dll_head = result->dle_next;
-
-	if (result == l->dll_tail)	/* if the head is also the tail */
-		l->dll_tail = NULL;
-
-	result->dle_next = NULL;
-	result->dle_list = NULL;
-
-	return result;
-}
-
-Dlelem *
-DLRemTail(Dllist *l)
-{
-	/* remove and return the tail */
-	Dlelem	   *result = l->dll_tail;
-
-	if (result == NULL)
-		return result;
-
-	if (result->dle_prev)
-		result->dle_prev->dle_next = NULL;
-
-	l->dll_tail = result->dle_prev;
-
-	if (result == l->dll_head)	/* if the tail is also the head */
-		l->dll_head = NULL;
-
-	result->dle_prev = NULL;
-	result->dle_list = NULL;
-
-	return result;
-}
-
-/* Same as DLRemove followed by DLAddHead, but faster */
-void
-DLMoveToFront(Dlelem *e)
-{
-	Dllist	   *l = e->dle_list;
-
-	if (l->dll_head == e)
-		return;					/* Fast path if already at front */
-
-	Assert(e->dle_prev != NULL);	/* since it's not the head */
-	e->dle_prev->dle_next = e->dle_next;
-
-	if (e->dle_next)
-		e->dle_next->dle_prev = e->dle_prev;
-	else
-	{
-		/* must be the tail element */
-		Assert(e == l->dll_tail);
-		l->dll_tail = e->dle_prev;
-	}
-
-	l->dll_head->dle_prev = e;
-	e->dle_next = l->dll_head;
-	e->dle_prev = NULL;
-	l->dll_head = e;
-	/* We need not check dll_tail, since there must have been > 1 entry */
-}