无锁编程单链表的实现，主要特性如下：
- 只能从尾部追加元素
- 不支持删除元素
- 支持Iterator遍历元素
- 提供了多线程情况下的测试用例
适用的场景如下：
- 搜索引擎，实时索引中的倒排链表
- 只添加元素，不删除元素的多线程场景
代码如下：
#include
#include
#include
#include
template
class LockFreeSignleLinkedList {
public:
struct Node {
union Data {
DataType *ptr;
uint64_t value;
} data;
std::atomic next = nullptr;
};
class Iterator {
public:
Iterator operator ++(int) {
Iterator it;
it.ptr = ptr->next;
return it;
}
Iterator& operator ++() {
ptr = ptr->next;
return *this;
}
bool operator ==(Iterator& iter) {
return (ptr == iter.ptr);
}
Iterator& operator =(const Iterator& iter) {
ptr = iter->ptr;
return *this;
}
DataType& operator *() {
if (std::is_class::value) {
return *(ptr->data.ptr);
}
uint64_t* data_ptr = &(ptr->data.value);
DataType* ptr = reinterpret_cast(data_ptr);
return *ptr;
}
friend class LockFreeSignleLinkedList;
private:
Node* ptr = nullptr;
};
LockFreeSignleLinkedList() {
head = new Node;
tail = head;
}
void push_back(const DataType& data) {
push_back(&data);
}
void push_back(const DataType* ptr) {
Node *tmp = new Node;
if (std::is_class ::value) {
tmp->data.ptr = const_cast(ptr);
} else {
DataType* tmp_ptr = reinterpret_cast(&(tmp->data.value));
*tmp_ptr = *ptr;
}
for(;;) {
ajustTail();
Node *real_tail = tail.load(std::memory_order_relaxed);
auto& next = real_tail->next;
Node *real_next = next.load(std::memory_order_relaxed);
if (nullptr != real_next) {
continue;
}
if (!next.compare_exchange_weak(real_next, tmp, std::memory_order_relaxed)) {
continue;
} else {
break;
}
}
cnt.fetch_add(1, std::memory_order_relaxed);
ajustTail();
}
Iterator begin() {
Iterator it;
it.ptr = head->next;
return it;
}
Iterator end() {
static Iterator blank_it;
return blank_it;
}
size_t size() { return cnt.load(std::memory_order_relaxed); }
private:
void ajustTail() {
for(;;) {
Node *real_tail = tail.load(std::memory_order_relaxed);
auto& next = real_tail->next;
Node *real_next = next.load(std::memory_order_relaxed);
if (nullptr == real_next) {
return;
}
if (!tail.compare_exchange_weak(real_tail, real_next, std::memory_order_relaxed)) {
continue;
}
} // end for
}
Node* head = nullptr;
std::atomic tail = nullptr;
std::atomic cnt = 0;
};
int main()
{
LockFreeSignleLinkedList l;
l.push_back(9);
l.push_back(2);
l.push_back(4);
l.push_back(5);
std::cout << "list:" << std::endl;
for (const int32_t n : l) {
std::cout << n << std::endl;
}
std::cout << "retry to list:" << std::endl;
for (auto it = l.begin(); it != l.end(); ++it ) {
std::cout << *it << std::endl;
}
LockFreeSignleLinkedList l2;
volatile bool run = false;
auto fun = [&]() {
for (;;) {
if (!run) {
continue;
} else {
break;
}
}
std::cout<< "start pid:" << std::this_thread::get_id() << std::endl;
for (int32_t i = 0; i < 900000; ++i) {
l2.push_back(i);
}
std::cout<< "end pid:" << std::this_thread::get_id() << std::endl;
};
std::thread t1([&](){fun();});
std::thread t2([&](){fun();});
std::thread t3([&](){fun();});
std::thread t4([&](){fun();});
std::atomic_thread_fence(std::memory_order_seq_cst);
run = true;
t1.join();
t2.join();
t3.join();
t4.join();
size_t s1 = 0;
for (auto it = l2.begin(); it != l2.end(); ++it ) {
++s1;
}
std::cout << "s1:" << s1 << std::endl;
std::cout << "s2:" << l2.size() << std::endl;
return 0;
} 