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 _______________________________________________ edk2-devel mailing list [email protected] https://lists.01.org/mailman/listinfo/edk2-devel
