#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>
#include <unistd.h>


typedef unsigned long ulong;

struct node {
	struct node *next;
};


clock_t
one_go(ulong size, ulong count)
{
	ulong len = size / sizeof (struct node);
	struct node array[len];
	ulong indices[len];
	ulong i, j, tmp;
	struct tms timebuf1, timebuf2;
	struct node *p;

	/* helper array */
	for (i=0; i<len; i++) {
		indices[i] = i;
	}
	/* Fisher-Yates shuffle (modern version) */
	for (i=len-1; i>0; i--) {
		j = lrand48() % i;
		tmp = indices[i];
		indices[i] = indices[j];
		indices[j] = tmp;
	}

	/* link pointers accordingly to the helper array */
	for (i=0; i<len-1; i++) {
		array[indices[i]].next = &array[indices[i+1]];
	}
	array[indices[len-1]].next = &array[indices[0]];

	times(&timebuf1);  /* start */
	p = array[0].next;
	while (count-- > 0) {
		p = p->next;
	}
	times(&timebuf2);  /* stop */
		
	return timebuf2.tms_utime - timebuf1.tms_utime;
}


int
main(int argc, char *argv[])
{
#ifndef CLK_TCK
	int CLK_TCK = sysconf(_SC_CLK_TCK);
#endif
	ulong max = 64*1024*1024;  /* in bytes */
	ulong mincount = 512*1024*1024;  /* very large for good results */
	ulong count;
	ulong size;

	for (size=1024; size<=max; size*=2) {
		count = 16 * size;
		if (count < mincount) {
			count = mincount;
		}
		double t = (double) one_go(size, count);
		double avgtime_nano = t / CLK_TCK * 1000000000 / (double)count;
		printf("%lu\t%f\n", size/1024, avgtime_nano);
	}

	return 0;
}