Re: [PATCH v3 00/21] OvmfPkg/Virtio: introduce IOMMU-like member functions

[Brijesh Singh <brijesh.singh@amd.com>]

On 8/23/17 8:22 PM, Laszlo Ersek wrote:Okay, I will look into it -
thanks for the tip. I wanted to actually use
>> the Simple array (because we know the maximum number of buffer we can
>> queue) but was  not sure about your preferences hence I went to with
>> list. If you are okay then I can use array's too.
> My concern isn't about memory consumption (if our queue is full (64
> elements, IIRC), we just reject the transmit request and let the caller
> deal with the error).
>
> Instead, I'd like to avoid an O(n) lookup time (where n is the number of
> pending requests), for whatever lookup is necessary now (I haven't
> checked the specifics yet). BaseOrderedCollectionRedBlackTreeLib would
> give you O(log n) lookup time.
>
> Without having looked at the details, I think an array would have O(n)
> lookup time as well (linear search, right?).
>
> (Let's not try to do O(1) with a hash function -- that's quite out of
> scope for now, and with a hash table, one has to think about collisions
> too, etc. When I contributed BaseOrderedCollectionRedBlackTreeLib, I
> wanted it to become *the* go-to associative data structure for edk2 --
> at least in such DXE and UEFI driver contexts where frequent pool
> allocations and releases are not a problem. Plus, RB trees double as
> fast priority queues, can be used for one-off sorting, have worst-case
> (not just on-average) O(log n) time guarantees... I think they're
> versatile.)

To my understanding the network packet enqueued in the transmit ring
will be completed in same order, hence I was thinking about the queue
data structure and was not concern about the search time. I was mostly
concerned about the memory consumption but if my understanding is wrong
then I agree that we need to pick right data structure. Since the
RedBlack tree is already implemented hence I have no issue using it. thanks

-Brijesh