tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: in which we present an ugly hack to make sys/queue.h CIRCLEQ work

On Thu, Nov 21, 2013 at 01:16:44AM +0100, Rhialto wrote:
 > Ever since I grokked the elegance of Lists in AmigaOS, I've always
 > wondered why other list implementations do it differently.

One reason is that with Amiga lists is that the list node structure
needs to be at the beginning of the object, and consequently any
particular object can only be on one list. This is ok for exec.library
(and a lot of other stuff) but falls down in many cases. Part of the
supposed advantage of the <sys/queue.h> types is that they don't have
this limitation.

Also, with current C and C compilers you really can't share the null
end pointer; you need two list nodes in the list head, and they need
to specifically be instances of the list node structure. Having only
the one null not only violates the strict-aliasing rules but also a
bunch of regulations about structure member padding and alignment.

 > This initially confusing situation eliminates all special cases for
 > node insertion and removal (and traversal isn't made more complicated).

Traversal is slightly more complicated, in that the start and end
logic has to skip the bookends, and until you're used to the idiom
it's easy to mess this up. And if you do, demons fly out of your

However, in general I agree with you, it's much more elegant.

David A. Holland

Home | Main Index | Thread Index | Old Index