Lock-Free Stack(2)

template<typename T>
class LockFreeStack
{
	struct Node
	{
		Node(const T& value) : data(value),next(nullptr) {}

		T data;
		Node* next;
	};

public:
	//1) 새 노드를 만들고
	//2) 새 노드의 next = head
	//3) head = 새 노드

	void Push(const T& value)
	{
		Node* node = new Node(value);
		node->next = _head;
	
		while (_head.compare_exchange_weak(node->next, node) == false)
		{
		}
	}

	//1) head 읽기
	//2) head->next 읽기
	//3) head = head->next
	//4) data 추출해서 반환
	//5) 추출한 노드를 삭제
	bool TryPop(T& value)
	{
		++_popCount;
		Node* oldHead = _head;

		while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)
		{
		}

		if (oldHead == nullptr)
		{
			--_popCount;
			return false;
		}

		value = oldHead->data;
		TryDelete(oldHead);
		return true;
	}

	//1) 데이터 분리
	//2) count 체크
	//3) 나 혼자면 삭제
	void TryDelete(Node* oldHead)
	{
		//나 외에 누가 있는가?
		if (_popCount == 1)
		{
			//나 혼자네?

			//이왕 혼자인거, 삭제 예약된 다른 데이터들도 삭제해보자.
			Node* node = _pendingList.exchange(nullptr);

			if (--_popCount == 0)
			{
				//끼어든 애가 없음 -> 삭제 진행
				//이제와서 끼어들어도, 어차피 데이터는 분리해둔 상태
				DeleteNodes(node);
			}
			else if (node)
			{
				//누가 끼어들었으니 다시 갖다 놓자.
				ChainPendingNodeList(node);
			}

			//내 데이터는 삭제
			delete oldHead;
		}
		else
		{
			// 누가 있네? 그럼 지금 바로 삭제하지 않고, 삭제 예약만 하자.
			ChainpendingNode(oldHead);
			_popCount--;
		}
	}

	void ChainPendingNodeList(Node* first, Node* last)
	{
		last->next = _pendingList;

		while (_pendingList.compare_exchange_weak(last->next, first) == false)
		{

		}
	}

	void ChainPendingNodeList(Node* node)
	{
		Node* last = node;

		while (last->next)
			last = last->next;

		ChainPendingNodeList(node, last);
	}

	void ChainpendingNode(Node* node)
	{
		ChainPendingNodeList(node, node);
	}

	static void DeleteNodes(Node* node)
	{
		while (node)
		{
			Node* next = node->next;
			delete node;
			node = next;
		}
	}

private:
	atomic<Node*> _head;

	atomic<uint32> _popCount = 0; //Pop을 실행중인 쓰레드 개수
	atomic<Node*> _pendingList; //삭제 되어야 할 노드들 (첫번째 노드)
};

 

Node* node = _pendingList.exchange(nullptr);

node에 _pendingList값을 넘겨 준다음 _pendingList를 nullptr로 바꿈.

 

 

void ChainPendingNodeList(Node* first, Node* last)

마지막 노드를 _pendingList와 연결해줌.

멀티쓰레드 특성상 누군가가 끼어들어서 똑같은 작업을 할 수 있기 때문에 CAS으로 루프를 돌면서

_pendingLists를 맨 앞노드로 만들어 준다.

 

 

void ChainPendingNodeList(Node* node)

첫 번째 노드를 건네주면 노드 리스트에 이어진 마지막 노드를 찾아서

(_pendingList에 삭제 보류중인 노드가 여러개 있을 수 도 있기 때문에 모든 노드를 검색해준다.)

ChainPendingNodeList(Node* first, Node* last)를 호출해주는 헬퍼함수

 

void ChainpendingNode(Node* node)

딱 한개의 노드만 받아와서 _pendingList와 연결 해줌.

 

static void DeleteNodes(Node* node)

while문을 돌려서 다음 노드를 추출하고, node는 삭제를 한 다음 node를 next로 바꿔줌.

 

---

void TryDelete(Node* oldHead)

if (_popCount == 1)

_popCount를 비교하여 나 외에 접근한 스레드가 있는지 확인.

---

Node* node = _pendingList.exchange(nullptr);

다른 접근한 스레드가 없을 경우 _pendingList에서 삭제 보류중인 노드를 가져온다. 

 

if (--_popCount == 0)
DeleteNodes(node);

--_popCount가 0인지 한번더 확인하고 삭제를 진행한다.

 

else if (node)
ChainPendingNodeList(node);

--_popCount가 0이 아니고 삭제 보류중인 노드가 있다면 삭제 보류중인 노드의 next를 _pendingList와 연결해준다.

그리고 CAS 루프를 진입하여 _pendingList를 맨 앞노드로 만들어준다.

 

delete oldHead;
원래 삭제하려던 oldHead 삭제.

---

else

다른 접근한 스레드가 있을 경우

 

ChainpendingNode(oldHead);

ChainpendingNode(oldHead)를 통해 _pendingList에 노드를 연결시킨다.

 

_popCount--;

그리고 _popCount를 감소시켜준다.