Chase-Lev deque implementation

chase_lev.cpp

// Copyright (c) 2013 Amanieu d'Antras
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

namespace async {
namespace detail {

// Chase-Lev work stealing deque
//
// Dynamic Circular Work-Stealing Deque
// http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.170.1097&rep=rep1&type=pdf
//
// Correct and Efficient Work-Stealing for Weak Memory Models
// http://www.di.ens.fr/~zappa/readings/ppopp13.pdf
class work_steal_queue {
	class circular_array {
	public:
		circular_array(std::size_t n)
			: items(n) {}
		std::size_t size() const
		{
			return items.size();
		}
		void* get(std::size_t index)
		{
			return items[index & (size() - 1)].load(std::memory_order_relaxed);
		}
		void put(std::size_t index, void* x)
		{
			items[index & (size() - 1)].store(x, std::memory_order_relaxed);
		}
		circular_array* grow(std::size_t top, std::size_t bottom)
		{
			circular_array* new_array = new circular_array(size() * 2);
			new_array->previous.reset(this);
			for (std::size_t i = top; i != bottom; ++i)
				new_array->put(i, get(i));
			return new_array;
		}
	private:
		aligned_array<std::atomic<void*>, LIBASYNC_CACHELINE_SIZE> items;
		std::unique_ptr<circular_array> previous;
	};

	std::atomic<circular_array*> array;
	std::atomic<std::size_t> top, bottom;

public:
	work_steal_queue()
		: array(new circular_array(32)), top(0), bottom(0) {}
	~work_steal_queue()
	{
		circular_array* p = array.load(std::memory_order_relaxed);
		if (p)
			delete p;
	}

	void push(task_run_handle x)
	{
		std::size_t b = bottom.load(std::memory_order_relaxed);
		std::size_t t = top.load(std::memory_order_acquire);
		circular_array* a = array.load(std::memory_order_relaxed);
		if (b - t > a->size() - 1) {
			a = a->grow(t, b);
			array.store(a, std::memory_order_relaxed);
		}
		a->put(b, x.to_void_ptr());
		std::atomic_thread_fence(std::memory_order_release);
		bottom.store(b + 1, std::memory_order_relaxed);
	}

	void* pop()
	{
		std::size_t b = bottom.load(std::memory_order_relaxed) - 1;
		circular_array* a = array.load(std::memory_order_relaxed);
		bottom.store(b, std::memory_order_relaxed);
		std::atomic_thread_fence(std::memory_order_seq_cst);
		std::size_t t = top.load(std::memory_order_relaxed);
		if (t <= b) {
			void* x = a->get(b);
			if (t == b) {
				if (!top.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst, std::memory_order_relaxed))
					x = nullptr;
				bottom.store(b + 1, std::memory_order_relaxed);
			}
			return x;
		} else {
			bottom.store(b + 1, std::memory_order_relaxed);
			return nullptr;
		}
	}

	void* steal()
	{
		std::size_t t = top.load(std::memory_order_acquire);
		std::atomic_thread_fence(std::memory_order_seq_cst);
		std::size_t b = bottom.load(std::memory_order_acquire);
		void* x = nullptr;
		if (t < b) {
			circular_array* a = array.load(std::memory_order_relaxed);
			x = a->get(t);
			if (!top.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst, std::memory_order_relaxed))
				return nullptr;
		}
		return x;
	}
};

} // namespace detail
} // namespace async

are there any bugs in this ? is it tested , i was looking for an implementation and stumbled on this, is it production ready ?? please revert.