/*
 * usage: time ./testit N
 *      N is a repeat count, set it large enough to get repeatable timings
 */

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

#define ALLOC_MINBITS           3       /* smallest chunk size is 8 bytes */
#define ALLOCSET_NUM_FREELISTS  11

/* number of calls to AllocSetFreeIndex with each result category */
static const int numoccurs[ALLOCSET_NUM_FREELISTS] = {
	2139534,
	5994692,
	5711479,
	3289034,
	4550931,
	2573389,
	487566,
	588470,
	155148,
	52750,
	202597
};

extern int AllocSetFreeIndex_clz(size_t size);
extern int AllocSetFreeIndex_bu(size_t size);
extern int AllocSetFreeIndex(size_t size);

int
main(int argc, char **argv)
{
	int repeat = atoi(argv[1]);
	int k,l,m, min=1000, total=0;
	size_t *arr;
	struct timeval before, after;
	double elapsed;

	for (k=0; k< ALLOCSET_NUM_FREELISTS; k++) 
		total += numoccurs[k]/min;
	
	arr = malloc(sizeof(size_t)*total);

	m = 0;
	for (k=0; k < ALLOCSET_NUM_FREELISTS; k++) 
		for (l=0; l < numoccurs[k]/min; l++)
		{
			int p = 1 << (ALLOC_MINBITS + k);
			p |= (p*2 - 1) & random();
			arr[m++] = p;
		}

	for (m=0; m < total; m++)
	{
		int r = random()%total;
		if (r != m) 
		{
			int tmp = arr[r];
			arr[r] = arr[m];
			arr[m] = tmp;
		}
	}

	repeat *= min;

	static int occurs[ALLOCSET_NUM_FREELISTS];

	for (m=0; m < total; m++)
	{
		int retval_clz = AllocSetFreeIndex_clz(arr[m]);
		int retval_bu  = AllocSetFreeIndex_bu(arr[m]);
		int retval     = AllocSetFreeIndex(arr[m]);
		
		if (retval != retval_clz ||
			retval != retval_bu)
			printf("%08zx: %4d %4d %4d\n", arr[m], retval, retval_clz, retval_bu);
		else
			occurs[retval]++;
	}
	for (k=0; k<ALLOCSET_NUM_FREELISTS; k++)
		printf("%4d: %8d\n", k, occurs[k]);
	
	gettimeofday(&before, NULL);
	for(l=0; l<repeat; l++)
		for (m=0; m < total; m++)
			AllocSetFreeIndex_clz(arr[m]);
	gettimeofday(&after, NULL);
	elapsed = after.tv_sec - before.tv_sec;
	elapsed += (after.tv_usec - before.tv_usec)/1000000.0;
	printf("%20s %.3fs\n", "clz", elapsed);

	gettimeofday(&before, NULL);
	for(l=0; l<repeat; l++)
		for (m=0; m < total; m++)
			AllocSetFreeIndex_bu(arr[m]);
	gettimeofday(&after, NULL);
	elapsed = after.tv_sec - before.tv_sec;
	elapsed += (after.tv_usec - before.tv_usec)/1000000.0;
	printf("%20s %.3fs\n", "bitutils func", elapsed);

	gettimeofday(&before, NULL);
	for(l=0; l<repeat; l++)
		for (m=0; m < total; m++)
			AllocSetFreeIndex(arr[m]);
	gettimeofday(&after, NULL);
	elapsed = after.tv_sec - before.tv_sec;
	elapsed += (after.tv_usec - before.tv_usec)/1000000.0;
	printf("%20s %.3fs\n", "current", elapsed);

	return 0;
}