From f8fdce6cb0da4d832ffa730e0dacb5544c1f8154 Mon Sep 17 00:00:00 2001 From: Allan McRae Date: Tue, 25 Jan 2011 11:49:34 +1000 Subject: Read pkgcache into hash Read the package information for sync/local databases into a pmpkghash_t structure. Provide a alpm_db_get_pkgcache_list() method that returns the list from the hash object. Most usages of alpm_db_get_pkgcache are converted to this at this stage for ease of implementation. Review whether these are better accessing the hash table directly at a later stage. Signed-off-by: Allan McRae --- lib/libalpm/db.c | 55 +++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 41 insertions(+), 14 deletions(-) (limited to 'lib/libalpm/db.c') diff --git a/lib/libalpm/db.c b/lib/libalpm/db.c index c80dcbb8..c0c2f0ca 100644 --- a/lib/libalpm/db.c +++ b/lib/libalpm/db.c @@ -249,9 +249,9 @@ pmpkg_t SYMEXPORT *alpm_db_get_pkg(pmdb_t *db, const char *name) /** Get the package cache of a package database * @param db pointer to the package database to get the package from - * @return the list of packages on success, NULL on error + * @return the hash of packages on success, NULL on error */ -alpm_list_t SYMEXPORT *alpm_db_get_pkgcache(pmdb_t *db) +pmpkghash_t SYMEXPORT *alpm_db_get_pkgcache(pmdb_t *db) { ALPM_LOG_FUNC; @@ -262,6 +262,21 @@ alpm_list_t SYMEXPORT *alpm_db_get_pkgcache(pmdb_t *db) return(_alpm_db_get_pkgcache(db)); } +/** Get the package cache of a package database + * @param db pointer to the package database to get the package from + * @return the list of packages on success, NULL on error + */ +alpm_list_t SYMEXPORT *alpm_db_get_pkgcache_list(pmdb_t *db) +{ + ALPM_LOG_FUNC; + + /* Sanity checks */ + ASSERT(handle != NULL, return(NULL)); + ASSERT(db != NULL, return(NULL)); + + return(_alpm_db_get_pkgcache_list(db)); +} + /** Get a group entry from a package database * @param db pointer to the package database to get the group from * @param name of the group @@ -417,7 +432,7 @@ alpm_list_t *_alpm_db_search(pmdb_t *db, const alpm_list_t *needles) const alpm_list_t *i, *j, *k; alpm_list_t *ret = NULL; /* copy the pkgcache- we will free the list var after each needle */ - alpm_list_t *list = alpm_list_copy(_alpm_db_get_pkgcache(db)); + alpm_list_t *list = alpm_list_copy(_alpm_db_get_pkgcache_list(db)); ALPM_LOG_FUNC; @@ -523,14 +538,15 @@ void _alpm_db_free_pkgcache(pmdb_t *db) _alpm_log(PM_LOG_DEBUG, "freeing package cache for repository '%s'\n", db->treename); - alpm_list_free_inner(db->pkgcache, (alpm_list_fn_free)_alpm_pkg_free); - alpm_list_free(db->pkgcache); + alpm_list_free_inner(_alpm_db_get_pkgcache_list(db), + (alpm_list_fn_free)_alpm_pkg_free); + _alpm_pkghash_free(db->pkgcache); db->pkgcache_loaded = 0; _alpm_db_free_grpcache(db); } -alpm_list_t *_alpm_db_get_pkgcache(pmdb_t *db) +pmpkghash_t *_alpm_db_get_pkgcache(pmdb_t *db) { ALPM_LOG_FUNC; @@ -550,6 +566,19 @@ alpm_list_t *_alpm_db_get_pkgcache(pmdb_t *db) return(db->pkgcache); } +alpm_list_t *_alpm_db_get_pkgcache_list(pmdb_t *db) +{ + ALPM_LOG_FUNC; + + pmpkghash_t *hash = _alpm_db_get_pkgcache(db); + + if(hash == NULL) { + return(NULL); + } + + return(hash->list); +} + /* "duplicate" pkg then add it to pkgcache */ int _alpm_db_add_pkgincache(pmdb_t *db, pmpkg_t *pkg) { @@ -568,7 +597,7 @@ int _alpm_db_add_pkgincache(pmdb_t *db, pmpkg_t *pkg) _alpm_log(PM_LOG_DEBUG, "adding entry '%s' in '%s' cache\n", alpm_pkg_get_name(newpkg), db->treename); - db->pkgcache = alpm_list_add_sorted(db->pkgcache, newpkg, _alpm_pkg_cmp); + db->pkgcache = _alpm_pkghash_add_sorted(db->pkgcache, newpkg); _alpm_db_free_grpcache(db); @@ -577,8 +606,7 @@ int _alpm_db_add_pkgincache(pmdb_t *db, pmpkg_t *pkg) int _alpm_db_remove_pkgfromcache(pmdb_t *db, pmpkg_t *pkg) { - void *vdata; - pmpkg_t *data; + pmpkg_t *data = NULL; ALPM_LOG_FUNC; @@ -589,8 +617,7 @@ int _alpm_db_remove_pkgfromcache(pmdb_t *db, pmpkg_t *pkg) _alpm_log(PM_LOG_DEBUG, "removing entry '%s' from '%s' cache\n", alpm_pkg_get_name(pkg), db->treename); - db->pkgcache = alpm_list_remove(db->pkgcache, pkg, _alpm_pkg_cmp, &vdata); - data = vdata; + db->pkgcache = _alpm_pkghash_remove(db->pkgcache, pkg, data); if(data == NULL) { /* package not found */ _alpm_log(PM_LOG_DEBUG, "cannot remove entry '%s' from '%s' cache: not found\n", @@ -613,14 +640,14 @@ pmpkg_t *_alpm_db_get_pkgfromcache(pmdb_t *db, const char *target) return(NULL); } - alpm_list_t *pkgcache = _alpm_db_get_pkgcache(db); + pmpkghash_t *pkgcache = _alpm_db_get_pkgcache(db); if(!pkgcache) { _alpm_log(PM_LOG_DEBUG, "warning: failed to get '%s' from NULL pkgcache\n", target); return(NULL); } - return(_alpm_pkg_find(pkgcache, target)); + return(_alpm_pkghash_find(pkgcache, target)); } /* Returns a new group cache from db. @@ -638,7 +665,7 @@ int _alpm_db_load_grpcache(pmdb_t *db) _alpm_log(PM_LOG_DEBUG, "loading group cache for repository '%s'\n", db->treename); - for(lp = _alpm_db_get_pkgcache(db); lp; lp = lp->next) { + for(lp = _alpm_db_get_pkgcache_list(db); lp; lp = lp->next) { const alpm_list_t *i; pmpkg_t *pkg = lp->data; -- cgit v1.2.3-54-g00ecf From 01c3c7e4f28d837f0b8a6aaaf27d16894d4b762d Mon Sep 17 00:00:00 2001 From: Allan McRae Date: Sun, 30 Jan 2011 22:42:45 +1000 Subject: Actually remove packages from pkghash on removal Fully removes a package from the hash. Also unify prototype with removal from an alpm_list_t, fixing issues when removing a package from the pkgcache. Signed-off-by: Allan McRae --- lib/libalpm/db.c | 2 +- lib/libalpm/pkghash.c | 37 +++++++++++++++++++++++++++++-------- lib/libalpm/pkghash.h | 2 +- 3 files changed, 31 insertions(+), 10 deletions(-) (limited to 'lib/libalpm/db.c') diff --git a/lib/libalpm/db.c b/lib/libalpm/db.c index c0c2f0ca..02f82823 100644 --- a/lib/libalpm/db.c +++ b/lib/libalpm/db.c @@ -617,7 +617,7 @@ int _alpm_db_remove_pkgfromcache(pmdb_t *db, pmpkg_t *pkg) _alpm_log(PM_LOG_DEBUG, "removing entry '%s' from '%s' cache\n", alpm_pkg_get_name(pkg), db->treename); - db->pkgcache = _alpm_pkghash_remove(db->pkgcache, pkg, data); + db->pkgcache = _alpm_pkghash_remove(db->pkgcache, pkg, &data); if(data == NULL) { /* package not found */ _alpm_log(PM_LOG_DEBUG, "cannot remove entry '%s' from '%s' cache: not found\n", diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c index bdff78ea..14056e37 100644 --- a/lib/libalpm/pkghash.c +++ b/lib/libalpm/pkghash.c @@ -219,11 +219,15 @@ pmpkghash_t *_alpm_pkghash_add_sorted(pmpkghash_t *hash, pmpkg_t *pkg) * * @return the resultant hash */ -pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data) +pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t **data) { alpm_list_t *i; size_t position; + if(data) { + *data = NULL; + } + if(pkg == NULL || hash == NULL) { return(hash); } @@ -235,7 +239,6 @@ pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data if(info->name_hash == pkg->name_hash && strcmp(info->name, pkg->name) == 0) { -#if 0 /* Actually removing items is not a good idea with linear probing... */ /* remove from list */ /* TODO - refactor with alpm_list_remove */ if(i == hash->list) { @@ -266,16 +269,34 @@ pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data } /* remove from hash */ - data = info; - info = NULL; + if(data) { + *data = info; + } + hash->hash_table[position] = NULL; free(i); - i = NULL; hash->entries -= 1; -#endif - /* fake removal - pkgname can not be blank so 0 hash is impossible */ - info->name_hash = 0; + /* potentially move entries following removed entry to keep + * open addressing collision resolution working */ + size_t next_null = (position + 1) % hash->buckets; + while(hash->hash_table[next_null] != NULL) { + next_null = (next_null + 1) % hash->buckets; + } + + position = (position + 1) % hash->buckets; + + while((i = hash->hash_table[position]) != NULL) { + info = i->data; + size_t new_position = get_hash_position(info->name_hash, hash); + + if(new_position != next_null) { + hash->hash_table[new_position] = i; + hash->hash_table[position] = NULL; + } + + position = (position + 1) % hash->buckets; + } return(hash); } diff --git a/lib/libalpm/pkghash.h b/lib/libalpm/pkghash.h index 7f90cb17..a6c1db71 100644 --- a/lib/libalpm/pkghash.h +++ b/lib/libalpm/pkghash.h @@ -47,7 +47,7 @@ pmpkghash_t *_alpm_pkghash_create(size_t size); pmpkghash_t *_alpm_pkghash_add(pmpkghash_t *hash, pmpkg_t *pkg); pmpkghash_t *_alpm_pkghash_add_sorted(pmpkghash_t *hash, pmpkg_t *pkg); -pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data); +pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t **data); void _alpm_pkghash_free(pmpkghash_t *hash); -- cgit v1.2.3-54-g00ecf