From owner-freebsd-arch Thu Jan 4 17:13:39 2001 From owner-freebsd-arch@FreeBSD.ORG Thu Jan 4 17:13:36 2001 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mobile.wemm.org (c1315225-a.plstn1.sfba.home.com [65.0.135.147]) by hub.freebsd.org (Postfix) with ESMTP id 4F04D37B400; Thu, 4 Jan 2001 17:13:35 -0800 (PST) Received: from netplex.com.au (localhost [127.0.0.1]) by mobile.wemm.org (8.11.1/8.11.1) with ESMTP id f051Dtq61858; Thu, 4 Jan 2001 17:13:55 -0800 (PST) (envelope-from peter@netplex.com.au) Message-Id: <200101050113.f051Dtq61858@mobile.wemm.org> X-Mailer: exmh version 2.2 06/23/2000 with nmh-1.0.4 To: Tony Finch Cc: Kirk McKusick , Alfred Perlstein , Will Andrews , Stephen McKay , phk@FreeBSD.ORG, arch@FreeBSD.ORG Subject: Re: Reinstatement of CIRCLEQ In-Reply-To: <20010104222519.Y2140@hand.dotat.at> Date: Thu, 04 Jan 2001 17:13:54 -0800 From: Peter Wemm Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG Tony Finch wrote: > Kirk McKusick wrote: > > From: Alfred Perlstein > > > > You're right, I'm wondering though, would it be possible > > to change TAILQ_PREV(elm, headname, field) to TAILQ_PREV(elm, > > field) by using the offset of 'field' into the struct? > > You could subtract the offset of 'field' from the tqe_prev > > of the next struct right? > > > >You are correct that your suggested change is exactly the > >unportability/headache that I am trying to avoid. > > The Apache Group needed a linked list structure that would allow > insertions before and after a given element without knowing the > address of the list header. Although I wanted to use sys/queue.h it > didn't quite have that functionality so I wrote some "ring" macros > based on code by Dean Gaudet. > > http://www.apache.org/websrc/cvsweb.cgi/~checkout~/apr-util/include/ap_ring.h ?rev=1.5&content-type=text/plain This reminds me a *lot* of the Amiga double linked lists. The one major difference is that the Amiga had a different head/tail node that was constructed in such a way that you didn't need a sentinal. struct list { void *next; void *prev; void *tailprev; } struct node { void *next; void *prev; } The list head was initialized as though it was was two nodes with the "prev" element overlapping. ie: the head had "next" and "prev" as the node next/prev pointers, while the "tail" had "prev" and "tailprev" as the next/ prev pointers. Your beginning and end of list test was (this->next->next == NULL) and the test for first element was (this->prev->prev == NULL). There were no special cases for insert/removal at all. Initialization looked something like this: head->next = &head->prev; head->prev = NULL; head->tailprev = &head->prev; node removal needed no head pointer at all. You could just do REMOVE(node); INSERT_BEFORE(node, node) and INSERT_AFTER(node, node) were also trivial and had no references to the head node or any conditionals. INSERT_FIRST(head, node) was identical to INSERT_AFTER(head, node); INSERT_LAST(head, node) was identical to INSERT_BEFORE(head, node); LIST_EMPTY(head) looked something like this: if (head->next == &head->prev) { list_is_empty; } There were no double pointers, practically no conditionals and it mapped onto the 68000 instruction set beautifully. The only complication compared to macros and traditional linked lists is that the last node did not have a NULL next pointer. The last node pointed to the middle of the 'head' structure. Uh oh, I feel a Terry Lambert Ascii Diagram(TM) coming up: HEAD/TAIL HEAD/TAIL node1 node2 node3 next node3 next -> next -> next -> next -> prev (null) next -> prev (null) <- prev <- prev <- prev <- tailprev prev <- tailprev Note that the HEAD/TAIL structure is the same thing and that I have shown node3 twice to illustrate the wraparound. Note that "node3"->next->next == NULL, even though the next pointer is actually pointing at the "prev" pointer in the head (which happens to be null and "looks like" a valid "node") It was actually very simple and very elegant. I have never seen the polymorphic head/tail/node construct used anywhere else. Cheers, -Peter -- Peter Wemm - peter@FreeBSD.org; peter@yahoo-inc.com; peter@netplex.com.au "All of this is for nothing if we don't go to the stars" - JMS/B5 To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message