*/
/*
- * 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 (len + 7) & ~7;
}
+static int
+dentry_clear_short_name(struct wim_dentry *dentry)
+{
+ if (dentry_has_short_name(dentry)) {
+ FREE(dentry->short_name);
+ dentry->short_name = NULL;
+ dentry->short_name_nbytes = 0;
+ }
+ return 0;
+}
+
/* Sets the name of a WIM dentry from a multibyte string.
* Only use this on dentries not inserted into the tree. Use rename_wim_path()
* to do a real rename. */
dentry_set_name(struct wim_dentry *dentry, const tchar *new_name)
{
int ret;
+
ret = get_utf16le_string(new_name, &dentry->file_name,
&dentry->file_name_nbytes);
- if (ret == 0) {
- /* Clear the short name and recalculate the dentry length */
- if (dentry_has_short_name(dentry)) {
- FREE(dentry->short_name);
- dentry->short_name = NULL;
- dentry->short_name_nbytes = 0;
- }
+ if (ret)
+ return ret;
+
+ return dentry_clear_short_name(dentry);
+}
+
+/* Sets the name of a WIM dentry from a UTF-16LE string.
+ * Only use this on dentries not inserted into the tree. Use rename_wim_path()
+ * to do a real rename. */
+int
+dentry_set_name_utf16le(struct wim_dentry *dentry, const utf16lechar *new_name)
+{
+ utf16lechar *name = NULL;
+ size_t name_nbytes = 0;
+
+ if (new_name && *new_name) {
+ const utf16lechar *tmp;
+
+ tmp = new_name;
+ do {
+ name_nbytes += sizeof(utf16lechar);
+ } while (*++tmp);
+
+ name = memdup(new_name, name_nbytes + sizeof(utf16lechar));
+ if (!name)
+ return WIMLIB_ERR_NOMEM;
}
- return ret;
+
+ FREE(dentry->file_name);
+ dentry->file_name = name;
+ dentry->file_name_nbytes = name_nbytes;
+
+ return dentry_clear_short_name(dentry);
}
/* Returns the total length of a WIM alternate data stream entry on-disk,
return (length + 7) & ~7;
}
-int
-for_dentry_in_rbtree(struct rb_node *root,
- int (*visitor)(struct wim_dentry *, void *),
- void *arg)
-{
- int ret;
- struct rb_node *node = root;
- LIST_HEAD(stack);
- while (1) {
- if (node) {
- list_add(&rbnode_dentry(node)->tmp_list, &stack);
- node = node->rb_left;
- } else {
- struct list_head *next;
- struct wim_dentry *dentry;
-
- next = stack.next;
- if (next == &stack)
- return 0;
- dentry = container_of(next, struct wim_dentry, tmp_list);
- list_del(next);
- ret = visitor(dentry, arg);
- if (ret != 0)
- return ret;
- node = dentry->rb_node.rb_right;
- }
- }
-}
-
static int
-for_dentry_tree_in_rbtree_depth(struct rb_node *node,
- int (*visitor)(struct wim_dentry*, void*),
- void *arg)
+do_for_dentry_in_tree(struct wim_dentry *dentry,
+ int (*visitor)(struct wim_dentry *, void *), void *arg)
{
int ret;
- if (node) {
- ret = for_dentry_tree_in_rbtree_depth(node->rb_left,
- visitor, arg);
- if (ret != 0)
- return ret;
- ret = for_dentry_tree_in_rbtree_depth(node->rb_right,
- visitor, arg);
- if (ret != 0)
- return ret;
- ret = for_dentry_in_tree_depth(rbnode_dentry(node), visitor, arg);
- if (ret != 0)
+ struct wim_dentry *child;
+
+ ret = (*visitor)(dentry, arg);
+ if (unlikely(ret))
+ return ret;
+
+ for_dentry_child(child, dentry) {
+ ret = do_for_dentry_in_tree(child, visitor, arg);
+ if (unlikely(ret))
return ret;
}
return 0;
}
+
static int
-for_dentry_tree_in_rbtree(struct rb_node *node,
- int (*visitor)(struct wim_dentry*, void*),
- void *arg)
+do_for_dentry_in_tree_depth(struct wim_dentry *dentry,
+ int (*visitor)(struct wim_dentry *, void *), void *arg)
{
int ret;
- if (node) {
- ret = for_dentry_tree_in_rbtree(node->rb_left, visitor, arg);
- if (ret)
- return ret;
- ret = for_dentry_in_tree(rbnode_dentry(node), visitor, arg);
- if (ret)
- return ret;
- ret = for_dentry_tree_in_rbtree(node->rb_right, visitor, arg);
- if (ret)
+ struct wim_dentry *child;
+
+ for_dentry_child_postorder(child, dentry) {
+ ret = do_for_dentry_in_tree_depth(child, visitor, arg);
+ if (unlikely(ret))
return ret;
}
- return 0;
-}
-
-/*
- * Iterate over all children of @dentry, calling the function @visitor, passing
- * it a child dentry and the extra argument @arg.
- *
- * Note: this function iterates over ALL child dentries, even those with the
- * same case-insensitive name.
- *
- * Note: this function clobbers the tmp_list field of the child dentries. */
-int
-for_dentry_child(const struct wim_dentry *dentry,
- int (*visitor)(struct wim_dentry *, void *),
- void *arg)
-{
- return for_dentry_in_rbtree(dentry->d_inode->i_children.rb_node,
- visitor,
- arg);
+ return unlikely((*visitor)(dentry, arg));
}
/* Calls a function on all directory entries in a WIM dentry tree. Logically,
* */
int
for_dentry_in_tree(struct wim_dentry *root,
- int (*visitor)(struct wim_dentry*, void*), void *arg)
+ int (*visitor)(struct wim_dentry *, void *), void *arg)
{
- int ret;
-
- if (root == NULL)
+ if (unlikely(!root))
return 0;
- ret = (*visitor)(root, arg);
- if (ret)
- return ret;
- return for_dentry_tree_in_rbtree(root->d_inode->i_children.rb_node,
- visitor,
- arg);
+ return do_for_dentry_in_tree(root, visitor, arg);
}
/* Like for_dentry_in_tree(), but the visitor function is always called on a
* dentry's children before on itself. */
int
for_dentry_in_tree_depth(struct wim_dentry *root,
- int (*visitor)(struct wim_dentry*, void*), void *arg)
+ int (*visitor)(struct wim_dentry *, void *), void *arg)
{
- int ret;
-
- if (root == NULL)
+ if (unlikely(!root))
return 0;
- ret = for_dentry_tree_in_rbtree_depth(root->d_inode->i_children.rb_node,
- visitor, arg);
- if (ret)
- return ret;
- return (*visitor)(root, arg);
+ return do_for_dentry_in_tree_depth(root, visitor, arg);
}
-/* Calculate the full path of @dentry. The full path of its parent must have
- * already been calculated, or it must be the root dentry. */
+/* Calculate the full path of @dentry. */
int
calculate_dentry_full_path(struct wim_dentry *dentry)
{
return 0;
}
-static int
-do_calculate_dentry_full_path(struct wim_dentry *dentry, void *_ignore)
-{
- return calculate_dentry_full_path(dentry);
-}
-
-int
-calculate_dentry_tree_full_paths(struct wim_dentry *root)
-{
- return for_dentry_in_tree(root, do_calculate_dentry_full_path, NULL);
-}
-
tchar *
dentry_full_path(struct wim_dentry *dentry)
{
}
static int
-increment_subdir_offset(struct wim_dentry *dentry, void *subdir_offset_p)
+dentry_calculate_subdir_offset(struct wim_dentry *dentry, void *_subdir_offset_p)
{
- *(u64*)subdir_offset_p += dentry_out_total_length(dentry);
- return 0;
-}
-static int
-call_calculate_subdir_offsets(struct wim_dentry *dentry, void *subdir_offset_p)
-{
- calculate_subdir_offsets(dentry, subdir_offset_p);
+ if (dentry_is_directory(dentry)) {
+ u64 *subdir_offset_p = _subdir_offset_p;
+ struct wim_dentry *child;
+
+ /* Set offset of directory's child dentries */
+ dentry->subdir_offset = *subdir_offset_p;
+
+ /* Account for child dentries */
+ for_dentry_child(child, dentry)
+ *subdir_offset_p += dentry_out_total_length(child);
+
+ /* Account for end-of-directory entry */
+ *subdir_offset_p += 8;
+ } else {
+ /* Not a directory; set subdir_offset to 0 */
+ dentry->subdir_offset = 0;
+ }
return 0;
}
/*
- * Recursively calculates the subdir offsets for a directory tree.
- *
- * @dentry: The root of the directory tree.
- * @subdir_offset_p: The current subdirectory offset; i.e., the subdirectory
- * offset for @dentry.
+ * Calculates the subdir offsets for a directory tree.
*/
void
-calculate_subdir_offsets(struct wim_dentry *dentry, u64 *subdir_offset_p)
+calculate_subdir_offsets(struct wim_dentry *root, u64 *subdir_offset_p)
{
- struct rb_node *node;
-
- dentry->subdir_offset = *subdir_offset_p;
- node = dentry->d_inode->i_children.rb_node;
- if (node) {
- /* Advance the subdir offset by the amount of space the children
- * of this dentry take up. */
- for_dentry_in_rbtree(node, increment_subdir_offset, subdir_offset_p);
-
- /* End-of-directory dentry on disk. */
- *subdir_offset_p += 8;
-
- /* Recursively call calculate_subdir_offsets() on all the
- * children. */
- for_dentry_in_rbtree(node, call_calculate_subdir_offsets, subdir_offset_p);
- } else {
- /* On disk, childless directories have a valid subdir_offset
- * that points to an 8-byte end-of-directory dentry. Regular
- * files or reparse points have a subdir_offset of 0. */
- if (dentry_is_directory(dentry))
- *subdir_offset_p += 8;
- else
- dentry->subdir_offset = 0;
- }
+ 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
if (ads_entry) {
stream_idx = ads_idx + 1;
lte = ads_entry->lte;
- goto out;
} else {
return -ENOENT;
}
} else {
lte = inode_unnamed_stream_resolved(inode, &stream_idx);
}
-out:
if (dentry_ret)
*dentry_ret = dentry;
if (lte_ret)
}
#endif /* WITH_FUSE */
-/* Prints the full path of a dentry. */
-int
-print_dentry_full_path(struct wim_dentry *dentry, void *_ignore)
-{
- int ret = calculate_dentry_full_path(dentry);
- if (ret)
- return ret;
- tprintf(T("%"TS"\n"), dentry->_full_path);
- return 0;
-}
-
-/* We want to be able to show the names of the file attribute flags that are
- * set. */
-struct file_attr_flag {
- u32 flag;
- const tchar *name;
-};
-struct file_attr_flag file_attr_flags[] = {
- {FILE_ATTRIBUTE_READONLY, T("READONLY")},
- {FILE_ATTRIBUTE_HIDDEN, T("HIDDEN")},
- {FILE_ATTRIBUTE_SYSTEM, T("SYSTEM")},
- {FILE_ATTRIBUTE_DIRECTORY, T("DIRECTORY")},
- {FILE_ATTRIBUTE_ARCHIVE, T("ARCHIVE")},
- {FILE_ATTRIBUTE_DEVICE, T("DEVICE")},
- {FILE_ATTRIBUTE_NORMAL, T("NORMAL")},
- {FILE_ATTRIBUTE_TEMPORARY, T("TEMPORARY")},
- {FILE_ATTRIBUTE_SPARSE_FILE, T("SPARSE_FILE")},
- {FILE_ATTRIBUTE_REPARSE_POINT, T("REPARSE_POINT")},
- {FILE_ATTRIBUTE_COMPRESSED, T("COMPRESSED")},
- {FILE_ATTRIBUTE_OFFLINE, T("OFFLINE")},
- {FILE_ATTRIBUTE_NOT_CONTENT_INDEXED,T("NOT_CONTENT_INDEXED")},
- {FILE_ATTRIBUTE_ENCRYPTED, T("ENCRYPTED")},
- {FILE_ATTRIBUTE_VIRTUAL, T("VIRTUAL")},
-};
-
-/* Prints a directory entry. @lookup_table is a pointer to the lookup table, if
- * available. If the dentry is unresolved and the lookup table is NULL, the
- * lookup table entries will not be printed. Otherwise, they will be. */
-int
-print_dentry(struct wim_dentry *dentry, void *lookup_table)
-{
- const u8 *hash;
- struct wim_lookup_table_entry *lte;
- const struct wim_inode *inode = dentry->d_inode;
- tchar buf[50];
-
- tprintf(T("[DENTRY]\n"));
- tprintf(T("Length = %"PRIu64"\n"), dentry->length);
- tprintf(T("Attributes = 0x%x\n"), inode->i_attributes);
- for (size_t i = 0; i < ARRAY_LEN(file_attr_flags); i++)
- if (file_attr_flags[i].flag & inode->i_attributes)
- tprintf(T(" FILE_ATTRIBUTE_%"TS" is set\n"),
- file_attr_flags[i].name);
- tprintf(T("Security ID = %d\n"), inode->i_security_id);
- tprintf(T("Subdir offset = %"PRIu64"\n"), dentry->subdir_offset);
-
- wim_timestamp_to_str(inode->i_creation_time, buf, sizeof(buf));
- tprintf(T("Creation Time = %"TS"\n"), buf);
-
- wim_timestamp_to_str(inode->i_last_access_time, buf, sizeof(buf));
- tprintf(T("Last Access Time = %"TS"\n"), buf);
-
- wim_timestamp_to_str(inode->i_last_write_time, buf, sizeof(buf));
- tprintf(T("Last Write Time = %"TS"\n"), buf);
-
- if (inode->i_attributes & FILE_ATTRIBUTE_REPARSE_POINT) {
- tprintf(T("Reparse Tag = 0x%"PRIx32"\n"), inode->i_reparse_tag);
- tprintf(T("Reparse Point Flags = 0x%"PRIx16"\n"),
- inode->i_not_rpfixed);
- tprintf(T("Reparse Point Unknown 2 = 0x%"PRIx32"\n"),
- inode->i_rp_unknown_2);
- }
- tprintf(T("Reparse Point Unknown 1 = 0x%"PRIx32"\n"),
- inode->i_rp_unknown_1);
- tprintf(T("Hard Link Group = 0x%"PRIx64"\n"), inode->i_ino);
- tprintf(T("Hard Link Group Size = %"PRIu32"\n"), inode->i_nlink);
- tprintf(T("Number of Alternate Data Streams = %hu\n"), inode->i_num_ads);
- if (dentry_has_long_name(dentry))
- wimlib_printf(T("Filename = \"%"WS"\"\n"), dentry->file_name);
- if (dentry_has_short_name(dentry))
- wimlib_printf(T("Short Name \"%"WS"\"\n"), dentry->short_name);
- if (dentry->_full_path)
- tprintf(T("Full Path = \"%"TS"\"\n"), dentry->_full_path);
-
- lte = inode_stream_lte(dentry->d_inode, 0, lookup_table);
- if (lte) {
- print_lookup_table_entry(lte, stdout);
- } else {
- hash = inode_stream_hash(inode, 0);
- if (hash) {
- tprintf(T("Hash = 0x"));
- print_hash(hash, stdout);
- tputchar(T('\n'));
- tputchar(T('\n'));
- }
- }
- for (u16 i = 0; i < inode->i_num_ads; i++) {
- tprintf(T("[Alternate Stream Entry %u]\n"), i);
- wimlib_printf(T("Name = \"%"WS"\"\n"),
- inode->i_ads_entries[i].stream_name);
- tprintf(T("Name Length (UTF16 bytes) = %hu\n"),
- inode->i_ads_entries[i].stream_name_nbytes);
- hash = inode_stream_hash(inode, i + 1);
- if (hash) {
- tprintf(T("Hash = 0x"));
- print_hash(hash, stdout);
- tputchar(T('\n'));
- }
- print_lookup_table_entry(inode_stream_lte(inode, i + 1, lookup_table),
- stdout);
- }
- return 0;
-}
-
-/* Initializations done on every `struct wim_dentry'. */
-static void
-dentry_common_init(struct wim_dentry *dentry)
-{
- memset(dentry, 0, sizeof(struct wim_dentry));
-}
-
/* Creates an unlinked directory entry. */
int
new_dentry(const tchar *name, struct wim_dentry **dentry_ret)
struct wim_dentry *dentry;
int ret;
- dentry = MALLOC(sizeof(struct wim_dentry));
- if (dentry == NULL)
+ dentry = CALLOC(1, sizeof(struct wim_dentry));
+ if (!dentry)
return WIMLIB_ERR_NOMEM;
- dentry_common_init(dentry);
if (*name) {
ret = dentry_set_name(dentry, name);
if (ret) {
}
int
-new_filler_directory(const tchar *name, struct wim_dentry **dentry_ret)
+new_filler_directory(struct wim_dentry **dentry_ret)
{
int ret;
struct wim_dentry *dentry;
- DEBUG("Creating filler directory \"%"TS"\"", name);
- ret = new_dentry_with_inode(name, &dentry);
+ ret = new_dentry_with_inode(T(""), &dentry);
if (ret)
return ret;
/* Leave the inode number as 0; this is allowed for non
for_dentry_in_tree(root, dentry_clear_inode_visited, NULL);
}
-/* Frees a WIM dentry.
+/*
+ * Free a WIM dentry.
*
- * The corresponding inode (if any) is freed only if its link count is
- * decremented to 0. */
+ * In addition to freeing the dentry itself, this decrements the link count of
+ * the corresponding inode (if any). If the inode's link count reaches 0, the
+ * inode is freed as well.
+ */
void
free_dentry(struct wim_dentry *dentry)
{
}
}
-/* This function is passed as an argument to for_dentry_in_tree_depth() in order
- * to free a directory tree. */
static int
-do_free_dentry(struct wim_dentry *dentry, void *_lookup_table)
+do_free_dentry(struct wim_dentry *dentry, void *_ignore)
{
- struct wim_lookup_table *lookup_table = _lookup_table;
-
- if (lookup_table) {
- struct wim_inode *inode = dentry->d_inode;
- for (unsigned i = 0; i <= inode->i_num_ads; i++) {
- struct wim_lookup_table_entry *lte;
+ free_dentry(dentry);
+ return 0;
+}
- lte = inode_stream_lte(inode, i, lookup_table);
- if (lte)
- lte_decrement_refcnt(lte, lookup_table);
- }
- }
+static int
+do_free_dentry_and_unref_streams(struct wim_dentry *dentry, void *lookup_table)
+{
+ inode_unref_streams(dentry->d_inode, lookup_table);
free_dentry(dentry);
return 0;
}
/*
- * Unlinks and frees a dentry tree.
+ * Recursively frees all directory entries in the specified tree.
*
* @root:
* The root of the tree.
* The lookup table for dentries. If non-NULL, the reference counts in the
* lookup table for the lookup table entries corresponding to the dentries
* will be decremented.
+ *
+ * This also puts references to the corresponding inodes.
+ *
+ * This does *not* unlink @root from its parent directory (if it has one).
*/
void
free_dentry_tree(struct wim_dentry *root, struct wim_lookup_table *lookup_table)
{
- for_dentry_in_tree_depth(root, do_free_dentry, lookup_table);
+ int (*f)(struct wim_dentry *, void *);
+
+ if (lookup_table)
+ f = do_free_dentry_and_unref_streams;
+ else
+ f = do_free_dentry;
+
+ for_dentry_in_tree_depth(root, f, 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);
- child->rb_node_case_insensitive.__rb_parent_color = 0;
- } 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 (dentry->rb_node_case_insensitive.__rb_parent_color) {
- /* 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);
-}
-
-static int
-free_dentry_full_path(struct wim_dentry *dentry, void *_ignore)
-{
- FREE(dentry->_full_path);
- dentry->_full_path = NULL;
- return 0;
-}
-
-/* Rename a file or directory in the WIM. */
-int
-rename_wim_path(WIMStruct *wim, const tchar *from, const tchar *to,
- CASE_SENSITIVITY_TYPE case_type)
-{
- struct wim_dentry *src;
- struct wim_dentry *dst;
- struct wim_dentry *parent_of_dst;
- int ret;
-
- /* This rename() implementation currently only supports actual files
- * (not alternate data streams) */
-
- src = get_dentry(wim, from, case_type);
- if (!src)
- return -errno;
-
- dst = get_dentry(wim, to, case_type);
-
- if (dst) {
- /* Destination file exists */
-
- if (src == dst) /* Same file */
- return 0;
-
- if (!dentry_is_directory(src)) {
- /* Cannot rename non-directory to directory. */
- if (dentry_is_directory(dst))
- return -EISDIR;
- } else {
- /* Cannot rename directory to a non-directory or a non-empty
- * directory */
- if (!dentry_is_directory(dst))
- return -ENOTDIR;
- if (dentry_has_children(dst))
- return -ENOTEMPTY;
- }
- parent_of_dst = dst->parent;
- } else {
- /* Destination does not exist */
- parent_of_dst = get_parent_dentry(wim, to, case_type);
- if (!parent_of_dst)
- return -errno;
-
- if (!dentry_is_directory(parent_of_dst))
- return -ENOTDIR;
- }
-
- ret = dentry_set_name(src, path_basename(to));
- if (ret)
- return -ENOMEM;
- if (dst) {
- unlink_dentry(dst);
- free_dentry_tree(dst, wim->lookup_table);
- }
- unlink_dentry(src);
- dentry_add_child(parent_of_dst, src);
- if (src->_full_path)
- for_dentry_in_tree(src, free_dentry_full_path, NULL);
- return 0;
+ list_del(&dentry->d_ci_conflict_list);
}
/* Reads a WIM directory entry, including all alternate data stream entries that
p = &buf[offset];
disk_dentry = (const struct wim_dentry_on_disk*)p;
- if (unlikely((uintptr_t)p & 7))
- WARNING("WIM dentry is not 8-byte aligned");
-
/* Get dentry length. */
length = le64_to_cpu(disk_dentry->length);
inode->i_attributes = le32_to_cpu(disk_dentry->attributes);
inode->i_security_id = le32_to_cpu(disk_dentry->security_id);
dentry->subdir_offset = le64_to_cpu(disk_dentry->subdir_offset);
- dentry->d_unused_1 = le64_to_cpu(disk_dentry->unused_1);
- dentry->d_unused_2 = le64_to_cpu(disk_dentry->unused_2);
inode->i_creation_time = le64_to_cpu(disk_dentry->creation_time);
inode->i_last_access_time = le64_to_cpu(disk_dentry->last_access_time);
inode->i_last_write_time = le64_to_cpu(disk_dentry->last_write_time);
return ret;
}
-static const tchar *
-dentry_get_file_type_string(const struct wim_dentry *dentry)
-{
- const struct wim_inode *inode = dentry->d_inode;
- if (inode_is_directory(inode))
- return T("directory");
- else if (inode_is_symlink(inode))
- return T("symbolic link");
- else
- return T("file");
-}
-
static bool
dentry_is_dot_or_dotdot(const struct wim_dentry *dentry)
{
/* We already found a dentry with this same
* case-sensitive long name. Only keep the first one.
*/
- const tchar *child_type, *duplicate_type;
- child_type = dentry_get_file_type_string(child);
- duplicate_type = dentry_get_file_type_string(duplicate);
- WARNING("Ignoring duplicate %"TS" \"%"TS"\" "
- "(the WIM image already contains a %"TS" "
+ WARNING("Ignoring duplicate file \"%"TS"\" "
+ "(the WIM image already contains a file "
"at that path with the exact same name)",
- child_type, dentry_full_path(duplicate),
- duplicate_type);
+ dentry_full_path(duplicate));
free_dentry(child);
continue;
}
disk_dentry->attributes = cpu_to_le32(inode->i_attributes);
disk_dentry->security_id = cpu_to_le32(inode->i_security_id);
disk_dentry->subdir_offset = cpu_to_le64(dentry->subdir_offset);
- disk_dentry->unused_1 = cpu_to_le64(dentry->d_unused_1);
- disk_dentry->unused_2 = cpu_to_le64(dentry->d_unused_2);
+ disk_dentry->unused_1 = cpu_to_le64(0);
+ disk_dentry->unused_2 = cpu_to_le64(0);
disk_dentry->creation_time = cpu_to_le64(inode->i_creation_time);
disk_dentry->last_access_time = cpu_to_le64(inode->i_last_access_time);
disk_dentry->last_write_time = cpu_to_le64(inode->i_last_write_time);
}
static int
-write_dentry_cb(struct wim_dentry *dentry, void *_p)
+write_dir_dentries(struct wim_dentry *dir, void *_pp)
{
- u8 **p = _p;
- *p = write_dentry(dentry, *p);
- return 0;
-}
+ if (dir->subdir_offset != 0) {
+ u8 **pp = _pp;
+ u8 *p = *pp;
+ struct wim_dentry *child;
-static u8 *
-write_dentry_tree_recursive(const struct wim_dentry *parent, u8 *p);
+ /* write child dentries */
+ for_dentry_child(child, dir)
+ p = write_dentry(child, p);
-static int
-write_dentry_tree_recursive_cb(struct wim_dentry *dentry, void *_p)
-{
- u8 **p = _p;
- *p = write_dentry_tree_recursive(dentry, *p);
+ /* write end of directory entry */
+ *(u64*)p = 0;
+ p += 8;
+ *pp = p;
+ }
return 0;
}
-/* Recursive function that writes a dentry tree rooted at @parent, not including
- * @parent itself, which has already been written. */
-static u8 *
-write_dentry_tree_recursive(const struct wim_dentry *parent, u8 *p)
-{
- /* Nothing to do if this dentry has no children. */
- if (parent->subdir_offset == 0)
- return p;
-
- /* Write child dentries and end-of-directory entry.
- *
- * Note: we need to write all of this dentry's children before
- * recursively writing the directory trees rooted at each of the child
- * dentries, since the on-disk dentries for a dentry's children are
- * always located at consecutive positions in the metadata resource! */
- for_dentry_child(parent, write_dentry_cb, &p);
-
- /* write end of directory entry */
- *(le64*)p = cpu_to_le64(0);
- p += 8;
-
- /* Recurse on children. */
- for_dentry_child(parent, write_dentry_tree_recursive_cb, &p);
- return p;
-}
-
/* Writes a directory tree to the metadata resource.
*
* @root: Root of the dentry tree.
* Returns pointer to the byte after the last byte we wrote.
*/
u8 *
-write_dentry_tree(const struct wim_dentry * restrict root, u8 * restrict p)
+write_dentry_tree(struct wim_dentry *root, u8 *p)
{
DEBUG("Writing dentry tree.");
wimlib_assert(dentry_is_root(root));
- /* If we're the root dentry, we have no parent that already
- * wrote us, so we need to write ourselves. */
+ /* write root dentry and end-of-directory entry following it */
p = write_dentry(root, p);
-
- /* Write end of directory entry after the root dentry just to be safe;
- * however the root dentry obviously cannot have any siblings. */
- *(le64*)p = cpu_to_le64(0);
+ *(u64*)p = 0;
p += 8;
- /* Recursively write the rest of the dentry tree. */
- return write_dentry_tree_recursive(root, p);
+ /* write the rest of the dentry tree */
+ for_dentry_in_tree(root, write_dir_dentries, &p);
+
+ return p;
}
git://wimlib.net / wimlib / blobdiff