write.c: cleanups and bug fixes

[wimlib] / src / blob_table.c

diff --git a/src/blob_table.c b/src/blob_table.c
index e9766b5f6419db7d1f35c4b79815a4169954a6ed..40c4af4bd023281157a4a653609c99ead554f961 100644 (file)
--- a/src/blob_table.c
+++ b/src/blob_table.c
@@ -34,6 +34,7 @@
 #include <unistd.h> /* for unlink()  */
 
 #include "wimlib/assert.h"
+#include "wimlib/bitops.h"
 #include "wimlib/blob_table.h"
 #include "wimlib/encoding.h"
 #include "wimlib/endianness.h"
@@ -49,15 +50,25 @@
 struct blob_table {
        struct hlist_head *array;
        size_t num_blobs;
-       size_t capacity;
+       size_t mask; /* capacity - 1; capacity is a power of 2  */
 };
 
+static size_t
+next_power_of_2(size_t n)
+{
+       if (n <= 1)
+               return 1;
+       return (size_t)1 << (1 + flsw(n - 1));
+}
+
 struct blob_table *
 new_blob_table(size_t capacity)
 {
        struct blob_table *table;
        struct hlist_head *array;
 
+       capacity = next_power_of_2(capacity);
+
        table = MALLOC(sizeof(struct blob_table));
        if (table == NULL)
                goto oom;
@@ -69,7 +80,7 @@ new_blob_table(size_t capacity)
        }
 
        table->num_blobs = 0;
-       table->capacity = capacity;
+       table->mask = capacity - 1;
        table->array = array;
        return table;
 
@@ -99,7 +110,7 @@ free_blob_table(struct blob_table *table)
 struct blob_descriptor *
 new_blob_descriptor(void)
 {
-       BUILD_BUG_ON(BLOB_NONEXISTENT != 0);
+       STATIC_ASSERT(BLOB_NONEXISTENT == 0);
        return CALLOC(1, sizeof(struct blob_descriptor));
 }
 
@@ -124,8 +135,8 @@ clone_blob_descriptor(const struct blob_descriptor *old)
 #endif
 #ifdef WITH_FUSE
        case BLOB_IN_STAGING_FILE:
-               BUILD_BUG_ON((void*)&old->file_on_disk !=
-                            (void*)&old->staging_file_name);
+               STATIC_ASSERT((void*)&old->file_on_disk ==
+                             (void*)&old->staging_file_name);
 #endif
                new->file_on_disk = TSTRDUP(old->file_on_disk);
                if (new->file_on_disk == NULL)
@@ -167,12 +178,12 @@ blob_release_location(struct blob_descriptor *blob)
 #endif
 #ifdef WITH_FUSE
        case BLOB_IN_STAGING_FILE:
-               BUILD_BUG_ON((void*)&blob->file_on_disk !=
-                            (void*)&blob->staging_file_name);
+               STATIC_ASSERT((void*)&blob->file_on_disk ==
+                             (void*)&blob->staging_file_name);
 #endif
        case BLOB_IN_ATTACHED_BUFFER:
-               BUILD_BUG_ON((void*)&blob->file_on_disk !=
-                            (void*)&blob->attached_buffer);
+               STATIC_ASSERT((void*)&blob->file_on_disk ==
+                             (void*)&blob->attached_buffer);
                FREE(blob->file_on_disk);
                break;
 #ifdef WITH_NTFS_3G
@@ -287,7 +298,7 @@ blob_decrement_num_opened_fds(struct blob_descriptor *blob)
 static void
 blob_table_insert_raw(struct blob_table *table, struct blob_descriptor *blob)
 {
-       size_t i = blob->hash_short % table->capacity;
+       size_t i = blob->hash_short & table->mask;
 
        hlist_add_head(&blob->hash_list, &table->array[i]);
 }
@@ -301,14 +312,14 @@ enlarge_blob_table(struct blob_table *table)
        struct hlist_node *tmp;
        size_t i;
 
-       old_capacity = table->capacity;
+       old_capacity = table->mask + 1;
        new_capacity = old_capacity * 2;
        new_array = CALLOC(new_capacity, sizeof(struct hlist_head));
        if (new_array == NULL)
                return;
        old_array = table->array;
        table->array = new_array;
-       table->capacity = new_capacity;
+       table->mask = new_capacity - 1;
 
        for (i = 0; i < old_capacity; i++)
                hlist_for_each_entry_safe(blob, tmp, &old_array[i], hash_list)
@@ -321,7 +332,7 @@ void
 blob_table_insert(struct blob_table *table, struct blob_descriptor *blob)
 {
        blob_table_insert_raw(table, blob);
-       if (++table->num_blobs > table->capacity)
+       if (table->num_blobs++ > table->mask)
                enlarge_blob_table(table);
 }
 
@@ -344,7 +355,7 @@ lookup_blob(const struct blob_table *table, const u8 *hash)
        size_t i;
        struct blob_descriptor *blob;
 
-       i = load_size_t_unaligned(hash) % table->capacity;
+       i = load_size_t_unaligned(hash) & table->mask;
        hlist_for_each_entry(blob, &table->array[i], hash_list)
                if (hashes_equal(hash, blob->hash))
                        return blob;
@@ -361,7 +372,7 @@ for_blob_in_table(struct blob_table *table,
        struct hlist_node *tmp;
        int ret;
 
-       for (size_t i = 0; i < table->capacity; i++) {
+       for (size_t i = 0; i <= table->mask; i++) {
                hlist_for_each_entry_safe(blob, tmp, &table->array[i],
                                          hash_list)
                {
@@ -401,22 +412,33 @@ cmp_blobs_by_sequential_order(const void *p1, const void *p2)
                wim1 = blob1->rdesc->wim;
                wim2 = blob2->rdesc->wim;
 
-               /* Different (possibly split) WIMs?  */
+               /* Different WIM files?  */
                if (wim1 != wim2) {
+
+                       /* Different split WIMs?  */
                        v = cmp_guids(wim1->hdr.guid, wim2->hdr.guid);
                        if (v)
                                return v;
+
+                       /* Different part numbers in the same split WIM?  */
+                       v = (int)wim1->hdr.part_number - (int)wim2->hdr.part_number;
+                       if (v)
+                               return v;
+
+                       /* Probably two WIMStructs for the same on-disk file.
+                        * Just sort by pointer.  */
+                       return wim1 < wim2 ? -1 : 1;
                }
 
-               /* Different part numbers in the same WIM?  */
-               v = (int)wim1->hdr.part_number - (int)wim2->hdr.part_number;
-               if (v)
-                       return v;
+               /* Same WIM file  */
 
+               /* Sort by increasing resource offset  */
                if (blob1->rdesc->offset_in_wim != blob2->rdesc->offset_in_wim)
                        return cmp_u64(blob1->rdesc->offset_in_wim,
                                       blob2->rdesc->offset_in_wim);
 
+               /* The blobs are in the same solid resource.  Sort by increasing
+                * offset in the resource.  */
                return cmp_u64(blob1->offset_in_res, blob2->offset_in_res);
 
        case BLOB_IN_FILE_ON_DISK:
@@ -627,10 +649,10 @@ do_load_solid_info(WIMStruct *wim, struct wim_resource_descriptor **rdescs,
 
                /* Compression format numbers must be the same as in
                 * WIMGAPI to be compatible here.  */
-               BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_NONE != 0);
-               BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_XPRESS != 1);
-               BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_LZX != 2);
-               BUILD_BUG_ON(WIMLIB_COMPRESSION_TYPE_LZMS != 3);
+               STATIC_ASSERT(WIMLIB_COMPRESSION_TYPE_NONE == 0);
+               STATIC_ASSERT(WIMLIB_COMPRESSION_TYPE_XPRESS == 1);
+               STATIC_ASSERT(WIMLIB_COMPRESSION_TYPE_LZX == 2);
+               STATIC_ASSERT(WIMLIB_COMPRESSION_TYPE_LZMS == 3);
                rdesc->compression_type = le32_to_cpu(hdr.compression_format);
                rdesc->chunk_size = le32_to_cpu(hdr.chunk_size);
        }
@@ -860,7 +882,7 @@ read_blob_table(WIMStruct *wim)
 
        /* Allocate a hash table to map SHA-1 message digests into blob
         * descriptors.  This is the in-memory "blob table".  */
-       table = new_blob_table(num_entries * 2 + 1);
+       table = new_blob_table(num_entries);
        if (!table)
                goto oom;