#include <stdio.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <malloc.h>

char **buff = NULL;
int zzz;
unsigned bsize;
unsigned bmask;
unsigned repeat;
#define LOAD 0x8000000

struct rusage ru_before, ru_after;

void mkbuff(unsigned size)
{
	int i;
	int l, m;
	char **j, **k;
	unsigned mm;

	if (buff != NULL) free(buff);
	if ((buff = (char **)malloc(size + sizeof(char *))) == NULL) {
		fprintf(stderr, "MALLOC\n");
		exit(-1);
	}
	bsize = size / sizeof(unsigned *);
	repeat = LOAD / bsize;
	bmask = 0xffffffff - bsize;
	for (mm = 0x80000000; (mm & bsize) == 0; mm >>= 1) {
		bmask -= mm;
	}
	for (m = -1, l = bmask; l >= 0; m++) {
		l = l << 1;
	}
	for (i = 0; i < bsize - 1; i++) buff[i] = NULL;
	k = &buff[0];
	for (i = 0; i < bsize; i++) {
		do {
			j = &buff[(rand() >> m) & bmask];
		} while (*j != NULL);
		*k = j;
		k = j;
	}
	*k = &buff[0];
//	printf("%08x,%08x %d\r", bsize, bmask, m);
}

void rtest()
{
	int i, j, k;
	for (i = 0; i < repeat; i++) {
		for (j = 0; j < bsize; j++) {
	//		buff[rand() & bmask]++ ;
		}
	}
}

int test()
{
	int i, j;
	char **k;
	int s;
	k = buff[0];
	for (i = 0; i < repeat; i++) {
		for (j = 0; j < bsize; j++) {
			k = *k;
			s += (int) k;
		}
	}
	return s;
}

void test0()
{
	int i, j, k;
	for (j = 0; j < bsize-10; j++) {
	//  buff[j] = buff[j + 1];
	}
}

main(int argc, char *argv[])
{
	unsigned i;
	unsigned tb, ta;

	for (i = 256; i < 0x800000; i <<= 1) {
		mkbuff(i);
//		test0();
		getrusage(RUSAGE_SELF, &ru_before);
		zzz += test();
		getrusage(RUSAGE_SELF, &ru_after);
		tb = ru_before.ru_utime.tv_usec + ru_before.ru_utime.tv_sec * 1000000;
		ta = ru_after.ru_utime.tv_usec + ru_after.ru_utime.tv_sec * 1000000;
		printf("%d,%d \n", i, ta - tb);
	}
}