aboutsummaryrefslogtreecommitdiffstats
path: root/util/thread/lfstack.h
diff options
context:
space:
mode:
authorironpeter <ironpeter@yandex-team.ru>2022-02-10 16:49:52 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:49:52 +0300
commitedee5b99e1eec042f46725b89dcd81ea7e41d663 (patch)
tree5d5cb817648f650d76cf1076100726fd9b8448e8 /util/thread/lfstack.h
parentff97837ecc5972a00cb395483d8856566738375c (diff)
downloadydb-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.h92
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
- }
-};
+ }
+};