1 /* 2 Copyright 2005-2014 Intel Corporation. All Rights Reserved. 3 4 This file is part of Threading Building Blocks. Threading Building Blocks is free software; 5 you can redistribute it and/or modify it under the terms of the GNU General Public License 6 version 2 as published by the Free Software Foundation. Threading Building Blocks is 7 distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the 8 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 9 See the GNU General Public License for more details. You should have received a copy of 10 the GNU General Public License along with Threading Building Blocks; if not, write to the 11 Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 12 13 As a special exception, you may use this file as part of a free software library without 14 restriction. Specifically, if other files instantiate templates or use macros or inline 15 functions from this file, or you compile this file and link it with other files to produce 16 an executable, this file does not by itself cause the resulting executable to be covered 17 by the GNU General Public License. This exception does not however invalidate any other 18 reasons why the executable file might be covered by the GNU General Public License. 19 */ 20 21 #ifndef __TBB__flow_graph_item_buffer_impl_H 22 #define __TBB__flow_graph_item_buffer_impl_H 23 24 #ifndef __TBB_flow_graph_H 25 #error Do not #include this internal file directly; use public TBB headers instead. 26 #endif 27 28 #include "tbb/internal/_flow_graph_types_impl.h" // for aligned_pair 29 30 // in namespace tbb::flow::interface7 (included in _flow_graph_node_impl.h) 31 32 //! Expandable buffer of items. The possible operations are push, pop, 33 //* tests for empty and so forth. No mutual exclusion is built in. 34 //* objects are constructed into and explicitly-destroyed. get_my_item gives 35 // a read-only reference to the item in the buffer. set_my_item may be called 36 // with either an empty or occupied slot. 37 38 using internal::aligned_pair; 39 using internal::alignment_of; 40 41 namespace internal { 42 43 template <typename T, typename A=cache_aligned_allocator<T> > 44 class item_buffer { 45 public: 46 typedef T item_type; 47 enum buffer_item_state { no_item=0, has_item=1, reserved_item=2 }; 48 protected: 49 typedef size_t size_type; 50 typedef typename aligned_pair<item_type, buffer_item_state>::type buffer_item_type; 51 typedef typename A::template rebind<buffer_item_type>::other allocator_type; 52 53 buffer_item_type *my_array; 54 size_type my_array_size; 55 static const size_type initial_buffer_size = 4; 56 size_type my_head; 57 size_type my_tail; 58 buffer_empty()59 bool buffer_empty() { return my_head == my_tail; } 60 item(size_type i)61 buffer_item_type &item(size_type i) { 62 __TBB_ASSERT(!(size_type(&(my_array[i&(my_array_size-1)].second))%alignment_of<buffer_item_state>::value),NULL); 63 __TBB_ASSERT(!(size_type(&(my_array[i&(my_array_size-1)].first))%alignment_of<item_type>::value), NULL); 64 return my_array[i & (my_array_size - 1) ]; 65 } 66 my_item_valid(size_type i)67 bool my_item_valid(size_type i) { return item(i).second != no_item; } my_item_reserved(size_type i)68 bool my_item_reserved(size_type i) { return item(i).second == reserved_item; } 69 70 // object management in buffer get_my_item(size_t i)71 const item_type &get_my_item(size_t i) { 72 __TBB_ASSERT(my_item_valid(i),"attempt to get invalid item"); 73 item_type *itm = (tbb::internal::punned_cast<item_type *>(&(item(i).first))); 74 return *(const item_type *)itm; 75 } 76 77 // may be called with an empty slot or a slot that has already been constructed into. set_my_item(size_t i,const item_type & o)78 void set_my_item(size_t i, const item_type &o) { 79 if(item(i).second != no_item) { 80 destroy_item(i); 81 } 82 new(&(item(i).first)) item_type(o); 83 item(i).second = has_item; 84 } 85 86 // destructively-fetch an object from the buffer fetch_item(size_t i,item_type & o)87 void fetch_item(size_t i, item_type &o) { 88 __TBB_ASSERT(my_item_valid(i), "Trying to fetch an empty slot"); 89 o = get_my_item(i); // could have std::move assign semantics 90 destroy_item(i); 91 } 92 93 // move an existing item from one slot to another. The moved-to slot must be unoccupied, 94 // the moved-from slot must exist and not be reserved. The after, from will be empty, 95 // to will be occupied but not reserved move_item(size_t to,size_t from)96 void move_item(size_t to, size_t from) { 97 __TBB_ASSERT(!my_item_valid(to), "Trying to move to a non-empty slot"); 98 __TBB_ASSERT(my_item_valid(from), "Trying to move from an empty slot"); 99 set_my_item(to, get_my_item(from)); // could have std::move semantics 100 destroy_item(from); 101 102 } 103 104 // put an item in an empty slot. Return true if successful, else false place_item(size_t here,const item_type & me)105 bool place_item(size_t here, const item_type &me) { 106 #if !TBB_DEPRECATED_SEQUENCER_DUPLICATES 107 if(my_item_valid(here)) return false; 108 #endif 109 set_my_item(here, me); 110 return true; 111 } 112 113 // could be implemented with std::move semantics swap_items(size_t i,size_t j)114 void swap_items(size_t i, size_t j) { 115 __TBB_ASSERT(my_item_valid(i) && my_item_valid(j), "attempt to swap invalid item(s)"); 116 item_type temp = get_my_item(i); 117 set_my_item(i, get_my_item(j)); 118 set_my_item(j, temp); 119 } 120 destroy_item(size_type i)121 void destroy_item(size_type i) { 122 __TBB_ASSERT(my_item_valid(i), "destruction of invalid item"); 123 (tbb::internal::punned_cast<item_type *>(&(item(i).first)))->~item_type(); 124 item(i).second = no_item; 125 } 126 127 // returns a copy of the front copy_front(item_type & v)128 void copy_front(item_type &v) { 129 __TBB_ASSERT(my_item_valid(my_head), "attempt to fetch head non-item"); 130 v = get_my_item(my_head); 131 } 132 // returns a copy of the back copy_back(item_type & v)133 void copy_back(item_type &v) { 134 __TBB_ASSERT(my_item_valid(my_tail-1), "attempt to fetch head non-item"); 135 v = get_my_item(my_tail-1); 136 } 137 138 // following methods are for reservation of the front of a bufffer. reserve_item(size_type i)139 void reserve_item(size_type i) { __TBB_ASSERT(my_item_valid(i) && !my_item_reserved(i), "item cannot be reserved"); item(i).second = reserved_item; } release_item(size_type i)140 void release_item(size_type i) { __TBB_ASSERT(my_item_reserved(i), "item is not reserved"); item(i).second = has_item; } 141 destroy_front()142 void destroy_front() { destroy_item(my_head); ++my_head; } destroy_back()143 void destroy_back() { destroy_item(my_tail-1); --my_tail; } 144 145 // we have to be able to test against a new tail value without changing my_tail 146 // grow_array doesn't work if we change my_tail when the old array is too small 147 size_type size(size_t new_tail = 0) { return (new_tail ? new_tail : my_tail) - my_head; } capacity()148 size_type capacity() { return my_array_size; } 149 // sequencer_node does not use this method, so we don't 150 // need a version that passes in the new_tail value. buffer_full()151 bool buffer_full() { return size() >= capacity(); } 152 153 //! Grows the internal array. grow_my_array(size_t minimum_size)154 void grow_my_array( size_t minimum_size ) { 155 // test that we haven't made the structure inconsistent. 156 __TBB_ASSERT(capacity() >= my_tail - my_head, "total items exceed capacity"); 157 size_type new_size = my_array_size ? 2*my_array_size : initial_buffer_size; 158 while( new_size<minimum_size ) 159 new_size*=2; 160 161 buffer_item_type* new_array = allocator_type().allocate(new_size); 162 163 // initialize validity to "no" 164 for( size_type i=0; i<new_size; ++i ) { new_array[i].second = no_item; } 165 166 for( size_type i=my_head; i<my_tail; ++i) { 167 if(my_item_valid(i)) { // sequencer_node may have empty slots 168 // placement-new copy-construct; could be std::move 169 char *new_space = (char *)&(new_array[i&(new_size-1)].first); 170 (void)new(new_space) item_type(get_my_item(i)); 171 new_array[i&(new_size-1)].second = item(i).second; 172 } 173 } 174 175 clean_up_buffer(/*reset_pointers*/false); 176 177 my_array = new_array; 178 my_array_size = new_size; 179 } 180 push_back(item_type & v)181 bool push_back(item_type &v) { 182 if(buffer_full()) { 183 grow_my_array(size() + 1); 184 } 185 set_my_item(my_tail, v); 186 ++my_tail; 187 return true; 188 } 189 pop_back(item_type & v)190 bool pop_back(item_type &v) { 191 if (!my_item_valid(my_tail-1)) { 192 return false; 193 } 194 copy_back(v); 195 destroy_back(); 196 return true; 197 } 198 pop_front(item_type & v)199 bool pop_front(item_type &v) { 200 if(!my_item_valid(my_head)) { 201 return false; 202 } 203 copy_front(v); 204 destroy_front(); 205 return true; 206 } 207 208 // This is used both for reset and for grow_my_array. In the case of grow_my_array 209 // we want to retain the values of the head and tail. clean_up_buffer(bool reset_pointers)210 void clean_up_buffer(bool reset_pointers) { 211 if (my_array) { 212 for( size_type i=0; i<my_array_size; ++i ) { 213 if(my_item_valid(i)) 214 destroy_item(i); 215 } 216 allocator_type().deallocate(my_array,my_array_size); 217 } 218 my_array = NULL; 219 if(reset_pointers) { 220 my_head = my_tail = my_array_size = 0; 221 } 222 } 223 224 public: 225 //! Constructor item_buffer()226 item_buffer( ) : my_array(NULL), my_array_size(0), 227 my_head(0), my_tail(0) { 228 grow_my_array(initial_buffer_size); 229 } 230 ~item_buffer()231 ~item_buffer() { 232 clean_up_buffer(/*reset_pointers*/true); 233 } 234 reset()235 void reset() { clean_up_buffer(/*reset_pointers*/true); grow_my_array(initial_buffer_size); } 236 237 }; 238 239 //! item_buffer with reservable front-end. NOTE: if reserving, do not 240 //* complete operation with pop_front(); use consume_front(). 241 //* No synchronization built-in. 242 template<typename T, typename A=cache_aligned_allocator<T> > 243 class reservable_item_buffer : public item_buffer<T, A> { 244 protected: 245 using item_buffer<T, A>::my_item_valid; 246 using item_buffer<T, A>::my_head; 247 248 public: reservable_item_buffer()249 reservable_item_buffer() : item_buffer<T, A>(), my_reserved(false) {} reset()250 void reset() {my_reserved = false; item_buffer<T,A>::reset(); } 251 protected: 252 reserve_front(T & v)253 bool reserve_front(T &v) { 254 if(my_reserved || !my_item_valid(my_head)) return false; 255 my_reserved = true; 256 // reserving the head 257 this->copy_front(v); 258 this->reserve_item(this->my_head); 259 return true; 260 } 261 consume_front()262 void consume_front() { 263 __TBB_ASSERT(my_reserved, "Attempt to consume a non-reserved item"); 264 this->destroy_front(); 265 my_reserved = false; 266 } 267 release_front()268 void release_front() { 269 __TBB_ASSERT(my_reserved, "Attempt to release a non-reserved item"); 270 this->release_item(this->my_head); 271 my_reserved = false; 272 } 273 274 bool my_reserved; 275 }; 276 277 } // namespace internal 278 279 #endif // __TBB__flow_graph_item_buffer_impl_H 280