Patchwork [5/8] qemu-queue: really simplify QSIMPLEQ

login
register
mail settings
Submitter Paolo Bonzini
Date Jan. 2, 2012, 6 p.m.
Message ID <1325527237-24146-6-git-send-email-pbonzini@redhat.com>
Download mbox | patch
Permalink /patch/133900/
State New
Headers show

Comments

Paolo Bonzini - Jan. 2, 2012, 6 p.m.
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(-)
Stefan Hajnoczi - Jan. 3, 2012, 12:04 p.m.
On Mon, Jan 02, 2012 at 07:00:34PM +0100, Paolo Bonzini wrote:
> 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.

<pedantic>QSIMPLEQ is no longer a queue if you cannot easily use it in a
FIFO manner.  A queue can efficiently push elements on one end and pop
them from the other end.</pedantic>

Stefan
Peter Maydell - Jan. 13, 2012, 4:04 p.m.
On 2 January 2012 18:00, Paolo Bonzini <pbonzini@redhat.com> wrote:
> 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.

I don't think we should have macros that follow the standard
BSD queue.h naming pattern but don't work the same way...
And as Stefan says, without the INSERT_TAIL operation it isn't
actually a queue any more.

If you actually want a singly linked list I think you should
probably pull in the SLIST macros from BSD queue.h.
(http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/queue.h?rev=1.53)

I think we'll then have the full set of data structures back
again (having added back simple-queues in commit c616bbe1).

-- PMM

Patch

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.
  */