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

[Blue Swirl]

On 10/7/08, Laurent Desnogues <address@hidden> wrote:
> Here is a revised version that uses less memory while keeping
>  the same complexity.
>
>  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?