From: Jens Axboe <axboe@suse.de>
To: linux-kernel@vger.kernel.org
Cc: Jens Axboe <axboe@suse.de>
Subject: [PATCH] 2/15 rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev
Date: Thu, 13 Jul 2006 14:46:25 +0200 [thread overview]
Message-ID: <11527947981091-git-send-email-axboe@suse.de> (raw)
In-Reply-To: <11527947982769-git-send-email-axboe@suse.de>
The conditions got reserved. Also make rb_next() and rb_prev() check
for the empty condition.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/as-iosched.c | 4 ++--
include/linux/rbtree.h | 2 +-
lib/rbtree.c | 6 ++++++
3 files changed, 9 insertions(+), 3 deletions(-)
diff --git a/block/as-iosched.c b/block/as-iosched.c
index 1c44ce3..d677029 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -336,7 +336,7 @@ static void as_add_arq_rb(struct as_data
static inline void as_del_arq_rb(struct as_data *ad, struct as_rq *arq)
{
- if (!RB_EMPTY_NODE(&arq->rb_node)) {
+ if (RB_EMPTY_NODE(&arq->rb_node)) {
WARN_ON(1);
return;
}
@@ -1039,7 +1039,7 @@ static void as_move_to_dispatch(struct a
struct request *rq = arq->request;
const int data_dir = arq->is_sync;
- BUG_ON(!RB_EMPTY_NODE(&arq->rb_node));
+ BUG_ON(RB_EMPTY_NODE(&arq->rb_node));
as_antic_stop(ad);
ad->antic_status = ANTIC_OFF;
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 8d5382e..344bc34 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -133,7 +133,7 @@ #define RB_ROOT (struct rb_root) { NULL,
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node) (rb_parent(node) != node)
+#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
extern void rb_insert_color(struct rb_node *, struct rb_root *);
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 1e55ba1..48499c2 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -322,6 +322,9 @@ struct rb_node *rb_next(struct rb_node *
{
struct rb_node *parent;
+ if (rb_parent(node) == node)
+ return NULL;
+
/* If we have a right-hand child, go down and then left as far
as we can. */
if (node->rb_right) {
@@ -348,6 +351,9 @@ struct rb_node *rb_prev(struct rb_node *
{
struct rb_node *parent;
+ if (rb_parent(node) == node)
+ return NULL;
+
/* If we have a left-hand child, go down and then right as far
as we can. */
if (node->rb_left) {
--
1.4.1.ged0e0
next prev parent reply other threads:[~2006-07-13 12:44 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
2006-07-13 12:46 ` [PATCH] 1/15 elevator: move the backmerging logic into the elevator core Jens Axboe
2006-07-13 12:46 ` Jens Axboe [this message]
2006-07-13 12:46 ` [PATCH] 3/15 elevator: abstract out the rbtree sort handling Jens Axboe
2006-07-13 12:46 ` [PATCH] 4/15 as-iosched: migrate to using the elevator rb functions Jens Axboe
2006-07-13 12:46 ` [PATCH] 5/15 cfq-iosched: " Jens Axboe
2006-07-13 12:46 ` [PATCH] 6/15 deadline-iosched: " Jens Axboe
2006-07-13 12:46 ` [PATCH] 7/15 elevator: introduce a way to reuse rq for internal FIFO handling Jens Axboe
2006-07-13 12:46 ` [PATCH] 8/15 cfq-iosched: convert to using the FIFO elevator defines Jens Axboe
2006-07-13 12:46 ` [PATCH] 9/15 as-iosched: reuse rq for fifo Jens Axboe
2006-07-13 12:46 ` [PATCH] 10/15 as-iosched: remove arq->is_sync member Jens Axboe
2006-07-13 12:46 ` [PATCH] 11/15 deadline-iosched: remove elevator private drq request type Jens Axboe
2006-07-13 12:46 ` [PATCH] 12/15 cfq-iosched: remove the crq flag functions/variable Jens Axboe
2006-07-13 12:46 ` [PATCH] 13/15 Add one more pointer to struct request for IO scheduler usage Jens Axboe
2006-07-13 12:46 ` [PATCH] 14/15 cfq-iosched: kill crq Jens Axboe
2006-07-13 12:46 ` [PATCH] 15/15 as-iosched: kill arq Jens Axboe
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=11527947981091-git-send-email-axboe@suse.de \
--to=axboe@suse.de \
--cc=linux-kernel@vger.kernel.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