folly/AtomicLinkedList.h

   1 /*
   2  * Copyright 2015 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 #pragma once
  17
  18 #include <atomic>
  19 #include <cassert>
  20
  21 #include <folly/AtomicIntrusiveLinkedList.h>
  22 #include <folly/Memory.h>
  23
  24 namespace folly {
  25
  26 /**
  27  * A very simple atomic single-linked list primitive.
  28  *
  29  * Usage:
  30  *
  31  * AtomicLinkedList<MyClass> list;
  32  * list.insert(a);
  33  * list.sweep([] (MyClass& c) { doSomething(c); }
  34  */
  35
  36 template <class T>
  37 class AtomicLinkedList {
  38  public:
  39   AtomicLinkedList() {}
  40   AtomicLinkedList(const AtomicLinkedList&) = delete;
  41   AtomicLinkedList& operator=(const AtomicLinkedList&) = delete;
  42   AtomicLinkedList(AtomicLinkedList&& other) noexcept = default;
  43   AtomicLinkedList& operator=(AtomicLinkedList&& other) = default;
  44
  45   ~AtomicLinkedList() {
  46     sweep([](T&&) {});
  47   }
  48
  49   bool empty() const { return list_.empty(); }
  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 = folly::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  private:
  77   struct Wrapper {
  78     explicit Wrapper(T&& t) : data(std::move(t)) {}
  79
  80     AtomicIntrusiveLinkedListHook<Wrapper> hook;
  81     T data;
  82   };
  83   AtomicIntrusiveLinkedList<Wrapper, &Wrapper::hook> list_;
  84 };
  85
  86 } // namespace folly