folly/IntrusiveList.h

   1 /*
   2  * Copyright 2012 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 typedefs 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 typedef boost::intrusive::list_member_hook<
  33       boost::intrusive::link_mode<boost::intrusive::auto_unlink> >
  34         IntrusiveListHook;
  35
  36 /**
  37  * An intrusive list.
  38  *
  39  * An IntrusiveList always uses an auto-unlink hook.
  40  * Beware that IntrusiveList::size() is an O(n) operation, since it has to walk
  41  * the entire list.
  42  *
  43  * Example usage:
  44  *
  45  *   class Foo {
  46  *     // Note that the listHook member variable needs to be visible
  47  *     // to the code that defines the IntrusiveList instantiation.
  48  *     // The list hook can be made public, or you can make the other class a
  49  *     // friend.
  50  *     IntrusiveListHook listHook;
  51  *   };
  52  *
  53  *   typedef IntrusiveList<Foo, &Foo::listHook> FooList;
  54  *
  55  *   Foo *foo = new Foo();
  56  *   FooList myList;
  57  *   myList.push_back(*foo);
  58  *
  59  * Note that each IntrusiveListHook can only be part of a single list at any
  60  * given time.  If you need the same object to be stored in two lists at once,
  61  * you need to use two different IntrusiveListHook member variables.
  62  *
  63  * The elements stored in the list must contain an IntrusiveListHook member
  64  * variable.
  65  *
  66  * TODO: This should really be a template alias.  However, gcc doesn't support
  67  * template aliases yet.  A subclass is a reasonable workaround for now.  This
  68  * subclass only supports the default constructor, but we could add other
  69  * constructors if necessary.
  70  */
  71 template<typename T, IntrusiveListHook T::* PtrToMember>
  72 class IntrusiveList : public boost::intrusive::list<
  73     T,
  74     boost::intrusive::member_hook<T, IntrusiveListHook, PtrToMember>,
  75     boost::intrusive::constant_time_size<false> > {
  76 };
  77
  78 /**
  79  * A safe-link intrusive list hook.
  80  */
  81 typedef boost::intrusive::list_member_hook<
  82       boost::intrusive::link_mode<boost::intrusive::safe_link> >
  83         SafeIntrusiveListHook;
  84
  85 /**
  86  * An intrusive list with const-time size() method.
  87  *
  88  * A CountedIntrusiveList always uses a safe-link hook.
  89  * CountedIntrusiveList::size() is an O(1) operation. Users of this type
  90  * of lists need to remove a member from a list by calling one of the
  91  * methods on the list (e.g., erase(), pop_front(), etc.), rather than
  92  * calling unlink on the member's list hook. Given references to a
  93  * list and a member, a constant-time removal operation can be
  94  * accomplished by list.erase(list.iterator_to(member)). Also, when a
  95  * member is destroyed, it is NOT automatically removed from the list.
  96  *
  97  * Example usage:
  98  *
  99  *   class Foo {
 100  *     // Note that the listHook member variable needs to be visible
 101  *     // to the code that defines the CountedIntrusiveList instantiation.
 102  *     // The list hook can be made public, or you can make the other class a
 103  *     // friend.
 104  *     SafeIntrusiveListHook listHook;
 105  *   };
 106  *
 107  *   typedef CountedIntrusiveList<Foo, &Foo::listHook> FooList;
 108  *
 109  *   Foo *foo = new Foo();
 110  *   FooList myList;
 111  *   myList.push_back(*foo);
 112  *   myList.pop_front();
 113  *
 114  * Note that each SafeIntrusiveListHook can only be part of a single list at any
 115  * given time.  If you need the same object to be stored in two lists at once,
 116  * you need to use two different SafeIntrusiveListHook member variables.
 117  *
 118  * The elements stored in the list must contain an SafeIntrusiveListHook member
 119  * variable.
 120  *
 121  * TODO: This should really be a template alias.  However, gcc doesn't support
 122  * template aliases yet.  A subclass is a reasonable workaround for now.  This
 123  * subclass only supports the default constructor, but we could add other
 124  * constructors if necessary.
 125  */
 126 template<typename T, SafeIntrusiveListHook T::* PtrToMember>
 127 class CountedIntrusiveList : public boost::intrusive::list<
 128     T,
 129     boost::intrusive::member_hook<T, SafeIntrusiveListHook, PtrToMember>,
 130     boost::intrusive::constant_time_size<true> > {
 131 };
 132
 133 } // folly
 134
 135 #endif // FOLLY_INTRUSIVELIST_H_