无锁编程单链表的实现，主要特性如下：

• 只能从尾部追加元素
• 不支持删除元素
• 支持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;
}