+
+/*
+ * dentry_tree_fix_inodes():
+ *
+ * This function takes as input a tree of WIM dentries that initially has a
+ * different inode associated with each dentry. Sets of dentries that should
+ * share the same inode (a.k.a. hard link groups) are built using the i_ino
+ * field of each inode, then the link count and alias list for one inode in each
+ * set is set correctly and the unnecessary struct wim_inode's freed. The
+ * effect is to correctly associate exactly one struct wim_inode with each
+ * original inode, regardless of how many dentries are aliases for that inode.
+ *
+ * The special inode number of 0 indicates that the dentry is in a hard link
+ * group by itself, and therefore has a 'struct wim_inode' with i_nlink=1 to
+ * itself.
+ *
+ * This function also checks the dentries in each hard link group for
+ * consistency. In some WIMs, such as install.wim for some versions of Windows
+ * 7, dentries can share the same hard link group ID but not actually be hard
+ * linked to each other (based on conflicting information, such as file
+ * contents). This should be an error, but this case needs be handled. So,
+ * each "nominal" inode (the inode based on the inode numbers provided in the
+ * WIM) is examined for consistency and may be split into multiple "true" inodes
+ * that are maximally sized consistent sets of dentries.
+ *
+ * Return 0 on success; WIMLIB_ERR_NOMEM or WIMLIB_ERR_INVALID_DENTRY on
+ * failure. On success, the list of "true" inodes, linked by the i_hlist field,
+ * is returned in the hlist @inode_list.
+ */
+int
+dentry_tree_fix_inodes(struct wim_dentry *root, struct list_head *inode_list)
+{
+ struct wim_inode_table inode_tab;
+ int ret;
+ bool ino_changes_needed;
+
+ DEBUG("Inserting dentries into inode table");
+ ret = init_inode_table(&inode_tab, 9001);
+ if (ret)
+ return ret;
+
+ for_dentry_in_tree(root, inode_table_insert, &inode_tab);
+
+ DEBUG("Cleaning up the hard link groups");
+ ino_changes_needed = false;
+ ret = fix_inodes(&inode_tab, inode_list, &ino_changes_needed);
+ destroy_inode_table(&inode_tab);
+
+ if (ret == 0 && ino_changes_needed) {
+ u64 cur_ino = 1;
+ struct wim_inode *inode;
+
+ WARNING("Re-assigning inode numbers due to inode inconsistencies");
+ list_for_each_entry(inode, inode_list, i_list) {
+ if (inode->i_nlink > 1)
+ inode->i_ino = cur_ino++;
+ else
+ inode->i_ino = 0;
+ }
+ }
+ return ret;
+}
+
+/* Assign consecutive inode numbers to the inodes in the inode table, and move
+ * the inodes to a single list @head. */
+void
+inode_table_prepare_inode_list(struct wim_inode_table *table,
+ struct list_head *head)
+{
+ struct wim_inode *inode;
+ struct hlist_node *cur, *tmp;
+ u64 cur_ino = 1;
+
+ INIT_LIST_HEAD(head);
+ for (size_t i = 0; i < table->capacity; i++) {
+ hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], i_hlist)
+ {
+ if (inode->i_nlink > 1)
+ inode->i_ino = cur_ino++;
+ else
+ inode->i_ino = 0;
+ list_add_tail(&inode->i_list, head);
+ }
+ INIT_HLIST_HEAD(&table->array[i]);
+ }
+ list_splice_tail(&table->extra_inodes, head);
+ table->num_entries = 0;
+}