Merge git://git.infradead.org/~dwmw2/rbtree-2.6

* git://git.infradead.org/~dwmw2/rbtree-2.6:
  [RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistency
  Update UML kernel/physmem.c to use rb_parent() accessor macro
  [RBTREE] Update hrtimers to use rb_parent() accessor macro.
  [RBTREE] Add explicit alignment to sizeof(long) for struct rb_node.
  [RBTREE] Merge colour and parent fields of struct rb_node.
  [RBTREE] Remove dead code in rb_erase()
  [RBTREE] Update JFFS2 to use rb_parent() accessor macro.
  [RBTREE] Update eventpoll.c to use rb_parent() accessor macro.
  [RBTREE] Update key.c to use rb_parent() accessor macro.
  [RBTREE] Update ext3 to use rb_parent() accessor macro.
  [RBTREE] Change rbtree off-tree marking in I/O schedulers.
  [RBTREE] Add accessor macros for colour and parent fields of rb_node

13 files changed, 140 insertions, 136 deletions

diff --git a/arch/um/kernel/physmem.c b/arch/um/kernel/physmem.c
index fc0f0b085ca7..166cb09cae4c 100644
--- a/arch/um/kernel/physmem.c
+++ b/arch/um/kernel/physmem.c
@@ -69,7 +69,7 @@ static void insert_phys_mapping(struct phys_desc *desc)
                 panic("Physical remapping for %p already present",
                       desc->virt);
 
-        rb_link_node(&desc->rb, (*n)->rb_parent, n);
+        rb_link_node(&desc->rb, rb_parent(*n), n);
         rb_insert_color(&desc->rb, &phys_mappings);
 }
 
diff --git a/block/as-iosched.c b/block/as-iosched.c
index a7caf35ca0c2..0c750393be4a 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -353,10 +353,9 @@ static struct request *as_find_arq_hash(struct as_data *ad, sector_t offset)
 /*
  * rb tree support functions
  */
-#define RB_NONE         (2)
 #define RB_EMPTY(root)  ((root)->rb_node == NULL)
-#define ON_RB(node)     ((node)->rb_color != RB_NONE)
-#define RB_CLEAR(node)  ((node)->rb_color = RB_NONE)
+#define ON_RB(node)     (rb_parent(node) != node)
+#define RB_CLEAR(node)  (rb_set_parent(node, node))
 #define rb_entry_arq(node)      rb_entry((node), struct as_rq, rb_node)
 #define ARQ_RB_ROOT(ad, arq)    (&(ad)->sort_list[(arq)->is_sync])
 #define rq_rb_key(rq)           (rq)->sector
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 052b17487625..6200d9b9af28 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -60,14 +60,9 @@ static DEFINE_SPINLOCK(cfq_exit_lock);
 /*
  * rb-tree defines
  */
-#define RB_NONE                 (2)
 #define RB_EMPTY(node)          ((node)->rb_node == NULL)
-#define RB_CLEAR_COLOR(node)    (node)->rb_color = RB_NONE
 #define RB_CLEAR(node)          do {    \
-        (node)->rb_parent = NULL;       \
-        RB_CLEAR_COLOR((node));         \
-        (node)->rb_right = NULL;        \
-        (node)->rb_left = NULL;         \
+                memset(node, 0, sizeof(*node)); \
 } while (0)
 #define RB_CLEAR_ROOT(root)     ((root)->rb_node = NULL)
 #define rb_entry_crq(node)      rb_entry((node), struct cfq_rq, rb_node)
@@ -567,7 +562,6 @@ static inline void cfq_del_crq_rb(struct cfq_rq *crq)
         cfq_update_next_crq(crq);
 
         rb_erase(&crq->rb_node, &cfqq->sort_list);
-        RB_CLEAR_COLOR(&crq->rb_node);
 
         if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list))
                 cfq_del_cfqq_rr(cfqd, cfqq);
diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index 3bd0415a9828..c94de8e12fbf 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -165,10 +165,9 @@ deadline_find_drq_hash(struct deadline_data *dd, sector_t offset)
 /*
  * rb tree support functions
  */
-#define RB_NONE         (2)
 #define RB_EMPTY(root)  ((root)->rb_node == NULL)
-#define ON_RB(node)     ((node)->rb_color != RB_NONE)
-#define RB_CLEAR(node)  ((node)->rb_color = RB_NONE)
+#define ON_RB(node)     (rb_parent(node) != node)
+#define RB_CLEAR(node)  (rb_set_parent(node, node))
 #define rb_entry_drq(node)      rb_entry((node), struct deadline_rq, rb_node)
 #define DRQ_RB_ROOT(dd, drq)    (&(dd)->sort_list[rq_data_dir((drq)->request)])
 #define rq_rb_key(rq)           (rq)->sector
diff --git a/fs/eventpoll.c b/fs/eventpoll.c
index 1b4491cdd115..2695337d4d64 100644
--- a/fs/eventpoll.c
+++ b/fs/eventpoll.c
@@ -337,20 +337,20 @@ static inline int ep_cmp_ffd(struct epoll_filefd *p1,
 /* Special initialization for the rb-tree node to detect linkage */
 static inline void ep_rb_initnode(struct rb_node *n)
 {
-        n->rb_parent = n;
+        rb_set_parent(n, n);
 }
 
 /* Removes a node from the rb-tree and marks it for a fast is-linked check */
 static inline void ep_rb_erase(struct rb_node *n, struct rb_root *r)
 {
         rb_erase(n, r);
-        n->rb_parent = n;
+        rb_set_parent(n, n);
 }
 
 /* Fast check to verify that the item is linked to the main rb-tree */
 static inline int ep_rb_linked(struct rb_node *n)
 {
-        return n->rb_parent != n;
+        return rb_parent(n) != n;
 }
 
 /*
diff --git a/fs/ext3/dir.c b/fs/ext3/dir.c
index f37528ed222e..fbb0d4ed07d4 100644
--- a/fs/ext3/dir.c
+++ b/fs/ext3/dir.c
@@ -284,7 +284,7 @@ static void free_rb_tree_fname(struct rb_root *root)
                  * beginning of the loop and try to free the parent
                  * node.
                  */
-                parent = n->rb_parent;
+                parent = rb_parent(n);
                 fname = rb_entry(n, struct fname, rb_hash);
                 while (fname) {
                         struct fname * old = fname;
diff --git a/fs/jffs2/nodelist.h b/fs/jffs2/nodelist.h
index 7ad8ee043880..b16c60bbcf6e 100644
--- a/fs/jffs2/nodelist.h
+++ b/fs/jffs2/nodelist.h
@@ -315,7 +315,6 @@ static inline struct jffs2_node_frag *frag_last(struct rb_root *root)
         return rb_entry(node, struct jffs2_node_frag, rb);
 }
 
-#define rb_parent(rb) ((rb)->rb_parent)
 #define frag_next(frag) rb_entry(rb_next(&(frag)->rb), struct jffs2_node_frag, rb)
 #define frag_prev(frag) rb_entry(rb_prev(&(frag)->rb), struct jffs2_node_frag, rb)
 #define frag_parent(frag) rb_entry(rb_parent(&(frag)->rb), struct jffs2_node_frag, rb)
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index 5ea4faafa2d3..5fec012b02ed 100644
--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -66,7 +66,7 @@ static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
                         jffs2_free_full_dnode(tn->fn);
                         jffs2_free_tmp_dnode_info(tn);
 
-                        this = this->rb_parent;
+                        this = rb_parent(this);
                         if (!this)
                                 break;
 
@@ -708,12 +708,12 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
                         jffs2_mark_node_obsolete(c, fn->raw);
 
                 BUG_ON(rb->rb_left);
-                if (rb->rb_parent && rb->rb_parent->rb_left == rb) {
+                if (rb_parent(rb) && rb_parent(rb)->rb_left == rb) {
                         /* We were then left-hand child of our parent. We need
                          * to move our own right-hand child into our place. */
                         repl_rb = rb->rb_right;
                         if (repl_rb)
-                                repl_rb->rb_parent = rb->rb_parent;
+                                rb_set_parent(repl_rb, rb_parent(rb));