//
// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// stackLockFree.hfa --
//
// Author           : Peter A. Buhr
// Created On       : Wed May 13 20:58:58 2020
// Last Modified By : Peter A. Buhr
// Last Modified On : Mon May 18 13:30:08 2020
// Update Count     : 55
//

#pragma once

#include <stdint.h>

forall( dtype T )
union Link {
	struct {									// 32/64-bit x 2
		T * volatile top;								// pointer to stack top
		uintptr_t count;						// count each push
	};
	#if __SIZEOF_INT128__ == 16
	__int128									// gcc, 128-bit integer
	#else
	uint64_t									// 64-bit integer
	#endif // __SIZEOF_INT128__ == 16
	atom;
}; // Link

forall( otype T | { Link(T) * getNext( T * ); } ) {
    struct StackLF {
		Link(T) stack;
	}; // StackLF

	static inline {
		void ?{}( StackLF(T) & this ) with(this) { stack.atom = 0; }

		T * top( StackLF(T) & this ) with(this) { return stack.top; }

		void push( StackLF(T) & this, T & n ) with(this) {
			for () {									// busy wait
				*getNext( &n ) = stack;					// atomic assignment unnecessary, or use CAA
			  if ( __atomic_compare_exchange_n( &stack.atom, &getNext( &n )->atom, (Link(T))@{ {&n, getNext( &n )->count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node
			} // for
		} // push

		T * pop( StackLF(T) & this ) with(this) {
			Link(T) t @= {};
			for () {									// busy wait
				t = stack;								// atomic assignment unnecessary, or use CAA
			  if ( t.top == 0p ) return 0p;				// empty stack ?
			  if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ {getNext( t.top )->top, t.count} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.top; // attempt to update top node
			} // for
		} // pop
	} // distribution
} // distribution


// Local Variables: //
// tab-width: 4 //
// End: //