summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-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);