From 15b547c55b2045e68f9f48f7d929d47b300dc3a9 Mon Sep 17 00:00:00 2001 From: Timo Teras Date: Wed, 14 Jan 2009 10:44:47 +0200 Subject: db: keep only filename in file entries, hash by both directory and file --- TODO | 3 --- src/apk_hash.h | 5 +++- src/blob.c | 2 +- src/database.c | 73 +++++++++++++++++++++++++++++++++++++++++++--------------- src/hash.c | 26 ++++++++++++++------- 5 files changed, 77 insertions(+), 32 deletions(-) diff --git a/TODO b/TODO index 51861a2..3c93ddd 100644 --- a/TODO +++ b/TODO @@ -1,9 +1,6 @@ - confirm whether to act (show changeset-size, installed, removed) if other packages affected then the ones explicitly specified -- complete lbu replacement -- links for lbu* and apk_* - - Index/pkginfo reader: same field multiple times -> memleak - Compress 'installed' and 'scripts' diff --git a/src/apk_hash.h b/src/apk_hash.h index f1a010c..b9c975e 100644 --- a/src/apk_hash.h +++ b/src/apk_hash.h @@ -20,6 +20,7 @@ typedef void *apk_hash_item; typedef unsigned long (*apk_hash_f)(apk_blob_t); typedef int (*apk_hash_compare_f)(apk_blob_t, apk_blob_t); +typedef int (*apk_hash_compare_item_f)(apk_hash_item, apk_blob_t); typedef void (*apk_hash_delete_f)(apk_hash_item); typedef int (*apk_hash_enumerator_f)(apk_hash_item, void *ctx); @@ -27,7 +28,9 @@ struct apk_hash_ops { ptrdiff_t node_offset; apk_blob_t (*get_key)(apk_hash_item item); unsigned long (*hash_key)(apk_blob_t key); - int (*compare)(apk_blob_t key, apk_blob_t itemkey); + unsigned long (*hash_item)(apk_hash_item item); + int (*compare)(apk_blob_t itemkey, apk_blob_t key); + int (*compare_item)(apk_hash_item item, apk_blob_t key); void (*delete_item)(apk_hash_item item); }; diff --git a/src/blob.c b/src/blob.c index 4fea730..ab514f8 100644 --- a/src/blob.c +++ b/src/blob.c @@ -42,7 +42,7 @@ int apk_blob_rsplit(apk_blob_t blob, char split, apk_blob_t *l, apk_blob_t *r) if (l != NULL) *l = APK_BLOB_PTR_PTR(blob.ptr, sep - 1); if (r != NULL) - *r = APK_BLOB_PTR_PTR(sep + 1, blob.ptr + blob.len); + *r = APK_BLOB_PTR_PTR(sep + 1, blob.ptr + blob.len - 1); return 1; } diff --git a/src/database.c b/src/database.c index d0207f2..a84154f 100644 --- a/src/database.c +++ b/src/database.c @@ -86,16 +86,45 @@ static const struct apk_hash_ops dir_hash_ops = { .delete_item = (apk_hash_delete_f) free, }; -static apk_blob_t apk_db_file_get_key(apk_hash_item item) +struct apk_db_file_hash_key { + apk_blob_t dirname; + apk_blob_t filename; +}; + +static unsigned long apk_db_file_hash_key(apk_blob_t _key) { - return APK_BLOB_STR(((struct apk_db_file *) item)->filename); + struct apk_db_file_hash_key *key = (struct apk_db_file_hash_key *) _key.ptr; + + return apk_blob_hash(key->dirname) ^ + apk_blob_hash(key->filename); +} + +static unsigned long apk_db_file_hash_item(apk_hash_item item) +{ + struct apk_db_file *dbf = (struct apk_db_file *) item; + + return apk_blob_hash(APK_BLOB_STR(dbf->diri->dir->dirname)) ^ + apk_blob_hash(APK_BLOB_STR(dbf->filename)); +} + +static int apk_db_file_compare_item(apk_hash_item item, apk_blob_t _key) +{ + struct apk_db_file *dbf = (struct apk_db_file *) item; + struct apk_db_file_hash_key *key = (struct apk_db_file_hash_key *) _key.ptr; + int r; + + r = apk_blob_compare(key->dirname, APK_BLOB_STR(dbf->diri->dir->dirname)); + if (r != 0) + return r; + + return apk_blob_compare(key->filename, APK_BLOB_STR(dbf->filename)); } static const struct apk_hash_ops file_hash_ops = { .node_offset = offsetof(struct apk_db_file, hash_node), - .get_key = apk_db_file_get_key, - .hash_key = apk_blob_hash, - .compare = apk_blob_compare, + .hash_key = apk_db_file_hash_key, + .hash_item = apk_db_file_hash_item, + .compare_item = apk_db_file_compare_item, .delete_item = (apk_hash_delete_f) free, }; @@ -242,25 +271,29 @@ static void apk_db_diri_free(struct apk_database *db, free(diri); } -static struct apk_db_file *apk_db_file_query(struct apk_database *db, - apk_blob_t name) -{ - return (struct apk_db_file *) apk_hash_get(&db->installed.files, name); -} - static struct apk_db_file *apk_db_file_get(struct apk_database *db, + struct apk_db_dir_instance *diri, apk_blob_t name) { struct apk_db_file *file; + struct apk_db_file_hash_key key; + + key = (struct apk_db_file_hash_key) { + .dirname = APK_BLOB_STR(diri->dir->dirname), + .filename = name, + }; - file = apk_db_file_query(db, name); + file = (struct apk_db_file *) apk_hash_get(&db->installed.files, + APK_BLOB_BUF(&key)); if (file != NULL) return file; file = calloc(1, sizeof(*file) + name.len + 1); memcpy(file->filename, name.ptr, name.len); file->filename[name.len] = 0; + file->diri = diri; apk_hash_insert(&db->installed.files, file); + file->diri = NULL; return file; } @@ -305,9 +338,8 @@ static int apk_db_index_read(struct apk_database *db, struct apk_istream *is, in struct hlist_node **file_diri_node = NULL; char buf[1024]; - char tmp[512]; apk_blob_t l, r; - int n, field, i; + int n, field; r = APK_BLOB_PTR_LEN(buf, 0); while (1) { @@ -384,9 +416,7 @@ static int apk_db_index_read(struct apk_database *db, struct apk_istream *is, in apk_error("FDB file entry before directory entry"); return -1; } - i = snprintf(tmp, sizeof(tmp), "%s/%.*s", - diri->dir->dirname, l.len, l.ptr); - file = apk_db_file_get(db, APK_BLOB_PTR_LEN(tmp, i)); + file = apk_db_file_get(db, diri, l); apk_db_file_set_owner(db, file, diri, file_diri_node); file_diri_node = &file->diri_files_list.next; break; @@ -701,11 +731,16 @@ struct apk_package *apk_db_get_file_owner(struct apk_database *db, apk_blob_t filename) { struct apk_db_file *dbf; + struct apk_db_file_hash_key key; if (filename.len && filename.ptr[0] == '/') filename.len--, filename.ptr++; - dbf = apk_db_file_query(db, filename); + if (!apk_blob_rsplit(filename, '/', &key.dirname, &key.filename)) + return NULL; + + dbf = (struct apk_db_file *) apk_hash_get(&db->installed.files, + APK_BLOB_BUF(&key)); if (dbf == NULL) return NULL; @@ -913,7 +948,7 @@ static int apk_db_install_archive_entry(void *_ctx, ctx->diri = diri; } - file = apk_db_file_get(db, name); + file = apk_db_file_get(db, diri, bfile); if (file == NULL) { apk_error("%s: Failed to create fdb entry for '%*s'\n", pkg->name->name, name.len, name.ptr); diff --git a/src/hash.c b/src/hash.c index 9260b9b..a81bb76 100644 --- a/src/hash.c +++ b/src/hash.c @@ -52,11 +52,19 @@ apk_hash_item apk_hash_get(struct apk_hash *h, apk_blob_t key) apk_blob_t itemkey; hash = h->ops->hash_key(key) % h->buckets->num; - hlist_for_each(pos, &h->buckets->item[hash]) { - item = ((void *) pos) - offset; - itemkey = h->ops->get_key(item); - if (h->ops->compare(key, itemkey) == 0) - return item; + if (h->ops->compare_item != NULL) { + hlist_for_each(pos, &h->buckets->item[hash]) { + item = ((void *) pos) - offset; + if (h->ops->compare_item(item, key) == 0) + return item; + } + } else { + hlist_for_each(pos, &h->buckets->item[hash]) { + item = ((void *) pos) - offset; + itemkey = h->ops->get_key(item); + if (h->ops->compare(key, itemkey) == 0) + return item; + } } return NULL; @@ -64,12 +72,14 @@ apk_hash_item apk_hash_get(struct apk_hash *h, apk_blob_t key) void apk_hash_insert(struct apk_hash *h, apk_hash_item item) { - apk_blob_t key; unsigned long hash; apk_hash_node *node; - key = h->ops->get_key(item); - hash = h->ops->hash_key(key) % h->buckets->num; + if (h->ops->hash_item == NULL) + hash = h->ops->hash_key(h->ops->get_key(item)); + else + hash = h->ops->hash_item(item); + hash %= h->buckets->num; node = (apk_hash_node *) (item + h->ops->node_offset); hlist_add_head(node, &h->buckets->item[hash]); h->num_items++; -- cgit v1.2.3