trash.txt

#include <pthread.h>
#include <assert.h>
#include <math.h>
#include <stdint.h>
#include <stdbool.h>

#define MAX_TNODES 200
#define MAX_PRI_SIZE 3

typedef struct tnode_t
{
	int num_ch;
	pthread_rwlock_t lock;
	//priority of node
	uint32_t pri_bits; 
	uint64_t pri[MAX_PRI_SIZE];
	//stored pointer to game state
	void* v; 
	//related nodes
	struct tnode_t* parent;
	struct tnode_t* ch[MAX_TNODES];	
}tnode;

#define shift_d64(val, num_shift) (((num_shift) == 64) ? (0x0000000000000000) : (val >> num_shift))
#define shift_u64(val, num_shift) (((num_shift) == 64) ? (0x0000000000000000) : (val << num_shift))

//not safe to use with the same address
//function works only for more than 0 zero chunks
inline void shift_down64(uint64_t* n_64_num, uint64_t* p_64_num, uint32_t n_bits)
{
	int i;
	//multiples of 64 bits to shift
	int m_64 = n_bits >> 6;	
	//remainder bits
	int r_bits = n_bits - (m_64*64); 
	//boundary for copying the rest of the chunks
	int b_cpy = MAX_PRI_SIZE - m_64 - 1;
	//printf("b_cpy = %d, m_64 = %d, r_bits = %d\n", b_cpy, m_64, r_bits);
	//set all top m_64 chucks to zero chunks, note MAX_PRI_SIZE>m_64 -> MAX_PRI_SIZE-m_64>0 
	//printf("---\n");
	//printf("n_bits = %d\n", n_bits);
	assert(n_bits <= (MAX_PRI_SIZE*64));
	for(i = MAX_PRI_SIZE-1; i > b_cpy; i--)
	{
		//printf("%d\n", i);
		n_64_num[i] = 0;
	}
	//first chunk is appended with r_bits of zeros
	n_64_num[b_cpy] = 0 | shift_d64(p_64_num[MAX_PRI_SIZE-1], r_bits);
	//chunks from from the MAX_PRI_SIZE - m_64 - 1 + m_64
	//printf("%016llX", p_64_num[i]);
	//printf("---\n");
	for(i = b_cpy-1; i >= 0; i--)
	{
		assert((((i) >= 0 && (i) < MAX_PRI_SIZE) && ((m_64+i) >= 0 && (m_64+i) < MAX_PRI_SIZE)));
		assert(((i+m_64+1) >= 0 && (i+m_64+1) < MAX_PRI_SIZE));
		//printf("%d, i+m_64+1 = %d, i+m_64 = %d\n", i, i+m_64+1, i+m_64);
		//MAX_PRI_SIZE - m_64 - 2 ... 0 [i]
		//MAX_PRI_SIZE - 1 ... m_64 + 1 [i+m_64+1]
		//MAX_PRI_SIZE - 2 ... m_64 	[i+m_64]
		n_64_num[i] = shift_u64(p_64_num[i+m_64+1], (64-r_bits)) | shift_d64(p_64_num[i+m_64], r_bits);
	}
	//printf("---\n");
		
}
//not safe to use with the same address
//function works only for more than 0 zero chunks
inline void shift_up64(uint64_t* n_64_num, uint64_t* p_64_num, uint32_t n_bits)
{
	int i;
	//multiples of 64 bits to shift
	int m_64 = n_bits >> 6;	
	//remainder bits
	int r_bits = n_bits - (m_64*64); 
	//printf("n_bits = %d, r_bits = %d\n", n_bits, r_bits);
	//set all m_64 chucks to zero chunks
	assert(n_bits <= (MAX_PRI_SIZE*64));
	for(i = 0; i < m_64; i++)
	{
		n_64_num[i] = 0;
	}
	//first chunk is appended with r_bits of zeros
	n_64_num[m_64] = shift_u64(p_64_num[0], r_bits) | 0;
	//assume there is atleast one chunk
	//printf("----\n");
	for(i = 1; i < MAX_PRI_SIZE-m_64; i++)
	{
		assert((((i) >= 0 && (i) < MAX_PRI_SIZE) && ((m_64+i) >= 0 && (m_64+i) < MAX_PRI_SIZE)));
		assert(((i-1) >= 0 && (i-1) < MAX_PRI_SIZE));
		//printf("i  = %d, m_64+i = %d, i = %d, i-1 = %d\n", i, m_64+i, i, i-1);
		//[i] 		1 ... MAX_PRI_SIZE - m_64 - 1
		//[m_64+i] 	1+m_64 .. MAX_PRI_SIZE - 1 
		//[i]		1 ... MAX_PRI_SIZE - m_64 - 1
		//[i-1]		0 ... MAX_PRI_SIZE - m_64 - 2
		n_64_num[m_64+i] = shift_u64(p_64_num[i], r_bits) | shift_d64(p_64_num[i-1], (64 - r_bits));
	}
	//printf("----\n");
}
inline int eq(uint64_t* pri_1, uint64_t* pri_2, int n_chunks)
{	
	n_chunks -= 1;
	while(n_chunks >= 0)
	{
		if(pri_1[n_chunks] != pri_2[n_chunks])
			return false;
		n_chunks--;	
	}
	return true;
}
inline int lt(uint64_t* pri_1, uint64_t* pri_2, int n_chunks)
{
	n_chunks -= 1;
	while(n_chunks >= 0)
	{
		if(pri_1[n_chunks] < pri_2[n_chunks])
			return true;
		else if(pri_1[n_chunks] > pri_2[n_chunks])
			return false;

		n_chunks--;	
	}
	return false;
}
inline int gt(uint64_t* pri_1, uint64_t* pri_2, int n_chunks)
{
	n_chunks -= 1;
	while(n_chunks >= 0)
	{
		if(pri_1[n_chunks] > pri_2[n_chunks])
			return true;
		else if (pri_1[n_chunks] < pri_2[n_chunks])
			return false;

		n_chunks--;
	}
	return false;
}

inline tnode* tnode_init()
{
	return (tnode*)malloc(sizeof(tnode));
} 

inline void tnode_set_pri(tnode* parent, tnode* child, int n_child, int bits_childs)
{
	// 0 <= n_childs < 2^(bits_childs)
	shift_up64(child->pri, parent->pri, bits_childs); 
	child->pri[0] |= n_child;
	// set the number of priority bits in the child
	child->pri_bits = parent->pri_bits + bits_childs;
} 
inline void tnode_free(tnode* tn)
{
	free(tn);
}

inline void tnode_print_pri(uint64_t* p_64_num, int n_bits)
{
	int i;
	printf("pri_bits = %d pri = ", n_bits);
	for(i = MAX_PRI_SIZE-1; i >= 0; i--)
		printf("%016llX", p_64_num[i]);
	printf("\n");
}
//implemented only with less than and greater than
int pri_compare(void* tn_va, void* tn_vb)
{
	tnode* tn_a = (tnode*)tn_va;
	tnode* tn_b = (tnode*)tn_vb;	
	int tn_diff, atn_diff;
	uint64_t pri_n[MAX_PRI_SIZE];	

	tn_diff = (tn_a->pri_bits) - (tn_b->pri_bits);
	atn_diff = abs(tn_diff);
	if(tn_diff >= 0)//tn_a has more pri bits so normalize tn_a pri
	{
		shift_up64(pri_n, tn_b->pri, atn_diff);
		if(lt(tn_a->pri, pri_n, MAX_PRI_SIZE))
			return -1;
		else if(gt(tn_a->pri, pri_n, MAX_PRI_SIZE))
			return 1; 
		else 
			if(tn_diff > 0)
				return 1;
			else if(tn_diff == 0)
				return 0;
			else 
				assert(0);
	}
	else //tn_b has more pri bits ...
	{
		shift_up64(pri_n, tn_a->pri, atn_diff);
		if(lt(pri_n, tn_b->pri, MAX_PRI_SIZE))
			return -1;
		else if(gt(pri_n, tn_b->pri, MAX_PRI_SIZE))
			return 1;
		else	//tn_b has more pri bits therefore a is smaller
			return -1;
	}
}


//testing arrays
uint64_t arrays[10][4]= {{0,0,0,0},
			{2,0,0,0},
			{3,0,0,0},
			{2,1,0,0},
			{4,4,0,0},
			{4,5,0,0},
			{4,6,0,0},
			{2,2,0,0},
			{3,4,0,0},
			{3,5,0,0}}; 
/*
uint64_t array1[3] = {-1, -1, 0xF000000FF000000F};
uint64_t array2[3] = {0, -1, 0};
uint64_t array3[3] = {0, -1, -1};
uint64_t array4[3] = {-1, -1, -1};
uint64_t array5[3] = {0, 0, 0};
uint64_t array6[3] = {0, 0, 0};
*/
char val_num = 33;
//testing the ppq enqueue prioritization bits
void tnode_add_rec(pp_queue* ppq, tnode* parent, int d)
{
	int i;
	tnode* tns;
	if(d == 0)
		return;
	tns = malloc(sizeof(tnode)*4);
	for(i = 0; i < 4; i++)
	{
		tnode_set_pri(parent, tns+i, i, 2);
		(tns+i)->v = (void*)val_num;
		val_num++;
		ppq_enqueue(ppq, tns+i);
		tnode_add_rec(ppq, tns+i, d-1);
	}
}
void tnode_test(void)
{
	/* TEST SHIFTING
	int i;
	printf("%d ", eq(array1, array1, MAX_PRI_SIZE));
	printf("%d ", lt(array1, array1, MAX_PRI_SIZE));
	printf("%d ", gt(array1, array1, MAX_PRI_SIZE));
	tnode_print_pri(array1, 30);
	for(i = 0; i < MAX_PRI_SIZE*64 + 1; i++)
	{
		shift_down64(array6,array1, i);	
		printf("%d ", eq(array6, array1, MAX_PRI_SIZE));
		printf("%d ", lt(array6, array1, MAX_PRI_SIZE));
		printf("%d ", gt(array6, array1, MAX_PRI_SIZE));
		tnode_print_pri(array6, 30);
	}
	*/
	//tnode_print_pri(array1, 30);
	/*
	printf("TEST down\n");
	printf("---\n");
	shift_down64(array6,array1,8);	
	tnode_print_pri(array1, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	shift_down64(array6,array2,20);	
	tnode_print_pri(array2, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	shift_down64(array6,array3,20);	
	tnode_print_pri(array3, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	shift_down64(array6,array4,20);	
	tnode_print_pri(array4, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	shift_down64(array6,array5,20);	
	tnode_print_pri(array5, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	printf("TEST up\n");
	printf("---\n");
	shift_up64(array6,array1,8);	
	tnode_print_pri(array1, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	shift_up64(array6,array2,20);	
	tnode_print_pri(array2, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	shift_up64(array6,array3,20);	
	tnode_print_pri(array3, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	shift_up64(array6,array4,20);	
	tnode_print_pri(array4, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	shift_up64(array6,array5,20);	
	tnode_print_pri(array5, 30);
	tnode_print_pri(array6, 30);
	printf("---\n");
	*/
	/* TESTINT THE PAPER EXAMPLE TREE (WORKS)
	int i;
	tnode* nodes = (tnode*)malloc(sizeof(tnode)*10);
	pp_queue* ppq = (pp_queue*)ppq_create(10, pri_compare);
	for(i = 0; i < 10; i++)
	{
		(nodes+i)->pri_bits = arrays[i][0];	
		((nodes+i)->pri)[0] = arrays[i][1];	
		((nodes+i)->pri)[1] = arrays[i][2];	
		((nodes+i)->pri)[2] = arrays[i][3];	
	}
	for(i = 0; i < 10; i++)
	{
		ppq_enqueue(ppq, nodes+i);				
	}
	
	for(i = 0; i < 10; i++)
	{
		tnode* tn = ppq_dequeue(ppq);
		printf("i = %d ", i);
		tnode_print_pri(tn->pri, tn->pri_bits);
	}
	free(nodes);
	*/
	/*
	tnode* ti;
	pp_queue* ppq = (pp_queue*)ppq_create(10, pri_compare);
	tnode* root = tnode_init();
	root->pri[0] = 0;
	root->pri[1] = 0;
	root->pri[2] = 0;
	root->pri_bits = 0;
	root->v = (void*)val_num;
	val_num++;
	tnode_add_rec(ppq, root, 2); 		
	ppq_enqueue(ppq, root);	
	root = ppq_dequeue(ppq);
	while(root != NULL)
	{
		printf("%c ", (char)root->v);
		tnode_print_pri(root->pri, root->pri_bits);
		root = ppq_dequeue(ppq);	
	}
	*/
}