#ifndef _WIMLIB_DENTRY_H
#define _WIMLIB_DENTRY_H
+#include "wimlib/avl_tree.h"
#include "wimlib/case.h"
#include "wimlib/compiler.h"
#include "wimlib/inode.h"
#include "wimlib/list.h"
-#include "wimlib/rbtree.h"
#include "wimlib/types.h"
struct wim_inode;
* to all dentries in a hard link group. */
struct wim_inode *d_inode;
- /* Node for the parent's red-black tree of child dentries, sorted by
- * case sensitive long name. */
- struct rb_node rb_node;
+ /* Node for the parent's balanced binary search tree of child dentries
+ * sorted by case sensitive long name (root i_children). */
+ struct avl_tree_node d_index_node;
- /* Node for the parent's red-black tree of child dentries, sorted by
- * case insensitive long name. */
- struct rb_node rb_node_case_insensitive;
+ /* Node for the parent's balanced binary search tree of child dentries,
+ * sorted by case insensitive long name (root i_children_ci). */
+ struct avl_tree_node d_index_node_ci;
/* List of dentries in a directory that have different case sensitive
- * long names but share the same case insensitive long name */
- struct list_head case_insensitive_conflict_list;
+ * long names but share the same case insensitive long name. */
+ struct list_head d_ci_conflict_list;
/* Length of UTF-16LE encoded short filename, in bytes, not including
* the terminating zero wide-character. */
size_t extraction_name_nchars;
};
-#define rbnode_dentry(node) container_of(node, struct wim_dentry, rb_node)
-
static inline bool
dentry_is_first_in_inode(const struct wim_dentry *dentry)
{
int (*visitor)(struct wim_dentry*, void*),
void *args);
-/* Iterate through each @child dentry of the @parent inode,
+/* Iterate through each @child dentry of the @dir directory inode,
* in sorted order (by case sensitive name). */
-#define for_inode_child(child, parent) \
- for (struct rb_node *_tmp = rb_first(&parent->i_children); \
+#define for_inode_child(child, dir) \
+ for (struct avl_tree_node *_tmp = \
+ avl_tree_first_in_order((dir)->i_children); \
_tmp && \
- ((child = rb_entry(_tmp, struct wim_dentry, rb_node)), 1); \
- _tmp = rb_next(_tmp))
+ (((child) = avl_tree_entry(_tmp, struct wim_dentry, \
+ d_index_node)), 1); \
+ _tmp = avl_tree_next_in_order(_tmp))
/* Iterate through each @child dentry of the @parent dentry,
* in sorted order (by case sensitive name). */
#define for_dentry_child(child, parent) \
- for_inode_child(child, parent->d_inode)
-
-/* Iterate through each @child dentry of the @parent inode,
- * in postorder (safe for freeing). */
-#define for_inode_child_postorder(child, parent) \
- for (struct rb_node *_tmp = rb_first_postorder(&parent->i_children), *_parent; \
- _tmp && \
- ((child = rb_entry(_tmp, struct wim_dentry, rb_node)), 1) && \
- ((_parent = rb_parent(_tmp)), 1); \
- _tmp = rb_next_postorder(_tmp, _parent))
+ for_inode_child((child), (parent)->d_inode)
+
+/* Iterate through each @child dentry of the @dir directory inode,
+ * in postorder (safe for freeing the child dentries). */
+#define for_inode_child_postorder(child, dir) \
+ for (struct avl_tree_node *_parent, *_tmp = \
+ avl_tree_first_in_postorder( \
+ (dir)->i_children); \
+ _tmp && \
+ (((child) = avl_tree_entry(_tmp, struct wim_dentry, \
+ d_index_node)), 1) && \
+ ((_parent = avl_get_parent(_tmp)), 1); \
+ _tmp = avl_tree_next_in_postorder(_tmp, _parent))
/* Iterate through each @child dentry of the @parent dentry,
- * in postorder (safe for freeing). */
+ * in postorder (safe for freeing the child dentries). */
#define for_dentry_child_postorder(child, parent) \
- for_inode_child_postorder(child, parent->d_inode)
+ for_inode_child_postorder((child), (parent)->d_inode)
+
+/* Get any child dentry of the @dir directory inode. Requires
+ * inode_has_children(@dir) == true. */
+#define inode_any_child(dir) \
+ avl_tree_entry((dir)->i_children, struct wim_dentry, d_index_node)
+
+/* Get any child dentry of the @parent dentry. Requires
+ * dentry_has_children(@parent) == true. */
+#define dentry_any_child(parent) \
+ inode_any_child((parent)->d_inode)
extern void
calculate_subdir_offsets(struct wim_dentry *root, u64 *subdir_offset_p);
unlink_dentry(struct wim_dentry *dentry);
extern struct wim_dentry *
-dentry_add_child(struct wim_dentry * restrict parent,
- struct wim_dentry * restrict child);
+dentry_add_child(struct wim_dentry *parent, struct wim_dentry *child);
extern int
rename_wim_path(WIMStruct *wim, const tchar *from, const tchar *to,
#include "wimlib/assert.h"
#include "wimlib/list.h"
#include "wimlib/lookup_table.h"
-#include "wimlib/rbtree.h"
#include "wimlib/sha1.h"
#include "wimlib/unix_data.h"
struct wim_security_data;
struct wim_lookup_table;
struct wimfs_fd;
+struct avl_tree_node;
/*
* WIM inode.
* this inode. */
u32 i_attributes;
- /* Root of a red-black tree storing the child dentries of this inode, if
- * any. Keyed by wim_dentry->file_name, case sensitively. */
- struct rb_root i_children;
+ /* Root of a balanced binary search tree storing the child directory
+ * entries of this inode, if any. Keyed by wim_dentry->file_name, case
+ * sensitively. If this inode is not a directory or if it has no
+ * children then this will be an empty tree (NULL). */
+ struct avl_tree_node *i_children;
- /* Root of a red-black tree storing the children of this inode, if any.
- * Keyed by wim_dentry->file_name, case insensitively. */
- struct rb_root i_children_case_insensitive;
+ /* Root of a balanced binary search tree storing the child directory
+ * entries of this inode, if any. Keyed by wim_dentry->file_name, case
+ * insensitively. If this inode is not a directory or if it has no
+ * children then this will be an empty tree (NULL). */
+ struct avl_tree_node *i_children_ci;
/* List of dentries that are aliases for this inode. There will be
* i_nlink dentries in this list. */
/* Does the inode have children?
* Currently (based on read_dentry_tree()), this can only return true for inodes
- * for which inode_is_directory() returns true. However, if a directory is
- * empty, this returns false. */
+ * for which inode_is_directory() returns true. (This also returns false on
+ * empty directories.) */
static inline bool
inode_has_children(const struct wim_inode *inode)
{
- return !rb_empty_root(&inode->i_children);
+ return inode->i_children != NULL;
}
extern int
#ifndef _WIMLIB_SECURITY_H
#define _WIMLIB_SECURITY_H
-#include "wimlib/rbtree.h"
#include "wimlib/types.h"
-/* Red-black tree that maps SHA1 message digests of security descriptors to
- * security IDs, which are themselves indices into the table of security
- * descriptors in the 'struct wim_security_data'. */
+struct wim_security_data;
+struct avl_tree_node;
+
+/* Map from SHA1 message digests of security descriptors to security IDs, which
+ * are themselves indices into the table of security descriptors in the 'struct
+ * wim_security_data'. */
struct wim_sd_set {
struct wim_security_data *sd;
- struct rb_root rb_root;
+ struct avl_tree_node *root;
int32_t orig_num_entries;
};
for_dentry_in_tree(root, dentry_calculate_subdir_offset, subdir_offset_p);
}
+/* Compare the UTF-16LE long filenames of two dentries case insensitively. */
static int
dentry_compare_names_case_insensitive(const struct wim_dentry *d1,
const struct wim_dentry *d2)
true);
}
+/* Compare the UTF-16LE long filenames of two dentries case sensitively. */
static int
dentry_compare_names_case_sensitive(const struct wim_dentry *d1,
const struct wim_dentry *d2)
false);
}
+static int
+_avl_dentry_compare_names_ci(const struct avl_tree_node *n1,
+ const struct avl_tree_node *n2)
+{
+ const struct wim_dentry *d1, *d2;
+
+ d1 = avl_tree_entry(n1, struct wim_dentry, d_index_node_ci);
+ d2 = avl_tree_entry(n2, struct wim_dentry, d_index_node_ci);
+ return dentry_compare_names_case_insensitive(d1, d2);
+}
+
+static int
+_avl_dentry_compare_names(const struct avl_tree_node *n1,
+ const struct avl_tree_node *n2)
+{
+ const struct wim_dentry *d1, *d2;
+
+ d1 = avl_tree_entry(n1, struct wim_dentry, d_index_node);
+ d2 = avl_tree_entry(n2, struct wim_dentry, d_index_node);
+ return dentry_compare_names_case_sensitive(d1, d2);
+}
+
/* Default case sensitivity behavior for searches with
* WIMLIB_CASE_PLATFORM_DEFAULT specified. This can be modified by
* wimlib_global_init(). */
#endif
;
+/* Case-sensitive dentry lookup. Only @file_name and @file_name_nbytes of
+ * @dummy must be valid. */
+static struct wim_dentry *
+dir_lookup(const struct wim_inode *dir, const struct wim_dentry *dummy)
+{
+ struct avl_tree_node *node;
+
+ node = avl_tree_lookup_node(dir->i_children,
+ &dummy->d_index_node,
+ _avl_dentry_compare_names);
+ if (!node)
+ return NULL;
+ return avl_tree_entry(node, struct wim_dentry, d_index_node);
+}
+
+/* Case-insensitive dentry lookup. Only @file_name and @file_name_nbytes of
+ * @dummy must be valid. */
+static struct wim_dentry *
+dir_lookup_ci(const struct wim_inode *dir, const struct wim_dentry *dummy)
+{
+ struct avl_tree_node *node;
+
+ node = avl_tree_lookup_node(dir->i_children_ci,
+ &dummy->d_index_node_ci,
+ _avl_dentry_compare_names_ci);
+ if (!node)
+ return NULL;
+ return avl_tree_entry(node, struct wim_dentry, d_index_node_ci);
+}
+
/* Given a UTF-16LE filename and a directory, look up the dentry for the file.
* Return it if found, otherwise NULL. This is case-sensitive on UNIX and
* case-insensitive on Windows. */
size_t name_nbytes,
CASE_SENSITIVITY_TYPE case_ctype)
{
- struct rb_node *node;
-
+ const struct wim_inode *dir = dentry->d_inode;
bool ignore_case = will_ignore_case(case_ctype);
+ struct wim_dentry dummy;
+ struct wim_dentry *child;
- if (ignore_case)
- node = dentry->d_inode->i_children_case_insensitive.rb_node;
- else
- node = dentry->d_inode->i_children.rb_node;
+ dummy.file_name = (utf16lechar*)name;
+ dummy.file_name_nbytes = name_nbytes;
- struct wim_dentry *child;
- while (node) {
- if (ignore_case)
- child = rb_entry(node, struct wim_dentry, rb_node_case_insensitive);
- else
- child = rb_entry(node, struct wim_dentry, rb_node);
-
- int result = cmp_utf16le_strings(name,
- name_nbytes / 2,
- child->file_name,
- child->file_name_nbytes / 2,
- ignore_case);
- if (result < 0) {
- node = node->rb_left;
- } else if (result > 0) {
- node = node->rb_right;
- } else if (!ignore_case ||
- list_empty(&child->case_insensitive_conflict_list)) {
- return child;
- } else {
- /* Multiple dentries have the same case-insensitive
- * name, and a case-insensitive lookup is being
- * performed. Choose the dentry with the same
- * case-sensitive name, if one exists; otherwise print a
- * warning and choose one arbitrarily. */
- struct wim_dentry *alt = child;
- size_t num_alts = 0;
-
- do {
- num_alts++;
- if (0 == cmp_utf16le_strings(name,
- name_nbytes / 2,
- alt->file_name,
- alt->file_name_nbytes / 2,
- false))
- return alt;
- alt = list_entry(alt->case_insensitive_conflict_list.next,
- struct wim_dentry,
- case_insensitive_conflict_list);
- } while (alt != child);
-
- WARNING("Result of case-insensitive lookup is ambiguous\n"
- " (returning \"%"TS"\" of %zu "
- "possible files, including \"%"TS"\")",
- dentry_full_path(child),
- num_alts,
- dentry_full_path(list_entry(child->case_insensitive_conflict_list.next,
- struct wim_dentry,
- case_insensitive_conflict_list)));
- return child;
- }
- }
- return NULL;
+ if (!ignore_case)
+ /* Case-sensitive lookup. */
+ return dir_lookup(dir, &dummy);
+
+ /* Case-insensitive lookup. */
+
+ child = dir_lookup_ci(dir, &dummy);
+ if (!child)
+ return NULL;
+
+ if (likely(list_empty(&child->d_ci_conflict_list)))
+ /* Only one dentry has this case-insensitive name; return it */
+ return child;
+
+ /* Multiple dentries have the same case-insensitive name. Choose the
+ * dentry with the same case-sensitive name, if one exists; otherwise
+ * print a warning and choose one of the possible dentries arbitrarily.
+ */
+ struct wim_dentry *alt = child;
+ size_t num_alts = 0;
+
+ do {
+ num_alts++;
+ if (!dentry_compare_names_case_sensitive(&dummy, alt))
+ return alt;
+ alt = list_entry(alt->d_ci_conflict_list.next,
+ struct wim_dentry, d_ci_conflict_list);
+ } while (alt != child);
+
+ WARNING("Result of case-insensitive lookup is ambiguous\n"
+ " (returning \"%"TS"\" of %zu "
+ "possible files, including \"%"TS"\")",
+ dentry_full_path(child),
+ num_alts,
+ dentry_full_path(list_entry(child->d_ci_conflict_list.next,
+ struct wim_dentry,
+ d_ci_conflict_list)));
+ return child;
}
/* Returns the child of @dentry that has the file name @name. Returns NULL if
for_dentry_in_tree_depth(root, do_free_dentry, lookup_table);
}
-/* Insert a dentry into the case insensitive index for a directory.
- *
- * This is a red-black tree, but when multiple dentries share the same
- * case-insensitive name, only one is inserted into the tree itself; the rest
- * are connected in a list.
- */
+/* Insert the @child dentry into the case sensitive index of the @dir directory.
+ * Return NULL if successfully inserted, otherwise a pointer to the
+ * already-inserted duplicate. */
static struct wim_dentry *
-dentry_add_child_case_insensitive(struct wim_dentry *parent,
- struct wim_dentry *child)
+dir_index_child(struct wim_inode *dir, struct wim_dentry *child)
{
- struct rb_root *root;
- struct rb_node **new;
- struct rb_node *rb_parent;
-
- root = &parent->d_inode->i_children_case_insensitive;
- new = &root->rb_node;
- rb_parent = NULL;
- while (*new) {
- struct wim_dentry *this = container_of(*new, struct wim_dentry,
- rb_node_case_insensitive);
- int result = dentry_compare_names_case_insensitive(child, this);
-
- rb_parent = *new;
-
- if (result < 0)
- new = &((*new)->rb_left);
- else if (result > 0)
- new = &((*new)->rb_right);
- else
- return this;
- }
- rb_link_node(&child->rb_node_case_insensitive, rb_parent, new);
- rb_insert_color(&child->rb_node_case_insensitive, root);
- return NULL;
+ struct avl_tree_node *duplicate;
+
+ duplicate = avl_tree_insert(&dir->i_children,
+ &child->d_index_node,
+ _avl_dentry_compare_names);
+ if (!duplicate)
+ return NULL;
+ return avl_tree_entry(duplicate, struct wim_dentry, d_index_node);
+}
+
+/* Insert the @child dentry into the case insensitive index of the @dir
+ * directory. Return NULL if successfully inserted, otherwise a pointer to the
+ * already-inserted duplicate. */
+static struct wim_dentry *
+dir_index_child_ci(struct wim_inode *dir, struct wim_dentry *child)
+{
+ struct avl_tree_node *duplicate;
+
+ duplicate = avl_tree_insert(&dir->i_children_ci,
+ &child->d_index_node_ci,
+ _avl_dentry_compare_names_ci);
+ if (!duplicate)
+ return NULL;
+ return avl_tree_entry(duplicate, struct wim_dentry, d_index_node_ci);
+}
+
+/* Removes the specified dentry from its directory's case-sensitive index. */
+static void
+dir_unindex_child(struct wim_inode *dir, struct wim_dentry *child)
+{
+ avl_tree_remove(&dir->i_children, &child->d_index_node);
+}
+
+/* Removes the specified dentry from its directory's case-insensitive index. */
+static void
+dir_unindex_child_ci(struct wim_inode *dir, struct wim_dentry *child)
+{
+ avl_tree_remove(&dir->i_children_ci, &child->d_index_node_ci);
+}
+
+/* Returns true iff the specified dentry is in its parent directory's
+ * case-insensitive index. */
+static bool
+dentry_in_ci_index(const struct wim_dentry *dentry)
+{
+ return !avl_tree_node_is_unlinked(&dentry->d_index_node_ci);
}
/*
* @child: The dentry to link.
*
* Returns NULL if successful. If @parent already contains a dentry with the
- * same case-sensitive name as @child, the pointer to this duplicate dentry is
- * returned.
+ * same case-sensitive name as @child, returns a pointer to this duplicate
+ * dentry.
*/
struct wim_dentry *
-dentry_add_child(struct wim_dentry * restrict parent,
- struct wim_dentry * restrict child)
+dentry_add_child(struct wim_dentry *parent, struct wim_dentry *child)
{
- struct rb_root *root;
- struct rb_node **new;
- struct rb_node *rb_parent;
+ struct wim_dentry *duplicate;
+ struct wim_inode *dir;
- wimlib_assert(dentry_is_directory(parent));
wimlib_assert(parent != child);
- /* Case sensitive child dentry index */
- root = &parent->d_inode->i_children;
- new = &root->rb_node;
- rb_parent = NULL;
- while (*new) {
- struct wim_dentry *this = rbnode_dentry(*new);
- int result = dentry_compare_names_case_sensitive(child, this);
-
- rb_parent = *new;
-
- if (result < 0)
- new = &((*new)->rb_left);
- else if (result > 0)
- new = &((*new)->rb_right);
- else
- return this;
- }
- child->parent = parent;
- rb_link_node(&child->rb_node, rb_parent, new);
- rb_insert_color(&child->rb_node, root);
+ dir = parent->d_inode;
- /* Case insensitive child dentry index */
- {
- struct wim_dentry *existing;
- existing = dentry_add_child_case_insensitive(parent, child);
- if (existing) {
- list_add(&child->case_insensitive_conflict_list,
- &existing->case_insensitive_conflict_list);
- rb_clear_node(&child->rb_node_case_insensitive);
- } else {
- INIT_LIST_HEAD(&child->case_insensitive_conflict_list);
- }
+ wimlib_assert(inode_is_directory(dir));
+
+ duplicate = dir_index_child(dir, child);
+ if (duplicate)
+ return duplicate;
+
+ duplicate = dir_index_child_ci(dir, child);
+ if (duplicate) {
+ list_add(&child->d_ci_conflict_list, &duplicate->d_ci_conflict_list);
+ avl_tree_node_set_unlinked(&child->d_index_node_ci);
+ } else {
+ INIT_LIST_HEAD(&child->d_ci_conflict_list);
}
+ child->parent = parent;
return NULL;
}
-/* Unlink a WIM dentry from the directory entry tree. */
+/* Unlink a WIM dentry from the directory entry tree. */
void
unlink_dentry(struct wim_dentry *dentry)
{
- struct wim_dentry *parent = dentry->parent;
+ struct wim_inode *dir;
- if (parent == dentry)
+ if (dentry_is_root(dentry))
return;
- rb_erase(&dentry->rb_node, &parent->d_inode->i_children);
- if (!rb_empty_node(&dentry->rb_node_case_insensitive)) {
- /* This dentry was in the case-insensitive red-black tree. */
- rb_erase(&dentry->rb_node_case_insensitive,
- &parent->d_inode->i_children_case_insensitive);
- if (!list_empty(&dentry->case_insensitive_conflict_list)) {
+ dir = dentry->parent->d_inode;
+
+ dir_unindex_child(dir, dentry);
+
+ if (dentry_in_ci_index(dentry)) {
+
+ dir_unindex_child_ci(dir, dentry);
+
+ if (!list_empty(&dentry->d_ci_conflict_list)) {
/* Make a different case-insensitively-the-same dentry
- * be the "representative" in the red-black tree. */
+ * be the "representative" in the search index. */
struct list_head *next;
struct wim_dentry *other;
struct wim_dentry *existing;
- next = dentry->case_insensitive_conflict_list.next;
- other = list_entry(next, struct wim_dentry, case_insensitive_conflict_list);
- existing = dentry_add_child_case_insensitive(parent, other);
+ next = dentry->d_ci_conflict_list.next;
+ other = list_entry(next, struct wim_dentry, d_ci_conflict_list);
+ existing = dir_index_child_ci(dir, other);
wimlib_assert(existing == NULL);
}
}
- list_del(&dentry->case_insensitive_conflict_list);
+ list_del(&dentry->d_ci_conflict_list);
}
static int
*/
/*
- * Copyright (C) 2012, 2013 Eric Biggers
+ * Copyright (C) 2012, 2013, 2014 Eric Biggers
*
* This file is part of wimlib, a library for working with WIM files.
*
if (!ctx->ops->supports_case_sensitive_filenames)
{
struct wim_dentry *other;
- list_for_each_entry(other, &dentry->case_insensitive_conflict_list,
- case_insensitive_conflict_list)
+ list_for_each_entry(other, &dentry->d_ci_conflict_list,
+ d_ci_conflict_list)
{
if (dentry_in_list(other)) {
if (ctx->extract_flags &
*/
/*
- * Copyright (C) 2012, 2013 Eric Biggers
+ * Copyright (C) 2012, 2013, 2014 Eric Biggers
*
* This file is part of wimlib, a library for working with WIM files.
*
return ret;
}
-/* Red-black tree that maps NTFS inode numbers to DOS names */
+/* Binary tree that maps NTFS inode numbers to DOS names */
struct dos_name_map {
- struct rb_root rb_root;
+ struct avl_tree_node *root;
};
struct dos_name_node {
- struct rb_node rb_node;
+ struct avl_tree_node index_node;
char dos_name[24];
int name_nbytes;
le64 ntfs_ino;
};
+#define DOS_NAME_NODE(avl_node) \
+ avl_tree_entry(avl_node, struct dos_name_node, index_node)
+
+static int
+_avl_cmp_by_ntfs_ino(const struct avl_tree_node *n1,
+ const struct avl_tree_node *n2)
+{
+ return cmp_u64(DOS_NAME_NODE(n1)->ntfs_ino,
+ DOS_NAME_NODE(n2)->ntfs_ino);
+}
+
/* Inserts a new DOS name into the map */
static int
insert_dos_name(struct dos_name_map *map, const ntfschar *dos_name,
size_t name_nbytes, le64 ntfs_ino)
{
struct dos_name_node *new_node;
- struct rb_node **p;
- struct rb_root *root;
- struct rb_node *rb_parent;
DEBUG("DOS name_len = %zu", name_nbytes);
new_node = MALLOC(sizeof(struct dos_name_node));
wimlib_assert(name_nbytes <= sizeof(new_node->dos_name));
/* Initialize the DOS name, DOS name length, and NTFS inode number of
- * the red-black tree node */
+ * the search tree node */
memcpy(new_node->dos_name, dos_name, name_nbytes);
new_node->name_nbytes = name_nbytes;
new_node->ntfs_ino = ntfs_ino;
- /* Insert the red-black tree node */
- root = &map->rb_root;
- p = &root->rb_node;
- rb_parent = NULL;
- while (*p) {
- struct dos_name_node *this;
-
- this = container_of(*p, struct dos_name_node, rb_node);
- rb_parent = *p;
- if (new_node->ntfs_ino < this->ntfs_ino)
- p = &((*p)->rb_left);
- else if (new_node->ntfs_ino > this->ntfs_ino)
- p = &((*p)->rb_right);
- else {
- /* This should be impossible since a NTFS inode cannot
- * have multiple DOS names, and we only should get each
- * DOS name entry once from the ntfs_readdir() calls. */
- ERROR("NTFS inode %"PRIu64" has multiple DOS names",
- le64_to_cpu(ntfs_ino));
- return -1;
- }
+ /* Insert the search tree node */
+ if (avl_tree_insert(&map->root, &new_node->index_node,
+ _avl_cmp_by_ntfs_ino))
+ {
+ /* This should be impossible since a NTFS inode cannot
+ * have multiple DOS names, and we only should get each
+ * DOS name entry once from the ntfs_readdir() calls. */
+ ERROR("NTFS inode %"PRIu64" has multiple DOS names",
+ le64_to_cpu(ntfs_ino));
+ FREE(new_node);
+ return -1;
}
- rb_link_node(&new_node->rb_node, rb_parent, p);
- rb_insert_color(&new_node->rb_node, root);
DEBUG("Inserted DOS name for inode %"PRIu64, le64_to_cpu(ntfs_ino));
return 0;
}
static struct dos_name_node *
lookup_dos_name(const struct dos_name_map *map, u64 ntfs_ino)
{
- struct rb_node *node = map->rb_root.rb_node;
- while (node) {
- struct dos_name_node *this;
- this = container_of(node, struct dos_name_node, rb_node);
- if (ntfs_ino < this->ntfs_ino)
- node = node->rb_left;
- else if (ntfs_ino > this->ntfs_ino)
- node = node->rb_right;
- else
- return this;
- }
- return NULL;
+ struct dos_name_node dummy;
+ struct avl_tree_node *res;
+
+ dummy.ntfs_ino = cpu_to_le64(ntfs_ino);
+
+ res = avl_tree_lookup_node(map->root, &dummy.index_node,
+ _avl_cmp_by_ntfs_ino);
+ if (!res)
+ return NULL;
+ return DOS_NAME_NODE(res);
}
static int
}
static void
-free_dos_name_tree(struct rb_node *node) {
+free_dos_name_tree(struct avl_tree_node *node) {
if (node) {
- free_dos_name_tree(node->rb_left);
- free_dos_name_tree(node->rb_right);
- FREE(container_of(node, struct dos_name_node, rb_node));
+ free_dos_name_tree(node->left);
+ free_dos_name_tree(node->right);
+ FREE(DOS_NAME_NODE(node));
}
}
static void
destroy_dos_name_map(struct dos_name_map *map)
{
- free_dos_name_tree(map->rb_root.rb_node);
+ free_dos_name_tree(map->root);
}
struct readdir_ctx {
/* Recurse to directory children */
s64 pos = 0;
- struct dos_name_map dos_name_map = { .rb_root = {.rb_node = NULL} };
+ struct dos_name_map dos_name_map = { .root = NULL };
struct readdir_ctx ctx = {
.parent = root,
.path = path,
*/
/*
- * Copyright (C) 2012, 2013 Eric Biggers
+ * Copyright (C) 2012, 2013, 2014 Eric Biggers
*
* This file is part of wimlib, a library for working with WIM files.
*
#endif
#include "wimlib/assert.h"
+#include "wimlib/avl_tree.h"
#include "wimlib/endianness.h"
#include "wimlib/error.h"
#include "wimlib/security.h"
struct sd_node {
int security_id;
u8 hash[SHA1_HASH_SIZE];
- struct rb_node rb_node;
+ struct avl_tree_node index_node;
};
+#define SD_NODE(avl_node) \
+ avl_tree_entry(avl_node, struct sd_node, index_node)
+
static void
-free_sd_tree(struct rb_node *node)
+free_sd_tree(struct avl_tree_node *node)
{
if (node) {
- free_sd_tree(node->rb_left);
- free_sd_tree(node->rb_right);
- FREE(container_of(node, struct sd_node, rb_node));
+ free_sd_tree(node->left);
+ free_sd_tree(node->right);
+ FREE(SD_NODE(node));
}
}
FREE(*descriptors++);
sd->num_entries = sd_set->orig_num_entries;
}
- free_sd_tree(sd_set->rb_root.rb_node);
+ free_sd_tree(sd_set->root);
}
-/* Inserts a a new node into the security descriptor index tree. */
+static int
+_avl_cmp_nodes_by_hash(const struct avl_tree_node *n1,
+ const struct avl_tree_node *n2)
+{
+ return hashes_cmp(SD_NODE(n1)->hash, SD_NODE(n2)->hash);
+}
+
+/* Inserts a a new node into the security descriptor index tree. Returns true
+ * if successful (not a duplicate). */
static bool
insert_sd_node(struct wim_sd_set *set, struct sd_node *new)
{
- struct rb_root *root = &set->rb_root;
- struct rb_node **p = &(root->rb_node);
- struct rb_node *rb_parent = NULL;
-
- while (*p) {
- struct sd_node *this = container_of(*p, struct sd_node, rb_node);
- int cmp = hashes_cmp(new->hash, this->hash);
-
- rb_parent = *p;
- if (cmp < 0)
- p = &((*p)->rb_left);
- else if (cmp > 0)
- p = &((*p)->rb_right);
- else
- return false; /* Duplicate security descriptor */
- }
- rb_link_node(&new->rb_node, rb_parent, p);
- rb_insert_color(&new->rb_node, root);
- return true;
+ return NULL == avl_tree_insert(&set->root, &new->index_node,
+ _avl_cmp_nodes_by_hash);
}
/* Returns the index of the security descriptor having a SHA1 message digest of
static int
lookup_sd(struct wim_sd_set *set, const u8 hash[SHA1_HASH_SIZE])
{
- struct rb_node *node = set->rb_root.rb_node;
-
- while (node) {
- struct sd_node *sd_node = container_of(node, struct sd_node, rb_node);
- int cmp = hashes_cmp(hash, sd_node->hash);
- if (cmp < 0)
- node = node->rb_left;
- else if (cmp > 0)
- node = node->rb_right;
- else
- return sd_node->security_id;
- }
- return -1;
+ struct avl_tree_node *res;
+ struct sd_node dummy;
+
+ copy_hash(dummy.hash, hash);
+ res = avl_tree_lookup_node(set->root, &dummy.index_node,
+ _avl_cmp_nodes_by_hash);
+ if (!res)
+ return -1;
+ return SD_NODE(res)->security_id;
}
/*
int ret;
sd_set->sd = sd;
- sd_set->rb_root.rb_node = NULL;
+ sd_set->root = NULL;
/* Remember the original number of security descriptors so that newly
* added ones can be rolled back if needed. */
static int
do_overlay(struct wim_dentry *target, struct wim_dentry *branch)
{
- struct rb_root *rb_root;
-
DEBUG("Doing overlay \"%"WS"\" => \"%"WS"\"",
branch->file_name, target->file_name);
return WIMLIB_ERR_INVALID_OVERLAY;
}
- rb_root = &branch->d_inode->i_children;
LIST_HEAD(moved_children);
- while (rb_root->rb_node) { /* While @branch has children... */
- struct wim_dentry *child = rbnode_dentry(rb_root->rb_node);
+ while (dentry_has_children(branch)) {
+ struct wim_dentry *child = dentry_any_child(branch);
struct wim_dentry *existing;
/* Move @child to the directory @target */