Date: Thu, 15 Mar 2007 22:04:53 +0300 From: Yar Tikhiy <yar@comp.chem.msu.su> To: Bakul Shah <bakul@bitblocks.com> Cc: arch@freebsd.org Subject: Re: <sys/queue.h> bikeshed proposal Message-ID: <20070315190453.GH28354@comp.chem.msu.su> In-Reply-To: <20070315175924.68E265B49@mail.bitblocks.com> References: <20070315134300.GE28354@comp.chem.msu.su> <20070315175924.68E265B49@mail.bitblocks.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, Mar 15, 2007 at 10:59:24AM -0700, Bakul Shah wrote:
> > On Tue, Mar 13, 2007 at 09:38:05AM +0000, Poul-Henning Kamp wrote:
> > > In message <39968.1173776514@critter.freebsd.dk>, Poul-Henning Kamp writes:
> > > >
> > > >It has always bothered me that some of the TAILQ macros need to
> > > >know the struct name of the header type.
> >
> > Yeah, <sys/queue.h> can present a challenge in understanding an
> > implementation of basic data structures and related algos. :-)
> > You thought that tqe_prev points to the whole entry structure when
> > making the patch, didn't you?
> >
> > Personally, I cannot explain to myself why in the double-linked
> > structs the prev member points to the next member in the previous
> > list element and not to the previous list element itself. Could
> > anybody with CS education explain merits of the current approach?
> > I can only see that now we have to go to the element before the
> > previous one for a pointer to the latter. I'm not going to dispute
> > the current way of things, just curious.
>
> IIRC, the main reason is so that you don't have to know the
> actual type of other things on the list. In particular the
> list head can be just a next/prev ptr pair and not the entire
> object. This is handy, for example, when you have a list
> hanging off another object -- you can remove any list element
> without detaching the entire list from the parent object.
> The queue.h trick is quite clever and useful. To appreciate
> it, try figuring out a solution using Lisp style lists!
> IIRC, your typical CS education doesn't spend much time on
> pragmatics.
Oh, now I seem to understand. Thank you!
Here's how I see it:
Let's assume that the prev member points to the whole previous
element of the list or queue. E.g.:
struct queue_head {
type *first;
type *last;
};
struct queue_entry {
type *next;
type *prev;
}
In this case we can indicate the first element of the queue by prev
being NULL. But then we have no way to get from the first element
to the list head. This means that we have to special case such
operations as removal of the first element and insertion before it.
OTOH, the current approach doesn't suffer from this shortcoming.
BTW, the Linux folks took a different way: They keep pointers to
the list entry structure itself (they call it list_head):
struct list_head {
struct list_head *next, *prev;
};
Consequently, they need to do pointer math to get from an embedded
list_head to the containing structure itself:
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
Linked lists are fun! :-)
Thank you once more for pointing me in the right direction!
--
Yar
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20070315190453.GH28354>