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

Ramana Nagasamudram rnagasam at stevens.edu
Sat Sep 1 20:45:28 EDT 2018

I am going through <sys/queue.h> and I find the implementation quite
interesting.  For example, if I wanted to implement a generic
singly-linked list, I would probably try something like this:

              struct sl_node {
                     void *datum;
                     struct sl_node *next;

However, in <sys/queue.h>, it is simply

              #define SLIST_ENTRY(type)         \
              struct {                              \
                     struct type *sle_next;           \

I understand you use these by embedding them in your "object" rather
than storing a reference to your object (using a void *) in some list
node struct.  Could anyone help me understand exactly how this can be
more efficient than the alternative?  Also, <sys/queue.h> seems to be
filled with clever tricks.  Where do I start if I want to learn to
program like this?


P.S. I see <sys/rbtree.h> uses the same technique for implementing
red-black trees.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.stevens.edu/pipermail/cs631apue/attachments/20180902/b9533bf5/attachment.html>

More information about the cs631apue mailing list