From owner-freebsd-arch Fri Jan 5 8:54:44 2001 From owner-freebsd-arch@FreeBSD.ORG Fri Jan 5 08:54:41 2001 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mail.wgate.com (mail.wgate.com [38.219.83.4]) by hub.freebsd.org (Postfix) with ESMTP id 68B9F37B400; Fri, 5 Jan 2001 08:54:41 -0800 (PST) Received: from jesup.eng.tvol.net ([10.32.2.26]) by mail.wgate.com with SMTP (Microsoft Exchange Internet Mail Service Version 5.5.2650.21) id CJP4VHG5; Fri, 5 Jan 2001 11:54:46 -0500 Reply-To: Randell Jesup To: Matt Dillon Cc: Peter Wemm , Tony Finch , Kirk McKusick , Alfred Perlstein , Will Andrews , Stephen McKay , phk@FreeBSD.ORG, arch@FreeBSD.ORG Subject: Re: Reinstatement of CIRCLEQ References: <200101050113.f051Dtq61858@mobile.wemm.org> <200101050147.f051lYr96332@earth.backplane.com> From: Randell Jesup Date: 05 Jan 2001 11:56:12 -0500 In-Reply-To: Matt Dillon's message of "Thu, 4 Jan 2001 17:47:34 -0800 (PST)" Message-ID: User-Agent: Gnus/5.0807 (Gnus v5.8.7) Emacs/20.7 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG Matt Dillon 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