[Qemu-devel] [PATCH 5/8] qemu-queue: really simplify QSIMPLEQ

[Paolo Bonzini <pbonzini@redhat.com>]

QSIMPLEQ is still relatively heavyweight when used as a free list,
compared to a simple singly-linked list.  One disadvantage is that
it requires an initializer macro, unlike for example QLIST.

The patch removes the double links so that there is a "really really
simple" queue type.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 qemu-queue.h |   57 +++++++++------------------------------------------------
 1 files changed, 9 insertions(+), 48 deletions(-)

diff --git a/qemu-queue.h b/qemu-queue.h
index 2214230..5f5b63a 100644
--- a/qemu-queue.h
+++ b/qemu-queue.h
@@ -51,12 +51,11 @@
  * or after an existing element or at the head of the list. A list
  * may only be traversed in the forward direction.
  *
- * A simple queue is headed by a pair of pointers, one the head of the
- * list and the other to the tail of the list. The elements are singly
- * linked to save space, so elements can only be removed from the
- * head of the list. New elements can be added to the list after
- * an existing element, at the head of the list, or at the end of the
- * list. A simple queue may only be traversed in the forward direction.
+ * A simple queue is headed by a single forward pointer, and the elements
+ * are also singly linked to save space.  Elements can only be removed
+ * from the head of the list. New elements can be added to the list after
+ * an existing element or at the head of the list.   A simple queue may
+ * only be traversed in the forward direction.
  *
  * 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
@@ -166,11 +165,10 @@ struct {                                                                \
 #define QSIMPLEQ_HEAD(name, type)                                       \
 struct name {                                                           \
     struct type *sqh_first;    /* first element */                      \
-    struct type **sqh_last;    /* addr of last next element */          \
 }
 
 #define QSIMPLEQ_HEAD_INITIALIZER(head)                                 \
-    { NULL, &(head).sqh_first }
+    { NULL }
 
 #define QSIMPLEQ_ENTRY(type)                                            \
 struct {                                                                \
@@ -182,43 +180,20 @@ struct {                                                                \
  */
 #define QSIMPLEQ_INIT(head) do {                                        \
     (head)->sqh_first = NULL;                                           \
-    (head)->sqh_last = &(head)->sqh_first;                              \
 } while (/*CONSTCOND*/0)
 
 #define QSIMPLEQ_INSERT_HEAD(head, elm, field) do {                     \
-    if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)            \
-        (head)->sqh_last = &(elm)->field.sqe_next;                      \
+    (elm)->field.sqe_next = (head)->sqh_first;                          \
     (head)->sqh_first = (elm);                                          \
 } while (/*CONSTCOND*/0)
 
-#define QSIMPLEQ_INSERT_TAIL(head, elm, field) do {                     \
-    (elm)->field.sqe_next = NULL;                                       \
-    *(head)->sqh_last = (elm);                                          \
-    (head)->sqh_last = &(elm)->field.sqe_next;                          \
-} while (/*CONSTCOND*/0)
-
 #define QSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {           \
-    if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)    \
-        (head)->sqh_last = &(elm)->field.sqe_next;                      \
+    (elm)->field.sqe_next = (listelm)->field.sqe_next;                  \
     (listelm)->field.sqe_next = (elm);                                  \
 } while (/*CONSTCOND*/0)
 
 #define QSIMPLEQ_REMOVE_HEAD(head, field) do {                          \
-    if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)\
-        (head)->sqh_last = &(head)->sqh_first;                          \
-} while (/*CONSTCOND*/0)
-
-#define QSIMPLEQ_REMOVE(head, elm, type, field) do {                    \
-    if ((head)->sqh_first == (elm)) {                                   \
-        QSIMPLEQ_REMOVE_HEAD((head), field);                            \
-    } else {                                                            \
-        struct type *curelm = (head)->sqh_first;                        \
-        while (curelm->field.sqe_next != (elm))                         \
-            curelm = curelm->field.sqe_next;                            \
-        if ((curelm->field.sqe_next =                                   \
-            curelm->field.sqe_next->field.sqe_next) == NULL)            \
-                (head)->sqh_last = &(curelm)->field.sqe_next;           \
-    }                                                                   \
+     (head)->sqh_first = (head)->sqh_first->field.sqe_next;             \
 } while (/*CONSTCOND*/0)
 
 #define QSIMPLEQ_FOREACH(var, head, field)                              \
@@ -231,20 +206,6 @@ struct {                                                                \
         (var) && ((next = ((var)->field.sqe_next)), 1);                 \
         (var) = (next))
 
-#define QSIMPLEQ_CONCAT(head1, head2) do {                              \
-    if (!QSIMPLEQ_EMPTY((head2))) {                                     \
-        *(head1)->sqh_last = (head2)->sqh_first;                        \
-        (head1)->sqh_last = (head2)->sqh_last;                          \
-        QSIMPLEQ_INIT((head2));                                         \
-    }                                                                   \
-} while (/*CONSTCOND*/0)
-
-#define QSIMPLEQ_LAST(head, type, field)                                \
-    (QSIMPLEQ_EMPTY((head)) ?                                           \
-        NULL :                                                          \
-            ((struct type *)(void *)                                    \
-        ((char *)((head)->sqh_last) - offsetof(struct type, field))))
-
 /*
  * Simple queue access methods.
  */
-- 
1.7.7.1