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>

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);