#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stddef.h>

#define FirstLowInvalidHeapAttributeNumber		(-8)
#define FLEXIBLE_ARRAY_MEMBER 1

#define elog(elevel, s)  \
	do { \
		printf("%s\n", s); \
		exit(EXIT_FAILURE); \
	} while(0)


#define BITS_PER_BITMAPWORD 32
#define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x)	((x) % BITS_PER_BITMAPWORD)

#define BITMAPSET_SIZE(nwords)	\
	(offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))

typedef unsigned int bitmapword;		/* must be an unsigned type */
typedef int signedbitmapword; /* must be the matching signed type */
typedef char bool;

#define true 1
#define false 0

typedef struct Bitmapset
{
	int			nwords;			/* number of words in array */
	bitmapword	words[FLEXIBLE_ARRAY_MEMBER];	/* really [nwords] */
} Bitmapset;

void *
palloc0(size_t size)
{
	void *p = malloc(size);
	if (!p)
		elog(ERROR, "out of memory");
	memset(p, 0, size);
	return p;
}
/*
 * bms_is_member - is X a member of A?
 */
bool
bms_is_member(int x, const Bitmapset *a)
{
	int			wordnum,
				bitnum;

	/* XXX better to just return false for x<0 ? */
	if (x < 0)
		elog(ERROR, "negative bitmapset member not allowed");
	if (a == NULL)
		return false;
	wordnum = WORDNUM(x);
	bitnum = BITNUM(x);
	if (wordnum >= a->nwords)
		return false;
	if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
		return true;
	return false;
}

static const unsigned char rightmost_one_pos[256] = {
	0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

int
bms_next_member(const Bitmapset *a, int prevbit)
{
	int			nwords;
	int			wordnum;
	bitmapword	mask;

	if (a == NULL)
		return -2;
	nwords = a->nwords;
	prevbit++;
	mask = (~(bitmapword) 0) << BITNUM(prevbit);
	for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
	{
		bitmapword	w = a->words[wordnum];

		/* ignore bits before prevbit */
		w &= mask;

		if (w != 0)
		{
			int			result;

			result = wordnum * BITS_PER_BITMAPWORD;
			while ((w & 255) == 0)
			{
				w >>= 8;
				result += 8;
			}
			result += rightmost_one_pos[w & 255];
			return result;
		}

		/* in subsequent words, consider all bits */
		mask = (~(bitmapword) 0);
	}
	return -2;
}

Bitmapset *
bms_make_singleton(int x)
{
	Bitmapset  *result;
	int			wordnum,
				bitnum;

	if (x < 0)
		elog(ERROR, "negative bitmapset member not allowed");
	wordnum = WORDNUM(x);
	bitnum = BITNUM(x);
	result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
	result->nwords = wordnum + 1;
	result->words[wordnum] = ((bitmapword) 1 << bitnum);
	return result;
}


int
has_system_columns(Bitmapset  *attrs_used)
{
	int i;
	for (i = FirstLowInvalidHeapAttributeNumber + 1; i < 0; i++)
	{
		if (bms_is_member(i - FirstLowInvalidHeapAttributeNumber, attrs_used))
		{
			return 1;
		}
	}
	return 0;
}

int has_system_columns2(Bitmapset  *attrs_used)
{
	int first = bms_next_member(attrs_used, -1);
	if (first >= 0 && first < -FirstLowInvalidHeapAttributeNumber)
		return 1;
	return 0;
}

#define LOOPS 100000000
int main(void)
{
	clock_t start, finish;
	int firstcol;
	
	for (firstcol = 1; firstcol <= 1024; firstcol <<= 1)
	{
		int loop;
		int dummycounter;
		Bitmapset *attrs_used = bms_make_singleton(firstcol - FirstLowInvalidHeapAttributeNumber);
		
		start = clock();
		
		for (loop = 0; loop <= LOOPS; loop++)
			dummycounter += has_system_columns(attrs_used);
		
		finish = clock();
		
		printf("%d has_system_columns complete in %f\n", firstcol, (double) (finish - start) / CLOCKS_PER_SEC);

		start = clock();
		
		for (loop = 0; loop <= LOOPS; loop++)
			dummycounter += has_system_columns2(attrs_used);
		
		finish = clock();
		
		printf("%d has_system_columns2 complete in %f\n", firstcol, (double) (finish - start) / CLOCKS_PER_SEC);
		
	}
}