]> git.proxmox.com Git - mirror_qemu.git/commit
qemu/queue.h: reimplement QTAILQ without pointer-to-pointers
authorPaolo Bonzini <pbonzini@redhat.com>
Thu, 6 Dec 2018 11:01:53 +0000 (12:01 +0100)
committerPaolo Bonzini <pbonzini@redhat.com>
Fri, 11 Jan 2019 14:46:55 +0000 (15:46 +0100)
commit7274f01bb8b81ffe8f13f463b6b0f3b9246c5387
tree3e886e2a3c8f59d66228f8eb7abd2c3c34057f76
parentf95bb39cf1014cfffbc94a1b4cea42864940fe3a
qemu/queue.h: reimplement QTAILQ without pointer-to-pointers

QTAILQ is a doubly linked list, with a pointer-to-pointer to the last
element from the head, and the previous element from each node.

But if you squint enough, QTAILQ becomes a combination of a singly-linked
forwards list, and another singly-linked list which goes backwards and
is circular.  This is the idea that lets QTAILQ implement reverse
iteration: only, because the backwards list points inside the node,
accessing the previous element needs to go two steps back and one
forwards.

What this patch does is implement it in these terms, without actually
changing the in-memory layout at all.  The coexistence of the two lists
is realized by making QTAILQ_HEAD and QTAILQ_ENTRY unions of the forwards
pointer and a generic QTailQLink node.  Thq QTailQLink can walk the list in
both directions; the union is needed so that the forwards pointer can
have the correct type, as a sort of poor man's template.  While there
are other ways to get the same layout without a union, this one has
the advantage of simpler operation in the debugger, because the fields
tqh_first and tqe_next still exist as before the patch.  Those fields are
also used by scripts/qemugdb/mtree.py, so it's a good idea to preserve them.

The advantage of the new representation is that the two-back-one-forward
dance done by backwards accesses can be done all while operating on
QTailQLinks.  No casting to the head struct is needed anymore because,
even though the QTailQLink's forward pointer is a void *, we can use
typeof to recover the correct type.  This patch only changes the
implementation, not the interface.  The next patch will remove the head
struct name from the backwards visit macros.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
include/qemu/queue.h
include/qemu/rcu_queue.h
scripts/cocci-macro-file.h