folly之侵入式链表

侵入式链表

侵入式链表（Intrusive Linked List）是一种数据结构，它的节点不是通过包含链表节点的对象来实现的（像非侵入式链表那样），而是通过在节点对象中直接包含指向其他节点的指针来实现的。这意味着链表节点对象本身需要被修改以包含指向链表其他部分的指针。

直接上代码

template <class T>
struct AtomicIntrusiveLinkedListHook {T* next{nullptr};
};template <class T, AtomicIntrusiveLinkedListHook<T> T::*HookMember>
class AtomicIntrusiveLinkedList {public:AtomicIntrusiveLinkedList() {}AtomicIntrusiveLinkedList(const AtomicIntrusiveLinkedList&) = delete;AtomicIntrusiveLinkedList& operator=(const AtomicIntrusiveLinkedList&) =delete;AtomicIntrusiveLinkedList(AtomicIntrusiveLinkedList&& other) noexcept {auto tmp = other.head_.load();other.head_ = head_.load();head_ = tmp;}AtomicIntrusiveLinkedList& operator=(AtomicIntrusiveLinkedList&& other) noexcept {auto tmp = other.head_.load();other.head_ = head_.load();head_ = tmp;return *this;}~AtomicIntrusiveLinkedList() {assert(empty());}bool empty() const {return head_.load() == nullptr;}bool insertHead(T* t) {assert(next(t) == nullptr);auto oldHead = head_.load(std::memory_order_relaxed);do {next(t) = oldHead;} while (!head_.compare_exchange_weak(oldHead, t,std::memory_order_release,std::memory_order_relaxed));return oldHead == nullptr;}template <typename F>bool swee