[PATCH stable] parsers: use the correct maximum radix tree depth
Bryan O'Sullivan
bos at serpentine.com
Tue May 8 16:55:06 CDT 2012
# HG changeset patch
# User Bryan O'Sullivan <bryano at fb.com>
# Date 1336513564 25200
# Node ID 852d9d87a0cdb977da9f5731bc978e72e9d19232
# Parent eab32ab5cd65b2c9d1319c1c07886b450614abbc
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 eab32ab5cd65 -r 852d9d87a0cd mercurial/parsers.c
--- a/mercurial/parsers.c Thu May 03 16:12:52 2012 -0500
+++ 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;
More information about the Mercurial-devel
mailing list