>From c4e60c28fe66985ac8224da832589c982010744e Mon Sep 17 00:00:00 2001
From: Geoffrey Irving <irving@xxxxxxx>
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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
