Lock-Poor Stack

#define RL_MSVC_OUTPUT
#include "relacy/relacy_std.hpp"
 
enum StackResult {
	STACK_RESULT_OK,
	STACK_RESULT_E_BAD_ALLOC,	// allocation failed
	STACK_RESULT_E_PRECOND,		// pre-condition failed
	STACK_RESULT_E_EMPTY,
};
 
typedef unsigned int uint32_t;
 
unsigned const thread_count__ = 3;
 
struct StackNode_struct
{
	struct StackNode_struct * next_;
	void * value_;
};
 
#define StackNode_setABACounter(p, a)					\
	((StackNode*)((((uint32_t)(p)) & 0xFFFFFFF0) | ((a) & 0x0000000F)))
#define StackNode_getABACounter(p) (((uint32_t)(p)) & 0x0000000F)
#define StackNode_getPointer(p) ((StackNode*)(((uint32_t)(p) & 0xFFFFFFF0)))
 
static StackNode * StackNode_new()
{
	// when we allocate a node, we actually allocate enough space for the node to
	// be aligned at a 16-byte boundary and in the four bytes before the node, we
	// have a pointer with the value of the original pointer, which we can call
	// free(3) with.
	uint32_t buffer = (uint32_t)calloc(1, 20 + sizeof(struct StackNode_struct));
	char * retval = (char*)((buffer + 15) & 0xFFFFFFF0);
	if ((((uint32_t)retval) - buffer) < 4) retval += 16;
	void ** p = (void**)(retval - 4);
	*p = (void*)buffer;
 
	return (StackNode*)retval;
}
 
static void StackNode_delete(StackNode * node)
{
	void ** p = (void**)(((char*)StackNode_getPointer(node)) - 4);
	free(*p);
}
 
struct Stack_struct
{
	Stack_struct()
		: top_(0)
	{
		if (pthread_mutex_init(&lock_, 0) != 0)
			throw std::bad_alloc();
	}
 
	~Stack_struct()
	{
		StackNode * node = StackNode_getPointer(top_($).load());
		StackNode * next;
		while (node)
		{
			next = StackNode_getPointer(node->next_);
			StackNode_delete(node);
			node = next;
		}
		pthread_mutex_destroy(&lock_);
	}
 
	std::atomic< StackNode * > top_;
	pthread_mutex_t lock_;
};
 
Stack * Stack_new()
{
	Stack * stack = 0;
 
	try
	{
		stack = new Stack_struct;
	}
	catch (const std::bad_alloc &)
	{
		stack = 0;
	}
 
	return stack;
}
 
void Stack_delete(Stack * stack)
{
	delete stack;
}
 
int Stack_push(Stack * stack, void * value)
{
	int retval = STACK_RESULT_OK;
 
	if (stack)
	{
		StackNode * node = StackNode_new();
		if (node)
		{
			StackNode * old_top = stack->top_($).load();
			do
			{
				node->value_ = value;
				node->next_ = old_top;
			} while (!stack->top_($).compare_exchange_strong(old_top, StackNode_setABACounter(node, StackNode_getABACounter(old_top) + 1)));
		}
		else retval = STACK_RESULT_E_BAD_ALLOC;
	}
	else retval = STACK_RESULT_E_PRECOND;
 
	return retval;
}
 
int Stack_top(Stack * stack, void ** value)
{
	int retval = STACK_RESULT_OK;
 
	if (stack && value)
	{
		StackNode top;
 
		pthread_mutex_lock(&stack->lock_);
		if (stack->top_($))
		{
			memcpy(&top, StackNode_getPointer(stack->top_($).load()), sizeof(top));
			*value = top.value_;
		}
		else retval = STACK_RESULT_E_EMPTY;
		pthread_mutex_unlock(&stack->lock_);
	}
	else
		retval = STACK_RESULT_E_PRECOND;
 
	return retval;
}
 
int Stack_pop(Stack * stack, void ** value)
{
	int retval = STACK_RESULT_OK;
 
	if (stack && value)
	{
		StackNode top;
		StackNode * top_ptr = 0;
		int done = 0;
 
		do
		{
			pthread_mutex_lock(&stack->lock_);
			top_ptr = stack->top_($);
			if (stack->top_($))
			{
				memcpy(&top, StackNode_getPointer(stack->top_($).load()), sizeof(top));
				pthread_mutex_unlock(&stack->lock_);
				done = stack->top_($).compare_exchange_strong(top_ptr, StackNode_setABACounter(top.next_, StackNode_getABACounter(top_ptr) + 1));
			}
			else
			{
				pthread_mutex_unlock(&stack->lock_);
				retval = STACK_RESULT_E_EMPTY;
				top_ptr = 0;
				done = 1;
			}
		} while (!done);
		StackNode_delete(top_ptr);
		*value = top.value_;
	}
	else
		retval = STACK_RESULT_E_PRECOND;
 
	return retval;
}
 
int Stack_empty(Stack * stack)
{
	return (stack && (StackNode_getPointer(stack->top_($).load()) == 0));
}
 
struct StackTest : rl::test_suite< StackTest, thread_count__ >
{
	void before()
	{
        for (int i(0); i < 16; ++i)
        {
            push_counts_[i]($) = 0;
            top_counts_[i]($) = 0;
            pop_counts_[i]($) = 0;
        }
		stack_ = Stack_new();
	}
 
	void thread(unsigned index)
	{
		int numbers[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
		std::random_shuffle(numbers, numbers + 16);
		for (unsigned int i(0); i < 16; ++i)
		{
			RL_ASSERT(Stack_push(stack_, (void*)numbers[i]) == 0);
			++push_counts_[i]($);
			void * p;
			RL_ASSERT(Stack_top(stack_, &p) == 0);
			++top_counts_[(int)p]($);
			RL_ASSERT(Stack_pop(stack_, &p) == 0);
			++pop_counts_[(int)p]($);
		}
	}
 
	void after()
	{
		RL_ASSERT(Stack_empty(stack_));
		Stack_delete(stack_);
        for (int i(0); i < 16; ++i)
        {
            RL_ASSERT(push_counts_[i]($) == 3);
            RL_ASSERT(pop_counts_[i]($) == 3);
        }
	}
 
	Stack * stack_;
	std::atomic< int > push_counts_[16];
	std::atomic< int > top_counts_[16];
	std::atomic< int > pop_counts_[16];
};
 
int main()
{
	rl::test_params p;
//	p.iteration_count = 100000;
	p.search_type = rl::fair_full_search_scheduler_type;
	rl::simulate< StackTest >(p);
}