Re: [Qemu-devel] [PATCH v2] Add ACPI tables for TPM

[Laszlo Ersek <lersek@redhat.com>]

On 07/30/14 18:07, Michael S. Tsirkin wrote:
> On Wed, Jul 30, 2014 at 06:02:21PM +0200, Laszlo Ersek wrote:
>> On 07/30/14 17:37, Michael S. Tsirkin wrote:
>>
>>> 1. execute alloc instructions, building a data structure mapping fwcfg
>>>    file names to memory.
>>
>> Yes, edk2 currently lacks a good (== sub-linear) dictionary data type.
>> This week I started porting a red-black tree library that I had
>> originally written in 1999 or 2000 or so. In OVMF coding I've faced a
>> few occasions when I would have wanted a dictionary, and one of them is
>> the above.
>>
>> Laszlo
> 
> number of tables is small though, seabios just uses a linked list
> and a linear search, to get N^2 complexity where N is number
> of tables.
> 
> it's up to you.

Correct, I did consider that, but I probed edk2-devel for opinions about
an associative data structure first, and feedback was positive, so I
started porting. I'll even admit that for small N, the O(N^2) of lists
might beat the rbtree's O(NlogN) in practice, due to the greater
constants in the "smart" data structure, but just the API should be that
much more convenient that I'm willing to accept that.

Laszlo