folly/AtomicLinkedList.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <folly/AtomicIntrusiveLinkedList.h>
  20 #include <folly/Memory.h>
  21
  22 namespace folly {
  23
  24 /**
  25  * A very simple atomic single-linked list primitive.
  26  *
  27  * Usage:
  28  *
  29  * AtomicLinkedList<MyClass> list;
  30  * list.insert(a);
  31  * list.sweep([] (MyClass& c) { doSomething(c); }
  32  */
  33
  34 template <class T>
  35 class AtomicLinkedList {
  36  public:
  37   AtomicLinkedList() {}
  38   AtomicLinkedList(const AtomicLinkedList&) = delete;
  39   AtomicLinkedList& operator=(const AtomicLinkedList&) = delete;
  40   AtomicLinkedList(AtomicLinkedList&& other) noexcept = default;
  41   AtomicLinkedList& operator=(AtomicLinkedList&& other) = default;
  42
  43   ~AtomicLinkedList() {
  44     sweep([](T&&) {});
  45   }
  46
  47   bool empty() const {
  48     return list_.empty();
  49   }
  50
  51   /**
  52    * Atomically insert t at the head of the list.
  53    * @return True if the inserted element is the only one in the list
  54    *         after the call.
  55    */
  56   bool insertHead(T t) {
  57     auto wrapper = std::make_unique<Wrapper>(std::move(t));
  58
  59     return list_.insertHead(wrapper.release());
  60   }
  61
  62   /**
  63    * Repeatedly pops element from head,
  64    * and calls func() on the removed elements in the order from tail to head.
  65    * Stops when the list is empty.
  66    */
  67   template <typename F>
  68   void sweep(F&& func) {
  69     list_.sweep([&](Wrapper* wrapperPtr) mutable {
  70       std::unique_ptr<Wrapper> wrapper(wrapperPtr);
  71
  72       func(std::move(wrapper->data));
  73     });
  74   }
  75
  76   /**
  77    * Similar to sweep() but calls func() on elements in LIFO order.
  78    *
  79    * func() is called for all elements in the list at the moment
  80    * reverseSweep() is called.  Unlike sweep() it does not loop to ensure the
  81    * list is empty at some point after the last invocation.  This way callers
  82    * can reason about the ordering: elements inserted since the last call to
  83    * reverseSweep() will be provided in LIFO order.
  84    *
  85    * Example: if elements are inserted in the order 1-2-3, the callback is
  86    * invoked 3-2-1.  If the callback moves elements onto a stack, popping off
  87    * the stack will produce the original insertion order 1-2-3.
  88    */
  89   template <typename F>
  90   void reverseSweep(F&& func) {
  91     list_.reverseSweep([&](Wrapper* wrapperPtr) mutable {
  92       std::unique_ptr<Wrapper> wrapper(wrapperPtr);
  93
  94       func(std::move(wrapper->data));
  95     });
  96   }
  97
  98  private:
  99   struct Wrapper {
 100     explicit Wrapper(T&& t) : data(std::move(t)) {}
 101
 102     AtomicIntrusiveLinkedListHook<Wrapper> hook;
 103     T data;
 104   };
 105   AtomicIntrusiveLinkedList<Wrapper, &Wrapper::hook> list_;
 106 };
 107
 108 } // namespace folly