Celebration time...

class LocklessMailbox
{
public:
	//
	// Construct and initialize the read and write stacks
	//
	LocklessMailbox()
	{
		std::auto_ptr<Node> wh(new Node);
		std::auto_ptr<Node> rh(new Node);

		WriteHead = wh.get();
		WriteHead->Next = NULL;
		WriteHead->Payload = NULL;

		ReadHead = rh.get();
		ReadHead->Next = NULL;
		ReadHead->Payload = NULL;

		wh.release();
		rh.release();
	}

	//
	// Clean up the read, write, and cache stacks, freeing any
	// remaining messages from each stack.
	//
	~LocklessMailbox()
	{
		Release();
	}

public:
	//
	// Register a message from a producer thread. Any number of threads
	// may call this function.
	//
	void AddMessage(MessageInfo* info)
	{
		Node* msgnode = new Node;
		msgnode->Payload = info;

		Node* oldval;
		Node* newval;
		Node* retval;

		do
		{
			msgnode->Next = WriteHead;
			__asm mfence;
			oldval = msgnode->Next;
			newval = msgnode;
			Node** fieldaddr = &(WriteHead);

			_asm
			{
				mfence
				mov eax, oldval
				mov ecx, newval
				mov edx, dword ptr [fieldaddr]

				lock cmpxchg dword ptr[edx], ecx
				mov retval, eax
				mfence
			}
		}
		while(retval != oldval);
	}

	//
	// Retrieve a message from the mailbox.
	// IMPORTANT: only ONE consumer thread (per mailbox) should call this function
	//
	MessageInfo* GetMessage()
	{
		if(!PendingReads.empty())
		{
			Node* readnode = PendingReads.top();
			MessageInfo* payload = readnode->Payload;
			delete readnode;
			PendingReads.pop();
			return payload;
		}

		if(ReadHead->Next == NULL)
			SwapReadAndWrite();

		Node* n = ReadHead;
		while(ReadHead->Next)
		{
			PendingReads.push(n);
			n = n->Next;
			ReadHead = n;
		}

		if(PendingReads.empty())
			return NULL;

		Node* readnode = PendingReads.top();
		MessageInfo* payload = readnode->Payload;
		delete readnode;
		PendingReads.pop();
		return payload;
	}

private:
	//
	// Internal helper for swapping the read/write stacks
	// See class comment for details
	//
	void SwapReadAndWrite()
	{
		Node* oldval;
		Node* newval;
		Node* retval;
		Node* swappedreadhead;

		do
		{
			swappedreadhead = WriteHead;
			__asm mfence;
			oldval = swappedreadhead;
			newval = ReadHead;
			Node** fieldaddr = &(WriteHead);

			_asm
			{
				mfence
				mov eax, oldval
				mov ecx, newval
				mov edx, dword ptr [fieldaddr]

				lock cmpxchg dword ptr[edx], ecx
				mov retval, eax
				mfence
			}
		}
		while(retval != oldval);

		ReadHead = swappedreadhead;
	}

	//
	// Release the mailbox and free any remaining messages
	//
	void Release()
	{
		for(std::stack<Node*>::container_type::iterator iter = PendingReads.c.begin(); iter != PendingReads.c.end(); ++iter)
		{
			delete (*iter)->Payload;
			delete *iter;
		}

		Node* n = WriteHead;
		while(n)
		{
			delete n->Payload;
			Node* nextn = n->Next;
			delete n;
			n = nextn;
		}

		n = ReadHead;
		while(n)
		{
			delete n->Payload;
			Node* nextn = n->Next;
			delete n;
			n = nextn;
		}
 	}

private:
	struct Node
	{
		Node* Next;
		MessageInfo* Payload;
	};

	Node* WriteHead;
	Node* ReadHead;
	std::stack<Node*> PendingReads;
};