#define BLCKSZ 8192
#define MaxHeapTuplesPerPage 291

typedef unsigned long long int64;
typedef unsigned short uint16;
typedef short int16;

typedef union PGAlignedBlock
{
	char		data[BLCKSZ];
	double		force_align_d;
	int64		force_align_i64;
} PGAlignedBlock;

typedef struct PageHeader
{
	int pd_lower;
	int pd_upper;
	int pd_special;
} PageHeader;

typedef struct itemIdCompactData
{
	uint16		offsetindex;	/* linp array index */
	int16		itemoff;		/* page offset of item data */
	uint16		alignedlen;		/* MAXALIGN(item data len) */
} itemIdCompactData;
typedef itemIdCompactData *itemIdCompact;

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

static int
itemoffcompare(const void *itemidp1, const void *itemidp2)
{
	/* Sort in decreasing itemoff order */
	return rand() > RAND_MAX / 2 ? 1 : -1;
}

void
make_itemIdCompactData_array(itemIdCompactData *array, int size, int tupwidth)
{
	int i;
	int pd_upper = BLCKSZ;
	
	if (size * tupwidth > BLCKSZ)
	{
		fprintf(stderr, "tuple data bigger than BLCKSZ\n");
		exit(-1);
	}
	
	for (i = 0; i < size; i++)
	{
		pd_upper -= tupwidth;
		array[i].offsetindex = i + 1;
		array[i].itemoff = pd_upper;
		array[i].alignedlen = tupwidth;
	}
	
	qsort((char *) array, size, sizeof(itemIdCompactData), itemoffcompare);
}

void
print_itemIdCompactData_array(itemIdCompactData *array, int size)
{
	int i;
	
	for (i = 0; i < size; i++)
	{
		itemIdCompact	itemidptr = &array[i];
		printf("item[%d] offset: %d, len: %u\n", itemidptr->offsetindex, itemidptr->itemoff, itemidptr->alignedlen);
	}
}

static void
compactify_tuples(itemIdCompact itemidbase, int nitems, int totaltups, PGAlignedBlock *page, PageHeader *phdr)
{
	int		upper;
	PGAlignedBlock scratch;
	char	   *scratchptr = scratch.data;
	int			i;

	/*
	 * The tuples in the itemidbase array may be in any order so in order to
	 * move these to the end of the page we must make a temp copy of each
	 * tuple before we copy them back into the page at the new position.
	 *
	 * If a large number of the tuples have been pruned (>75%) then we'll copy
	 * these into the temp buffer tuple-by-tuple, otherwise we'll just copy
	 * the entire tuple section of the page in a single memcpy().  Doing this
	 * saves us doing large copies when we're pruning most of the tuples.
	 */
	if (nitems < totaltups / 2)
	{
		for (i = 0; i < nitems; i++)
		{
			itemIdCompact	itemidptr = &itemidbase[i];
			memcpy(scratchptr + itemidptr->itemoff, page->data + itemidptr->itemoff,
				   itemidptr->alignedlen);
		}
	}
	else
	{
		/* Copy the entire tuple space */
		memcpy(scratchptr + phdr->pd_upper,
			   page->data + phdr->pd_upper,
			   phdr->pd_special - phdr->pd_upper);
	}

	upper = BLCKSZ;
	for (i = 0; i < nitems; i++)
	{
		itemIdCompact	itemidptr = &itemidbase[i];

		upper -= itemidptr->alignedlen;
		memcpy((char *) page + upper,
			   scratchptr + itemidptr->itemoff,
			   itemidptr->alignedlen);
	}
}



int main(int argc, char **argv)
{
	int tupwidth;
	int ntuples;
	int unprunedtups;
	PGAlignedBlock page;
	PageHeader header;
	clock_t start, end;
	int i;
	int t;
	
	if (argc < 3)
	{
		printf("Usage: %s <tupwidth> <ntuples>\n", argv[0]);
		return -1;
	}
	
	tupwidth = atoi(argv[1]);
	ntuples = atoi(argv[2]);
	
	if (ntuples > MaxHeapTuplesPerPage)
	{
		printf("ntuples cannot be above %d\n", MaxHeapTuplesPerPage);
		return -1;
	}
	
	header.pd_lower = 0;
	header.pd_upper = BLCKSZ - tupwidth * ntuples;
	header.pd_special = BLCKSZ;
	
	itemIdCompactData itemidbase[MaxHeapTuplesPerPage];

	for (unprunedtups = 1; unprunedtups < ntuples; unprunedtups++)
	{

		make_itemIdCompactData_array(itemidbase, unprunedtups, tupwidth);
	
		start = clock();
		for (i = 0; i < 1000000; i++)
			compactify_tuples(itemidbase, unprunedtups, ntuples, &page, &header);
		end = clock();
		
		printf("%d : %g msec\n", unprunedtups, (double) (end - start) / CLOCKS_PER_SEC * 1000);
	}
	return 0;
}