summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@osdl.org>2006-10-17 02:58:54 (GMT)
committerJunio C Hamano <junkio@cox.net>2006-10-17 04:27:44 (GMT)
commit9de0834663f28bee9e6b2c4647ed6128241ed26f (patch)
tree75e3cdf40a6d77455c6177dd579c02fb66116675
parent6fe5b7ff6cafcc94415deba2f3d611770d8e6b1e (diff)
downloadgit-9de0834663f28bee9e6b2c4647ed6128241ed26f.zip
git-9de0834663f28bee9e6b2c4647ed6128241ed26f.tar.gz
git-9de0834663f28bee9e6b2c4647ed6128241ed26f.tar.bz2
Fix hash function in xdiff libraryv1.4.2.4
Jim Mayering noticed that xdiff library took insanely long time when comparing files with many identical lines. This was because the hash function used in the library is broken on 64-bit architectures and caused too many collisions. http://thread.gmane.org/gmane.comp.version-control.git/28962/focus=28994 Acked-by: Davide Libenzi <davidel@xmaliserver.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
-rw-r--r--xdiff/xmacros.h5
1 files changed, 3 insertions, 2 deletions
diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h
index 4c2fde8..e2cd202 100644
--- a/xdiff/xmacros.h
+++ b/xdiff/xmacros.h
@@ -24,14 +24,15 @@
#define XMACROS_H
-#define GR_PRIME 0x9e370001UL
#define XDL_MIN(a, b) ((a) < (b) ? (a): (b))
#define XDL_MAX(a, b) ((a) > (b) ? (a): (b))
#define XDL_ABS(v) ((v) >= 0 ? (v): -(v))
#define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')
-#define XDL_HASHLONG(v, b) (((unsigned long)(v) * GR_PRIME) >> ((CHAR_BIT * sizeof(unsigned long)) - (b)))
+#define XDL_ADDBITS(v,b) ((v) + ((v) >> (b)))
+#define XDL_MASKBITS(b) ((1UL << (b)) - 1)
+#define XDL_HASHLONG(v,b) (XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))
#define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)
#define XDL_LE32_PUT(p, v) \
do { \