*/
/*
- * Copyright (C) 2012, 2013, 2014 Eric Biggers
+ * Copyright (C) 2012-2016 Eric Biggers
*
* This file is free software; you can redistribute it and/or modify it under
* the terms of the GNU Lesser General Public License as published by the Free
# include "config.h"
#endif
+#include "wimlib/bitops.h"
#include "wimlib/dentry.h"
#include "wimlib/error.h"
#include "wimlib/inode.h"
int
init_inode_table(struct wim_inode_table *table, size_t capacity)
{
+ capacity = roundup_pow_of_2(capacity);
table->array = CALLOC(capacity, sizeof(table->array[0]));
if (!table->array)
return WIMLIB_ERR_NOMEM;
- table->num_entries = 0;
+ table->filled = 0;
table->capacity = capacity;
- INIT_LIST_HEAD(&table->extra_inodes);
+ INIT_HLIST_HEAD(&table->extra_inodes);
return 0;
}
FREE(table->array);
}
+/* Double the capacity of the inode hash table. */
+void
+enlarge_inode_table(struct wim_inode_table *table)
+{
+ const size_t old_capacity = table->capacity;
+ const size_t new_capacity = old_capacity * 2;
+ struct hlist_head *old_array = table->array;
+ struct hlist_head *new_array;
+ struct wim_inode *inode;
+ struct hlist_node *tmp;
+
+ new_array = CALLOC(new_capacity, sizeof(struct hlist_head));
+ if (!new_array)
+ return;
+ table->array = new_array;
+ table->capacity = new_capacity;
+ for (size_t i = 0; i < old_capacity; i++) {
+ hlist_for_each_entry_safe(inode, tmp, &old_array[i], i_hlist_node) {
+ hlist_add_head(&inode->i_hlist_node,
+ &new_array[hash_inode(table, inode->i_ino,
+ inode->i_devno)]);
+ }
+ }
+ FREE(old_array);
+}
+
/*
* Allocate a new dentry, with hard link detection.
*
{
struct wim_dentry *dentry;
struct wim_inode *inode;
+ struct hlist_head *list;
int ret;
if (noshare) {
- /* File that cannot be hardlinked--- Return a new inode with its
- * inode and device numbers left at 0. */
- ret = new_dentry_with_new_inode(name, false, &dentry);
- if (ret)
- return ret;
- list_add_tail(&dentry->d_inode->i_list, &table->extra_inodes);
+ /* No hard link detection */
+ list = &table->extra_inodes;
} else {
- size_t pos;
-
- /* File that can be hardlinked--- search the table for an
- * existing inode matching the inode number and device. */
- pos = hash_u64(hash_u64(ino) + hash_u64(devno)) % table->capacity;
- hlist_for_each_entry(inode, &table->array[pos], i_hlist) {
- if (inode->i_ino == ino && inode->i_devno == devno) {
- /* Found; use the existing inode. */
- return new_dentry_with_existing_inode(name, inode,
- dentry_ret);
+ /* Hard link detection */
+ list = &table->array[hash_inode(table, ino, devno)];
+ hlist_for_each_entry(inode, list, i_hlist_node) {
+ if (inode->i_ino != ino || inode->i_devno != devno)
+ continue;
+ if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) {
+ WARNING("Not honoring directory hard link "
+ "of \"%"TS"\"",
+ inode_any_full_path(inode));
+ continue;
}
+ /* Inode found; use it. */
+ return new_dentry_with_existing_inode(name, inode,
+ dentry_ret);
}
- /* Not found; create a new inode and add it to the table. */
- ret = new_dentry_with_new_inode(name, false, &dentry);
- if (ret)
- return ret;
- inode = dentry->d_inode;
- inode->i_ino = ino;
- inode->i_devno = devno;
- hlist_add_head(&inode->i_hlist, &table->array[pos]);
- table->num_entries++;
+ /* Inode not found; create it. */
}
+
+ ret = new_dentry_with_new_inode(name, false, &dentry);
+ if (ret)
+ return ret;
+ inode = dentry->d_inode;
+ inode->i_ino = ino;
+ inode->i_devno = devno;
+ hlist_add_head(&inode->i_hlist_node, list);
+ if (list != &table->extra_inodes)
+ if (++table->filled > table->capacity)
+ enlarge_inode_table(table);
*dentry_ret = dentry;
return 0;
}
*/
void
inode_table_prepare_inode_list(struct wim_inode_table *table,
- struct list_head *head)
+ struct hlist_head *head)
{
- struct wim_inode *inode, *tmp_inode;
+ struct wim_inode *inode;
struct hlist_node *tmp;
u64 cur_ino = 1;
/* Re-assign inode numbers in the existing list to avoid duplicates. */
- list_for_each_entry(inode, head, i_list)
+ hlist_for_each_entry(inode, head, i_hlist_node)
inode->i_ino = cur_ino++;
/* Assign inode numbers to the new inodes and move them to the image's
* inode list. */
for (size_t i = 0; i < table->capacity; i++) {
- hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist) {
+ hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist_node) {
inode->i_ino = cur_ino++;
- inode->i_devno = 0;
- list_add_tail(&inode->i_list, head);
+ hlist_add_head(&inode->i_hlist_node, head);
}
- INIT_HLIST_HEAD(&table->array[i]);
}
- list_for_each_entry_safe(inode, tmp_inode, &table->extra_inodes, i_list)
- {
+ hlist_for_each_entry_safe(inode, tmp, &table->extra_inodes, i_hlist_node) {
inode->i_ino = cur_ino++;
- inode->i_devno = 0;
- list_add_tail(&inode->i_list, head);
+ hlist_add_head(&inode->i_hlist_node, head);
}
- INIT_LIST_HEAD(&table->extra_inodes);
- table->num_entries = 0;
}