[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Xen-devel] [Draft D] Xen on ARM vITS Handling
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
|
Lists.xenproject.org is hosted with RackSpace, monitoring our |