From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47789) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XCWdp-0008QM-TM for qemu-devel@nongnu.org; Wed, 30 Jul 2014 12:22:20 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XCWdj-0000mH-OO for qemu-devel@nongnu.org; Wed, 30 Jul 2014 12:22:13 -0400 Received: from mx1.redhat.com ([209.132.183.28]:44258) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XCWdj-0000mD-GH for qemu-devel@nongnu.org; Wed, 30 Jul 2014 12:22:07 -0400 Message-ID: <53D91BAA.5050506@redhat.com> Date: Wed, 30 Jul 2014 18:22:02 +0200 From: Laszlo Ersek MIME-Version: 1.0 References: <1406631139-6754-1-git-send-email-stefanb@us.ibm.com> <20140730132027.GA26025@redhat.com> <53D902F6.1050106@redhat.com> <20140730144623.GA26956@redhat.com> <53D90C19.80005@redhat.com> <20140730153738.GG26313@redhat.com> <53D9170D.1060204@redhat.com> <20140730160706.GE27451@redhat.com> In-Reply-To: <20140730160706.GE27451@redhat.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH v2] Add ACPI tables for TPM List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: "Michael S. Tsirkin" Cc: Stefan Berger , qemu-devel@nongnu.org, Stefan Berger 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