On 08/24/17 04:06, Brijesh Singh wrote: > > > 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,
The current code does not make this assumption -- please see the very last paragraph in "OvmfPkg/VirtioNetDxe/TechNotes.txt" --, and it would be good to keep it that way. > 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 OK, thanks! Laszlo _______________________________________________ edk2-devel mailing list [email protected] https://lists.01.org/mailman/listinfo/edk2-devel
