Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
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"
21
22namespace tbb {
23namespace internal {
24
26
33#if TBB_USE_ASSERT
35#endif /* TBB_USE_ASSERT */
36};
37
39
40template <class List, class T>
44
46 size_t my_size;
47
48 static intrusive_list_node& node ( T& item ) { return List::node(item); }
49
50 static T& item ( intrusive_list_node* node ) { return List::item(node); }
51
52 template<class Iterator>
54 Iterator& self () { return *static_cast<Iterator*>(this); }
55
58
59 protected:
61 : my_pos(pos)
62 {}
63
64 T& item () const {
66 }
67
68 public:
69 iterator_impl () : my_pos(NULL) {}
70
71 Iterator& operator = ( const Iterator& it ) {
72 return my_pos = it.my_pos;
73 }
74
75 Iterator& operator = ( const T& val ) {
76 return my_pos = &node(val);
77 }
78
79 bool operator == ( const Iterator& it ) const {
80 return my_pos == it.my_pos;
81 }
82
83 bool operator != ( const Iterator& it ) const {
84 return my_pos != it.my_pos;
85 }
86
87 Iterator& operator++ () {
89 return self();
90 }
91
92 Iterator& operator-- () {
94 return self();
95 }
96
97 Iterator operator++ ( int ) {
98 Iterator result = self();
99 ++(*this);
100 return result;
101 }
102
103 Iterator operator-- ( int ) {
104 Iterator result = self();
105 --(*this);
106 return result;
107 }
108 }; // intrusive_list_base::iterator_impl
109
110 void assert_ok () const {
112 (my_head.my_next_node != &my_head && my_size >0), "intrusive_list_base corrupted" );
113#if TBB_USE_ASSERT >= 2
114 size_t i = 0;
116 ++i;
117 __TBB_ASSERT( my_size == i, "Wrong size" );
118#endif /* TBB_USE_ASSERT >= 2 */
119 }
120
121public:
122 class iterator : public iterator_impl<iterator> {
123 template <class U, class V> friend class intrusive_list_base;
124 public:
126 : iterator_impl<iterator>(pos )
127 {}
129
130 T* operator-> () const { return &this->item(); }
131
132 T& operator* () const { return this->item(); }
133 }; // class iterator
134
135 class const_iterator : public iterator_impl<const_iterator> {
136 template <class U, class V> friend class intrusive_list_base;
137 public:
140 {}
142
143 const T* operator-> () const { return &this->item(); }
144
145 const T& operator* () const { return this->item(); }
146 }; // class iterator
147
148 intrusive_list_base () : my_size(0) {
151 }
152
153 bool empty () const { return my_head.my_next_node == &my_head; }
154
155 size_t size () const { return my_size; }
156
158
159 iterator end () { return iterator(&my_head); }
160
162
164
165 void push_front ( T& val ) {
166 __TBB_ASSERT( node(val).my_prev_node == &node(val) && node(val).my_next_node == &node(val),
167 "Object with intrusive list node can be part of only one intrusive list simultaneously" );
168 // An object can be part of only one intrusive list at the given moment via the given node member
169 node(val).my_prev_node = &my_head;
172 my_head.my_next_node = &node(val);
173 ++my_size;
174 assert_ok();
175 }
176
177 void remove( T& val ) {
178 __TBB_ASSERT( node(val).my_prev_node != &node(val) && node(val).my_next_node != &node(val), "Element to remove is not in the list" );
179 __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" );
180 --my_size;
183#if TBB_USE_ASSERT
184 node(val).my_prev_node = node(val).my_next_node = &node(val);
185#endif
186 assert_ok();
187 }
188
190 T& val = *it;
191 ++it;
192 remove( val );
193 return it;
194 }
195
196}; // intrusive_list_base
197
198
200
208template <class T, class U, intrusive_list_node U::*NodePtr>
209class memptr_intrusive_list : public intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>
210{
211 friend class intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>;
212
213 static intrusive_list_node& node ( T& val ) { return val.*NodePtr; }
214
216 // Cannot use __TBB_offsetof (and consequently __TBB_get_object_ref) macro
217 // with *NodePtr argument because gcc refuses to interpret pasted "->" and "*"
218 // as member pointer dereferencing operator, and explicit usage of ## in
219 // __TBB_offsetof implementation breaks operations with normal member names.
220 return *reinterpret_cast<T*>((char*)node - ((ptrdiff_t)&(reinterpret_cast<T*>(0x1000)->*NodePtr) - 0x1000));
221 }
222}; // intrusive_list<T, U, NodePtr>
223
225
229template <class T>
230class intrusive_list : public intrusive_list_base<intrusive_list<T>, T>
231{
232 friend class intrusive_list_base<intrusive_list<T>, T>;
233
234 static intrusive_list_node& node ( T& val ) { return val; }
235
236 static T& item ( intrusive_list_node* node ) { return *static_cast<T*>(node); }
237}; // intrusive_list<T>
238
239} // namespace internal
240} // namespace tbb
241
242#endif /* _TBB_intrusive_list_H */
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
The graph class.
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.
static T & item(intrusive_list_node *node)
intrusive_list_node * my_pos
Node the iterator points to at the moment.
const_iterator(const intrusive_list_node *pos)
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 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.