Re: Adapting switch(x){case(y):...} with hashing

[Geoff Keating <geoffk at geoffk dot org>]

dewar@gnat.com (Robert Dewar) writes:

> <<One of the obscure to-do list entries had an interesting request.
> Currently, g++ uses a binary-tree / jump-table solution to handle
> "switch"-"case" processing.  The request was for hashing to be added as
> an alternative when it would be appropriate (the note suggested sparse
> sets).  Obviously, the problem is more complex than it appears, and
> binary searches have their strengths.  Also, memory requirements may be
> critically fatal.
> >>
> 
> I don't see why there should be any conceptual problem in implementing
> this approach. All BCPL compilers had this capability for example.

There are many things you can do in this area.

For instance, often people have an enum:

enum { FOO_0, FOO_1, FOO_2, FOO_3, FOO_4, FOO_5, FOO_6 };

and write

if (x == FOO_1 || x == FOO_2 || x == FOO_4 || x == FOO_5 || x == FOO_6)

or have a switch statement:

switch (x)
{
  case FOO_1: case FOO_2: case FOO_4: case FOO_5: case FOO_6:
    ...
  case FOO_0: case FOO_3:
    ...
}

and this could be turned into, for instance

if (x & ~7)
{
  int t = 1 << x;
  if (t & 0x76)
    ...
  else if (t & 0x09)
    ...
}



For hashing, you'd probably want to try to find a perfect hash, like gperf,
when possible.

-- 
- Geoffrey Keating <geoffk@geoffk.org>