where to find Linux version sys/queue.h header file?

Question

sys/queue.h first appeared in 4.4BSD. Linux has included it in its distribution, but the version seems not up-to-date.

FreeBSD version implements singly-linked lists, singly-linked tail queues, lists and tail queues. Linux version implements lists, tail queues, and circular queues.

I installed libbsd-dev package in my Ubuntu PC and then found BSD version's sys/queue.h in /usr/include/bsd/sys/queue.h.

My questions:

• Where can I find the Linux version of this header file?

• What's the main difference between these two implementations? Is Linux version just a out-dated version of BSD's ?

Answer 1

They share the same ancestry, but it looks like any development that have been done in them diverged a long time ago.

If you want to use it in your project your best bet is to just copy the one you like the most into your project and use that. Don't depend on the system providing it for you. It's just a header file with a bunch of macros and doesn't need a library or any dependencies to work and as such isn't operating system specific at all. I usually take the one from OpenBSD for my projects.

Answer 2

Looks like Linux's version is seriously outdated. CIRCLEQ is (rather strongly) deprecated in BSDs since 2001, and it even got removed from the documentation, even if the implementation is still in queue.h. We are supposed to use TAILQ, which offers the same functionality with better performance/less problems/saner implementation.

Meanwhile, in Linux it's still even documented, but you can find changes in kconfig migrating from CIRCLEQ to TAILQ citing the BSD deprecation.

The concrete problem in CIRCLEQ seems to be that it uses a specific head, different to a list node, but which is anyway linked as a node; so the head pointer has to be kept around and checked at every node access to see if the node turns out to be the head. So there are 2 problems: the checks at every access, and the need to keep the head pointer at hand, taking registers or cache.