ilist-4-circular.patch

*** a/src/backend/utils/cache/catcache.c
--- b/src/backend/utils/cache/catcache.c
***************
*** 791,799 **** InitCatCache(int id,
  		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
--- 791,797 ----
  		cp->cc_key[i] = key[i];
  
  	dlist_init(&cp->cc_lists);
! 	MemSet(&cp->cc_bucket, 0, nbuckets * sizeof(dlist_head));
  
  	/*
  	 * new cache is initialized as far as we can go for now. print some
*** a/src/include/lib/ilist.h
--- b/src/include/lib/ilist.h
***************
*** 6,15 ****
   * 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
--- 6,18 ----
   * 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.
!  *
!  * There are two kinds of empty doubly linked lists: those that have been
!  * initialized to NULL, and those that have been initialized to circularity.
!  * The second kind is useful for tight optimization, because there are some
!  * operations that can be done without branches (and thus faster) on lists that
!  * have been initialized to circularity.  Most users don't care all that much,
!  * and so can skip the initialization step until really required.
   *
   * NOTES
   *		This is intended to be used in situations where memory for a struct and
***************
*** 120,137 **** struct dlist_node
  /*
   * 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;
--- 123,141 ----
  /*
   * Head of a doubly linked list.
   *
!  * Non-empty lists are internally circularly linked.  Circular lists have the
!  * advantage of not needing any branches in the most common list manipulations.
!  * An empty list can also be represented as a pair of NULL pointers, making
!  * initialization easier.
   */
  typedef struct dlist_head
  {
  	/*
! 	 * head->next either points to the first element of the list; to &head if
! 	 * it's a circular empty list; or to NULL if empty and not circular.
  	 *
! 	 * head->prev either points to the last element of the list; to &head if
! 	 * it's a circular empty list; or to NULL if empty and not circular.
  	 */
  	dlist_node	head;
  } dlist_head;
***************
*** 265,271 **** extern void slist_check(slist_head *head);
--- 269,277 ----
  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 dlisti_push_head(dlist_head *head, dlist_node *node);
  extern void dlist_push_tail(dlist_head *head, dlist_node *node);
+ extern void dlisti_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,
***************
*** 304,309 **** dlist_init(dlist_head *head)
--- 310,334 ----
  STATIC_IF_INLINE void
  dlist_push_head(dlist_head *head, dlist_node *node)
  {
+ 	if (head->head.next == NULL)
+ 		dlist_init(head);
+ 
+ 	node->next = head->head.next;
+ 	node->prev = &head->head;
+ 	node->next->prev = node;
+ 	head->head.next = node;
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * As above, except assume the list has been initialized to circularity.
+  */
+ STATIC_IF_INLINE void
+ dlisti_push_head(dlist_head *head, dlist_node *node)
+ {
+ 	Assert(head->head.next != NULL);
+ 
  	node->next = head->head.next;
  	node->prev = &head->head;
  	node->next->prev = node;
***************
*** 318,323 **** dlist_push_head(dlist_head *head, dlist_node *node)
--- 343,367 ----
  STATIC_IF_INLINE void
  dlist_push_tail(dlist_head *head, dlist_node *node)
  {
+ 	if (head->head.next == NULL)
+ 		dlist_init(head);
+ 
+ 	node->next = &head->head;
+ 	node->prev = head->head.prev;
+ 	node->prev->next = node;
+ 	head->head.prev = node;
+ 
+ 	dlist_check(head);
+ }
+ 
+ /*
+  * As above, except assume the list has been initialized to circularity.
+  */
+ STATIC_IF_INLINE void
+ dlisti_push_tail(dlist_head *head, dlist_node *node)
+ {
+ 	Assert(head->head.next != NULL);
+ 
  	node->next = &head->head;
  	node->prev = head->head.prev;
  	node->prev->next = node;
***************
*** 379,385 **** dlist_delete(dlist_head *head, dlist_node *node)
  /*
   * 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 *
--- 423,429 ----
  /*
   * 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 *
***************
*** 459,469 **** dlist_prev_node(dlist_head *head, dlist_node *node)
  
  /*
   * 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 */
--- 503,517 ----
  
  /*
   * Return whether the list is empty.
+  *
+  * An empty list has either its first 'next' pointer set to NULL, or to itself.
   */
  STATIC_IF_INLINE bool
  dlist_is_empty(dlist_head *head)
  {
! 	dlist_check(head);
! 
! 	return head->head.next == NULL || head->head.next == &(head->head);
  }
  
  /* internal support function */
***************
*** 553,559 **** dlist_tail_node(dlist_head *head)
  #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)
  
--- 601,608 ----
  #define dlist_foreach(iter, ptr)											 \
  	AssertVariableIsOfType(iter, dlist_iter);								 \
  	AssertVariableIsOfType(ptr, dlist_head *);								 \
! 	for (iter.end = &(ptr)->head,											 \
! 		 iter.cur = iter.end->next ? iter.end->next : iter.end;				 \
  		 iter.cur != iter.end;												 \
  		 iter.cur = iter.cur->next)
  
***************
*** 568,575 **** dlist_tail_node(dlist_head *head)
  #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)
  
--- 617,625 ----
  #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.end->next : iter.end,				 \
! 		 iter.next = iter.cur->next;										 \
  		 iter.cur != iter.end;												 \
  		 iter.cur = iter.next, iter.next = iter.cur->next)