Re: [Xen-devel] [Draft D] Xen on ARM vITS Handling

[Ian Campbell <ian.campbell@xxxxxxxxxx>]

On Fri, 2015-06-05 at 10:28 +0100, Julien Grall wrote:
> 
> On 05/06/2015 07:07, Vijay Kilari wrote:
> > On Thu, Jun 4, 2015 at 7:24 PM, Ian Campbell <ian.campbell@xxxxxxxxxx> 
> > 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).

Lets try not to worry too much about the specific data structures at
this stage. The key point is its not a list (potentially enormous memory
overhead) nor a simple list (bad lookup times).

Ian.


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel