diff options
| -rw-r--r-- | include/rbtree.h (renamed from jffsX-utils/rbtree.h) | 32 | ||||
| -rw-r--r-- | jffsX-utils/Makemodule.am | 6 | ||||
| -rw-r--r-- | lib/Makemodule.am | 2 | ||||
| -rw-r--r-- | lib/rbtree.c (renamed from jffsX-utils/rbtree.c) | 38 |
4 files changed, 74 insertions, 4 deletions
diff --git a/jffsX-utils/rbtree.h b/include/rbtree.h index 0d77b65..89926e7 100644 --- a/jffsX-utils/rbtree.h +++ b/include/rbtree.h @@ -155,6 +155,38 @@ 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 *); +/* Postorder iteration - always visit the parent after its children */ +extern struct rb_node *rb_first_postorder(const struct rb_root *); +extern struct rb_node *rb_next_postorder(const struct rb_node *); + +#define rb_entry_safe(ptr, type, member) \ + ({ typeof(ptr) ____ptr = (ptr); \ + ____ptr ? rb_entry(____ptr, type, member) : NULL; \ + }) + +/** + * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of + * given type allowing the backing memory of @pos to be invalidated + * + * @pos: the 'type *' to use as a loop cursor. + * @n: another 'type *' to use as temporary storage + * @root: 'rb_root *' of the rbtree. + * @field: the name of the rb_node field within 'type'. + * + * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as + * list_for_each_entry_safe() and allows the iteration to continue independent + * of changes to @pos by the body of the loop. + * + * Note, however, that it cannot handle other modifications that re-order the + * rbtree it is iterating over. This includes calling rb_erase() on @pos, as + * rb_erase() may rebalance the tree, causing us to miss some nodes. + */ +#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ + for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \ + pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \ + typeof(*pos), field); 1; }); \ + pos = n) + /* 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); diff --git a/jffsX-utils/Makemodule.am b/jffsX-utils/Makemodule.am index 2374b85..4ae4c57 100644 --- a/jffsX-utils/Makemodule.am +++ b/jffsX-utils/Makemodule.am @@ -1,16 +1,14 @@ mkfs_jffs2_SOURCES = \ jffsX-utils/mkfs.jffs2.c \ - jffsX-utils/rbtree.h \ jffsX-utils/compr.h \ - jffsX-utils/rbtree.c \ jffsX-utils/compr.c \ jffsX-utils/compr_rtime.c \ jffsX-utils/compr.h \ - jffsX-utils/rbtree.h \ jffsX-utils/summary.h \ include/linux/jffs2.h \ include/mtd/jffs2-user.h \ - include/list.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) diff --git a/lib/Makemodule.am b/lib/Makemodule.am index 7f890da..441532d 100644 --- a/lib/Makemodule.am +++ b/lib/Makemodule.am @@ -7,6 +7,8 @@ libmtd_a_SOURCES = \ include/common.h \ lib/list_sort.c \ include/list.h \ + lib/rbtree.c \ + include/rbtree.h \ lib/libcrc32.c \ include/crc32.h \ lib/libmtd_legacy.c \ diff --git a/jffsX-utils/rbtree.c b/lib/rbtree.c index 329e098..32c8755 100644 --- a/jffsX-utils/rbtree.c +++ b/lib/rbtree.c @@ -388,3 +388,41 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, /* Copy the pointers/colour from the victim to the replacement */ *new = *victim; } + +static struct rb_node *rb_left_deepest_node(const struct rb_node *node) +{ + for (;;) { + if (node->rb_left) + node = node->rb_left; + else if (node->rb_right) + node = node->rb_right; + else + return (struct rb_node *)node; + } +} + +struct rb_node *rb_next_postorder(const struct rb_node *node) +{ + const struct rb_node *parent; + if (!node) + return NULL; + parent = rb_parent(node); + + /* If we're sitting on node, we've already seen our children */ + if (parent && node == parent->rb_left && parent->rb_right) { + /* If we are the parent's left node, go to the parent's right + * node then all the way down to the left */ + return rb_left_deepest_node(parent->rb_right); + } else + /* Otherwise we are the parent's right node, and the parent + * should be next */ + return (struct rb_node *)parent; +} + +struct rb_node *rb_first_postorder(const struct rb_root *root) +{ + if (!root->rb_node) + return NULL; + + return rb_left_deepest_node(root->rb_node); +} |