Date: 05 Jan 2001 11:56:12 -0500 From: Randell Jesup <rjesup@wgate.com> To: Matt Dillon <dillon@earth.backplane.com> Cc: Peter Wemm <peter@netplex.com.au>, Tony Finch <dot@dotat.at>, Kirk McKusick <mckusick@mckusick.com>, Alfred Perlstein <bright@wintelcom.net>, Will Andrews <will@physics.purdue.edu>, Stephen McKay <mckay@thehub.com.au>, phk@FreeBSD.ORG, arch@FreeBSD.ORG Subject: Re: Reinstatement of CIRCLEQ Message-ID: <ybuofxm7xar.fsf@jesup.eng.tvol.net.jesup.eng.tvol.net> In-Reply-To: Matt Dillon's message of "Thu, 4 Jan 2001 17:47:34 -0800 (PST)" References: <200101050113.f051Dtq61858@mobile.wemm.org> <200101050147.f051lYr96332@earth.backplane.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Matt Dillon <dillon@earth.backplane.com> writes:
> Basically when implementing a doubly linked list the optimization
> tradeoff comes down to whether you want to remove the conditionals
> from the list scanning routines, or whether you want to remove the
> conditionals from the list insertion and removal routines.
>
> What it comes down to, in a nutshell, is that a circular-list
> implementation can be done that has no more conditionals then a
> non-circular list implementation. You simply have a LIST_EOF() macro
> which for a circular queue compares the 'next node' or 'previous node'
> against &listhead (which you probably already have in the L1 cache
> anyway or can calculate trivially, so no biggy).
The only thing you lose in your implementation (which is, BTW,
quite nice) versus the Amiga-style lists is that you can't test for
LIST_EOF() unless you already have the list pointer. This means there are
cases where for example some code wants to move a node to the head or end
of a list _without knowing what list it's on_ will be tougher, or code that
wants to search the other nodes on the same list without knowing which list
it's on, etc. These are admittedly rare operations (though not unheard
of), and there are user-level solutions (like storing the list it's on in
the user's structure when this sort of thing is needed, or other ways of
obtaining the list pointer).
--
Randell Jesup, Worldgate Communications, ex-Scala, ex-Amiga OS team ('88-94)
rjesup@wgate.com
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ybuofxm7xar.fsf>