What does (*(QUEUE **) &((*(q))[0])) mean in libuv, or How does the queue work?

I am just getting into void pointers and double pointers in C and such to try and make things dynamic. Then I came across this which looks as follows:

typedef void *QUEUE[2];

#define QUEUE_NEXT(q)       (*(QUEUE **) &((*(q))[0]))
#define QUEUE_PREV(q)       (*(QUEUE **) &((*(q))[1]))

There are too many pointers, parens, and references going on for my eyes. Wondering if someone could explain:

what that section (*(QUEUE **) &((*(q)) is doing, and
how this queue can only have two items.

How does this work? Specifically, they have this:

#define QUEUE_INSERT_TAIL(h, q)                             \
  do {                                                      \
    QUEUE_NEXT(q) = (h);                                    \
    QUEUE_PREV(q) = QUEUE_PREV(h);                          \
    QUEUE_PREV_NEXT(q) = (q);                               \
    QUEUE_PREV(h) = (q);                                    \
  }                                                         \
  while (0)

How does that QUEUE_INSERT_TAIL work?

Or for example, I'd also be interested to know what is going on with this:

#define QUEUE_INIT(q)                                                         \
  do {                                                                        \
    QUEUE_NEXT(q) = (q);                                                      \
    QUEUE_PREV(q) = (q);                                                      \
  }                                                                           \
  while (0)

...

QUEUE_INIT(&loop->wq);
QUEUE_INIT(&loop->idle_handles);
QUEUE_INIT(&loop->async_handles);
QUEUE_INIT(&loop->check_handles);
QUEUE_INIT(&loop->prepare_handles);
QUEUE_INIT(&loop->handle_queue);

In the end, they all use QUEUE_NEXT and QUEUE_PREV internally, doing some sort of magic.

Solution

It's an interface to a circular linked list. When you resolve the first macro usage you get:

QUEUE_NEXT(&loop->wq) ->
*(QUEUE **) &((*( &loop->wq ))[0]) ->
*(QUEUE **) &(( loop->wq )[0]) ->
*(QUEUE **) &( loop->wq[0] ) ->
*(QUEUE **) &loop->wq[0]

which effectively is the same as (QUEUE *)( loop->wq[0] ) or just loop->wq[0]

This of course works only if wq is of type QUEUE which is nothing but an array of two void pointers. The author resorted to void* because afaik it's impossible in C to typedef an array of pointers to itself.

And QUEUE_INSERT_TAIL btw is the code to splice two lists. The interesting aspect of this interface is, how do you get to the content of each element? Take a look at the definition of QUEUE_DATA

#define QUEUE_DATA(ptr, type, field)                                          \
  ((type *) ((char *) (ptr) - ((long) &((type *) 0)->field)))

and it's usage

struct user_s {
  int age;
  char* name;

  QUEUE node;
};
user = QUEUE_DATA(q, struct user_s, node);

This resolves to

QUEUE_DATA(q, struct user_s, node) ->
(struct user_s*) ((char *) (q) - ((long) &((struct user_s*) 0)->node))

which effectively returns an address to the containing struct by subtracting the offset of its QUEUE member, so the value of q is adjusted to the address of the struct (here user_s) it is pointing into.