[pacman-dev] [PATCH 2/4] Add hash_sdbm function

[Dan McGee]

This is prepping for the addition of a hash field to each package to greatly
speed up the string comparisons we frequently do on package name in
_alpm_pkg_find.

Signed-off-by: Dan McGee <dan at archlinux.org>
---
 lib/libalpm/util.c |   21 +++++++++++++++++++++
 lib/libalpm/util.h |    1 +
 2 files changed, 22 insertions(+), 0 deletions(-)

diff --git a/lib/libalpm/util.c b/lib/libalpm/util.c
index e425fa4..8e83bda 100644
--- a/lib/libalpm/util.c
+++ b/lib/libalpm/util.c
@@ -845,4 +845,25 @@ int _alpm_splitname(const char *target, pmpkg_t *pkg)
 	return(0);
 }
 
+/**
+ * Hash the given string to an unsigned long value.
+ * This is the standard sdbm hashing algorithm.
+ * @param str string to hash
+ * @return the hash value of the given string
+ */
+unsigned long _alpm_hash_sdbm(const char *str)
+{
+	unsigned long hash = 0;
+	int c;
+
+	if(!str) {
+		return(hash);
+	}
+	while((c = *str++)) {
+		hash = c + (hash << 6) + (hash << 16) - hash;
+	}
+
+	return(hash);
+}
+
 /* vim: set ts=2 sw=2 noet: */
diff --git a/lib/libalpm/util.h b/lib/libalpm/util.h
index 78877a2..0b80420 100644
--- a/lib/libalpm/util.h
+++ b/lib/libalpm/util.h
@@ -78,6 +78,7 @@ int _alpm_lstat(const char *path, struct stat *buf);
 int _alpm_test_md5sum(const char *filepath, const char *md5sum);
 char *_alpm_archive_fgets(char *line, size_t size, struct archive *a);
 int _alpm_splitname(const char *target, pmpkg_t *pkg);
+unsigned long _alpm_hash_sdbm(const char *str);
 
 #ifndef HAVE_STRSEP
 char *strsep(char **, const char *);
-- 
1.7.3.3