//
// Cforall Version 1.0.0 Copyright (C) 2022 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// lockfree_stack.cfa -- 
//
// Author           : Peter A. Buhr
// Created On       : Thu May 25 15:36:50 2023
// Last Modified By : Peter A. Buhr
// Last Modified On : Fri Jun  9 14:01:07 2023
// Update Count     : 68
// 

#include <thread.hfa>
#include <atomic.hfa>									// CASV
#include <fstream.hfa>

struct Node;											// forward declaration
union Link {
	struct {											// 32/64-bit x 2
		Node * volatile top;							// pointer to stack top
		uintptr_t count;								// count each push
	};
	#if defined( __SIZEOF_INT128__ )
	__int128 atom;										// gcc, 128-bit integer
	#else
	int64_t atom;
	#endif // __SIZEOF_INT128__
};

struct Node {
	// resource data
	Link next;											// pointer to next node/count (resource)
};
struct Stack {
	Link stack;
};

void push( Stack & s, Node & n ) with(s) {
	n.next = stack;										// atomic assignment unnecessary
	for () {											// busy wait
		Link temp{ &n, n.next.count + 1 };
		if ( CASV( s.stack.atom, n.next.atom, temp.atom ) ) break; // attempt to update top node
	}
}

Node * pop( Stack & s ) with(s) {
	Link t = stack;										// atomic assignment unnecessary
	for () {											// busy wait
		if ( t.top == NULL ) return NULL;				// empty stack ?
		Link temp{ t.top->next.top, t.count };
		if ( CASV( stack.atom, t.atom, temp.atom ) ) return t.top; // attempt to update top node
	}
}
void ?{}( Stack & s ) with(s) { stack.atom = 0; }

Stack stack;											// global stack

enum { Times = 2_000_000 };

thread Worker {};
void main( Worker & w ) {
	for ( i; Times ) {
		Node & n = *pop( stack );						// pop any node
		assert( &n != NULL );
		n.next.top = 0p;								// scrub fields
		n.next.count = 0;
		//yield( rand() % 3 );
		push( stack, n );								// push it back
	}
}

int main() {
	enum { N = 8 };										// kernel threads
	processor p[N - 1];									// add kernel threads

	for ( i; N ) {										// push N values on stack
		push( stack, *(Node *)new() );					// must be 16-byte aligned
	}
	{
		Worker workers[N];								// run test
	}
	for ( i; N ) {										// pop N nodes from list
		free( pop( stack ) );
	}
	sout | "done";										// non-empty .expect file
}

// Local Variables: //
// compile-command: "cfa -g -O3 lockfree_stack.cfa" //
// End: //