共计 2163 个字符,预计需要花费 6 分钟才能阅读完成。
有朋友熟悉 C++ 编程吗?能帮我看看这里有什么 bug 吗(更新两个 atomic)
目的是实现一个 Multiset(Non-blocking)
template
class CMSet {bool contains(T element);
int count(T element);
void add(T element);
bool remove(T element);
};
template struct ANode {
T data;
std::atomic count{};
std::atomic*> next;
size_t key{};
ANode() : next(nullptr) {};
explicit ANode(T data) : data(data), next(nullptr) {};
explicit ANode(T data, size_t key) : data(data), key(key), next(nullptr) {this->count.store(1);
};
};
template
class CMSetWithNonBlocking : public CMSet {
private:
atomic*> head;
public:
CMSetWithNonBlocking () {auto* h = new ANode;
h->key = std::numeric_limits::min();
auto* t = new ANode;
t->key = std::numeric_limits::max();
head.store(h);
head.load()->next.store(t);
}
bool contains(T data) {size_t key = std::hash{}(data);
ANode* curr = head.load()->next.load();
while (curr->key next.load();}
return curr->key == key && curr->count.load()> 0;
}
int count(T data) {size_t key = std::hash{}(data);
ANode* curr = head.load()->next.load();
while (curr->key next.load();}
if (curr->key == key) {return curr->count.load();}
return 0;
}
void add(T data) {size_t key = std::hash{}(data);
auto* newNode = new ANode(data, key);
while (true) {ANode* prev = head.load();
ANode* curr = prev->next.load();
while (curr->key next.load();}
if (curr->key == key) {
// If node with key exists, increment count atomically
int oldCount = curr->count.load();
if (curr->count.compare_exchange_weak(oldCount, oldCount + 1)) {
delete newNode; // newNode not needed, delete it
return;
}
} else {
// Insert new node
newNode->next.store(curr);
if (prev->next.compare_exchange_weak(curr, newNode)) {return; // Successfully added}
}
}
}
bool remove(T data) {size_t key = std::hash{}(data);
while (true) {ANode* prev = head.load();
ANode* curr = prev->next.load();
while (curr->key next.load();}
if (curr->key == key) {int oldCount = curr->count.load();
if (oldCount == 0) {return false; // Node already removed or never added}
if (curr->count.compare_exchange_weak(oldCount, oldCount - 1)) {if (oldCount - 1 == 0) {
// If count decremented to 0, remove node
ANode* next = curr->next.load();
if (!prev->next.compare_exchange_weak(curr, next)) {continue; // CAS failed, retry} else {delete curr; // Node removed, delete it}
}
return true; // Count decremented successfully
}
// If CAS fails, loop will retry
} else {return false; // Node with key not found}
}
}
};
正文完