From: Junio C Hamano <gitster@pobox.com>
Date: Wed, 12 Aug 2015 22:48:25 GMT
Subject: Re: [PATCH v3 2/4] path: optimize common dir checking
Message-ID: <xmqqio8kjf7q.fsf@gitster.dls.corp.google.com>
In-Reply-To: <1439416645-19173-2-git-send-email-dturner@twopensource.com>

David Turner <dturner@twopensource.com> writes:

> Instead of a linear search over common_list to check whether
> a path is common, use a trie.  The trie search operates on
> path prefixes, and handles excludes.
>
> Signed-off-by: David Turner <dturner@twopensource.com>
> ---
>
> Probably overkill, but maybe we could later use it for making exclude
> or sparse-checkout matching faster (or maybe we have to go all the way
> to McNaughton-Yamada for that to be truly worthwhile).

This is why I love this list.  A mere mention of "something better
than linear list" immediately is answered by a trie and a mention of
McNaughton-Yamada ;-).