[PATCH] Sort "loose" dives properly in-between trips

Dirk Hohndel dirk at hohndel.org
Mon Jan 7 10:57:29 PST 2013


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

> On Mon, Jan 7, 2013 at 9:56 AM, Miika Turkia <miika.turkia at gmail.com> wrote:
>>
>> Your extension is clearly required. (I only had one dive not in trip,
>> thus didn't even consider this part of the sorting.)
>>
>> When comparing the original sorting code and my code, a difference I
>> can see is that my code does not return 0 when the times are the same.
>> I believe the times should never be the same, but I am not sure about
>> it.
>
> It can happen if you load the XML files for two people. We don't want
> the trips to mix, but there's a possibility (although remote) that
> there are times that just happen to be the same.

Case in point - Linus and I go diving together reasonably
frequently. And we have indeed have had dives with the same start
time. All it takes is for that to be the first dive of a trip and bingo,
we'll have two trips with the same dates if we load both of our data
files. 

> However, the much *bigger* possibility is that there are dive trips
> that overlap, and dives that are outside those dive trips, and then
> the real issue is that the sort really does have to be transitive.
> Otherwise you can get really nasty bugs (not just wrong ordering -
> unexpected lockups due to infinite loops in the sorting that happen
> under just very special cases, and only with particular sorting
> algorithms).

Yes, transitivity is not optional.

> One thing to look out for is to make sure we never compare two dives
> in separate trips with the dive time. And that's where it worries me
> to compare a dive time with a trip time: the transitivity means that
>
>  - dive a in trip A
>  - dive b in no trip
>  - dive c in trip C
>
> has to be *very* careful about comparing dives a/b and b/c, because
> the transitivity implies that it implicitly then compares dives a/c.
> We need to make sure that a comparison of a/c gets a result that is
> consistent with the comparisons of a/b and b/c.
>
> I *think* your patch is ok (because a and c will be compared by the
> dates of A/C, and then a/b will compare A/b times, and b/c will
> compare b/C times), but I worry about this a bit.

Thinking this through I think that is EXACTLY the right behavior.
a and c will sort by the A and C timestamp. So in order for this to be
consistent, we need to compare b with A and C and not a and c.

> The main thing I want you to think about is that it's actually more
> complicated than just ever looking at two particular dives. The full
> ordering is about all the edges between all the dives, and if you can
> create a loop in that graph, you can confuse the sorting algorithm.

With all that said - should I apply the patch and we test it in tree, or
should I wait for Miika to come back and say "yes, this is good"?

/D


More information about the subsurface mailing list