diff options
| -rw-r--r-- | fs/jffs2/nodelist.c | 73 | ||||
| -rw-r--r-- | fs/jffs2/nodelist.h | 6 | ||||
| -rw-r--r-- | fs/jffs2/readinode.c | 36 |
3 files changed, 88 insertions, 27 deletions
diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c index 8a8e4b86382..be38cc5c35c 100644 --- a/fs/jffs2/nodelist.c +++ b/fs/jffs2/nodelist.c @@ -7,7 +7,7 @@ * * For licensing information, see the file 'LICENCE' in this directory. * - * $Id: nodelist.c,v 1.94 2005/04/13 13:22:35 dwmw2 Exp $ + * $Id: nodelist.c,v 1.95 2005/07/05 21:03:07 dwmw2 Exp $ * */ @@ -58,27 +58,61 @@ void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new /* Put a new tmp_dnode_info into the list, keeping the list in order of increasing version */ -static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct jffs2_tmp_dnode_info **list) + +static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct rb_root *list) { - struct jffs2_tmp_dnode_info **prev = list; - - while ((*prev) && (*prev)->version < tn->version) { - prev = &((*prev)->next); - } - tn->next = (*prev); - *prev = tn; + struct rb_node **p = &list->rb_node; + struct rb_node * parent = NULL; + struct jffs2_tmp_dnode_info *this; + + while (*p) { + parent = *p; + this = rb_entry(parent, struct jffs2_tmp_dnode_info, rb); + + if (tn->version < this->version) + p = &(*p)->rb_left; + else if (tn->version > this->version) + p = &(*p)->rb_right; + else if (tn < this) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + + rb_link_node(&tn->rb, parent, p); + rb_insert_color(&tn->rb, list); } -static void jffs2_free_tmp_dnode_info_list(struct jffs2_tmp_dnode_info *tn) +static void jffs2_free_tmp_dnode_info_list(struct rb_root *list) { - struct jffs2_tmp_dnode_info *next; + struct rb_node *this; + struct jffs2_tmp_dnode_info *tn; + + this = list->rb_node; - while (tn) { - next = tn; - tn = tn->next; - jffs2_free_full_dnode(next->fn); - jffs2_free_tmp_dnode_info(next); + /* Now at bottom of tree */ + while (this) { + if (this->rb_left) + this = this->rb_left; + else if (this->rb_right) + this = this->rb_right; + else { + tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb); + jffs2_free_full_dnode(tn->fn); + jffs2_free_tmp_dnode_info(tn); + + this = this->rb_parent; + if (!this) + break; + + if (this->rb_left == &tn->rb) + this->rb_left = NULL; + else if (this->rb_right == &tn->rb) + this->rb_right = NULL; + else BUG(); + } } + list->rb_node = NULL; } static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd) @@ -108,12 +142,13 @@ static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_r with this ino, returning the former in order of version */ int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f, - struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp, + struct rb_root *tnp, struct jffs2_full_dirent **fdp, uint32_t *highest_version, uint32_t *latest_mctime, uint32_t *mctime_ver) { struct jffs2_raw_node_ref *ref, *valid_ref; - struct jffs2_tmp_dnode_info *tn, *ret_tn = NULL; + struct jffs2_tmp_dnode_info *tn; + struct rb_root ret_tn = RB_ROOT; struct jffs2_full_dirent *fd, *ret_fd = NULL; union jffs2_node_union node; size_t retlen; @@ -450,7 +485,7 @@ int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f, return 0; free_out: - jffs2_free_tmp_dnode_info_list(ret_tn); + jffs2_free_tmp_dnode_info_list(&ret_tn); jffs2_free_full_dirent_list(ret_fd); return err; } diff --git a/fs/jffs2/nodelist.h b/fs/jffs2/nodelist.h index a65539f28b0..b34c397909e 100644 --- a/fs/jffs2/nodelist.h +++ b/fs/jffs2/nodelist.h @@ -7,7 +7,7 @@ * * For licensing information, see the file 'LICENCE' in this directory. * - * $Id: nodelist.h,v 1.130 2005/04/09 10:46:59 dedekind Exp $ + * $Id: nodelist.h,v 1.131 2005/07/05 21:03:07 dwmw2 Exp $ * */ @@ -161,7 +161,7 @@ struct jffs2_full_dnode */ struct jffs2_tmp_dnode_info { - struct jffs2_tmp_dnode_info *next; + struct rb_node rb; struct jffs2_full_dnode *fn; uint32_t version; }; @@ -387,7 +387,7 @@ static inline struct jffs2_node_frag *frag_last(struct rb_root *root) D2(void jffs2_print_frag_list(struct jffs2_inode_info *f)); void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list); int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f, - struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp, + struct rb_root *tnp, struct jffs2_full_dirent **fdp, uint32_t *highest_version, uint32_t *latest_mctime, uint32_t *mctime_ver); void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state); diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c index ef552477c81..081656c1d49 100644 --- a/fs/jffs2/readinode.c +++ b/fs/jffs2/readinode.c @@ -7,7 +7,7 @@ * * For licensing information, see the file 'LICENCE' in this directory. * - * $Id: readinode.c,v 1.119 2005/03/01 10:34:03 dedekind Exp $ + * $Id: readinode.c,v 1.120 2005/07/05 21:03:07 dwmw2 Exp $ * */ @@ -500,7 +500,9 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_raw_inode *latest_node) { - struct jffs2_tmp_dnode_info *tn_list, *tn; + struct jffs2_tmp_dnode_info *tn = NULL; + struct rb_root tn_list; + struct rb_node *rb, *repl_rb; struct jffs2_full_dirent *fd_list; struct jffs2_full_dnode *fn = NULL; uint32_t crc; @@ -522,9 +524,10 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c, } f->dents = fd_list; - while (tn_list) { - tn = tn_list; + rb = rb_first(&tn_list); + while (rb) { + tn = rb_entry(rb, struct jffs2_tmp_dnode_info, rb); fn = tn->fn; if (f->metadata) { @@ -556,7 +559,30 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c, mdata_ver = tn->version; } next_tn: - tn_list = tn->next; + BUG_ON(rb->rb_left); + repl_rb = NULL; + if (rb->rb_parent && rb->rb_parent->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; + } else + repl_rb = NULL; + + rb = rb_next(rb); + + /* Remove the spent tn from the tree; don't bother rebalancing + but put our right-hand child in our own place. */ + if (tn->rb.rb_parent) { + if (tn->rb.rb_parent->rb_left == &tn->rb) + tn->rb.rb_parent->rb_left = repl_rb; + else if (tn->rb.rb_parent->rb_right == &tn->rb) + tn->rb.rb_parent->rb_right = repl_rb; + else BUG(); + } else if (tn->rb.rb_right) + tn->rb.rb_right->rb_parent = NULL; + jffs2_free_tmp_dnode_info(tn); } D1(jffs2_sanitycheck_fragtree(f)); |