Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> writes: > 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, [...] >> 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
