diff options
| -rw-r--r-- | share/man/man3/Makefile | 1 | ||||
| -rw-r--r-- | share/man/man3/queue.3 | 26 | ||||
| -rw-r--r-- | sys/sys/cdefs.h | 2 | ||||
| -rw-r--r-- | sys/sys/param.h | 3 | ||||
| -rw-r--r-- | sys/sys/queue.h | 12 |
5 files changed, 35 insertions, 9 deletions
diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile index 7979e0ecbd8a..ccdc54985026 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 76f9464d99c4..256fea3f97db 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 diff --git a/sys/sys/cdefs.h b/sys/sys/cdefs.h index f86a75506239..34b715e0932e 100644 --- a/sys/sys/cdefs.h +++ b/sys/sys/cdefs.h @@ -402,6 +402,8 @@ #endif #define __rangeof(type, start, end) \ (__offsetof(type, end) - __offsetof(type, start)) +#define __member2struct(s, m, x) \ + ((struct s *)(void *)((char *)(x) - __offsetof(struct s, m))) /* * Compiler-dependent macros to declare that functions take printf-like diff --git a/sys/sys/param.h b/sys/sys/param.h index a079980bc076..59c1e3f02e95 100644 --- a/sys/sys/param.h +++ b/sys/sys/param.h @@ -334,8 +334,7 @@ __END_DECLS * Given the pointer x to the member m of the struct s, return * a pointer to the containing structure. */ -#define member2struct(s, m, x) \ - ((struct s *)(void *)((char *)(x) - offsetof(struct s, m))) +#define member2struct(s, m, x) __member2struct(s, m, x) /* * Access a variable length array that has been declared as a fixed diff --git a/sys/sys/queue.h b/sys/sys/queue.h index 274e636c5330..3995ca06bc30 100644 --- a/sys/sys/queue.h +++ b/sys/sys/queue.h @@ -65,7 +65,7 @@ * so that an arbitrary element can be removed without a need to * traverse the list. New elements can be added to the list before * or after an existing element or at the head of the list. A list - * may only be traversed in the forward direction. + * may be traversed in either direction. * * A tail queue is headed by a pair of pointers, one to the head of the * list and the other to the tail of the list. The elements are doubly @@ -85,7 +85,7 @@ * _EMPTY + + + + * _FIRST + + + + * _NEXT + + + + - * _PREV - - - + + * _PREV - + - + * _LAST - - + + * _FOREACH + + + + * _FOREACH_SAFE + + + + @@ -289,8 +289,7 @@ struct { \ #define STAILQ_LAST(head, type, field) \ (STAILQ_EMPTY((head)) ? \ NULL : \ - ((struct type *)(void *) \ - ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) + __member2struct(type, field, (head)->stqh_last)) #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) @@ -425,6 +424,11 @@ struct { \ #define LIST_NEXT(elm, field) ((elm)->field.le_next) +#define LIST_PREV(elm, head, type, field) \ + ((elm)->field.le_prev == &LIST_FIRST((head)) ? \ + NULL : \ + __member2struct(type, field, (elm)->field.le_prev)) + #define LIST_REMOVE(elm, field) do { \ QMD_SAVELINK(oldnext, (elm)->field.le_next); \ QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ |