Merge remote-tracking branch 'allan/hash'

15 files changed, 610 insertions, 73 deletions

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..7fec293d 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
@@ -186,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/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
@@ -287,6 +287,53 @@ alpm_list_t SYMEXPORT *alpm_list_msort(alpm_list_t *list, size_t n, alpm_list_fn
 
 /**
  * @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.
  *
  * @param haystack the list to remove the item from
  * @param needle   the data member of the item we're removing
@@ -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);
diff --git a/lib/libalpm/be_local.c b/lib/libalpm/be_local.c
index c7110faf..12021ac2 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,15 @@ 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;
+
+	/* initialize hash at 50% full */
+	db->pkgcache = _alpm_pkghash_create(est_count * 2);
+
 	while((ent = readdir(dbdir)) != NULL) {
 		const char *name = ent->d_name;
 
@@ -410,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;
@@ -430,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 f7101f54..4ad045c2 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,13 @@ 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);
+
+	/* 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;
@@ -194,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;
@@ -207,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 */
@@ -215,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);
@@ -281,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..02f82823 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/pkghash.c b/lib/libalpm/pkghash.c
new file mode 100644
index 00000000..54805275
--- /dev/null
+++ b/lib/libalpm/pkghash.c
@@ -0,0 +1,346 @@
+/*
+ *  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;
+	hash->buckets = 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;
+		}
+	}
+
+	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));
+
+	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;
+	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
+	 *
+	 * 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. */
+	if(oldhash->buckets < 500) {
+		newsize = oldhash->buckets * 2;
+	} else if(oldhash->buckets < 2000) {
+		newsize = oldhash->buckets * 3 / 2;
+	} else if(oldhash->buckets < 5000) {
+		newsize = oldhash->buckets * 4 / 3;
+	} else {
+		newsize = oldhash->buckets + 1;
+	}
+
+	newhash = _alpm_pkghash_create(newsize);
+	if(newhash == NULL) {
+		/* creation of newhash failed, stick with old one... */
+		return(oldhash);
+	}
+
+	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 = get_hash_position(package->name_hash, newhash);
+
+			newhash->hash_table[position] = oldhash->hash_table[i];
+			oldhash->hash_table[i] = NULL;
+		}
+	}
+
+	newhash->entries = oldhash->entries;
+
+	_alpm_pkghash_free(oldhash);
+
+	return(newhash);
+}
+
+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 = get_hash_position(pkg->name_hash, hash);
+
+	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 = get_hash_position(pkg->name_hash, hash);
+
+	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);
+}
+
+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.
+ *
+ * @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(data) {
+		*data = NULL;
+	}
+
+	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) {
+			size_t stop, prev;
+
+			/* remove from list and hash */
+			hash->list = alpm_list_remove_item(hash->list, i);
+			if(data) {
+				*data = info;
+			}
+			hash->hash_table[position] = NULL;
+			free(i);
+			hash->entries -= 1;
+
+			/* 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;
+			}
+			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);
+		}
+
+		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..a6c1db71
--- /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 */
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;