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

原文地址：https://blog.csdn.net/qq_42805085/article/details/144378830

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！