cas实现双向链表

CAS (Compare-and-Swap) 是一种原子操作，可以实现线程安全的修改共享变量的值，避免并发环境下的数据竞争问题。双向链表是一种常见的数据结构，可以支持快速的插入、删除和查找操作。下面是一个基于 CAS 实现的简单双向链表代码示例，其中节点的结构体包括前驱节点指针 prev、后继节点指针 next 和节点值 val：

#include <atomic>

template <typename T>
struct Node {
    T val;
    std::atomic<Node<T>*> prev;
    std::atomic<Node<T>*> next;

    Node(T val) : val(val), prev(nullptr), next(nullptr) {}
};

template <typename T>
class LinkedList {
public:
    LinkedList() : head(new Node<T>(0)), tail(new Node<T>(0)) {
        head->next.store(tail);
        tail->prev.store(head);
    }

    ~LinkedList() {
        Node<T>* cur = head;
        while (cur) {
            Node<T>* next = cur->next.load();
            delete cur;
            cur = next;
        }
    }

    bool insert(T val) {
        Node<T>* pred = nullptr;
        Node<T>* curr = nullptr;
        Node<T>* newNode = new Node<T>(val);
        do {
            pred = head;
            curr = pred->next.load();
            while (curr != tail && curr->val < val) {
                pred = curr;
                curr = curr->next.load();
            }
            if (curr == tail || curr->val > val) {
                newNode->prev.store(pred);
                newNode->next.store(curr);
                if (pred->next.compare_exchange_strong(curr, newNode)) {
                    curr->prev.store(newNode);
                    return true;
                }
            }
            else {
                delete newNode;
                return false;
            }
        } while (true);
    }

    bool remove(T val) {
        Node<T>* pred = nullptr;
        Node<T>* curr = nullptr;
        do {
            pred = head;
            curr = pred->next.load();
            while (curr != tail && curr->val < val) {
                pred = curr;
                curr = curr->next.load();
            }
            if (curr == tail || curr->val > val) {
                return false;
            }
            if (pred->next.compare_exchange_strong(curr, curr->next.load())) {
                curr->next.load()->prev.store(pred);
                delete curr;
                return true;
            }
        } while (true);
    }

private:
    Node<T>* head;
    Node<T>* tail;
};

上述代码中，insert() 函数用于向链表中插入新节点，remove() 函数用于删除链表中的某个节点。在插入和删除节点时，采用了自旋锁的方式进行多次尝试，直到操作成功。需要注意的是，在使用 CAS 操作修改指针时，需要考虑指针的内存模型，以避免 ABA 问题的发生。另外，为了方便起见，上述代码中使用了 C++11 中的 std::atomic 类型来定义节点的指针，以实现线程安全的操作。