Gitweb:
http://git.fedorahosted.org/git/?p=gfs2-utils.git;a=commitdiff;h=0d5e2886...
Commit: 0d5e28860c10fb460277088c807558b4d78dced6
Parent: da2bced4ff2a8fa9c95fde8071f2f164c0c1466a
Author: Bob Peterson <rpeterso(a)redhat.com>
AuthorDate: Fri Feb 5 08:39:42 2016 -0500
Committer: Bob Peterson <rpeterso(a)redhat.com>
CommitterDate: Thu Feb 25 10:42:05 2016 -0500
libgfs2: Backport rbtree fixes from upstream
This patch changes the osi_tree.h include to more closely match
the current rbtree implementation in e2fsprogs.
Signed-off-by: Bob Peterson <rpeterso(a)redhat.com>
---
gfs2/include/osi_tree.h | 51 +++++++++++++++++++++++++++-------------------
1 files changed, 30 insertions(+), 21 deletions(-)
diff --git a/gfs2/include/osi_tree.h b/gfs2/include/osi_tree.h
index f0d0768..eca04a0 100644
--- a/gfs2/include/osi_tree.h
+++ b/gfs2/include/osi_tree.h
@@ -12,7 +12,6 @@ struct osi_node {
#define OSI_BLACK 1
struct osi_node *osi_left;
struct osi_node *osi_right;
- struct osi_node *osi_parent;
};
#define osi_parent(r) ((struct osi_node *)((r)->osi_parent_color & ~3))
@@ -21,22 +20,25 @@ struct osi_node {
#define osi_is_black(r) osi_color(r)
#define osi_set_red(r) do { (r)->osi_parent_color &= ~1; } while (0)
#define osi_set_black(r) do { (r)->osi_parent_color |= 1; } while (0)
+#define OSI_EMPTY_NODE(node) (osi_parent(node) == node)
struct osi_root
{
struct osi_node *osi_node;
};
-static inline void osi_set_color(struct osi_node *rb, int color)
-{
- rb->osi_parent_color = (rb->osi_parent_color & ~1) | color;
-}
+#define OSI_EMPTY_ROOT(root) ((root)->osi_node == NULL)
static inline void osi_set_parent(struct osi_node *rb, struct osi_node *p)
{
rb->osi_parent_color = (rb->osi_parent_color & 3) | (unsigned long)p;
}
+static inline void osi_set_color(struct osi_node *rb, int color)
+{
+ rb->osi_parent_color = (rb->osi_parent_color & ~1) | color;
+}
+
static inline void osi_link_node(struct osi_node *node,
struct osi_node *parent,
struct osi_node **osi_link)
@@ -245,33 +247,34 @@ static inline void osi_erase(struct osi_node *node, struct osi_root
*root)
node = node->osi_right;
while ((left = node->osi_left) != NULL)
node = left;
+
+ if (osi_parent(old)) {
+ if (osi_parent(old)->osi_left == old)
+ osi_parent(old)->osi_left = node;
+ else
+ osi_parent(old)->osi_right = node;
+ } else
+ root->osi_node = node;
+
child = node->osi_right;
parent = osi_parent(node);
color = osi_color(node);
- if (child)
- osi_set_parent(child, parent);
if (parent == old) {
- parent->osi_right = child;
parent = node;
- } else
+ } else {
+ if (child)
+ osi_set_parent(child, parent);
parent->osi_left = child;
+ node->osi_right = old->osi_right;
+ osi_set_parent(old->osi_right, node);
+ }
+
node->osi_parent_color = old->osi_parent_color;
- node->osi_right = old->osi_right;
node->osi_left = old->osi_left;
-
- if (osi_parent(old)) {
- if (osi_parent(old)->osi_left == old)
- osi_parent(old)->osi_left = node;
- else
- osi_parent(old)->osi_right = node;
- } else
- root->osi_node = node;
-
osi_set_parent(old->osi_left, node);
- if (old->osi_right)
- osi_set_parent(old->osi_right, node);
+
goto color;
}
@@ -326,6 +329,9 @@ static inline struct osi_node *osi_next(struct osi_node *node)
{
struct osi_node *parent;
+ if (OSI_EMPTY_NODE(node))
+ return NULL;
+
/* If we have a right-hand child, go down and then left as far
as we can. */
if (node->osi_right) {
@@ -351,6 +357,9 @@ static inline struct osi_node *osi_prev(struct osi_node *node)
{
struct osi_node *parent;
+ if (OSI_EMPTY_NODE(node))
+ return NULL;
+
/* If we have a left-hand child, go down and then right as far
as we can. */
if (node->osi_left) {