From 01c3c7e4f28d837f0b8a6aaaf27d16894d4b762d Mon Sep 17 00:00:00 2001
From: Allan McRae <allan@archlinux.org>
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 <allan@archlinux.org>
---
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')
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-70-g09d2