1 /* 2 Copyright (c) 2005-2021 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 "oneapi/tbb/detail/_intrusive_list_node.h" 21 22 namespace tbb { 23 namespace detail { 24 namespace r1 { 25 26 using d1::intrusive_list_node; 27 28 //! List of element of type T, where T is derived from intrusive_list_node 29 /** The class is not thread safe. **/ 30 template <class List, class T> 31 class intrusive_list_base { 32 //! Pointer to the head node 33 intrusive_list_node my_head; 34 35 //! Number of list elements 36 std::size_t my_size; 37 node(T & item)38 static intrusive_list_node& node ( T& item ) { return List::node(item); } 39 item(intrusive_list_node * node)40 static T& item ( intrusive_list_node* node ) { return List::item(node); } 41 item(const intrusive_list_node * node)42 static const T& item( const intrusive_list_node* node ) { return List::item(node); } 43 44 template <typename DereferenceType> 45 class iterator_impl { 46 static_assert(std::is_same<DereferenceType, T>::value || 47 std::is_same<DereferenceType, const T>::value, 48 "Incorrect DereferenceType in iterator_impl"); 49 50 using pointer_type = typename std::conditional<std::is_same<DereferenceType, T>::value, 51 intrusive_list_node*, 52 const intrusive_list_node*>::type; 53 54 public: iterator_impl()55 iterator_impl() : my_pos(nullptr) {} 56 iterator_impl(pointer_type pos)57 iterator_impl( pointer_type pos ) : my_pos(pos) {} 58 59 iterator_impl& operator++() { 60 my_pos = my_pos->my_next_node; 61 return *this; 62 } 63 64 iterator_impl operator++( int ) { 65 iterator_impl it(*this); 66 ++*this; 67 return it; 68 } 69 70 iterator_impl& operator--() { 71 my_pos = my_pos->my_prev_node; 72 return *this; 73 } 74 75 iterator_impl operator--( int ) { 76 iterator_impl it(*this); 77 --*this; 78 return it; 79 } 80 81 bool operator==( const iterator_impl& rhs ) const { 82 return my_pos == rhs.my_pos; 83 } 84 85 bool operator!=( const iterator_impl& rhs ) const { 86 return my_pos != rhs.my_pos; 87 } 88 89 DereferenceType& operator*() const { 90 return intrusive_list_base::item(my_pos); 91 } 92 93 DereferenceType* operator->() const { 94 return &intrusive_list_base::item(my_pos); 95 } 96 private: 97 // Node the iterator points to at the moment 98 pointer_type my_pos; 99 }; // class iterator_impl 100 assert_ok()101 void assert_ok () const { 102 __TBB_ASSERT( (my_head.my_prev_node == &my_head && !my_size) || 103 (my_head.my_next_node != &my_head && my_size >0), "intrusive_list_base corrupted" ); 104 #if TBB_USE_ASSERT >= 2 105 std::size_t i = 0; 106 for ( intrusive_list_node *n = my_head.my_next_node; n != &my_head; n = n->my_next_node ) 107 ++i; 108 __TBB_ASSERT( my_size == i, "Wrong size" ); 109 #endif /* TBB_USE_ASSERT >= 2 */ 110 } 111 112 public: 113 using iterator = iterator_impl<T>; 114 using const_iterator = iterator_impl<const T>; 115 intrusive_list_base()116 intrusive_list_base () : my_size(0) { 117 my_head.my_prev_node = &my_head; 118 my_head.my_next_node = &my_head; 119 } 120 empty()121 bool empty () const { return my_head.my_next_node == &my_head; } 122 size()123 std::size_t size () const { return my_size; } 124 begin()125 iterator begin () { return iterator(my_head.my_next_node); } 126 end()127 iterator end () { return iterator(&my_head); } 128 begin()129 const_iterator begin () const { return const_iterator(my_head.my_next_node); } 130 end()131 const_iterator end () const { return const_iterator(&my_head); } 132 push_front(T & val)133 void push_front ( T& val ) { 134 __TBB_ASSERT( node(val).my_prev_node == &node(val) && node(val).my_next_node == &node(val), 135 "Object with intrusive list node can be part of only one intrusive list simultaneously" ); 136 // An object can be part of only one intrusive list at the given moment via the given node member 137 node(val).my_prev_node = &my_head; 138 node(val).my_next_node = my_head.my_next_node; 139 my_head.my_next_node->my_prev_node = &node(val); 140 my_head.my_next_node = &node(val); 141 ++my_size; 142 assert_ok(); 143 } 144 remove(T & val)145 void remove( T& val ) { 146 __TBB_ASSERT( node(val).my_prev_node != &node(val) && node(val).my_next_node != &node(val), "Element to remove is not in the list" ); 147 __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" ); 148 --my_size; 149 node(val).my_next_node->my_prev_node = node(val).my_prev_node; 150 node(val).my_prev_node->my_next_node = node(val).my_next_node; 151 #if TBB_USE_ASSERT 152 node(val).my_prev_node = node(val).my_next_node = &node(val); 153 #endif 154 assert_ok(); 155 } 156 erase(iterator it)157 iterator erase ( iterator it ) { 158 T& val = *it; 159 ++it; 160 remove( val ); 161 return it; 162 } 163 164 }; // intrusive_list_base 165 166 #if __TBB_TODO 167 // With standard compliant compilers memptr_intrusive_list could be named simply intrusive_list, 168 // and inheritance based intrusive_list version would become its partial specialization. 169 // Here are the corresponding declarations: 170 171 struct dummy_intrusive_list_item { intrusive_list_node my_node; }; 172 173 template <class T, class U = dummy_intrusive_list_item, intrusive_list_node U::*NodePtr = &dummy_intrusive_list_item::my_node> 174 class intrusive_list : public intrusive_list_base<intrusive_list<T, U, NodePtr>, T>; 175 176 template <class T> 177 class intrusive_list<T, dummy_intrusive_list_item, &dummy_intrusive_list_item::my_node> 178 : public intrusive_list_base<intrusive_list<T>, T>; 179 180 #endif /* __TBB_TODO */ 181 182 //! Double linked list of items of type T containing a member of type intrusive_list_node. 183 /** NodePtr is a member pointer to the node data field. Class U is either T or 184 a base class of T containing the node member. Default values exist for the sake 185 of a partial specialization working with inheritance case. 186 187 The list does not have ownership of its items. Its purpose is to avoid dynamic 188 memory allocation when forming lists of existing objects. 189 190 The class is not thread safe. **/ 191 template <class T, class U, intrusive_list_node U::*NodePtr> 192 class memptr_intrusive_list : public intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T> 193 { 194 friend class intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>; 195 node(T & val)196 static intrusive_list_node& node ( T& val ) { return val.*NodePtr; } 197 item(intrusive_list_node * node)198 static T& item ( intrusive_list_node* node ) { 199 // Cannot use __TBB_offsetof (and consequently __TBB_get_object_ref) macro 200 // with *NodePtr argument because gcc refuses to interpret pasted "->" and "*" 201 // as member pointer dereferencing operator, and explicit usage of ## in 202 // __TBB_offsetof implementation breaks operations with normal member names. 203 return *reinterpret_cast<T*>((char*)node - ((ptrdiff_t)&(reinterpret_cast<T*>(0x1000)->*NodePtr) - 0x1000)); 204 } 205 item(const intrusive_list_node * node)206 static const T& item( const intrusive_list_node* node ) { 207 return item(const_cast<intrusive_list_node*>(node)); 208 } 209 210 }; // intrusive_list<T, U, NodePtr> 211 212 //! Double linked list of items of type T that is derived from intrusive_list_node class. 213 /** The list does not have ownership of its items. Its purpose is to avoid dynamic 214 memory allocation when forming lists of existing objects. 215 216 The class is not thread safe. **/ 217 template <class T> 218 class intrusive_list : public intrusive_list_base<intrusive_list<T>, T> 219 { 220 friend class intrusive_list_base<intrusive_list<T>, T>; 221 node(T & val)222 static intrusive_list_node& node ( T& val ) { return val; } 223 item(intrusive_list_node * node)224 static T& item ( intrusive_list_node* node ) { return *static_cast<T*>(node); } 225 item(const intrusive_list_node * node)226 static const T& item( const intrusive_list_node* node ) { return *static_cast<const T*>(node); } 227 }; // intrusive_list<T> 228 229 } // namespace r1 230 } // namespace detail 231 } // namespace tbb 232 233 #endif /* _TBB_intrusive_list_H */ 234