From owner-svn-src-stable@FreeBSD.ORG Sun Nov 11 12:21:52 2012 Return-Path: Delivered-To: svn-src-stable@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 7A5A9F49; Sun, 11 Nov 2012 12:21:52 +0000 (UTC) (envelope-from ed@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) by mx1.freebsd.org (Postfix) with ESMTP id 581AD8FC08; Sun, 11 Nov 2012 12:21:52 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.5/8.14.5) with ESMTP id qABCLqZU083149; Sun, 11 Nov 2012 12:21:52 GMT (envelope-from ed@svn.freebsd.org) Received: (from ed@localhost) by svn.freebsd.org (8.14.5/8.14.5/Submit) id qABCLqD9083144; Sun, 11 Nov 2012 12:21:52 GMT (envelope-from ed@svn.freebsd.org) Message-Id: <201211111221.qABCLqD9083144@svn.freebsd.org> From: Ed Schouten Date: Sun, 11 Nov 2012 12:21:52 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-9@freebsd.org Subject: svn commit: r242893 - in stable/9: share/man/man3 sys/sys X-SVN-Group: stable-9 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-stable@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: SVN commit messages for all the -stable branches of the src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 11 Nov 2012 12:21:52 -0000 Author: ed Date: Sun Nov 11 12:21:51 2012 New Revision: 242893 URL: http://svnweb.freebsd.org/changeset/base/242893 Log: MFC r240422, r240426 and r240450: 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, add __containerof(). Compared to __member2struct(), this macro has the following advantages: - It ensures that the type of the pointer is compatible with the member field of the structure (or a void pointer). - It works properly in combination with volatile and const, though unfortunately it drops these qualifiers from the returned value. mdf@ proposed to add the container_of() macro, just like Linux has. Eventually I decided against this, as is included all over the place. It seems container_of() on Linux is specific to the kernel, not userspace. I'd rather not pollute userspace with this. I also thought about adding __container_of(), but this would have two advantages. Xorg seems to already have a __container_of(), which is not compatible with this version. Also, the underscore in the middle conflicts with our existing macros (__offsetof, __rangeof, etc). Modified: stable/9/share/man/man3/Makefile stable/9/share/man/man3/queue.3 stable/9/sys/sys/cdefs.h stable/9/sys/sys/param.h stable/9/sys/sys/queue.h Directory Properties: stable/9/share/man/man3/ (props changed) stable/9/sys/ (props changed) Modified: stable/9/share/man/man3/Makefile ============================================================================== --- stable/9/share/man/man3/Makefile Sun Nov 11 12:12:44 2012 (r242892) +++ stable/9/share/man/man3/Makefile Sun Nov 11 12:21:51 2012 (r242893) @@ -52,6 +52,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 \ Modified: stable/9/share/man/man3/queue.3 ============================================================================== --- stable/9/share/man/man3/queue.3 Sun Nov 11 12:12:44 2012 (r242892) +++ stable/9/share/man/man3/queue.3 Sun Nov 11 12:21:51 2012 (r242893) @@ -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 operatio 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 Modified: stable/9/sys/sys/cdefs.h ============================================================================== --- stable/9/sys/sys/cdefs.h Sun Nov 11 12:12:44 2012 (r242892) +++ stable/9/sys/sys/cdefs.h Sun Nov 11 12:21:51 2012 (r242893) @@ -404,6 +404,22 @@ (__offsetof(type, end) - __offsetof(type, start)) /* + * Given the pointer x to the member m of the struct s, return + * a pointer to the containing structure. When using GCC, we first + * assign pointer x to a local variable, to check that its type is + * compatible with member m. + */ +#if __GNUC_PREREQ__(3, 1) +#define __containerof(x, s, m) ({ \ + const volatile __typeof(((s *)0)->m) *__x = (x); \ + __DEQUALIFY(s *, (const volatile char *)__x - __offsetof(s, m));\ +}) +#else +#define __containerof(x, s, m) \ + __DEQUALIFY(s *, (const volatile char *)(x) - __offsetof(s, m)) +#endif + +/* * Compiler-dependent macros to declare that functions take printf-like * or scanf-like arguments. They are null except for versions of gcc * that are known to support the features properly (old versions of gcc-2 Modified: stable/9/sys/sys/param.h ============================================================================== --- stable/9/sys/sys/param.h Sun Nov 11 12:12:44 2012 (r242892) +++ stable/9/sys/sys/param.h Sun Nov 11 12:21:51 2012 (r242893) @@ -331,8 +331,7 @@ __END_DECLS ((db) << (PAGE_SHIFT - DEV_BSHIFT)) /* - * Given the pointer x to the member m of the struct s, return - * a pointer to the containing structure. + * Old spelling of __containerof(). */ #define member2struct(s, m, x) \ ((struct s *)(void *)((char *)(x) - offsetof(struct s, m))) Modified: stable/9/sys/sys/queue.h ============================================================================== --- stable/9/sys/sys/queue.h Sun Nov 11 12:12:44 2012 (r242892) +++ stable/9/sys/sys/queue.h Sun Nov 11 12:21:51 2012 (r242893) @@ -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 + + + + @@ -287,10 +287,8 @@ struct { \ } while (0) #define STAILQ_LAST(head, type, field) \ - (STAILQ_EMPTY((head)) ? \ - NULL : \ - ((struct type *)(void *) \ - ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) + (STAILQ_EMPTY((head)) ? NULL : \ + __containerof((head)->stqh_last, struct type, field.stqe_next)) #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) @@ -425,6 +423,10 @@ 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 : \ + __containerof((elm)->field.le_prev, struct type, field.le_next)) + #define LIST_REMOVE(elm, field) do { \ QMD_SAVELINK(oldnext, (elm)->field.le_next); \ QMD_SAVELINK(oldprev, (elm)->field.le_prev); \