#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>

typedef uintptr_t T;

volatile int theone = 2;

T core [1024 * 1024];
T *free_pointer = core;

double now (void)
{
  struct timeval tv;
  gettimeofday (&tv, NULL);
  return tv.tv_sec + tv.tv_usec * 1e-6;
}

#define ptr(x) ((volatile T*)(x))

T car (T x)
{
  T r = ptr(x)[0];
  return r;
}

T cdr (T x)
{
  T r = ptr(x)[1];
  return r;
}

T car_fw (T x)
{
  T r = ptr(x)[0];
  if (r & 1)
    return ptr(r-1)[0];
  else
    return r;
}

T cdr_fw (T x)
{
  T r = ptr(x)[1];
  if (r & 1)
    return ptr(r-1)[0];
  else
    return r;
}

T cons (T x, T y)
{
  T res = (T)free_pointer;
  ptr(res)[0] = x;
  ptr(res)[1] = y;
  free_pointer += 2;
  return res;
}

T make_list (size_t n)
{
  T res = 0;
  while (n--)
    res = cons (theone, res);
  return res;
}

T traverse (T q)
{
  T s = 0;
  while (q)
    {
      s += car (q);
      q = cdr (q);
    }
  return q;
}

T traverse_fw (T q)
{
  T s = 0;
  while (q)
    {
      s += car_fw (q);
      q = cdr_fw (q);
    }
  return s;
}

volatile T sum;

int main (int argc, char **argv)
{
  T q;
  unsigned n, m, i;
  double t, t1, t2;
  
  (void)argc;
  (void)argv;

  n = 10000;
  m = 1000000;
  q = make_list (n);

  printf ("n = %u, m = %u\n", n, m);

  t = now();
  i = m;
  while (i--)
    sum = traverse (q);
  t1 = (now() - t);
  printf ("w/o forwarding  %gms\n", t1*1000);
  
  t = now();
  i = m;
  while (i--)
    sum = traverse_fw (q);
  t2 = (now() - t);
  printf ("with forwarding %gms\n", t2*1000);
  printf ("overhead = %g%%\n", (1.0 - t2/t1) * 100);
  
  return 0;
}