jump tables (-Edit- Eliminating conditional statements :-))

[bloodline]

Is there any "nice" way to do this in C, pointer magic etc?

Imagine I have an array of pointers to allow me to jump to a subroutine based on the index stored in a variable:

int* jump[3];

jump[0]= &task1;
jump[1]= &task2;
jump[2]= &task3;

a=user_input(); // where the user could enter 1, 2 or 3

Goto jump(a);
task_return:


task1:
Do Something;
goto task_return;

task2:
Do Something else;
goto task_return;

task3:
Do Something different;
goto task_return;


I have no idea why I'm asking this... :crazy:

[Piru]

I won't give you the exact solution, but this should help still:

Code: [Select]


#include <stdio.h>

typedef int (*funcptr_t)(int, char *);

int func1(int x, char *str);
int func2(int x, char *str);
int func3(int x, char *str);

int main(void)
{
  funcptr_t funcarray[3] =
  {
    func1,
    func2,
    func3
  };
  int i;

  for (i = 0; i < 3; i++)
  {
    int ret;

    ret = funcarray[i](i * i + 2, &quot;moo&quot;);
    printf(&quot;ret %d\n&quot;, ret);
  }

  return 0;
}

int func1(int x, char *str)
{
  printf(&quot;func1 x=%d, str=<%s>\n&quot;, x, str);
  return 1;
}

int func2(int x, char *str)
{
  printf(&quot;func2 x=%d, str=<%s>\n&quot;, x, str);
  return 2;
}

int func3(int x, char *str)
{
  printf(&quot;func3 x=%d, str=<%s>\n&quot;, x, str);
  return 3;
}


[EDIT]changed i*i to i*i+2 to make it more obvious the input isn't always the index ;-)[/EDIT]

[bloodline]

Piru wrote:
I won't give you the exact solution, but this should help still:

Code: [Select]


#include <stdio.h>

typedef int (*funcptr_t)(int, char *);

int func1(int x, char *str);
int func2(int x, char *str);
int func3(int x, char *str);

int main(void)
{
  funcptr_t funcarray[3] =
  {
    func1,
    func2,
    func3
  };
  int i;

  for (i = 0; i < 3; i++)
  {
    int ret;

    ret = funcarray[i](i*i, &quot;moo&quot;);
    printf(&quot;ret %d\n&quot;, ret);
  }

  return 0;
}

int func1(int x, char *str)
{
  printf(&quot;func1 x=%d, str=<%s>\n&quot;, x, str);
  return 1;
}

int func2(int x, char *str)
{
  printf(&quot;func2 x=%d, str=<%s>\n&quot;, x, str);
  return 2;
}

int func3(int x, char *str)
{
  printf(&quot;func3 x=%d, str=<%s>\n&quot;, x, str);
  return 3;
}


Hmmm, yeah that actually makes more sense than what I was trying to achive!! Cheers :-D

[Karlos]

Function lookup is great :-)

Generally, the syntax for a function pointer is ugly, but typedefs help a lot

eg

typedef (*)();

So, suppose you want a pointer to function of the signature "int func(const char* blah);"

you would use

typedef int (*MyFuncPtrType)(const char*);

and then you can do stuff like

int foo(const char* blah);
int moo(const char* blah);
int poo(const char* blah);

...

MyFuncPtr p = &foo; /* the & is optional here btw */

p("hello!");

Or create arrays of pointers of this kind,

MyFuncPtr jumpTable[] = { &foo, &moo, &poo };

and do

jumpTable[1]("Hello");

etc...

[Karlos]

@bloodline

Of course C++ virtual functions are a bit nicer to use ;-)

[bloodline]

Karlos wrote:
@bloodline

Of course C++ virtual functions are a bit nicer to use ;-)

Que?

[Karlos]

@bloodline

Consider

class GameMonsterAI {
public:
virtual void huntTarget(); // AI behaviours
virtual void foundTarget();
virutal void attackTarget();
//..
};

Then later

class UglyMonster : public GameMosterAI {
public:
void huntTarget(); // unique implementation for this monster
void foundTarget(); // ditto
void attackTarget(); // ditto
//...
};

class FlyingMonster : public GameMosterAI {
public:
void huntTarget(); // unique implementation for this monster
void foundTarget(); // ditto
void attackTarget(); // ditto
//...
};

...and you might have loads of different monsters types.

You don't need to know exactly what monster you have to tell it how to huntTarget(), you just need to know that it has that method. This is the root of your "polymorphic" behaviour.

Whatever real monster type you have, simply handling it as an instance of GameMonsterAI and calling the huntTarget() method will invoke the appropriate behavour for the actual monster at hand.

That's about it for virtual functions. Each class that implements a set of virtual functions generally uses a jump table internally, so they're the same thing really.

It's just a nicer syntax :-)

[LP]

yeah.. polymorphism rules, just too bad c++ is such a killer on the 68k's

[bloodline]

Hmmm, But I can't see how virtual functions are applicable to my initial problem, which is to speed up a conditional path... (I've only realised that is what I was trying to achive after I saw Piru's example).

-Edit-
If you look at my original post, I could have written:

switch(a) {


    case 1 : Do_something;
    case 2 : Do_Something_else;
    case 3 : Do_something_different;

}

I'm not sure why I chose to do it the other way... except maybe to eliminate any conditionality from the code.

[bloodline]

So I suppose my question is, How does one eliminate uncertainty from a program :-D

[Karlos]

Jump tables can be much faster than switch/case constructs. The latter often end up like large nested if/else if, especially when the blocks of code are different sizes or if the range has gaps. The further down the switch  you go, the longer it takes.

A function lookup table can be written instead. It totally doesnt matter if the functions are different sizes or if there are holes in the range of cases - provided your overall table is big enough for every known case value.

The function lookup table effectively takes a constant time to evaluate for any case.

I use them in quite a few places where you might think a switch/case would do (I only use the switch/case when the range is small and the code for each case is so small that physically calling the function would take longer).

[Karlos]

LP wrote:
yeah.. polymorphism rules, just too bad c++ is such a killer on the 68k's

It isn't that bad. It all depends on how you design your code - C++ can be more efficient than C code even on 680x0, provided you designed it properly in the first instance (no pun intended).

[bloodline]

Karlos wrote:
Jump tables can be much faster than switch/case constructs. The latter often end up like large nested if/else if, especially when the blocks of code are different sizes or if the range has gaps. The further down the switch  you go, the longer it takes.

Yup, I though I was on the right path... the idea of having to evaluate 60000 odd possible conditions made me panic... The Jumptable/function look up table is the best option!

A function lookup table can be written instead. It totally doesnt matter if the functions are different sizes or if there are holes in the range of cases - provided your overall table is big enough for every known case value.

The function lookup table effectively takes a constant time to evaluate for any case.

"Constant time to evaluate" are the magic words here :-)

I use them in quite a few places where you might think a switch/case would do (I only use the switch/case when the range is small and the code for each case is so small that physically calling the function would take longer).

Have you go any nice and simple, I mean really dumb, examples of function look up's that I can compare and contrast with Piru's? I've never seen these before and I want to get a few in to my brain :-D

[falemagn]

 Jump tables can be much faster than switch/case constructs. The latter often end up like large nested if/else if, especially when the blocks of code are different sizes or if the range has gaps. The further down the switch you go, the longer it takes.

Decent compilers (and gcc is one such), compile switch/case statements down to a jump table for when there are no holes in the range of possibilities, or to a binary search tree in the other case (it prefers saving space, if the range is very sparse).

Therefore, you go from costant time to O(log n) time.

@bloodline

Using functions is perhaps cleaner, but can be overkill for the functions prologue/epilogue. If you are using gcc, you may want to use its "computed goto's" extension.

It works like this (notice the double ampersand!):

Code: [Select]


    void *jmptable[] =
    {
        &&lab1,
        &&lab2,
        &&lab3,
         ...
        &&labN
    };

    ...
    ...

    goto jmptable[foo];
    returnpoint:
    ...

    lab1:
    ...
    goto returnpoint;

    lab2:
    ...
    goto returnpoint;

    lab3:
    ...
    goto returnpoint;

    ...

    labN:
    ...
    goto returnpoint;


This is pretty much like the GOSUB statement from BASIC.

[falemagn]

bloodline wrote:
If you look at my original post, I could have written:

switch(a) {


    case 1 : Do_something;
    case 2 : Do_Something_else;
    case 3 : Do_something_different;

}

I'm not sure why I chose to do it the other way... except maybe to eliminate any conditionality from the code.

If that's really what it would look like, save your efforts for other parts of the code Gcc will compile that down to  a jumptable.