Introduce a list_dequeue function and rename list_queue to list_enqueue.

2008-11-12  Neal H. Walfield  <neal@gnu.org>

	* list.h (list_queue): Rename from this...
	(list_enqueue): ... to this.  Update users.
	(list_dequeue): New function.
	(LIST_CLASS): Rename the generated queue function accordingly and
	update users.  Generate a stub for dequeueing elements.

5 files changed, 88 insertions, 15 deletions

diff --git a/viengoos/ChangeLog b/viengoos/ChangeLog
index e96eb5a..77819ff 100644
--- a/viengoos/ChangeLog
+++ b/viengoos/ChangeLog
@@ -1,5 +1,13 @@
 2008-11-12  Neal H. Walfield  <neal@gnu.org>
 
+	* list.h (list_queue): Rename from this...
+	(list_enqueue): ... to this.  Update users.
+	(list_dequeue): New function.
+	(LIST_CLASS): Rename the generated queue function accordingly and
+	update users.  Generate a stub for dequeueing elements.
+
+2008-11-12  Neal H. Walfield  <neal@gnu.org>
+
 	* pager.c (reclaim_from): Add victims to the end of the eviction
 	list.
 
diff --git a/viengoos/ager.c b/viengoos/ager.c
index 151ce4d..808a257 100644
--- a/viengoos/ager.c
+++ b/viengoos/ager.c
@@ -618,7 +618,7 @@ ager_loop (void)
 		      int priority = desc->policy.priority;
 		      activity_list_unlink
 			(&desc->activity->frames[priority].active, desc);
-		      activity_list_queue
+		      activity_list_enqueue
 			(&desc->activity->frames[priority].inactive, desc);
 		    }
 		  else
@@ -641,7 +641,7 @@ ager_loop (void)
 		      int priority = desc->policy.priority;
 		      activity_list_unlink
 			(&desc->activity->frames[priority].inactive, desc);
-		      activity_list_queue
+		      activity_list_enqueue
 			(&desc->activity->frames[priority].active, desc);
 
 		      desc->dirty |= dirty;
diff --git a/viengoos/list.h b/viengoos/list.h
index 488e1f5..7fdb206 100644
--- a/viengoos/list.h
+++ b/viengoos/list.h
@@ -175,7 +175,7 @@ list_push (struct list *list, struct list_node *item)
 
 /* Add ITEM to the end of the list LIST.  */
 static inline void
-list_queue (struct list *list, struct list_node *item)
+list_enqueue (struct list *list, struct list_node *item)
 {
   /* We require that when an item is added to a list that its next and
      previous pointers be NULL.  This helps to catch when an item is
@@ -213,6 +213,57 @@ list_queue (struct list *list, struct list_node *item)
   list->count ++;
 }
 
+/* Remove the first item in list LIST and return it.  If the list is
+   empty, returns NULL.  */
+static inline struct list_node *
+list_dequeue (struct list *list)
+{
+  if (! list->head)
+    /* List is empty.  */
+    {
+      assert (list->count == 0);
+      return NULL;
+    }
+
+  struct list_node *item = list_head (list);
+  assert (item);
+  assert (LIST_SENTINEL_P (item->prev));
+
+  /* The new head.  */
+  struct list_node *head = list_next (item);
+  list->head = head;
+
+#ifndef NDEBUG
+  /* The current tail.  It remains pointing at LIST.  */
+  struct list_node *tail = LIST_PTR (item->prev);
+  assert (LIST_PTR (tail->next) == (void *) list);
+#endif
+
+  if (! head)
+    /* The list contained a single element.  It is now empty.  */
+    {
+      /* Next pointers: list -> item -> list.  */
+      assert (LIST_SENTINEL_P (item->next));
+      assert (LIST_PTR (item->next) == (void *) list);
+      /* Previous pointers: item <- item.  */
+      assert (LIST_PTR (item->prev) == item);
+
+      assert (list->count == 1);
+    }
+  else
+    /* Update the new head's previous pointer to point at the list's
+       tail.  */
+    head->prev = item->prev;
+
+  list->count --;
+
+#ifndef NDEBUG
+  item->next = item->prev = NULL;
+#endif
+
+  return item;
+}
+
 /* Insert ITEM after node NODE.  If NODE is NULL, insert at the head
    of the list.  */
 static inline void
@@ -255,6 +306,7 @@ list_unlink (struct list *list, struct list_node *item)
   assert (item->prev);
 
   /* Ensure that ITEM appears on LIST.  */
+#ifndef NCHECK
   assertx (({
 	struct list_node *i = item;
 	while (! LIST_SENTINEL_P (i->next))
@@ -269,6 +321,7 @@ list_unlink (struct list *list, struct list_node *item)
 	LIST_PTR (i->next) == (void *) list;
       }), "list: %p (%s) (%d), item: %p",
     list, list->name, list_count (list), item);
+#endif
 
   if (LIST_SENTINEL_P (item->next) && LIST_SENTINEL_P (item->prev))
     /* The only item on the list.  */
@@ -381,7 +434,8 @@ list_join (struct list *target, struct list *source)
      struct foo *foo_list_prev (struct foo *item);
 
      void foo_list_push (struct foo_list *list, struct foo *object);
-     void foo_list_queue (struct foo_list *list, struct foo *object);
+     void foo_list_enqueue (struct foo_list *list, struct foo *object);
+     void foo_list_dequeue (struct foo_list *list, struct foo *object);
      void foo_list_unlink (struct foo_list *list, struct foo *object);
 
      void foo_list_move (struct foo_list *target, struct foo_list *source);
@@ -460,9 +514,18 @@ list_join (struct list *target, struct list *source)
   }									\
 									\
   static inline void							\
-  name##_list_queue (struct name##_list *list, object_type *object)	\
+  name##_list_enqueue (struct name##_list *list, object_type *object)	\
   {									\
-    list_queue (&list->list, &object->node_field);			\
+    list_enqueue (&list->list, &object->node_field);			\
+  }									\
+									\
+  static inline object_type *						\
+  name##_list_dequeue (struct name##_list *list)			\
+  {									\
+    struct list_node *node = list_dequeue (&list->list);		\
+    if (! node)								\
+      return NULL;							\
+    return (void *) node - offsetof (object_type, node_field);		\
   }									\
 									\
   static inline void							\
diff --git a/viengoos/pager.c b/viengoos/pager.c
index 861f8cc..68a146a 100644
--- a/viengoos/pager.c
+++ b/viengoos/pager.c
@@ -116,18 +116,18 @@ reclaim_from (struct activity *victim, int goal)
 	  object_desc_flush (desc, false);
 	  if (desc->dirty && ! desc->policy.discardable)
 	    {
-	      eviction_list_queue (&victim->eviction_dirty, desc);
+	      eviction_list_enqueue (&victim->eviction_dirty, desc);
 
-	      laundry_list_queue (&laundry, desc);
+	      laundry_list_enqueue (&laundry, desc);
 	      laundry_count ++;
 	    }
 	  else
 	    {
 	      is_clean (desc);
 
-	      eviction_list_queue (&victim->eviction_clean, desc);
+	      eviction_list_enqueue (&victim->eviction_clean, desc);
 
-	      available_list_queue (&available, desc);
+	      available_list_enqueue (&available, desc);
 
 	      if (desc->policy.discardable)
 		discarded ++;
@@ -162,9 +162,9 @@ reclaim_from (struct activity *victim, int goal)
 	  if (desc->dirty && ! desc->policy.discardable)
 	    {
 	      if (! list_node_attached (&desc->laundry_node))
-		laundry_list_queue (&laundry, desc);
+		laundry_list_enqueue (&laundry, desc);
 
-	      eviction_list_queue (&victim->eviction_dirty, desc);
+	      eviction_list_enqueue (&victim->eviction_dirty, desc);
 	      laundry_count ++;
 	    }
 	  else
@@ -172,8 +172,8 @@ reclaim_from (struct activity *victim, int goal)
 	      assert (! list_node_attached (&desc->available_node));
 	      is_clean (desc);
 
-	      available_list_queue (&available, desc);
-	      eviction_list_queue (&victim->eviction_clean, desc);
+	      available_list_enqueue (&available, desc);
+	      eviction_list_enqueue (&victim->eviction_clean, desc);
 
 	      if (desc->policy.discardable)
 		discarded ++;
diff --git a/viengoos/server.c b/viengoos/server.c
index 81f5411..623b743 100644
--- a/viengoos/server.c
+++ b/viengoos/server.c
@@ -134,6 +134,8 @@ server_loop (void)
 	       any message in the last few seconds.  Perhaps there is
 	       a dead-lock.  Dump the rpc trace.  */
 	    {
+	      debug (0, "No IPCs for some time.  Deadlock?");
+
 	      struct thread *thread;
 	      while ((thread = futex_waiter_list_head (&futex_waiters)))
 		{
@@ -1624,7 +1626,7 @@ server_loop (void)
 		object_wait_queue_enqueue (principal, object1, thread);
 
 #ifndef NDEBUG
-		futex_waiter_list_queue (&futex_waiters, thread);
+		futex_waiter_list_enqueue (&futex_waiters, thread);
 #endif
 
 		/* Don't reply.  */