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

Geoffrey Irving· Jul 9, 2008, 03:56 UTC · lore

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

Show changes to cached-sha1-map.c +38 −30

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

Junio C Hamano· Jul 9, 2008, 05:27 UTC · re: Geoffrey Irving · lore

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

"Geoffrey Irving" <irving@naml.us> writes:

Show 8 quoted lines

> 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.
> ---

Sign-off?

>  cached-sha1-map.c |   68 +++++++++++++++++++++++++++++-----------------------
>  1 files changed, 38 insertions(+), 30 deletions(-)

The refactoring is good, and it should have been that way from the beginning. Please don't send in "introduce foo.c [1/N]", "oops, initial version of foo.c was crap, here is a fixup [2/N]".

Show 26 quoted lines

> 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
> @@ -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;

Does this have to be extern?

If you are designing an API from scratch, and if you want a long, use it consistently. Do not demote an int to shorter int in a callchain unnecessarily.

patch, 3 partscached-sha1-map: refactoring hash traversal code