_flow_graph_item_buffer_impl.h
Go to the documentation of this file.
/*
Copyright (c) 2005-2020 Intel Corporation
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
#ifndef __TBB__flow_graph_item_buffer_impl_H
#define __TBB__flow_graph_item_buffer_impl_H
#ifndef __TBB_flow_graph_H
#error Do not #include this internal file directly; use public TBB headers instead.
#endif
#include "tbb/internal/_flow_graph_types_impl.h" // for aligned_pair
// in namespace tbb::flow::interfaceX (included in _flow_graph_node_impl.h)
//* tests for empty and so forth. No mutual exclusion is built in.
//* objects are constructed into and explicitly-destroyed. get_my_item gives
// a read-only reference to the item in the buffer. set_my_item may be called
// with either an empty or occupied slot.
using internal::aligned_pair;
using internal::alignment_of;
namespace internal {
template <typename T, typename A=cache_aligned_allocator<T> >
class item_buffer {
public:
typedef T item_type;
enum buffer_item_state { no_item=0, has_item=1, reserved_item=2 };
protected:
typedef size_t size_type;
typedef typename aligned_pair<item_type, buffer_item_state>::type buffer_item_type;
typedef typename tbb::internal::allocator_rebind<A, buffer_item_type>::type allocator_type;
buffer_item_type *my_array;
size_type my_array_size;
static const size_type initial_buffer_size = 4;
size_type my_head;
size_type my_tail;
bool buffer_empty() const { return my_head == my_tail; }
buffer_item_type &item(size_type i) {
__TBB_ASSERT(!(size_type(&(my_array[i&(my_array_size-1)].second))%alignment_of<buffer_item_state>::value),NULL);
__TBB_ASSERT(!(size_type(&(my_array[i&(my_array_size-1)].first))%alignment_of<item_type>::value), NULL);
return my_array[i & (my_array_size - 1) ];
}
const buffer_item_type &item(size_type i) const {
__TBB_ASSERT(!(size_type(&(my_array[i&(my_array_size-1)].second))%alignment_of<buffer_item_state>::value), NULL);
__TBB_ASSERT(!(size_type(&(my_array[i&(my_array_size-1)].first))%alignment_of<item_type>::value), NULL);
return my_array[i & (my_array_size-1)];
}
bool my_item_valid(size_type i) const { return (i < my_tail) && (i >= my_head) && (item(i).second != no_item); }
bool my_item_reserved(size_type i) const { return item(i).second == reserved_item; }
// object management in buffer
const item_type &get_my_item(size_t i) const {
__TBB_ASSERT(my_item_valid(i),"attempt to get invalid item");
item_type *itm = (tbb::internal::punned_cast<item_type *>(&(item(i).first)));
return *(const item_type *)itm;
}
// may be called with an empty slot or a slot that has already been constructed into.
void set_my_item(size_t i, const item_type &o) {
if(item(i).second != no_item) {
destroy_item(i);
}
new(&(item(i).first)) item_type(o);
item(i).second = has_item;
}
// destructively-fetch an object from the buffer
void fetch_item(size_t i, item_type &o) {
__TBB_ASSERT(my_item_valid(i), "Trying to fetch an empty slot");
o = get_my_item(i); // could have std::move assign semantics
destroy_item(i);
}
// move an existing item from one slot to another. The moved-to slot must be unoccupied,
// the moved-from slot must exist and not be reserved. The after, from will be empty,
// to will be occupied but not reserved
void move_item(size_t to, size_t from) {
__TBB_ASSERT(!my_item_valid(to), "Trying to move to a non-empty slot");
__TBB_ASSERT(my_item_valid(from), "Trying to move from an empty slot");
set_my_item(to, get_my_item(from)); // could have std::move semantics
destroy_item(from);
}
// put an item in an empty slot. Return true if successful, else false
bool place_item(size_t here, const item_type &me) {
#if !TBB_DEPRECATED_SEQUENCER_DUPLICATES
if(my_item_valid(here)) return false;
#endif
set_my_item(here, me);
return true;
}
// could be implemented with std::move semantics
void swap_items(size_t i, size_t j) {
__TBB_ASSERT(my_item_valid(i) && my_item_valid(j), "attempt to swap invalid item(s)");
item_type temp = get_my_item(i);
set_my_item(i, get_my_item(j));
set_my_item(j, temp);
}
void destroy_item(size_type i) {
__TBB_ASSERT(my_item_valid(i), "destruction of invalid item");
(tbb::internal::punned_cast<item_type *>(&(item(i).first)))->~item_type();
item(i).second = no_item;
}
// returns the front element
const item_type& front() const
{
__TBB_ASSERT(my_item_valid(my_head), "attempt to fetch head non-item");
return get_my_item(my_head);
}
// returns the back element
const item_type& back() const
{
__TBB_ASSERT(my_item_valid(my_tail - 1), "attempt to fetch head non-item");
return get_my_item(my_tail - 1);
}
// following methods are for reservation of the front of a buffer.
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; }
void release_item(size_type i) { __TBB_ASSERT(my_item_reserved(i), "item is not reserved"); item(i).second = has_item; }
void destroy_front() { destroy_item(my_head); ++my_head; }
void destroy_back() { destroy_item(my_tail-1); --my_tail; }
// we have to be able to test against a new tail value without changing my_tail
// grow_array doesn't work if we change my_tail when the old array is too small
size_type size(size_t new_tail = 0) { return (new_tail ? new_tail : my_tail) - my_head; }
size_type capacity() { return my_array_size; }
// sequencer_node does not use this method, so we don't
// need a version that passes in the new_tail value.
bool buffer_full() { return size() >= capacity(); }
void grow_my_array( size_t minimum_size ) {
// test that we haven't made the structure inconsistent.
__TBB_ASSERT(capacity() >= my_tail - my_head, "total items exceed capacity");
size_type new_size = my_array_size ? 2*my_array_size : initial_buffer_size;
while( new_size<minimum_size )
new_size*=2;
buffer_item_type* new_array = allocator_type().allocate(new_size);
// initialize validity to "no"
for( size_type i=0; i<new_size; ++i ) { new_array[i].second = no_item; }
for( size_type i=my_head; i<my_tail; ++i) {
if(my_item_valid(i)) { // sequencer_node may have empty slots
// placement-new copy-construct; could be std::move
char *new_space = (char *)&(new_array[i&(new_size-1)].first);
(void)new(new_space) item_type(get_my_item(i));
new_array[i&(new_size-1)].second = item(i).second;
}
}
clean_up_buffer(/*reset_pointers*/false);
my_array = new_array;
my_array_size = new_size;
}
bool push_back(item_type &v) {
if(buffer_full()) {
grow_my_array(size() + 1);
}
set_my_item(my_tail, v);
++my_tail;
return true;
}
bool pop_back(item_type &v) {
if (!my_item_valid(my_tail-1)) {
return false;
}
v = this->back();
destroy_back();
return true;
}
bool pop_front(item_type &v) {
if(!my_item_valid(my_head)) {
return false;
}
v = this->front();
destroy_front();
return true;
}
// This is used both for reset and for grow_my_array. In the case of grow_my_array
// we want to retain the values of the head and tail.
void clean_up_buffer(bool reset_pointers) {
if (my_array) {
for( size_type i=my_head; i<my_tail; ++i ) {
if(my_item_valid(i))
destroy_item(i);
}
allocator_type().deallocate(my_array,my_array_size);
}
my_array = NULL;
if(reset_pointers) {
my_head = my_tail = my_array_size = 0;
}
}
public:
item_buffer( ) : my_array(NULL), my_array_size(0),
my_head(0), my_tail(0) {
grow_my_array(initial_buffer_size);
}
~item_buffer() {
clean_up_buffer(/*reset_pointers*/true);
}
void reset() { clean_up_buffer(/*reset_pointers*/true); grow_my_array(initial_buffer_size); }
};
//* complete operation with pop_front(); use consume_front().
//* No synchronization built-in.
template<typename T, typename A=cache_aligned_allocator<T> >
class reservable_item_buffer : public item_buffer<T, A> {
protected:
using item_buffer<T, A>::my_item_valid;
using item_buffer<T, A>::my_head;
public:
reservable_item_buffer() : item_buffer<T, A>(), my_reserved(false) {}
void reset() {my_reserved = false; item_buffer<T,A>::reset(); }
protected:
bool reserve_front(T &v) {
if(my_reserved || !my_item_valid(this->my_head)) return false;
my_reserved = true;
// reserving the head
v = this->front();
this->reserve_item(this->my_head);
return true;
}
void consume_front() {
__TBB_ASSERT(my_reserved, "Attempt to consume a non-reserved item");
this->destroy_front();
my_reserved = false;
}
void release_front() {
__TBB_ASSERT(my_reserved, "Attempt to release a non-reserved item");
this->release_item(this->my_head);
my_reserved = false;
}
bool my_reserved;
};
} // namespace internal
#endif // __TBB__flow_graph_item_buffer_impl_H
_flow_graph_types_impl.h
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
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
void
void
Definition: ittnotify_static.h:91
tbb::internal::first
auto first(Container &c) -> decltype(begin(c))
Definition: _range_iterator.h:34
internal
Definition: _flow_graph_async_msg_impl.h:24
tbb::internal::allocator_rebind::type
allocator_traits< Alloc >::template rebind_alloc< T >::other type
Definition: _allocator_traits.h:149
internal::item_buffer
Definition: _flow_graph_item_buffer_impl.h:40
internal::item_buffer::front
const item_type & front() const
Definition: _flow_graph_item_buffer_impl.h:129
internal::item_buffer::item_type
T item_type
Definition: _flow_graph_item_buffer_impl.h:42
internal::item_buffer::capacity
size_type capacity()
Definition: _flow_graph_item_buffer_impl.h:152
internal::item_buffer::destroy_item
void destroy_item(size_type i)
Definition: _flow_graph_item_buffer_impl.h:122
internal::item_buffer::pop_back
bool pop_back(item_type &v)
Definition: _flow_graph_item_buffer_impl.h:194
internal::item_buffer::move_item
void move_item(size_t to, size_t from)
Definition: _flow_graph_item_buffer_impl.h:97
internal::item_buffer::buffer_full
bool buffer_full()
Definition: _flow_graph_item_buffer_impl.h:155
internal::item_buffer::get_my_item
const item_type & get_my_item(size_t i) const
Definition: _flow_graph_item_buffer_impl.h:72
internal::item_buffer::clean_up_buffer
void clean_up_buffer(bool reset_pointers)
Definition: _flow_graph_item_buffer_impl.h:214
internal::item_buffer::my_array
buffer_item_type * my_array
Definition: _flow_graph_item_buffer_impl.h:48
internal::item_buffer::item_buffer
item_buffer()
Constructor.
Definition: _flow_graph_item_buffer_impl.h:230
internal::item_buffer::my_item_reserved
bool my_item_reserved(size_type i) const
Definition: _flow_graph_item_buffer_impl.h:69
internal::item_buffer::initial_buffer_size
static const size_type initial_buffer_size
Definition: _flow_graph_item_buffer_impl.h:50
internal::item_buffer::item
buffer_item_type & item(size_type i)
Definition: _flow_graph_item_buffer_impl.h:56
internal::item_buffer::my_tail
size_type my_tail
Definition: _flow_graph_item_buffer_impl.h:52
internal::item_buffer::back
const item_type & back() const
Definition: _flow_graph_item_buffer_impl.h:136
internal::item_buffer::place_item
bool place_item(size_t here, const item_type &me)
Definition: _flow_graph_item_buffer_impl.h:106
internal::item_buffer::~item_buffer
~item_buffer()
Definition: _flow_graph_item_buffer_impl.h:235
internal::item_buffer::item
const buffer_item_type & item(size_type i) const
Definition: _flow_graph_item_buffer_impl.h:62
internal::item_buffer::buffer_empty
bool buffer_empty() const
Definition: _flow_graph_item_buffer_impl.h:54
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:158
internal::item_buffer::size_type
size_t size_type
Definition: _flow_graph_item_buffer_impl.h:45
internal::item_buffer::size
size_type size(size_t new_tail=0)
Definition: _flow_graph_item_buffer_impl.h:151
internal::item_buffer::fetch_item
void fetch_item(size_t i, item_type &o)
Definition: _flow_graph_item_buffer_impl.h:88
internal::item_buffer::reset
void reset()
Definition: _flow_graph_item_buffer_impl.h:239
internal::item_buffer::my_item_valid
bool my_item_valid(size_type i) const
Definition: _flow_graph_item_buffer_impl.h:68
internal::item_buffer::my_head
size_type my_head
Definition: _flow_graph_item_buffer_impl.h:51
internal::item_buffer::set_my_item
void set_my_item(size_t i, const item_type &o)
Definition: _flow_graph_item_buffer_impl.h:79
internal::item_buffer::reserve_item
void reserve_item(size_type i)
Definition: _flow_graph_item_buffer_impl.h:143
internal::item_buffer::buffer_item_state
buffer_item_state
Definition: _flow_graph_item_buffer_impl.h:43
internal::item_buffer::reserved_item
@ reserved_item
Definition: _flow_graph_item_buffer_impl.h:43
internal::item_buffer::no_item
@ no_item
Definition: _flow_graph_item_buffer_impl.h:43
internal::item_buffer::has_item
@ has_item
Definition: _flow_graph_item_buffer_impl.h:43
internal::item_buffer::my_array_size
size_type my_array_size
Definition: _flow_graph_item_buffer_impl.h:49
internal::item_buffer::release_item
void release_item(size_type i)
Definition: _flow_graph_item_buffer_impl.h:144
internal::item_buffer::pop_front
bool pop_front(item_type &v)
Definition: _flow_graph_item_buffer_impl.h:203
internal::item_buffer::destroy_back
void destroy_back()
Definition: _flow_graph_item_buffer_impl.h:147
internal::item_buffer::allocator_type
tbb::internal::allocator_rebind< A, buffer_item_type >::type allocator_type
Definition: _flow_graph_item_buffer_impl.h:47
internal::item_buffer::swap_items
void swap_items(size_t i, size_t j)
Definition: _flow_graph_item_buffer_impl.h:115
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::destroy_front
void destroy_front()
Definition: _flow_graph_item_buffer_impl.h:146
internal::item_buffer::push_back
bool push_back(item_type &v)
Definition: _flow_graph_item_buffer_impl.h:185
internal::reservable_item_buffer
item_buffer with reservable front-end. NOTE: if reserving, do not
Definition: _flow_graph_item_buffer_impl.h:247
internal::reservable_item_buffer::reset
void reset()
Definition: _flow_graph_item_buffer_impl.h:254
internal::reservable_item_buffer::release_front
void release_front()
Definition: _flow_graph_item_buffer_impl.h:272
internal::reservable_item_buffer::reserve_front
bool reserve_front(T &v)
Definition: _flow_graph_item_buffer_impl.h:257
internal::reservable_item_buffer::my_reserved
bool my_reserved
Definition: _flow_graph_item_buffer_impl.h:278
internal::reservable_item_buffer::reservable_item_buffer
reservable_item_buffer()
Definition: _flow_graph_item_buffer_impl.h:253
internal::reservable_item_buffer::consume_front
void consume_front()
Definition: _flow_graph_item_buffer_impl.h:266
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
internal::type_plus_align::first
char first[sizeof(T1)]
Definition: _flow_graph_types_impl.h:392
internal::type_plus_align::second
T2 second
Definition: _flow_graph_types_impl.h:393
internal::alignment_of
Definition: _flow_graph_types_impl.h:403
internal::aligned_pair
Definition: _flow_graph_types_impl.h:412

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.