From: Paolo Bonzini <pbonzini@redhat.com>
To: qemu-devel@nongnu.org
Subject: [Qemu-devel] [PATCH v2 3/5] qemu-queue: drop QCIRCLEQ
Date: Fri, 13 Jan 2012 17:34:03 +0100 [thread overview]
Message-ID: <1326472445-25966-4-git-send-email-pbonzini@redhat.com> (raw)
In-Reply-To: <1326472445-25966-1-git-send-email-pbonzini@redhat.com>
The main advantage of circular lists (the fact that the head node
has the same memory layout as any other node) is completely negated
by the implementation in qemu-queue.h. Not surprisingly, nobody
uses QCIRCLEQ. While this might change if RCU is ever adopted by
QEMU, the QLIST is also RCU-friendly and in fact it is used in a
RCU-like manner by 9pfs already. So, just kill QCIRCLEQ.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
qemu-queue.h | 122 +--------------------------------------------------------
1 files changed, 3 insertions(+), 119 deletions(-)
diff --git a/qemu-queue.h b/qemu-queue.h
index 6021057..92df809 100644
--- a/qemu-queue.h
+++ b/qemu-queue.h
@@ -3,7 +3,7 @@
/*
* Qemu version: Copy from netbsd, removed debug code, removed some of
* the implementations. Left in singly-linked lists, lists, simple
- * queues, tail queues and circular queues.
+ * queues, and tail queues.
*/
/*
@@ -41,8 +41,8 @@
#define QEMU_SYS_QUEUE_H_
/*
- * This file defines five types of data structures: singly-linked lists,
- * lists, simple queues, tail queues, and circular queues.
+ * This file defines four types of data structures: singly-linked lists,
+ * lists, simple queues, and tail queues.
*
* A singly-linked list is headed by a single forward pointer. The
* elements are singly linked for minimum space and pointer manipulation
@@ -75,14 +75,6 @@
* 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.
*
- * A circle 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 circle queue may be traversed in either direction, but has a more
- * complex end of list detection.
- *
* For details on the use of these macros, see the queue(3) manual page.
*/
@@ -432,112 +424,4 @@ struct { \
#define QTAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
-
-/*
- * Circular queue definitions.
- */
-#define QCIRCLEQ_HEAD(name, type) \
-struct name { \
- struct type *cqh_first; /* first element */ \
- struct type *cqh_last; /* last element */ \
-}
-
-#define QCIRCLEQ_HEAD_INITIALIZER(head) \
- { (void *)&head, (void *)&head }
-
-#define QCIRCLEQ_ENTRY(type) \
-struct { \
- struct type *cqe_next; /* next element */ \
- struct type *cqe_prev; /* previous element */ \
-}
-
-/*
- * Circular queue functions.
- */
-#define QCIRCLEQ_INIT(head) do { \
- (head)->cqh_first = (void *)(head); \
- (head)->cqh_last = (void *)(head); \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
- (elm)->field.cqe_next = (listelm)->field.cqe_next; \
- (elm)->field.cqe_prev = (listelm); \
- if ((listelm)->field.cqe_next == (void *)(head)) \
- (head)->cqh_last = (elm); \
- else \
- (listelm)->field.cqe_next->field.cqe_prev = (elm); \
- (listelm)->field.cqe_next = (elm); \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
- (elm)->field.cqe_next = (listelm); \
- (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
- if ((listelm)->field.cqe_prev == (void *)(head)) \
- (head)->cqh_first = (elm); \
- else \
- (listelm)->field.cqe_prev->field.cqe_next = (elm); \
- (listelm)->field.cqe_prev = (elm); \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_INSERT_HEAD(head, elm, field) do { \
- (elm)->field.cqe_next = (head)->cqh_first; \
- (elm)->field.cqe_prev = (void *)(head); \
- if ((head)->cqh_last == (void *)(head)) \
- (head)->cqh_last = (elm); \
- else \
- (head)->cqh_first->field.cqe_prev = (elm); \
- (head)->cqh_first = (elm); \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_INSERT_TAIL(head, elm, field) do { \
- (elm)->field.cqe_next = (void *)(head); \
- (elm)->field.cqe_prev = (head)->cqh_last; \
- if ((head)->cqh_first == (void *)(head)) \
- (head)->cqh_first = (elm); \
- else \
- (head)->cqh_last->field.cqe_next = (elm); \
- (head)->cqh_last = (elm); \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_REMOVE(head, elm, field) do { \
- if ((elm)->field.cqe_next == (void *)(head)) \
- (head)->cqh_last = (elm)->field.cqe_prev; \
- else \
- (elm)->field.cqe_next->field.cqe_prev = \
- (elm)->field.cqe_prev; \
- if ((elm)->field.cqe_prev == (void *)(head)) \
- (head)->cqh_first = (elm)->field.cqe_next; \
- else \
- (elm)->field.cqe_prev->field.cqe_next = \
- (elm)->field.cqe_next; \
-} while (/*CONSTCOND*/0)
-
-#define QCIRCLEQ_FOREACH(var, head, field) \
- for ((var) = ((head)->cqh_first); \
- (var) != (const void *)(head); \
- (var) = ((var)->field.cqe_next))
-
-#define QCIRCLEQ_FOREACH_REVERSE(var, head, field) \
- for ((var) = ((head)->cqh_last); \
- (var) != (const void *)(head); \
- (var) = ((var)->field.cqe_prev))
-
-/*
- * Circular queue access methods.
- */
-#define QCIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
-#define QCIRCLEQ_FIRST(head) ((head)->cqh_first)
-#define QCIRCLEQ_LAST(head) ((head)->cqh_last)
-#define QCIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
-#define QCIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
-
-#define QCIRCLEQ_LOOP_NEXT(head, elm, field) \
- (((elm)->field.cqe_next == (void *)(head)) \
- ? ((head)->cqh_first) \
- : (elm->field.cqe_next))
-#define QCIRCLEQ_LOOP_PREV(head, elm, field) \
- (((elm)->field.cqe_prev == (void *)(head)) \
- ? ((head)->cqh_last) \
- : (elm->field.cqe_prev))
-
#endif /* !QEMU_SYS_QUEUE_H_ */
--
1.7.7.1
next prev parent reply other threads:[~2012-01-13 16:34 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-01-13 16:34 [Qemu-devel] [PATCH v2 0/5] qemu-queue cleanups Paolo Bonzini
2012-01-13 16:34 ` [Qemu-devel] [PATCH v2 1/5] notifier: switch to QLIST Paolo Bonzini
2012-01-13 16:34 ` [Qemu-devel] [PATCH v2 2/5] qemu-queue: add QSLIST Paolo Bonzini
2012-01-13 16:34 ` Paolo Bonzini [this message]
2012-01-13 16:44 ` [Qemu-devel] [PATCH v2 3/5] qemu-queue: drop QCIRCLEQ Peter Maydell
2012-01-13 17:05 ` Paolo Bonzini
2012-01-13 19:11 ` Paolo Bonzini
2012-01-13 16:34 ` [Qemu-devel] [PATCH v2 4/5] coroutine: switch to QSLIST Paolo Bonzini
2012-01-13 16:34 ` [Qemu-devel] [PATCH v2 5/5] block: use QSLIST for the AIO free list Paolo Bonzini
2012-02-17 16:03 ` Anthony Liguori
2012-02-15 9:05 ` [Qemu-devel] [PATCH v2 0/5] qemu-queue cleanups Paolo Bonzini
2012-02-17 18:15 ` Anthony Liguori
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1326472445-25966-4-git-send-email-pbonzini@redhat.com \
--to=pbonzini@redhat.com \
--cc=qemu-devel@nongnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).