X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Finode_table.c;h=5955580f1cbda2526423cac140a23223944024f1;hb=7453f4a4245219a9c01a70902283f6ebb2a65123;hp=6e1c143b3c33336d4767627b98aff8893b717fba;hpb=7251c7d0afac3b738dda1c4f45e6d3d3090f2622;p=wimlib diff --git a/src/inode_table.c b/src/inode_table.c index 6e1c143b..5955580f 100644 --- 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,12 +35,13 @@ 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; } @@ -50,33 +52,30 @@ destroy_inode_table(struct wim_inode_table *table) FREE(table->array); } -static struct wim_inode * -inode_table_get_inode(struct wim_inode_table *table, u64 ino, u64 devno) +/* Double the capacity of the inode hash table. */ +void +enlarge_inode_table(struct wim_inode_table *table) { - size_t pos; + 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 *cur; + struct hlist_node *tmp; - /* Search for an existing inode having the same inode number and device - * number. */ - pos = hash_u64(hash_u64(ino) + hash_u64(devno)) % table->capacity; - hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) { - if (inode->i_ino == ino && inode->i_devno == devno) { - /* Found; use the existing inode. */ - inode->i_nlink++; - return inode; + 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)]); } } - - /* Create a new inode and insert it into the table. */ - inode = new_timeless_inode(); - if (inode) { - inode->i_ino = ino; - inode->i_devno = devno; - hlist_add_head(&inode->i_hlist, &table->array[pos]); - table->num_entries++; - } - return inode; + FREE(old_array); } /* @@ -120,34 +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_timeless_inode(name, &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 { - /* File that can be hardlinked--- search the table for an - * existing inode matching the inode number and device; - * otherwise create a new inode. */ - ret = new_dentry(name, &dentry); - if (ret) - return ret; - inode = inode_table_get_inode(table, ino, devno); - if (!inode) { - free_dentry(dentry); - return WIMLIB_ERR_NOMEM; + /* 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); } - /* If using an existing inode, we need to gain a reference to - * each of its streams. */ - if (inode->i_nlink > 1) - inode_ref_streams(inode); - dentry->d_inode = inode; - inode_add_dentry(dentry, inode); + + /* 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; } @@ -160,33 +167,26 @@ inode_table_new_dentry(struct wim_inode_table *table, const tchar *name, */ 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 hlist_node *cur, *tmp; + 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, cur, 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; }