summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDan McGee <dan@archlinux.org>2011-02-03 10:55:26 -0600
committerAllan McRae <allan@archlinux.org>2011-02-04 10:03:04 +1000
commit6b0d4674bb132b2583920211cc798f3db77ec392 (patch)
treeb752fbe93c55d04a94e1c346f6bab52ce9de18ec
parent1f145bcd1a4fb22d4cb548a3be64898f60820695 (diff)
downloadpacman-6b0d4674bb132b2583920211cc798f3db77ec392.tar.xz
Improve pkghash_remove algorithm
Rather than potentially move every item to the next NULL, attempt to move at most one item at a time by iterating backwards from the NULL location in the hash array. If we move an item, we repeat the process on the now shorter "chain" until no more items need moving. Signed-off-by: Dan McGee <dan@archlinux.org> Signed-off-by: Allan McRae <allan@archlinux.org>
-rw-r--r--lib/libalpm/pkghash.c62
1 files changed, 43 insertions, 19 deletions
diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
index 3d420e1f..54805275 100644
--- a/lib/libalpm/pkghash.c
+++ b/lib/libalpm/pkghash.c
@@ -210,6 +210,34 @@ pmpkghash_t *_alpm_pkghash_add_sorted(pmpkghash_t *hash, pmpkg_t *pkg)
return(hash);
}
+static size_t move_one_entry(pmpkghash_t *hash, size_t start, size_t end)
+{
+ /* Iterate backwards from 'end' to 'start', seeing if any of the items
+ * would hash to 'start'. If we find one, we move it there and break. If
+ * we get all the way back to position and find none that hash to it, we
+ * also end iteration. Iterating backwards helps prevent needless shuffles;
+ * we will never need to move more than one item per function call. The
+ * return value is our current iteration location; if this is equal to
+ * 'start' we can stop this madness. */
+ while(end != start) {
+ alpm_list_t *i = hash->hash_table[end];
+ pmpkg_t *info = i->data;
+ size_t new_position = get_hash_position(info->name_hash, hash);
+
+ if(new_position == start) {
+ hash->hash_table[start] = i;
+ hash->hash_table[end] = NULL;
+ break;
+ }
+
+ /* the odd math ensures we are always positive, e.g.
+ * e.g. (0 - 1) % 47 == -1
+ * e.g. (47 + 0 - 1) % 47 == 46 */
+ end = (hash->buckets + end - 1) % hash->buckets;
+ }
+ return(end);
+}
+
/**
* @brief Remove a package from a pkghash.
*
@@ -239,6 +267,7 @@ pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg,
if(info->name_hash == pkg->name_hash &&
strcmp(info->name, pkg->name) == 0) {
+ size_t stop, prev;
/* remove from list and hash */
hash->list = alpm_list_remove_item(hash->list, i);
@@ -247,28 +276,23 @@ pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg,
}
hash->hash_table[position] = NULL;
free(i);
-
hash->entries -= 1;
- /* 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;
+ /* Potentially move entries following removed entry to keep open
+ * addressing collision resolution working. We start by finding the
+ * next null bucket to know how far we have to look. */
+ stop = (position + 1) % hash->buckets;
+ while(hash->hash_table[stop] != NULL && stop != position) {
+ stop = (stop + 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;
+ stop = (hash->buckets + stop - 1) % hash->buckets;
+
+ /* We now search backwards from stop to position. If we find an
+ * item that now hashes to position, we will move it, and then try
+ * to plug the new hole we just opened up, until we finally don't
+ * move anything. */
+ while((prev = move_one_entry(hash, position, stop)) != position) {
+ position = prev;
}
return(hash);