diff options
Diffstat (limited to 'lib/sqfs')
| -rw-r--r-- | lib/sqfs/Makemodule.am | 1 | ||||
| -rw-r--r-- | lib/sqfs/frag_table.c | 116 |
2 files changed, 45 insertions, 72 deletions
diff --git a/lib/sqfs/Makemodule.am b/lib/sqfs/Makemodule.am index 942c37c..32b4c25 100644 --- a/lib/sqfs/Makemodule.am +++ b/lib/sqfs/Makemodule.am @@ -36,6 +36,7 @@ libsquashfs_la_LIBADD += $(ZSTD_LIBS) $(PTHREAD_LIBS) # directly "import" stuff from libutil libsquashfs_la_SOURCES += lib/util/str_table.c lib/util/alloc.c libsquashfs_la_SOURCES += lib/util/xxhash.c +libsquashfs_la_SOURCES += lib/util/hash_table.c lib/util/hash_table.h if WINDOWS libsquashfs_la_SOURCES += lib/sqfs/win32/io_file.c diff --git a/lib/sqfs/frag_table.c b/lib/sqfs/frag_table.c index 51164e6..59811bb 100644 --- a/lib/sqfs/frag_table.c +++ b/lib/sqfs/frag_table.c @@ -14,13 +14,12 @@ #include "sqfs/block.h" #include "compat.h" +#include "lib/util/hash_table.h" + #include <stdlib.h> #include <string.h> -#define NUM_BUCKETS (128) - - typedef struct chunk_info_t { struct chunk_info_t *next; sqfs_u32 index; @@ -37,23 +36,32 @@ struct sqfs_frag_table_t { size_t used; sqfs_fragment_t *table; - chunk_info_t chunks[NUM_BUCKETS]; + struct hash_table *ht; }; +static uint32_t chunk_info_hash(const void *key) +{ + const chunk_info_t *chunk = key; + return chunk->hash; +} + +static bool chunk_info_equals(const void *a, const void *b) +{ + const chunk_info_t *a_ = a, *b_ = b; + return a_->size == b_->size && + a_->hash == b_->hash; +} + +static void delete_function(struct hash_entry *entry) +{ + free(entry->data); +} + static void frag_table_destroy(sqfs_object_t *obj) { sqfs_frag_table_t *tbl = (sqfs_frag_table_t *)obj; - chunk_info_t *info; - size_t i; - - for (i = 0; i < NUM_BUCKETS; ++i) { - while (tbl->chunks[i].next != NULL) { - info = tbl->chunks[i].next; - tbl->chunks[i].next = info->next; - free(info); - } - } + hash_table_destroy(tbl->ht, delete_function); free(tbl->table); free(tbl); } @@ -62,38 +70,15 @@ static sqfs_object_t *frag_table_copy(const sqfs_object_t *obj) { const sqfs_frag_table_t *tbl = (const sqfs_frag_table_t *)obj; sqfs_frag_table_t *copy; - const chunk_info_t *it; - chunk_info_t *last; - size_t i; copy = malloc(sizeof(*copy)); if (copy == NULL) return NULL; memcpy(copy, tbl, sizeof(*tbl)); - for (i = 0; i < NUM_BUCKETS; ++i) - copy->chunks[i].next = NULL; - - for (i = 0; i < NUM_BUCKETS; ++i) { - last = &(copy->chunks[i]); - it = tbl->chunks[i].next; - - while (it != NULL) { - last->next = malloc(sizeof(*it)); - if (last->next == NULL) - goto fail; - - memcpy(last->next, it, sizeof(*it)); - last = last->next; - last->next = NULL; - it = it->next; - } - } + copy->ht = hash_table_clone(tbl->ht); return (sqfs_object_t *)copy; -fail: - frag_table_destroy((sqfs_object_t *)copy); - return NULL; } sqfs_frag_table_t *sqfs_frag_table_create(sqfs_u32 flags) @@ -107,6 +92,8 @@ sqfs_frag_table_t *sqfs_frag_table_create(sqfs_u32 flags) if (tbl == NULL) return NULL; + tbl->ht = hash_table_create(chunk_info_hash, chunk_info_equals); + ((sqfs_object_t *)tbl)->copy = frag_table_copy; ((sqfs_object_t *)tbl)->destroy = frag_table_destroy; return tbl; @@ -267,30 +254,16 @@ int sqfs_frag_table_add_tail_end(sqfs_frag_table_t *tbl, sqfs_u32 index, sqfs_u32 offset, sqfs_u32 size, sqfs_u32 hash) { - size_t idx = hash % NUM_BUCKETS; - chunk_info_t *new, *it; - - if (tbl->chunks[idx].size == 0 && tbl->chunks[idx].hash == 0) { - tbl->chunks[idx].index = index; - tbl->chunks[idx].offset = offset; - tbl->chunks[idx].size = size; - tbl->chunks[idx].hash = hash; - } else { - new = calloc(1, sizeof(*new)); - if (new == NULL) - return SQFS_ERROR_ALLOC; + chunk_info_t *new = calloc(1, sizeof(*new)); + if (new == NULL) + return SQFS_ERROR_ALLOC; - new->index = index; - new->offset = offset; - new->size = size; - new->hash = hash; + new->index = index; + new->offset = offset; + new->size = size; + new->hash = hash; - it = &tbl->chunks[idx]; - while (it->next != NULL) - it = it->next; - - it->next = new; - } + hash_table_insert_pre_hashed(tbl->ht, new->hash, new, new); return 0; } @@ -299,19 +272,18 @@ int sqfs_frag_table_find_tail_end(sqfs_frag_table_t *tbl, sqfs_u32 hash, sqfs_u32 size, sqfs_u32 *index, sqfs_u32 *offset) { - size_t idx = hash % NUM_BUCKETS; - chunk_info_t *it; + struct hash_entry *entry; + chunk_info_t *chunk, search; - if (tbl->chunks[idx].size == 0 && tbl->chunks[idx].hash == 0) - return SQFS_ERROR_NO_ENTRY; + search.hash = hash; + search.size = size; - for (it = &tbl->chunks[idx]; it != NULL; it = it->next) { - if (it->hash == hash && it->size == size) { - *index = it->index; - *offset = it->offset; - return 0; - } - } + entry = hash_table_search_pre_hashed(tbl->ht, hash, &search); + if (!entry) + return SQFS_ERROR_NO_ENTRY; - return SQFS_ERROR_NO_ENTRY; + chunk = entry->data; + *index = chunk->index; + *offset = chunk->offset; + return 0; } |