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
26namespace folly {
27
28/**
29 * An auto-unlink intrusive list hook.
30 */
31using 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 */
64template <typename T, IntrusiveListHook T::*PtrToMember>
65using 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 */
73using 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 */
112template <typename T, SafeIntrusiveListHook T::*PtrToMember>
113using 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