Implement LIST_PREV().

Regular LISTs have been implemented in such a way that the prev-pointer
does not point to the previous element, but to the next-pointer stored
in the previous element. This is done to simplify LIST_REMOVE(). This
macro can be implemented without knowing the address of the list head.

Unfortunately this makes it harder to implement LIST_PREV(), which is
why this macro was never here. Still, it is possible to implement this
macro. If the prev-pointer points to the list head, we return NULL.
Otherwise we simply subtract the offset of the prev-pointer within the
structure.

It's not as efficient as traversing forward of course, but in practice
it shouldn't be that bad. In almost all use cases, people will want to
compare the value returned by LIST_PREV() against NULL, so an optimizing
compiler will not emit code that does more branching than TAILQs.

While there, make the code a bit more readable by introducing
__member2struct(). This makes STAILQ_LAST() far more readable.

MFC after:	1 month

2 files changed, 24 insertions, 3 deletions

diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile
index 7979e0e..ccdc549 100644
--- a/share/man/man3/Makefile
+++ b/share/man/man3/Makefile
@@ -76,6 +76,7 @@ MLINKS+=	queue.3 LIST_EMPTY.3 \
 		queue.3 LIST_INSERT_BEFORE.3 \
 		queue.3 LIST_INSERT_HEAD.3 \
 		queue.3 LIST_NEXT.3 \
+		queue.3 LIST_PREV.3 \
 		queue.3 LIST_REMOVE.3 \
 		queue.3 LIST_SWAP.3 \
 		queue.3 SLIST_EMPTY.3 \
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3
index 76f9464..256fea3 100644
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -32,7 +32,7 @@
 .\"	@(#)queue.3	8.2 (Berkeley) 1/24/94
 .\" $FreeBSD$
 .\"
-.Dd May 13, 2011
+.Dd Sep 12, 2012
 .Dt QUEUE 3
 .Os
 .Sh NAME
@@ -81,6 +81,7 @@
 .Nm LIST_INSERT_BEFORE ,
 .Nm LIST_INSERT_HEAD ,
 .Nm LIST_NEXT ,
+.Nm LIST_PREV ,
 .Nm LIST_REMOVE ,
 .Nm LIST_SWAP ,
 .Nm TAILQ_CONCAT ,
@@ -155,6 +156,7 @@ lists and tail queues
 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
+.Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME"
 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
 .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
 .\"
@@ -248,8 +250,18 @@ Code size and execution time of operations (except for removal) is about
 twice that of the singly-linked data-structures.
 .El
 .Pp
-Linked lists are the simplest of the doubly linked data structures and support
-only the above functionality over singly-linked lists.
+Linked lists are the simplest of the doubly linked data structures.
+They add the following functionality over the above:
+.Bl -enum -compact -offset indent
+.It
+They may be traversed backwards.
+.El
+However:
+.Bl -enum -compact -offset indent
+.It
+To traverse backwards, an entry to begin the traversal and the list in
+which it is contained must be specified.
+.El
 .Pp
 Tail queues add the following functionality:
 .Bl -enum -compact -offset indent
@@ -763,6 +775,14 @@ The macro
 returns the next element in the list, or NULL if this is the last.
 .Pp
 The macro
+.Nm LIST_PREV
+returns the previous element in the list, or NULL if this is the first.
+List
+.Fa head
+must contain element
+.Fa elm .
+.Pp
+The macro
 .Nm LIST_REMOVE
 removes the element
 .Fa elm