summaryrefslogtreecommitdiff
path: root/fs/jffs2/readinode.c
diff options
context:
space:
mode:
authorDavid Woodhouse <dwmw2@infradead.org>2005-07-06 01:03:10 +0400
committerThomas Gleixner <tglx@mtd.linutronix.de>2005-07-06 16:07:54 +0400
commit9dee7503ce3fc38911b9873216619190cf688128 (patch)
tree4a980e7afd14722a81472600ed13e147ff69f923 /fs/jffs2/readinode.c
parent10c96f2ec37f5369a785cf8c5a065a15e323c743 (diff)
downloadlinux-9dee7503ce3fc38911b9873216619190cf688128.tar.xz
[JFFS2] Optimise jffs2_add_tn_to_list
Use an rbtree instead of a simple linked list. We were wasting an amazing amount of time in jffs2_add_tn_to_list(). Thanks to Artem Bityuckiy and Jarkko Jlavinen for noticing. Signed-off-by: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Diffstat (limited to 'fs/jffs2/readinode.c')
-rw-r--r--fs/jffs2/readinode.c36
1 files changed, 31 insertions, 5 deletions
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index ef552477c813..081656c1d49e 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));