Re: [PATCH v4 2/4] path: optimize common dir checking

From

Junio C Hamano <gitster@pobox.com>

Date

Aug 28, 2015, 16:39 UTC

Message-ID

<xmqqoahr2wqj.fsf@gitster.mtv.corp.google.com>

In-Reply-To

<1440627545.26055.8.camel@twopensource.com>

David Turner <dturner@twopensource.com> writes:

> On Wed, 2015-08-26 at 18:10 -0400, David Turner wrote:
>> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:
>> > > + * For example, consider the following set of strings:
>> > > + * abc
>> > > + * def
>> > > + * definite
>> > > + * definition
>> > > + *
>> > > + * The trie would look look like:
>> > > + * root: len = 0, value = (something), children a and d non-NULL.
>> > 
>> > "value = NULL", as there is no empty string registered in the trie?
>> 
>> Indeed.
>> 
>> > > + *    a: len = 2, contents = bc
>> > 
>> > "value = NULL" here, too (just showing I am following along, not
>> > just skimming)?
>> 
>> Yep.
>
> No, wait. value should be non-NULL, since abc is in the string set. 

True.  Here is what I came up with on top of your original.  

 path.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/path.c b/path.c
index 4100ba6..ce0530b 100644
--- a/path.c
+++ b/path.c
@@ -133,12 +133,13 @@ struct common_dir common_list[] = {
  * definition
  *
  * The trie would look look like:
- * root: len = 0, value = (something), children a and d non-NULL.
- *    a: len = 2, contents = bc
- *    d: len = 2, contents = ef, children i non-NULL, value = (something)
+ * root: len = 0, children a and d non-NULL, value = NULL.
+ *    a: len = 2, contents = bc, value = (data for "abc")
+ *    d: len = 2, contents = ef, children i non-NULL, value = (data for "def")
  *       i: len = 3, contents = nit, children e and i non-NULL, value = NULL
- *           e: len = 0, children all NULL, value = (something)
- *           i: len = 2, contents = on, children all NULL, value = (something)
+ *           e: len = 0, children all NULL, value = (data for "definite")
+ *           i: len = 2, contents = on, children all NULL,
+ *              value = (data for "definition")
  */
 struct trie {
 	struct trie *children[256];