Re: [Draft D] Xen on ARM vITS Handling

[Julien Grall <julien.grall@citrix.com>]

On 05/06/2015 07:07, Vijay Kilari wrote:
> On Thu, Jun 4, 2015 at 7:24 PM, Ian Campbell <ian.campbell@citrix.com> wrote:
>> This information shall include at least:
>>
>> - The Device ID of the device.
>> - The maximum number of Events which the device is capable of
>>    generating.
>>
>> When a device is discovered/registered (i.e. when all necessary
>> information is available) then:
>>
>> - `struct its_device` and the embedded `events` array will be
>>    allocated (the latter with `nr_events` elements).
>> - The `struct its_device` will be inserted into a mapping (possibly an
>>    R-B tree) from its physical Device ID to the `struct its`.
>
>     Why not radix tree. It might be better in look up?

The lookup up in the radix tree is in O(k) where k is the size of the 
index (i.e the number of DevID bits).

In the R-B tree, the lookup is in O(log(n)) where n is the number of 
member in the tree.

As we use integer for the index, the R-B tree will be faster (The number 
of PCI device per domain will never be too big).

Regards,

-- 
Julien Grall