From mboxrd@z Thu Jan 1 00:00:00 1970 From: Julien Grall Subject: Re: [Draft D] Xen on ARM vITS Handling Date: Fri, 5 Jun 2015 10:28:17 +0100 Message-ID: <55716BB1.7070806@citrix.com> References: <1433426053.7108.107.camel@citrix.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; Format="flowed" Content-Transfer-Encoding: 7bit Return-path: In-Reply-To: List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org To: Vijay Kilari , Ian Campbell Cc: manish.jaggi@caviumnetworks.com, Julien Grall , Stefano Stabellini , "xen-devel@lists.xen.org" List-Id: xen-devel@lists.xenproject.org On 05/06/2015 07:07, Vijay Kilari wrote: > On Thu, Jun 4, 2015 at 7:24 PM, Ian Campbell 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