2 * Copyright 2014 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 typedefs that make boost::intrusive::list
25 #include <boost/intrusive/list.hpp>
30 * An auto-unlink intrusive list hook.
32 typedef boost::intrusive::list_member_hook<
33 boost::intrusive::link_mode<boost::intrusive::auto_unlink> >
39 * An IntrusiveList always uses an auto-unlink hook.
40 * Beware that IntrusiveList::size() is an O(n) operation, since it has to walk
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
50 * IntrusiveListHook listHook;
53 * typedef IntrusiveList<Foo, &Foo::listHook> FooList;
55 * Foo *foo = new Foo();
57 * myList.push_back(*foo);
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.
63 * The elements stored in the list must contain an IntrusiveListHook member
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.
71 template<typename T, IntrusiveListHook T::* PtrToMember>
72 class IntrusiveList : public boost::intrusive::list<
74 boost::intrusive::member_hook<T, IntrusiveListHook, PtrToMember>,
75 boost::intrusive::constant_time_size<false> > {
79 * A safe-link intrusive list hook.
81 typedef boost::intrusive::list_member_hook<
82 boost::intrusive::link_mode<boost::intrusive::safe_link> >
83 SafeIntrusiveListHook;
86 * An intrusive list with const-time size() method.
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.
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
104 * SafeIntrusiveListHook listHook;
107 * typedef CountedIntrusiveList<Foo, &Foo::listHook> FooList;
109 * Foo *foo = new Foo();
111 * myList.push_back(*foo);
112 * myList.pop_front();
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.
118 * The elements stored in the list must contain an SafeIntrusiveListHook member
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.
126 template<typename T, SafeIntrusiveListHook T::* PtrToMember>
127 class CountedIntrusiveList : public boost::intrusive::list<
129 boost::intrusive::member_hook<T, SafeIntrusiveListHook, PtrToMember>,
130 boost::intrusive::constant_time_size<true> > {
135 #endif // FOLLY_INTRUSIVELIST_H_