[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH 5/8] qemu-queue: really simplify QSIMPLEQ
From: |
Paolo Bonzini |
Subject: |
[Qemu-devel] [PATCH 5/8] qemu-queue: really simplify QSIMPLEQ |
Date: |
Mon, 2 Jan 2012 19:00:34 +0100 |
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 <address@hidden>
---
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
- [Qemu-devel] [PATCH 0/8] qemu-queue cleanups, Paolo Bonzini, 2012/01/02
- [Qemu-devel] [PATCH 2/8] block-migration: switch to QTAILQ, Paolo Bonzini, 2012/01/02
- [Qemu-devel] [PATCH 3/8] qed: switch to QTAILQ, Paolo Bonzini, 2012/01/02
- [Qemu-devel] [PATCH 8/8] block: use QSIMPLEQ for the AIO free list, Paolo Bonzini, 2012/01/02
- [Qemu-devel] [PATCH 7/8] coroutine: switch to QSIMPLEQ, Paolo Bonzini, 2012/01/02
- [Qemu-devel] [PATCH 5/8] qemu-queue: really simplify QSIMPLEQ,
Paolo Bonzini <=
- [Qemu-devel] [PATCH 6/8] qemu-queue: drop QCIRCLEQ, Paolo Bonzini, 2012/01/02
- [Qemu-devel] [PATCH 4/8] ccid: switch to QTAILQ, Paolo Bonzini, 2012/01/02
- Re: [Qemu-devel] [Qemu-trivial] [PATCH 0/8] qemu-queue cleanups, Stefan Hajnoczi, 2012/01/03
- Re: [Qemu-devel] [PATCH 0/8] qemu-queue cleanups, Paolo Bonzini, 2012/01/13