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"
22 
23 namespace tbb {
24 namespace internal {
25 
27 
34 #if TBB_USE_ASSERT
36 #endif /* TBB_USE_ASSERT */
37 };
38 
40 
41 template <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>
56  class iterator_impl {
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 
82  return *this;
83  }
84 
86  iterator_impl it(*this);
87  ++*this;
88  return it;
89  }
90 
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;
128  for ( intrusive_list_node *n = my_head.my_next_node; n != &my_head; n = n->my_next_node )
129  ++i;
130  __TBB_ASSERT( my_size == i, "Wrong size" );
131 #endif /* TBB_USE_ASSERT >= 2 */
132  }
133 
134 public:
135  typedef iterator_impl<T> iterator;
136  typedef iterator_impl<const T> const_iterator;
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 
153  const_iterator end () const { return const_iterator(&my_head); }
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 
198 template <class T, class U, intrusive_list_node U::*NodePtr>
199 class 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 
223 template <class T>
224 class 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 */
tbb::internal::intrusive_list_base::item
static const T & item(const intrusive_list_node *node)
Definition: intrusive_list.h:53
tbb::internal::intrusive_list_base::push_front
void push_front(T &val)
Definition: intrusive_list.h:155
tbb::internal::intrusive_list_base::iterator_impl::iterator_impl
iterator_impl(pointer_type pos)
Definition: intrusive_list.h:66
tbb::internal::intrusive_list_node::my_next_node
intrusive_list_node * my_next_node
Definition: intrusive_list.h:33
internal
Definition: _flow_graph_async_msg_impl.h:24
tbb::internal::intrusive_list_base::iterator_impl::operator->
DereferenceType * operator->() const
Definition: intrusive_list.h:114
tbb::internal::intrusive_list_base::iterator_impl::my_pos
pointer_type my_pos
Definition: intrusive_list.h:120
tbb::internal::intrusive_list_base::iterator_impl::operator--
iterator_impl operator--(int)
Definition: intrusive_list.h:96
tbb::internal::intrusive_list_base::iterator_impl::pointer_type
tbb::internal::conditional< tbb::internal::is_same_type< DereferenceType, T >::value, intrusive_list_node *, const intrusive_list_node * >::type pointer_type
Definition: intrusive_list.h:62
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::internal::intrusive_list_base
List of element of type T, where T is derived from intrusive_list_node.
Definition: intrusive_list.h:42
tbb::internal::intrusive_list_base::end
iterator end()
Definition: intrusive_list.h:149
tbb::internal::intrusive_list_node::my_prev_node
intrusive_list_node * my_prev_node
Definition: intrusive_list.h:32
tbb::internal::intrusive_list_base::iterator_impl::operator=
iterator_impl & operator=(const T &val)
Definition: intrusive_list.h:75
tbb
The graph class.
Definition: serial/tbb/parallel_for.h:46
tbb::internal::memptr_intrusive_list::item
static const T & item(const intrusive_list_node *node)
Definition: intrusive_list.h:213
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:200
tbb::internal::intrusive_list_node
Data structure to be inherited by the types that can form intrusive lists.
Definition: intrusive_list.h:31
tbb::internal::intrusive_list_base::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:51
tbb::internal::intrusive_list_base::iterator_impl::operator++
iterator_impl & operator++()
Definition: intrusive_list.h:80
tbb::internal::intrusive_list_base::intrusive_list_base
intrusive_list_base()
Definition: intrusive_list.h:138
_template_helpers.h
tbb::internal::intrusive_list_base::size
size_t size() const
Definition: intrusive_list.h:145
tbb::internal::intrusive_list_base::iterator_impl::__TBB_STATIC_ASSERT
__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")
tbb::internal::intrusive_list::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:230
tbb::internal::intrusive_list_base::iterator_impl::operator--
iterator_impl & operator--()
Definition: intrusive_list.h:91
tbb::internal::intrusive_list::item
static const T & item(const intrusive_list_node *node)
Definition: intrusive_list.h:231
tbb::internal::intrusive_list_base::begin
const_iterator begin() const
Definition: intrusive_list.h:151
tbb::internal::intrusive_list_base::erase
iterator erase(iterator it)
Definition: intrusive_list.h:179
tbb::internal::intrusive_list_base::iterator_impl::operator++
iterator_impl operator++(int)
Definition: intrusive_list.h:85
tbb::internal::memptr_intrusive_list::node
static intrusive_list_node & node(T &val)
Definition: intrusive_list.h:203
tbb::internal::intrusive_list_base::node
static intrusive_list_node & node(T &item)
Definition: intrusive_list.h:49
tbb::internal::intrusive_list_base::const_iterator
iterator_impl< const T > const_iterator
Definition: intrusive_list.h:136
tbb::internal::memptr_intrusive_list::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:205
tbb::internal::intrusive_list_base::end
const_iterator end() const
Definition: intrusive_list.h:153
tbb::internal::intrusive_list_base::my_size
size_t my_size
Number of list elements.
Definition: intrusive_list.h:47
tbb::internal::is_same_type
Detects whether two given types are the same.
Definition: _template_helpers.h:61
tbb::internal::intrusive_list_base::begin
iterator begin()
Definition: intrusive_list.h:147
tbb::internal::intrusive_list::node
static intrusive_list_node & node(T &val)
Definition: intrusive_list.h:228
tbb::internal::intrusive_list_base::iterator_impl::operator*
DereferenceType & operator*() const
Definition: intrusive_list.h:110
tbb::internal::intrusive_list_base::my_head
intrusive_list_node my_head
Pointer to the head node.
Definition: intrusive_list.h:44
tbb::internal::intrusive_list_base::assert_ok
void assert_ok() const
Definition: intrusive_list.h:123
tbb::internal::conditional
Definition: _template_helpers.h:299
tbb::internal::intrusive_list_base::iterator_impl::iterator_impl
iterator_impl()
Definition: intrusive_list.h:64
tbb::internal::intrusive_list
Double linked list of items of type T that is derived from intrusive_list_node class.
Definition: intrusive_list.h:225
tbb::internal::intrusive_list_base::empty
bool empty() const
Definition: intrusive_list.h:143
tbb::internal::intrusive_list_base::iterator
iterator_impl< T > iterator
Definition: intrusive_list.h:135
tbb::internal::intrusive_list_base::iterator_impl
Definition: intrusive_list.h:56
tbb_stddef.h
type
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
Definition: ittnotify_static.h:198
tbb::internal::intrusive_list_base::iterator_impl::operator!=
bool operator!=(const iterator_impl &rhs) const
Definition: intrusive_list.h:106
tbb::internal::intrusive_list_base::iterator_impl::operator=
iterator_impl & operator=(const iterator_impl &other)
Definition: intrusive_list.h:68
tbb::internal::intrusive_list_base::iterator_impl::operator==
bool operator==(const iterator_impl &rhs) const
Definition: intrusive_list.h:102
tbb::internal::intrusive_list_base::remove
void remove(T &val)
Definition: intrusive_list.h:167

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.