[PATCH 2/3] cached-sha1-map: refactoring hash traversal code

["Geoffrey Irving" <irving@naml.us>]

>From c4e60c28fe66985ac8224da832589c982010744e Mon Sep 17 00:00:00 2001
From: Geoffrey Irving <irving@naml.us>
Date: Tue, 8 Jul 2008 19:47:22 -0700
Subject: [PATCH 2/3] cached-sha1-map: refactoring hash traversal code

Pulling common code from get_cached_sha1_entry and set_cached_sha1_entry
into static find_helper function.
---
 cached-sha1-map.c |   68 +++++++++++++++++++++++++++++-----------------------
 1 files changed, 38 insertions(+), 30 deletions(-)

diff --git a/cached-sha1-map.c b/cached-sha1-map.c
index e363745..147c7a2 100644
--- a/cached-sha1-map.c
+++ b/cached-sha1-map.c
@@ -129,10 +129,14 @@ static size_t get_hash_index(const unsigned char *sha1)
 	return ntohl(*(size_t*)sha1);
 }

-int get_cached_sha1_entry(struct cached_sha1_map *cache,
-	const unsigned char *key, unsigned char *value)
+/*
+ * Returns the index if the entry exists, and the complemented index of
+ * the next free entry otherwise.
+ */
+static long find_helper(struct cached_sha1_map *cache,
+	const unsigned char *key)
 {
-	size_t i, mask;
+	long i, mask;

 	if (!cache->initialized)
 		init_cached_sha1_map(cache);
@@ -140,43 +144,47 @@ int get_cached_sha1_entry(struct cached_sha1_map *cache,
 	mask = cache->size - 1;

 	for (i = get_hash_index(key) & mask; ; i = (i+1) & mask) {
-		if (!hashcmp(key, cache->entries[i].key)) {
-			hashcpy(value, cache->entries[i].value);
-			return 0;
-		} else if (is_null_sha1(cache->entries[i].key))
-			return -1;
+		if (!hashcmp(key, cache->entries[i].key))
+			return i;
+		else if (is_null_sha1(cache->entries[i].key))
+			return ~i;
 	}
 }

+int get_cached_sha1_entry(struct cached_sha1_map *cache,
+	const unsigned char *key, unsigned char *value)
+{
+	long i = find_helper(cache, key);
+	if(i < 0)
+		return -1;
+
+	/* entry found, return value */
+	hashcpy(value, cache->entries[i].value);
+	return 0;
+}
+
 void set_cached_sha1_entry(struct cached_sha1_map *cache,
 	const unsigned char *key, const unsigned char *value)
 {
-	size_t i, mask;
+	long i;
 	struct cached_sha1_entry *entry;

-	if (!cache->initialized)
-		init_cached_sha1_map(cache);
-
-	if (4*cache->count >= 3*cache->size)
-		grow_map(cache);
-
-	mask = cache->size - 1;
-
-	for (i = get_hash_index(key) & mask; ; i = (i+1) & mask) {
-		entry = cache->entries+i;
-
-		if (is_null_sha1(entry->key)) {
-			hashcpy(entry->key, key);
+	i = find_helper(cache, key);
+
+	if (i < 0) { /* write new entry */
+		entry = cache->entries + ~i;
+		hashcpy(entry->key, key);
+		hashcpy(entry->value, value);
+		cache->count++;
+		cache->dirty = 1;
+	} else { /* overwrite existing entry */
+		entry = cache->entries + i;
+		if (hashcmp(value, entry->value)) {
 			hashcpy(entry->value, value);
-			cache->count++;
 			cache->dirty = 1;
-			return;
-		} else if(!hashcmp(key, entry->key)) {
-			if (hashcmp(value, entry->value)) {
-				hashcpy(entry->value, value);
-				cache->dirty = 1;
-			}
-			return;
 		}
 	}
+
+	if (4*cache->count >= 3*cache->size)
+		grow_map(cache);
 }
-- 
1.5.6.2.258.g7a51a