Subject: [PATCH 11/11] object: try 2-way cuckoo again

From: Junio C Hamano <[email-masked]>
Date: Thu, 11 Aug 2011 10:53:16 -0700

This should match the first "naive" cuckoo hashing implementation.

Signed-off-by: Junio C Hamano <[email-masked]>
---
../+v/ddb2c7c09c7af16bf00aa5aef6cdf54ae4611aec/git-pack-objects
Counting objects: 2139209, done.
31.28user 3.15system 0:34.53elapsed 99%CPU (0avgtext+0avgdata 8177056maxresident)k
0inputs+0outputs (0major+1206514minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.06user 3.26system 0:34.43elapsed 99%CPU (0avgtext+0avgdata 8177056maxresident)k
0inputs+0outputs (0major+1206514minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.06user 3.22system 0:34.39elapsed 99%CPU (0avgtext+0avgdata 8176512maxresident)k
0inputs+0outputs (0major+1206542minor)pagefaults 0swaps
---
 object.c |   15 ++++-----------
 1 files changed, 4 insertions(+), 11 deletions(-)

diff --git a/object.c b/object.c
index 18e6bcf..fc08e5b 100644
--- a/object.c
+++ b/object.c
@@ -49,18 +49,16 @@ struct object *get_indexed_object(unsigned int idx)
 struct object *lookup_object(const unsigned char *sha1)
 {
 	struct object *obj;
-	unsigned int hashval[3];
+	unsigned int hashval[2];
 
 	if (!obj_hash)
 		return NULL;
 
-	memcpy(hashval, sha1, 12);
+	memcpy(hashval, sha1, 8);
 	if ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
 	if ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
-	if ((obj = obj_hash[H(hashval, 2)]) && !hashcmp(sha1, obj->sha1))
-		return obj;
 	return NULL;
 }
 
@@ -80,20 +78,15 @@ static struct object *insert_obj_hash(struct object *obj)
 	for (loop = obj_hash_size / 2; 0 <= loop; loop--) {
 		struct object *tmp_obj;
 		unsigned int ix;
-		unsigned int hashval[3];
+		unsigned int hashval[2];
 
-		memcpy(hashval, obj->sha1, 12);
+		memcpy(hashval, obj->sha1, 8);
 		ix = H(hashval, 0);
 		if (!obj_hash[ix]) {
 			obj_hash[ix] = obj;
 			return NULL;
 		}
 		ix = H(hashval, 1);
-		if (!obj_hash[ix]) {
-			obj_hash[ix] = obj;
-			return NULL;
-		}
-		ix = H(hashval, 2);
 		tmp_obj = obj_hash[ix];
 		obj_hash[ix] = obj;
 		if (!tmp_obj)
-- 
1.7.6.433.g1421f