[cs631apue] Data structure implementations in <sys/queue.h>

[Jan Schaumann]

Ramana Nagasamudram <rnagasam at stevens.edu> wrote:
 
> Could anyone help me understand exactly how this can be more efficient
> than the alternative?

I have never looked at this in detail, but my guess is:

By not including a reference to the object, you can more easily allocate
the data structures and align them at compile time.  Note: the
implementation is (almost?) entirely  in macros, so the code is inserted
as is at compile time.  By not including a pointer to the object, and
instead requiring the object to contain the list head struct, you also
yield branchless insertion/deletion in the list: any object can
dereference the next item in the list without having to check the
reference on the object.

The lack of pointers to the object within the list structure ought to
make memory allocation more efficient, which for the purposes of the
slist per the header comments and queue(3) description is desirable.

But honestly, the question would likely be better and more completely
answered by your Data Structures & Algorithms instructor.

>  Also, <sys/queue.h> seems to be filled with clever tricks.  Where do
>  I start if I want to learn to program like this?

You wouldn't. :-)  By and large what we'll do in _this_ class, anyway,
is to stay as far away from clever tricks as possible.  Clever tricks
make code hard(er) to read, understand, debug.  We will focus on boring,
easy to understand and read code.

(However, if you're interested in optimizing your code, Data Structures
& Algorithms is again the best area of expertise to immerse yourself in.
There are several good code-agnostic books on the subject; translating
the efficient algorithm into a given language is something that then
comes with time and experience.  Online communities and groups can help
you practice this, too.)

Hope this helps,
-Jan