2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef FOLLY_INTRUSIVELIST_H_
18 #define FOLLY_INTRUSIVELIST_H_
21 * This file contains convenience aliases that make boost::intrusive::list
25 #include <boost/intrusive/list.hpp>
30 * An auto-unlink intrusive list hook.
32 using IntrusiveListHook = boost::intrusive::list_member_hook<
33 boost::intrusive::link_mode<boost::intrusive::auto_unlink>>;
38 * An IntrusiveList always uses an auto-unlink hook.
39 * Beware that IntrusiveList::size() is an O(n) operation, since it has to walk
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
49 * IntrusiveListHook listHook;
52 * using FooList = IntrusiveList<Foo, &Foo::listHook>;
54 * Foo *foo = new Foo();
56 * myList.push_back(*foo);
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.
62 * The elements stored in the list must contain an IntrusiveListHook member
65 template<typename T, IntrusiveListHook T::* PtrToMember>
66 using IntrusiveList = boost::intrusive::list<
68 boost::intrusive::member_hook<T, IntrusiveListHook, PtrToMember>,
69 boost::intrusive::constant_time_size<false>>;
72 * A safe-link intrusive list hook.
74 using SafeIntrusiveListHook = boost::intrusive::list_member_hook<
75 boost::intrusive::link_mode<boost::intrusive::safe_link>>;
78 * An intrusive list with const-time size() method.
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.
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
96 * SafeIntrusiveListHook listHook;
99 * using FooList = CountedIntrusiveList<Foo, &Foo::listHook> FooList;
101 * Foo *foo = new Foo();
103 * myList.push_back(*foo);
104 * myList.pop_front();
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.
110 * The elements stored in the list must contain an SafeIntrusiveListHook member
113 template<typename T, SafeIntrusiveListHook T::* PtrToMember>
114 using CountedIntrusiveList = boost::intrusive::list<
116 boost::intrusive::member_hook<T, SafeIntrusiveListHook, PtrToMember>,
117 boost::intrusive::constant_time_size<true>>;
121 #endif // FOLLY_INTRUSIVELIST_H_