+/*
+ * hardlink.c
+ *
+ * Code to deal with hard links in WIMs.
+ */
+
+/*
+ * Copyright (C) 2012, 2013 Eric Biggers
+ *
+ * This file is part of wimlib, a library for working with WIM files.
+ *
+ * wimlib is free software; you can redistribute it and/or modify it under the
+ * terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 3 of the License, or (at your option)
+ * any later version.
+ *
+ * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ * A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with wimlib; if not, see http://www.gnu.org/licenses/.
+ */
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "wimlib/capture.h"
+#include "wimlib/dentry.h"
+#include "wimlib/error.h"
+#include "wimlib/lookup_table.h"
+
+/* NULL NULL
+ * ^ ^
+ * dentry | |
+ * / \ ----------- -----------
+ * | dentry<---| struct | | struct |---> dentry
+ * \ / | wim_inode| | wim_inode|
+ * dentry ------------ ------------
+ * ^ ^
+ * | |
+ * | | dentry
+ * ----------- ----------- / \
+ * dentry<---| struct | | struct |---> dentry dentry
+ * / | wim_inode| | wim_inode| \ /
+ * dentry ------------ ------------ dentry
+ * ^ ^
+ * | |
+ * -----------------
+ * wim_inode_table->array | idx 0 | idx 1 |
+ * -----------------
+ */
+
+
+int
+init_inode_table(struct wim_inode_table *table, size_t capacity)
+{
+ table->array = CALLOC(capacity, sizeof(table->array[0]));
+ if (!table->array) {
+ ERROR("Cannot initalize inode table: out of memory");
+ return WIMLIB_ERR_NOMEM;
+ }
+ table->num_entries = 0;
+ table->capacity = capacity;
+ INIT_LIST_HEAD(&table->extra_inodes);
+ return 0;
+}
+
+static inline size_t
+inode_link_count(const struct wim_inode *inode)
+{
+ const struct list_head *cur;
+ size_t size = 0;
+ list_for_each(cur, &inode->i_dentry)
+ size++;
+ return size;
+}
+
+/* Insert a dentry into the inode table based on the inode number of the
+ * attached inode (which came from the hard link group ID field of the on-disk
+ * WIM dentry) */
+static int
+inode_table_insert(struct wim_dentry *dentry, void *_table)
+{
+ struct wim_inode_table *table = _table;
+ struct wim_inode *d_inode = dentry->d_inode;
+
+ if (d_inode->i_ino == 0) {
+ /* A dentry with a hard link group ID of 0 indicates that it's
+ * in a hard link group by itself. Add it to the list of extra
+ * inodes rather than inserting it into the hash lists. */
+ list_add_tail(&d_inode->i_list, &table->extra_inodes);
+
+ wimlib_assert(d_inode->i_dentry.next == &dentry->d_alias);
+ wimlib_assert(d_inode->i_dentry.prev == &dentry->d_alias);
+ wimlib_assert(d_inode->i_nlink == 1);
+ } else {
+ size_t pos;
+ struct wim_inode *inode;
+ struct hlist_node *cur;
+
+ /* Try adding this dentry to an existing inode */
+ pos = d_inode->i_ino % table->capacity;
+ hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) {
+ if (inode->i_ino == d_inode->i_ino) {
+ if (unlikely((inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) ||
+ (d_inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))
+ {
+ ERROR("Unsupported directory hard link "
+ "\"%"TS"\" <=> \"%"TS"\"",
+ dentry_full_path(dentry),
+ dentry_full_path(inode_first_dentry(inode)));
+ return WIMLIB_ERR_INVALID_DENTRY;
+ }
+ inode_add_dentry(dentry, inode);
+ inode->i_nlink++;
+ return 0;
+ }
+ }
+
+ /* No inode in the table has the same number as this one, so add
+ * it to the table. */
+ hlist_add_head(&d_inode->i_hlist, &table->array[pos]);
+
+ wimlib_assert(d_inode->i_dentry.next == &dentry->d_alias);
+ wimlib_assert(d_inode->i_dentry.prev == &dentry->d_alias);
+ wimlib_assert(d_inode->i_nlink == 1);
+
+ /* XXX Make the table grow when too many entries have been
+ * inserted. */
+ table->num_entries++;
+ }
+ return 0;
+}
+
+static struct wim_inode *
+inode_table_get_inode(struct wim_inode_table *table, u64 ino, u64 devno)