I'm trying to understand Qemu's queue macros: https://github.com/qemu/qemu/blob/stable-4.2/include/qemu/queue.h
What does the following structures do?
typedef struct QTailQLink {
void *tql_next;
struct QTailQLink *tql_prev;
} QTailQLink;
/*
* Tail queue definitions. The union acts as a poor man template, as if
* it were QTailQLink<type>.
*/
#define QTAILQ_HEAD(name, type) \
union name { \
struct type *tqh_first; /* first element */ \
QTailQLink tqh_circ; /* link for circular backwards list */ \
}
ps: I found https://medium.com/@chenfelix/tail-queue-1b23232e4f49 but it's outdated, does not look like Qemu's source now.
Well, a Queue is a structure that stores some elements in an order, and you add on top of them:
a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. Wikipedia
It makes sense to have a head for this queue, so I gues this is what the QTAILQ_HEAD does. You can hold a pointer to the first element. I wonder why not a pointer to the last also. Anyways, you can find the last by traversing the queue elements.
What does not make sense for me is the QTailQLink tqh_circ;. It's some recursive thing, but I don't understand why it's in the head.
Also, why such things exist: QSLIST_INSERT_AFTER, QSLIST_INSERT_HEAD? In a queue, by definition, you can only insert/remove at the tips. These macros make you insert at an arbitrary point.
The comment at the top of the header file defines what the properties of this data structure are:
* A tail queue is headed by a pair of pointers, one to the head of the
* list and the other to the tail of the list. The elements are doubly
* linked so that an arbitrary element can be removed without a need to
* traverse the list. New elements can be added to the list before or
* after an existing element, at the head of the list, or at the end of
* the list. A tail queue may be traversed in either direction.
Why this data structure and why these operations? Because it's a useful set of things to be able to do, and gives more flexibility than for a simple "all you can do is add at the tail and take off at the head" queue.
The header also notes that these macros are borrowed (and renamed) from those in the BSDs; you might want to read the FreeBSD manpage on them for some more detailed information.
More generally, almost nobody really needs to study the internals of these macros, except for educational purposes. If you're just writing QEMU code then you should be able to use the macros this header provides to do the operations like "traverse this queue" without having to care about how they are implemented internally.
If you do want to investigate how the macros are implemented, there are a couple of clever tricks that may be confusing you:
(1) Use of unions -- both the QTAILQ_HEAD() and QTAILQ_ENTRY() define unions, such that some of the fields are overlaid on top of each other, and the same pointer can be accessed in two ways. For instance in a QTAILQ_HEAD, the tqh_circ.tql_next pointer is the same as the qth_first pointer -- but one is a 'void *' and the other is a 'struct type *', so which one is used depends on whether the macro wants to effectively provide some type safety when it's doing an assignment to the pointer.
(2) A data item can be on more than one queue at once. This is done by having the data item's structure have multiple QTAILQ_ENTRY()s in its definition. This means the queue implementation needs to be careful about distinguishing "this is a pointer to a data item" from "this is a pointer to the QTailQLink embedded inside the data item" -- one data item structure could have several QTailQLinks, for different lists it could be on.
(3) Reusing the same data type in the head that is used in each data item (here, a QTailQLink) can be useful for avoiding having to special case "is this the first item in the list" in the various add/remove/etc operations. This is why it doesn't just use "prev pointer is NULL" for an empty queue.
(The header also defines a "simple queue" which is based on a singly linked list and avoids these clever tricks; it's less flexible and in some situations less efficient.)
My recommendation if you want to investigate further would be to draw out some diagrams of what exactly the data structure looks like, including which pointer fields point to which other places when you have a queue with, say, 3 entries in it.