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

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