Date: Thu, 04 Jan 2001 17:13:54 -0800 From: Peter Wemm <peter@netplex.com.au> To: Tony Finch <dot@dotat.at> Cc: 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: <200101050113.f051Dtq61858@mobile.wemm.org> In-Reply-To: <20010104222519.Y2140@hand.dotat.at>
next in thread | previous in thread | raw e-mail | index | archive | help
Tony Finch wrote: > Kirk McKusick <mckusick@mckusick.com> wrote: > > From: Alfred Perlstein <bright@wintelcom.net> > > > > 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 <sys/queue.h> 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200101050113.f051Dtq61858>