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-2019 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 
18 
19 */
20 
21 #ifndef _TBB_intrusive_list_H
22 #define _TBB_intrusive_list_H
23 
24 #include "tbb/tbb_stddef.h"
25 
26 namespace tbb {
27 namespace internal {
28 
30 
36  *my_next_node;
37 #if TBB_USE_ASSERT
39 #endif /* TBB_USE_ASSERT */
40 };
41 
43 
44 template <class List, class T>
48 
50  size_t my_size;
51 
52  static intrusive_list_node& node ( T& item ) { return List::node(item); }
53 
54  static T& item ( intrusive_list_node* node ) { return List::item(node); }
55 
56  template<class Iterator>
57  class iterator_impl {
58  Iterator& self () { return *static_cast<Iterator*>(this); }
59 
62 
63  protected:
65  : my_pos(pos)
66  {}
67 
68  T& item () const {
70  }
71 
72  public:
73  iterator_impl () : my_pos(NULL) {}
74 
75  Iterator& operator = ( const Iterator& it ) {
76  return my_pos = it.my_pos;
77  }
78 
79  Iterator& operator = ( const T& val ) {
80  return my_pos = &node(val);
81  }
82 
83  bool operator == ( const Iterator& it ) const {
84  return my_pos == it.my_pos;
85  }
86 
87  bool operator != ( const Iterator& it ) const {
88  return my_pos != it.my_pos;
89  }
90 
91  Iterator& operator++ () {
93  return self();
94  }
95 
96  Iterator& operator-- () {
98  return self();
99  }
100 
101  Iterator operator++ ( int ) {
102  Iterator result = self();
103  ++(*this);
104  return result;
105  }
106 
107  Iterator operator-- ( int ) {
108  Iterator result = self();
109  --(*this);
110  return result;
111  }
112  }; // intrusive_list_base::iterator_impl
113 
114  void assert_ok () const {
116  (my_head.my_next_node != &my_head && my_size >0), "intrusive_list_base corrupted" );
117 #if TBB_USE_ASSERT >= 2
118  size_t i = 0;
119  for ( intrusive_list_node *n = my_head.my_next_node; n != &my_head; n = n->my_next_node )
120  ++i;
121  __TBB_ASSERT( my_size == i, "Wrong size" );
122 #endif /* TBB_USE_ASSERT >= 2 */
123  }
124 
125 public:
126  class iterator : public iterator_impl<iterator> {
127  template <class U, class V> friend class intrusive_list_base;
128  public:
130  : iterator_impl<iterator>(pos )
131  {}
132  iterator () {}
133 
134  T* operator-> () const { return &this->item(); }
135 
136  T& operator* () const { return this->item(); }
137  }; // class iterator
138 
139  class const_iterator : public iterator_impl<const_iterator> {
140  template <class U, class V> friend class intrusive_list_base;
141  public:
143  : iterator_impl<const_iterator>(const_cast<intrusive_list_node*>(pos) )
144  {}
146 
147  const T* operator-> () const { return &this->item(); }
148 
149  const T& operator* () const { return this->item(); }
150  }; // class iterator
151 
152  intrusive_list_base () : my_size(0) {
155  }
156 
157  bool empty () const { return my_head.my_next_node == &my_head; }
158 
159  size_t size () const { return my_size; }
160 
161  iterator begin () { return iterator(my_head.my_next_node); }
162 
163  iterator end () { return iterator(&my_head); }
164 
165  const_iterator begin () const { return const_iterator(my_head.my_next_node); }
166 
167  const_iterator end () const { return const_iterator(&my_head); }
168 
169  void push_front ( T& val ) {
170  __TBB_ASSERT( node(val).my_prev_node == &node(val) && node(val).my_next_node == &node(val),
171  "Object with intrusive list node can be part of only one intrusive list simultaneously" );
172  // An object can be part of only one intrusive list at the given moment via the given node member
173  node(val).my_prev_node = &my_head;
176  my_head.my_next_node = &node(val);
177  ++my_size;
178  assert_ok();
179  }
180 
181  void remove( T& val ) {
182  __TBB_ASSERT( node(val).my_prev_node != &node(val) && node(val).my_next_node != &node(val), "Element to remove is not in the list" );
183  __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" );
184  --my_size;
187 #if TBB_USE_ASSERT
188  node(val).my_prev_node = node(val).my_next_node = &node(val);
189 #endif
190  assert_ok();
191  }
192 
193  iterator erase ( iterator it ) {
194  T& val = *it;
195  ++it;
196  remove( val );
197  return it;
198  }
199 
200 }; // intrusive_list_base
201 
202 
204 
212 template <class T, class U, intrusive_list_node U::*NodePtr>
213 class memptr_intrusive_list : public intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>
214 {
215  friend class intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>;
216 
217  static intrusive_list_node& node ( T& val ) { return val.*NodePtr; }
218 
219  static T& item ( intrusive_list_node* node ) {
220  // Cannot use __TBB_offsetof (and consequently __TBB_get_object_ref) macro
221  // with *NodePtr argument because gcc refuses to interpret pasted "->" and "*"
222  // as member pointer dereferencing operator, and explicit usage of ## in
223  // __TBB_offsetof implementation breaks operations with normal member names.
224  return *reinterpret_cast<T*>((char*)node - ((ptrdiff_t)&(reinterpret_cast<T*>(0x1000)->*NodePtr) - 0x1000));
225  }
226 }; // intrusive_list<T, U, NodePtr>
227 
229 
233 template <class T>
234 class intrusive_list : public intrusive_list_base<intrusive_list<T>, T>
235 {
236  friend class intrusive_list_base<intrusive_list<T>, T>;
237 
238  static intrusive_list_node& node ( T& val ) { return val; }
239 
240  static T& item ( intrusive_list_node* node ) { return *static_cast<T*>(node); }
241 }; // intrusive_list<T>
242 
243 } // namespace internal
244 } // namespace tbb
245 
246 #endif /* _TBB_intrusive_list_H */
static T & item(intrusive_list_node *node)
const_iterator(const intrusive_list_node *pos)
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
intrusive_list_node * my_prev_node
intrusive_list_node * my_pos
Node the iterator points to at the moment.
static intrusive_list_node & node(T &item)
List of element of type T, where T is derived from intrusive_list_node.
Double linked list of items of type T that is derived from intrusive_list_node class.
size_t my_size
Number of list elements.
intrusive_list_node * my_next_node
static intrusive_list_node & node(T &val)
The graph class.
static intrusive_list_node & node(T &val)
intrusive_list_node my_head
Pointer to the head node.
static T & item(intrusive_list_node *node)
static T & item(intrusive_list_node *node)
Data structure to be inherited by the types that can form intrusive lists.
Double linked list of items of type T containing a member of type intrusive_list_node.

Copyright © 2005-2019 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.