1 | /* |
2 | * Copyright 2011-present 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 |
119 | |