//
// CS 4331: UPC Parallel Permutation		Fall, 2008
//
// Code the permute the elements of an array with initial contexts
// 0, 1, 2, ..., BLK*THREADS-1
//
// Each thread swaps the elements it has affinity to with randomly
// selected other elements.  Race conditions are avoided by
// associating a unique lock with each array element.

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

#define BLK 5

shared [BLK] int A[BLK*THREADS];
//upc_lock_t *shared [BLK] lk[BLK*THREADS];

shared [BLK] upc_lock_t *lk[BLK*THREADS];

// shared [BLK] int *shared p[BLK*THREADS];
// shared int *shared [BLK] q[BLK*THREADS];

int main(int argc, char **argv) {

int i, s, t;

// Generate inital, sorted array elements and allocate locks
//&A[i] 

upc_forall(i=0; i<BLK*THREADS; ++i; &A[i])
{
	A[i] = i;
	lk[i] = upc_global_lock_alloc();
}


upc_barrier  ;


// Move the random number generator ahead in each thread.

srand48(0xFEEDFACE);



//for (i=0; i<BLK*MYTHREAD; ++i) 		s = (int)drand48();

for (i=BLK*MYTHREAD; i<BLK*(MYTHREAD+1); ++i)
{
	// Generate an array element index to swap with
	s = (int)lrand48() % (BLK*THREADS);
	printf("Swap %d and %d \n", i, s);

	// Avoid deadlocks by requesting higher-numbered lock first
	
	if (s < i)
	{	upc_lock(lk[i]);
		upc_lock(lk[s]);
		// Swap
		t = A[i];
		A[i] = A[s];
		A[s] = t;
		// Dont forget to unlock
		upc_unlock(lk[i]);
		upc_unlock(lk[s]);
	}
	if (s > i)
	{	upc_lock(lk[s]);
		upc_lock(lk[i]);
		// Swap
		t = A[i];
		A[i] = A[s];
		A[s] = t;
		// Dont forget to unlock
		upc_unlock(lk[i]);
		upc_unlock(lk[s]);
	}
	
}

upc_barrier;

if (MYTHREAD==0)
{
	// Print permuted array elements
	for (i=0; i<BLK*THREADS; ++i)
		printf("%2d  ", A[i]);
	printf("\n");

	// Check for missing and duplicate elements
	for (i=0; i<BLK*THREADS; ++i)
	{ 	int j, count = 0;
		for (j=0; j<BLK*THREADS; ++j)
			if (A[j] == i)
				 ++count;
		if (count == 0)
			printf("%d is missing\n", i);
		if (count > 1)
			printf("%d occurs %d times\n", i, count);
	}
}
}