Search code examples
clinuxqueuebsd

Why do the TAILQ_INSERT_* macros require an entry to be bound to a variable?


When using the tail queue implementation from sys/queue.h, why does the following code work:

item_t *item = mkitem(...);
TAILQ_INSERT_HEAD(&list, item, entry);

while the following, which should be equivalent, does not:

TAILQ_INSERT_HEAD(&list, mkitem(...), entry);

Minimal working example

#include <stdlib.h>
#include <stdio.h>
#include <sys/queue.h>

typedef struct item item_t;
typedef TAILQ_HEAD(list_head, item) list_head_t;

struct item {
    int value;
    TAILQ_ENTRY(item) entry;
};

static list_head_t items = TAILQ_HEAD_INITIALIZER(items);

static item_t* mkitem(int i) {
    item_t *item = calloc(1, sizeof(item_t));
    item->value = i;
    return item;
}

static void print_tailq() {
    item_t *it;
    TAILQ_FOREACH(it, &items, entry) {
        printf("%d,", it->value);
    }
    printf("\n");
}

int main() {
    item_t *i1, *i2, *i3;

    i1 = mkitem(1);
    i2 = mkitem(2);
    i3 = mkitem(3);

    TAILQ_INSERT_HEAD(&items, i1, entry);
    print_tailq();
    TAILQ_INSERT_HEAD(&items, i2, entry);
    print_tailq();
    TAILQ_INSERT_TAIL(&items, i3, entry);
    print_tailq();

    /* However, this does not work: */
    TAILQ_INSERT_HEAD(&items, mkitem(4), entry);
    print_tailq();
    TAILQ_INSERT_HEAD(&items, mkitem(5), entry);
    print_tailq();
    TAILQ_INSERT_TAIL(&items, mkitem(6), entry);
    print_tailq();

    return 0;
}

As expected, the first three invocations of print_tailq() print out, respectively:

1,
2,1,
2,1,3,

However, the last three invocations show that the list is truncated by TAILQ_INSERT_HEAD, and TAILQ_INSERT_TAIL is essentially a no-op.

4,
5,
5,

Solution

  • From here the implementation of TAILQ_INSERT_HEAD macro TAILQ_INSERT_HEAD(head, elm, field)

    #define TAILQ_INSERT_HEAD(head, elm, field) do {                \
        if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)    \
            (head)->tqh_first->field.tqe_prev =                     \
                &(elm)->field.tqe_next;                             \
        else                                                        \
            (head)->tqh_last = &(elm)->field.tqe_next;              \
        (head)->tqh_first = (elm);                                  \
        (elm)->field.tqe_prev = &(head)->tqh_first;                 \
    } while (0)
    

    It is macro which is being expanded - so it is basically replacing the elm with multiple calls to mkitem(). Passing directly the results of mkitem() invokes erroneous behavior in your code. Using mkitem directly overwrites the previous list (there is a memory leak) and the new list with single element is created - which is printed. You have to use a variable here like you did earlier - otherwise it won't work. Actually you thought that this is a function which it is not. (You will see that man page examples also reflect this idea of using a variable)