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