aboutsummaryrefslogtreecommitdiff
path: root/jffsX-utils
diff options
context:
space:
mode:
Diffstat (limited to 'jffsX-utils')
-rw-r--r--jffsX-utils/Makemodule.am43
-rw-r--r--jffsX-utils/compr.c57
-rw-r--r--jffsX-utils/compr.h11
-rw-r--r--jffsX-utils/compr_lzo.c15
-rw-r--r--jffsX-utils/jffs2dump.c15
-rw-r--r--jffsX-utils/jffs2reader.c15
-rw-r--r--jffsX-utils/mkfs.jffs2.14
-rw-r--r--jffsX-utils/mkfs.jffs2.c17
-rw-r--r--jffsX-utils/rbtree.c390
-rw-r--r--jffsX-utils/rbtree.h171
10 files changed, 66 insertions, 672 deletions
diff --git a/jffsX-utils/Makemodule.am b/jffsX-utils/Makemodule.am
index fb181de..4ae4c57 100644
--- a/jffsX-utils/Makemodule.am
+++ b/jffsX-utils/Makemodule.am
@@ -1,37 +1,38 @@
mkfs_jffs2_SOURCES = \
jffsX-utils/mkfs.jffs2.c \
- jffsX-utils/rbtree.h \
- jffsX-utils/compr_zlib.c \
jffsX-utils/compr.h \
- jffsX-utils/rbtree.c \
- jffsX-utils/compr_lzo.c \
jffsX-utils/compr.c \
- jffsX-utils/compr_rtime.c
+ jffsX-utils/compr_rtime.c \
+ jffsX-utils/compr.h \
+ jffsX-utils/summary.h \
+ include/linux/jffs2.h \
+ include/mtd/jffs2-user.h \
+ include/list.h \
+ include/rbtree.h
mkfs_jffs2_LDADD = libmtd.a $(ZLIB_LIBS) $(LZO_LIBS)
mkfs_jffs2_CPPFLAGS = $(AM_CPPFLAGS) $(ZLIB_CFLAGS) $(LZO_CFLAGS)
-jffs2reader_SOURCES = jffsX-utils/jffs2reader.c
+jffs2reader_SOURCES = jffsX-utils/jffs2reader.c include/mtd/jffs2-user.h
jffs2reader_LDADD = libmtd.a $(ZLIB_LIBS) $(LZO_LIBS)
+jffs2reader_CPPFLAGS = $(AM_CPPFLAGS) $(ZLIB_CFLAGS) $(LZO_CFLAGS)
-jffs2dump_SOURCES = jffsX-utils/jffs2dump.c
+jffs2dump_SOURCES = jffsX-utils/jffs2dump.c include/mtd/jffs2-user.h
+jffs2dump_SOURCES += jffsX-utils/summary.h
jffs2dump_LDADD = libmtd.a $(ZLIB_LIBS) $(LZO_LIBS)
+jffs2dump_CPPFLAGS = $(AM_CPPFLAGS) $(ZLIB_CFLAGS) $(LZO_CFLAGS)
-sumtool_SOURCES = jffsX-utils/sumtool.c
+sumtool_SOURCES = jffsX-utils/sumtool.c jffsX-utils/summary.h
sumtool_LDADD = libmtd.a
-JFFSX_BINS = \
- mkfs.jffs2 jffs2dump jffs2reader sumtool
-
-JFFSX_MAN = \
- jffsX-utils/mkfs.jffs2.1
-
-JFFSX_EXTRA = \
- jffsX-utils/device_table.txt jffsX-utils/mkfs.jffs2.1
+if WITH_LZO
+mkfs_jffs2_SOURCES += jffsX-utils/compr_lzo.c
+endif
-JFFSX_HEADER = \
- jffsX-utils/compr.h jffsX-utils/rbtree.h jffsX-utils/summary.h
+if WITH_ZLIB
+mkfs_jffs2_SOURCES += jffsX-utils/compr_zlib.c
+endif
-EXTRA_DIST += $(JFFSX_HEADER) $(JFFSX_EXTRA)
+EXTRA_DIST += jffsX-utils/device_table.txt jffsX-utils/mkfs.jffs2.1
-dist_man1_MANS += $(JFFSX_MAN)
-sbin_PROGRAMS += $(JFFSX_BINS)
+dist_man1_MANS += jffsX-utils/mkfs.jffs2.1
+sbin_PROGRAMS += mkfs.jffs2 jffs2dump jffs2reader sumtool
diff --git a/jffsX-utils/compr.c b/jffsX-utils/compr.c
index cb4432e..d408ef8 100644
--- a/jffsX-utils/compr.c
+++ b/jffsX-utils/compr.c
@@ -17,55 +17,6 @@
extern int page_size;
-/* LIST IMPLEMENTATION (from linux/list.h) */
-
-#define LIST_HEAD_INIT(name) { &(name), &(name) }
-
-#define LIST_HEAD(name) \
- struct list_head name = LIST_HEAD_INIT(name)
-
-static inline void __list_add(struct list_head *new,
- struct list_head *prev,
- struct list_head *next)
-{
- next->prev = new;
- new->next = next;
- new->prev = prev;
- prev->next = new;
-}
-
-static inline void list_add(struct list_head *new, struct list_head *head)
-{
- __list_add(new, head, head->next);
-}
-
-static inline void list_add_tail(struct list_head *new, struct list_head *head)
-{
- __list_add(new, head->prev, head);
-}
-
-static inline void __list_del(struct list_head *prev, struct list_head *next)
-{
- next->prev = prev;
- prev->next = next;
-}
-
-static inline void list_del(struct list_head *entry)
-{
- __list_del(entry->prev, entry->next);
- entry->next = (void *) 0;
- entry->prev = (void *) 0;
-}
-
-#define list_entry(ptr, type, member) \
- ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
-
-#define list_for_each_entry(pos, head, member) \
- for (pos = list_entry((head)->next, typeof(*pos), member); \
- &pos->member != (head); \
- pos = list_entry(pos->member.next, typeof(*pos), member))
-
-
/* Available compressors are on this list */
static LIST_HEAD(jffs2_compressor_list);
@@ -511,13 +462,13 @@ reinsert:
int jffs2_compressors_init(void)
{
-#ifdef CONFIG_JFFS2_ZLIB
+#ifdef WITH_ZLIB
jffs2_zlib_init();
#endif
#ifdef CONFIG_JFFS2_RTIME
jffs2_rtime_init();
#endif
-#ifdef CONFIG_JFFS2_LZO
+#ifdef WITH_LZO
jffs2_lzo_init();
#endif
return 0;
@@ -528,10 +479,10 @@ int jffs2_compressors_exit(void)
#ifdef CONFIG_JFFS2_RTIME
jffs2_rtime_exit();
#endif
-#ifdef CONFIG_JFFS2_ZLIB
+#ifdef WITH_ZLIB
jffs2_zlib_exit();
#endif
-#ifdef CONFIG_JFFS2_LZO
+#ifdef WITH_LZO
jffs2_lzo_exit();
#endif
return 0;
diff --git a/jffsX-utils/compr.h b/jffsX-utils/compr.h
index a21e935..6969952 100644
--- a/jffsX-utils/compr.h
+++ b/jffsX-utils/compr.h
@@ -15,10 +15,9 @@
#include <stdlib.h>
#include <stdint.h>
#include "linux/jffs2.h"
+#include "list.h"
-#define CONFIG_JFFS2_ZLIB
#define CONFIG_JFFS2_RTIME
-#define CONFIG_JFFS2_LZO
#define JFFS2_RUBINMIPS_PRIORITY 10
#define JFFS2_DYNRUBIN_PRIORITY 20
@@ -51,10 +50,6 @@
#define KERN_INFO
#define KERN_DEBUG
-struct list_head {
- struct list_head *next, *prev;
-};
-
void jffs2_set_compression_mode(int mode);
int jffs2_get_compression_mode(void);
int jffs2_set_compression_mode_name(const char *mode_name);
@@ -103,7 +98,7 @@ char *jffs2_stats(void);
/* Compressor modules */
/* These functions will be called by jffs2_compressors_init/exit */
-#ifdef CONFIG_JFFS2_ZLIB
+#ifdef WITH_ZLIB
int jffs2_zlib_init(void);
void jffs2_zlib_exit(void);
#endif
@@ -111,7 +106,7 @@ void jffs2_zlib_exit(void);
int jffs2_rtime_init(void);
void jffs2_rtime_exit(void);
#endif
-#ifdef CONFIG_JFFS2_LZO
+#ifdef WITH_LZO
int jffs2_lzo_init(void);
void jffs2_lzo_exit(void);
#endif
diff --git a/jffsX-utils/compr_lzo.c b/jffsX-utils/compr_lzo.c
index 56aa1b4..ddd8d55 100644
--- a/jffsX-utils/compr_lzo.c
+++ b/jffsX-utils/compr_lzo.c
@@ -24,8 +24,6 @@
#include <stdint.h>
#include <stdio.h>
#include <string.h>
-
-#ifndef WITHOUT_LZO
#include <asm/types.h>
#include <linux/jffs2.h>
#include <lzo/lzo1x.h>
@@ -121,16 +119,3 @@ void jffs2_lzo_exit(void)
free(lzo_compress_buf);
free(lzo_mem);
}
-
-#else
-
-int jffs2_lzo_init(void)
-{
- return 0;
-}
-
-void jffs2_lzo_exit(void)
-{
-}
-
-#endif
diff --git a/jffsX-utils/jffs2dump.c b/jffsX-utils/jffs2dump.c
index d30b59f..b757ebe 100644
--- a/jffsX-utils/jffs2dump.c
+++ b/jffsX-utils/jffs2dump.c
@@ -757,6 +757,12 @@ int main(int argc, char **argv)
// get image length
imglen = lseek(fd, 0, SEEK_END);
+ if (imglen < 0) {
+ perror(img);
+ close(fd);
+ exit(EXIT_FAILURE);
+ }
+
lseek (fd, 0, SEEK_SET);
data = malloc (imglen);
@@ -766,6 +772,13 @@ int main(int argc, char **argv)
exit(EXIT_FAILURE);
}
+ if (datsize < 0 || oobsize < 0 || datsize > imglen || (long)datsize + oobsize < 0) {
+ fprintf(stderr, "Error: invalid datsize/oobsize.\n");
+ free(data);
+ close (fd);
+ exit(EXIT_FAILURE);
+ }
+
if (datsize && oobsize) {
int idx = 0;
long len = imglen;
@@ -777,7 +790,7 @@ int main(int argc, char **argv)
read_nocheck (fd, oob, oobsize);
idx += datsize;
imglen -= oobsize;
- len -= datsize + oobsize;
+ len -= (long)datsize + oobsize;
}
} else {
diff --git a/jffsX-utils/jffs2reader.c b/jffsX-utils/jffs2reader.c
index 083500e..548fc8d 100644
--- a/jffsX-utils/jffs2reader.c
+++ b/jffsX-utils/jffs2reader.c
@@ -75,7 +75,11 @@ BUGS:
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
+#ifdef WITH_ZLIB
#include <zlib.h>
+#else
+typedef unsigned long uLongf;
+#endif
#include "mtd/jffs2-user.h"
#include "common.h"
@@ -132,12 +136,13 @@ static void putblock(char *b, size_t bsize, size_t * rsize,
bzero(b + *rsize, je32_to_cpu(n->isize) - *rsize);
switch (n->compr) {
+#ifdef WITH_ZLIB
case JFFS2_COMPR_ZLIB:
uncompress((Bytef *) b + je32_to_cpu(n->offset), &dlen,
(Bytef *) ((char *) n) + sizeof(struct jffs2_raw_inode),
(uLongf) je32_to_cpu(n->csize));
break;
-
+#endif
case JFFS2_COMPR_NONE:
memcpy(b + je32_to_cpu(n->offset),
((char *) n) + sizeof(struct jffs2_raw_inode), dlen);
@@ -336,8 +341,9 @@ static void printdir(char *o, size_t size, struct dir *d, const char *path,
d = d->next;
continue;
}
-
- filetime = ctime((const time_t *) &(ri->ctime));
+ time_t _ctime;
+ memcpy(&_ctime, &(ri->ctime), sizeof(time_t));
+ filetime = ctime(&_ctime);
age = time(NULL) - je32_to_cpu(ri->ctime);
mode.v32 = ri->mode.m;
printf("%s %-4d %-8d %-8d ", mode_string(je32_to_cpu(mode)),
@@ -688,6 +694,9 @@ static struct jffs2_raw_dirent *resolvepath0(char *o, size_t size, uint32_t ino,
pp = path = xstrdup(p);
+ if (path == NULL)
+ return NULL;
+
if (*path == '/') {
path++;
ino = 1;
diff --git a/jffsX-utils/mkfs.jffs2.1 b/jffsX-utils/mkfs.jffs2.1
index 7c57ddc..75f96f5 100644
--- a/jffsX-utils/mkfs.jffs2.1
+++ b/jffsX-utils/mkfs.jffs2.1
@@ -119,13 +119,13 @@ the kernel can be changed with a #define to accept images of the
non-native endianness. Full bi-endian support in the kernel is not
planned.
-It is unlikely that JFFS2 images are useful except in conjuction
+It is unlikely that JFFS2 images are useful except in conjunction
with the MTD (Memory Technology Device) drivers in the Linux
kernel, since the JFFS2 file system driver in the kernel requires
MTD devices.
.SH OPTIONS
Options that take SIZE arguments can be specified as either
-decimal (e.g., 65536), octal (0200000), or hexidecimal (0x1000).
+decimal (e.g., 65536), octal (0200000), or hexadecimal (0x1000).
.TP
.B -p, --pad[=SIZE]
Pad output to SIZE bytes with 0xFF. If SIZE is not specified,
diff --git a/jffsX-utils/mkfs.jffs2.c b/jffsX-utils/mkfs.jffs2.c
index 9cc5eaf..da07b69 100644
--- a/jffsX-utils/mkfs.jffs2.c
+++ b/jffsX-utils/mkfs.jffs2.c
@@ -65,7 +65,7 @@
#include <ctype.h>
#include <time.h>
#include <getopt.h>
-#ifndef WITHOUT_XATTR
+#ifdef WITH_XATTR
#include <sys/xattr.h>
#include <sys/acl.h>
#endif
@@ -428,7 +428,7 @@ static int interpret_table_entry(struct filesystem_entry *root, char *line)
if (sscanf (line, "%" SCANF_PREFIX "s %c %lo %lu %lu %lu %lu %lu %lu %lu",
SCANF_STRING(name), &type, &mode, &uid, &gid, &major, &minor,
- &start, &increment, &count) < 0)
+ &start, &increment, &count) < 2)
{
return 1;
}
@@ -978,7 +978,7 @@ static void write_special_file(struct filesystem_entry *e)
padword();
}
-#ifndef WITHOUT_XATTR
+#ifdef WITH_XATTR
typedef struct xattr_entry {
struct xattr_entry *next;
uint32_t xid;
@@ -1209,7 +1209,7 @@ static void write_xattr_entry(struct filesystem_entry *e)
}
}
-#else /* WITHOUT_XATTR */
+#else /* WITH_XATTR */
#define write_xattr_entry(x)
#endif
@@ -1380,7 +1380,7 @@ static struct option long_options[] = {
{"test-compression", 0, NULL, 't'},
{"compressor-priority", 1, NULL, 'y'},
{"incremental", 1, NULL, 'i'},
-#ifndef WITHOUT_XATTR
+#ifdef WITH_XATTR
{"with-xattr", 0, NULL, 1000 },
{"with-selinux", 0, NULL, 1001 },
{"with-posix-acl", 0, NULL, 1002 },
@@ -1401,7 +1401,8 @@ static const char helptext[] =
" page size (default: 4KiB)\n"
" -e, --eraseblock=SIZE Use erase block size SIZE (default: 64KiB)\n"
" -c, --cleanmarker=SIZE Size of cleanmarker (default 12)\n"
-" -m, --compr-mode=MODE Select compression mode (default: priority)\n"
+" -m, --compression-mode=MODE\n"
+" Select compression mode (default: priority)\n"
" -x, --disable-compressor=COMPRESSOR_NAME\n"
" Disable a compressor\n"
" -X, --enable-compressor=COMPRESSOR_NAME\n"
@@ -1419,7 +1420,7 @@ static const char helptext[] =
" -q, --squash Squash permissions and owners making all files be owned by root\n"
" -U, --squash-uids Squash owners making all files be owned by root\n"
" -P, --squash-perms Squash permissions on all files\n"
-#ifndef WITHOUT_XATTR
+#ifdef WITH_XATTR
" --with-xattr stuff all xattr entries into image\n"
" --with-selinux stuff only SELinux Labels into jffs2 image\n"
" --with-posix-acl stuff only POSIX ACL entries into jffs2 image\n"
@@ -1744,7 +1745,7 @@ int main(int argc, char **argv)
sys_errmsg_die("cannot open (incremental) file");
}
break;
-#ifndef WITHOUT_XATTR
+#ifdef WITH_XATTR
case 1000: /* --with-xattr */
enable_xattr |= (1 << JFFS2_XPREFIX_USER)
| (1 << JFFS2_XPREFIX_SECURITY)
diff --git a/jffsX-utils/rbtree.c b/jffsX-utils/rbtree.c
deleted file mode 100644
index 329e098..0000000
--- a/jffsX-utils/rbtree.c
+++ /dev/null
@@ -1,390 +0,0 @@
-/*
- Red Black Trees
- (C) 1999 Andrea Arcangeli <andrea@suse.de>
- (C) 2002 David Woodhouse <dwmw2@infradead.org>
-
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-
- linux/lib/rbtree.c
-*/
-
-#include <stdlib.h>
-#include "rbtree.h"
-
-static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *right = node->rb_right;
- struct rb_node *parent = rb_parent(node);
-
- if ((node->rb_right = right->rb_left))
- rb_set_parent(right->rb_left, node);
- right->rb_left = node;
-
- rb_set_parent(right, parent);
-
- if (parent)
- {
- if (node == parent->rb_left)
- parent->rb_left = right;
- else
- parent->rb_right = right;
- }
- else
- root->rb_node = right;
- rb_set_parent(node, right);
-}
-
-static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *left = node->rb_left;
- struct rb_node *parent = rb_parent(node);
-
- if ((node->rb_left = left->rb_right))
- rb_set_parent(left->rb_right, node);
- left->rb_right = node;
-
- rb_set_parent(left, parent);
-
- if (parent)
- {
- if (node == parent->rb_right)
- parent->rb_right = left;
- else
- parent->rb_left = left;
- }
- else
- root->rb_node = left;
- rb_set_parent(node, left);
-}
-
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *parent, *gparent;
-
- while ((parent = rb_parent(node)) && rb_is_red(parent))
- {
- gparent = rb_parent(parent);
-
- if (parent == gparent->rb_left)
- {
- {
- register struct rb_node *uncle = gparent->rb_right;
- if (uncle && rb_is_red(uncle))
- {
- rb_set_black(uncle);
- rb_set_black(parent);
- rb_set_red(gparent);
- node = gparent;
- continue;
- }
- }
-
- if (parent->rb_right == node)
- {
- register struct rb_node *tmp;
- __rb_rotate_left(parent, root);
- tmp = parent;
- parent = node;
- node = tmp;
- }
-
- rb_set_black(parent);
- rb_set_red(gparent);
- __rb_rotate_right(gparent, root);
- } else {
- {
- register struct rb_node *uncle = gparent->rb_left;
- if (uncle && rb_is_red(uncle))
- {
- rb_set_black(uncle);
- rb_set_black(parent);
- rb_set_red(gparent);
- node = gparent;
- continue;
- }
- }
-
- if (parent->rb_left == node)
- {
- register struct rb_node *tmp;
- __rb_rotate_right(parent, root);
- tmp = parent;
- parent = node;
- node = tmp;
- }
-
- rb_set_black(parent);
- rb_set_red(gparent);
- __rb_rotate_left(gparent, root);
- }
- }
-
- rb_set_black(root->rb_node);
-}
-
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
- struct rb_root *root)
-{
- struct rb_node *other;
-
- while ((!node || rb_is_black(node)) && node != root->rb_node)
- {
- if (parent->rb_left == node)
- {
- other = parent->rb_right;
- if (rb_is_red(other))
- {
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_left(parent, root);
- other = parent->rb_right;
- }
- if ((!other->rb_left || rb_is_black(other->rb_left)) &&
- (!other->rb_right || rb_is_black(other->rb_right)))
- {
- rb_set_red(other);
- node = parent;
- parent = rb_parent(node);
- }
- else
- {
- if (!other->rb_right || rb_is_black(other->rb_right))
- {
- struct rb_node *o_left;
- if ((o_left = other->rb_left))
- rb_set_black(o_left);
- rb_set_red(other);
- __rb_rotate_right(other, root);
- other = parent->rb_right;
- }
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- if (other->rb_right)
- rb_set_black(other->rb_right);
- __rb_rotate_left(parent, root);
- node = root->rb_node;
- break;
- }
- }
- else
- {
- other = parent->rb_left;
- if (rb_is_red(other))
- {
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_right(parent, root);
- other = parent->rb_left;
- }
- if ((!other->rb_left || rb_is_black(other->rb_left)) &&
- (!other->rb_right || rb_is_black(other->rb_right)))
- {
- rb_set_red(other);
- node = parent;
- parent = rb_parent(node);
- }
- else
- {
- if (!other->rb_left || rb_is_black(other->rb_left))
- {
- register struct rb_node *o_right;
- if ((o_right = other->rb_right))
- rb_set_black(o_right);
- rb_set_red(other);
- __rb_rotate_left(other, root);
- other = parent->rb_left;
- }
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- if (other->rb_left)
- rb_set_black(other->rb_left);
- __rb_rotate_right(parent, root);
- node = root->rb_node;
- break;
- }
- }
- }
- if (node)
- rb_set_black(node);
-}
-
-void rb_erase(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *child, *parent;
- int color;
-
- if (!node->rb_left)
- child = node->rb_right;
- else if (!node->rb_right)
- child = node->rb_left;
- else
- {
- struct rb_node *old = node, *left;
-
- node = node->rb_right;
- while ((left = node->rb_left) != NULL)
- node = left;
- child = node->rb_right;
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (child)
- rb_set_parent(child, parent);
- if (parent == old) {
- parent->rb_right = child;
- parent = node;
- } else
- parent->rb_left = child;
-
- node->rb_parent_color = old->rb_parent_color;
- node->rb_right = old->rb_right;
- node->rb_left = old->rb_left;
-
- if (rb_parent(old))
- {
- if (rb_parent(old)->rb_left == old)
- rb_parent(old)->rb_left = node;
- else
- rb_parent(old)->rb_right = node;
- } else
- root->rb_node = node;
-
- rb_set_parent(old->rb_left, node);
- if (old->rb_right)
- rb_set_parent(old->rb_right, node);
- goto color;
- }
-
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (child)
- rb_set_parent(child, parent);
- if (parent)
- {
- if (parent->rb_left == node)
- parent->rb_left = child;
- else
- parent->rb_right = child;
- }
- else
- root->rb_node = child;
-
- color:
- if (color == RB_BLACK)
- __rb_erase_color(child, parent, root);
-}
-
-/*
- * This function returns the first node (in sort order) of the tree.
- */
-struct rb_node *rb_first(struct rb_root *root)
-{
- struct rb_node *n;
-
- n = root->rb_node;
- if (!n)
- return NULL;
- while (n->rb_left)
- n = n->rb_left;
- return n;
-}
-
-struct rb_node *rb_last(struct rb_root *root)
-{
- struct rb_node *n;
-
- n = root->rb_node;
- if (!n)
- return NULL;
- while (n->rb_right)
- n = n->rb_right;
- return n;
-}
-
-struct rb_node *rb_next(struct rb_node *node)
-{
- struct rb_node *parent;
-
- if (rb_parent(node) == node)
- return NULL;
-
- /* If we have a right-hand child, go down and then left as far
- as we can. */
- if (node->rb_right) {
- node = node->rb_right;
- while (node->rb_left)
- node=node->rb_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 = rb_parent(node)) && node == parent->rb_right)
- node = parent;
-
- return parent;
-}
-
-struct rb_node *rb_prev(struct rb_node *node)
-{
- struct rb_node *parent;
-
- if (rb_parent(node) == node)
- return NULL;
-
- /* If we have a left-hand child, go down and then right as far
- as we can. */
- if (node->rb_left) {
- node = node->rb_left;
- while (node->rb_right)
- node=node->rb_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 = rb_parent(node)) && node == parent->rb_left)
- node = parent;
-
- return parent;
-}
-
-void rb_replace_node(struct rb_node *victim, struct rb_node *new,
- struct rb_root *root)
-{
- struct rb_node *parent = rb_parent(victim);
-
- /* Set the surrounding nodes to point to the replacement */
- if (parent) {
- if (victim == parent->rb_left)
- parent->rb_left = new;
- else
- parent->rb_right = new;
- } else {
- root->rb_node = new;
- }
- if (victim->rb_left)
- rb_set_parent(victim->rb_left, new);
- if (victim->rb_right)
- rb_set_parent(victim->rb_right, new);
-
- /* Copy the pointers/colour from the victim to the replacement */
- *new = *victim;
-}
diff --git a/jffsX-utils/rbtree.h b/jffsX-utils/rbtree.h
deleted file mode 100644
index 0d77b65..0000000
--- a/jffsX-utils/rbtree.h
+++ /dev/null
@@ -1,171 +0,0 @@
-/*
- Red Black Trees
- (C) 1999 Andrea Arcangeli <andrea@suse.de>
-
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-
- linux/include/linux/rbtree.h
-
- To use rbtrees you'll have to implement your own insert and search cores.
- This will avoid us to use callbacks and to drop drammatically performances.
- I know it's not the cleaner way, but in C (not in C++) to get
- performances and genericity...
-
- Some example of insert and search follows here. The search is a plain
- normal search over an ordered tree. The insert instead must be implemented
- int two steps: as first thing the code must insert the element in
- order as a red leaf in the tree, then the support library function
- rb_insert_color() must be called. Such function will do the
- not trivial work to rebalance the rbtree if necessary.
-
------------------------------------------------------------------------
-static inline struct page * rb_search_page_cache(struct inode * inode,
- unsigned long offset)
-{
- struct rb_node * n = inode->i_rb_page_cache.rb_node;
- struct page * page;
-
- while (n)
- {
- page = rb_entry(n, struct page, rb_page_cache);
-
- if (offset < page->offset)
- n = n->rb_left;
- else if (offset > page->offset)
- n = n->rb_right;
- else
- return page;
- }
- return NULL;
-}
-
-static inline struct page * __rb_insert_page_cache(struct inode * inode,
- unsigned long offset,
- struct rb_node * node)
-{
- struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
- struct rb_node * parent = NULL;
- struct page * page;
-
- while (*p)
- {
- parent = *p;
- page = rb_entry(parent, struct page, rb_page_cache);
-
- if (offset < page->offset)
- p = &(*p)->rb_left;
- else if (offset > page->offset)
- p = &(*p)->rb_right;
- else
- return page;
- }
-
- rb_link_node(node, parent, p);
-
- return NULL;
-}
-
-static inline struct page * rb_insert_page_cache(struct inode * inode,
- unsigned long offset,
- struct rb_node * node)
-{
- struct page * ret;
- if ((ret = __rb_insert_page_cache(inode, offset, node)))
- goto out;
- rb_insert_color(node, &inode->i_rb_page_cache);
- out:
- return ret;
-}
------------------------------------------------------------------------
-*/
-
-#ifndef _LINUX_RBTREE_H
-#define _LINUX_RBTREE_H
-
-#include <linux/kernel.h>
-#include <linux/stddef.h>
-
-struct rb_node
-{
- unsigned long rb_parent_color;
-#define RB_RED 0
-#define RB_BLACK 1
- struct rb_node *rb_right;
- struct rb_node *rb_left;
-} __attribute__((aligned(sizeof(long))));
- /* The alignment might seem pointless, but allegedly CRIS needs it */
-
-struct rb_root
-{
- struct rb_node *rb_node;
-};
-
-
-#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
-#define rb_color(r) ((r)->rb_parent_color & 1)
-#define rb_is_red(r) (!rb_color(r))
-#define rb_is_black(r) rb_color(r)
-#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
-
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
- rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
-}
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
- rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
-
-#define RB_ROOT (struct rb_root) { NULL, }
-
-/* Newer gcc versions take care of exporting this */
-#ifndef offsetof
-#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
-#endif
-
-#define container_of(ptr, type, member) ({ \
- const typeof( ((type *)0)->member ) *__mptr = (ptr); \
- (type *)( (char *)__mptr - offsetof(type,member) );})
-
-#define rb_entry(ptr, type, member) container_of(ptr, type, member)
-
-#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
-#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
-
-extern void rb_insert_color(struct rb_node *, struct rb_root *);
-extern void rb_erase(struct rb_node *, struct rb_root *);
-
-/* Find logical next and previous nodes in a tree */
-extern struct rb_node *rb_next(struct rb_node *);
-extern struct rb_node *rb_prev(struct rb_node *);
-extern struct rb_node *rb_first(struct rb_root *);
-extern struct rb_node *rb_last(struct rb_root *);
-
-/* Fast replacement of a single node without remove/rebalance/add/rebalance */
-extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
- struct rb_root *root);
-
-static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
- struct rb_node ** rb_link)
-{
- node->rb_parent_color = (unsigned long )parent;
- node->rb_left = node->rb_right = NULL;
-
- *rb_link = node;
-}
-
-#endif /* _LINUX_RBTREE_H */
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-19 19:14:07 +0000