summaryrefslogtreecommitdiff
path: root/mkfs.jffs2.c
diff options
context:
space:
mode:
Diffstat (limited to 'mkfs.jffs2.c')
-rw-r--r--mkfs.jffs2.c34
1 files changed, 22 insertions, 12 deletions
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 <zlib.h>
#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;
}