folly/AtomicLinkedList.h

   1 /*
   2  * Copyright 2016 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 = 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