folly/IntrusiveList.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 /*
  20  * This file contains convenience aliases that make boost::intrusive::list
  21  * easier to use.
  22  */
  23
  24 #include <boost/intrusive/list.hpp>
  25
  26 namespace folly {
  27
  28 /**
  29  * An auto-unlink intrusive list hook.
  30  */
  31 using IntrusiveListHook = boost::intrusive::list_member_hook<
  32       boost::intrusive::link_mode<boost::intrusive::auto_unlink>>;
  33
  34 /**
  35  * An intrusive list.
  36  *
  37  * An IntrusiveList always uses an auto-unlink hook.
  38  * Beware that IntrusiveList::size() is an O(n) operation, since it has to walk
  39  * the entire list.
  40  *
  41  * Example usage:
  42  *
  43  *   class Foo {
  44  *     // Note that the listHook member variable needs to be visible
  45  *     // to the code that defines the IntrusiveList instantiation.
  46  *     // The list hook can be made public, or you can make the other class a
  47  *     // friend.
  48  *     IntrusiveListHook listHook;
  49  *   };
  50  *
  51  *   using FooList = IntrusiveList<Foo, &Foo::listHook>;
  52  *
  53  *   Foo *foo = new Foo();
  54  *   FooList myList;
  55  *   myList.push_back(*foo);
  56  *
  57  * Note that each IntrusiveListHook can only be part of a single list at any
  58  * given time.  If you need the same object to be stored in two lists at once,
  59  * you need to use two different IntrusiveListHook member variables.
  60  *
  61  * The elements stored in the list must contain an IntrusiveListHook member
  62  * variable.
  63  */
  64 template <typename T, IntrusiveListHook T::*PtrToMember>
  65 using IntrusiveList = boost::intrusive::list<
  66     T,
  67     boost::intrusive::member_hook<T, IntrusiveListHook, PtrToMember>,
  68     boost::intrusive::constant_time_size<false>>;
  69
  70 /**
  71  * A safe-link intrusive list hook.
  72  */
  73 using SafeIntrusiveListHook = boost::intrusive::list_member_hook<
  74       boost::intrusive::link_mode<boost::intrusive::safe_link>>;
  75
  76 /**
  77  * An intrusive list with const-time size() method.
  78  *
  79  * A CountedIntrusiveList always uses a safe-link hook.
  80  * CountedIntrusiveList::size() is an O(1) operation. Users of this type
  81  * of lists need to remove a member from a list by calling one of the
  82  * methods on the list (e.g., erase(), pop_front(), etc.), rather than
  83  * calling unlink on the member's list hook. Given references to a
  84  * list and a member, a constant-time removal operation can be
  85  * accomplished by list.erase(list.iterator_to(member)). Also, when a
  86  * member is destroyed, it is NOT automatically removed from the list.
  87  *
  88  * Example usage:
  89  *
  90  *   class Foo {
  91  *     // Note that the listHook member variable needs to be visible
  92  *     // to the code that defines the CountedIntrusiveList instantiation.
  93  *     // The list hook can be made public, or you can make the other class a
  94  *     // friend.
  95  *     SafeIntrusiveListHook listHook;
  96  *   };
  97  *
  98  *   using FooList = CountedIntrusiveList<Foo, &Foo::listHook> FooList;
  99  *
 100  *   Foo *foo = new Foo();
 101  *   FooList myList;
 102  *   myList.push_back(*foo);
 103  *   myList.pop_front();
 104  *
 105  * Note that each SafeIntrusiveListHook can only be part of a single list at any
 106  * given time.  If you need the same object to be stored in two lists at once,
 107  * you need to use two different SafeIntrusiveListHook member variables.
 108  *
 109  * The elements stored in the list must contain an SafeIntrusiveListHook member
 110  * variable.
 111  */
 112 template <typename T, SafeIntrusiveListHook T::*PtrToMember>
 113 using CountedIntrusiveList = boost::intrusive::list<
 114     T,
 115     boost::intrusive::member_hook<T, SafeIntrusiveListHook, PtrToMember>,
 116     boost::intrusive::constant_time_size<true>>;
 117
 118 } // namespace folly