summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAlan D. Brunelle <alan.brunelle@hp.com>2008-11-10 10:34:02 -0500
committerAlan D. Brunelle <alan.brunelle@hp.com>2008-11-10 10:34:02 -0500
commitcdc033a3e6615142697e99b6be43319b8b8233e9 (patch)
tree2c21d86a2923117546abdf5e43051e2a888f97db
parent57425a8a0c1238a9fc9dbc70a597c4011ea82f31 (diff)
parent07b96824e26286321b99c30526d8d67aca16e584 (diff)
downloadblktrace-cdc033a3e6615142697e99b6be43319b8b8233e9.tar.gz
blktrace-cdc033a3e6615142697e99b6be43319b8b8233e9.tar.bz2
Merge branch 'master' of ssh://alanbrunelle@git.kernel.dk/data/git/blktrace
-rw-r--r--blkparse.c2
-rw-r--r--blktrace.c2
-rw-r--r--rbtree.c195
-rw-r--r--rbtree.h22
4 files changed, 119 insertions, 102 deletions
diff --git a/blkparse.c b/blkparse.c
index 3177a41..d869da6 100644
--- a/blkparse.c
+++ b/blkparse.c
@@ -36,7 +36,7 @@
#include "rbtree.h"
#include "jhash.h"
-static char blkparse_version[] = "0.99.3";
+static char blkparse_version[] = "1.0.0";
struct skip_info {
unsigned long start, end;
diff --git a/blktrace.c b/blktrace.c
index 68a7c70..7e27f14 100644
--- a/blktrace.c
+++ b/blktrace.c
@@ -47,7 +47,7 @@
#include "blktrace.h"
#include "barrier.h"
-static char blktrace_version[] = "0.99.3";
+static char blktrace_version[] = "1.0.0";
/*
* You may want to increase this even more, if you are logging at a high
diff --git a/rbtree.c b/rbtree.c
index 37bc021..6ad800f 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -25,60 +25,66 @@
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
struct rb_node *right = node->rb_right;
+ struct rb_node *parent = rb_parent(node);
if ((node->rb_right = right->rb_left))
- right->rb_left->rb_parent = node;
+ rb_set_parent(right->rb_left, node);
right->rb_left = node;
- if ((right->rb_parent = node->rb_parent))
+ rb_set_parent(right, parent);
+
+ if (parent)
{
- if (node == node->rb_parent->rb_left)
- node->rb_parent->rb_left = right;
+ if (node == parent->rb_left)
+ parent->rb_left = right;
else
- node->rb_parent->rb_right = right;
+ parent->rb_right = right;
}
else
root->rb_node = right;
- node->rb_parent = right;
+ rb_set_parent(node, right);
}
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
{
struct rb_node *left = node->rb_left;
+ struct rb_node *parent = rb_parent(node);
if ((node->rb_left = left->rb_right))
- left->rb_right->rb_parent = node;
+ rb_set_parent(left->rb_right, node);
left->rb_right = node;
- if ((left->rb_parent = node->rb_parent))
+ rb_set_parent(left, parent);
+
+ if (parent)
{
- if (node == node->rb_parent->rb_right)
- node->rb_parent->rb_right = left;
+ if (node == parent->rb_right)
+ parent->rb_right = left;
else
- node->rb_parent->rb_left = left;
+ parent->rb_left = left;
}
else
root->rb_node = left;
- node->rb_parent = left;
+ rb_set_parent(node, left);
}
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
struct rb_node *parent, *gparent;
- while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
+ while ((parent = rb_parent(node)) && rb_is_red(parent))
{
- gparent = parent->rb_parent;
+ gparent = rb_parent(parent);
if (parent == gparent->rb_left)
{
{
register struct rb_node *uncle = gparent->rb_right;
- if (uncle && uncle->rb_color == RB_RED)
+ if (uncle && rb_is_red(uncle))
{
- uncle->rb_color = RB_BLACK;
- parent->rb_color = RB_BLACK;
- gparent->rb_color = RB_RED;
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
node = gparent;
continue;
}
@@ -93,17 +99,17 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
node = tmp;
}
- parent->rb_color = RB_BLACK;
- gparent->rb_color = RB_RED;
+ rb_set_black(parent);
+ rb_set_red(gparent);
__rb_rotate_right(gparent, root);
} else {
{
register struct rb_node *uncle = gparent->rb_left;
- if (uncle && uncle->rb_color == RB_RED)
+ if (uncle && rb_is_red(uncle))
{
- uncle->rb_color = RB_BLACK;
- parent->rb_color = RB_BLACK;
- gparent->rb_color = RB_RED;
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
node = gparent;
continue;
}
@@ -118,13 +124,13 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
node = tmp;
}
- parent->rb_color = RB_BLACK;
- gparent->rb_color = RB_RED;
+ rb_set_black(parent);
+ rb_set_red(gparent);
__rb_rotate_left(gparent, root);
}
}
- root->rb_node->rb_color = RB_BLACK;
+ rb_set_black(root->rb_node);
}
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
@@ -132,43 +138,40 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
{
struct rb_node *other;
- while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
+ while ((!node || rb_is_black(node)) && node != root->rb_node)
{
if (parent->rb_left == node)
{
other = parent->rb_right;
- if (other->rb_color == RB_RED)
+ if (rb_is_red(other))
{
- other->rb_color = RB_BLACK;
- parent->rb_color = RB_RED;
+ rb_set_black(other);
+ rb_set_red(parent);
__rb_rotate_left(parent, root);
other = parent->rb_right;
}
- if ((!other->rb_left ||
- other->rb_left->rb_color == RB_BLACK)
- && (!other->rb_right ||
- other->rb_right->rb_color == RB_BLACK))
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
{
- other->rb_color = RB_RED;
+ rb_set_red(other);
node = parent;
- parent = node->rb_parent;
+ parent = rb_parent(node);
}
else
{
- if (!other->rb_right ||
- other->rb_right->rb_color == RB_BLACK)
+ if (!other->rb_right || rb_is_black(other->rb_right))
{
- register struct rb_node *o_left;
+ struct rb_node *o_left;
if ((o_left = other->rb_left))
- o_left->rb_color = RB_BLACK;
- other->rb_color = RB_RED;
+ rb_set_black(o_left);
+ rb_set_red(other);
__rb_rotate_right(other, root);
other = parent->rb_right;
}
- other->rb_color = parent->rb_color;
- parent->rb_color = RB_BLACK;
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
if (other->rb_right)
- other->rb_right->rb_color = RB_BLACK;
+ rb_set_black(other->rb_right);
__rb_rotate_left(parent, root);
node = root->rb_node;
break;
@@ -177,38 +180,35 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
else
{
other = parent->rb_left;
- if (other->rb_color == RB_RED)
+ if (rb_is_red(other))
{
- other->rb_color = RB_BLACK;
- parent->rb_color = RB_RED;
+ rb_set_black(other);
+ rb_set_red(parent);
__rb_rotate_right(parent, root);
other = parent->rb_left;
}
- if ((!other->rb_left ||
- other->rb_left->rb_color == RB_BLACK)
- && (!other->rb_right ||
- other->rb_right->rb_color == RB_BLACK))
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
{
- other->rb_color = RB_RED;
+ rb_set_red(other);
node = parent;
- parent = node->rb_parent;
+ parent = rb_parent(node);
}
else
{
- if (!other->rb_left ||
- other->rb_left->rb_color == RB_BLACK)
+ if (!other->rb_left || rb_is_black(other->rb_left))
{
register struct rb_node *o_right;
if ((o_right = other->rb_right))
- o_right->rb_color = RB_BLACK;
- other->rb_color = RB_RED;
+ rb_set_black(o_right);
+ rb_set_red(other);
__rb_rotate_left(other, root);
other = parent->rb_left;
}
- other->rb_color = parent->rb_color;
- parent->rb_color = RB_BLACK;
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
if (other->rb_left)
- other->rb_left->rb_color = RB_BLACK;
+ rb_set_black(other->rb_left);
__rb_rotate_right(parent, root);
node = root->rb_node;
break;
@@ -216,7 +216,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
}
}
if (node)
- node->rb_color = RB_BLACK;
+ rb_set_black(node);
}
void rb_erase(struct rb_node *node, struct rb_root *root)
@@ -236,48 +236,41 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
while ((left = node->rb_left) != NULL)
node = left;
child = node->rb_right;
- parent = node->rb_parent;
- color = node->rb_color;
+ parent = rb_parent(node);
+ color = rb_color(node);
if (child)
- child->rb_parent = parent;
- if (parent)
- {
- if (parent->rb_left == node)
- parent->rb_left = child;
- else
- parent->rb_right = child;
- }
- else
- root->rb_node = child;
-
- if (node->rb_parent == old)
+ rb_set_parent(child, parent);
+ if (parent == old) {
+ parent->rb_right = child;
parent = node;
- node->rb_parent = old->rb_parent;
- node->rb_color = old->rb_color;
+ } else
+ parent->rb_left = child;
+
+ node->rb_parent_color = old->rb_parent_color;
node->rb_right = old->rb_right;
node->rb_left = old->rb_left;
- if (old->rb_parent)
+ if (rb_parent(old))
{
- if (old->rb_parent->rb_left == old)
- old->rb_parent->rb_left = node;
+ if (rb_parent(old)->rb_left == old)
+ rb_parent(old)->rb_left = node;
else
- old->rb_parent->rb_right = node;
+ rb_parent(old)->rb_right = node;
} else
root->rb_node = node;
- old->rb_left->rb_parent = node;
+ rb_set_parent(old->rb_left, node);
if (old->rb_right)
- old->rb_right->rb_parent = node;
+ rb_set_parent(old->rb_right, node);
goto color;
}
- parent = node->rb_parent;
- color = node->rb_color;
+ parent = rb_parent(node);
+ color = rb_color(node);
if (child)
- child->rb_parent = parent;
+ rb_set_parent(child, parent);
if (parent)
{
if (parent->rb_left == node)
@@ -322,6 +315,11 @@ struct rb_node *rb_last(struct rb_root *root)
struct rb_node *rb_next(struct rb_node *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) {
@@ -337,14 +335,19 @@ struct rb_node *rb_next(struct rb_node *node)
ancestor is a right-hand child of its parent, keep going
up. First time it's a left-hand child of its parent, said
parent is our 'next' node. */
- while (node->rb_parent && node == node->rb_parent->rb_right)
- node = node->rb_parent;
+ while ((parent = rb_parent(node)) && node == parent->rb_right)
+ node = parent;
- return node->rb_parent;
+ return parent;
}
struct rb_node *rb_prev(struct rb_node *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) {
@@ -356,16 +359,16 @@ struct rb_node *rb_prev(struct rb_node *node)
/* No left-hand children. Go up till we find an ancestor which
is a right-hand child of its parent */
- while (node->rb_parent && node == node->rb_parent->rb_left)
- node = node->rb_parent;
+ while ((parent = rb_parent(node)) && node == parent->rb_left)
+ node = parent;
- return node->rb_parent;
+ return parent;
}
void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_root *root)
{
- struct rb_node *parent = victim->rb_parent;
+ struct rb_node *parent = rb_parent(victim);
/* Set the surrounding nodes to point to the replacement */
if (parent) {
@@ -377,9 +380,9 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
root->rb_node = new;
}
if (victim->rb_left)
- victim->rb_left->rb_parent = new;
+ rb_set_parent(victim->rb_left, new);
if (victim->rb_right)
- victim->rb_right->rb_parent = new;
+ rb_set_parent(victim->rb_right, new);
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
diff --git a/rbtree.h b/rbtree.h
index e722b1e..4c06d98 100644
--- a/rbtree.h
+++ b/rbtree.h
@@ -98,8 +98,7 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
struct rb_node
{
- struct rb_node *rb_parent;
- int rb_color;
+ unsigned long rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
@@ -122,6 +121,22 @@ struct rb_root
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
+#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
+#define rb_color(r) ((r)->rb_parent_color & 1)
+#define rb_is_red(r) (!rb_color(r))
+#define rb_is_black(r) rb_color(r)
+#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
+#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+ rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void rb_set_color(struct rb_node *rb, int color)
+{
+ rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
#define RB_ROOT (struct rb_root) { NULL, }
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
@@ -141,8 +156,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
struct rb_node ** rb_link)
{
- node->rb_parent = parent;
- node->rb_color = RB_RED;
+ node->rb_parent_color = (unsigned long )parent;
node->rb_left = node->rb_right = NULL;
*rb_link = node;