Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
Loading...
Searching...
No Matches
intrusive_list.h
Go to the documentation of this file.
1/*
2 Copyright (c) 2005-2020 Intel Corporation
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 _TBB_intrusive_list_H
18#define _TBB_intrusive_list_H
19
20#include "tbb/tbb_stddef.h"
22
23namespace tbb {
24namespace internal {
25
27
34#if TBB_USE_ASSERT
36#endif /* TBB_USE_ASSERT */
37};
38
40
41template <class List, class T>
45
47 size_t my_size;
48
49 static intrusive_list_node& node ( T& item ) { return List::node(item); }
50
51 static T& item ( intrusive_list_node* node ) { return List::item(node); }
52
53 static const T& item( const intrusive_list_node* node ) { return List::item(node); }
54
55 template <typename DereferenceType>
59 "Incorrect DereferenceType in iterator_impl");
63 public:
64 iterator_impl() : my_pos(NULL) {}
65
67
69 if (this != &other) {
70 my_pos = other.my_pos;
71 }
72 return *this;
73 }
74
75 iterator_impl& operator=( const T& val ) {
76 my_pos = &node(val);
77 return *this;
78 }
79
81 my_pos = my_pos->my_next_node;
82 return *this;
83 }
84
86 iterator_impl it(*this);
87 ++*this;
88 return it;
89 }
90
92 my_pos = my_pos->my_prev_node;
93 return *this;
94 }
95
97 iterator_impl it(*this);
98 --*this;
99 return it;
100 }
101
102 bool operator==( const iterator_impl& rhs ) const {
103 return my_pos == rhs.my_pos;
104 }
105
106 bool operator!=( const iterator_impl& rhs ) const {
107 return my_pos != rhs.my_pos;
108 }
109
110 DereferenceType& operator*() const {
112 }
113
114 DereferenceType* operator->() const {
116 }
117
118 private:
119 // Node the iterator points to at the moment
121 }; // class iterator_impl
122
123 void assert_ok () const {
125 (my_head.my_next_node != &my_head && my_size >0), "intrusive_list_base corrupted" );
126#if TBB_USE_ASSERT >= 2
127 size_t i = 0;
129 ++i;
130 __TBB_ASSERT( my_size == i, "Wrong size" );
131#endif /* TBB_USE_ASSERT >= 2 */
132 }
133
134public:
137
141 }
142
143 bool empty () const { return my_head.my_next_node == &my_head; }
144
145 size_t size () const { return my_size; }
146
148
149 iterator end () { return iterator(&my_head); }
150
152
154
155 void push_front ( T& val ) {
156 __TBB_ASSERT( node(val).my_prev_node == &node(val) && node(val).my_next_node == &node(val),
157 "Object with intrusive list node can be part of only one intrusive list simultaneously" );
158 // An object can be part of only one intrusive list at the given moment via the given node member
159 node(val).my_prev_node = &my_head;
162 my_head.my_next_node = &node(val);
163 ++my_size;
164 assert_ok();
165 }
166
167 void remove( T& val ) {
168 __TBB_ASSERT( node(val).my_prev_node != &node(val) && node(val).my_next_node != &node(val), "Element to remove is not in the list" );
169 __TBB_ASSERT( node(val).my_prev_node->my_next_node == &node(val) && node(val).my_next_node->my_prev_node == &node(val), "Element to remove is not in the list" );
170 --my_size;
173#if TBB_USE_ASSERT
174 node(val).my_prev_node = node(val).my_next_node = &node(val);
175#endif
176 assert_ok();
177 }
178
180 T& val = *it;
181 ++it;
182 remove( val );
183 return it;
184 }
185
186}; // intrusive_list_base
187
188
190
198template <class T, class U, intrusive_list_node U::*NodePtr>
199class memptr_intrusive_list : public intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>
200{
201 friend class intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>;
202
203 static intrusive_list_node& node ( T& val ) { return val.*NodePtr; }
204
205 static T& item ( intrusive_list_node* node ) {
206 // Cannot use __TBB_offsetof (and consequently __TBB_get_object_ref) macro
207 // with *NodePtr argument because gcc refuses to interpret pasted "->" and "*"
208 // as member pointer dereferencing operator, and explicit usage of ## in
209 // __TBB_offsetof implementation breaks operations with normal member names.
210 return *reinterpret_cast<T*>((char*)node - ((ptrdiff_t)&(reinterpret_cast<T*>(0x1000)->*NodePtr) - 0x1000));
211 }
212
213 static const T& item( const intrusive_list_node* node ) {
214 return item(const_cast<intrusive_list_node*>(node));
215 }
216}; // intrusive_list<T, U, NodePtr>
217
219
223template <class T>
224class intrusive_list : public intrusive_list_base<intrusive_list<T>, T>
225{
226 friend class intrusive_list_base<intrusive_list<T>, T>;
227
228 static intrusive_list_node& node ( T& val ) { return val; }
229
230 static T& item ( intrusive_list_node* node ) { return *static_cast<T*>(node); }
231 static const T& item( const intrusive_list_node* node ) { return *static_cast<const T*>(node); }
232}; // intrusive_list<T>
233
234} // namespace internal
235} // namespace tbb
236
237#endif /* _TBB_intrusive_list_H */
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
The graph class.
Detects whether two given types are the same.
Data structure to be inherited by the types that can form intrusive lists.
intrusive_list_node * my_prev_node
intrusive_list_node * my_next_node
List of element of type T, where T is derived from intrusive_list_node.
static intrusive_list_node & node(T &item)
intrusive_list_node my_head
Pointer to the head node.
size_t my_size
Number of list elements.
iterator_impl< const T > const_iterator
static const T & item(const intrusive_list_node *node)
static T & item(intrusive_list_node *node)
bool operator!=(const iterator_impl &rhs) const
tbb::internal::conditional< tbb::internal::is_same_type< DereferenceType, T >::value, intrusive_list_node *, constintrusive_list_node * >::type pointer_type
bool operator==(const iterator_impl &rhs) const
__TBB_STATIC_ASSERT((tbb::internal::is_same_type< DereferenceType, T >::value||tbb::internal::is_same_type< DereferenceType, const T >::value), "Incorrect DereferenceType in iterator_impl")
iterator_impl & operator=(const iterator_impl &other)
Double linked list of items of type T containing a member of type intrusive_list_node.
static intrusive_list_node & node(T &val)
static T & item(intrusive_list_node *node)
Double linked list of items of type T that is derived from intrusive_list_node class.
static const T & item(const intrusive_list_node *node)
static T & item(intrusive_list_node *node)
static intrusive_list_node & node(T &val)

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.