From f1985b03bdf77c049cc28b25fe6275867c25ba49 Mon Sep 17 00:00:00 2001 From: Timo Teras Date: Tue, 14 Jul 2009 10:47:20 +0300 Subject: hash: allow caching of hash value --- src/apk_blob.h | 1 + src/apk_database.h | 1 + src/apk_hash.h | 36 ++++++++++++++++++++++++++++++++---- src/blob.c | 9 +++++++-- src/database.c | 22 ++++++++++++++-------- src/hash.c | 19 ++++++------------- 6 files changed, 61 insertions(+), 27 deletions(-) (limited to 'src') diff --git a/src/apk_blob.h b/src/apk_blob.h index 6359313..bea2d08 100644 --- a/src/apk_blob.h +++ b/src/apk_blob.h @@ -41,6 +41,7 @@ int apk_blob_spn(apk_blob_t blob, const char *accept, apk_blob_t *l, apk_blob_t int apk_blob_cspn(apk_blob_t blob, const char *reject, apk_blob_t *l, apk_blob_t *r); int apk_blob_split(apk_blob_t blob, apk_blob_t split, apk_blob_t *l, apk_blob_t *r); int apk_blob_rsplit(apk_blob_t blob, char split, apk_blob_t *l, apk_blob_t *r); +unsigned long apk_blob_hash_seed(apk_blob_t, unsigned long seed); unsigned long apk_blob_hash(apk_blob_t str); int apk_blob_compare(apk_blob_t a, apk_blob_t b); unsigned int apk_blob_parse_uint(apk_blob_t *b, int radix); diff --git a/src/apk_database.h b/src/apk_database.h index 1a2ffb8..31f83f2 100644 --- a/src/apk_database.h +++ b/src/apk_database.h @@ -38,6 +38,7 @@ struct apk_db_file { struct apk_db_dir { apk_hash_node hash_node; + unsigned int hash; struct hlist_head files; struct apk_db_dir *parent; diff --git a/src/apk_hash.h b/src/apk_hash.h index b9c975e..bcaaed1 100644 --- a/src/apk_hash.h +++ b/src/apk_hash.h @@ -4,7 +4,7 @@ * Copyright (C) 2008 Timo Teräs * All rights reserved. * - * This program is free software; you can redistribute it and/or modify it + * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 as published * by the Free Software Foundation. See http://www.gnu.org/ for details. */ @@ -48,8 +48,36 @@ void apk_hash_init(struct apk_hash *h, const struct apk_hash_ops *ops, void apk_hash_free(struct apk_hash *h); int apk_hash_foreach(struct apk_hash *h, apk_hash_enumerator_f e, void *ctx); -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); -void apk_hash_delete(struct apk_hash *h, apk_blob_t key); +apk_hash_item apk_hash_get_hashed(struct apk_hash *h, apk_blob_t key, unsigned long hash); +void apk_hash_insert_hashed(struct apk_hash *h, apk_hash_item item, unsigned long hash); +void apk_hash_delete_hashed(struct apk_hash *h, apk_blob_t key, unsigned long hash); + +static inline unsigned long apk_hash_from_key(struct apk_hash *h, apk_blob_t key) +{ + return h->ops->hash_key(key); +} + +static inline unsigned long apk_hash_from_item(struct apk_hash *h, apk_hash_item item) +{ + if (h->ops->hash_item != NULL) + return h->ops->hash_item(item); + return apk_hash_from_key(h, h->ops->get_key(item)); +} + +static inline apk_hash_item apk_hash_get(struct apk_hash *h, apk_blob_t key) +{ + return apk_hash_get_hashed(h, key, apk_hash_from_key(h, key)); +} + + +static inline void apk_hash_insert(struct apk_hash *h, apk_hash_item item) +{ + return apk_hash_insert_hashed(h, item, apk_hash_from_item(h, item)); +} + +static inline void apk_hash_delete(struct apk_hash *h, apk_blob_t key) +{ + return apk_hash_delete_hashed(h, key, apk_hash_from_key(h, key)); +} #endif diff --git a/src/blob.c b/src/blob.c index 43c94ea..9f253cb 100644 --- a/src/blob.c +++ b/src/blob.c @@ -98,9 +98,9 @@ int apk_blob_split(apk_blob_t blob, apk_blob_t split, apk_blob_t *l, apk_blob_t } } -unsigned long apk_blob_hash(apk_blob_t blob) +unsigned long apk_blob_hash_seed(apk_blob_t blob, unsigned long seed) { - unsigned long hash = 5381; + unsigned long hash = seed; int i; for (i = 0; i < blob.len; i++) @@ -109,6 +109,11 @@ unsigned long apk_blob_hash(apk_blob_t blob) return hash; } +unsigned long apk_blob_hash(apk_blob_t blob) +{ + return apk_blob_hash_seed(blob, 5381); +} + int apk_blob_compare(apk_blob_t a, apk_blob_t b) { if (a.len == b.len) diff --git a/src/database.c b/src/database.c index 996738e..cce1b0c 100644 --- a/src/database.c +++ b/src/database.c @@ -101,6 +101,7 @@ static const struct apk_hash_ops dir_hash_ops = { }; struct apk_db_file_hash_key { + unsigned long dirhash; apk_blob_t dirname; apk_blob_t filename; }; @@ -109,16 +110,14 @@ static unsigned long apk_db_file_hash_key(apk_blob_t _key) { 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); + return apk_blob_hash_seed(key->filename, key->dirhash); } 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)); + return apk_blob_hash_seed(APK_BLOB_STR(dbf->filename), dbf->diri->dir->hash); } static int apk_db_file_compare_item(apk_hash_item item, apk_blob_t _key) @@ -127,6 +126,9 @@ static int apk_db_file_compare_item(apk_hash_item item, apk_blob_t _key) struct apk_db_file_hash_key *key = (struct apk_db_file_hash_key *) _key.ptr; int r; + if (key->dirhash != dbf->diri->dir->hash) + return key->dirhash - dbf->diri->dir->hash; + r = apk_blob_compare(key->dirname, APK_BLOB_STR(dbf->diri->dir->dirname)); if (r != 0) return r; @@ -150,8 +152,9 @@ struct apk_name *apk_db_query_name(struct apk_database *db, apk_blob_t name) struct apk_name *apk_db_get_name(struct apk_database *db, apk_blob_t name) { struct apk_name *pn; + unsigned long hash = apk_hash_from_key(&db->available.names, name); - pn = apk_db_query_name(db, name); + pn = (struct apk_name *) apk_hash_get_hashed(&db->available.names, name, hash); if (pn != NULL) return pn; @@ -161,7 +164,7 @@ struct apk_name *apk_db_get_name(struct apk_database *db, apk_blob_t name) pn->name = apk_blob_cstr(name); pn->id = db->name_id++; - apk_hash_insert(&db->available.names, pn); + apk_hash_insert_hashed(&db->available.names, pn, hash); return pn; } @@ -195,12 +198,13 @@ static struct apk_db_dir *apk_db_dir_get(struct apk_database *db, { struct apk_db_dir *dir; apk_blob_t bparent; + unsigned long hash = apk_hash_from_key(&db->installed.dirs, name); int i; if (name.len && name.ptr[name.len-1] == '/') name.len--; - dir = apk_db_dir_query(db, name); + dir = (struct apk_db_dir *) apk_hash_get_hashed(&db->installed.dirs, name, hash); if (dir != NULL) return apk_db_dir_ref(dir); @@ -210,7 +214,8 @@ static struct apk_db_dir *apk_db_dir_get(struct apk_database *db, dir->refs = 1; memcpy(dir->dirname, name.ptr, name.len); dir->dirname[name.len] = 0; - apk_hash_insert(&db->installed.dirs, dir); + dir->hash = apk_blob_hash(APK_BLOB_STR(dir->dirname)); + apk_hash_insert_hashed(&db->installed.dirs, dir, hash); if (name.len == 0) dir->parent = NULL; @@ -286,6 +291,7 @@ struct apk_db_file *apk_db_file_query(struct apk_database *db, struct apk_db_file_hash_key key; key = (struct apk_db_file_hash_key) { + .dirhash = apk_blob_hash(dir), .dirname = dir, .filename = name, }; diff --git a/src/hash.c b/src/hash.c index 8013d06..c85a29d 100644 --- a/src/hash.c +++ b/src/hash.c @@ -4,7 +4,7 @@ * Copyright (C) 2008 Timo Teräs * All rights reserved. * - * This program is free software; you can redistribute it and/or modify it + * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 as published * by the Free Software Foundation. See http://www.gnu.org/ for details. */ @@ -43,15 +43,14 @@ int apk_hash_foreach(struct apk_hash *h, apk_hash_enumerator_f e, void *ctx) return 0; } -apk_hash_item apk_hash_get(struct apk_hash *h, apk_blob_t key) +apk_hash_item apk_hash_get_hashed(struct apk_hash *h, apk_blob_t key, unsigned long hash) { ptrdiff_t offset = h->ops->node_offset; - unsigned long hash; apk_hash_node *pos; apk_hash_item item; apk_blob_t itemkey; - hash = h->ops->hash_key(key) % h->buckets->num; + hash %= h->buckets->num; if (h->ops->compare_item != NULL) { hlist_for_each(pos, &h->buckets->item[hash]) { item = ((void *) pos) - offset; @@ -70,30 +69,24 @@ apk_hash_item apk_hash_get(struct apk_hash *h, apk_blob_t key) return NULL; } -void apk_hash_insert(struct apk_hash *h, apk_hash_item item) +void apk_hash_insert_hashed(struct apk_hash *h, apk_hash_item item, unsigned long hash) { - unsigned long hash; apk_hash_node *node; - 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++; } -void apk_hash_delete(struct apk_hash *h, apk_blob_t key) +void apk_hash_delete_hashed(struct apk_hash *h, apk_blob_t key, unsigned long hash) { ptrdiff_t offset = h->ops->node_offset; - unsigned long hash; apk_hash_node *pos; apk_hash_item item; apk_blob_t itemkey; - hash = h->ops->hash_key(key) % h->buckets->num; + hash %= h->buckets->num; if (h->ops->compare_item != NULL) { hlist_for_each(pos, &h->buckets->item[hash]) { item = ((void *) pos) - offset; -- cgit v1.2.3