//
// 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 : Sun Jun 14 13:25:09 2020
// Update Count     : 64
//

#pragma once

#include <stdint.h>

forall( 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( T | sized(T) | { Link(T) * ?`next( 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) {
			*( &n )`next = stack;					// atomic assignment unnecessary, or use CAA
			for () {									// busy wait
			  if ( __atomic_compare_exchange_n( &stack.atom, &( &n )`next->atom, (Link(T))@{ {&n, ( &n )`next->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 @= stack;							// atomic assignment unnecessary, or use CAA
			for () {									// busy wait
			  if ( t.top == 0p ) return 0p;				// empty stack ?
			  if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ {( t.top )`next->top, t.count} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.top; // attempt to update top node
			} // for
		} // pop

		bool unsafe_remove( StackLF(T) & this, T * node ) with(this) {
			Link(T) * link = &stack;
			for() {
				T * next = link->top;
				if( next == node ) {
					link->top = ( node )`next->top;
					return true;
				}
				if( next == 0p ) return false;
				link = (next)`next;
			}
		}
	} // distribution
} // distribution


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