/* Testing different schemes of dynamic dispatch. */
/* Link with -lrt */
/* Sam Danielson 2009 */

#include <stdio.h>
#include <time.h>

#define ITERATIONS 1000000
#define DEPTH 200

/* Returns microseconds since _from_, sets _from to current time. */
long laptime_usec (struct timespec *from) {
  struct timespec now;
  clock_gettime (CLOCK_THREAD_CPUTIME_ID, &now);
  long t = ((now.tv_sec - from->tv_sec) * 1000000L + (now.tv_nsec - from->tv_nsec) / 1000);
  *from = now;
  return t;
}

/* Our types. */
typedef enum {
  TYPE_INVAL,
  TYPE_VIRTUAL,
  TYPE_FUNC_TABLE,
  TYPE_FUNC_TABLE_DYNAMIC,
  TYPE_SWITCH,
  TYPE_SWITCH_INLINE,
  TYPE_SWITCH_DISPERSED,
  TYPE_SWITCH_LARGE,
  TYPE_FUNC_TABLE_SUBTRACT = 999,
} Type;

/* We might wish to define the beginning index of a function table. */
#define TYPE_SUBTRACT_BEGIN TYPE_FUNC_TABLE_SUBTRACT

/* Make a classed type with a vtable. */
typedef struct _FooClass FooClass;
typedef struct _Foo Foo;

void foo_virtual (Foo *, int);
void func_table_func (Foo *, int);
void func_table_subtract_func (Foo *, int);
void func_table_dynamic_func (Foo *, int);
void func_switch_func (Foo *, int);
void func_switch_dispersed_func (Foo *, int);
void func_switch_large_func (Foo *self, int);

struct _FooClass {
  /* Type not used for vtable dispatch. Most object systems want it though. */
  Type type;
  /* The virtual function table */
  void (*func0)(Foo*, int);
  void (*func1)(Foo*, int);
  void (*func2)(Foo*, int);
  void (*virtual)(Foo*, int);
  void (*func4)(Foo*, int);
  void (*func5)(Foo*, int);
  void (*func6)(Foo*, int);
  void (*func7)(Foo*, int);
};
FooClass foo_class = {
  TYPE_INVAL,
  0,
  0,
  0,
  foo_virtual,
};

struct _Foo {
  /* class for vtable dispatch */
  FooClass *klass;
  /* type for unclassed dispatch */
  Type type;
  int member;
};

void foo_virtual (Foo *self, int depth_to_go) {
  if (! depth_to_go) return;
  /* Calls itself via the class's vtable. */
  self->klass->virtual (self, depth_to_go - 1);
  self->klass = &foo_class;
}

/* Make a function table and function using unclassed dispatch via indexed table. */
void (* func_table[])(Foo*, int) = {
  0,
  0,
  func_table_func,
  func_table_dynamic_func,
  0,
  0,
  0,
  0,
};

/* A pointer to point to a function table */
void (** func_table_dynamic)(Foo*, int);

void (* func_table_for_big_index[])(Foo*, int) = {
  func_table_subtract_func,
};

void func_table_func (Foo *self, int depth_to_go) {
  if (! depth_to_go) return;
  /* Calls itself via the function table */
  func_table[self->type] (self, depth_to_go - 1);
  self->member++;
}

/* Same but deny the compiler a static function table. */
void func_table_dynamic_func (Foo *self, int depth_to_go) {
  if (! depth_to_go) return;
  /* Calls itself via global pointer to the function table */
  func_table_dynamic[self->type] (self, depth_to_go - 1);
  self->member++;
}

/* Useful for if the method is only useful for indexes of e.g. 995-1000. */
/* Rather than make a mostly empty table we just adjust the index to 0. */
/* The compiler should fold the constant offset into the table's address. */
void func_table_subtract_func (Foo *self, int depth_to_go) {
  if (! depth_to_go) return;
  func_table_for_big_index[self->type - TYPE_SUBTRACT_BEGIN] (self, depth_to_go - 1);
  self->member++;
}

/* Make a switching function and function to use it for unclassed dispatch.  */
void func_switch (Foo *foo, int depth_to_go) {
  switch (foo->type) {
  case 0: func_switch_func (foo, depth_to_go);
	return;
  case 1: func_switch_func (foo, depth_to_go);
	return;
  case 2: func_switch_func (foo, depth_to_go);
	return;
  case 3: func_switch_func (foo, depth_to_go);
	return;
  case TYPE_SWITCH: func_switch_func (foo, depth_to_go);
	return;
  case TYPE_SWITCH_INLINE: {
	if (! depth_to_go) return;
	func_switch (foo, depth_to_go - 1);
	foo->member++;
  }
	return;
  case 6: func_switch_func (foo, depth_to_go);
	return;
  case 7: func_switch_func (foo, depth_to_go);
	return;
  }
}

void func_switch_func (Foo *self, int depth_to_go) {
  if (! depth_to_go) return;
  /* Calls itself via the switch function */
  func_switch (self, depth_to_go - 1);
  self->member++;  
}


/* A switch statement with dispersed types. */
/* Useful for sparse domains. */
void func_switch_dispersed (Foo *foo, int depth_to_go) {
  switch (foo->type) {
	/* modify args on non-existant types to befuddle optimizer (maybe paranoid) */
  case 10000: func_switch_dispersed_func (foo, depth_to_go + 2);
	break;
  case 2394303L: func_switch_dispersed_func (foo, depth_to_go + 1);
	break;
  case 23: func_switch_dispersed_func (foo, depth_to_go + 3);
	break;
  case -1093: func_switch_dispersed_func (foo, depth_to_go + 13);
	break;
  case 3444: func_switch_dispersed_func (foo, depth_to_go + 4);
	break;
  case 342: func_switch_dispersed_func (foo, depth_to_go + 42);
	break;
	/* This is the existing type foo. */
  case TYPE_SWITCH_DISPERSED: func_switch_dispersed_func (foo, depth_to_go);
	break;
  case 493049283L: func_switch_dispersed_func (foo, depth_to_go + 3);
	break;
  }
}

void func_switch_dispersed_func (Foo *self, int depth_to_go) {
  if (! depth_to_go) return;
  /* Calls itself via the dispersed switch function. */
  func_switch_dispersed (self, depth_to_go - 1);
  self->member++;  
}

void func_switch_large (Foo *foo, int depth_to_go) {
  switch (foo->type) {
	/* modify args on non-existant types to befuddle optimizer (maybe paranoid) */
  case 13002: func_switch_dispersed_func (foo, depth_to_go + 2);
	break;
  case 23943453L: func_switch_dispersed_func (foo, depth_to_go + 1);
	break;
  case 2343: func_switch_dispersed_func (foo, depth_to_go + 3);
	break;
  case -1693: func_switch_dispersed_func (foo, depth_to_go + 13);
	break;
  case 11444: func_switch_dispersed_func (foo, depth_to_go + 4);
	break;
  case 8341: func_switch_dispersed_func (foo, depth_to_go + 42);
	break;
  case 10300: func_switch_dispersed_func (foo, depth_to_go + 2);
	break;
  case 2394353L: func_switch_dispersed_func (foo, depth_to_go + 1);
	break;
  case 5243: func_switch_dispersed_func (foo, depth_to_go + 3);
	break;
  case -1493: func_switch_dispersed_func (foo, depth_to_go + 13);
	break;
  case 12444: func_switch_dispersed_func (foo, depth_to_go + 4);
	break;
  case 9342: func_switch_dispersed_func (foo, depth_to_go + 42);
	break;
  case 493049283L: func_switch_dispersed_func (foo, depth_to_go + 3);
	break;
  case TYPE_SWITCH_LARGE: func_switch_large_func (foo, depth_to_go);
	break;
  case 2394603L: func_switch_dispersed_func (foo, depth_to_go + 1);
	break;
  case 1243: func_switch_dispersed_func (foo, depth_to_go + 3);
	break;
  case -1083: func_switch_dispersed_func (foo, depth_to_go + 13);
	break;
  case 34: func_switch_dispersed_func (foo, depth_to_go + 4);
	break;
  case 18332: func_switch_dispersed_func (foo, depth_to_go + 42);
	break;
  case 10700: func_switch_dispersed_func (foo, depth_to_go + 2);
	break;
  case 2394303L: func_switch_dispersed_func (foo, depth_to_go + 1);
	break;
  case 213: func_switch_dispersed_func (foo, depth_to_go + 3);
	break;
  case -1043: func_switch_dispersed_func (foo, depth_to_go + 13);
	break;
  case 3434: func_switch_dispersed_func (foo, depth_to_go + 4);
	break;
  case 3342: func_switch_dispersed_func (foo, depth_to_go + 42);
	break;
  case 10040: func_switch_dispersed_func (foo, depth_to_go + 2);
	break;
  case 5239: func_switch_dispersed_func (foo, depth_to_go + 1);
	break;
  case 230: func_switch_dispersed_func (foo, depth_to_go + 3);
	break;
  case -1093: func_switch_dispersed_func (foo, depth_to_go + 13);
	break;
  case 3449: func_switch_dispersed_func (foo, depth_to_go + 4);
	break;
  case 342: func_switch_dispersed_func (foo, depth_to_go + 42);
	break;
  }
}

void func_switch_large_func (Foo *self, int depth_to_go) {
  if (! depth_to_go) return;
  func_switch_large (self, depth_to_go - 1);
  self->member++;  
}

void foo_direct (Foo *self, int depth_to_go) {
  if (! depth_to_go) return;
  /* Calls itself directly */
  foo_direct (self, depth_to_go - 1);
  self->member++;
}

void do_virtual (void) {
  Foo foo = { &foo_class, TYPE_VIRTUAL, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	foo.klass->virtual (&foo, DEPTH);
  }
}

void do_func_table (void) {
  Foo foo = { NULL, TYPE_FUNC_TABLE, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	func_table[foo.type] (&foo, DEPTH);
  }
}

void do_func_table_sutract (void) {
  Foo foo = { NULL, TYPE_FUNC_TABLE_SUBTRACT, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	func_table_for_big_index[foo.type - TYPE_SUBTRACT_BEGIN] (&foo, DEPTH);
  }
}

void do_func_table_dynamic (void) {
  func_table_dynamic = func_table;
  Foo foo = { NULL, TYPE_FUNC_TABLE_DYNAMIC, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	func_table_dynamic[foo.type] (&foo, DEPTH);
  }
}

void do_func_switch_inline (void) {
  Foo foo = { NULL, TYPE_SWITCH_INLINE, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	func_switch (&foo, DEPTH);
  }
}

void do_func_switch (void) {
  Foo foo = { NULL, TYPE_SWITCH, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	func_switch (&foo, DEPTH);
  }
}

void do_func_switch_dispersed (void) {
  Foo foo = { NULL, TYPE_SWITCH_DISPERSED, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	func_switch_dispersed (&foo, DEPTH);
  }
}

void do_func_switch_large (void) {
  Foo foo = { NULL, TYPE_SWITCH_LARGE, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	func_switch_large (&foo, DEPTH);
  }
}

void do_direct (void) {
  Foo foo = { NULL, TYPE_INVAL, 42 };
  unsigned long i;
  for (i = 0; i < ITERATIONS; i++) {
	foo_direct (&foo, DEPTH);
  }
}

int main (int argc, char **argv) {
  
  struct timespec start;
  clock_gettime (CLOCK_THREAD_CPUTIME_ID, &start);

  do_virtual ();
  printf ("Classed virtual: %ld\n", laptime_usec (&start));

  do_func_table ();
  printf ("Function table: %ld\n", laptime_usec (&start));

  do_func_table_sutract ();
  printf ("Function table with subtraction: %ld\n", laptime_usec (&start));

  do_func_table_dynamic ();
  printf ("Function table dynamic: %ld\n", laptime_usec (&start));

  do_func_switch_inline ();
  printf ("Switch inline code: %ld\n", laptime_usec (&start));

  do_func_switch ();
  printf ("Function switch: %ld\n", laptime_usec (&start));

  do_func_switch_large ();
  printf ("Function switch large: %ld\n", laptime_usec (&start));

  do_func_switch_dispersed ();
  printf ("Function switch dispersed: %ld\n", laptime_usec (&start));

  do_direct ();
  printf ("Direct call: %ld\n", laptime_usec (&start));

  return 0;
}