Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
_flow_graph_item_buffer_impl.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__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::interfaceX (included in _flow_graph_node_impl.h)
31 
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 
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;
48  protected:
49  typedef size_t size_type;
51  typedef typename A::template rebind<buffer_item_type>::other allocator_type;
52 
55  static const size_type initial_buffer_size = 4;
58 
59  bool buffer_empty() const { return my_head == my_tail; }
60 
64  return my_array[i & (my_array_size - 1) ];
65  }
66 
67  const buffer_item_type &item(size_type i) const {
70  return my_array[i & (my_array_size-1)];
71  }
72 
73  bool my_item_valid(size_type i) const { return (i < my_tail) && (i >= my_head) && (item(i).second != no_item); }
74  bool my_item_reserved(size_type i) const { return item(i).second == reserved_item; }
75 
76  // object management in buffer
77  const item_type &get_my_item(size_t i) const {
78  __TBB_ASSERT(my_item_valid(i),"attempt to get invalid item");
79  item_type *itm = (tbb::internal::punned_cast<item_type *>(&(item(i).first)));
80  return *(const item_type *)itm;
81  }
82 
83  // may be called with an empty slot or a slot that has already been constructed into.
84  void set_my_item(size_t i, const item_type &o) {
85  if(item(i).second != no_item) {
86  destroy_item(i);
87  }
88  new(&(item(i).first)) item_type(o);
89  item(i).second = has_item;
90  }
91 
92  // destructively-fetch an object from the buffer
93  void fetch_item(size_t i, item_type &o) {
94  __TBB_ASSERT(my_item_valid(i), "Trying to fetch an empty slot");
95  o = get_my_item(i); // could have std::move assign semantics
96  destroy_item(i);
97  }
98 
99  // move an existing item from one slot to another. The moved-to slot must be unoccupied,
100  // the moved-from slot must exist and not be reserved. The after, from will be empty,
101  // to will be occupied but not reserved
102  void move_item(size_t to, size_t from) {
103  __TBB_ASSERT(!my_item_valid(to), "Trying to move to a non-empty slot");
104  __TBB_ASSERT(my_item_valid(from), "Trying to move from an empty slot");
105  set_my_item(to, get_my_item(from)); // could have std::move semantics
106  destroy_item(from);
107 
108  }
109 
110  // put an item in an empty slot. Return true if successful, else false
111  bool place_item(size_t here, const item_type &me) {
112 #if !TBB_DEPRECATED_SEQUENCER_DUPLICATES
113  if(my_item_valid(here)) return false;
114 #endif
115  set_my_item(here, me);
116  return true;
117  }
118 
119  // could be implemented with std::move semantics
120  void swap_items(size_t i, size_t j) {
121  __TBB_ASSERT(my_item_valid(i) && my_item_valid(j), "attempt to swap invalid item(s)");
122  item_type temp = get_my_item(i);
123  set_my_item(i, get_my_item(j));
124  set_my_item(j, temp);
125  }
126 
128  __TBB_ASSERT(my_item_valid(i), "destruction of invalid item");
129  (tbb::internal::punned_cast<item_type *>(&(item(i).first)))->~item_type();
130  item(i).second = no_item;
131  }
132 
133  // returns the front element
134  const item_type& front() const
135  {
136  __TBB_ASSERT(my_item_valid(my_head), "attempt to fetch head non-item");
137  return get_my_item(my_head);
138  }
139 
140  // returns the back element
141  const item_type& back() const
142  {
143  __TBB_ASSERT(my_item_valid(my_tail - 1), "attempt to fetch head non-item");
144  return get_my_item(my_tail - 1);
145  }
146 
147  // following methods are for reservation of the front of a bufffer.
148  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; }
149  void release_item(size_type i) { __TBB_ASSERT(my_item_reserved(i), "item is not reserved"); item(i).second = has_item; }
150 
153 
154  // we have to be able to test against a new tail value without changing my_tail
155  // grow_array doesn't work if we change my_tail when the old array is too small
156  size_type size(size_t new_tail = 0) { return (new_tail ? new_tail : my_tail) - my_head; }
158  // sequencer_node does not use this method, so we don't
159  // need a version that passes in the new_tail value.
160  bool buffer_full() { return size() >= capacity(); }
161 
163  void grow_my_array( size_t minimum_size ) {
164  // test that we haven't made the structure inconsistent.
165  __TBB_ASSERT(capacity() >= my_tail - my_head, "total items exceed capacity");
167  while( new_size<minimum_size )
168  new_size*=2;
169 
170  buffer_item_type* new_array = allocator_type().allocate(new_size);
171 
172  // initialize validity to "no"
173  for( size_type i=0; i<new_size; ++i ) { new_array[i].second = no_item; }
174 
175  for( size_type i=my_head; i<my_tail; ++i) {
176  if(my_item_valid(i)) { // sequencer_node may have empty slots
177  // placement-new copy-construct; could be std::move
178  char *new_space = (char *)&(new_array[i&(new_size-1)].first);
179  (void)new(new_space) item_type(get_my_item(i));
180  new_array[i&(new_size-1)].second = item(i).second;
181  }
182  }
183 
184  clean_up_buffer(/*reset_pointers*/false);
185 
186  my_array = new_array;
188  }
189 
190  bool push_back(item_type &v) {
191  if(buffer_full()) {
192  grow_my_array(size() + 1);
193  }
194  set_my_item(my_tail, v);
195  ++my_tail;
196  return true;
197  }
198 
199  bool pop_back(item_type &v) {
200  if (!my_item_valid(my_tail-1)) {
201  return false;
202  }
203  v = this->back();
204  destroy_back();
205  return true;
206  }
207 
208  bool pop_front(item_type &v) {
209  if(!my_item_valid(my_head)) {
210  return false;
211  }
212  v = this->front();
213  destroy_front();
214  return true;
215  }
216 
217  // This is used both for reset and for grow_my_array. In the case of grow_my_array
218  // we want to retain the values of the head and tail.
219  void clean_up_buffer(bool reset_pointers) {
220  if (my_array) {
221  for( size_type i=my_head; i<my_tail; ++i ) {
222  if(my_item_valid(i))
223  destroy_item(i);
224  }
225  allocator_type().deallocate(my_array,my_array_size);
226  }
227  my_array = NULL;
228  if(reset_pointers) {
229  my_head = my_tail = my_array_size = 0;
230  }
231  }
232 
233  public:
236  my_head(0), my_tail(0) {
238  }
239 
241  clean_up_buffer(/*reset_pointers*/true);
242  }
243 
244  void reset() { clean_up_buffer(/*reset_pointers*/true); grow_my_array(initial_buffer_size); }
245 
246  };
247 
249  //* complete operation with pop_front(); use consume_front().
250  //* No synchronization built-in.
251  template<typename T, typename A=cache_aligned_allocator<T> >
252  class reservable_item_buffer : public item_buffer<T, A> {
253  protected:
256 
257  public:
260  protected:
261 
262  bool reserve_front(T &v) {
263  if(my_reserved || !my_item_valid(this->my_head)) return false;
264  my_reserved = true;
265  // reserving the head
266  v = this->front();
267  this->reserve_item(this->my_head);
268  return true;
269  }
270 
271  void consume_front() {
272  __TBB_ASSERT(my_reserved, "Attempt to consume a non-reserved item");
273  this->destroy_front();
274  my_reserved = false;
275  }
276 
277  void release_front() {
278  __TBB_ASSERT(my_reserved, "Attempt to release a non-reserved item");
279  this->release_item(this->my_head);
280  my_reserved = false;
281  }
282 
284  };
285 
286 } // namespace internal
287 
288 #endif // __TBB__flow_graph_item_buffer_impl_H
void set_my_item(size_t i, const item_type &o)
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
void swap_items(size_t i, size_t j)
auto first(Container &c) -> decltype(begin(c))
bool my_item_valid(size_type i) const
const buffer_item_type & item(size_type i) const
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 new_size
bool place_item(size_t here, const item_type &me)
A::template rebind< buffer_item_type >::other allocator_type
void clean_up_buffer(bool reset_pointers)
void move_item(size_t to, size_t from)
size_type size(size_t new_tail=0)
aligned_pair< item_type, buffer_item_state >::type buffer_item_type
const item_type & get_my_item(size_t i) const
const item_type & back() const
const item_type & front() const
void grow_my_array(size_t minimum_size)
Grows the internal array.
bool my_item_reserved(size_type i) const
static const size_type initial_buffer_size
item_buffer with reservable front-end. NOTE: if reserving, do not
type mimicking std::pair but with trailing fill to ensure each element of an array
void fetch_item(size_t i, item_type &o)
buffer_item_type & item(size_type i)

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.