123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178 |
- /*
- * Copyright 2014-present Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- #pragma once
- #include <atomic>
- #include <cassert>
- #include <utility>
- namespace folly {
- /**
- * A very simple atomic single-linked list primitive.
- *
- * Usage:
- *
- * class MyClass {
- * AtomicIntrusiveLinkedListHook<MyClass> hook_;
- * }
- *
- * AtomicIntrusiveLinkedList<MyClass, &MyClass::hook_> list;
- * list.insert(&a);
- * list.sweep([] (MyClass* c) { doSomething(c); }
- */
- 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;
- }
- /**
- * Note: list must be empty on destruction.
- */
- ~AtomicIntrusiveLinkedList() {
- assert(empty());
- }
- bool empty() const {
- return head_.load() == nullptr;
- }
- /**
- * Atomically insert t at the head of the list.
- * @return True if the inserted element is the only one in the list
- * after the call.
- */
- bool insertHead(T* t) {
- assert(next(t) == nullptr);
- auto oldHead = head_.load(std::memory_order_relaxed);
- do {
- next(t) = oldHead;
- /* oldHead is updated by the call below.
- NOTE: we don't use next(t) instead of oldHead directly due to
- compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
- MSVC (bug 819819); source:
- http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
- } while (!head_.compare_exchange_weak(
- oldHead, t, std::memory_order_release, std::memory_order_relaxed));
- return oldHead == nullptr;
- }
- /**
- * Replaces the head with nullptr,
- * and calls func() on the removed elements in the order from tail to head.
- * Returns false if the list was empty.
- */
- template <typename F>
- bool sweepOnce(F&& func) {
- if (auto head = head_.exchange(nullptr)) {
- auto rhead = reverse(head);
- unlinkAll(rhead, std::forward<F>(func));
- return true;
- }
- return false;
- }
- /**
- * Repeatedly replaces the head with nullptr,
- * and calls func() on the removed elements in the order from tail to head.
- * Stops when the list is empty.
- */
- template <typename F>
- void sweep(F&& func) {
- while (sweepOnce(func)) {
- }
- }
- /**
- * Similar to sweep() but calls func() on elements in LIFO order.
- *
- * func() is called for all elements in the list at the moment
- * reverseSweep() is called. Unlike sweep() it does not loop to ensure the
- * list is empty at some point after the last invocation. This way callers
- * can reason about the ordering: elements inserted since the last call to
- * reverseSweep() will be provided in LIFO order.
- *
- * Example: if elements are inserted in the order 1-2-3, the callback is
- * invoked 3-2-1. If the callback moves elements onto a stack, popping off
- * the stack will produce the original insertion order 1-2-3.
- */
- template <typename F>
- void reverseSweep(F&& func) {
- // We don't loop like sweep() does because the overall order of callbacks
- // would be strand-wise LIFO which is meaningless to callers.
- auto head = head_.exchange(nullptr);
- unlinkAll(head, std::forward<F>(func));
- }
- private:
- std::atomic<T*> head_{nullptr};
- static T*& next(T* t) {
- return (t->*HookMember).next;
- }
- /* Reverses a linked list, returning the pointer to the new head
- (old tail) */
- static T* reverse(T* head) {
- T* rhead = nullptr;
- while (head != nullptr) {
- auto t = head;
- head = next(t);
- next(t) = rhead;
- rhead = t;
- }
- return rhead;
- }
- /* Unlinks all elements in the linked list fragment pointed to by `head',
- * calling func() on every element */
- template <typename F>
- void unlinkAll(T* head, F&& func) {
- while (head != nullptr) {
- auto t = head;
- head = next(t);
- next(t) = nullptr;
- func(t);
- }
- }
- };
- } // namespace folly
|