inode_table: don't bother clearing array while preparing list

[wimlib] / src / inode_table.c

diff --git a/src/inode_table.c b/src/inode_table.c
index 1eac9466b133e1e4d50fa1ef8324d2a3798839b6..5955580f1cbda2526423cac140a23223944024f1 100644 (file)
--- a/src/inode_table.c
+++ b/src/inode_table.c
@@ -3,7 +3,7 @@
  */
 
 /*
- * 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
@@ -23,6 +23,7 @@
 #  include "config.h"
 #endif
 
+#include "wimlib/bitops.h"
 #include "wimlib/dentry.h"
 #include "wimlib/error.h"
 #include "wimlib/inode.h"
@@ -34,10 +35,11 @@
 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_HLIST_HEAD(&table->extra_inodes);
        return 0;
@@ -50,6 +52,32 @@ destroy_inode_table(struct wim_inode_table *table)
        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.
  *
@@ -91,39 +119,42 @@ inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
 {
        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;
-               hlist_add_head(&dentry->d_inode->i_hlist_node, &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_node) {
-                       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_node, &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;
 }
@@ -151,16 +182,11 @@ inode_table_prepare_inode_list(struct wim_inode_table *table,
        for (size_t i = 0; i < table->capacity; i++) {
                hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist_node) {
                        inode->i_ino = cur_ino++;
-                       inode->i_devno = 0;
                        hlist_add_head(&inode->i_hlist_node, head);
                }
-               INIT_HLIST_HEAD(&table->array[i]);
        }
        hlist_for_each_entry_safe(inode, tmp, &table->extra_inodes, i_hlist_node) {
                inode->i_ino = cur_ino++;
-               inode->i_devno = 0;
                hlist_add_head(&inode->i_hlist_node, head);
        }
-       INIT_HLIST_HEAD(&table->extra_inodes);
-       table->num_entries = 0;
 }