/*
	Copyright (C) 2008 Cory Nelson

	This software is provided 'as-is', without any express or implied
	warranty.  In no event will the authors be held liable for any damages
	arising from the use of this software.

	Permission is granted to anyone to use this software for any purpose,
	including commercial applications, and to alter it and redistribute it
	freely, subject to the following restrictions:

	1. The origin of this software must not be misrepresented; you must not
		claim that you wrote the original software. If you use this software
		in a product, an acknowledgment in the product documentation would be
		appreciated but is not required.
	2. Altered source versions must be plainly marked as such, and must not be
		misrepresented as being the original software.
	3. This notice may not be removed or altered from any source distribution.
*/

#pragma once

#include <intrin.h>
#include "spinwait.hpp"
#include "tagged_ptr.hpp"

namespace interlocked {

template<typename T>
class basic_iqueue {
public:
	struct node {
		typedef tagged_ptr<node> tagged_type;

		tagged_type next;
		T value;

		node() {}
		node(const T &value) : value(value) {}
	};

	basic_iqueue(node &init) {
		m_head.reset(&init);
		m_tail.reset(&init);
	}

	void push(node &n) {
		spin_wait wait;
		int ret;

		n.next.reset();

		for(;;) {
			ret = try_push(n);
			if(ret == 0) return;
			if(ret == 1) wait.spin();
		}
	}

	node* pop(T &value) {
		spin_wait wait;
		node *n;
		int ret;

		for(;;) {
			ret = try_pop(value, n);
			if(ret == 0) return n;
			if(ret == 1) wait.spin();
		}
	}

	// returns 0 on success, 2 on non-contention recall needed, 1 on contention.
	int try_push(node &n) {
		typename node::tagged_type::cmp2_type tail, next;
		node *tptr, *nptr;

		tail = m_tail.val2();
		tptr = m_tail.val(tail);

		detail::read_barrier();

		next = tptr->next.val2();
		nptr = tptr->next.val(next);

		detail::read_barrier();

		if(tail != m_tail.val2()) return 1;

		if(!nptr) {
			if(tptr->next.cas2(&n, next)) {
				m_tail.cas2(&n, tail);
				return 0;
			}

			return 1;
		}

		return m_tail.cas2(nptr, tail) ? 2 : 1;
	}

	// returns 0 on success, 2 on non-contention recall needed, 1 on contention.
	int try_pop(T &value, node* &n) {
		typename node::tagged_type::cmp2_type head, tail, next;
		node *hptr, *tptr, *nptr;

		head = m_head.val2();
		hptr = m_head.val(head);

		detail::read_barrier();

		tail = m_tail.val2();
		tptr = m_tail.val(tail);

		detail::read_barrier();

		next = hptr->next.val2();
		nptr = hptr->next.val(next);

		detail::read_barrier();

		if(head != m_head.val2()) return 1;

		if(hptr == tptr) {
			if(!nptr) {
				n = nptr;
				return 0;
			}

			return m_tail.cas2(nptr, tail) ? 2 : 1;
		}

		value = nptr->value;

		if(m_head.cas2(nptr, head)) {
			n = hptr;
			return 0;
		}

		return 1;
	}

private:
	typename node::tagged_type m_head, m_tail;
};

}