speculative-read.cpp

template<typename T> // fuck anyone who writes 'class T'
struct alignas(T) speculative_buffer {
	static_assert(std::is_default_constructible_v<T>, "T must be DefaultConstructible");
	static_assert(std::is_trivially_copyable_v<T>, "T must be TriviallyCopyable");

	speculative_buffer(T* src) {
		unsafe_read(src);
	}
	
	void unsafe_read(T* src) { // nb: can read from any pointer, does not need to be atomic etc.
		std::unsafe_memcpy(raw, src, sizeof(T)); // magic version of memcpy that we permit to do dirty reads. Regular memcpy in any sane platform.
	}

	T hydrate() const {
		T dst;
		std::memcpy(&dst, raw, sizeof(T));
		return dst;
	}

private:
	byte raw[sizeof(T)];
};

struct ws_deque_base {
	std::atomic<uint64_t> bottom;
	std::atomic<uint64_t> top;
};

template<typename T>
struct ws_deque : ws_deque_base {
	atomic<T*> active_array; // ordinary array of T
	
	
	std::pair<bool, std::optional<T>> steal() {
		size_t t = top.load(std::memory_order_acquire);
		std::atomic_thread_fence(std::memory_order_seq_cst);
		size_t b = bottom.load(std::memory_order_acquire);
		if(t < b) {
			T* a = active_array.load(std::memory_order_acquire);
			speculative_buffer<T> spec(&a[t % size]);
			if(!top.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst, std::memory_order_relaxed)) {
				return std::make_pair(false, std::nullopt);
			}
			T t = speculative_buffer.hydrate();
			return std::make_pair(true, std::optional<T>(t));
		}
		return std::make_pair(true, std::nullopt);
	}	
};