On 20 Nov, 2013, at 12:32 , Zhihao Yuan <[email protected]> wrote: > On Wed, Nov 20, 2013 at 12:07 PM, Ken Hornstein <[email protected]> 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
