Re: Switch statement code generation

nathan.mccauley@gmail.com wrote:


> On Nov 5, 12:12 pm, Walter Banks <wal...@bytecraft.com> wrote:
>> Joshua Cranmer wrote:
>> > I'm trying to put together a list of various methods to do code
>> > generate for switch statements. ...
>
> Has anyone seen tries used for the string-based switch statements?


No... Not tries exactly. Since compilation happens on static data, it's
easy to build a simple balanced binary tree. The extra complication of
tries when you're not going to be doing insertions and deletions isn't
worth it.


I think the winner for string switches is a string representation with
a precomputed hash code, used in combination with a hashtable of
jump addresses.


Because the elements are known at compilation time, you can know in
advance the number of collisions in the longest bucket when you're
allocating the table, which means you can just allocate a table of
NxM entities where N is the number of buckets (a power of 2) and M
is the longest length needed (rounded up to a power of 2).


So when you get the string's hash code, you do a bitmask to get the
index into the hash table, and then check to see if you have a matching
hash code(success) or a zero hashcode (failure) there - if not,
increment the index by one until you do (a degenerate case of
"rehashing" that you can use here because you don't have to deal
with the possibility of making space for arbitrary insertions) and
then you have the jump address.


                                                                Bear

Return to the comp.compilers page.
Search the comp.compilers archives again.