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

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 20 Nov, 2013, at 12:32 , Zhihao Yuan <zy%miator.net@localhost> wrote:
> On Wed, Nov 20, 2013 at 12:07 PM, Ken Hornstein 
> <kenh%cmf.nrl.navy.mil@localhost> wrote:
>> I see that at least on MacOS X, sys/queue.h contains the following note:
>> 
>> * Note that circle queues are deprecated, because, as the removal log
>> * in FreeBSD states, "CIRCLEQs are a disgrace to everything Knuth taught
>> * us in Volume 1 Chapter 2. [...] Use TAILQ instead, it provides the same
>> * functionality." Code using them will continue to compile, but they
>> * are no longer documented on the man page.
>> 
>> I don't think I'm knowledgable enough to speak to the accuracy of that
>> comment, but would it be simpler just to migrate all of the code over to
>> TAILQ if the CIRCLEQ ABI is broken as designed?
> 
> It should not be too hard.  Actually, after I mirgrated CIRCLEQ to
> TAILQ in nvi2's code,
> 
>  https://github.com/lichray/nvi2/commits/master?page=9
> 
> FreeBSD base already has absolutely no code using CIRCLEQ.
> 
> So my suggestion is simple: nuke it out.

This functionally works, but the TAILQ data structure is not the same as
the CIRCLEQ data structure (i.e. no ABI compatibility, if that matters; I'm
not quite sure why it does) and unnecessarily penalizes applications which
need to traverse the list in the tail->head direction.

If one were starting this from scratch I don't think there would be
separate TAILQ and CIRCLEQ implementations, there would instead be one
implementation which used the CIRCLEQ data structure but with NULL in
the .cqe_prev member of the head of the list and the .cqe_next member
at the tail.  TAILQ users couldn't tell the difference between this and
the current TAILQ structure in terms of either performance or API, save
for the fact that TAILQ_INSERT_BEFORE() would need to acquire a pointer
to head like the other TAILQ_INSERT_*() macros have, while CIRCLEQ users
wouldn't be penalized for wanting a list which works equally well when
moving in either direction but would get to detect the end of list (in
either direction) with a more conventional comparison to NULL rather
than the disgusting thing they have to do now.

Dennis Ferguson