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 #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 
32  *my_next_node;
33 #if TBB_USE_ASSERT
34  intrusive_list_node () { my_prev_node = my_next_node = this; }
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 {
65  return intrusive_list_base::item(my_pos);
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++ () {
88  my_pos = my_pos->my_next_node;
89  return self();
90  }
91 
92  Iterator& operator-- () {
93  my_pos = my_pos->my_prev_node;
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 {
111  __TBB_ASSERT( (my_head.my_prev_node == &my_head && !my_size) ||
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) {
149  my_head.my_prev_node = &my_head;
150  my_head.my_next_node = &my_head;
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;
170  node(val).my_next_node = my_head.my_next_node;
171  my_head.my_next_node->my_prev_node = &node(val);
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;
181  node(val).my_next_node->my_prev_node = node(val).my_prev_node;
182  node(val).my_prev_node->my_next_node = node(val).my_next_node;
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 */
static intrusive_list_node & node(T &val)
Data structure to be inherited by the types that can form intrusive lists.
static intrusive_list_node & node(T &item)
intrusive_list_node * my_next_node
static intrusive_list_node & node(T &val)
The graph class.
intrusive_list_node * my_prev_node
size_t my_size
Number of list elements.
Double linked list of items of type T that is derived from intrusive_list_node class.
Double linked list of items of type T containing a member of type intrusive_list_node.
bool operator!=(const vector_iterator< Container, T > &i, const vector_iterator< Container, U > &j)
static T & item(intrusive_list_node *node)
static T & item(intrusive_list_node *node)
const_iterator(const intrusive_list_node *pos)
bool operator==(const vector_iterator< Container, T > &i, const vector_iterator< Container, U > &j)
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
intrusive_list_node my_head
Pointer to the head node.
List of element of type T, where T is derived from intrusive_list_node.
intrusive_list_node * my_pos
Node the iterator points to at the moment.
static T & item(intrusive_list_node *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.