I wrote a header implementing what I called Generic Circular Queues: a
doubly linked list using a single structure and retriving the enclosing
object via the offsetof() macro (similar to CIRCQ in kern_timeout.c).  A
head structure is separately named but contains the same structure.  The
main point is to provide an efficient merge, however it also defines other
operations somewhat differently from queue(9), for efficiency or
convenience.  IMO, it is at least almost always preferrable to the doubly
linked lists in queue(9).

  I put the proposed gcq.h, gcq.3 (and gcq.0) under:
http://www.city-net.com/~darkstar/netbsd/sl

  I wrote this for a new slhci driver that supports bulk transfer and the
Ratoc CFU1U CF USB Host Controller.  This chip only implements individual
transfers and SOF generation, so queue management must be done in the
driver.  The driver is in that directory as well (slhci.diff for full
diffs, sl811hs.c for main driver).  The author of the current slhci
driver, Tetsuya Isaki, asked that I post here about GCQ (the slhci driver
in the above directory is untested on x68k due to a bug in a previous
version).

  I also converted callouts to use GCQ (to_gcq.diff) as another usage
example, which required adding a name argument to constant initializers.
In that patch I also added an inline callout_init_setfunc_zeroed, which
does initialization assuming the structure is already zeroed, converted
some uses of callout_reset to callout_schedule in files with constant
intitializers, removed dead __HAVE_SOFT_INTERRUPT code using constant
initializers, changed a few variable names for consistancy, and removed
callout.h inclusion from a couple of userland programs that did not
actually use it.  I tested this with my custom kernel, but did not test or
compile other kernels.  With GCQ, callout_reset and callout_schedule could
be simplified by removing the test logic since the remove operation is
always valid, but this might cause additional softclock interrupts.

  The callout conversion to GCQ shrinks the kern_timeout.o text segment
from 2062 bytes to 1498, moves 64 bytes from bss to data, and shrinks my
kernel's text segment 544 bytes.

  GCQ could be:
a) adopted as gcq.h as suggested (or a different name)
b) merged into queue.h
c) combined with CIRCQ closer to queue(9) style
d) used minimally only in the slhci driver

Matthew Orgass
darkstar@city-net.com