pkghash improvements/modifications

This patch changes a variety of small things related to our pkghash
implementation with an eye toward performance, especially on native
32-bit systems.

* Use `unsigned int` rather than `size_t` for hash sizes. We already
  return ERANGE for any attempted creation of a hash greater than 1
  million elements, so unsigned int is more than large enough for our
  purposes. Switching to this type allows 32 bit systems to do native
  math without helper functions from libgcc.
* _alpm_pkghash_create() now internally adds extra padding for
  additional array elements, rather than that being the responsibility of
  the caller.
* #define values are moved into static const values in pkghash.c; a new
  `stride` value is also extracted (but remains set at 1).
* Division and modulus operators are removed from the normal find and
  add paths if possible. We store the upper limit of the number of
  elements in the hash so we no longer need to calculate this every
  element addition. When doing wraparound position calculations, we only
  apply the modulus operator if the value is greater than the number of
  buckets.

Signed-off-by: Dan McGee <dan@archlinux.org>

1 files changed, 7 insertions, 7 deletions

diff --git a/lib/libalpm/pkghash.h b/lib/libalpm/pkghash.h
index edd500e9..64a32b22 100644
--- a/lib/libalpm/pkghash.h
+++ b/lib/libalpm/pkghash.h
@@ -35,17 +35,19 @@
 struct __alpm_pkghash_t {
 	/** data held by the hash table */
 	alpm_list_t **hash_table;
-	/** number of buckets in hash table */
-	size_t buckets;
-	/** number of entries in hash table */
-	size_t entries;
 	/** head node of the hash table data in normal list format */
 	alpm_list_t *list;
+	/** number of buckets in hash table */
+	unsigned int buckets;
+	/** number of entries in hash table */
+	unsigned int entries;
+	/** max number of entries before a resize is needed */
+	unsigned int limit;
 };
 
 typedef struct __alpm_pkghash_t alpm_pkghash_t;
 
-alpm_pkghash_t *_alpm_pkghash_create(size_t size);
+alpm_pkghash_t *_alpm_pkghash_create(unsigned int size);
 
 alpm_pkghash_t *_alpm_pkghash_add(alpm_pkghash_t *hash, alpm_pkg_t *pkg);
 alpm_pkghash_t *_alpm_pkghash_add_sorted(alpm_pkghash_t *hash, alpm_pkg_t *pkg);
@@ -55,6 +57,4 @@ void _alpm_pkghash_free(alpm_pkghash_t *hash);
 
 alpm_pkg_t *_alpm_pkghash_find(alpm_pkghash_t *hash, const char *name);
 
-#define MAX_HASH_LOAD 0.7
-
 #endif /* _ALPM_PKGHASH_H */