*** a/src/backend/lib/Makefile
--- b/src/backend/lib/Makefile
***************
*** 12,17 **** subdir = src/backend/lib
  top_builddir = ../../..
  include $(top_builddir)/src/Makefile.global
  
! OBJS = dllist.o stringinfo.o
  
  include $(top_srcdir)/src/backend/common.mk
--- 12,17 ----
  top_builddir = ../../..
  include $(top_builddir)/src/Makefile.global
  
! OBJS = ilist.o stringinfo.o
  
  include $(top_srcdir)/src/backend/common.mk
*** a/src/backend/lib/dllist.c
--- /dev/null
***************
*** 1,214 ****
- /*-------------------------------------------------------------------------
-  *
-  * 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 */
- }
--- 0 ----
*** /dev/null
--- b/src/backend/lib/ilist.c
***************
*** 0 ****
--- 1,109 ----
+ /*-------------------------------------------------------------------------
+  *
+  * ilist.c
+  *	  support for integrated/inline doubly- and singly- linked lists
+  *
+  * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+  * Portions Copyright (c) 1994, Regents of the University of California
+  *
+  *
+  * IDENTIFICATION
+  *	  src/backend/lib/ilist.c
+  *
+  * NOTES
+  *	  This file only contains functions that are too big to be considered
+  *	  for inlining.  See ilist.h for most of the goodies.
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ /* See ilist.h */
+ #define ILIST_INCLUDE_DEFINITIONS
+ 
+ #include "lib/ilist.h"
+ 
+ /*
+  * removes a node from a list
+  *
+  * Attention: O(n)
+  */
+ void
+ slist_delete(slist_head *head, slist_node *node)
+ {
+ 	slist_node *last = &head->head;
+ 	slist_node *cur;
+ 	bool found	PG_USED_FOR_ASSERTS_ONLY = false;
+ 
+ 	while ((cur = last->next) != NULL)
+ 	{
+ 		if (cur == node)
+ 		{
+ 			last->next = cur->next;
+ #ifdef USE_ASSERT_CHECKING
+ 			found = true;
+ #endif
+ 			break;
+ 		}
+ 		last = cur;
+ 	}
+ 
+ 	slist_check(head);
+ 	Assert(found);
+ }
+ 
+ #ifdef ILIST_DEBUG
+ /*
+  * Verify integrity of a doubly linked list
+  */
+ void
+ dlist_check(dlist_head *head)
+ {
+ 	dlist_node *cur;
+ 
+ 	if (head == NULL || !(&head->head))
+ 		elog(ERROR, "doubly linked list head is not properly initialized");
+ 
+ 	/* iterate in forward direction */
+ 	for (cur = head->head.next; cur != &head->head; cur = cur->next)
+ 	{
+ 		if (cur == NULL ||
+ 			cur->next == NULL ||
+ 			cur->prev == NULL ||
+ 			cur->prev->next != cur ||
+ 			cur->next->prev != cur)
+ 			elog(ERROR, "doubly linked list is corrupted");
+ 	}
+ 
+ 	/* iterate in backward direction */
+ 	for (cur = head->head.prev; cur != &head->head; cur = cur->prev)
+ 	{
+ 		if (cur == NULL ||
+ 			cur->next == NULL ||
+ 			cur->prev == NULL ||
+ 			cur->prev->next != cur ||
+ 			cur->next->prev != cur)
+ 			elog(ERROR, "doubly linked list is corrupted");
+ 	}
+ }
+ 
+ /*
+  * Verify integrity of a singly linked list
+  */
+ void
+ slist_check(slist_head *head)
+ {
+ 	slist_node *cur;
+ 
+ 	if (head == NULL)
+ 		elog(ERROR, "singly linked is NULL");
+ 
+ 	/*
+ 	 * there isn't much we can test in a singly linked list other that it
+ 	 * actually ends sometime, i.e. hasn't introduced a cycle or similar
+ 	 */
+ 	for (cur = head->head.next; cur != NULL; cur = cur->next)
+ 		;
+ }
+ 
+ #endif   /* ILIST_DEBUG */
*** a/src/backend/postmaster/autovacuum.c
--- b/src/backend/postmaster/autovacuum.c
***************
*** 77,83 ****
  #include "catalog/pg_database.h"
  #include "commands/dbcommands.h"
  #include "commands/vacuum.h"
! #include "lib/dllist.h"
  #include "libpq/pqsignal.h"
  #include "miscadmin.h"
  #include "pgstat.h"
--- 77,83 ----
  #include "catalog/pg_database.h"
  #include "commands/dbcommands.h"
  #include "commands/vacuum.h"
! #include "lib/ilist.h"
  #include "libpq/pqsignal.h"
  #include "miscadmin.h"
  #include "pgstat.h"
***************
*** 152,157 **** typedef struct avl_dbase
--- 152,158 ----
  	Oid			adl_datid;		/* hash key -- must be first */
  	TimestampTz adl_next_worker;
  	int			adl_score;
+ 	dlist_node	adl_node;
  } avl_dbase;
  
  /* struct to keep track of databases in worker */
***************
*** 258,265 **** typedef struct
  
  static AutoVacuumShmemStruct *AutoVacuumShmem;
  
! /* the database list in the launcher, and the context that contains it */
! static Dllist *DatabaseList = NULL;
  static MemoryContext DatabaseListCxt = NULL;
  
  /* Pointer to my own WorkerInfo, valid on each worker */
--- 259,269 ----
  
  static AutoVacuumShmemStruct *AutoVacuumShmem;
  
! /*
!  * the database list (of avl_dbase elements) in the launcher, and the context
!  * that contains it
!  */
! static dlist_head DatabaseList = DLIST_STATIC_INIT(DatabaseList);
  static MemoryContext DatabaseListCxt = NULL;
  
  /* Pointer to my own WorkerInfo, valid on each worker */
***************
*** 508,514 **** AutoVacLauncherMain(int argc, char *argv[])
  
  		/* don't leave dangling pointers to freed memory */
  		DatabaseListCxt = NULL;
! 		DatabaseList = NULL;
  
  		/*
  		 * Make sure pgstat also considers our stat data as gone.  Note: we
--- 512,518 ----
  
  		/* don't leave dangling pointers to freed memory */
  		DatabaseListCxt = NULL;
! 		dlist_init(&DatabaseList);
  
  		/*
  		 * Make sure pgstat also considers our stat data as gone.  Note: we
***************
*** 576,582 **** AutoVacLauncherMain(int argc, char *argv[])
  		struct timeval nap;
  		TimestampTz current_time = 0;
  		bool		can_launch;
! 		Dlelem	   *elem;
  		int			rc;
  
  		/*
--- 580,586 ----
  		struct timeval nap;
  		TimestampTz current_time = 0;
  		bool		can_launch;
! 		avl_dbase  *avdb;
  		int			rc;
  
  		/*
***************
*** 738,757 **** AutoVacLauncherMain(int argc, char *argv[])
  
  		/* We're OK to start a new worker */
  
! 		elem = DLGetTail(DatabaseList);
! 		if (elem != NULL)
! 		{
! 			avl_dbase  *avdb = DLE_VAL(elem);
! 
! 			/*
! 			 * launch a worker if next_worker is right now or it is in the
! 			 * past
! 			 */
! 			if (TimestampDifferenceExceeds(avdb->adl_next_worker,
! 										   current_time, 0))
! 				launch_worker(current_time);
! 		}
! 		else
  		{
  			/*
  			 * Special case when the list is empty: start a worker right away.
--- 742,748 ----
  
  		/* We're OK to start a new worker */
  
! 		if (dlist_is_empty(&DatabaseList))
  		{
  			/*
  			 * Special case when the list is empty: start a worker right away.
***************
*** 763,768 **** AutoVacLauncherMain(int argc, char *argv[])
--- 754,776 ----
  			 */
  			launch_worker(current_time);
  		}
+ 		else
+ 		{
+ 			/*
+ 			 * because rebuild_database_list constructs a list with most
+ 			 * distant adl_next_worker first, we obtain our database from the
+ 			 * tail of the list.
+ 			 */
+ 			avdb = dlist_tail_element(avl_dbase, adl_node, &DatabaseList);
+ 
+ 			/*
+ 			 * launch a worker if next_worker is right now or it is in the
+ 			 * past
+ 			 */
+ 			if (TimestampDifferenceExceeds(avdb->adl_next_worker,
+ 										   current_time, 0))
+ 				launch_worker(current_time);
+ 		}
  	}
  
  	/* Normal exit from the autovac launcher is here */
***************
*** 783,789 **** AutoVacLauncherMain(int argc, char *argv[])
  static void
  launcher_determine_sleep(bool canlaunch, bool recursing, struct timeval * nap)
  {
! 	Dlelem	   *elem;
  
  	/*
  	 * We sleep until the next scheduled vacuum.  We trust that when the
--- 791,797 ----
  static void
  launcher_determine_sleep(bool canlaunch, bool recursing, struct timeval * nap)
  {
! 	avl_dbase  *avdb;
  
  	/*
  	 * We sleep until the next scheduled vacuum.  We trust that when the
***************
*** 796,809 **** launcher_determine_sleep(bool canlaunch, bool recursing, struct timeval * nap)
  		nap->tv_sec = autovacuum_naptime;
  		nap->tv_usec = 0;
  	}
! 	else if ((elem = DLGetTail(DatabaseList)) != NULL)
  	{
- 		avl_dbase  *avdb = DLE_VAL(elem);
  		TimestampTz current_time = GetCurrentTimestamp();
  		TimestampTz next_wakeup;
  		long		secs;
  		int			usecs;
  
  		next_wakeup = avdb->adl_next_worker;
  		TimestampDifference(current_time, next_wakeup, &secs, &usecs);
  
--- 804,818 ----
  		nap->tv_sec = autovacuum_naptime;
  		nap->tv_usec = 0;
  	}
! 	else if (!dlist_is_empty(&DatabaseList))
  	{
  		TimestampTz current_time = GetCurrentTimestamp();
  		TimestampTz next_wakeup;
  		long		secs;
  		int			usecs;
  
+ 		avdb = dlist_tail_element(avl_dbase, adl_node, &DatabaseList);
+ 
  		next_wakeup = avdb->adl_next_worker;
  		TimestampDifference(current_time, next_wakeup, &secs, &usecs);
  
***************
*** 867,872 **** rebuild_database_list(Oid newdb)
--- 876,882 ----
  	int			score;
  	int			nelems;
  	HTAB	   *dbhash;
+ 	dlist_iter  iter;
  
  	/* use fresh stats */
  	autovac_refresh_stats();
***************
*** 927,962 **** rebuild_database_list(Oid newdb)
  	}
  
  	/* Now insert the databases from the existing list */
! 	if (DatabaseList != NULL)
  	{
! 		Dlelem	   *elem;
! 
! 		elem = DLGetHead(DatabaseList);
! 		while (elem != NULL)
! 		{
! 			avl_dbase  *avdb = DLE_VAL(elem);
! 			avl_dbase  *db;
! 			bool		found;
! 			PgStat_StatDBEntry *entry;
! 
! 			elem = DLGetSucc(elem);
  
! 			/*
! 			 * skip databases with no stat entries -- in particular, this gets
! 			 * rid of dropped databases
! 			 */
! 			entry = pgstat_fetch_stat_dbentry(avdb->adl_datid);
! 			if (entry == NULL)
! 				continue;
  
! 			db = hash_search(dbhash, &(avdb->adl_datid), HASH_ENTER, &found);
  
! 			if (!found)
! 			{
! 				/* hash_search already filled in the key */
! 				db->adl_score = score++;
! 				/* next_worker is filled in later */
! 			}
  		}
  	}
  
--- 937,964 ----
  	}
  
  	/* Now insert the databases from the existing list */
! 	dlist_foreach(iter, &DatabaseList)
  	{
! 		avl_dbase  *avdb = dlist_container(avl_dbase, adl_node, iter.cur);
! 		avl_dbase  *db;
! 		bool		found;
! 		PgStat_StatDBEntry *entry;
  
! 		/*
! 		 * skip databases with no stat entries -- in particular, this gets
! 		 * rid of dropped databases
! 		 */
! 		entry = pgstat_fetch_stat_dbentry(avdb->adl_datid);
! 		if (entry == NULL)
! 			continue;
  
! 		db = hash_search(dbhash, &(avdb->adl_datid), HASH_ENTER, &found);
  
! 		if (!found)
! 		{
! 			/* hash_search already filled in the key */
! 			db->adl_score = score++;
! 			/* next_worker is filled in later */
  		}
  	}
  
***************
*** 987,993 **** rebuild_database_list(Oid newdb)
  
  	/* from here on, the allocated memory belongs to the new list */
  	MemoryContextSwitchTo(newcxt);
! 	DatabaseList = DLNewList();
  
  	if (nelems > 0)
  	{
--- 989,995 ----
  
  	/* from here on, the allocated memory belongs to the new list */
  	MemoryContextSwitchTo(newcxt);
! 	dlist_init(&DatabaseList);
  
  	if (nelems > 0)
  	{
***************
*** 1029,1043 **** rebuild_database_list(Oid newdb)
  		for (i = 0; i < nelems; i++)
  		{
  			avl_dbase  *db = &(dbary[i]);
- 			Dlelem	   *elem;
  
  			current_time = TimestampTzPlusMilliseconds(current_time,
  													   millis_increment);
  			db->adl_next_worker = current_time;
  
- 			elem = DLNewElem(db);
  			/* later elements should go closer to the head of the list */
! 			DLAddHead(DatabaseList, elem);
  		}
  	}
  
--- 1031,1043 ----
  		for (i = 0; i < nelems; i++)
  		{
  			avl_dbase  *db = &(dbary[i]);
  
  			current_time = TimestampTzPlusMilliseconds(current_time,
  													   millis_increment);
  			db->adl_next_worker = current_time;
  
  			/* later elements should go closer to the head of the list */
! 			dlist_push_head(&DatabaseList, &db->adl_node);
  		}
  	}
  
***************
*** 1147,1153 **** do_start_worker(void)
  	foreach(cell, dblist)
  	{
  		avw_dbase  *tmp = lfirst(cell);
! 		Dlelem	   *elem;
  
  		/* Check to see if this one is at risk of wraparound */
  		if (TransactionIdPrecedes(tmp->adw_frozenxid, xidForceLimit))
--- 1147,1153 ----
  	foreach(cell, dblist)
  	{
  		avw_dbase  *tmp = lfirst(cell);
! 		dlist_iter iter;
  
  		/* Check to see if this one is at risk of wraparound */
  		if (TransactionIdPrecedes(tmp->adw_frozenxid, xidForceLimit))
***************
*** 1179,1189 **** do_start_worker(void)
  		 * autovacuum time yet.
  		 */
  		skipit = false;
- 		elem = DatabaseList ? DLGetTail(DatabaseList) : NULL;
  
! 		while (elem != NULL)
  		{
! 			avl_dbase  *dbp = DLE_VAL(elem);
  
  			if (dbp->adl_datid == tmp->adw_datid)
  			{
--- 1179,1188 ----
  		 * autovacuum time yet.
  		 */
  		skipit = false;
  
! 		dlist_reverse_foreach(iter, &DatabaseList)
  		{
! 			avl_dbase  *dbp = dlist_container(avl_dbase, adl_node, iter.cur);
  
  			if (dbp->adl_datid == tmp->adw_datid)
  			{
***************
*** 1200,1206 **** do_start_worker(void)
  
  				break;
  			}
- 			elem = DLGetPred(elem);
  		}
  		if (skipit)
  			continue;
--- 1199,1204 ----
***************
*** 1274,1295 **** static void
  launch_worker(TimestampTz now)
  {
  	Oid			dbid;
! 	Dlelem	   *elem;
  
  	dbid = do_start_worker();
  	if (OidIsValid(dbid))
  	{
  		/*
  		 * Walk the database list and update the corresponding entry.  If the
  		 * database is not on the list, we'll recreate the list.
  		 */
! 		elem = (DatabaseList == NULL) ? NULL : DLGetHead(DatabaseList);
! 		while (elem != NULL)
  		{
! 			avl_dbase  *avdb = DLE_VAL(elem);
  
  			if (avdb->adl_datid == dbid)
  			{
  				/*
  				 * add autovacuum_naptime seconds to the current time, and use
  				 * that as the new "next_worker" field for this database.
--- 1272,1296 ----
  launch_worker(TimestampTz now)
  {
  	Oid			dbid;
! 	dlist_iter  iter;
  
  	dbid = do_start_worker();
  	if (OidIsValid(dbid))
  	{
+ 		bool found = false;
+ 
  		/*
  		 * Walk the database list and update the corresponding entry.  If the
  		 * database is not on the list, we'll recreate the list.
  		 */
! 		dlist_foreach(iter, &DatabaseList)
  		{
! 			avl_dbase  *avdb = dlist_container(avl_dbase, adl_node, iter.cur);
  
  			if (avdb->adl_datid == dbid)
  			{
+ 				found = true;
+ 
  				/*
  				 * add autovacuum_naptime seconds to the current time, and use
  				 * that as the new "next_worker" field for this database.
***************
*** 1297,1306 **** launch_worker(TimestampTz now)
  				avdb->adl_next_worker =
  					TimestampTzPlusMilliseconds(now, autovacuum_naptime * 1000);
  
! 				DLMoveToFront(elem);
  				break;
  			}
- 			elem = DLGetSucc(elem);
  		}
  
  		/*
--- 1298,1306 ----
  				avdb->adl_next_worker =
  					TimestampTzPlusMilliseconds(now, autovacuum_naptime * 1000);
  
! 				dlist_move_head(&DatabaseList, iter.cur);
  				break;
  			}
  		}
  
  		/*
***************
*** 1310,1316 **** launch_worker(TimestampTz now)
  		 * pgstat entry, but this is not a problem because we don't want to
  		 * schedule workers regularly into those in any case.
  		 */
! 		if (elem == NULL)
  			rebuild_database_list(dbid);
  	}
  }
--- 1310,1316 ----
  		 * pgstat entry, but this is not a problem because we don't want to
  		 * schedule workers regularly into those in any case.
  		 */
! 		if (!found)
  			rebuild_database_list(dbid);
  	}
  }
*** a/src/backend/postmaster/postmaster.c
--- b/src/backend/postmaster/postmaster.c
***************
*** 95,101 ****
  #include "access/xlog.h"
  #include "bootstrap/bootstrap.h"
  #include "catalog/pg_control.h"
! #include "lib/dllist.h"
  #include "libpq/auth.h"
  #include "libpq/ip.h"
  #include "libpq/libpq.h"
--- 95,101 ----
  #include "access/xlog.h"
  #include "bootstrap/bootstrap.h"
  #include "catalog/pg_control.h"
! #include "lib/ilist.h"
  #include "libpq/auth.h"
  #include "libpq/ip.h"
  #include "libpq/libpq.h"
***************
*** 146,155 **** typedef struct bkend
  	int			child_slot;		/* PMChildSlot for this backend, if any */
  	bool		is_autovacuum;	/* is it an autovacuum process? */
  	bool		dead_end;		/* is it going to send an error and quit? */
! 	Dlelem		elem;			/* list link in BackendList */
  } Backend;
  
! static Dllist *BackendList;
  
  #ifdef EXEC_BACKEND
  static Backend *ShmemBackendArray;
--- 146,155 ----
  	int			child_slot;		/* PMChildSlot for this backend, if any */
  	bool		is_autovacuum;	/* is it an autovacuum process? */
  	bool		dead_end;		/* is it going to send an error and quit? */
! 	dlist_node	elem;			/* list link in BackendList */
  } Backend;
  
! static dlist_head BackendList = DLIST_STATIC_INIT(BackendList);
  
  #ifdef EXEC_BACKEND
  static Backend *ShmemBackendArray;
***************
*** 1028,1038 **** PostmasterMain(int argc, char *argv[])
  	set_stack_base();
  
  	/*
- 	 * Initialize the list of active backends.
- 	 */
- 	BackendList = DLNewList();
- 
- 	/*
  	 * Initialize pipe (or process handle on Windows) that allows children to
  	 * wake up from sleep on postmaster death.
  	 */
--- 1028,1033 ----
***************
*** 1872,1878 **** processCancelRequest(Port *port, void *pkt)
  	Backend    *bp;
  
  #ifndef EXEC_BACKEND
! 	Dlelem	   *curr;
  #else
  	int			i;
  #endif
--- 1867,1873 ----
  	Backend    *bp;
  
  #ifndef EXEC_BACKEND
! 	dlist_iter  iter;
  #else
  	int			i;
  #endif
***************
*** 1886,1894 **** processCancelRequest(Port *port, void *pkt)
  	 * duplicate array in shared memory.
  	 */
  #ifndef EXEC_BACKEND
! 	for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr))
  	{
! 		bp = (Backend *) DLE_VAL(curr);
  #else
  	for (i = MaxLivePostmasterChildren() - 1; i >= 0; i--)
  	{
--- 1881,1889 ----
  	 * duplicate array in shared memory.
  	 */
  #ifndef EXEC_BACKEND
! 	dlist_foreach(iter, &BackendList)
  	{
! 		bp = dlist_container(Backend, elem, iter.cur);
  #else
  	for (i = MaxLivePostmasterChildren() - 1; i >= 0; i--)
  	{
***************
*** 2648,2654 **** static void
  CleanupBackend(int pid,
  			   int exitstatus)	/* child's exit status. */
  {
! 	Dlelem	   *curr;
  
  	LogChildExit(DEBUG2, _("server process"), pid, exitstatus);
  
--- 2643,2649 ----
  CleanupBackend(int pid,
  			   int exitstatus)	/* child's exit status. */
  {
! 	dlist_mutable_iter iter;
  
  	LogChildExit(DEBUG2, _("server process"), pid, exitstatus);
  
***************
*** 2680,2688 **** CleanupBackend(int pid,
  		return;
  	}
  
! 	for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr))
  	{
! 		Backend    *bp = (Backend *) DLE_VAL(curr);
  
  		if (bp->pid == pid)
  		{
--- 2675,2683 ----
  		return;
  	}
  
! 	dlist_foreach_modify(iter, &BackendList)
  	{
! 		Backend    *bp = dlist_container(Backend, elem, iter.cur);
  
  		if (bp->pid == pid)
  		{
***************
*** 2701,2707 **** CleanupBackend(int pid,
  				ShmemBackendArrayRemove(bp);
  #endif
  			}
! 			DLRemove(curr);
  			free(bp);
  			break;
  		}
--- 2696,2702 ----
  				ShmemBackendArrayRemove(bp);
  #endif
  			}
! 			dlist_delete(&BackendList, iter.cur);
  			free(bp);
  			break;
  		}
***************
*** 2718,2725 **** CleanupBackend(int pid,
  static void
  HandleChildCrash(int pid, int exitstatus, const char *procname)
  {
! 	Dlelem	   *curr,
! 			   *next;
  	Backend    *bp;
  
  	/*
--- 2713,2719 ----
  static void
  HandleChildCrash(int pid, int exitstatus, const char *procname)
  {
! 	dlist_mutable_iter iter;
  	Backend    *bp;
  
  	/*
***************
*** 2734,2743 **** HandleChildCrash(int pid, int exitstatus, const char *procname)
  	}
  
  	/* Process regular backends */
! 	for (curr = DLGetHead(BackendList); curr; curr = next)
  	{
! 		next = DLGetSucc(curr);
! 		bp = (Backend *) DLE_VAL(curr);
  		if (bp->pid == pid)
  		{
  			/*
--- 2728,2737 ----
  	}
  
  	/* Process regular backends */
! 	dlist_foreach_modify(iter, &BackendList)
  	{
! 		bp = dlist_container(Backend, elem, iter.cur);
! 
  		if (bp->pid == pid)
  		{
  			/*
***************
*** 2750,2756 **** HandleChildCrash(int pid, int exitstatus, const char *procname)
  				ShmemBackendArrayRemove(bp);
  #endif
  			}
! 			DLRemove(curr);
  			free(bp);
  			/* Keep looping so we can signal remaining backends */
  		}
--- 2744,2750 ----
  				ShmemBackendArrayRemove(bp);
  #endif
  			}
! 			dlist_delete(&BackendList, iter.cur);
  			free(bp);
  			/* Keep looping so we can signal remaining backends */
  		}
***************
*** 3113,3119 **** PostmasterStateMachine(void)
  		 * normal state transition leading up to PM_WAIT_DEAD_END, or during
  		 * FatalError processing.
  		 */
! 		if (DLGetHead(BackendList) == NULL &&
  			PgArchPID == 0 && PgStatPID == 0)
  		{
  			/* These other guys should be dead already */
--- 3107,3113 ----
  		 * normal state transition leading up to PM_WAIT_DEAD_END, or during
  		 * FatalError processing.
  		 */
! 		if (dlist_is_empty(&BackendList) &&
  			PgArchPID == 0 && PgStatPID == 0)
  		{
  			/* These other guys should be dead already */
***************
*** 3239,3250 **** signal_child(pid_t pid, int signal)
  static bool
  SignalSomeChildren(int signal, int target)
  {
! 	Dlelem	   *curr;
  	bool		signaled = false;
  
! 	for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr))
  	{
! 		Backend    *bp = (Backend *) DLE_VAL(curr);
  
  		if (bp->dead_end)
  			continue;
--- 3233,3244 ----
  static bool
  SignalSomeChildren(int signal, int target)
  {
! 	dlist_iter  iter;
  	bool		signaled = false;
  
! 	dlist_foreach(iter, &BackendList)
  	{
! 		Backend    *bp = dlist_container(Backend, elem, iter.cur);
  
  		if (bp->dead_end)
  			continue;
***************
*** 3382,3389 **** BackendStartup(Port *port)
  	 */
  	bn->pid = pid;
  	bn->is_autovacuum = false;
! 	DLInitElem(&bn->elem, bn);
! 	DLAddHead(BackendList, &bn->elem);
  #ifdef EXEC_BACKEND
  	if (!bn->dead_end)
  		ShmemBackendArrayAdd(bn);
--- 3376,3383 ----
  	 */
  	bn->pid = pid;
  	bn->is_autovacuum = false;
! 	dlist_push_head(&BackendList, &bn->elem);
! 
  #ifdef EXEC_BACKEND
  	if (!bn->dead_end)
  		ShmemBackendArrayAdd(bn);
***************
*** 4491,4502 **** PostmasterRandom(void)
  static int
  CountChildren(int target)
  {
! 	Dlelem	   *curr;
  	int			cnt = 0;
  
! 	for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr))
  	{
! 		Backend    *bp = (Backend *) DLE_VAL(curr);
  
  		if (bp->dead_end)
  			continue;
--- 4485,4496 ----
  static int
  CountChildren(int target)
  {
! 	dlist_iter  iter;
  	int			cnt = 0;
  
! 	dlist_foreach(iter, &BackendList)
  	{
! 		Backend    *bp = dlist_container(Backend, elem, iter.cur);
  
  		if (bp->dead_end)
  			continue;
***************
*** 4675,4682 **** StartAutovacuumWorker(void)
  			if (bn->pid > 0)
  			{
  				bn->is_autovacuum = true;
! 				DLInitElem(&bn->elem, bn);
! 				DLAddHead(BackendList, &bn->elem);
  #ifdef EXEC_BACKEND
  				ShmemBackendArrayAdd(bn);
  #endif
--- 4669,4675 ----
  			if (bn->pid > 0)
  			{
  				bn->is_autovacuum = true;
! 				dlist_push_head(&BackendList, &bn->elem);
  #ifdef EXEC_BACKEND
  				ShmemBackendArrayAdd(bn);
  #endif
*** a/src/backend/utils/cache/catcache.c
--- b/src/backend/utils/cache/catcache.c
***************
*** 291,297 **** CatalogCacheComputeTupleHashValue(CatCache *cache, HeapTuple tuple)
  static void
  CatCachePrintStats(int code, Datum arg)
  {
! 	CatCache   *cache;
  	long		cc_searches = 0;
  	long		cc_hits = 0;
  	long		cc_neg_hits = 0;
--- 291,297 ----
  static void
  CatCachePrintStats(int code, Datum arg)
  {
! 	slist_iter  iter;
  	long		cc_searches = 0;
  	long		cc_hits = 0;
  	long		cc_neg_hits = 0;
***************
*** 300,307 **** CatCachePrintStats(int code, Datum arg)
  	long		cc_lsearches = 0;
  	long		cc_lhits = 0;
  
! 	for (cache = CacheHdr->ch_caches; cache; cache = cache->cc_next)
  	{
  		if (cache->cc_ntup == 0 && cache->cc_searches == 0)
  			continue;			/* don't print unused caches */
  		elog(DEBUG2, "catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits",
--- 300,309 ----
  	long		cc_lsearches = 0;
  	long		cc_lhits = 0;
  
! 	slist_foreach(iter, &CacheHdr->ch_caches)
  	{
+ 		CatCache   *cache = slist_container(CatCache, cc_next, iter.cur);
+ 
  		if (cache->cc_ntup == 0 && cache->cc_searches == 0)
  			continue;			/* don't print unused caches */
  		elog(DEBUG2, "catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits",
***************
*** 368,375 **** CatCacheRemoveCTup(CatCache *cache, CatCTup *ct)
  		return;					/* nothing left to do */
  	}
  
! 	/* delink from linked list */
! 	DLRemove(&ct->cache_elem);
  
  	/* free associated tuple data */
  	if (ct->tuple.t_data != NULL)
--- 370,376 ----
  		return;					/* nothing left to do */
  	}
  
! 	dlist_delete(ct->cache_bucket, &ct->cache_elem);
  
  	/* free associated tuple data */
  	if (ct->tuple.t_data != NULL)
***************
*** 412,418 **** CatCacheRemoveCList(CatCache *cache, CatCList *cl)
  	}
  
  	/* delink from linked list */
! 	DLRemove(&cl->cache_elem);
  
  	/* free associated tuple data */
  	if (cl->tuple.t_data != NULL)
--- 413,419 ----
  	}
  
  	/* delink from linked list */
! 	dlist_delete(&cache->cc_lists, &cl->cache_elem);
  
  	/* free associated tuple data */
  	if (cl->tuple.t_data != NULL)
***************
*** 442,459 **** CatCacheRemoveCList(CatCache *cache, CatCList *cl)
  void
  CatalogCacheIdInvalidate(int cacheId, uint32 hashValue)
  {
! 	CatCache   *ccp;
  
  	CACHE1_elog(DEBUG2, "CatalogCacheIdInvalidate: called");
  
  	/*
  	 * inspect caches to find the proper cache
  	 */
! 	for (ccp = CacheHdr->ch_caches; ccp; ccp = ccp->cc_next)
  	{
  		Index		hashIndex;
! 		Dlelem	   *elt,
! 				   *nextelt;
  
  		if (cacheId != ccp->id)
  			continue;
--- 443,460 ----
  void
  CatalogCacheIdInvalidate(int cacheId, uint32 hashValue)
  {
! 	slist_iter cache_iter;
  
  	CACHE1_elog(DEBUG2, "CatalogCacheIdInvalidate: called");
  
  	/*
  	 * inspect caches to find the proper cache
  	 */
! 	slist_foreach(cache_iter, &CacheHdr->ch_caches)
  	{
  		Index		hashIndex;
! 		dlist_mutable_iter iter;
! 		CatCache   *ccp = slist_container(CatCache, cc_next, cache_iter.cur);
  
  		if (cacheId != ccp->id)
  			continue;
***************
*** 468,478 **** CatalogCacheIdInvalidate(int cacheId, uint32 hashValue)
  		 * Invalidate *all* CatCLists in this cache; it's too hard to tell
  		 * which searches might still be correct, so just zap 'em all.
  		 */
! 		for (elt = DLGetHead(&ccp->cc_lists); elt; elt = nextelt)
  		{
! 			CatCList   *cl = (CatCList *) DLE_VAL(elt);
! 
! 			nextelt = DLGetSucc(elt);
  
  			if (cl->refcount > 0)
  				cl->dead = true;
--- 469,477 ----
  		 * Invalidate *all* CatCLists in this cache; it's too hard to tell
  		 * which searches might still be correct, so just zap 'em all.
  		 */
! 		dlist_foreach_modify(iter, &ccp->cc_lists)
  		{
! 			CatCList   *cl = dlist_container(CatCList, cache_elem, iter.cur);
  
  			if (cl->refcount > 0)
  				cl->dead = true;
***************
*** 484,495 **** CatalogCacheIdInvalidate(int cacheId, uint32 hashValue)
  		 * inspect the proper hash bucket for tuple matches
  		 */
  		hashIndex = HASH_INDEX(hashValue, ccp->cc_nbuckets);
! 
! 		for (elt = DLGetHead(&ccp->cc_bucket[hashIndex]); elt; elt = nextelt)
  		{
! 			CatCTup    *ct = (CatCTup *) DLE_VAL(elt);
! 
! 			nextelt = DLGetSucc(elt);
  
  			if (hashValue == ct->hash_value)
  			{
--- 483,491 ----
  		 * inspect the proper hash bucket for tuple matches
  		 */
  		hashIndex = HASH_INDEX(hashValue, ccp->cc_nbuckets);
! 		dlist_foreach_modify(iter, &ccp->cc_bucket[hashIndex])
  		{
! 			CatCTup    *ct = dlist_container(CatCTup, cache_elem, iter.cur);
  
  			if (hashValue == ct->hash_value)
  			{
***************
*** 557,573 **** AtEOXact_CatCache(bool isCommit)
  #ifdef USE_ASSERT_CHECKING
  	if (assert_enabled)
  	{
! 		CatCache   *ccp;
  
! 		for (ccp = CacheHdr->ch_caches; ccp; ccp = ccp->cc_next)
  		{
! 			Dlelem	   *elt;
  			int			i;
  
  			/* Check CatCLists */
! 			for (elt = DLGetHead(&ccp->cc_lists); elt; elt = DLGetSucc(elt))
  			{
! 				CatCList   *cl = (CatCList *) DLE_VAL(elt);
  
  				Assert(cl->cl_magic == CL_MAGIC);
  				Assert(cl->refcount == 0);
--- 553,570 ----
  #ifdef USE_ASSERT_CHECKING
  	if (assert_enabled)
  	{
! 		slist_iter  cache_iter;
  
! 		slist_foreach(cache_iter, &(CacheHdr->ch_caches))
  		{
! 			CatCache   *ccp = slist_container(CatCache, cc_next, cache_iter.cur);
! 			dlist_iter  iter;
  			int			i;
  
  			/* Check CatCLists */
! 			dlist_foreach(iter, &ccp->cc_lists)
  			{
! 				CatCList   *cl = dlist_container(CatCList, cache_elem, iter.cur);
  
  				Assert(cl->cl_magic == CL_MAGIC);
  				Assert(cl->refcount == 0);
***************
*** 577,587 **** AtEOXact_CatCache(bool isCommit)
  			/* Check individual tuples */
  			for (i = 0; i < ccp->cc_nbuckets; i++)
  			{
! 				for (elt = DLGetHead(&ccp->cc_bucket[i]);
! 					 elt;
! 					 elt = DLGetSucc(elt))
  				{
! 					CatCTup    *ct = (CatCTup *) DLE_VAL(elt);
  
  					Assert(ct->ct_magic == CT_MAGIC);
  					Assert(ct->refcount == 0);
--- 574,584 ----
  			/* Check individual tuples */
  			for (i = 0; i < ccp->cc_nbuckets; i++)
  			{
! 				dlist_head *bucket = &ccp->cc_bucket[i];
! 
! 				dlist_foreach(iter, bucket)
  				{
! 					CatCTup    *ct = dlist_container(CatCTup, cache_elem, iter.cur);
  
  					Assert(ct->ct_magic == CT_MAGIC);
  					Assert(ct->refcount == 0);
***************
*** 604,619 **** AtEOXact_CatCache(bool isCommit)
  static void
  ResetCatalogCache(CatCache *cache)
  {
! 	Dlelem	   *elt,
! 			   *nextelt;
  	int			i;
  
  	/* Remove each list in this cache, or at least mark it dead */
! 	for (elt = DLGetHead(&cache->cc_lists); elt; elt = nextelt)
  	{
! 		CatCList   *cl = (CatCList *) DLE_VAL(elt);
! 
! 		nextelt = DLGetSucc(elt);
  
  		if (cl->refcount > 0)
  			cl->dead = true;
--- 601,613 ----
  static void
  ResetCatalogCache(CatCache *cache)
  {
! 	dlist_mutable_iter iter;
  	int			i;
  
  	/* Remove each list in this cache, or at least mark it dead */
! 	dlist_foreach_modify(iter, &cache->cc_lists)
  	{
! 		CatCList   *cl = dlist_container(CatCList, cache_elem, iter.cur);
  
  		if (cl->refcount > 0)
  			cl->dead = true;
***************
*** 624,634 **** ResetCatalogCache(CatCache *cache)
  	/* Remove each tuple in this cache, or at least mark it dead */
  	for (i = 0; i < cache->cc_nbuckets; i++)
  	{
! 		for (elt = DLGetHead(&cache->cc_bucket[i]); elt; elt = nextelt)
! 		{
! 			CatCTup    *ct = (CatCTup *) DLE_VAL(elt);
  
! 			nextelt = DLGetSucc(elt);
  
  			if (ct->refcount > 0 ||
  				(ct->c_list && ct->c_list->refcount > 0))
--- 618,628 ----
  	/* Remove each tuple in this cache, or at least mark it dead */
  	for (i = 0; i < cache->cc_nbuckets; i++)
  	{
! 		dlist_head *bucket = &cache->cc_bucket[i];
  
! 		dlist_foreach_modify(iter, bucket)
! 		{
! 			CatCTup    *ct = dlist_container(CatCTup, cache_elem, iter.cur);
  
  			if (ct->refcount > 0 ||
  				(ct->c_list && ct->c_list->refcount > 0))
***************
*** 654,665 **** ResetCatalogCache(CatCache *cache)
  void
  ResetCatalogCaches(void)
  {
! 	CatCache   *cache;
  
  	CACHE1_elog(DEBUG2, "ResetCatalogCaches called");
  
! 	for (cache = CacheHdr->ch_caches; cache; cache = cache->cc_next)
  		ResetCatalogCache(cache);
  
  	CACHE1_elog(DEBUG2, "end of ResetCatalogCaches call");
  }
--- 648,663 ----
  void
  ResetCatalogCaches(void)
  {
! 	slist_iter    iter;
  
  	CACHE1_elog(DEBUG2, "ResetCatalogCaches called");
  
! 	slist_foreach(iter, &CacheHdr->ch_caches)
! 	{
! 		CatCache   *cache = slist_container(CatCache, cc_next, iter.cur);
! 
  		ResetCatalogCache(cache);
+ 	}
  
  	CACHE1_elog(DEBUG2, "end of ResetCatalogCaches call");
  }
***************
*** 680,691 **** ResetCatalogCaches(void)
  void
  CatalogCacheFlushCatalog(Oid catId)
  {
! 	CatCache   *cache;
  
  	CACHE2_elog(DEBUG2, "CatalogCacheFlushCatalog called for %u", catId);
  
! 	for (cache = CacheHdr->ch_caches; cache; cache = cache->cc_next)
  	{
  		/* Does this cache store tuples of the target catalog? */
  		if (cache->cc_reloid == catId)
  		{
--- 678,691 ----
  void
  CatalogCacheFlushCatalog(Oid catId)
  {
! 	slist_iter  iter;
  
  	CACHE2_elog(DEBUG2, "CatalogCacheFlushCatalog called for %u", catId);
  
! 	slist_foreach(iter, &(CacheHdr->ch_caches))
  	{
+ 		CatCache   *cache = slist_container(CatCache, cc_next, iter.cur);
+ 
  		/* Does this cache store tuples of the target catalog? */
  		if (cache->cc_reloid == catId)
  		{
***************
*** 760,766 **** InitCatCache(int id,
  	if (CacheHdr == NULL)
  	{
  		CacheHdr = (CatCacheHeader *) palloc(sizeof(CatCacheHeader));
! 		CacheHdr->ch_caches = NULL;
  		CacheHdr->ch_ntup = 0;
  #ifdef CATCACHE_STATS
  		/* set up to dump stats at backend exit */
--- 760,766 ----
  	if (CacheHdr == NULL)
  	{
  		CacheHdr = (CatCacheHeader *) palloc(sizeof(CatCacheHeader));
! 		slist_init(&CacheHdr->ch_caches);
  		CacheHdr->ch_ntup = 0;
  #ifdef CATCACHE_STATS
  		/* set up to dump stats at backend exit */
***************
*** 770,779 **** InitCatCache(int id,
  
  	/*
  	 * allocate a new cache structure
- 	 *
- 	 * Note: we assume zeroing initializes the Dllist headers correctly
  	 */
! 	cp = (CatCache *) palloc0(sizeof(CatCache) + nbuckets * sizeof(Dllist));
  
  	/*
  	 * initialize the cache's relation information for the relation
--- 770,777 ----
  
  	/*
  	 * allocate a new cache structure
  	 */
! 	cp = (CatCache *) palloc0(sizeof(CatCache) + nbuckets * sizeof(dlist_node));
  
  	/*
  	 * initialize the cache's relation information for the relation
***************
*** 792,797 **** InitCatCache(int id,
--- 790,800 ----
  	for (i = 0; i < nkeys; ++i)
  		cp->cc_key[i] = key[i];
  
+ 	dlist_init(&cp->cc_lists);
+ 
+ 	for (i = 0; i < nbuckets; i++)
+ 		dlist_init(&cp->cc_bucket[i]);
+ 
  	/*
  	 * new cache is initialized as far as we can go for now. print some
  	 * debugging information, if appropriate.
***************
*** 801,808 **** InitCatCache(int id,
  	/*
  	 * add completed cache to top of group header's list
  	 */
! 	cp->cc_next = CacheHdr->ch_caches;
! 	CacheHdr->ch_caches = cp;
  
  	/*
  	 * back to the old context before we return...
--- 804,810 ----
  	/*
  	 * add completed cache to top of group header's list
  	 */
! 	slist_push_head(&CacheHdr->ch_caches, &cp->cc_next);
  
  	/*
  	 * back to the old context before we return...
***************
*** 1060,1066 **** SearchCatCache(CatCache *cache,
  	ScanKeyData cur_skey[CATCACHE_MAXKEYS];
  	uint32		hashValue;
  	Index		hashIndex;
! 	Dlelem	   *elt;
  	CatCTup    *ct;
  	Relation	relation;
  	SysScanDesc scandesc;
--- 1062,1069 ----
  	ScanKeyData cur_skey[CATCACHE_MAXKEYS];
  	uint32		hashValue;
  	Index		hashIndex;
! 	dlist_mutable_iter  iter;
! 	dlist_head *bucket;
  	CatCTup    *ct;
  	Relation	relation;
  	SysScanDesc scandesc;
***************
*** 1094,1106 **** SearchCatCache(CatCache *cache,
  	/*
  	 * scan the hash bucket until we find a match or exhaust our tuples
  	 */
! 	for (elt = DLGetHead(&cache->cc_bucket[hashIndex]);
! 		 elt;
! 		 elt = DLGetSucc(elt))
  	{
  		bool		res;
  
! 		ct = (CatCTup *) DLE_VAL(elt);
  
  		if (ct->dead)
  			continue;			/* ignore dead entries */
--- 1097,1109 ----
  	/*
  	 * scan the hash bucket until we find a match or exhaust our tuples
  	 */
! 	bucket = &cache->cc_bucket[hashIndex];
! 
! 	dlist_foreach_modify(iter, bucket)
  	{
  		bool		res;
  
! 		ct = dlist_container(CatCTup, cache_elem, iter.cur);
  
  		if (ct->dead)
  			continue;			/* ignore dead entries */
***************
*** 1125,1131 **** SearchCatCache(CatCache *cache,
  		 * most frequently accessed elements in any hashbucket will tend to be
  		 * near the front of the hashbucket's list.)
  		 */
! 		DLMoveToFront(&ct->cache_elem);
  
  		/*
  		 * If it's a positive entry, bump its refcount and return it. If it's
--- 1128,1134 ----
  		 * most frequently accessed elements in any hashbucket will tend to be
  		 * near the front of the hashbucket's list.)
  		 */
! 		dlist_move_head(bucket, &ct->cache_elem);
  
  		/*
  		 * If it's a positive entry, bump its refcount and return it. If it's
***************
*** 1340,1346 **** SearchCatCacheList(CatCache *cache,
  {
  	ScanKeyData cur_skey[CATCACHE_MAXKEYS];
  	uint32		lHashValue;
! 	Dlelem	   *elt;
  	CatCList   *cl;
  	CatCTup    *ct;
  	List	   *volatile ctlist;
--- 1343,1349 ----
  {
  	ScanKeyData cur_skey[CATCACHE_MAXKEYS];
  	uint32		lHashValue;
! 	dlist_iter  iter;
  	CatCList   *cl;
  	CatCTup    *ct;
  	List	   *volatile ctlist;
***************
*** 1382,1394 **** SearchCatCacheList(CatCache *cache,
  	/*
  	 * scan the items until we find a match or exhaust our list
  	 */
! 	for (elt = DLGetHead(&cache->cc_lists);
! 		 elt;
! 		 elt = DLGetSucc(elt))
  	{
  		bool		res;
  
! 		cl = (CatCList *) DLE_VAL(elt);
  
  		if (cl->dead)
  			continue;			/* ignore dead entries */
--- 1385,1395 ----
  	/*
  	 * scan the items until we find a match or exhaust our list
  	 */
! 	dlist_foreach(iter, &cache->cc_lists)
  	{
  		bool		res;
  
! 		cl = dlist_container(CatCList, cache_elem, iter.cur);
  
  		if (cl->dead)
  			continue;			/* ignore dead entries */
***************
*** 1416,1422 **** SearchCatCacheList(CatCache *cache,
  		 * since there's no point in that unless they are searched for
  		 * individually.)
  		 */
! 		DLMoveToFront(&cl->cache_elem);
  
  		/* Bump the list's refcount and return it */
  		ResourceOwnerEnlargeCatCacheListRefs(CurrentResourceOwner);
--- 1417,1423 ----
  		 * since there's no point in that unless they are searched for
  		 * individually.)
  		 */
! 		dlist_move_head(&cache->cc_lists, &cl->cache_elem);
  
  		/* Bump the list's refcount and return it */
  		ResourceOwnerEnlargeCatCacheListRefs(CurrentResourceOwner);
***************
*** 1468,1473 **** SearchCatCacheList(CatCache *cache,
--- 1469,1476 ----
  		{
  			uint32		hashValue;
  			Index		hashIndex;
+ 			bool		found = false;
+ 			dlist_head *bucket;
  
  			/*
  			 * See if there's an entry for this tuple already.
***************
*** 1476,1486 **** SearchCatCacheList(CatCache *cache,
  			hashValue = CatalogCacheComputeTupleHashValue(cache, ntp);
  			hashIndex = HASH_INDEX(hashValue, cache->cc_nbuckets);
  
! 			for (elt = DLGetHead(&cache->cc_bucket[hashIndex]);
! 				 elt;
! 				 elt = DLGetSucc(elt))
  			{
! 				ct = (CatCTup *) DLE_VAL(elt);
  
  				if (ct->dead || ct->negative)
  					continue;	/* ignore dead and negative entries */
--- 1479,1488 ----
  			hashValue = CatalogCacheComputeTupleHashValue(cache, ntp);
  			hashIndex = HASH_INDEX(hashValue, cache->cc_nbuckets);
  
! 			bucket = &cache->cc_bucket[hashIndex];
! 			dlist_foreach(iter, bucket)
  			{
! 				ct = dlist_container(CatCTup, cache_elem, iter.cur);
  
  				if (ct->dead || ct->negative)
  					continue;	/* ignore dead and negative entries */
***************
*** 1498,1507 **** SearchCatCacheList(CatCache *cache,
  				if (ct->c_list)
  					continue;
  
  				break;			/* A-OK */
  			}
  
! 			if (elt == NULL)
  			{
  				/* We didn't find a usable entry, so make a new one */
  				ct = CatalogCacheCreateEntry(cache, ntp,
--- 1500,1510 ----
  				if (ct->c_list)
  					continue;
  
+ 				found = true;
  				break;			/* A-OK */
  			}
  
! 			if (!found)
  			{
  				/* We didn't find a usable entry, so make a new one */
  				ct = CatalogCacheCreateEntry(cache, ntp,
***************
*** 1564,1570 **** SearchCatCacheList(CatCache *cache,
  
  	cl->cl_magic = CL_MAGIC;
  	cl->my_cache = cache;
- 	DLInitElem(&cl->cache_elem, cl);
  	cl->refcount = 0;			/* for the moment */
  	cl->dead = false;
  	cl->ordered = ordered;
--- 1567,1572 ----
***************
*** 1587,1593 **** SearchCatCacheList(CatCache *cache,
  	}
  	Assert(i == nmembers);
  
! 	DLAddHead(&cache->cc_lists, &cl->cache_elem);
  
  	/* Finally, bump the list's refcount and return it */
  	cl->refcount++;
--- 1589,1595 ----
  	}
  	Assert(i == nmembers);
  
! 	dlist_push_head(&cache->cc_lists, &cl->cache_elem);
  
  	/* Finally, bump the list's refcount and return it */
  	cl->refcount++;
***************
*** 1664,1677 **** CatalogCacheCreateEntry(CatCache *cache, HeapTuple ntp,
  	 */
  	ct->ct_magic = CT_MAGIC;
  	ct->my_cache = cache;
! 	DLInitElem(&ct->cache_elem, (void *) ct);
  	ct->c_list = NULL;
  	ct->refcount = 0;			/* for the moment */
  	ct->dead = false;
  	ct->negative = negative;
  	ct->hash_value = hashValue;
  
! 	DLAddHead(&cache->cc_bucket[hashIndex], &ct->cache_elem);
  
  	cache->cc_ntup++;
  	CacheHdr->ch_ntup++;
--- 1666,1680 ----
  	 */
  	ct->ct_magic = CT_MAGIC;
  	ct->my_cache = cache;
! 	ct->cache_bucket = &cache->cc_bucket[hashIndex];
! 
  	ct->c_list = NULL;
  	ct->refcount = 0;			/* for the moment */
  	ct->dead = false;
  	ct->negative = negative;
  	ct->hash_value = hashValue;
  
! 	dlist_push_head(ct->cache_bucket, &ct->cache_elem);
  
  	cache->cc_ntup++;
  	CacheHdr->ch_ntup++;
***************
*** 1785,1791 **** PrepareToInvalidateCacheTuple(Relation relation,
  							  HeapTuple newtuple,
  							  void (*function) (int, uint32, Oid))
  {
! 	CatCache   *ccp;
  	Oid			reloid;
  
  	CACHE1_elog(DEBUG2, "PrepareToInvalidateCacheTuple: called");
--- 1788,1794 ----
  							  HeapTuple newtuple,
  							  void (*function) (int, uint32, Oid))
  {
! 	slist_iter  iter;
  	Oid			reloid;
  
  	CACHE1_elog(DEBUG2, "PrepareToInvalidateCacheTuple: called");
***************
*** 1808,1817 **** PrepareToInvalidateCacheTuple(Relation relation,
  	 * ----------------
  	 */
  
! 	for (ccp = CacheHdr->ch_caches; ccp; ccp = ccp->cc_next)
  	{
  		uint32		hashvalue;
  		Oid			dbid;
  
  		if (ccp->cc_reloid != reloid)
  			continue;
--- 1811,1821 ----
  	 * ----------------
  	 */
  
! 	slist_foreach(iter, &(CacheHdr->ch_caches))
  	{
  		uint32		hashvalue;
  		Oid			dbid;
+ 		CatCache   *ccp = slist_container(CatCache, cc_next, iter.cur);
  
  		if (ccp->cc_reloid != reloid)
  			continue;
*** a/src/include/lib/dllist.h
--- /dev/null
***************
*** 1,85 ****
- /*-------------------------------------------------------------------------
-  *
-  * dllist.h
-  *		simple doubly linked list primitives
-  *		the elements of the list are void* so the lists can contain anything
-  *		Dlelem can only be in one list at a time
-  *
-  *
-  *	 Here's a small example of how to use Dllists:
-  *
-  *	 Dllist *lst;
-  *	 Dlelem *elt;
-  *	 void	*in_stuff;	  -- stuff to stick in the list
-  *	 void	*out_stuff
-  *
-  *	 lst = DLNewList();				   -- make a new dllist
-  *	 DLAddHead(lst, DLNewElem(in_stuff)); -- add a new element to the list
-  *											 with in_stuff as the value
-  *	  ...
-  *	 elt = DLGetHead(lst);			   -- retrieve the head element
-  *	 out_stuff = (void*)DLE_VAL(elt);  -- get the stuff out
-  *	 DLRemove(elt);					   -- removes the element from its list
-  *	 DLFreeElem(elt);				   -- free the element since we don't
-  *										  use it anymore
-  *
-  *
-  * It is also possible to use Dllist objects that are embedded in larger
-  * structures instead of being separately malloc'd.  To do this, use
-  * DLInitElem() to initialize a Dllist field within a larger object.
-  * Don't forget to DLRemove() each field from its list (if any) before
-  * freeing the larger object!
-  *
-  *
-  * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
-  * Portions Copyright (c) 1994, Regents of the University of California
-  *
-  * src/include/lib/dllist.h
-  *
-  *-------------------------------------------------------------------------
-  */
- 
- #ifndef DLLIST_H
- #define DLLIST_H
- 
- struct Dllist;
- struct Dlelem;
- 
- typedef struct Dlelem
- {
- 	struct Dlelem *dle_next;	/* next element */
- 	struct Dlelem *dle_prev;	/* previous element */
- 	void	   *dle_val;		/* value of the element */
- 	struct Dllist *dle_list;	/* what list this element is in */
- } Dlelem;
- 
- typedef struct Dllist
- {
- 	Dlelem	   *dll_head;
- 	Dlelem	   *dll_tail;
- } Dllist;
- 
- extern Dllist *DLNewList(void); /* allocate and initialize a list header */
- extern void DLInitList(Dllist *list);	/* init a header alloced by caller */
- extern void DLFreeList(Dllist *list);	/* free up a list and all the nodes in
- 										 * it */
- extern Dlelem *DLNewElem(void *val);
- extern void DLInitElem(Dlelem *e, void *val);
- extern void DLFreeElem(Dlelem *e);
- extern void DLRemove(Dlelem *e);	/* removes node from list */
- extern void DLAddHead(Dllist *list, Dlelem *node);
- extern void DLAddTail(Dllist *list, Dlelem *node);
- extern Dlelem *DLRemHead(Dllist *list); /* remove and return the head */
- extern Dlelem *DLRemTail(Dllist *list);
- extern void DLMoveToFront(Dlelem *e);	/* move node to front of its list */
- 
- /* These are macros for speed */
- #define DLGetHead(list)  ((list)->dll_head)
- #define DLGetTail(list)  ((list)->dll_tail)
- #define DLGetSucc(elem)  ((elem)->dle_next)
- #define DLGetPred(elem)  ((elem)->dle_prev)
- #define DLGetListHdr(elem)	((elem)->dle_list)
- 
- #define DLE_VAL(elem)	((elem)->dle_val)
- 
- #endif   /* DLLIST_H */
--- 0 ----
*** /dev/null
--- b/src/include/lib/ilist.h
***************
*** 0 ****
--- 1,749 ----
+ /*-------------------------------------------------------------------------
+  *
+  * ilist.h
+  *		integrated/inline doubly- and singly-linked lists
+  *
+  * This implementation is as efficient as possible: the lists don't have
+  * any memory management overhead, because the list pointers are embedded
+  * within some larger structure.
+ 
+  * Also, the doubly-linked lists are always circularly linked, even when empty;
+  * this enables many manipulations to be done without branches, which is
+  * beneficial performance-wise.
+  *
+  * NOTES
+  *		This is intended to be used in situations where memory for a struct and
+  *		its contents already needs to be allocated and the overhead of
+  *		allocating extra list cells for every list element is noticeable.  Thus,
+  *		none of the functions here allocate any memory; they just manipulate
+  *		externally managed memory.	The API for singly/doubly linked lists is
+  *		identical as far as capabilities of both allow.
+  *
+  * EXAMPLES
+  *
+  * An oversimplified example demonstrating how this can be used.  Let's assume
+  * we want to store information about the tables contained in a database.
+  *
+  * #include "lib/ilist.h"
+  *
+  * // Define struct for the databases including a list header that will be used
+  * // to access the nodes in the list later on.
+  * typedef struct my_database
+  * {
+  *		char	   *datname;
+  *		dlist_head	tables;
+  *		// ...
+  * } my_database;
+  *
+  * // Define struct for the tables. Note the list_node element which stores
+  * // information about prev/next list nodes.
+  * typedef struct my_table
+  * {
+  *		char	   *tablename;
+  *		dlist_node	list_node;
+  *		perm_t		permissions;
+  *		// ...
+  * } value_in_a_list;
+  *
+  * // create a database
+  * my_database *db = create_database();
+  *
+  * // and add a few tables to its table list
+  * dlist_push_head(&db->tables, &create_table(db, "a")->list_node);
+  * ...
+  * dlist_push_head(&db->tables, &create_table(db, "b")->list_node);
+  *
+  *
+  * To iterate over the table list, we allocate an iterator element and use
+  * a specialized looping construct.  Inside a dlist_foreach, the iterator's
+  * 'cur' field can be used to access the current element.  iter.cur points to a
+  * 'dlist_node', but most of the time what we want is the actual table
+  * information; dlist_container() gives us that, like so:
+  *
+  * dlist_iter	iter;
+  * dlist_foreach(iter, &db->tables)
+  * {
+  *		my_table   *tbl = dlist_container(my_table, list_node, iter.cur);
+  *		printf("we have a table: %s in database %s\n",
+  *			   val->tablename, db->datname);
+  * }
+  *
+  *
+  * While a simple iteration is useful, we sometimes also want to manipulate
+  * the list while iterating.  There is a different iterator element and looping
+  * construct for that.	Suppose we want to delete tables that meet a certain
+  * criterion:
+  *
+  * dlist_mutable_iter miter;
+  * dlist_foreach_modify(miter, &db->tables)
+  * {
+  *		my_table   *tbl = dlist_container(my_table, list_node, miter.cur);
+  *
+  *		if (!tbl->to_be_deleted)
+  *			continue;		// don't touch this one
+  *
+  *		// unlink the current table from the linked list
+  *		dlist_delete(&db->tables, miter.cur);
+  *		// as these lists never manage memory, we can freely access the table
+  *		// after it's been deleted
+  *		drop_table(db, tbl);
+  * }
+  *
+  * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+  * Portions Copyright (c) 1994, Regents of the University of California
+  *
+  * IDENTIFICATION
+  *		src/include/lib/ilist.h
+  *-------------------------------------------------------------------------
+  */
+ #ifndef ILIST_H
+ #define ILIST_H
+ 
+ /*
+  * Enable for extra debugging. This is rather expensive, so it's not enabled by
+  * default even when USE_ASSERT_CHECKING.
+  */
+ /* #define ILIST_DEBUG */
+ 
+ /*
+  * Node of a doubly linked list.
+  *
+  * Embed this in structs that need to be part of a doubly linked list.
+  */
+ typedef struct dlist_node dlist_node;
+ struct dlist_node
+ {
+ 	dlist_node *prev;
+ 	dlist_node *next;
+ };
+ 
+ /*
+  * Head of a doubly linked list.
+  *
+  * Lists are internally *always* circularly linked, even when empty. Circular
+  * lists have the advantage of not needing any branches in the most common list
+  * manipulations.
+  */
+ typedef struct dlist_head
+ {
+ 	/*
+ 	 * head->next either points to the first element of the list or to &head
+ 	 * if empty.
+ 	 *
+ 	 * head->prev either points to the last element of the list or to &head if
+ 	 * empty.
+ 	 */
+ 	dlist_node	head;
+ } dlist_head;
+ 
+ 
+ /*
+  * Doubly linked list iterator.
+  *
+  * Used as state in dlist_foreach() and dlist_reverse_foreach(). To get the
+  * current element of the iteration use the 'cur' member.
+  *
+  * Iterations using this are *not* allowed to change the list while iterating!
+  *
+  * NB: We use an extra type for this to make it possible to avoid multiple
+  * evaluations of arguments in the dlist_foreach() macro.
+  */
+ typedef struct dlist_iter
+ {
+ 	dlist_node *end;			/* last node we iterate to */
+ 	dlist_node *cur;			/* current element */
+ } dlist_iter;
+ 
+ /*
+  * Doubly linked list iterator allowing some modifications while iterating
+  *
+  * Used as state in dlist_foreach_modify(). To get the current element of the
+  * iteration use the 'cur' member.
+  *
+  * Iterations using this are only allowed to change the list *at the current
+  * point of iteration*. It is fine to delete the current node, but it is *not*
+  * fine to modify other nodes.
+  *
+  * NB: We need a separate type for mutable iterations to avoid having to pass
+  * in two iterators or some other state variable as we need to store the
+  * '->next' node of the current node so it can be deleted or modified by the
+  * user.
+  */
+ typedef struct dlist_mutable_iter
+ {
+ 	dlist_node *end;			/* last node we iterate to */
+ 	dlist_node *cur;			/* current element */
+ 	dlist_node *next;			/* next node we iterate to, so we can delete
+ 								 * cur */
+ } dlist_mutable_iter;
+ 
+ /*
+  * Node of a singly linked list.
+  *
+  * Embed this in structs that need to be part of a singly linked list.
+  */
+ typedef struct slist_node slist_node;
+ struct slist_node
+ {
+ 	slist_node *next;
+ };
+ 
+ /*
+  * Head of a singly linked list.
+  *
+  * Singly linked lists are not circularly linked, in contrast to doubly linked
+  * lists. As no pointer to the last list element and to the previous node needs
+  * to be maintained this doesn't incur any additional branches in the usual
+  * manipulations.
+  */
+ typedef struct slist_head
+ {
+ 	slist_node	head;
+ } slist_head;
+ 
+ /*
+  * Singly linked list iterator
+  *
+  * Used in slist_foreach(). To get the current element of the iteration use the
+  * 'cur' member.
+  *
+  * Do *not* manipulate the list while iterating!
+  *
+  * NB: this wouldn't really need to be an extra struct, we could use a
+  * slist_node * directly. We still use a separate type for consistency.
+  */
+ typedef struct slist_iter
+ {
+ 	slist_node *cur;
+ } slist_iter;
+ 
+ /*
+  * Singly linked list iterator allowing some modifications while iterating
+  *
+  * Used in slist_foreach_modify.
+  *
+  * Iterations using this are allowed to remove the current node and to add more
+  * nodes to the beginning of the list.
+  */
+ typedef struct slist_mutable_iter
+ {
+ 	slist_node *cur;
+ 	slist_node *next;
+ } slist_mutable_iter;
+ 
+ 
+ /* Prototypes for functions too big to be inline */
+ 
+ /* Attention: O(n) */
+ extern void slist_delete(slist_head *head, slist_node *node);
+ 
+ #ifdef ILIST_DEBUG
+ extern void dlist_check(dlist_head *head);
+ extern void slist_check(slist_head *head);
+ #else
+ /*
+  * These seemingly useless casts to void are here to keep the compiler quiet
+  * about the argument being unused in many functions in a non-debug compile,
+  * in which functions the only point of passing the list head pointer is to be
+  * able to run these checks.
+  */
+ #define dlist_check(head)	(void) (head)
+ #define slist_check(head)	(void) (head)
+ #endif   /* ILIST_DEBUG */
+ 
+ /* Static initializers */
+ #define DLIST_STATIC_INIT(name) {{&name.head, &name.head}}
+ #define SLIST_STATIC_INIT(name) {{NULL}}
+ 
+ 
+ /*
+  * We want the functions below to be inline; but if the compiler doesn't
+  * support that, fall back on providing them as regular functions.	See
+  * STATIC_IF_INLINE in c.h.
+  */
+ #ifndef PG_USE_INLINE
+ extern void dlist_init(dlist_head *head);
+ extern bool dlist_is_empty(dlist_head *head);
+ extern void dlist_push_head(dlist_head *head, dlist_node *node);
+ extern void dlist_push_tail(dlist_head *head, dlist_node *node);
+ extern void dlist_insert_after(dlist_head *head,
+ 				   dlist_node *after, dlist_node *node);
+ extern void dlist_insert_before(dlist_head *head,
+ 					dlist_node *before, dlist_node *node);
+ extern void dlist_delete(dlist_head *head, dlist_node *node);
+ extern dlist_node *dlist_pop_head_node(dlist_head *head);
+ extern void dlist_move_head(dlist_head *head, dlist_node *node);
+ extern bool dlist_has_next(dlist_head *head, dlist_node *node);
+ extern bool dlist_has_prev(dlist_head *head, dlist_node *node);
+ extern dlist_node *dlist_next_node(dlist_head *head, dlist_node *node);
+ extern dlist_node *dlist_prev_node(dlist_head *head, dlist_node *node);
+ extern dlist_node *dlist_head_node(dlist_head *head);
+ extern dlist_node *dlist_tail_node(dlist_head *head);
+ 
+ /* dlist macro support functions */
+ extern void *dlist_tail_element_off(dlist_head *head, size_t off);
+ extern void *dlist_head_element_off(dlist_head *head, size_t off);
+ #endif   /* !PG_USE_INLINE */
+ 
+ #if defined(PG_USE_INLINE) || defined(ILIST_INCLUDE_DEFINITIONS)
+ /*
+  * Initialize the head of a list. Previous state will be thrown away without
+  * any cleanup.
+  */
+ STATIC_IF_INLINE void
+ dlist_init(dlist_head *head)
+ {
+ 	head->head.next = head->head.prev = &head->head;
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * Insert a node at the beginning of the list.
+  */
+ STATIC_IF_INLINE void
+ dlist_push_head(dlist_head *head, dlist_node *node)
+ {
+ 	node->next = head->head.next;
+ 	node->prev = &head->head;
+ 	node->next->prev = node;
+ 	head->head.next = node;
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * Inserts a node at the end of the list.
+  */
+ STATIC_IF_INLINE void
+ dlist_push_tail(dlist_head *head, dlist_node *node)
+ {
+ 	node->next = &head->head;
+ 	node->prev = head->head.prev;
+ 	node->prev->next = node;
+ 	head->head.prev = node;
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * Insert a node after another *in the same list*
+  */
+ STATIC_IF_INLINE void
+ dlist_insert_after(dlist_head *head, dlist_node *after, dlist_node *node)
+ {
+ 	dlist_check(head);
+ 	/* XXX: assert 'after' is in 'head'? */
+ 
+ 	node->prev = after;
+ 	node->next = after->next;
+ 	after->next = node;
+ 	node->next->prev = node;
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * Insert a node before another *in the same list*
+  */
+ STATIC_IF_INLINE void
+ dlist_insert_before(dlist_head *head, dlist_node *before, dlist_node *node)
+ {
+ 	dlist_check(head);
+ 	/* XXX: assert 'before' is in 'head'? */
+ 
+ 	node->prev = before->prev;
+ 	node->next = before;
+ 	before->prev = node;
+ 	node->prev->next = node;
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * Delete 'node' from list.
+  *
+  * It is not allowed to delete a 'node' which is is not in the list 'head'
+  */
+ STATIC_IF_INLINE void
+ dlist_delete(dlist_head *head, dlist_node *node)
+ {
+ 	dlist_check(head);
+ 
+ 	node->prev->next = node->next;
+ 	node->next->prev = node->prev;
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * Delete and return the first node from a list.
+  *
+  * Undefined behaviour when the list is empty.  Check with dlist_is_empty if
+  * necessary.
+  */
+ STATIC_IF_INLINE dlist_node *
+ dlist_pop_head_node(dlist_head *head)
+ {
+ 	dlist_node *ret;
+ 
+ 	Assert(&head->head != head->head.next);
+ 
+ 	ret = head->head.next;
+ 	dlist_delete(head, head->head.next);
+ 	return ret;
+ }
+ 
+ /*
+  * Move element from its current position in the list to the head position in
+  * the same list.
+  *
+  * Undefined behaviour if 'node' is not already part of the list.
+  */
+ STATIC_IF_INLINE void
+ dlist_move_head(dlist_head *head, dlist_node *node)
+ {
+ 	/* fast path if it's already at the head */
+ 	if (head->head.next == node)
+ 		return;
+ 
+ 	dlist_delete(head, node);
+ 	dlist_push_head(head, node);
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * Check whether the passed node is the last element in the list.
+  */
+ STATIC_IF_INLINE bool
+ dlist_has_next(dlist_head *head, dlist_node *node)
+ {
+ 	return node->next != &head->head;
+ }
+ 
+ /*
+  * Check whether the passed node is the first element in the list.
+  */
+ STATIC_IF_INLINE bool
+ dlist_has_prev(dlist_head *head, dlist_node *node)
+ {
+ 	return node->prev != &head->head;
+ }
+ 
+ /*
+  * Return the next node in the list.
+  *
+  * Undefined behaviour when no next node exists.  Use dlist_has_next to make
+  * sure.
+  */
+ STATIC_IF_INLINE dlist_node *
+ dlist_next_node(dlist_head *head, dlist_node *node)
+ {
+ 	Assert(dlist_has_next(head, node));
+ 	return node->next;
+ }
+ 
+ /*
+  * Return previous node in the list.
+  *
+  * Undefined behaviour when no prev node exists.  Use dlist_has_prev to make
+  * sure.
+  */
+ STATIC_IF_INLINE dlist_node *
+ dlist_prev_node(dlist_head *head, dlist_node *node)
+ {
+ 	Assert(dlist_has_prev(head, node));
+ 	return node->prev;
+ }
+ 
+ /*
+  * Return whether the list is empty.
+  */
+ STATIC_IF_INLINE bool
+ dlist_is_empty(dlist_head *head)
+ {
+ 	return head->head.next == &(head->head);
+ }
+ 
+ /* internal support function */
+ STATIC_IF_INLINE void *
+ dlist_head_element_off(dlist_head *head, size_t off)
+ {
+ 	Assert(!dlist_is_empty(head));
+ 	return (char *) head->head.next - off;
+ }
+ 
+ /*
+  * Return the first node in the list.
+  *
+  * Use dlist_is_empty to make sure the list is not empty if not sure.
+  */
+ STATIC_IF_INLINE dlist_node *
+ dlist_head_node(dlist_head *head)
+ {
+ 	return dlist_head_element_off(head, 0);
+ }
+ 
+ /* internal support function */
+ STATIC_IF_INLINE void *
+ dlist_tail_element_off(dlist_head *head, size_t off)
+ {
+ 	Assert(!dlist_is_empty(head));
+ 	return (char *) head->head.prev - off;
+ }
+ 
+ /*
+  * Return the last node in the list.
+  *
+  * Use dlist_is_empty to make sure the list is not empty if not sure.
+  */
+ STATIC_IF_INLINE dlist_node *
+ dlist_tail_node(dlist_head *head)
+ {
+ 	return dlist_tail_element_off(head, 0);
+ }
+ #endif   /* PG_USE_INLINE || ILIST_INCLUDE_DEFINITIONS */
+ 
+ /*
+  * Return the containing struct of 'type' where 'membername' is the dlist_node
+  * pointed at by 'ptr'.
+  *
+  * This is used to convert a dlist_node * back to its containing struct.
+  *
+  * Note that AssertVariableIsOfTypeMacro is a compile time only check, so we
+  * don't have multiple evaluation dangers here.
+  */
+ #define dlist_container(type, membername, ptr)								 \
+ 	(AssertVariableIsOfTypeMacro(ptr, dlist_node *),						 \
+ 	 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),	 \
+ 	 ((type *)((char *)(ptr) - offsetof(type, membername))))
+ 
+ /*
+  * Return the value of first element in the list.
+  *
+  * The list must not be empty.
+  *
+  * Note that AssertVariableIsOfTypeMacro is a compile time only check, so we
+  * don't have multiple evaluation dangers here.
+  */
+ #define dlist_head_element(type, membername, ptr)							 \
+ 	(AssertVariableIsOfTypeMacro(((type*) NULL)->membername, dlist_node),	 \
+ 	 ((type *)dlist_get_head_off(ptr, offsetof(type, membername))))
+ 
+ /*
+  * Return the value of first element in the list.
+  *
+  * The list must not be empty.
+  *
+  * Note that AssertVariableIsOfTypeMacro is a compile time only check, so we
+  * don't have multiple evaluation dangers here.
+  */
+ #define dlist_tail_element(type, membername, ptr)							 \
+ 	(AssertVariableIsOfTypeMacro(((type*) NULL)->membername, dlist_node),	 \
+ 	 ((type *)dlist_tail_element_off(ptr, offsetof(type, membername))))
+ 
+ /*
+  * Iterate through the list pointed at by 'ptr' storing the state in 'iter'.
+  *
+  * Access the current element with iter.cur.
+  *
+  * It is *not* allowed to manipulate the list during iteration.
+  */
+ #define dlist_foreach(iter, ptr)											 \
+ 	AssertVariableIsOfType(iter, dlist_iter);								 \
+ 	AssertVariableIsOfType(ptr, dlist_head *);								 \
+ 	for (iter.end = &(ptr)->head, iter.cur = iter.end->next;				 \
+ 		 iter.cur != iter.end;												 \
+ 		 iter.cur = iter.cur->next)
+ 
+ /*
+  * Iterate through the list pointed at by 'ptr' storing the state in 'iter'.
+  *
+  * Access the current element with iter.cur.
+  *
+  * It is allowed to delete the current element from the list. Every other
+  * manipulation can lead to corruption.
+  */
+ #define dlist_foreach_modify(iter, ptr)										 \
+ 	AssertVariableIsOfType(iter, dlist_mutable_iter);						 \
+ 	AssertVariableIsOfType(ptr, dlist_head *);								 \
+ 	for (iter.end = &(ptr)->head, iter.cur = iter.end->next,				 \
+ 			 iter.next = iter.cur->next;									 \
+ 		 iter.cur != iter.end;												 \
+ 		 iter.cur = iter.next, iter.next = iter.cur->next)
+ 
+ /*
+  * Iterate through the list in reverse order.
+  *
+  * It is *not* allowed to manipulate the list during iteration.
+  */
+ #define dlist_reverse_foreach(iter, ptr)									 \
+ 	AssertVariableIsOfType(iter, dlist_iter);								 \
+ 	AssertVariableIsOfType(ptr, dlist_head *);								 \
+ 	for (iter.end = &(ptr)->head, iter.cur = iter.end->prev;				 \
+ 		 iter.cur != iter.end;												 \
+ 		 iter.cur = iter.cur->prev)
+ 
+ 
+ /*
+  * We want the functions below to be inline; but if the compiler doesn't
+  * support that, fall back on providing them as regular functions.	See
+  * STATIC_IF_INLINE in c.h.
+  */
+ #ifndef PG_USE_INLINE
+ extern void slist_init(slist_head *head);
+ extern bool slist_is_empty(slist_head *head);
+ extern slist_node *slist_head_node(slist_head *head);
+ extern void slist_push_head(slist_head *head, slist_node *node);
+ extern slist_node *slist_pop_head_node(slist_head *head);
+ extern void slist_insert_after(slist_head *head,
+ 				   slist_node *after, slist_node *node);
+ extern bool slist_has_next(slist_head *head, slist_node *node);
+ extern slist_node *slist_next_node(slist_head *head, slist_node *node);
+ 
+ /* slist macro support function */
+ extern void *slist_head_element_off(slist_head *head, size_t off);
+ #endif
+ 
+ #if defined(PG_USE_INLINE) || defined(ILIST_INCLUDE_DEFINITIONS)
+ /*
+  * Initialize a singly linked list.
+  */
+ STATIC_IF_INLINE void
+ slist_init(slist_head *head)
+ {
+ 	head->head.next = NULL;
+ 
+ 	slist_check(head);
+ }
+ 
+ /*
+  * Is the list empty?
+  */
+ STATIC_IF_INLINE bool
+ slist_is_empty(slist_head *head)
+ {
+ 	slist_check(head);
+ 
+ 	return head->head.next == NULL;
+ }
+ 
+ /* internal support function */
+ STATIC_IF_INLINE void *
+ slist_head_element_off(slist_head *head, size_t off)
+ {
+ 	Assert(!slist_is_empty(head));
+ 	return (char *) head->head.next - off;
+ }
+ 
+ /*
+  * Push 'node' as the new first node in the list, pushing the original head to
+  * the second position.
+  */
+ STATIC_IF_INLINE void
+ slist_push_head(slist_head *head, slist_node *node)
+ {
+ 	node->next = head->head.next;
+ 	head->head.next = node;
+ 
+ 	slist_check(head);
+ }
+ 
+ /*
+  * Remove and return the first node in the list
+  *
+  * Undefined behaviour if the list is empty.
+  */
+ STATIC_IF_INLINE slist_node *
+ slist_pop_head_node(slist_head *head)
+ {
+ 	slist_node *node;
+ 
+ 	Assert(!slist_is_empty(head));
+ 
+ 	node = head->head.next;
+ 	head->head.next = head->head.next->next;
+ 
+ 	slist_check(head);
+ 
+ 	return node;
+ }
+ 
+ /*
+  * Insert a new node after another one
+  *
+  * Undefined behaviour if 'after' is not part of the list already.
+  */
+ STATIC_IF_INLINE void
+ slist_insert_after(slist_head *head, slist_node *after,
+ 				   slist_node *node)
+ {
+ 	node->next = after->next;
+ 	after->next = node;
+ 
+ 	slist_check(head);
+ }
+ 
+ /*
+  * Return whether 'node' has a following node
+  */
+ STATIC_IF_INLINE bool
+ slist_has_next(slist_head *head,
+ 			   slist_node *node)
+ {
+ 	slist_check(head);
+ 
+ 	return node->next != NULL;
+ }
+ #endif   /* PG_USE_INLINE || ILIST_INCLUDE_DEFINITIONS */
+ 
+ /*
+  * Return the containing struct of 'type' where 'membername' is the slist_node
+  * pointed at by 'ptr'.
+  *
+  * This is used to convert a slist_node * back to its containing struct.
+  *
+  * Note that AssertVariableIsOfTypeMacro is a compile time only check, so we
+  * don't have multiple evaluation dangers here.
+  */
+ #define slist_container(type, membername, ptr)								 \
+ 	(AssertVariableIsOfTypeMacro(ptr, slist_node *),						 \
+ 	 AssertVariableIsOfTypeMacro(((type*)NULL)->membername, slist_node),	 \
+ 	 ((type *)((char *)(ptr) - offsetof(type, membername))))
+ 
+ /*
+  * Return the value of first element in the list.
+  */
+ #define slist_head_element(type, membername, ptr)							 \
+ 	(AssertVariableIsOfTypeMacro(((type*)NULL)->membername, slist_node),	 \
+ 	 slist_head_element_off(ptr, offsetoff(type, membername)))
+ 
+ /*
+  * Iterate through the list 'ptr' using the iterator 'iter'.
+  *
+  * It is *not* allowed to manipulate the list during iteration.
+  */
+ #define slist_foreach(iter, ptr)											 \
+ 	AssertVariableIsOfType(iter, slist_iter);								 \
+ 	AssertVariableIsOfType(ptr, slist_head *);								 \
+ 	for (iter.cur = (ptr)->head.next;										 \
+ 		 iter.cur != NULL;													 \
+ 		 iter.cur = iter.cur->next)
+ 
+ /*
+  * Iterate through the list 'ptr' using the iterator 'iter' allowing some
+  * modifications.
+  *
+  * It is allowed to delete the current element from the list and add new nodes
+  * before the current position. Other manipulations can lead to corruption.
+  */
+ #define slist_foreach_modify(iter, ptr)										 \
+ 	AssertVariableIsOfType(iter, slist_mutable_iter);						 \
+ 	AssertVariableIsOfType(ptr, slist_head *);								 \
+ 	for (iter.cur = (ptr)->head.next,										 \
+ 			 iter.next = iter.cur ? iter.cur->next : NULL;					 \
+ 		iter.cur != NULL;													 \
+ 		iter.cur = iter.next, iter.next = iter.next ? iter.next->next : NULL)
+ 
+ #endif   /* ILIST_H */
*** a/src/include/utils/catcache.h
--- b/src/include/utils/catcache.h
***************
*** 22,28 ****
  
  #include "access/htup.h"
  #include "access/skey.h"
! #include "lib/dllist.h"
  #include "utils/relcache.h"
  
  /*
--- 22,28 ----
  
  #include "access/htup.h"
  #include "access/skey.h"
! #include "lib/ilist.h"
  #include "utils/relcache.h"
  
  /*
***************
*** 37,43 ****
  typedef struct catcache
  {
  	int			id;				/* cache identifier --- see syscache.h */
! 	struct catcache *cc_next;	/* link to next catcache */
  	const char *cc_relname;		/* name of relation the tuples come from */
  	Oid			cc_reloid;		/* OID of relation the tuples come from */
  	Oid			cc_indexoid;	/* OID of index matching cache keys */
--- 37,43 ----
  typedef struct catcache
  {
  	int			id;				/* cache identifier --- see syscache.h */
! 	slist_node	cc_next;		/* list link */
  	const char *cc_relname;		/* name of relation the tuples come from */
  	Oid			cc_reloid;		/* OID of relation the tuples come from */
  	Oid			cc_indexoid;	/* OID of index matching cache keys */
***************
*** 51,57 **** typedef struct catcache
  	ScanKeyData cc_skey[CATCACHE_MAXKEYS];		/* precomputed key info for
  												 * heap scans */
  	bool		cc_isname[CATCACHE_MAXKEYS];	/* flag "name" key columns */
! 	Dllist		cc_lists;		/* list of CatCList structs */
  #ifdef CATCACHE_STATS
  	long		cc_searches;	/* total # searches against this cache */
  	long		cc_hits;		/* # of matches against existing entry */
--- 51,57 ----
  	ScanKeyData cc_skey[CATCACHE_MAXKEYS];		/* precomputed key info for
  												 * heap scans */
  	bool		cc_isname[CATCACHE_MAXKEYS];	/* flag "name" key columns */
! 	dlist_head	cc_lists;		/* list of CatCList structs */
  #ifdef CATCACHE_STATS
  	long		cc_searches;	/* total # searches against this cache */
  	long		cc_hits;		/* # of matches against existing entry */
***************
*** 66,72 **** typedef struct catcache
  	long		cc_lsearches;	/* total # list-searches */
  	long		cc_lhits;		/* # of matches against existing lists */
  #endif
! 	Dllist		cc_bucket[1];	/* hash buckets --- VARIABLE LENGTH ARRAY */
  } CatCache;						/* VARIABLE LENGTH STRUCT */
  
  
--- 66,72 ----
  	long		cc_lsearches;	/* total # list-searches */
  	long		cc_lhits;		/* # of matches against existing lists */
  #endif
! 	dlist_head	cc_bucket[1];	/* hash buckets --- VARIABLE LENGTH ARRAY */
  } CatCache;						/* VARIABLE LENGTH STRUCT */
  
  
***************
*** 77,87 **** typedef struct catctup
  	CatCache   *my_cache;		/* link to owning catcache */
  
  	/*
! 	 * Each tuple in a cache is a member of a Dllist that stores the elements
! 	 * of its hash bucket.	We keep each Dllist in LRU order to speed repeated
  	 * lookups.
  	 */
! 	Dlelem		cache_elem;		/* list member of per-bucket list */
  
  	/*
  	 * The tuple may also be a member of at most one CatCList.	(If a single
--- 77,88 ----
  	CatCache   *my_cache;		/* link to owning catcache */
  
  	/*
! 	 * Each tuple in a cache is a member of a dlist that stores the elements
! 	 * of its hash bucket.	We keep each dlist in LRU order to speed repeated
  	 * lookups.
  	 */
! 	dlist_node	cache_elem;		/* list member of per-bucket list */
! 	dlist_head *cache_bucket;	/* containing bucket dlist */
  
  	/*
  	 * The tuple may also be a member of at most one CatCList.	(If a single
***************
*** 139,145 **** typedef struct catclist
  	 * might not be true during bootstrap or recovery operations. (namespace.c
  	 * is able to save some cycles when it is true.)
  	 */
! 	Dlelem		cache_elem;		/* list member of per-catcache list */
  	int			refcount;		/* number of active references */
  	bool		dead;			/* dead but not yet removed? */
  	bool		ordered;		/* members listed in index order? */
--- 140,146 ----
  	 * might not be true during bootstrap or recovery operations. (namespace.c
  	 * is able to save some cycles when it is true.)
  	 */
! 	dlist_node	cache_elem;		/* list member of per-catcache list */
  	int			refcount;		/* number of active references */
  	bool		dead;			/* dead but not yet removed? */
  	bool		ordered;		/* members listed in index order? */
***************
*** 153,159 **** typedef struct catclist
  
  typedef struct catcacheheader
  {
! 	CatCache   *ch_caches;		/* head of list of CatCache structs */
  	int			ch_ntup;		/* # of tuples in all caches */
  } CatCacheHeader;
  
--- 154,160 ----
  
  typedef struct catcacheheader
  {
! 	slist_head	ch_caches;		/* head of list of CatCache structs */
  	int			ch_ntup;		/* # of tuples in all caches */
  } CatCacheHeader;