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 
22 namespace tbb {
23 namespace internal {
24 
26 
33 #if TBB_USE_ASSERT
35 #endif /* TBB_USE_ASSERT */
36 };
37 
39 
40 template <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>
53  class iterator_impl {
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;
115  for ( intrusive_list_node *n = my_head.my_next_node; n != &my_head; n = n->my_next_node )
116  ++i;
117  __TBB_ASSERT( my_size == i, "Wrong size" );
118 #endif /* TBB_USE_ASSERT >= 2 */
119  }
120 
121 public:
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  {}
128  iterator () {}
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:
139  : iterator_impl<const_iterator>(const_cast<intrusive_list_node*>(pos) )
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 
157  iterator begin () { return iterator(my_head.my_next_node); }
158 
159  iterator end () { return iterator(&my_head); }
160 
161  const_iterator begin () const { return const_iterator(my_head.my_next_node); }
162 
163  const_iterator end () const { return const_iterator(&my_head); }
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 
189  iterator erase ( iterator it ) {
190  T& val = *it;
191  ++it;
192  remove( val );
193  return it;
194  }
195 
196 }; // intrusive_list_base
197 
198 
200 
208 template <class T, class U, intrusive_list_node U::*NodePtr>
209 class 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 
215  static T& item ( intrusive_list_node* node ) {
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 
229 template <class T>
230 class 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 */
tbb::internal::intrusive_list_base::iterator::iterator
iterator()
Definition: intrusive_list.h:128
tbb::internal::intrusive_list_base
List of element of type T, where T is derived from intrusive_list_node.
Definition: intrusive_list.h:41
tbb::internal::intrusive_list_base::size
size_t size() const
Definition: intrusive_list.h:155
tbb::internal::intrusive_list_base::iterator_impl::operator==
bool operator==(const Iterator &it) const
Definition: intrusive_list.h:79
internal
Definition: _flow_graph_async_msg_impl.h:24
tbb::internal::intrusive_list::node
static intrusive_list_node & node(T &val)
Definition: intrusive_list.h:234
tbb::internal::memptr_intrusive_list
Double linked list of items of type T containing a member of type intrusive_list_node.
Definition: intrusive_list.h:209
tbb::internal::memptr_intrusive_list::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:215
tbb::internal::intrusive_list::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:236
tbb::internal::intrusive_list_base::end
const_iterator end() const
Definition: intrusive_list.h:163
tbb::internal::intrusive_list_base::iterator::operator*
T & operator*() const
Definition: intrusive_list.h:132
tbb::internal::intrusive_list_base::my_size
size_t my_size
Number of list elements.
Definition: intrusive_list.h:46
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::internal::intrusive_list_base::begin
iterator begin()
Definition: intrusive_list.h:157
tbb::internal::intrusive_list_base::begin
const_iterator begin() const
Definition: intrusive_list.h:161
tbb::internal::intrusive_list_base::iterator
Definition: intrusive_list.h:122
tbb::internal::intrusive_list_node
Data structure to be inherited by the types that can form intrusive lists.
Definition: intrusive_list.h:30
tbb::internal::intrusive_list_base::iterator_impl::item
T & item() const
Definition: intrusive_list.h:64
tbb
The graph class.
Definition: serial/tbb/parallel_for.h:46
tbb::internal::intrusive_list_base::iterator_impl::iterator_impl
iterator_impl()
Definition: intrusive_list.h:69
tbb::internal::intrusive_list_base::iterator_impl::my_pos
intrusive_list_node * my_pos
Node the iterator points to at the moment.
Definition: intrusive_list.h:57
tbb::internal::intrusive_list_node::my_next_node
intrusive_list_node * my_next_node
Definition: intrusive_list.h:32
tbb::internal::intrusive_list_base::const_iterator::const_iterator
const_iterator(const intrusive_list_node *pos)
Definition: intrusive_list.h:138
tbb::internal::intrusive_list_base::erase
iterator erase(iterator it)
Definition: intrusive_list.h:189
tbb::internal::intrusive_list_base::my_head
intrusive_list_node my_head
Pointer to the head node.
Definition: intrusive_list.h:43
tbb::internal::intrusive_list_base::iterator::iterator
iterator(intrusive_list_node *pos)
Definition: intrusive_list.h:125
tbb::internal::intrusive_list_base::iterator_impl::operator++
Iterator & operator++()
Definition: intrusive_list.h:87
tbb::internal::memptr_intrusive_list::node
static intrusive_list_node & node(T &val)
Definition: intrusive_list.h:213
tbb::internal::intrusive_list_base::const_iterator::operator->
const T * operator->() const
Definition: intrusive_list.h:143
tbb::internal::intrusive_list_base::remove
void remove(T &val)
Definition: intrusive_list.h:177
tbb::internal::intrusive_list_base::iterator_impl::iterator_impl
iterator_impl(intrusive_list_node *pos)
Definition: intrusive_list.h:60
tbb::internal::intrusive_list_base::iterator_impl::operator!=
bool operator!=(const Iterator &it) const
Definition: intrusive_list.h:83
tbb::internal::intrusive_list_base::const_iterator
Definition: intrusive_list.h:135
tbb::internal::intrusive_list_base::const_iterator::operator*
const T & operator*() const
Definition: intrusive_list.h:145
tbb::internal::intrusive_list_base::iterator::operator->
T * operator->() const
Definition: intrusive_list.h:130
tbb::internal::intrusive_list_base::end
iterator end()
Definition: intrusive_list.h:159
tbb::internal::intrusive_list_base::empty
bool empty() const
Definition: intrusive_list.h:153
tbb::internal::intrusive_list_base::push_front
void push_front(T &val)
Definition: intrusive_list.h:165
tbb::internal::intrusive_list_base::iterator_impl
Definition: intrusive_list.h:53
tbb::internal::intrusive_list_base::iterator_impl::operator--
Iterator & operator--()
Definition: intrusive_list.h:92
tbb::internal::intrusive_list_base::assert_ok
void assert_ok() const
Definition: intrusive_list.h:110
tbb::internal::intrusive_list_base::node
static intrusive_list_node & node(T &item)
Definition: intrusive_list.h:48
tbb::internal::intrusive_list_base::const_iterator::const_iterator
const_iterator()
Definition: intrusive_list.h:141
tbb::internal::intrusive_list_base::intrusive_list_base
intrusive_list_base()
Definition: intrusive_list.h:148
tbb_stddef.h
tbb::internal::intrusive_list_base::iterator_impl::operator=
Iterator & operator=(const Iterator &it)
Definition: intrusive_list.h:71
tbb::internal::intrusive_list_node::my_prev_node
intrusive_list_node * my_prev_node
Definition: intrusive_list.h:31
tbb::internal::intrusive_list
Double linked list of items of type T that is derived from intrusive_list_node class.
Definition: intrusive_list.h:230
tbb::internal::intrusive_list_base::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:50

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.