Gitweb: http://git.fedorahosted.org/git/cluster.git?p=cluster.git;a=commitdiff;h=b4e... Commit: b4eba17564b216b75eb89f6b06a62b572a69ac2e Parent: 7079b2141b66a78e0484d56025ad3e6c238a021c Author: Bob Peterson bob@ganesha.peterson AuthorDate: Thu Jan 21 12:16:10 2010 -0600 Committer: Bob Peterson rpeterso@redhat.com CommitterDate: Fri Apr 9 23:33:16 2010 -0500
fsck.gfs2: convert dup_list to a rbtree
This patch uses a new include file, osi_tree.h to implement the duplicates list as a red-black tree. This will speed up the duplicate processing considerably.
rhbz#455300 --- gfs2/fsck/fsck.h | 36 ++++- gfs2/fsck/initialize.c | 23 +-- gfs2/fsck/main.c | 2 +- gfs2/fsck/metawalk.c | 31 ++-- gfs2/fsck/metawalk.h | 2 +- gfs2/fsck/pass1b.c | 39 ++--- gfs2/fsck/pass2.c | 8 +- gfs2/fsck/util.c | 53 +++++-- gfs2/fsck/util.h | 2 +- gfs2/include/osi_tree.h | 395 +++++++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 511 insertions(+), 80 deletions(-)
diff --git a/gfs2/fsck/fsck.h b/gfs2/fsck/fsck.h index 5594548..fadb73e 100644 --- a/gfs2/fsck/fsck.h +++ b/gfs2/fsck/fsck.h @@ -14,6 +14,7 @@ #define _FSCK_H
#include "libgfs2.h" +#include "osi_tree.h"
#define FSCK_HASH_SHIFT (13) #define FSCK_HASH_SIZE (1 << FSCK_HASH_SHIFT) @@ -60,6 +61,31 @@ struct dir_status { uint32_t entry_count; };
+struct duptree { + struct osi_node node; + int first_ref_found; /* Has the original reference been found? */ + int refs; + uint64_t block; + osi_list_t ref_inode_list; /* list of inodes referencing a dup block */ + osi_list_t ref_invinode_list; /* list of invalid inodes referencing */ +}; + +enum dup_ref_type { + ref_as_data = 0, + ref_as_meta = 1, + ref_as_ea = 2, + ref_types = 3 +}; + +struct inode_with_dups { + osi_list_t list; + uint64_t block_no; + int dup_count; + int ea_only; + uint64_t parent; + char *name; +}; + enum rgindex_trust_level { /* how far can we trust our RG index? */ blind_faith = 0, /* We'd like to trust the rgindex. We always used to before bz 179069. This should cover most cases. */ @@ -71,12 +97,6 @@ enum rgindex_trust_level { /* how far can we trust our RG index? */ gfs2_grow or something. Count the RGs by hand. */ };
-struct dup_blks { - osi_list_t list; - uint64_t block; - osi_list_t ref_inode_list; -}; - extern struct gfs2_inode *fsck_load_inode(struct gfs2_sbd *sbp, uint64_t block); extern struct gfs2_inode *fsck_inode_get(struct gfs2_sbd *sdp, struct gfs2_buffer_head *bh); @@ -93,9 +113,11 @@ extern int pass3(struct gfs2_sbd *sbp); extern int pass4(struct gfs2_sbd *sbp); extern int pass5(struct gfs2_sbd *sbp); extern int rg_repair(struct gfs2_sbd *sdp, int trust_lvl, int *rg_count); +extern void gfs2_dup_free(void); extern int fsck_query(const char *format, ...) __attribute__((format(printf,1,2))); extern struct dir_info *dirtree_find(uint64_t block); +extern void dup_delete(struct duptree *b); extern void dirtree_delete(struct dir_info *b);
/* FIXME: Hack to get this going for pass2 - this should be pulled out @@ -113,6 +135,6 @@ extern int skip_this_pass, fsck_abort; extern int errors_found, errors_corrected; extern uint64_t last_data_block; extern uint64_t first_data_block; -extern struct dup_blks dup_blocks; +extern struct osi_root dup_blocks;
#endif /* _FSCK_H */ diff --git a/gfs2/fsck/initialize.c b/gfs2/fsck/initialize.c index 7aad96e..48859eb 100644 --- a/gfs2/fsck/initialize.c +++ b/gfs2/fsck/initialize.c @@ -72,17 +72,14 @@ static int block_mounters(struct gfs2_sbd *sbp, int block_em) return 0; }
-static void gfs2_dup_free(void) +void gfs2_dup_free(void) { - struct dup_blks *f; - - while(!osi_list_empty(&dup_blocks.list)) { - f = osi_list_entry(dup_blocks.list.next, struct dup_blks, - list); - while (!osi_list_empty(&f->ref_inode_list)) - osi_list_del(&f->ref_inode_list); - osi_list_del(&f->list); - free(f); + struct osi_node *n; + struct duptree *dt; + + while ((n = osi_first(&dup_blocks))) { + dt = (struct duptree *)n; + dup_delete(dt); } }
@@ -117,10 +114,9 @@ static void empty_super_block(struct gfs2_sbd *sdp) } }
- if (bl) { + if (bl) gfs2_bmap_destroy(sdp, bl); - gfs2_dup_free(); - } + gfs2_dup_free(); }
@@ -411,7 +407,6 @@ static int init_system_inodes(struct gfs2_sbd *sdp) log_crit( _("Please increase your swap space by that amount and run gfs2_fsck again.\n")); goto fail; } - osi_list_init(&dup_blocks.list); return 0; fail: empty_super_block(sdp); diff --git a/gfs2/fsck/main.c b/gfs2/fsck/main.c index 3b5bfac..24f9500 100644 --- a/gfs2/fsck/main.c +++ b/gfs2/fsck/main.c @@ -43,7 +43,7 @@ uint64_t last_data_block; uint64_t first_data_block; const char *prog_name = "gfs2_fsck"; /* needed by libgfs2 */ int preen = 0, force_check = 0; -struct dup_blks dup_blocks; +struct osi_root dup_blocks = (struct osi_root) { NULL, };
/* This function is for libgfs2's sake. */ void print_it(const char *label, const char *fmt, const char *fmt2, ...) diff --git a/gfs2/fsck/metawalk.c b/gfs2/fsck/metawalk.c index b547f44..dae71ab 100644 --- a/gfs2/fsck/metawalk.c +++ b/gfs2/fsck/metawalk.c @@ -29,20 +29,6 @@
#define COMFORTABLE_BLKS 5242880 /* 20GB in 4K blocks */
-struct dup_blks *dupfind(uint64_t num) -{ - osi_list_t *head = &dup_blocks.list; - osi_list_t *tmp; - struct dup_blks *b; - - for (tmp = head->next; tmp != head; tmp = tmp->next) { - b = osi_list_entry(tmp, struct dup_blks, list); - if (b->block == num) - return b; - } - return NULL; -} - static struct gfs2_inode *get_system_inode(struct gfs2_sbd *sbp, uint64_t block) { @@ -67,6 +53,23 @@ static struct gfs2_inode *get_system_inode(struct gfs2_sbd *sbp, return is_system_inode(sbp, block); }
+struct duptree *dupfind(uint64_t block) +{ + struct osi_node *node = dup_blocks.osi_node; + + while (node) { + struct duptree *data = (struct duptree *)node; + + if (block < data->block) + node = node->osi_left; + else if (block > data->block) + node = node->osi_right; + else + return data; + } + return NULL; +} + /* fsck_load_inode - same as gfs2_load_inode() in libgfs2 but system inodes get special treatment. */ struct gfs2_inode *fsck_load_inode(struct gfs2_sbd *sbp, uint64_t block) diff --git a/gfs2/fsck/metawalk.h b/gfs2/fsck/metawalk.h index 1c1a646..497a1bf 100644 --- a/gfs2/fsck/metawalk.h +++ b/gfs2/fsck/metawalk.h @@ -44,7 +44,7 @@ extern int delete_eattr_indir(struct gfs2_inode *ip, uint64_t block, extern int delete_eattr_leaf(struct gfs2_inode *ip, uint64_t block, uint64_t parent, struct gfs2_buffer_head **bh, void *private); -extern struct dup_blks *dupfind(uint64_t num); +extern struct duptree *dupfind(uint64_t block);
#define is_duplicate(dblock) ((dupfind(dblock)) ? 1 : 0)
diff --git a/gfs2/fsck/pass1b.c b/gfs2/fsck/pass1b.c index 57e4c47..d035e4f 100644 --- a/gfs2/fsck/pass1b.c +++ b/gfs2/fsck/pass1b.c @@ -26,15 +26,6 @@ #include "metawalk.h" #include "inode_hash.h"
-struct inode_with_dups { - osi_list_t list; - uint64_t block_no; - int dup_count; - int ea_only; - uint64_t parent; - char *name; -}; - struct fxn_info { uint64_t block; int found; @@ -42,7 +33,7 @@ struct fxn_info { };
struct dup_handler { - struct dup_blks *b; + struct duptree *b; struct inode_with_dups *id; int ref_inode_count; int ref_count; @@ -127,13 +118,14 @@ static int find_dentry(struct gfs2_inode *ip, struct gfs2_dirent *de, struct gfs2_buffer_head *bh, char *filename, uint16_t *count, void *priv) { - osi_list_t *tmp1, *tmp2; - struct dup_blks *b; + struct osi_node *n; + osi_list_t *tmp2; + struct duptree *b; struct inode_with_dups *id; struct gfs2_leaf leaf;
- osi_list_foreach(tmp1, &dup_blocks.list) { - b = osi_list_entry(tmp1, struct dup_blks, list); + for (n = osi_first(&dup_blocks); n; n = osi_next(n)) { + b = (struct duptree *)n; osi_list_foreach(tmp2, &b->ref_inode_list) { id = osi_list_entry(tmp2, struct inode_with_dups, list); @@ -328,7 +320,7 @@ static int clear_eattr_extentry(struct gfs2_inode *ip, uint64_t *ea_data_ptr, }
/* Finds all references to duplicate blocks in the metadata */ -static int find_block_ref(struct gfs2_sbd *sbp, uint64_t inode, struct dup_blks *b) +static int find_block_ref(struct gfs2_sbd *sbp, uint64_t inode, struct duptree *b) { struct gfs2_inode *ip; struct fxn_info myfi = {b->block, 0, 1}; @@ -382,7 +374,7 @@ static int find_block_ref(struct gfs2_sbd *sbp, uint64_t inode, struct dup_blks return 0; }
-static int handle_dup_blk(struct gfs2_sbd *sbp, struct dup_blks *b) +static int handle_dup_blk(struct gfs2_sbd *sbp, struct duptree *b) { osi_list_t *tmp; struct inode_with_dups *id; @@ -506,10 +498,10 @@ static int handle_dup_blk(struct gfs2_sbd *sbp, struct dup_blks *b) * use in pass2 */ int pass1b(struct gfs2_sbd *sbp) { - struct dup_blks *b; + struct duptree *b; uint64_t i; uint8_t q; - osi_list_t *tmp = NULL, *x; + struct osi_node *n; struct metawalk_fxns find_dirents = {0}; int rc = FSCK_OK; find_dirents.check_dentry = &find_dentry; @@ -517,7 +509,7 @@ int pass1b(struct gfs2_sbd *sbp) log_info( _("Looking for duplicate blocks...\n"));
/* If there were no dups in the bitmap, we don't need to do anymore */ - if(osi_list_empty(&dup_blocks.list)) { + if (dup_blocks.osi_node == NULL) { log_info( _("No duplicate blocks found\n")); return FSCK_OK; } @@ -541,9 +533,8 @@ int pass1b(struct gfs2_sbd *sbp) (q == gfs2_inode_chr) || (q == gfs2_inode_fifo) || (q == gfs2_inode_sock)) { - osi_list_foreach_safe(tmp, &dup_blocks.list, x) { - b = osi_list_entry(tmp, struct dup_blks, - list); + for (n = osi_first(&dup_blocks); n; n = osi_next(n)) { + b = (struct duptree *)n; if(find_block_ref(sbp, i, b)) { stack; rc = FSCK_ERROR; @@ -560,8 +551,8 @@ int pass1b(struct gfs2_sbd *sbp) * it later */ log_info( _("Handling duplicate blocks\n")); out: - osi_list_foreach_safe(tmp, &dup_blocks.list, x) { - b = osi_list_entry(tmp, struct dup_blks, list); + for (n = osi_first(&dup_blocks); n; n = osi_next(n)) { + b = (struct duptree *)n; if (!skip_this_pass && !rc) /* no error & not asked to skip the rest */ handle_dup_blk(sbp, b); /* Do not attempt to free the dup_blocks list or its parts diff --git a/gfs2/fsck/pass2.c b/gfs2/fsck/pass2.c index 1547e6e..55a5be3 100644 --- a/gfs2/fsck/pass2.c +++ b/gfs2/fsck/pass2.c @@ -678,7 +678,6 @@ int pass2(struct gfs2_sbd *sbp) int filename_len; char tmp_name[256]; int error = 0; - struct dup_blks *b;
/* Check all the system directory inodes. */ if (check_system_dir(sbp->md.jiinode, "jindex", build_jindex)) { @@ -824,12 +823,7 @@ int pass2(struct gfs2_sbd *sbp) deleting it from both inodes referencing it. Note: The other returns from this function are premature exits of the program and gfs2_block_list_destroy should get rid of the list for us. */ - while (!osi_list_empty(&dup_blocks.list)) { - b = osi_list_entry(dup_blocks.list.next, - struct dup_blks, list); - osi_list_del(&b->list); - free(b); - } + gfs2_dup_free(); return FSCK_OK; }
diff --git a/gfs2/fsck/util.c b/gfs2/fsck/util.c index 264489a..6af2b41 100644 --- a/gfs2/fsck/util.c +++ b/gfs2/fsck/util.c @@ -197,18 +197,49 @@ int fsck_query(const char *format, ...) return ret; }
-void gfs2_dup_set(uint64_t block) +struct duptree *gfs2_dup_set(uint64_t dblock) { - struct dup_blks *b; + struct osi_node **newn = &dup_blocks.osi_node, *parent = NULL; + struct duptree *data; + + /* Figure out where to put new node */ + while (*newn) { + struct duptree *cur = (struct duptree *)*newn; + + parent = *newn; + if (dblock < cur->block) + newn = &((*newn)->osi_left); + else if (dblock > cur->block) + newn = &((*newn)->osi_right); + else + return cur; + }
- if (dupfind(block)) - return; - b = malloc(sizeof(struct dup_blks)); - if (b) { - memset(b, 0, sizeof(*b)); - b->block = block; - osi_list_init(&b->ref_inode_list); - osi_list_add(&b->list, &dup_blocks.list); + data = malloc(sizeof(struct duptree)); + memset(data, 0, sizeof(struct duptree)); + /* Add new node and rebalance tree. */ + data->block = dblock; + data->refs = 2; /* first call is the second reference to the block */ + osi_list_init(&data->ref_inode_list); + osi_link_node(&data->node, parent, newn); + osi_insert_color(&data->node, &dup_blocks); + + return data; +} + +void dup_delete(struct duptree *b) +{ + struct inode_with_dups *id; + osi_list_t *tmp; + + while (!osi_list_empty(&b->ref_inode_list)) { + tmp = (&b->ref_inode_list)->next; + id = osi_list_entry(tmp, struct inode_with_dups, list); + if (id->name) + free(id->name); + osi_list_del(&id->list); + free(id); } - return; + osi_erase(&b->node, &dup_blocks); + free(b); } diff --git a/gfs2/fsck/util.h b/gfs2/fsck/util.h index 3a0d959..0113bdb 100644 --- a/gfs2/fsck/util.h +++ b/gfs2/fsck/util.h @@ -25,7 +25,7 @@ struct di_info *search_list(osi_list_t *list, uint64_t addr); void big_file_comfort(struct gfs2_inode *ip, uint64_t blks_checked); void warm_fuzzy_stuff(uint64_t block); const char *block_type_string(uint8_t q); -void gfs2_dup_set(uint64_t block); +struct duptree *gfs2_dup_set(uint64_t dblock);
static inline uint8_t block_type(uint64_t bblock) { diff --git a/gfs2/include/osi_tree.h b/gfs2/include/osi_tree.h new file mode 100644 index 0000000..4ffae94 --- /dev/null +++ b/gfs2/include/osi_tree.h @@ -0,0 +1,395 @@ +#ifndef __OSI_RBTREE_DOT_H__ +#define __OSI_RBTREE_DOT_H__ + +#include <stdlib.h> +#include <stddef.h> +#include <assert.h> + +/* Adapted from the kernel's rbtree.c */ +struct osi_node { + unsigned long osi_parent_color; +#define OSI_RED 0 +#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)) +#define osi_color(r) ((r)->osi_parent_color & 1) +#define osi_is_red(r) (!osi_color(r)) +#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) + +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; +} + +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_link_node(struct osi_node *node, + struct osi_node *parent, + struct osi_node **osi_link) +{ + node->osi_parent_color = (unsigned long )parent; + node->osi_left = node->osi_right = NULL; + + *osi_link = node; +} + +static inline void __osi_rotate_left(struct osi_node *node, + struct osi_root *root) +{ + struct osi_node *right = node->osi_right; + struct osi_node *parent = osi_parent(node); + + if ((node->osi_right = right->osi_left)) + osi_set_parent(right->osi_left, node); + right->osi_left = node; + + osi_set_parent(right, parent); + + if (parent) { + if (node == parent->osi_left) + parent->osi_left = right; + else + parent->osi_right = right; + } + else + root->osi_node = right; + osi_set_parent(node, right); +} + +static inline void __osi_rotate_right(struct osi_node *node, + struct osi_root *root) +{ + struct osi_node *left = node->osi_left; + struct osi_node *parent = osi_parent(node); + + if ((node->osi_left = left->osi_right)) + osi_set_parent(left->osi_right, node); + left->osi_right = node; + + osi_set_parent(left, parent); + + if (parent) { + if (node == parent->osi_right) + parent->osi_right = left; + else + parent->osi_left = left; + } else + root->osi_node = left; + osi_set_parent(node, left); +} + +static inline void osi_insert_color(struct osi_node *node, + struct osi_root *root) +{ + struct osi_node *parent, *gparent; + + while ((parent = osi_parent(node)) && osi_is_red(parent)) { + gparent = osi_parent(parent); + + if (parent == gparent->osi_left) { + { + register struct osi_node *uncle = gparent->osi_right; + if (uncle && osi_is_red(uncle)) { + osi_set_black(uncle); + osi_set_black(parent); + osi_set_red(gparent); + node = gparent; + continue; + } + } + + if (parent->osi_right == node) { + register struct osi_node *tmp; + + __osi_rotate_left(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + osi_set_black(parent); + osi_set_red(gparent); + __osi_rotate_right(gparent, root); + } else { + { + register struct osi_node *uncle = gparent->osi_left; + if (uncle && osi_is_red(uncle)) { + osi_set_black(uncle); + osi_set_black(parent); + osi_set_red(gparent); + node = gparent; + continue; + } + } + + if (parent->osi_left == node) { + register struct osi_node *tmp; + __osi_rotate_right(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + osi_set_black(parent); + osi_set_red(gparent); + __osi_rotate_left(gparent, root); + } + } + + osi_set_black(root->osi_node); +} + +static inline void __osi_erase_color(struct osi_node *node, + struct osi_node *parent, + struct osi_root *root) +{ + struct osi_node *other; + + while ((!node || osi_is_black(node)) && node != root->osi_node) { + if (parent->osi_left == node) { + other = parent->osi_right; + if (osi_is_red(other)) { + osi_set_black(other); + osi_set_red(parent); + __osi_rotate_left(parent, root); + other = parent->osi_right; + } + if ((!other->osi_left || osi_is_black(other->osi_left)) && + (!other->osi_right || osi_is_black(other->osi_right))) + { + osi_set_red(other); + node = parent; + parent = osi_parent(node); + } else { + if (!other->osi_right || osi_is_black(other->osi_right)) + { + struct osi_node *o_left; + if ((o_left = other->osi_left)) + osi_set_black(o_left); + osi_set_red(other); + __osi_rotate_right(other, root); + other = parent->osi_right; + } + osi_set_color(other, osi_color(parent)); + osi_set_black(parent); + if (other->osi_right) + osi_set_black(other->osi_right); + __osi_rotate_left(parent, root); + node = root->osi_node; + break; + } + } else { + other = parent->osi_left; + if (osi_is_red(other)) { + osi_set_black(other); + osi_set_red(parent); + __osi_rotate_right(parent, root); + other = parent->osi_left; + } + if ((!other->osi_left || osi_is_black(other->osi_left)) && + (!other->osi_right || osi_is_black(other->osi_right))) + { + osi_set_red(other); + node = parent; + parent = osi_parent(node); + } else { + if (!other->osi_left || osi_is_black(other->osi_left)) + { + register struct osi_node *o_right; + if ((o_right = other->osi_right)) + osi_set_black(o_right); + osi_set_red(other); + __osi_rotate_left(other, root); + other = parent->osi_left; + } + osi_set_color(other, osi_color(parent)); + osi_set_black(parent); + if (other->osi_left) + osi_set_black(other->osi_left); + __osi_rotate_right(parent, root); + node = root->osi_node; + break; + } + } + } + if (node) + osi_set_black(node); +} + +static inline void osi_erase(struct osi_node *node, struct osi_root *root) +{ + struct osi_node *child, *parent; + int color; + + if (!node->osi_left) + child = node->osi_right; + else if (!node->osi_right) + child = node->osi_left; + else { + struct osi_node *old = node, *left; + + node = node->osi_right; + while ((left = node->osi_left) != NULL) + node = left; + 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 + parent->osi_left = child; + + 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; + } + + parent = osi_parent(node); + color = osi_color(node); + + if (child) + osi_set_parent(child, parent); + if (parent) + { + if (parent->osi_left == node) + parent->osi_left = child; + else + parent->osi_right = child; + } + else + root->osi_node = child; + + color: + if (color == OSI_BLACK) + __osi_erase_color(child, parent, root); +} + +/* + * This function returns the first node (in sort order) of the tree. + */ +static inline struct osi_node *osi_first(struct osi_root *root) +{ + struct osi_node *n; + + n = root->osi_node; + if (!n) + return NULL; + while (n->osi_left) + n = n->osi_left; + return n; +} + +static inline struct osi_node *osi_last(struct osi_root *root) +{ + struct osi_node *n; + + n = root->osi_node; + if (!n) + return NULL; + while (n->osi_right) + n = n->osi_right; + return n; +} + +static inline struct osi_node *osi_next(struct osi_node *node) +{ + struct osi_node *parent; + + /* If we have a right-hand child, go down and then left as far + as we can. */ + if (node->osi_right) { + node = node->osi_right; + while (node->osi_left) + node=node->osi_left; + return node; + } + + /* No right-hand children. Everything down and left is + smaller than us, so any 'next' node must be in the general + direction of our parent. Go up the tree; any time the + 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 ((parent = osi_parent(node)) && node == parent->osi_right) + node = parent; + + return parent; +} + +static inline struct osi_node *osi_prev(struct osi_node *node) +{ + struct osi_node *parent; + + /* If we have a left-hand child, go down and then right as far + as we can. */ + if (node->osi_left) { + node = node->osi_left; + while (node->osi_right) + node=node->osi_right; + return node; + } + + /* No left-hand children. Go up till we find an ancestor which + is a right-hand child of its parent */ + while ((parent = osi_parent(node)) && node == parent->osi_left) + node = parent; + + return parent; +} + +static inline void osi_replace_node(struct osi_node *victim, + struct osi_node *new, + struct osi_root *root) +{ + struct osi_node *parent = osi_parent(victim); + + /* Set the surrounding nodes to point to the replacement */ + if (parent) { + if (victim == parent->osi_left) + parent->osi_left = new; + else + parent->osi_right = new; + } else { + root->osi_node = new; + } + if (victim->osi_left) + osi_set_parent(victim->osi_left, new); + if (victim->osi_right) + osi_set_parent(victim->osi_right, new); + + /* Copy the pointers/colour from the victim to the replacement */ + *new = *victim; +} + +#endif