#include <stdio.h>

#define Assert(condition)

#define ALLOC_MINBITS 3
#define ALLOCSET_NUM_FREELISTS 11
typedef size_t Size;

/*
 * faster version of AllocSetFreeIndex for x86 architecure.
 * this function runs in O(1).
 */
static inline int
AllocSetFreeIndex_new(Size size)
{
    int idx;

    if (__builtin_expect(size < (1 << ALLOC_MINBITS), 0))
		size = (1 << ALLOC_MINBITS);

    /* bsr(Bit Scan Reverse): Search the most significant set bit */
    __asm__ ("bsr %1, %0" :"=r"(idx) :"g"(size - 1));

    return idx - (ALLOC_MINBITS - 1);
}

static inline int
AllocSetFreeIndex(Size size)
{
	int         idx = 0;

	if (size > 0)
	{
		size = (size - 1) >> ALLOC_MINBITS;
		while (size != 0)
		{
			idx++;
			size >>= 1;
		}
		Assert(idx < ALLOCSET_NUM_FREELISTS);
	}

	return idx;
}

int main(int argc, char *argv[])
{
	int		loop_cnt;
	int		size[16];
	int		i, j;
	int		result = 0;

	if(argc < 4) {
		fprintf(stderr, "usage: asettest (new|old) loop_cnt size...\n");
		return 1;
	}

	loop_cnt = atoi(argv[2]);

	for(i = 0; i < 16; i++) {
		if(argc <= i + 3) {
			size[i] = size[0];
		} else {
			size[i] = atoi(argv[i + 3]);
		}
	}

	if(strcmp(argv[1], "new") == 0) {
		for(i = 0; i < loop_cnt; i++) {
			for(j = 0; j < 16; j++) {
				result += AllocSetFreeIndex_new(size[j]);
			}
		}
	} else if(strcmp(argv[1], "old") == 0) {
		for(i = 0; i < loop_cnt; i++) {
			for(j = 0; j < 16; j++) {
				result += AllocSetFreeIndex(size[j]);
			}
		}
	} else {
		fprintf(stderr, "usage: asettest (new|old) size loop_cnt\n");
		return 1;
	}

	fprintf(stderr, "%s, size:%d, loop:%d, checksum:%d\n",
		argv[1], size[0], loop_cnt, result);

	return 0;
}