#include "wimlib/list.h"
#include "wimlib/types.h"
+#include "wimlib/util.h"
struct wim_dentry;
-/* Hash table to find inodes, given an inode number (in the case of reading
- * a WIM images), or both an inode number and a device number (in the case of
- * capturing a WIM image). */
+/* Hash table to find inodes for hard link detection, given an inode number (in
+ * the case of reading a WIM image), or both an inode number and a device number
+ * (in the case of adding files to a WIM image). Also contains an extra list to
+ * hold inodes for which no additional hard link detection is desired. In both
+ * cases the inodes are linked by i_hlist_node. */
struct wim_inode_table {
- /* Fields for the hash table */
struct hlist_head *array;
- size_t num_entries;
+ size_t filled;
size_t capacity;
-
- /*
- * Linked list of "extra" inodes. These may be:
- *
- * - inodes with link count 1, which are all allowed to have 0 for their
- * inode number, meaning we cannot insert them into the hash table.
- *
- * - Groups we create ourselves by splitting a nominal inode due to
- * inconsistencies in the dentries. These inodes will share an inode
- * number with some other inode until assign_inode_numbers() is
- * called.
- */
- struct list_head extra_inodes;
+ struct hlist_head extra_inodes;
};
+/* Compute the index of the hash bucket to use for the given inode number and
+ * device number. */
+static inline size_t
+hash_inode(const struct wim_inode_table *table, u64 ino, u64 devno)
+{
+ return (hash_u64(ino) + devno) & (table->capacity - 1);
+}
+
extern int
init_inode_table(struct wim_inode_table *table, size_t capacity);
u64 ino, u64 devno, bool noshare,
struct wim_dentry **dentry_ret);
+extern void
+enlarge_inode_table(struct wim_inode_table *table);
+
extern void
inode_table_prepare_inode_list(struct wim_inode_table *table,
- struct list_head *head);
+ struct hlist_head *head);
extern void
destroy_inode_table(struct wim_inode_table *table);