# HG changeset patch
# User Bryan O'Sullivan <bryano@fb.com>
# Date 1336513564 25200
# Node ID e6dfbc5df76fe96f73ca204b1d10cd27a814e890
# Parent  592e0beee8b0d07298943f87b1a117c049f53fd0
parsers: use the correct maximum radix tree depth

Previously, we would not use more than half of a SHA-1 hash when
constructing and searching the tree.

diff -r 592e0beee8b0 -r e6dfbc5df76f mercurial/parsers.c
--- a/mercurial/parsers.c	Wed May 09 18:45:14 2012 +0200
+++ b/mercurial/parsers.c	Tue May 08 14:46:04 2012 -0700
@@ -546,7 +546,7 @@
 
 static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen)
 {
-	int level, off;
+	int level, maxlevel, off;
 
 	if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
 		return -1;
@@ -554,7 +554,9 @@
 	if (self->nt == NULL)
 		return -2;
 
-	for (level = off = 0; level < nodelen; level++) {
+	maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2);
+
+	for (level = off = 0; level < maxlevel; level++) {
 		int k = nt_level(node, level);
 		nodetree *n = &self->nt[off];
 		int v = n->children[k];
@@ -596,7 +598,7 @@
 	int level = 0;
 	int off = 0;
 
-	while (level < 20) {
+	while (level < 40) {
 		int k = nt_level(node, level);
 		nodetree *n;
 		int v;