From 2a1df5b2bd5328faa21353946587be507067a910 Mon Sep 17 00:00:00 2001 From: David Woodhouse Date: Fri, 14 Dec 2007 22:02:05 -0500 Subject: mkfs.jffs2.c: use rbtrees for hardlink tracking I just couldn't live with myself. Signed-off-by: David Woodhouse --- mkfs.jffs2.c | 34 ++++++++++++++++++++++------------ 1 file changed, 22 insertions(+), 12 deletions(-) (limited to 'mkfs.jffs2.c') diff --git a/mkfs.jffs2.c b/mkfs.jffs2.c index 087f8bd..2228ee1 100644 --- a/mkfs.jffs2.c +++ b/mkfs.jffs2.c @@ -73,8 +73,9 @@ #include #undef crc32 #include "crc32.h" +#include "rbtree.h" -/* Do not use the wierd XPG version of basename */ +/* Do not use the weird XPG version of basename */ #undef basename //#define DMALLOC @@ -96,10 +97,10 @@ struct filesystem_entry { struct filesystem_entry *prev; /* Only relevant to non-directories */ struct filesystem_entry *next; /* Only relevant to non-directories */ struct filesystem_entry *files; /* Only relevant to directories */ - struct filesystem_entry *hardlink_next; + struct rb_node hardlink_rb; }; -struct filesystem_entry *hardlinks = NULL; +struct rb_root hardlinks; static int out_fd = -1; static int in_fd = -1; static char default_rootdir[] = "."; @@ -115,18 +116,27 @@ static const char *const memory_exhausted = "memory exhausted"; uint32_t find_hardlink(struct filesystem_entry *e) { struct filesystem_entry *f; - - for (f = hardlinks; f; f = f->hardlink_next) { - if (f->sb.st_dev == e->sb.st_dev && - f->sb.st_ino == e->sb.st_ino) { + struct rb_node **n = &hardlinks.rb_node; + struct rb_node *parent = NULL; + + while (*n) { + parent = *n; + f = rb_entry(parent, struct filesystem_entry, hardlink_rb); + + if ((f->sb.st_dev < e->sb.st_dev) || + (f->sb.st_dev == e->sb.st_dev && + f->sb.st_ino < e->sb.st_ino)) + n = &parent->rb_left; + else if ((f->sb.st_dev > e->sb.st_dev) || + (f->sb.st_dev == e->sb.st_dev && + f->sb.st_ino > e->sb.st_ino)) { + n = &parent->rb_right; + } else return f->ino; - } } - /* Add it to the list for later */ - e->hardlink_next = hardlinks; - hardlinks = e; - + rb_link_node(&e->hardlink_rb, parent, n); + rb_insert_color(&e->hardlink_rb, &hardlinks); return 0; } -- cgit v1.2.3