Re: Hash table based symbol lookup (was: Re: [Qemu-devel] [PATCH] Fix symbol lookup for mips64* targets)

[Laurent Desnogues]

On Tue, Oct 7, 2008 at 7:50 PM, Blue Swirl <address@hidden> wrote:
> On 10/7/08, Laurent Desnogues <address@hidden> wrote:
>>
>>  This could be made less memory hungry by using some
>>  binary tree data structure at the expense of code complexity.
>>  I won't go down that road as anyway this stuff is mainly used
>>  for debugging and tracing purposes.
>
> I agree that hash and binary tree would be too complex.
>
> But what if you dropped the hash table and used a binary tree instead?
> A binary tree would be both memory efficient (you could keep the
> regions, maybe just use a pointer to the original symbol table) and
> it's relatively fast. Maybe the original symbols could be sorted so
> that the binary search could use the original table directly?

I was indeed talking about replacing the whole hash table by a
binary tree (it has been proven that mixing both is not the way
to go;  cf Knuth).  The problem we have here is that we are
doing an interval search:  we are looking if an address belongs
to a function.

I will give that some thought, but don't hold your breath :-)


Laurent