Re: [PATCH 1/5] Add 'df_name_compare()' helper function

From: David Kastrup <dak@gnu.org>
Date: Mar 6, 2008, 21:50 UTC
Message-ID: <85bq5r34kh.fsf@lola.goethe.zz>
In-Reply-To: <alpine.LFD.1.00.0803060743180.12253@woody.linux-foundation.org>

Linus Torvalds <torvalds@linux-foundation.org> writes:

Show 17 quoted lines

> On Thu, 6 Mar 2008, David Kastrup wrote:
>
>> Consider the case of a merge of
>> 
>> A:
>> blubb
>> blubb.hi
>> 
>> B:
>> blubb.hi
>> blubb/
>> 
>> Any traversal that is done reasonably efficiently will never compare
>> blubb to blubb/ and I don't see how to get around this.
>
> Correct. There _is_ no sort order that will find the conflict in a
> single pass,

[...]

Show 5 quoted lines

>> Basically, I think you need a special traversal routine.
>
> Yes, we need to handle it in two passes. Which is actually hopefully
> not all that hard, but it is totally impossible (at least for me) with
> the old code that was so hard to follow.

Well, as I said: a single pass is ok when additionally supported by a FIFO keeping x around until x/ (or its place in the order of things) passes by. This will be O(1) with regards to comparisons, and typically cheap with regard to memory requirements (things get unfriendly if there are billions of files or even directories obeying the pattern x.*, but only with regard to memory, not speed).

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum