else if (inode_is_directory(inode))
stbuf->st_mode = S_IFDIR | 0755;
else
- stbuf->st_mode = S_IFREG | 0644;
+ stbuf->st_mode = S_IFREG | 0755;
stbuf->st_ino = (ino_t)inode->ino;
stbuf->st_nlink = inode->link_count;
}
#endif
-int for_dentry_in_rbtree(struct rb_node *node,
+int for_dentry_in_rbtree(struct rb_node *root,
int (*visitor)(struct dentry *, void *),
void *arg)
{
int ret;
- if (node) {
- ret = for_dentry_in_rbtree(node->rb_left, visitor, arg);
- if (ret != 0)
- return ret;
- ret = visitor(rbnode_dentry(node), arg);
- if (ret != 0)
- return ret;
- ret = for_dentry_in_rbtree(node->rb_right, visitor, arg);
- if (ret != 0)
- return ret;
+ struct rb_node *node = root;
+ LIST_HEAD(stack);
+ while (true) {
+ if (node) {
+ list_add(&rbnode_dentry(node)->tmp_list, &stack);
+ node = node->rb_left;
+ } else {
+ struct list_head *next;
+ struct dentry *dentry;
+
+ next = stack.next;
+ if (next == &stack)
+ return 0;
+ dentry = container_of(next, struct dentry, tmp_list);
+ list_del(next);
+ ret = visitor(dentry, arg);
+ if (ret != 0)
+ return ret;
+ node = dentry->rb_node.rb_right;
+ }
}
- return 0;
}
-int for_dentry_tree_in_rbtree(struct rb_node *node,
- int (*visitor)(struct dentry*, void*),
- void *arg)
+static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
+ int (*visitor)(struct dentry*, void*),
+ void *arg)
{
int ret;
if (node) {
- ret = for_dentry_tree_in_rbtree(node->rb_left, visitor, arg);
+ ret = for_dentry_tree_in_rbtree_depth(node->rb_left,
+ visitor, arg);
if (ret != 0)
return ret;
- ret = for_dentry_in_tree(rbnode_dentry(node), visitor, arg);
+ ret = for_dentry_tree_in_rbtree_depth(node->rb_right,
+ visitor, arg);
if (ret != 0)
return ret;
- ret = for_dentry_tree_in_rbtree(node->rb_right, visitor, arg);
+ ret = for_dentry_in_tree_depth(rbnode_dentry(node), visitor, arg);
if (ret != 0)
return ret;
}
return 0;
}
-static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
- int (*visitor)(struct dentry*, void*),
- void *arg)
+/*#define RECURSIVE_FOR_DENTRY_IN_TREE*/
+
+#ifdef RECURSIVE_FOR_DENTRY_IN_TREE
+static int for_dentry_tree_in_rbtree(struct rb_node *node,
+ int (*visitor)(struct dentry*, void*),
+ void *arg)
{
int ret;
if (node) {
- ret = for_dentry_tree_in_rbtree_depth(node->rb_left,
- visitor, arg);
+ ret = for_dentry_tree_in_rbtree(node->rb_left, visitor, arg);
if (ret != 0)
return ret;
- ret = for_dentry_tree_in_rbtree_depth(node->rb_right,
- visitor, arg);
+ ret = for_dentry_in_tree(rbnode_dentry(node), visitor, arg);
if (ret != 0)
return ret;
- ret = for_dentry_in_tree_depth(rbnode_dentry(node), visitor, arg);
+ ret = for_dentry_tree_in_rbtree(node->rb_right, visitor, arg);
if (ret != 0)
return ret;
}
return 0;
}
+#endif
/*
- * Calls a function on all directory entries in a directory tree. It is called
- * on a parent before its children.
+ * Calls a function on all directory entries in a WIM dentry tree. Logically,
+ * this is a pre-order traversal (the function is called on a parent dentry
+ * before its children), but sibling dentries will be visited in order as well.
+ *
+ * In reality, the data structures are more complicated than the above might
+ * suggest because there is a separate red-black tree for each dentry that
+ * contains its direct children.
*/
int for_dentry_in_tree(struct dentry *root,
int (*visitor)(struct dentry*, void*), void *arg)
{
+#ifdef RECURSIVE_FOR_DENTRY_IN_TREE
int ret = visitor(root, arg);
+ if (ret != 0)
+ return ret;
+ return for_dentry_tree_in_rbtree(root->d_inode->children.rb_node, visitor, arg);
+#else
+ int ret;
+ struct list_head main_stack;
+ struct list_head sibling_stack;
+ struct list_head *sibling_stack_bottom;
+ struct dentry *main_dentry;
+ struct rb_node *node;
+ struct list_head *next_sibling;
+ struct dentry *dentry;
+
+ ret = visitor(root, arg);
if (ret != 0)
return ret;
- return for_dentry_tree_in_rbtree(root->d_inode->children.rb_node,
- visitor, arg);
+ main_dentry = root;
+ sibling_stack_bottom = &sibling_stack;
+ INIT_LIST_HEAD(&main_stack);
+ INIT_LIST_HEAD(&sibling_stack);
+
+ list_add(&root->tmp_list, &main_stack);
+ node = root->d_inode->children.rb_node;
+
+ while (1) {
+ // Prepare for non-recursive in-order traversal of the red-black
+ // tree of this dentry's children
+
+ while (node) {
+ // Push this node to the sibling stack and examine the
+ // left neighbor, if any
+ list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+ node = node->rb_left;
+ }
+
+ next_sibling = sibling_stack.next;
+ if (next_sibling == sibling_stack_bottom) {
+ // Done with all siblings. Pop the main dentry to move
+ // back up one level.
+ main_dentry = container_of(main_stack.next,
+ struct dentry,
+ tmp_list);
+ list_del(&main_dentry->tmp_list);
+
+ if (main_dentry == root)
+ goto out;
+
+ // Restore sibling stack bottom from the previous level
+ sibling_stack_bottom = (void*)main_dentry->parent;
+
+ // Restore the just-popped main dentry's parent
+ main_dentry->parent = container_of(main_stack.next,
+ struct dentry,
+ tmp_list);
+
+ // The next sibling to traverse in the previous level,
+ // in the in-order traversal of the red-black tree, is
+ // the one to the right.
+ node = main_dentry->rb_node.rb_right;
+ } else {
+ // The sibling stack is not empty, so there are more to
+ // go!
+
+ // Pop a sibling from the stack.
+ list_del(next_sibling);
+ dentry = container_of(next_sibling, struct dentry, tmp_list);
+
+ // Visit the sibling.
+ ret = visitor(dentry, arg);
+ if (ret != 0) {
+ // Failed. Restore parent pointers for the
+ // dentries in the main stack
+ list_for_each_entry(dentry, &main_stack, tmp_list) {
+ dentry->parent = container_of(dentry->tmp_list.next,
+ struct dentry,
+ tmp_list);
+ }
+ goto out;
+ }
+
+ // We'd like to recursively visit the dentry tree rooted
+ // at this sibling. To do this, add it to the main
+ // stack, save the bottom of this level's sibling stack
+ // in the dentry->parent field, re-set the bottom of the
+ // sibling stack to be its current height, and set
+ // main_dentry to the sibling so it becomes the parent
+ // dentry in the next iteration through the outer loop.
+ if (inode_has_children(dentry->d_inode)) {
+ list_add(&dentry->tmp_list, &main_stack);
+ dentry->parent = (void*)sibling_stack_bottom;
+ sibling_stack_bottom = sibling_stack.next;
+
+ main_dentry = dentry;
+ node = main_dentry->d_inode->children.rb_node;
+ } else {
+ node = dentry->rb_node.rb_right;
+ }
+ }
+ }
+out:
+ root->parent = root;
+ return ret;
+#endif
}
/*
int for_dentry_in_tree_depth(struct dentry *root,
int (*visitor)(struct dentry*, void*), void *arg)
{
-
- int ret = for_dentry_tree_in_rbtree_depth(root->d_inode->children.rb_node,
- visitor, arg);
+#if 1
+ int ret;
+ ret = for_dentry_tree_in_rbtree_depth(root->d_inode->children.rb_node,
+ visitor, arg);
if (ret != 0)
return ret;
return visitor(root, arg);
+
+#else
+ int ret;
+ struct list_head main_stack;
+ struct list_head sibling_stack;
+ struct list_head *sibling_stack_bottom;
+ struct dentry *main_dentry;
+ struct rb_node *node;
+ struct list_head *next_sibling;
+ struct dentry *dentry;
+
+ main_dentry = root;
+ sibling_stack_bottom = &sibling_stack;
+ INIT_LIST_HEAD(&main_stack);
+ INIT_LIST_HEAD(&sibling_stack);
+
+ list_add(&main_dentry->tmp_list, &main_stack);
+
+ while (1) {
+ node = main_dentry->d_inode->children.rb_node;
+
+ while (1) {
+ if (node->rb_left) {
+ list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+ node = node->rb_left;
+ continue;
+ }
+ if (node->rb_right) {
+ list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+ node = node->rb_right;
+ continue;
+ }
+ list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+ }
+
+ pop_sibling:
+ next_sibling = sibling_stack.next;
+ if (next_sibling == sibling_stack_bottom) {
+ main_dentry = container_of(main_stack.next,
+ struct dentry,
+ tmp_list);
+ list_del(&main_dentry->tmp_list);
+
+
+ sibling_stack_bottom = (void*)main_dentry->parent;
+
+ if (main_dentry == root) {
+ main_dentry->parent = main_dentry;
+ ret = visitor(dentry, arg);
+ return ret;
+ } else {
+ main_dentry->parent = container_of(main_stack.next,
+ struct dentry,
+ tmp_list);
+ }
+
+ ret = visitor(main_dentry, arg);
+
+ if (ret != 0) {
+ list_del(&root->tmp_list);
+ list_for_each_entry(dentry, &main_stack, tmp_list) {
+ dentry->parent = container_of(dentry->tmp_list.next,
+ struct dentry,
+ tmp_list);
+ }
+ root->parent = root;
+ return ret;
+ }
+ goto pop_sibling;
+ } else {
+
+ list_del(next_sibling);
+ dentry = container_of(next_sibling, struct dentry, tmp_list);
+
+
+ list_add(&dentry->tmp_list, &main_stack);
+ dentry->parent = (void*)sibling_stack_bottom;
+ sibling_stack_bottom = sibling_stack.next;
+
+ main_dentry = dentry;
+ }
+ }
+#endif
}
/*
}
}
-static int compare_names(const char *name_1, size_t len_1,
- const char *name_2, size_t len_2)
+static int compare_names(const char *name_1, u16 len_1,
+ const char *name_2, u16 len_2)
{
- if (len_1 < len_2)
- return -1;
- else if (len_1 > len_2)
- return 1;
- else
- return memcmp(name_1, name_2, len_1);
+ int result = strncasecmp(name_1, name_2, min(len_1, len_2));
+ if (result) {
+ return result;
+ } else {
+ return (int)len_1 - (int)len_2;
+ }
}
static int dentry_compare_names(const struct dentry *d1, const struct dentry *d2)
inode->link_count = 1;
#ifdef WITH_FUSE
inode->next_stream_id = 1;
+ if (pthread_mutex_init(&inode->i_mutex, NULL) != 0) {
+ ERROR_WITH_ERRNO("Error initializing mutex");
+ FREE(inode);
+ return NULL;
+ }
#endif
INIT_LIST_HEAD(&inode->dentry_list);
}
#ifdef WITH_FUSE
wimlib_assert(inode->num_opened_fds == 0);
FREE(inode->fds);
+ pthread_mutex_destroy(&inode->i_mutex);
#endif
FREE(inode->extracted_file);
FREE(inode);
struct dentry *dentry)
{
u64 cur_offset = dentry->subdir_offset;
- struct dentry *prev_child = NULL;
- struct dentry *first_child = NULL;
struct dentry *child;
struct dentry cur_child;
int ret;
git://wimlib.net / wimlib / blobdiff