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

Linus Torvalds [off-list ref] writes:

On Thu, 6 Mar 2008, David Kastrup wrote:

quoted

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,

[...]

quoted

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