diff options
author | ironpeter <ironpeter@yandex-team.ru> | 2022-02-10 16:49:52 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:49:52 +0300 |
commit | edee5b99e1eec042f46725b89dcd81ea7e41d663 (patch) | |
tree | 5d5cb817648f650d76cf1076100726fd9b8448e8 /util/thread/lfstack.h | |
parent | ff97837ecc5972a00cb395483d8856566738375c (diff) | |
download | ydb-edee5b99e1eec042f46725b89dcd81ea7e41d663.tar.gz |
Restoring authorship annotation for <ironpeter@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'util/thread/lfstack.h')
-rw-r--r-- | util/thread/lfstack.h | 92 |
1 files changed, 46 insertions, 46 deletions
diff --git a/util/thread/lfstack.h b/util/thread/lfstack.h index a85b6100b6..ca3d95f3c3 100644 --- a/util/thread/lfstack.h +++ b/util/thread/lfstack.h @@ -1,16 +1,16 @@ #pragma once - + #include <util/generic/noncopyable.h> -#include <util/system/atomic.h> - -////////////////////////////// -// lock free lifo stack +#include <util/system/atomic.h> + +////////////////////////////// +// lock free lifo stack template <class T> class TLockFreeStack: TNonCopyable { struct TNode { - T Value; + T Value; TNode* Next; - + TNode() = default; template <class U> @@ -19,29 +19,29 @@ class TLockFreeStack: TNonCopyable { , Next(nullptr) { } - }; - + }; + TNode* Head; TNode* FreePtr; - TAtomic DequeueCount; - + TAtomic DequeueCount; + void TryToFreeMemory() { TNode* current = AtomicGet(FreePtr); - if (!current) - return; + if (!current) + return; if (AtomicAdd(DequeueCount, 0) == 1) { - // node current is in free list, we are the last thread so try to cleanup + // node current is in free list, we are the last thread so try to cleanup if (AtomicCas(&FreePtr, (TNode*)nullptr, current)) - EraseList(current); - } - } + EraseList(current); + } + } void EraseList(TNode* volatile p) { - while (p) { + while (p) { TNode* next = p->Next; - delete p; - p = next; - } - } + delete p; + p = next; + } + } void EnqueueImpl(TNode* volatile head, TNode* volatile tail) { for (;;) { tail->Next = AtomicGet(Head); @@ -55,7 +55,7 @@ class TLockFreeStack: TNonCopyable { EnqueueImpl(node, node); } -public: +public: TLockFreeStack() : Head(nullptr) , FreePtr(nullptr) @@ -63,9 +63,9 @@ public: { } ~TLockFreeStack() { - EraseList(Head); - EraseList(FreePtr); - } + EraseList(Head); + EraseList(FreePtr); + } void Enqueue(const T& t) { EnqueueImpl(t); @@ -83,7 +83,7 @@ public: void EnqueueAll(TIter dataBegin, TIter dataEnd) { if (dataBegin == dataEnd) { return; - } + } TIter i = dataBegin; TNode* volatile node = new TNode(*i); TNode* volatile tail = node; @@ -94,33 +94,33 @@ public: node->Next = nextNode; } EnqueueImpl(node, tail); - } + } bool Dequeue(T* res) { AtomicAdd(DequeueCount, 1); for (TNode* current = AtomicGet(Head); current; current = AtomicGet(Head)) { if (AtomicCas(&Head, AtomicGet(current->Next), current)) { *res = std::move(current->Value); - // delete current; // ABA problem - // even more complex node deletion - TryToFreeMemory(); + // delete current; // ABA problem + // even more complex node deletion + TryToFreeMemory(); if (AtomicAdd(DequeueCount, -1) == 0) { - // no other Dequeue()s, can safely reclaim memory - delete current; - } else { - // Dequeue()s in progress, put node to free list + // no other Dequeue()s, can safely reclaim memory + delete current; + } else { + // Dequeue()s in progress, put node to free list for (;;) { AtomicSet(current->Next, AtomicGet(FreePtr)); if (AtomicCas(&FreePtr, current, current->Next)) - break; - } - } - return true; - } - } - TryToFreeMemory(); + break; + } + } + return true; + } + } + TryToFreeMemory(); AtomicAdd(DequeueCount, -1); - return false; - } + return false; + } // add all elements to *res // elements are returned in order of dequeue (top to bottom; see example in unittest) template <typename TCollection> @@ -184,5 +184,5 @@ public: bool IsEmpty() { AtomicAdd(DequeueCount, 0); // mem barrier return AtomicGet(Head) == nullptr; // without lock, so result is approximate - } -}; + } +}; |