summaryrefslogtreecommitdiff
path: root/lib/sqfs/frag_table.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/sqfs/frag_table.c')
-rw-r--r--lib/sqfs/frag_table.c116
1 files changed, 44 insertions, 72 deletions
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;
}