From e17b0446bd815f7b25f5bf0b838ef3d02d4eb64e Mon Sep 17 00:00:00 2001
From: Allan McRae <allan@archlinux.org>
Date: Fri, 7 Jan 2011 00:32:17 +1000
Subject: Add a hash table for holding packages

Signed-off-by: Allan McRae <allan@archlinux.org>
---
 lib/libalpm/Makefile.am |   1 +
 lib/libalpm/alpm.h      |   1 +
 lib/libalpm/pkghash.c   | 292 ++++++++++++++++++++++++++++++++++++++++++++++++
 lib/libalpm/pkghash.h   |  58 ++++++++++
 4 files changed, 352 insertions(+)
 create mode 100644 lib/libalpm/pkghash.c
 create mode 100644 lib/libalpm/pkghash.h

diff --git a/lib/libalpm/Makefile.am b/lib/libalpm/Makefile.am
index da663cb5..1bda5714 100644
--- a/lib/libalpm/Makefile.am
+++ b/lib/libalpm/Makefile.am
@@ -40,6 +40,7 @@ libalpm_la_SOURCES = \
 	handle.h handle.c \
 	log.h log.c \
 	package.h package.c \
+	pkghash.h pkghash.c \
 	remove.h remove.c \
 	sync.h sync.c \
 	trans.h trans.c \
diff --git a/lib/libalpm/alpm.h b/lib/libalpm/alpm.h
index 19ea4ffd..f33abf7a 100644
--- a/lib/libalpm/alpm.h
+++ b/lib/libalpm/alpm.h
@@ -52,6 +52,7 @@ typedef struct __pmdepend_t pmdepend_t;
 typedef struct __pmdepmissing_t pmdepmissing_t;
 typedef struct __pmconflict_t pmconflict_t;
 typedef struct __pmfileconflict_t pmfileconflict_t;
+typedef struct __pmpkghash_t pmpkghash_t;
 
 /*
  * Library
diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
new file mode 100644
index 00000000..3ed6453f
--- /dev/null
+++ b/lib/libalpm/pkghash.c
@@ -0,0 +1,292 @@
+/*
+ *  pkghash.c
+ *
+ *  Copyright (c) 2011 Pacman Development Team <pacman-dev@archlinux.org>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "pkghash.h"
+#include "util.h"
+#include "log.h"
+
+/* List of primes for possible sizes of hash tables.
+ *
+ * The maximum table size is the last prime under 1,000,000.  That is
+ * more than an order of magnitude greater than the number of packages
+ * in any Linux distribution.
+ */
+static const size_t prime_list[] =
+{
+	11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, 37ul, 41ul, 43ul, 47ul,
+	53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, 83ul, 89ul, 97ul, 103ul,
+	109ul, 113ul, 127ul, 137ul, 139ul, 149ul, 157ul, 167ul, 179ul, 193ul,
+	199ul, 211ul, 227ul, 241ul, 257ul, 277ul, 293ul, 313ul, 337ul, 359ul,
+	383ul, 409ul, 439ul, 467ul, 503ul, 541ul, 577ul, 619ul, 661ul, 709ul,
+	761ul, 823ul, 887ul, 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul,
+	1493ul, 1613ul, 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul,
+	2753ul, 2971ul, 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul,
+	5087ul, 5503ul, 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul,
+	9497ul, 10273ul, 11113ul, 12011ul, 12983ul, 14033ul, 15173ul,
+	16411ul, 17749ul, 19183ul, 20753ul, 22447ul, 24281ul, 26267ul,
+	28411ul, 30727ul, 33223ul, 35933ul, 38873ul, 42043ul, 45481ul,
+	49201ul, 53201ul, 57557ul, 62233ul, 67307ul, 72817ul, 78779ul,
+	85229ul, 92203ul, 99733ul, 107897ul, 116731ul, 126271ul, 136607ul,
+	147793ul, 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
+	256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, 410857ul,
+	444487ul, 480881ul, 520241ul, 562841ul, 608903ul, 658753ul, 712697ul,
+	771049ul, 834181ul, 902483ul, 976369ul
+};
+
+/* Allocate a hash table with at least "size" buckets */
+pmpkghash_t *_alpm_pkghash_create(size_t size)
+{
+	pmpkghash_t *hash = NULL;
+	size_t i, loopsize;
+
+	MALLOC(hash, sizeof(pmpkghash_t), RET_ERR(PM_ERR_MEMORY, NULL));
+
+	hash->list = NULL;
+	hash->entries = 0;
+
+	loopsize = sizeof(prime_list) / sizeof(*prime_list);
+	for(i = 0; i < loopsize; i++) {
+		if(prime_list[i] > size) {
+			hash->buckets = prime_list[i];
+			break;
+		}
+	}
+
+	CALLOC(hash->hash_table, hash->buckets, sizeof(alpm_list_t*), \
+				free(hash); RET_ERR(PM_ERR_MEMORY, NULL));
+
+	return(hash);
+}
+
+/* Expand the hash table size to the next increment and rebin the entries */
+static pmpkghash_t *rehash(pmpkghash_t *oldhash)
+{
+	//pmpkghash_t *newhash;
+
+	/* TODO - calculate size of newhash */
+	/* Hash tables will need resized in two cases:
+	 *  - adding packages to the local database
+	 *  - poor estimation of the number of packages in sync database
+	 *
+	 * For small hash tables sizes (<500) the increase in size is by a
+	 * minimum of a factor of 2 for optimal rehash efficiency.  For
+	 * larger database sizes, this increase is reduced to avoid excess
+	 * memory allocation as both scenarios requiring a rehash should not
+	 * require a table size increase that large. */
+
+	//newhash = _alpm_pkghash_create(oldhash->buckets);
+
+	/* TODO - rebin entries */
+
+	//_alpm_pkghash_free(oldhash);
+
+	//return newhash;
+
+	printf("rehash needed!!!\n");
+	return(oldhash);
+}
+
+pmpkghash_t *_alpm_pkghash_add(pmpkghash_t *hash, pmpkg_t *pkg)
+{
+	alpm_list_t *ptr;
+	size_t position;
+
+	if(pkg == NULL || hash == NULL) {
+		return(hash);
+	}
+
+	if((hash->entries + 1) / MAX_HASH_LOAD > hash->buckets) {
+		hash = rehash(hash);
+	}
+
+	position = pkg->name_hash % hash->buckets;
+
+	/* collision resolution using open addressing with linear probing */
+	while((ptr = hash->hash_table[position]) != NULL) {
+		position = (position + 1) % hash->buckets;
+	}
+
+	ptr = calloc(1, sizeof(alpm_list_t));
+	if(ptr == NULL) {
+		return(hash);
+	}
+
+	ptr->data = pkg;
+	ptr->next = NULL;
+	ptr->prev = ptr;
+
+	hash->hash_table[position] = ptr;
+	hash->list = alpm_list_join(hash->list, ptr);
+	hash->entries += 1;
+
+	return(hash);
+}
+
+pmpkghash_t *_alpm_pkghash_add_sorted(pmpkghash_t *hash, pmpkg_t *pkg)
+{
+	if(!hash) {
+		return(_alpm_pkghash_add(hash, pkg));
+	}
+
+	alpm_list_t *ptr;
+	size_t position;
+
+	if((hash->entries + 1) / MAX_HASH_LOAD > hash->buckets) {
+		hash = rehash(hash);
+	}
+
+	position = pkg->name_hash % hash->buckets;
+
+	/* collision resolution using open addressing with linear probing */
+	while((ptr = hash->hash_table[position]) != NULL) {
+		position = (position + 1) % hash->buckets;
+	}
+
+	ptr = calloc(1, sizeof(alpm_list_t));
+	if(ptr == NULL) {
+		return(hash);
+	}
+
+	ptr->data = pkg;
+	ptr->next = NULL;
+	ptr->prev = ptr;
+
+	hash->hash_table[position] = ptr;
+	hash->list = alpm_list_mmerge(hash->list, ptr, _alpm_pkg_cmp);
+	hash->entries += 1;
+
+	return(hash);
+}
+
+/**
+ * @brief Remove a package from a pkghash.
+ *
+ * @param hash     the hash to remove the package from
+ * @param pkg      the package we are removing
+ * @param data     output parameter containing the removed item
+ *
+ * @return the resultant hash
+ */
+pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t *data)
+{
+	alpm_list_t *i;
+	size_t position;
+
+	if(pkg == NULL || hash == NULL) {
+		return(hash);
+	}
+
+	position = pkg->name_hash % hash->buckets;
+	while((i = hash->hash_table[position]) != NULL) {
+		pmpkg_t *info = i->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) {
+				/* Special case: removing the head node which has a back reference to
+				 * the tail node */
+				hash->list = i->next;
+				if(hash->list) {
+					hash->list->prev = i->prev;
+				}
+				i->prev = NULL;
+			} else if(i == hash->list->prev) {
+				/* Special case: removing the tail node, so we need to fix the back
+				 * reference on the head node. We also know tail != head. */
+				if(i->prev) {
+					/* i->next should always be null */
+					i->prev->next = i->next;
+					hash->list->prev = i->prev;
+					i->prev = NULL;
+				}
+			} else {
+				/* Normal case, non-head and non-tail node */
+				if(i->next) {
+					i->next->prev = i->prev;
+				}
+				if(i->prev) {
+					i->prev->next = i->next;
+				}
+			}
+
+			/* remove from hash */
+			data = info;
+			info = 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;
+
+			return(hash);
+		}
+
+		position = (position + 1) % hash->buckets;
+	}
+
+	return(hash);
+}
+
+void _alpm_pkghash_free(pmpkghash_t *hash)
+{
+	size_t i;
+	if(hash != NULL) {
+		for(i = 0; i < hash->buckets; i++) {
+			free(hash->hash_table[i]);
+		}
+		free(hash->hash_table);
+	}
+	free(hash);
+}
+
+pmpkg_t *_alpm_pkghash_find(pmpkghash_t *hash, const char *name)
+{
+	alpm_list_t *lp;
+	unsigned long name_hash;
+	size_t position;
+
+	ALPM_LOG_FUNC;
+
+	if(name == NULL || hash == NULL) {
+		return(NULL);
+	}
+
+	name_hash = _alpm_hash_sdbm(name);
+
+	position = name_hash % hash->buckets;
+
+	while((lp = hash->hash_table[position]) != NULL) {
+		pmpkg_t *info = lp->data;
+
+		if(info->name_hash == name_hash && strcmp(info->name, name) == 0) {
+			return(info);
+		}
+
+		position = (position + 1) % hash->buckets;
+	}
+
+	return(NULL);
+}
diff --git a/lib/libalpm/pkghash.h b/lib/libalpm/pkghash.h
new file mode 100644
index 00000000..7f90cb17
--- /dev/null
+++ b/lib/libalpm/pkghash.h
@@ -0,0 +1,58 @@
+/*
+ *  pkghash.h
+ *
+ *  Copyright (c) 2011 Pacman Development Team <pacman-dev@archlinux.org>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _ALPM_PKGHASH_H
+#define _ALPM_PKGHASH_H
+
+#include <stdlib.h>
+
+#include "alpm.h"
+#include "alpm_list.h"
+
+
+/**
+ * @brief A hash table for holding pmpkg_t objects.
+ *
+ * A combination of a hash table and a list, allowing for fast look-up
+ * by package name but also iteration over the packages.
+ */
+struct __pmpkghash_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;
+};
+
+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);
+
+void _alpm_pkghash_free(pmpkghash_t *hash);
+
+pmpkg_t *_alpm_pkghash_find(pmpkghash_t *hash, const char *name);
+
+#define MAX_HASH_LOAD 0.7
+
+#endif /* _ALPM_PKGHASH_H */
-- 
cgit v1.2.3-70-g09d2


From 5dae577a87795e7666f05613cf9aa7207fd17346 Mon Sep 17 00:00:00 2001
From: Dan McGee <dan@archlinux.org>
Date: Mon, 24 Jan 2011 17:48:54 -0600
Subject: Get estimated package count when populating databases

This works for both local and sync databases in slightly different ways. For
the local database, we can use the directory hard link count on the local/
folder. For sync databases, we use the archive size coupled with some
computed average per-package sizes to determine an estimate.

This is currently a dead assignment once calculated, but could be used to
set the initial size of a hash table.

Signed-off-by: Dan McGee <dan@archlinux.org>
Signed-off-by: Allan McRae <allan@archlinux.org>
---
 lib/libalpm/be_local.c |  8 ++++++-
 lib/libalpm/be_sync.c  | 64 +++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 70 insertions(+), 2 deletions(-)

diff --git a/lib/libalpm/be_local.c b/lib/libalpm/be_local.c
index c7110faf..b97fca71 100644
--- a/lib/libalpm/be_local.c
+++ b/lib/libalpm/be_local.c
@@ -367,7 +367,8 @@ static int is_dir(const char *path, struct dirent *entry)
 
 static int local_db_populate(pmdb_t *db)
 {
-	int count = 0;
+	int est_count, count = 0;
+	struct stat buf;
 	struct dirent *ent = NULL;
 	const char *dbpath;
 	DIR *dbdir;
@@ -384,6 +385,11 @@ static int local_db_populate(pmdb_t *db)
 	if(dbdir == NULL) {
 		return(0);
 	}
+	if(fstat(dirfd(dbdir), &buf) != 0) {
+		return(0);
+	}
+	/* subtract the two always-there pointers to get # of children */
+	est_count = (int)buf.st_nlink - 2;
 	while((ent = readdir(dbdir)) != NULL) {
 		const char *name = ent->d_name;
 
diff --git a/lib/libalpm/be_sync.c b/lib/libalpm/be_sync.c
index f7101f54..0c968b45 100644
--- a/lib/libalpm/be_sync.c
+++ b/lib/libalpm/be_sync.c
@@ -145,9 +145,67 @@ int SYMEXPORT alpm_db_update(int force, pmdb_t *db)
 static int sync_db_read(pmdb_t *db, struct archive *archive,
 		struct archive_entry *entry, pmpkg_t *likely_pkg);
 
+/*
+ * This is the data table used to generate the estimating function below.
+ * "Weighted Avg" means averaging the bottom table values; thus each repo, big
+ * or small, will have equal influence.  "Unweighted Avg" means averaging the
+ * sums of the top table columns, thus each package has equal influence.  The
+ * final values are calculated by (surprise) averaging the averages, because
+ * why the hell not.
+ *
+ * Database   Pkgs  tar      bz2     gz      xz
+ * community  2096  5294080  256391  421227  301296
+ * core        180   460800   25257   36850   29356
+ * extra      2606  6635520  294647  470818  339392
+ * multilib    126   327680   16120   23261   18732
+ * testing      76   204800   10902   14348   12100
+ *
+ * Bytes Per Package
+ * community  2096  2525.80  122.32  200.97  143.75
+ * core        180  2560.00  140.32  204.72  163.09
+ * extra      2606  2546.25  113.06  180.67  130.23
+ * multilib    126  2600.63  127.94  184.61  148.67
+ * testing      76  2694.74  143.45  188.79  159.21
+
+ * Weighted Avg     2585.48  129.42  191.95  148.99
+ * Unweighted Avg   2543.39  118.74  190.16  137.93
+ * Average of Avgs  2564.44  124.08  191.06  143.46
+ */
+static int estimate_package_count(struct stat *st, struct archive *archive)
+{
+	unsigned int per_package;
+
+	switch(archive_compression(archive)) {
+		case ARCHIVE_COMPRESSION_NONE:
+			per_package = 2564;
+			break;
+		case ARCHIVE_COMPRESSION_GZIP:
+			per_package = 191;
+			break;
+		case ARCHIVE_COMPRESSION_BZIP2:
+			per_package = 124;
+			break;
+		case ARCHIVE_COMPRESSION_COMPRESS:
+			per_package = 193;
+			break;
+		case ARCHIVE_COMPRESSION_LZMA:
+		case ARCHIVE_COMPRESSION_XZ:
+			per_package = 143;
+			break;
+		case ARCHIVE_COMPRESSION_UU:
+			per_package = 3543;
+			break;
+		default:
+			/* assume it is at least somewhat compressed */
+			per_package = 200;
+	}
+	return((int)(st->st_size / per_package) + 1);
+}
+
 static int sync_db_populate(pmdb_t *db)
 {
-	int count = 0;
+	int est_count, count = 0;
+	struct stat buf;
 	struct archive *archive;
 	struct archive_entry *entry;
 	pmpkg_t *pkg = NULL;
@@ -169,6 +227,10 @@ static int sync_db_populate(pmdb_t *db)
 		archive_read_finish(archive);
 		RET_ERR(PM_ERR_DB_OPEN, 1);
 	}
+	if(lstat(_alpm_db_path(db), &buf) != 0) {
+		RET_ERR(PM_ERR_DB_OPEN, 1);
+	}
+	est_count = estimate_package_count(&buf, archive);
 
 	while(archive_read_next_header(archive, &entry) == ARCHIVE_OK) {
 		const struct stat *st;
-- 
cgit v1.2.3-70-g09d2


From f8fdce6cb0da4d832ffa730e0dacb5544c1f8154 Mon Sep 17 00:00:00 2001
From: Allan McRae <allan@archlinux.org>
Date: Tue, 25 Jan 2011 11:49:34 +1000
Subject: Read pkgcache into hash

Read the package information for sync/local databases into a pmpkghash_t
structure.

Provide a alpm_db_get_pkgcache_list() method that returns the list from
the hash object.  Most usages of alpm_db_get_pkgcache are converted to
this at this stage for ease of implementation.  Review whether these are
better accessing the hash table directly at a later stage.

Signed-off-by: Allan McRae <allan@archlinux.org>
---
 lib/libalpm/alpm.h      |  3 ++-
 lib/libalpm/be_local.c  | 12 ++++++++---
 lib/libalpm/be_sync.c   | 13 ++++++++----
 lib/libalpm/conflict.c  |  4 ++--
 lib/libalpm/db.c        | 55 ++++++++++++++++++++++++++++++++++++-------------
 lib/libalpm/db.h        |  7 +++++--
 lib/libalpm/deps.c      |  8 +++----
 lib/libalpm/package.c   |  2 +-
 lib/libalpm/remove.c    |  6 +++---
 lib/libalpm/sync.c      |  8 +++----
 src/pacman/deptest.c    |  2 +-
 src/pacman/query.c      |  6 +++---
 src/pacman/sync.c       | 10 ++++-----
 src/util/cleanupdelta.c |  2 +-
 src/util/pactree.c      |  4 ++--
 src/util/testdb.c       |  4 ++--
 16 files changed, 94 insertions(+), 52 deletions(-)

diff --git a/lib/libalpm/alpm.h b/lib/libalpm/alpm.h
index f33abf7a..7fec293d 100644
--- a/lib/libalpm/alpm.h
+++ b/lib/libalpm/alpm.h
@@ -187,7 +187,8 @@ int alpm_db_setserver(pmdb_t *db, const char *url);
 int alpm_db_update(int level, pmdb_t *db);
 
 pmpkg_t *alpm_db_get_pkg(pmdb_t *db, const char *name);
-alpm_list_t *alpm_db_get_pkgcache(pmdb_t *db);
+pmpkghash_t *alpm_db_get_pkgcache(pmdb_t *db);
+alpm_list_t *alpm_db_get_pkgcache_list(pmdb_t *db);
 
 pmgrp_t *alpm_db_readgrp(pmdb_t *db, const char *name);
 alpm_list_t *alpm_db_get_grpcache(pmdb_t *db);
diff --git a/lib/libalpm/be_local.c b/lib/libalpm/be_local.c
index b97fca71..12021ac2 100644
--- a/lib/libalpm/be_local.c
+++ b/lib/libalpm/be_local.c
@@ -390,6 +390,10 @@ static int local_db_populate(pmdb_t *db)
 	}
 	/* subtract the two always-there pointers to get # of children */
 	est_count = (int)buf.st_nlink - 2;
+
+	/* initialize hash at 50% full */
+	db->pkgcache = _alpm_pkghash_create(est_count * 2);
+
 	while((ent = readdir(dbdir)) != NULL) {
 		const char *name = ent->d_name;
 
@@ -416,7 +420,7 @@ static int local_db_populate(pmdb_t *db)
 		}
 
 		/* duplicated database entries are not allowed */
-		if(_alpm_pkg_find(db->pkgcache, pkg->name)) {
+		if(_alpm_pkghash_find(db->pkgcache, pkg->name)) {
 			_alpm_log(PM_LOG_ERROR, _("duplicated database entry '%s'\n"), pkg->name);
 			_alpm_pkg_free(pkg);
 			continue;
@@ -436,12 +440,14 @@ static int local_db_populate(pmdb_t *db)
 		/* add to the collection */
 		_alpm_log(PM_LOG_FUNCTION, "adding '%s' to package cache for db '%s'\n",
 				pkg->name, db->treename);
-		db->pkgcache = alpm_list_add(db->pkgcache, pkg);
+		db->pkgcache = _alpm_pkghash_add(db->pkgcache, pkg);
 		count++;
 	}
 
 	closedir(dbdir);
-	db->pkgcache = alpm_list_msort(db->pkgcache, (size_t)count, _alpm_pkg_cmp);
+	if(count > 0) {
+		db->pkgcache->list = alpm_list_msort(db->pkgcache->list, (size_t)count, _alpm_pkg_cmp);
+	}
 	return(count);
 }
 
diff --git a/lib/libalpm/be_sync.c b/lib/libalpm/be_sync.c
index 0c968b45..2c70e2c5 100644
--- a/lib/libalpm/be_sync.c
+++ b/lib/libalpm/be_sync.c
@@ -232,6 +232,9 @@ static int sync_db_populate(pmdb_t *db)
 	}
 	est_count = estimate_package_count(&buf, archive);
 
+	/* initialize hash at 50% full */
+	db->pkgcache = _alpm_pkghash_create(est_count * 2);
+
 	while(archive_read_next_header(archive, &entry) == ARCHIVE_OK) {
 		const struct stat *st;
 
@@ -256,7 +259,7 @@ static int sync_db_populate(pmdb_t *db)
 			}
 
 			/* duplicated database entries are not allowed */
-			if(_alpm_pkg_find(db->pkgcache, pkg->name)) {
+			if(_alpm_pkghash_find(db->pkgcache, pkg->name)) {
 				_alpm_log(PM_LOG_ERROR, _("duplicated database entry '%s'\n"), pkg->name);
 				_alpm_pkg_free(pkg);
 				continue;
@@ -269,7 +272,7 @@ static int sync_db_populate(pmdb_t *db)
 			/* add to the collection */
 			_alpm_log(PM_LOG_FUNCTION, "adding '%s' to package cache for db '%s'\n",
 					pkg->name, db->treename);
-			db->pkgcache = alpm_list_add(db->pkgcache, pkg);
+			db->pkgcache = _alpm_pkghash_add(db->pkgcache, pkg);
 			count++;
 		} else {
 			/* we have desc, depends or deltas - parse it */
@@ -277,7 +280,9 @@ static int sync_db_populate(pmdb_t *db)
 		}
 	}
 
-	db->pkgcache = alpm_list_msort(db->pkgcache, (size_t)count, _alpm_pkg_cmp);
+	if(count > 0) {
+		db->pkgcache->list = alpm_list_msort(db->pkgcache->list, (size_t)count, _alpm_pkg_cmp);
+	}
 	archive_read_finish(archive);
 
 	return(count);
@@ -343,7 +348,7 @@ static int sync_db_read(pmdb_t *db, struct archive *archive,
 	if(likely_pkg && strcmp(likely_pkg->name, pkgname) == 0) {
 		pkg = likely_pkg;
 	} else {
-		pkg = _alpm_pkg_find(db->pkgcache, pkgname);
+		pkg = _alpm_pkghash_find(db->pkgcache, pkgname);
 	}
 	if(pkg == NULL) {
 		_alpm_log(PM_LOG_DEBUG, "package %s not found in %s sync database",
diff --git a/lib/libalpm/conflict.c b/lib/libalpm/conflict.c
index fc25e7d3..17e728a5 100644
--- a/lib/libalpm/conflict.c
+++ b/lib/libalpm/conflict.c
@@ -207,8 +207,8 @@ alpm_list_t *_alpm_outerconflicts(pmdb_t *db, alpm_list_t *packages)
 		return(NULL);
 	}
 
-	alpm_list_t *dblist = alpm_list_diff(_alpm_db_get_pkgcache(db), packages,
-			_alpm_pkg_cmp);
+	alpm_list_t *dblist = alpm_list_diff(_alpm_db_get_pkgcache_list(db),
+			packages, _alpm_pkg_cmp);
 
 	/* two checks to be done here for conflicts */
 	_alpm_log(PM_LOG_DEBUG, "check targets vs db\n");
diff --git a/lib/libalpm/db.c b/lib/libalpm/db.c
index c80dcbb8..c0c2f0ca 100644
--- a/lib/libalpm/db.c
+++ b/lib/libalpm/db.c
@@ -249,9 +249,9 @@ pmpkg_t SYMEXPORT *alpm_db_get_pkg(pmdb_t *db, const char *name)
 
 /** Get the package cache of a package database
  * @param db pointer to the package database to get the package from
- * @return the list of packages on success, NULL on error
+ * @return the hash of packages on success, NULL on error
  */
-alpm_list_t SYMEXPORT *alpm_db_get_pkgcache(pmdb_t *db)
+pmpkghash_t SYMEXPORT *alpm_db_get_pkgcache(pmdb_t *db)
 {
 	ALPM_LOG_FUNC;
 
@@ -262,6 +262,21 @@ alpm_list_t SYMEXPORT *alpm_db_get_pkgcache(pmdb_t *db)
 	return(_alpm_db_get_pkgcache(db));
 }
 
+/** Get the package cache of a package database
+ * @param db pointer to the package database to get the package from
+ * @return the list of packages on success, NULL on error
+ */
+alpm_list_t SYMEXPORT *alpm_db_get_pkgcache_list(pmdb_t *db)
+{
+	ALPM_LOG_FUNC;
+
+	/* Sanity checks */
+	ASSERT(handle != NULL, return(NULL));
+	ASSERT(db != NULL, return(NULL));
+
+	return(_alpm_db_get_pkgcache_list(db));
+}
+
 /** Get a group entry from a package database
  * @param db pointer to the package database to get the group from
  * @param name of the group
@@ -417,7 +432,7 @@ alpm_list_t *_alpm_db_search(pmdb_t *db, const alpm_list_t *needles)
 	const alpm_list_t *i, *j, *k;
 	alpm_list_t *ret = NULL;
 	/* copy the pkgcache- we will free the list var after each needle */
-	alpm_list_t *list = alpm_list_copy(_alpm_db_get_pkgcache(db));
+	alpm_list_t *list = alpm_list_copy(_alpm_db_get_pkgcache_list(db));
 
 	ALPM_LOG_FUNC;
 
@@ -523,14 +538,15 @@ void _alpm_db_free_pkgcache(pmdb_t *db)
 	_alpm_log(PM_LOG_DEBUG, "freeing package cache for repository '%s'\n",
 	                        db->treename);
 
-	alpm_list_free_inner(db->pkgcache, (alpm_list_fn_free)_alpm_pkg_free);
-	alpm_list_free(db->pkgcache);
+	alpm_list_free_inner(_alpm_db_get_pkgcache_list(db),
+				(alpm_list_fn_free)_alpm_pkg_free);
+	_alpm_pkghash_free(db->pkgcache);
 	db->pkgcache_loaded = 0;
 
 	_alpm_db_free_grpcache(db);
 }
 
-alpm_list_t *_alpm_db_get_pkgcache(pmdb_t *db)
+pmpkghash_t *_alpm_db_get_pkgcache(pmdb_t *db)
 {
 	ALPM_LOG_FUNC;
 
@@ -550,6 +566,19 @@ alpm_list_t *_alpm_db_get_pkgcache(pmdb_t *db)
 	return(db->pkgcache);
 }
 
+alpm_list_t *_alpm_db_get_pkgcache_list(pmdb_t *db)
+{
+	ALPM_LOG_FUNC;
+
+	pmpkghash_t *hash = _alpm_db_get_pkgcache(db);
+
+	if(hash == NULL) {
+		return(NULL);
+	}
+
+	return(hash->list);
+}
+
 /* "duplicate" pkg then add it to pkgcache */
 int _alpm_db_add_pkgincache(pmdb_t *db, pmpkg_t *pkg)
 {
@@ -568,7 +597,7 @@ int _alpm_db_add_pkgincache(pmdb_t *db, pmpkg_t *pkg)
 
 	_alpm_log(PM_LOG_DEBUG, "adding entry '%s' in '%s' cache\n",
 						alpm_pkg_get_name(newpkg), db->treename);
-	db->pkgcache = alpm_list_add_sorted(db->pkgcache, newpkg, _alpm_pkg_cmp);
+	db->pkgcache = _alpm_pkghash_add_sorted(db->pkgcache, newpkg);
 
 	_alpm_db_free_grpcache(db);
 
@@ -577,8 +606,7 @@ int _alpm_db_add_pkgincache(pmdb_t *db, pmpkg_t *pkg)
 
 int _alpm_db_remove_pkgfromcache(pmdb_t *db, pmpkg_t *pkg)
 {
-	void *vdata;
-	pmpkg_t *data;
+	pmpkg_t *data = NULL;
 
 	ALPM_LOG_FUNC;
 
@@ -589,8 +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_list_remove(db->pkgcache, pkg, _alpm_pkg_cmp, &vdata);
-	data = vdata;
+	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",
@@ -613,14 +640,14 @@ pmpkg_t *_alpm_db_get_pkgfromcache(pmdb_t *db, const char *target)
 		return(NULL);
 	}
 
-	alpm_list_t *pkgcache = _alpm_db_get_pkgcache(db);
+	pmpkghash_t *pkgcache = _alpm_db_get_pkgcache(db);
 	if(!pkgcache) {
 		_alpm_log(PM_LOG_DEBUG, "warning: failed to get '%s' from NULL pkgcache\n",
 				target);
 		return(NULL);
 	}
 
-	return(_alpm_pkg_find(pkgcache, target));
+	return(_alpm_pkghash_find(pkgcache, target));
 }
 
 /* Returns a new group cache from db.
@@ -638,7 +665,7 @@ int _alpm_db_load_grpcache(pmdb_t *db)
 	_alpm_log(PM_LOG_DEBUG, "loading group cache for repository '%s'\n",
 			db->treename);
 
-	for(lp = _alpm_db_get_pkgcache(db); lp; lp = lp->next) {
+	for(lp = _alpm_db_get_pkgcache_list(db); lp; lp = lp->next) {
 		const alpm_list_t *i;
 		pmpkg_t *pkg = lp->data;
 
diff --git a/lib/libalpm/db.h b/lib/libalpm/db.h
index b7fa7ca6..c5b3db69 100644
--- a/lib/libalpm/db.h
+++ b/lib/libalpm/db.h
@@ -23,6 +23,8 @@
 #define _ALPM_DB_H
 
 #include "alpm.h"
+#include "pkghash.h"
+
 #include <time.h>
 
 /* libarchive */
@@ -54,7 +56,7 @@ struct __pmdb_t {
 	int grpcache_loaded;
 	/* also indicates whether we are RO or RW */
 	int is_local;
-	alpm_list_t *pkgcache;
+	pmpkghash_t *pkgcache;
 	alpm_list_t *grpcache;
 	alpm_list_t *servers;
 
@@ -84,7 +86,8 @@ int _alpm_db_load_pkgcache(pmdb_t *db);
 void _alpm_db_free_pkgcache(pmdb_t *db);
 int _alpm_db_add_pkgincache(pmdb_t *db, pmpkg_t *pkg);
 int _alpm_db_remove_pkgfromcache(pmdb_t *db, pmpkg_t *pkg);
-alpm_list_t *_alpm_db_get_pkgcache(pmdb_t *db);
+pmpkghash_t *_alpm_db_get_pkgcache(pmdb_t *db);
+alpm_list_t *_alpm_db_get_pkgcache_list(pmdb_t *db);
 int _alpm_db_ensure_pkgcache(pmdb_t *db, pmdbinfrq_t infolevel);
 pmpkg_t *_alpm_db_get_pkgfromcache(pmdb_t *db, const char *target);
 /* groups */
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index b667b0e8..dca8877e 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -475,7 +475,7 @@ static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets,
 	 * if checkdeps detected it would break something */
 
 	/* see if other packages need it */
-	for(i = _alpm_db_get_pkgcache(db); i; i = i->next) {
+	for(i = _alpm_db_get_pkgcache_list(db); i; i = i->next) {
 		pmpkg_t *lpkg = i->data;
 		if(_alpm_dep_edge(lpkg, pkg) && !_alpm_pkg_find(targets, lpkg->name)) {
 			return(0);
@@ -508,7 +508,7 @@ void _alpm_recursedeps(pmdb_t *db, alpm_list_t *targs, int include_explicit)
 
 	for(i = targs; i; i = i->next) {
 		pmpkg_t *pkg = i->data;
-		for(j = _alpm_db_get_pkgcache(db); j; j = j->next) {
+		for(j = _alpm_db_get_pkgcache_list(db); j; j = j->next) {
 			pmpkg_t *deppkg = j->data;
 			if(_alpm_dep_edge(pkg, deppkg)
 					&& can_remove_package(db, deppkg, targs, include_explicit)) {
@@ -586,7 +586,7 @@ pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs,
 	}
 	/* 2. satisfiers (skip literals here) */
 	for(i = dbs; i; i = i->next) {
-		for(j = _alpm_db_get_pkgcache(i->data); j; j = j->next) {
+		for(j = _alpm_db_get_pkgcache_list(i->data); j; j = j->next) {
 			pmpkg_t *pkg = j->data;
 			if(_alpm_depcmp_tolerant(pkg, dep) && strcmp(pkg->name, dep->name) != 0 &&
 			             !_alpm_pkg_find(excluding, pkg->name)) {
@@ -614,7 +614,7 @@ pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs,
 	/* first check if one provider is already installed locally */
 	for(i = providers; i; i = i->next) {
 		pmpkg_t *pkg = i->data;
-		if (_alpm_pkg_find(_alpm_db_get_pkgcache(handle->db_local), pkg->name)) {
+		if (_alpm_pkghash_find(_alpm_db_get_pkgcache(handle->db_local), pkg->name)) {
 			alpm_list_free(providers);
 			return(pkg);
 		}
diff --git a/lib/libalpm/package.c b/lib/libalpm/package.c
index d4b3b9c0..0a1102c8 100644
--- a/lib/libalpm/package.c
+++ b/lib/libalpm/package.c
@@ -338,7 +338,7 @@ int SYMEXPORT alpm_pkg_has_scriptlet(pmpkg_t *pkg)
 static void find_requiredby(pmpkg_t *pkg, pmdb_t *db, alpm_list_t **reqs)
 {
 	const alpm_list_t *i;
-	for(i = _alpm_db_get_pkgcache(db); i; i = i->next) {
+	for(i = _alpm_db_get_pkgcache_list(db); i; i = i->next) {
 		if(!i->data) {
 			continue;
 		}
diff --git a/lib/libalpm/remove.c b/lib/libalpm/remove.c
index 5def92a6..823795be 100644
--- a/lib/libalpm/remove.c
+++ b/lib/libalpm/remove.c
@@ -95,7 +95,7 @@ static void remove_prepare_cascade(pmtrans_t *trans, pmdb_t *db,
 		}
 		alpm_list_free_inner(lp, (alpm_list_fn_free)_alpm_depmiss_free);
 		alpm_list_free(lp);
-		lp = alpm_checkdeps(_alpm_db_get_pkgcache(db), 1, trans->remove, NULL);
+		lp = alpm_checkdeps(_alpm_db_get_pkgcache_list(db), 1, trans->remove, NULL);
 	}
 }
 
@@ -125,7 +125,7 @@ static void remove_prepare_keep_needed(pmtrans_t *trans, pmdb_t *db,
 		}
 		alpm_list_free_inner(lp, (alpm_list_fn_free)_alpm_depmiss_free);
 		alpm_list_free(lp);
-		lp = alpm_checkdeps(_alpm_db_get_pkgcache(db), 1, trans->remove, NULL);
+		lp = alpm_checkdeps(_alpm_db_get_pkgcache_list(db), 1, trans->remove, NULL);
 	}
 }
 
@@ -147,7 +147,7 @@ int _alpm_remove_prepare(pmtrans_t *trans, pmdb_t *db, alpm_list_t **data)
 		EVENT(trans, PM_TRANS_EVT_CHECKDEPS_START, NULL, NULL);
 
 		_alpm_log(PM_LOG_DEBUG, "looking for unsatisfied dependencies\n");
-		lp = alpm_checkdeps(_alpm_db_get_pkgcache(db), 1, trans->remove, NULL);
+		lp = alpm_checkdeps(_alpm_db_get_pkgcache_list(db), 1, trans->remove, NULL);
 		if(lp != NULL) {
 
 			if(trans->flags & PM_TRANS_FLAG_CASCADE) {
diff --git a/lib/libalpm/sync.c b/lib/libalpm/sync.c
index 9f5bec3b..859b8c94 100644
--- a/lib/libalpm/sync.c
+++ b/lib/libalpm/sync.c
@@ -102,7 +102,7 @@ int SYMEXPORT alpm_sync_sysupgrade(int enable_downgrade)
 	ASSERT(trans->state == STATE_INITIALIZED, RET_ERR(PM_ERR_TRANS_NOT_INITIALIZED, -1));
 
 	_alpm_log(PM_LOG_DEBUG, "checking for package upgrades\n");
-	for(i = _alpm_db_get_pkgcache(db_local); i; i = i->next) {
+	for(i = _alpm_db_get_pkgcache_list(db_local); i; i = i->next) {
 		pmpkg_t *lpkg = i->data;
 
 		if(_alpm_pkg_find(trans->add, lpkg->name)) {
@@ -149,7 +149,7 @@ int SYMEXPORT alpm_sync_sysupgrade(int enable_downgrade)
 				break; /* jump to next local package */
 			} else { /* 2. search for replacers in sdb */
 				int found = 0;
-				for(k = _alpm_db_get_pkgcache(sdb); k; k = k->next) {
+				for(k = _alpm_db_get_pkgcache_list(sdb); k; k = k->next) {
 					spkg = k->data;
 					if(alpm_list_find_str(alpm_pkg_get_replaces(spkg), lpkg->name)) {
 						found = 1;
@@ -331,7 +331,7 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync
 		}
 
 		/* Compute the fake local database for resolvedeps (partial fix for the phonon/qt issue) */
-		alpm_list_t *localpkgs = alpm_list_diff(_alpm_db_get_pkgcache(db_local), trans->add, _alpm_pkg_cmp);
+		alpm_list_t *localpkgs = alpm_list_diff(_alpm_db_get_pkgcache_list(db_local), trans->add, _alpm_pkg_cmp);
 
 		/* Resolve packages in the transaction one at a time, in addtion
 		   building up a list of packages which could not be resolved. */
@@ -518,7 +518,7 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync
 
 	if(!(trans->flags & PM_TRANS_FLAG_NODEPS)) {
 		_alpm_log(PM_LOG_DEBUG, "checking dependencies\n");
-		deps = alpm_checkdeps(_alpm_db_get_pkgcache(db_local), 1, trans->remove, trans->add);
+		deps = alpm_checkdeps(_alpm_db_get_pkgcache_list(db_local), 1, trans->remove, trans->add);
 		if(deps) {
 			pm_errno = PM_ERR_UNSATISFIED_DEPS;
 			ret = -1;
diff --git a/src/pacman/deptest.c b/src/pacman/deptest.c
index 8895b487..0d265c70 100644
--- a/src/pacman/deptest.c
+++ b/src/pacman/deptest.c
@@ -41,7 +41,7 @@ int pacman_deptest(alpm_list_t *targets)
 	for(i = targets; i; i = alpm_list_next(i)) {
 		char *target = alpm_list_getdata(i);
 
-		if(!alpm_find_satisfier(alpm_db_get_pkgcache(localdb), target)) {
+		if(!alpm_find_satisfier(alpm_db_get_pkgcache_list(localdb), target)) {
 			deps = alpm_list_add(deps, target);
 		}
 	}
diff --git a/src/pacman/query.c b/src/pacman/query.c
index c79133d1..734875be 100644
--- a/src/pacman/query.c
+++ b/src/pacman/query.c
@@ -170,7 +170,7 @@ static int query_fileowner(alpm_list_t *targets)
 		}
 		free(dname);
 
-		for(i = alpm_db_get_pkgcache(db_local); i && !found; i = alpm_list_next(i)) {
+		for(i = alpm_db_get_pkgcache_list(db_local); i && !found; i = alpm_list_next(i)) {
 			alpm_list_t *j;
 			pmpkg_t *info = alpm_list_getdata(i);
 
@@ -228,7 +228,7 @@ static int query_search(alpm_list_t *targets)
 		searchlist = alpm_db_search(db_local, targets);
 		freelist = 1;
 	} else {
-		searchlist = alpm_db_get_pkgcache(db_local);
+		searchlist = alpm_db_get_pkgcache_list(db_local);
 		freelist = 0;
 	}
 	if(searchlist == NULL) {
@@ -511,7 +511,7 @@ int pacman_query(alpm_list_t *targets)
 			return(1);
 		}
 
-		for(i = alpm_db_get_pkgcache(db_local); i; i = alpm_list_next(i)) {
+		for(i = alpm_db_get_pkgcache_list(db_local); i; i = alpm_list_next(i)) {
 			pkg = alpm_list_getdata(i);
 			if(filter(pkg)) {
 				int value = display(pkg);
diff --git a/src/pacman/sync.c b/src/pacman/sync.c
index 26f6f824..7af1667a 100644
--- a/src/pacman/sync.c
+++ b/src/pacman/sync.c
@@ -328,7 +328,7 @@ static int sync_search(alpm_list_t *syncs, alpm_list_t *targets)
 			ret = alpm_db_search(db, targets);
 			freelist = 1;
 		} else {
-			ret = alpm_db_get_pkgcache(db);
+			ret = alpm_db_get_pkgcache_list(db);
 			freelist = 0;
 		}
 		if(ret == NULL) {
@@ -469,7 +469,7 @@ static int sync_info(alpm_list_t *syncs, alpm_list_t *targets)
 					return(1);
 				}
 
-				for(k = alpm_db_get_pkgcache(db); k; k = alpm_list_next(k)) {
+				for(k = alpm_db_get_pkgcache_list(db); k; k = alpm_list_next(k)) {
 					pmpkg_t *pkg = alpm_list_getdata(k);
 
 					if(strcmp(alpm_pkg_get_name(pkg), pkgstr) == 0) {
@@ -490,7 +490,7 @@ static int sync_info(alpm_list_t *syncs, alpm_list_t *targets)
 				for(j = syncs; j; j = alpm_list_next(j)) {
 					pmdb_t *db = alpm_list_getdata(j);
 
-					for(k = alpm_db_get_pkgcache(db); k; k = alpm_list_next(k)) {
+					for(k = alpm_db_get_pkgcache_list(db); k; k = alpm_list_next(k)) {
 						pmpkg_t *pkg = alpm_list_getdata(k);
 
 						if(strcmp(alpm_pkg_get_name(pkg), pkgstr) == 0) {
@@ -511,7 +511,7 @@ static int sync_info(alpm_list_t *syncs, alpm_list_t *targets)
 		for(i = syncs; i; i = alpm_list_next(i)) {
 			pmdb_t *db = alpm_list_getdata(i);
 
-			for(j = alpm_db_get_pkgcache(db); j; j = alpm_list_next(j)) {
+			for(j = alpm_db_get_pkgcache_list(db); j; j = alpm_list_next(j)) {
 				dump_pkg_sync(alpm_list_getdata(j), alpm_db_get_name(db), config->op_s_info);
 			}
 		}
@@ -555,7 +555,7 @@ static int sync_list(alpm_list_t *syncs, alpm_list_t *targets)
 	for(i = ls; i; i = alpm_list_next(i)) {
 		pmdb_t *db = alpm_list_getdata(i);
 
-		for(j = alpm_db_get_pkgcache(db); j; j = alpm_list_next(j)) {
+		for(j = alpm_db_get_pkgcache_list(db); j; j = alpm_list_next(j)) {
 			pmpkg_t *pkg = alpm_list_getdata(j);
 
 			if (!config->quiet) {
diff --git a/src/util/cleanupdelta.c b/src/util/cleanupdelta.c
index 4403e9fa..36a4e072 100644
--- a/src/util/cleanupdelta.c
+++ b/src/util/cleanupdelta.c
@@ -79,7 +79,7 @@ static void checkdbs(char *dbpath, alpm_list_t *dbnames) {
 					alpm_strerrorlast());
 			return;
 		}
-		checkpkgs(alpm_db_get_pkgcache(db));
+		checkpkgs(alpm_db_get_pkgcache_list(db));
 	}
 
 }
diff --git a/src/util/pactree.c b/src/util/pactree.c
index 6a10006f..947ed61c 100644
--- a/src/util/pactree.c
+++ b/src/util/pactree.c
@@ -303,7 +303,7 @@ static void walk_deps(pmpkg_t *pkg, int depth)
 
 	for(i = alpm_pkg_get_depends(pkg); i; i = alpm_list_next(i)) {
 		pmdepend_t *depend = alpm_list_getdata(i);
-		pmpkg_t *provider = alpm_find_satisfier(alpm_db_get_pkgcache(db_local),
+		pmpkg_t *provider = alpm_find_satisfier(alpm_db_get_pkgcache_list(db_local),
 				alpm_dep_get_name(depend));
 
 		if(provider) {
@@ -347,7 +347,7 @@ int main(int argc, char *argv[])
 	/* we only care about the first non option arg for walking */
 	target_name = argv[optind];
 
-	pkg = alpm_find_satisfier(alpm_db_get_pkgcache(db_local), target_name);
+	pkg = alpm_find_satisfier(alpm_db_get_pkgcache_list(db_local), target_name);
 	if(!pkg) {
 		fprintf(stderr, "error: package '%s' not found\n", target_name);
 		ret = 1;
diff --git a/src/util/testdb.c b/src/util/testdb.c
index 461cf23a..124a66dd 100644
--- a/src/util/testdb.c
+++ b/src/util/testdb.c
@@ -142,7 +142,7 @@ static int check_localdb(void) {
 				alpm_strerrorlast());
 		cleanup(EXIT_FAILURE);
 	}
-	pkglist = alpm_db_get_pkgcache(db);
+	pkglist = alpm_db_get_pkgcache_list(db);
 	ret += checkdeps(pkglist);
 	ret += checkconflicts(pkglist);
 	return(ret);
@@ -162,7 +162,7 @@ static int check_syncdbs(alpm_list_t *dbnames) {
 			ret = 1;
 			goto cleanup;
 		}
-		pkglist = alpm_db_get_pkgcache(db);
+		pkglist = alpm_db_get_pkgcache_list(db);
 		syncpkglist = alpm_list_join(syncpkglist, alpm_list_copy(pkglist));
 	}
 	ret += checkdeps(syncpkglist);
-- 
cgit v1.2.3-70-g09d2


From ce5471511257ada996bfcb6ea4236cd89c0d6890 Mon Sep 17 00:00:00 2001
From: Dan McGee <dan@archlinux.org>
Date: Fri, 28 Jan 2011 12:03:36 -0600
Subject: Implement a quick and dirty rehash function

This allows us to get through the rehash required by smoke001 and pass
all pactests. It is by no means the best or most efficient
implementation but it does do the job.

Signed-off-by: Dan McGee <dan@archlinux.org>
---
 lib/libalpm/pkghash.c | 27 ++++++++++++++++-----------
 1 file changed, 16 insertions(+), 11 deletions(-)

diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
index 3ed6453f..f2497070 100644
--- a/lib/libalpm/pkghash.c
+++ b/lib/libalpm/pkghash.c
@@ -77,9 +77,9 @@ pmpkghash_t *_alpm_pkghash_create(size_t size)
 /* Expand the hash table size to the next increment and rebin the entries */
 static pmpkghash_t *rehash(pmpkghash_t *oldhash)
 {
-	//pmpkghash_t *newhash;
-
-	/* TODO - calculate size of newhash */
+	pmpkghash_t *newhash;
+	alpm_list_t *ptr;
+	size_t newsize;
 	/* Hash tables will need resized in two cases:
 	 *  - adding packages to the local database
 	 *  - poor estimation of the number of packages in sync database
@@ -89,17 +89,22 @@ static pmpkghash_t *rehash(pmpkghash_t *oldhash)
 	 * larger database sizes, this increase is reduced to avoid excess
 	 * memory allocation as both scenarios requiring a rehash should not
 	 * require a table size increase that large. */
+	if(oldhash->buckets < 500) {
+		newsize = oldhash->buckets * 2;
+	} else if(oldhash->buckets < 3500) {
+		newsize = oldhash->buckets * 3 / 2;
+	} else {
+		newsize = oldhash->buckets * 4 / 3;
+	}
 
-	//newhash = _alpm_pkghash_create(oldhash->buckets);
-
-	/* TODO - rebin entries */
-
-	//_alpm_pkghash_free(oldhash);
+	newhash = _alpm_pkghash_create(newsize);
+	for(ptr = oldhash->list; ptr != NULL; ptr = ptr->next) {
+		newhash = _alpm_pkghash_add(newhash, ptr->data);
+	}
 
-	//return newhash;
+	_alpm_pkghash_free(oldhash);
 
-	printf("rehash needed!!!\n");
-	return(oldhash);
+	return(newhash);
 }
 
 pmpkghash_t *_alpm_pkghash_add(pmpkghash_t *hash, pmpkg_t *pkg)
-- 
cgit v1.2.3-70-g09d2


From 021085624ea94a7116c60552e5c153de6cb5f057 Mon Sep 17 00:00:00 2001
From: Dan McGee <dan@archlinux.org>
Date: Fri, 28 Jan 2011 12:04:27 -0600
Subject: Change default sync hash table sizing to 66% full

Since the sync database never changes size once we initialize it, we
allow it to be filled a bit more. This reduces the overall memory
footprint needed by the hash table.

Signed-off-by: Dan McGee <dan@archlinux.org>
---
 lib/libalpm/be_sync.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/libalpm/be_sync.c b/lib/libalpm/be_sync.c
index 2c70e2c5..4ad045c2 100644
--- a/lib/libalpm/be_sync.c
+++ b/lib/libalpm/be_sync.c
@@ -232,8 +232,8 @@ static int sync_db_populate(pmdb_t *db)
 	}
 	est_count = estimate_package_count(&buf, archive);
 
-	/* initialize hash at 50% full */
-	db->pkgcache = _alpm_pkghash_create(est_count * 2);
+	/* initialize hash at 66% full */
+	db->pkgcache = _alpm_pkghash_create(est_count * 3 / 2);
 
 	while(archive_read_next_header(archive, &entry) == ARCHIVE_OK) {
 		const struct stat *st;
-- 
cgit v1.2.3-70-g09d2


From d843c86b7b7cbf376716817e7c2c55b1f9360a72 Mon Sep 17 00:00:00 2001
From: Allan McRae <allan@archlinux.org>
Date: Sat, 29 Jan 2011 11:39:25 +1000
Subject: Error handling for maximum database size

Check that the requested size of a pkghash is not beyond the maximum
prime.  Also check for successful creation of a new hash before
rehashing.

Signed-off-by: Allan McRae <allan@archlinux.org>
---
 lib/libalpm/pkghash.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
index f2497070..0324465f 100644
--- a/lib/libalpm/pkghash.c
+++ b/lib/libalpm/pkghash.c
@@ -59,6 +59,7 @@ pmpkghash_t *_alpm_pkghash_create(size_t size)
 
 	hash->list = NULL;
 	hash->entries = 0;
+	hash->buckets = 0;
 
 	loopsize = sizeof(prime_list) / sizeof(*prime_list);
 	for(i = 0; i < loopsize; i++) {
@@ -68,6 +69,12 @@ pmpkghash_t *_alpm_pkghash_create(size_t size)
 		}
 	}
 
+	if(hash->buckets < size) {
+		_alpm_log(PM_LOG_ERROR, _("database larger than maximum size"));
+		free(hash);
+		return(NULL);
+	}
+
 	CALLOC(hash->hash_table, hash->buckets, sizeof(alpm_list_t*), \
 				free(hash); RET_ERR(PM_ERR_MEMORY, NULL));
 
@@ -98,6 +105,11 @@ static pmpkghash_t *rehash(pmpkghash_t *oldhash)
 	}
 
 	newhash = _alpm_pkghash_create(newsize);
+	if(newhash == NULL) {
+		/* creation of newhash failed, stick with old one... */
+		return(oldhash);
+	}
+
 	for(ptr = oldhash->list; ptr != NULL; ptr = ptr->next) {
 		newhash = _alpm_pkghash_add(newhash, ptr->data);
 	}
-- 
cgit v1.2.3-70-g09d2


From c9820ec97b417d33dc37eb589f069766f1068ea1 Mon Sep 17 00:00:00 2001
From: Allan McRae <allan@archlinux.org>
Date: Sat, 29 Jan 2011 11:47:31 +1000
Subject: Slightly more efficient rehash size selection

While probably still not optimal in terms of everyday usage in
pacman, this reduces the absolute size increase to "more reasonable"
levels.  For databases greater than 5000 in size, the minimum size
increase is used which is still on the order of a 10% increase.

Signed-off-by: Allan McRae <allan@archlinux.org>
---
 lib/libalpm/pkghash.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
index 0324465f..8f7168d2 100644
--- a/lib/libalpm/pkghash.c
+++ b/lib/libalpm/pkghash.c
@@ -98,10 +98,12 @@ static pmpkghash_t *rehash(pmpkghash_t *oldhash)
 	 * require a table size increase that large. */
 	if(oldhash->buckets < 500) {
 		newsize = oldhash->buckets * 2;
-	} else if(oldhash->buckets < 3500) {
+	} else if(oldhash->buckets < 2000) {
 		newsize = oldhash->buckets * 3 / 2;
-	} else {
+	} else if(oldhash->buckets < 5000) {
 		newsize = oldhash->buckets * 4 / 3;
+	} else {
+		newsize = oldhash->buckets + 1;
 	}
 
 	newhash = _alpm_pkghash_create(newsize);
-- 
cgit v1.2.3-70-g09d2


From 93207863493b54e794098b4ee5987d59c8c4b14b Mon Sep 17 00:00:00 2001
From: Allan McRae <allan@archlinux.org>
Date: Sat, 29 Jan 2011 22:50:55 +1000
Subject: Rehash efficiently

Rehash without recreating the hash table list or reallocating the
memory for holding the list nodes.

Signed-off-by: Allan McRae <allan@archlinux.org>
---
 lib/libalpm/pkghash.c | 24 +++++++++++++++++++++---
 1 file changed, 21 insertions(+), 3 deletions(-)

diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
index 8f7168d2..44a03ab5 100644
--- a/lib/libalpm/pkghash.c
+++ b/lib/libalpm/pkghash.c
@@ -86,7 +86,8 @@ static pmpkghash_t *rehash(pmpkghash_t *oldhash)
 {
 	pmpkghash_t *newhash;
 	alpm_list_t *ptr;
-	size_t newsize;
+	size_t newsize, position, i;
+
 	/* Hash tables will need resized in two cases:
 	 *  - adding packages to the local database
 	 *  - poor estimation of the number of packages in sync database
@@ -112,10 +113,27 @@ static pmpkghash_t *rehash(pmpkghash_t *oldhash)
 		return(oldhash);
 	}
 
-	for(ptr = oldhash->list; ptr != NULL; ptr = ptr->next) {
-		newhash = _alpm_pkghash_add(newhash, ptr->data);
+	newhash->list = oldhash->list;
+	oldhash->list = NULL;
+
+	for(i = 0; i < oldhash->buckets; i++) {
+		if(oldhash->hash_table[i] != NULL) {
+			pmpkg_t *package = oldhash->hash_table[i]->data;
+
+			position = package->name_hash % newhash->buckets;
+
+			/* collision resolution using open addressing with linear probing */
+			while((ptr = newhash->hash_table[position]) != NULL) {
+				position = (position + 1) % newhash->buckets;
+			}
+
+			newhash->hash_table[position] = oldhash->hash_table[i];
+			oldhash->hash_table[i] = NULL;
+		}
 	}
 
+	newhash->entries = oldhash->entries;
+
 	_alpm_pkghash_free(oldhash);
 
 	return(newhash);
-- 
cgit v1.2.3-70-g09d2


From 11e5e86151f83219b1cedbca31be7530911e25eb Mon Sep 17 00:00:00 2001
From: Allan McRae <allan@archlinux.org>
Date: Sat, 29 Jan 2011 23:24:13 +1000
Subject: Refactor finding position for new hash entry

Signed-off-by: Allan McRae <allan@archlinux.org>
---
 lib/libalpm/pkghash.c | 37 ++++++++++++++++++-------------------
 1 file changed, 18 insertions(+), 19 deletions(-)

diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
index 44a03ab5..bdff78ea 100644
--- a/lib/libalpm/pkghash.c
+++ b/lib/libalpm/pkghash.c
@@ -81,11 +81,25 @@ pmpkghash_t *_alpm_pkghash_create(size_t size)
 	return(hash);
 }
 
+static size_t get_hash_position(unsigned long name_hash, pmpkghash_t *hash)
+{
+	size_t position;
+	alpm_list_t *ptr;
+
+	position = name_hash % hash->buckets;
+
+	/* collision resolution using open addressing with linear probing */
+	while((ptr = hash->hash_table[position]) != NULL) {
+		position = (position + 1) % hash->buckets;
+	}
+
+	return(position);
+}
+
 /* Expand the hash table size to the next increment and rebin the entries */
 static pmpkghash_t *rehash(pmpkghash_t *oldhash)
 {
 	pmpkghash_t *newhash;
-	alpm_list_t *ptr;
 	size_t newsize, position, i;
 
 	/* Hash tables will need resized in two cases:
@@ -120,12 +134,7 @@ static pmpkghash_t *rehash(pmpkghash_t *oldhash)
 		if(oldhash->hash_table[i] != NULL) {
 			pmpkg_t *package = oldhash->hash_table[i]->data;
 
-			position = package->name_hash % newhash->buckets;
-
-			/* collision resolution using open addressing with linear probing */
-			while((ptr = newhash->hash_table[position]) != NULL) {
-				position = (position + 1) % newhash->buckets;
-			}
+			position = get_hash_position(package->name_hash, newhash);
 
 			newhash->hash_table[position] = oldhash->hash_table[i];
 			oldhash->hash_table[i] = NULL;
@@ -152,12 +161,7 @@ pmpkghash_t *_alpm_pkghash_add(pmpkghash_t *hash, pmpkg_t *pkg)
 		hash = rehash(hash);
 	}
 
-	position = pkg->name_hash % hash->buckets;
-
-	/* collision resolution using open addressing with linear probing */
-	while((ptr = hash->hash_table[position]) != NULL) {
-		position = (position + 1) % hash->buckets;
-	}
+	position = get_hash_position(pkg->name_hash, hash);
 
 	ptr = calloc(1, sizeof(alpm_list_t));
 	if(ptr == NULL) {
@@ -188,12 +192,7 @@ pmpkghash_t *_alpm_pkghash_add_sorted(pmpkghash_t *hash, pmpkg_t *pkg)
 		hash = rehash(hash);
 	}
 
-	position = pkg->name_hash % hash->buckets;
-
-	/* collision resolution using open addressing with linear probing */
-	while((ptr = hash->hash_table[position]) != NULL) {
-		position = (position + 1) % hash->buckets;
-	}
+	position = get_hash_position(pkg->name_hash, hash);
 
 	ptr = calloc(1, sizeof(alpm_list_t));
 	if(ptr == NULL) {
-- 
cgit v1.2.3-70-g09d2


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

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


From 09e582b4117356f996f6d94ca5e490aebd0a0fd5 Mon Sep 17 00:00:00 2001
From: Dan McGee <dan@archlinux.org>
Date: Wed, 2 Feb 2011 20:46:27 -0600
Subject: Add a new removal smoke test

Hint: this will really stress hash table removal.

Signed-off-by: Dan McGee <dan@archlinux.org>
---
 test/pacman/tests/smoke001.py |  9 ++++-----
 test/pacman/tests/smoke003.py | 19 +++++++++++++++++++
 2 files changed, 23 insertions(+), 5 deletions(-)
 create mode 100644 test/pacman/tests/smoke003.py

diff --git a/test/pacman/tests/smoke001.py b/test/pacman/tests/smoke001.py
index c6636391..16576b75 100644
--- a/test/pacman/tests/smoke001.py
+++ b/test/pacman/tests/smoke001.py
@@ -4,18 +4,17 @@ p = pmpkg("pkg1000")
 
 self.addpkg2db("local", p)
 
-for i in range(1000):
+for i in xrange(1000):
 	p = pmpkg("pkg%03d" % i)
 	p.depends = ["pkg%03d" % (i+1)]
 	p.files = ["usr/share/pkg%03d" % i]
 	self.addpkg(p)
 
-_list = []
-[_list.append(p.filename()) for p in self.localpkgs]
-self.args = "-U %s" % " ".join(_list)
+pkglist = [p.filename() for p in self.localpkgs]
+self.args = "-U %s" % " ".join(pkglist)
 
 self.addrule("PACMAN_RETCODE=0")
-#for i in range(1000):
+#for i in xrange(1000):
 #	self.addrule("PKG_EXIST=pkg%03d" %i)
 # picked 3 random packages to test for, since the loop is too much to handle
 self.addrule("PKG_EXIST=pkg050")
diff --git a/test/pacman/tests/smoke003.py b/test/pacman/tests/smoke003.py
new file mode 100644
index 00000000..c2460fbf
--- /dev/null
+++ b/test/pacman/tests/smoke003.py
@@ -0,0 +1,19 @@
+self.description = "Remove a thousand packages in a single transaction"
+
+for i in xrange(1000):
+	p = pmpkg("pkg%03dname" % i)
+	p.files = ["usr/share/pkg%03d/file" % i]
+	self.addpkg2db("local", p)
+
+pkglist = ["pkg%03dname" % i for i in xrange(100, 1000)]
+self.args = "-R %s" % " ".join(pkglist)
+
+self.addrule("PACMAN_RETCODE=0")
+# picked random packages to test for, since a loop is too much to handle
+self.addrule("PKG_EXIST=pkg000name")
+self.addrule("PKG_EXIST=pkg050name")
+self.addrule("PKG_EXIST=pkg099name")
+self.addrule("!PKG_EXIST=pkg100name")
+self.addrule("!PKG_EXIST=pkg383name")
+self.addrule("!PKG_EXIST=pkg674name")
+self.addrule("!PKG_EXIST=pkg999name")
-- 
cgit v1.2.3-70-g09d2


From 14fd1e63a2ce420c555c6de34a815a8b62a9859b Mon Sep 17 00:00:00 2001
From: Dan McGee <dan@archlinux.org>
Date: Wed, 2 Feb 2011 20:46:28 -0600
Subject: Add new alpm_list_remove_item() function

This takes in the list and a list item, and does the pointer dance necessary
to remove it from the list regardless of whether it is first, last, or
somewhere in the middle. It is useful for callers that already know what
item needs to be removed and have a pointer to it rather than doing a search
by data that the plain alpm_list_remove() does.

Refactor alpm_list_remove() to use this function as well.

Signed-off-by: Dan McGee <dan@archlinux.org>
---
 lib/libalpm/alpm_list.c | 86 ++++++++++++++++++++++++++++++-------------------
 lib/libalpm/alpm_list.h |  1 +
 2 files changed, 54 insertions(+), 33 deletions(-)

diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c
index 3f9525e8..4cab665f 100644
--- a/lib/libalpm/alpm_list.c
+++ b/lib/libalpm/alpm_list.c
@@ -285,6 +285,53 @@ alpm_list_t SYMEXPORT *alpm_list_msort(alpm_list_t *list, size_t n, alpm_list_fn
 	return(list);
 }
 
+/**
+ * @brief Remove an item from the list.
+ * item is not freed; this is the respnsiblity of the caller.
+ *
+ * @param haystack the list to remove the item from
+ * @param item the item to remove from the list
+ *
+ * @return the resultant list
+ */
+alpm_list_t SYMEXPORT *alpm_list_remove_item(alpm_list_t *haystack,
+		alpm_list_t *item)
+{
+	if(haystack == NULL || item == NULL) {
+		return(haystack);
+	}
+
+	if(item == haystack) {
+		/* Special case: removing the head node which has a back reference to
+		 * the tail node */
+		haystack = item->next;
+		if(haystack) {
+			haystack->prev = item->prev;
+		}
+		item->prev = NULL;
+	} else if(item == haystack->prev) {
+		/* Special case: removing the tail node, so we need to fix the back
+		 * reference on the head node. We also know tail != head. */
+		if(item->prev) {
+			/* i->next should always be null */
+			item->prev->next = item->next;
+			haystack->prev = item->prev;
+			item->prev = NULL;
+		}
+	} else {
+		/* Normal case, non-head and non-tail node */
+		if(item->next) {
+			item->next->prev = item->prev;
+		}
+		if(item->prev) {
+			item->prev->next = item->next;
+		}
+	}
+
+	return(haystack);
+}
+
+
 /**
  * @brief Remove an item from the list.
  *
@@ -295,9 +342,10 @@ alpm_list_t SYMEXPORT *alpm_list_msort(alpm_list_t *list, size_t n, alpm_list_fn
  *
  * @return the resultant list
  */
-alpm_list_t SYMEXPORT *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_list_fn_cmp fn, void **data)
+alpm_list_t SYMEXPORT *alpm_list_remove(alpm_list_t *haystack,
+		const void *needle, alpm_list_fn_cmp fn, void **data)
 {
-	alpm_list_t *i = haystack, *tmp = NULL;
+	alpm_list_t *i = haystack;
 
 	if(data) {
 		*data = NULL;
@@ -312,44 +360,16 @@ alpm_list_t SYMEXPORT *alpm_list_remove(alpm_list_t *haystack, const void *needl
 			i = i->next;
 			continue;
 		}
-		tmp = i->next;
 		if(fn(i->data, needle) == 0) {
-			/* we found a matching item */
-			if(i == haystack) {
-				/* Special case: removing the head node which has a back reference to
-				 * the tail node */
-				haystack = i->next;
-				if(haystack) {
-					haystack->prev = i->prev;
-				}
-				i->prev = NULL;
-			} else if(i == haystack->prev) {
-				/* Special case: removing the tail node, so we need to fix the back
-				 * reference on the head node. We also know tail != head. */
-				if(i->prev) {
-					/* i->next should always be null */
-					i->prev->next = i->next;
-					haystack->prev = i->prev;
-					i->prev = NULL;
-				}
-			} else {
-				/* Normal case, non-head and non-tail node */
-				if(i->next) {
-					i->next->prev = i->prev;
-				}
-				if(i->prev) {
-					i->prev->next = i->next;
-				}
-			}
+			haystack = alpm_list_remove_item(haystack, i);
 
 			if(data) {
 				*data = i->data;
 			}
-			i->data = NULL;
 			free(i);
-			i = NULL;
+			break;
 		} else {
-			i = tmp;
+			i = i->next;
 		}
 	}
 
diff --git a/lib/libalpm/alpm_list.h b/lib/libalpm/alpm_list.h
index ee85a5dd..1f6393a6 100644
--- a/lib/libalpm/alpm_list.h
+++ b/lib/libalpm/alpm_list.h
@@ -57,6 +57,7 @@ alpm_list_t *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_list_fn_cm
 alpm_list_t *alpm_list_join(alpm_list_t *first, alpm_list_t *second);
 alpm_list_t *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_fn_cmp fn);
 alpm_list_t *alpm_list_msort(alpm_list_t *list, size_t n, alpm_list_fn_cmp fn);
+alpm_list_t *alpm_list_remove_item(alpm_list_t *haystack, alpm_list_t *item);
 alpm_list_t *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_list_fn_cmp fn, void **data);
 alpm_list_t *alpm_list_remove_str(alpm_list_t *haystack, const char *needle, char **data);
 alpm_list_t *alpm_list_remove_dupes(const alpm_list_t *list);
-- 
cgit v1.2.3-70-g09d2


From 1f145bcd1a4fb22d4cb548a3be64898f60820695 Mon Sep 17 00:00:00 2001
From: Dan McGee <dan@archlinux.org>
Date: Wed, 2 Feb 2011 20:46:29 -0600
Subject: Use alpm_list_remove_item in pkghash_remove

Removes the code that was duplicated and has now been refactored into a
separate method.

Signed-off-by: Dan McGee <dan@archlinux.org>
---
 lib/libalpm/pkghash.c | 35 ++++-------------------------------
 1 file changed, 4 insertions(+), 31 deletions(-)

diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
index 14056e37..3d420e1f 100644
--- a/lib/libalpm/pkghash.c
+++ b/lib/libalpm/pkghash.c
@@ -219,7 +219,8 @@ 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;
@@ -239,36 +240,8 @@ pmpkghash_t *_alpm_pkghash_remove(pmpkghash_t *hash, pmpkg_t *pkg, pmpkg_t **dat
 		if(info->name_hash == pkg->name_hash &&
 					strcmp(info->name, pkg->name) == 0) {
 
-			/* remove from list */
-			/* TODO - refactor with alpm_list_remove */
-			if(i == hash->list) {
-				/* Special case: removing the head node which has a back reference to
-				 * the tail node */
-				hash->list = i->next;
-				if(hash->list) {
-					hash->list->prev = i->prev;
-				}
-				i->prev = NULL;
-			} else if(i == hash->list->prev) {
-				/* Special case: removing the tail node, so we need to fix the back
-				 * reference on the head node. We also know tail != head. */
-				if(i->prev) {
-					/* i->next should always be null */
-					i->prev->next = i->next;
-					hash->list->prev = i->prev;
-					i->prev = NULL;
-				}
-			} else {
-				/* Normal case, non-head and non-tail node */
-				if(i->next) {
-					i->next->prev = i->prev;
-				}
-				if(i->prev) {
-					i->prev->next = i->next;
-				}
-			}
-
-			/* remove from hash */
+			/* remove from list and hash */
+			hash->list = alpm_list_remove_item(hash->list, i);
 			if(data) {
 				*data = info;
 			}
-- 
cgit v1.2.3-70-g09d2


From 6b0d4674bb132b2583920211cc798f3db77ec392 Mon Sep 17 00:00:00 2001
From: Dan McGee <dan@archlinux.org>
Date: Thu, 3 Feb 2011 10:55:26 -0600
Subject: 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>
---
 lib/libalpm/pkghash.c | 62 +++++++++++++++++++++++++++++++++++----------------
 1 file 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);
-- 
cgit v1.2.3-70-g09d2