Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups

[Alexander Shishkin]

Alexey Budankov <alexey.budankov@xxxxxxxxxxxxxxx> writes:

>>>>> bool event_less(left, right)
>>>>> {
>>>>>   if (left->cpu < right->cpu)
>>>>>     return true;
>>>>>
>>>>>   if (left->cpu > right_cpu)
>>>>>     return false;
>>>>>
>>>>>   if (left->vtime < right->vtime)
>>>>>     return true;
>>>>>
>>>>>   return false;
>>>>> }
>>>>>
>>>>> insert_group(group, event, tail)
>>>>> {
>>>>>   if (tail)
>>>>>     event->vtime = ++group->vtime;
>>>>>
>>>>>   tree_insert(&group->root, event);
>>>>> }

[ ... ]

> 2. implementing special _less() function and rotation by re-inserting
>    group with incremented index;
>

[ ... ]

> Now I figured that not all indexed events are always located under 
> the root with the same cpu, and it depends on the order of insertion
> e.g. with insertion order 01,02,03,14,15,16 we get this:
>
>      02
>     /  \
>    01  14
>       /  \
>      03  15
>            \
>            16

How did you arrive at this? Seeing the actual code would help, because
this is not the ordering we're looking for. With Peter's earlier example
(quoted above) it shouldn't look like this.

Regards,
--
Alex