_concurrent_queue_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__concurrent_queue_impl_H
#define __TBB__concurrent_queue_impl_H
#ifndef __TBB_concurrent_queue_H
#error Do not #include this internal file directly; use public TBB headers instead.
#endif
#include "../tbb_stddef.h"
#include "../tbb_machine.h"
#include "../atomic.h"
#include "../spin_mutex.h"
#include "../cache_aligned_allocator.h"
#include "../tbb_exception.h"
#include "../tbb_profiling.h"
#include <new>
#include __TBB_STD_SWAP_HEADER
#include <iterator>
namespace tbb {
#if !__TBB_TEMPLATE_FRIENDS_BROKEN
// forward declaration
namespace strict_ppl {
template<typename T, typename A> class concurrent_queue;
}
template<typename T, typename A> class concurrent_bounded_queue;
#endif
namespace strict_ppl {
namespace internal {
using namespace tbb::internal;
typedef size_t ticket;
template<typename T> class micro_queue ;
template<typename T> class micro_queue_pop_finalizer ;
template<typename T> class concurrent_queue_base_v3;
template<typename T> struct concurrent_queue_rep;
struct concurrent_queue_rep_base : no_copy {
template<typename T> friend class micro_queue;
template<typename T> friend class concurrent_queue_base_v3;
protected:
static const size_t phi = 3;
public:
// must be power of 2
static const size_t n_queue = 8;
struct page {
page* next;
uintptr_t mask;
};
atomic<ticket> head_counter;
char pad1[NFS_MaxLineSize-sizeof(atomic<ticket>)];
atomic<ticket> tail_counter;
char pad2[NFS_MaxLineSize-sizeof(atomic<ticket>)];
size_t items_per_page;
size_t item_size;
atomic<size_t> n_invalid_entries;
char pad3[NFS_MaxLineSize-sizeof(size_t)-sizeof(size_t)-sizeof(atomic<size_t>)];
} ;
inline bool is_valid_page(const concurrent_queue_rep_base::page* p) {
return uintptr_t(p)>1;
}
class concurrent_queue_page_allocator
{
template<typename T> friend class micro_queue ;
template<typename T> friend class micro_queue_pop_finalizer ;
protected:
virtual ~concurrent_queue_page_allocator() {}
private:
virtual concurrent_queue_rep_base::page* allocate_page() = 0;
virtual void deallocate_page( concurrent_queue_rep_base::page* p ) = 0;
} ;
#if _MSC_VER && !defined(__INTEL_COMPILER)
// unary minus operator applied to unsigned type, result still unsigned
#pragma warning( push )
#pragma warning( disable: 4146 )
#endif
template<typename T>
class micro_queue : no_copy {
public:
typedef void (*item_constructor_t)(T* location, const void* src);
private:
typedef concurrent_queue_rep_base::page page;
class destroyer: no_copy {
T& my_value;
public:
destroyer( T& value ) : my_value(value) {}
~destroyer() {my_value.~T();}
};
void copy_item( page& dst, size_t dindex, const void* src, item_constructor_t construct_item ) {
construct_item( &get_ref(dst, dindex), src );
}
void copy_item( page& dst, size_t dindex, const page& src, size_t sindex,
item_constructor_t construct_item )
{
T& src_item = get_ref( const_cast<page&>(src), sindex );
construct_item( &get_ref(dst, dindex), static_cast<const void*>(&src_item) );
}
void assign_and_destroy_item( void* dst, page& src, size_t index ) {
T& from = get_ref(src,index);
destroyer d(from);
*static_cast<T*>(dst) = tbb::internal::move( from );
}
void spin_wait_until_my_turn( atomic<ticket>& counter, ticket k, concurrent_queue_rep_base& rb ) const ;
public:
friend class micro_queue_pop_finalizer<T>;
struct padded_page: page {
padded_page();
void operator=( const padded_page& );
T last;
};
static T& get_ref( page& p, size_t index ) {
return (&static_cast<padded_page*>(static_cast<void*>(&p))->last)[index];
}
atomic<page*> head_page;
atomic<ticket> head_counter;
atomic<page*> tail_page;
atomic<ticket> tail_counter;
spin_mutex page_mutex;
void push( const void* item, ticket k, concurrent_queue_base_v3<T>& base,
item_constructor_t construct_item ) ;
bool pop( void* dst, ticket k, concurrent_queue_base_v3<T>& base ) ;
micro_queue& assign( const micro_queue& src, concurrent_queue_base_v3<T>& base,
item_constructor_t construct_item ) ;
page* make_copy( concurrent_queue_base_v3<T>& base, const page* src_page, size_t begin_in_page,
size_t end_in_page, ticket& g_index, item_constructor_t construct_item ) ;
void invalidate_page_and_rethrow( ticket k ) ;
};
template<typename T>
void micro_queue<T>::spin_wait_until_my_turn( atomic<ticket>& counter, ticket k, concurrent_queue_rep_base& rb ) const {
for( atomic_backoff b(true);;b.pause() ) {
ticket c = counter;
if( c==k ) return;
else if( c&1 ) {
++rb.n_invalid_entries;
throw_exception( eid_bad_last_alloc );
}
}
}
template<typename T>
void micro_queue<T>::push( const void* item, ticket k, concurrent_queue_base_v3<T>& base,
item_constructor_t construct_item )
{
k &= -concurrent_queue_rep_base::n_queue;
page* p = NULL;
size_t index = modulo_power_of_two( k/concurrent_queue_rep_base::n_queue, base.my_rep->items_per_page);
if( !index ) {
__TBB_TRY {
concurrent_queue_page_allocator& pa = base;
p = pa.allocate_page();
} __TBB_CATCH (...) {
++base.my_rep->n_invalid_entries;
invalidate_page_and_rethrow( k );
}
p->mask = 0;
p->next = NULL;
}
if( tail_counter != k ) spin_wait_until_my_turn( tail_counter, k, *base.my_rep );
call_itt_notify(acquired, &tail_counter);
if( p ) {
spin_mutex::scoped_lock lock( page_mutex );
page* q = tail_page;
if( is_valid_page(q) )
q->next = p;
else
head_page = p;
tail_page = p;
} else {
p = tail_page;
}
__TBB_TRY {
copy_item( *p, index, item, construct_item );
// If no exception was thrown, mark item as present.
itt_hide_store_word(p->mask, p->mask | uintptr_t(1)<<index);
call_itt_notify(releasing, &tail_counter);
tail_counter += concurrent_queue_rep_base::n_queue;
} __TBB_CATCH (...) {
++base.my_rep->n_invalid_entries;
call_itt_notify(releasing, &tail_counter);
tail_counter += concurrent_queue_rep_base::n_queue;
__TBB_RETHROW();
}
}
template<typename T>
bool micro_queue<T>::pop( void* dst, ticket k, concurrent_queue_base_v3<T>& base ) {
k &= -concurrent_queue_rep_base::n_queue;
if( head_counter!=k ) spin_wait_until_eq( head_counter, k );
call_itt_notify(acquired, &head_counter);
if( tail_counter==k ) spin_wait_while_eq( tail_counter, k );
call_itt_notify(acquired, &tail_counter);
page *p = head_page;
__TBB_ASSERT( p, NULL );
size_t index = modulo_power_of_two( k/concurrent_queue_rep_base::n_queue, base.my_rep->items_per_page );
bool success = false;
{
micro_queue_pop_finalizer<T> finalizer( *this, base, k+concurrent_queue_rep_base::n_queue, index==base.my_rep->items_per_page-1 ? p : NULL );
if( p->mask & uintptr_t(1)<<index ) {
success = true;
assign_and_destroy_item( dst, *p, index );
} else {
--base.my_rep->n_invalid_entries;
}
}
return success;
}
template<typename T>
micro_queue<T>& micro_queue<T>::assign( const micro_queue<T>& src, concurrent_queue_base_v3<T>& base,
item_constructor_t construct_item )
{
head_counter = src.head_counter;
tail_counter = src.tail_counter;
const page* srcp = src.head_page;
if( is_valid_page(srcp) ) {
ticket g_index = head_counter;
__TBB_TRY {
size_t n_items = (tail_counter-head_counter)/concurrent_queue_rep_base::n_queue;
size_t index = modulo_power_of_two( head_counter/concurrent_queue_rep_base::n_queue, base.my_rep->items_per_page );
size_t end_in_first_page = (index+n_items<base.my_rep->items_per_page)?(index+n_items):base.my_rep->items_per_page;
head_page = make_copy( base, srcp, index, end_in_first_page, g_index, construct_item );
page* cur_page = head_page;
if( srcp != src.tail_page ) {
for( srcp = srcp->next; srcp!=src.tail_page; srcp=srcp->next ) {
cur_page->next = make_copy( base, srcp, 0, base.my_rep->items_per_page, g_index, construct_item );
cur_page = cur_page->next;
}
__TBB_ASSERT( srcp==src.tail_page, NULL );
size_t last_index = modulo_power_of_two( tail_counter/concurrent_queue_rep_base::n_queue, base.my_rep->items_per_page );
if( last_index==0 ) last_index = base.my_rep->items_per_page;
cur_page->next = make_copy( base, srcp, 0, last_index, g_index, construct_item );
cur_page = cur_page->next;
}
tail_page = cur_page;
} __TBB_CATCH (...) {
invalidate_page_and_rethrow( g_index );
}
} else {
head_page = tail_page = NULL;
}
return *this;
}
template<typename T>
void micro_queue<T>::invalidate_page_and_rethrow( ticket k ) {
// Append an invalid page at address 1 so that no more pushes are allowed.
page* invalid_page = (page*)uintptr_t(1);
{
spin_mutex::scoped_lock lock( page_mutex );
itt_store_word_with_release(tail_counter, k+concurrent_queue_rep_base::n_queue+1);
page* q = tail_page;
if( is_valid_page(q) )
q->next = invalid_page;
else
head_page = invalid_page;
tail_page = invalid_page;
}
__TBB_RETHROW();
}
template<typename T>
concurrent_queue_rep_base::page* micro_queue<T>::make_copy( concurrent_queue_base_v3<T>& base,
const concurrent_queue_rep_base::page* src_page, size_t begin_in_page, size_t end_in_page,
ticket& g_index, item_constructor_t construct_item )
{
concurrent_queue_page_allocator& pa = base;
page* new_page = pa.allocate_page();
new_page->next = NULL;
new_page->mask = src_page->mask;
for( ; begin_in_page!=end_in_page; ++begin_in_page, ++g_index )
if( new_page->mask & uintptr_t(1)<<begin_in_page )
copy_item( *new_page, begin_in_page, *src_page, begin_in_page, construct_item );
return new_page;
}
template<typename T>
class micro_queue_pop_finalizer: no_copy {
typedef concurrent_queue_rep_base::page page;
ticket my_ticket;
micro_queue<T>& my_queue;
page* my_page;
concurrent_queue_page_allocator& allocator;
public:
micro_queue_pop_finalizer( micro_queue<T>& queue, concurrent_queue_base_v3<T>& b, ticket k, page* p ) :
my_ticket(k), my_queue(queue), my_page(p), allocator(b)
{}
~micro_queue_pop_finalizer() ;
};
template<typename T>
micro_queue_pop_finalizer<T>::~micro_queue_pop_finalizer() {
page* p = my_page;
if( is_valid_page(p) ) {
spin_mutex::scoped_lock lock( my_queue.page_mutex );
page* q = p->next;
my_queue.head_page = q;
if( !is_valid_page(q) ) {
my_queue.tail_page = NULL;
}
}
itt_store_word_with_release(my_queue.head_counter, my_ticket);
if( is_valid_page(p) ) {
allocator.deallocate_page( p );
}
}
#if _MSC_VER && !defined(__INTEL_COMPILER)
#pragma warning( pop )
#endif // warning 4146 is back
template<typename T> class concurrent_queue_iterator_rep ;
template<typename T> class concurrent_queue_iterator_base_v3;
template<typename T>
struct concurrent_queue_rep : public concurrent_queue_rep_base {
micro_queue<T> array[n_queue];
static size_t index( ticket k ) {
return k*phi%n_queue;
}
micro_queue<T>& choose( ticket k ) {
// The formula here approximates LRU in a cache-oblivious way.
return array[index(k)];
}
};
template<typename T>
class concurrent_queue_base_v3: public concurrent_queue_page_allocator {
private:
concurrent_queue_rep<T>* my_rep;
friend struct concurrent_queue_rep<T>;
friend class micro_queue<T>;
friend class concurrent_queue_iterator_rep<T>;
friend class concurrent_queue_iterator_base_v3<T>;
protected:
typedef typename concurrent_queue_rep<T>::page page;
private:
typedef typename micro_queue<T>::padded_page padded_page;
typedef typename micro_queue<T>::item_constructor_t item_constructor_t;
virtual page *allocate_page() __TBB_override {
concurrent_queue_rep<T>& r = *my_rep;
size_t n = sizeof(padded_page) + (r.items_per_page-1)*sizeof(T);
return reinterpret_cast<page*>(allocate_block ( n ));
}
virtual void deallocate_page( concurrent_queue_rep_base::page *p ) __TBB_override {
concurrent_queue_rep<T>& r = *my_rep;
size_t n = sizeof(padded_page) + (r.items_per_page-1)*sizeof(T);
deallocate_block( reinterpret_cast<void*>(p), n );
}
virtual void *allocate_block( size_t n ) = 0;
virtual void deallocate_block( void *p, size_t n ) = 0;
protected:
concurrent_queue_base_v3();
virtual ~concurrent_queue_base_v3() {
#if TBB_USE_ASSERT
size_t nq = my_rep->n_queue;
for( size_t i=0; i<nq; i++ )
__TBB_ASSERT( my_rep->array[i].tail_page==NULL, "pages were not freed properly" );
#endif /* TBB_USE_ASSERT */
cache_aligned_allocator<concurrent_queue_rep<T> >().deallocate(my_rep,1);
}
void internal_push( const void* src, item_constructor_t construct_item ) {
concurrent_queue_rep<T>& r = *my_rep;
ticket k = r.tail_counter++;
r.choose(k).push( src, k, *this, construct_item );
}
bool internal_try_pop( void* dst ) ;
size_t internal_size() const ;
bool internal_empty() const ;
/* note that the name may be misleading, but it remains so due to a historical accident. */
void internal_finish_clear() ;
void internal_throw_exception() const {
throw_exception( eid_bad_alloc );
}
void assign( const concurrent_queue_base_v3& src, item_constructor_t construct_item ) ;
#if __TBB_CPP11_RVALUE_REF_PRESENT
void internal_swap( concurrent_queue_base_v3& src ) {
std::swap( my_rep, src.my_rep );
}
#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
};
template<typename T>
concurrent_queue_base_v3<T>::concurrent_queue_base_v3() {
const size_t item_size = sizeof(T);
my_rep = cache_aligned_allocator<concurrent_queue_rep<T> >().allocate(1);
__TBB_ASSERT( (size_t)my_rep % NFS_GetLineSize()==0, "alignment error" );
__TBB_ASSERT( (size_t)&my_rep->head_counter % NFS_GetLineSize()==0, "alignment error" );
__TBB_ASSERT( (size_t)&my_rep->tail_counter % NFS_GetLineSize()==0, "alignment error" );
__TBB_ASSERT( (size_t)&my_rep->array % NFS_GetLineSize()==0, "alignment error" );
memset(static_cast<void*>(my_rep),0,sizeof(concurrent_queue_rep<T>));
my_rep->item_size = item_size;
my_rep->items_per_page = item_size<= 8 ? 32 :
item_size<= 16 ? 16 :
item_size<= 32 ? 8 :
item_size<= 64 ? 4 :
item_size<=128 ? 2 :
1;
}
template<typename T>
bool concurrent_queue_base_v3<T>::internal_try_pop( void* dst ) {
concurrent_queue_rep<T>& r = *my_rep;
ticket k;
do {
k = r.head_counter;
for(;;) {
if( (ptrdiff_t)(r.tail_counter-k)<=0 ) {
// Queue is empty
return false;
}
// Queue had item with ticket k when we looked. Attempt to get that item.
ticket tk=k;
#if defined(_MSC_VER) && defined(_Wp64)
#pragma warning (push)
#pragma warning (disable: 4267)
#endif
k = r.head_counter.compare_and_swap( tk+1, tk );
#if defined(_MSC_VER) && defined(_Wp64)
#pragma warning (pop)
#endif
if( k==tk )
break;
// Another thread snatched the item, retry.
}
} while( !r.choose( k ).pop( dst, k, *this ) );
return true;
}
template<typename T>
size_t concurrent_queue_base_v3<T>::internal_size() const {
concurrent_queue_rep<T>& r = *my_rep;
__TBB_ASSERT( sizeof(ptrdiff_t)<=sizeof(size_t), NULL );
ticket hc = r.head_counter;
size_t nie = r.n_invalid_entries;
ticket tc = r.tail_counter;
__TBB_ASSERT( hc!=tc || !nie, NULL );
ptrdiff_t sz = tc-hc-nie;
return sz<0 ? 0 : size_t(sz);
}
template<typename T>
bool concurrent_queue_base_v3<T>::internal_empty() const {
concurrent_queue_rep<T>& r = *my_rep;
ticket tc = r.tail_counter;
ticket hc = r.head_counter;
// if tc!=r.tail_counter, the queue was not empty at some point between the two reads.
return tc==r.tail_counter && tc==hc+r.n_invalid_entries ;
}
template<typename T>
void concurrent_queue_base_v3<T>::internal_finish_clear() {
concurrent_queue_rep<T>& r = *my_rep;
size_t nq = r.n_queue;
for( size_t i=0; i<nq; ++i ) {
page* tp = r.array[i].tail_page;
if( is_valid_page(tp) ) {
__TBB_ASSERT( r.array[i].head_page==tp, "at most one page should remain" );
deallocate_page( tp );
r.array[i].tail_page = NULL;
} else
__TBB_ASSERT( !is_valid_page(r.array[i].head_page), "head page pointer corrupt?" );
}
}
template<typename T>
void concurrent_queue_base_v3<T>::assign( const concurrent_queue_base_v3& src,
item_constructor_t construct_item )
{
concurrent_queue_rep<T>& r = *my_rep;
r.items_per_page = src.my_rep->items_per_page;
// copy concurrent_queue_rep data
r.head_counter = src.my_rep->head_counter;
r.tail_counter = src.my_rep->tail_counter;
r.n_invalid_entries = src.my_rep->n_invalid_entries;
// copy or move micro_queues
for( size_t i = 0; i < r.n_queue; ++i )
r.array[i].assign( src.my_rep->array[i], *this, construct_item);
__TBB_ASSERT( r.head_counter==src.my_rep->head_counter && r.tail_counter==src.my_rep->tail_counter,
"the source concurrent queue should not be concurrently modified." );
}
template<typename Container, typename Value> class concurrent_queue_iterator;
template<typename T>
class concurrent_queue_iterator_rep: no_assign {
typedef typename micro_queue<T>::padded_page padded_page;
public:
ticket head_counter;
const concurrent_queue_base_v3<T>& my_queue;
typename concurrent_queue_base_v3<T>::page* array[concurrent_queue_rep<T>::n_queue];
concurrent_queue_iterator_rep( const concurrent_queue_base_v3<T>& queue ) :
head_counter(queue.my_rep->head_counter),
my_queue(queue)
{
for( size_t k=0; k<concurrent_queue_rep<T>::n_queue; ++k )
array[k] = queue.my_rep->array[k].head_page;
}
bool get_item( T*& item, size_t k ) ;
};
template<typename T>
bool concurrent_queue_iterator_rep<T>::get_item( T*& item, size_t k ) {
if( k==my_queue.my_rep->tail_counter ) {
item = NULL;
return true;
} else {
typename concurrent_queue_base_v3<T>::page* p = array[concurrent_queue_rep<T>::index(k)];
__TBB_ASSERT(p,NULL);
size_t i = modulo_power_of_two( k/concurrent_queue_rep<T>::n_queue, my_queue.my_rep->items_per_page );
item = &micro_queue<T>::get_ref(*p,i);
return (p->mask & uintptr_t(1)<<i)!=0;
}
}
template<typename Value>
class concurrent_queue_iterator_base_v3 {
concurrent_queue_iterator_rep<Value>* my_rep;
template<typename C, typename T, typename U>
friend bool operator==( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j );
template<typename C, typename T, typename U>
friend bool operator!=( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j );
protected:
Value* my_item;
concurrent_queue_iterator_base_v3() : my_rep(NULL), my_item(NULL) {
#if __TBB_GCC_OPTIMIZER_ORDERING_BROKEN
__TBB_compiler_fence();
#endif
}
concurrent_queue_iterator_base_v3( const concurrent_queue_iterator_base_v3& i )
: my_rep(NULL), my_item(NULL) {
assign(i);
}
concurrent_queue_iterator_base_v3& operator=( const concurrent_queue_iterator_base_v3& i ) {
assign(i);
return *this;
}
concurrent_queue_iterator_base_v3( const concurrent_queue_base_v3<Value>& queue ) ;
void assign( const concurrent_queue_iterator_base_v3<Value>& other ) ;
void advance() ;
~concurrent_queue_iterator_base_v3() {
cache_aligned_allocator<concurrent_queue_iterator_rep<Value> >().deallocate(my_rep, 1);
my_rep = NULL;
}
};
template<typename Value>
concurrent_queue_iterator_base_v3<Value>::concurrent_queue_iterator_base_v3( const concurrent_queue_base_v3<Value>& queue ) {
my_rep = cache_aligned_allocator<concurrent_queue_iterator_rep<Value> >().allocate(1);
new( my_rep ) concurrent_queue_iterator_rep<Value>(queue);
size_t k = my_rep->head_counter;
if( !my_rep->get_item(my_item, k) ) advance();
}
template<typename Value>
void concurrent_queue_iterator_base_v3<Value>::assign( const concurrent_queue_iterator_base_v3<Value>& other ) {
if( my_rep!=other.my_rep ) {
if( my_rep ) {
cache_aligned_allocator<concurrent_queue_iterator_rep<Value> >().deallocate(my_rep, 1);
my_rep = NULL;
}
if( other.my_rep ) {
my_rep = cache_aligned_allocator<concurrent_queue_iterator_rep<Value> >().allocate(1);
new( my_rep ) concurrent_queue_iterator_rep<Value>( *other.my_rep );
}
}
my_item = other.my_item;
}
template<typename Value>
void concurrent_queue_iterator_base_v3<Value>::advance() {
__TBB_ASSERT( my_item, "attempt to increment iterator past end of queue" );
size_t k = my_rep->head_counter;
const concurrent_queue_base_v3<Value>& queue = my_rep->my_queue;
#if TBB_USE_ASSERT
Value* tmp;
my_rep->get_item(tmp,k);
__TBB_ASSERT( my_item==tmp, NULL );
#endif /* TBB_USE_ASSERT */
size_t i = modulo_power_of_two( k/concurrent_queue_rep<Value>::n_queue, queue.my_rep->items_per_page );
if( i==queue.my_rep->items_per_page-1 ) {
typename concurrent_queue_base_v3<Value>::page*& root = my_rep->array[concurrent_queue_rep<Value>::index(k)];
root = root->next;
}
// advance k
my_rep->head_counter = ++k;
if( !my_rep->get_item(my_item, k) ) advance();
}
template<typename T> struct tbb_remove_cv {typedef T type;};
template<typename T> struct tbb_remove_cv<const T> {typedef T type;};
template<typename T> struct tbb_remove_cv<volatile T> {typedef T type;};
template<typename T> struct tbb_remove_cv<const volatile T> {typedef T type;};
template<typename Container, typename Value>
class concurrent_queue_iterator: public concurrent_queue_iterator_base_v3<typename tbb_remove_cv<Value>::type>,
public std::iterator<std::forward_iterator_tag,Value> {
#if !__TBB_TEMPLATE_FRIENDS_BROKEN
template<typename T, class A>
friend class ::tbb::strict_ppl::concurrent_queue;
#else
public:
#endif
explicit concurrent_queue_iterator( const concurrent_queue_base_v3<typename tbb_remove_cv<Value>::type>& queue ) :
concurrent_queue_iterator_base_v3<typename tbb_remove_cv<Value>::type>(queue)
{
}
public:
concurrent_queue_iterator() {}
concurrent_queue_iterator( const concurrent_queue_iterator<Container,typename Container::value_type>& other ) :
concurrent_queue_iterator_base_v3<typename tbb_remove_cv<Value>::type>(other)
{}
concurrent_queue_iterator& operator=( const concurrent_queue_iterator<Container,typename Container::value_type>& other ) {
concurrent_queue_iterator_base_v3<typename tbb_remove_cv<Value>::type>::operator=(other);
return *this;
}
Value& operator*() const {
return *static_cast<Value*>(this->my_item);
}
Value* operator->() const {return &operator*();}
concurrent_queue_iterator& operator++() {
this->advance();
return *this;
}
Value* operator++(int) {
Value* result = &operator*();
operator++();
return result;
}
}; // concurrent_queue_iterator
template<typename C, typename T, typename U>
bool operator==( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j ) {
return i.my_item==j.my_item;
}
template<typename C, typename T, typename U>
bool operator!=( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j ) {
return i.my_item!=j.my_item;
}
} // namespace internal
} // namespace strict_ppl
namespace internal {
class concurrent_queue_rep;
class concurrent_queue_iterator_rep;
class concurrent_queue_iterator_base_v3;
template<typename Container, typename Value> class concurrent_queue_iterator;
class concurrent_queue_base_v3: no_copy {
private:
concurrent_queue_rep* my_rep;
friend class concurrent_queue_rep;
friend struct micro_queue;
friend class micro_queue_pop_finalizer;
friend class concurrent_queue_iterator_rep;
friend class concurrent_queue_iterator_base_v3;
protected:
struct page {
page* next;
uintptr_t mask;
};
ptrdiff_t my_capacity;
size_t items_per_page;
size_t item_size;
enum copy_specifics { copy, move };
#if __TBB_PROTECTED_NESTED_CLASS_BROKEN
public:
#endif
template<typename T>
struct padded_page: page {
padded_page();
void operator=( const padded_page& );
T last;
};
private:
virtual void copy_item( page& dst, size_t index, const void* src ) = 0;
virtual void assign_and_destroy_item( void* dst, page& src, size_t index ) = 0;
protected:
__TBB_EXPORTED_METHOD concurrent_queue_base_v3( size_t item_size );
virtual __TBB_EXPORTED_METHOD ~concurrent_queue_base_v3();
void __TBB_EXPORTED_METHOD internal_push( const void* src );
void __TBB_EXPORTED_METHOD internal_pop( void* dst );
void __TBB_EXPORTED_METHOD internal_abort();
bool __TBB_EXPORTED_METHOD internal_push_if_not_full( const void* src );
bool __TBB_EXPORTED_METHOD internal_pop_if_present( void* dst );
ptrdiff_t __TBB_EXPORTED_METHOD internal_size() const;
bool __TBB_EXPORTED_METHOD internal_empty() const;
void __TBB_EXPORTED_METHOD internal_set_capacity( ptrdiff_t capacity, size_t element_size );
virtual page *allocate_page() = 0;
virtual void deallocate_page( page *p ) = 0;
/* note that the name may be misleading, but it remains so due to a historical accident. */
void __TBB_EXPORTED_METHOD internal_finish_clear() ;
void __TBB_EXPORTED_METHOD internal_throw_exception() const;
void __TBB_EXPORTED_METHOD assign( const concurrent_queue_base_v3& src ) ;
#if __TBB_CPP11_RVALUE_REF_PRESENT
void internal_swap( concurrent_queue_base_v3& src ) {
std::swap( my_capacity, src.my_capacity );
std::swap( items_per_page, src.items_per_page );
std::swap( item_size, src.item_size );
std::swap( my_rep, src.my_rep );
}
#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
void internal_insert_item( const void* src, copy_specifics op_type );
bool internal_insert_if_not_full( const void* src, copy_specifics op_type );
void internal_assign( const concurrent_queue_base_v3& src, copy_specifics op_type );
private:
virtual void copy_page_item( page& dst, size_t dindex, const page& src, size_t sindex ) = 0;
};
class concurrent_queue_base_v8: public concurrent_queue_base_v3 {
protected:
concurrent_queue_base_v8( size_t item_sz ) : concurrent_queue_base_v3( item_sz ) {}
void __TBB_EXPORTED_METHOD move_content( concurrent_queue_base_v8& src ) ;
bool __TBB_EXPORTED_METHOD internal_push_move_if_not_full( const void* src );
void __TBB_EXPORTED_METHOD internal_push_move( const void* src );
private:
friend struct micro_queue;
virtual void move_page_item( page& dst, size_t dindex, const page& src, size_t sindex ) = 0;
virtual void move_item( page& dst, size_t index, const void* src ) = 0;
};
class concurrent_queue_iterator_base_v3 {
concurrent_queue_iterator_rep* my_rep;
template<typename C, typename T, typename U>
friend bool operator==( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j );
template<typename C, typename T, typename U>
friend bool operator!=( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j );
void initialize( const concurrent_queue_base_v3& queue, size_t offset_of_data );
protected:
void* my_item;
concurrent_queue_iterator_base_v3() : my_rep(NULL), my_item(NULL) {}
concurrent_queue_iterator_base_v3( const concurrent_queue_iterator_base_v3& i ) : my_rep(NULL), my_item(NULL) {
assign(i);
}
concurrent_queue_iterator_base_v3& operator=( const concurrent_queue_iterator_base_v3& i ) {
assign(i);
return *this;
}
__TBB_EXPORTED_METHOD concurrent_queue_iterator_base_v3( const concurrent_queue_base_v3& queue );
__TBB_EXPORTED_METHOD concurrent_queue_iterator_base_v3( const concurrent_queue_base_v3& queue, size_t offset_of_data );
void __TBB_EXPORTED_METHOD assign( const concurrent_queue_iterator_base_v3& i );
void __TBB_EXPORTED_METHOD advance();
__TBB_EXPORTED_METHOD ~concurrent_queue_iterator_base_v3();
};
typedef concurrent_queue_iterator_base_v3 concurrent_queue_iterator_base;
template<typename Container, typename Value>
class concurrent_queue_iterator: public concurrent_queue_iterator_base,
public std::iterator<std::forward_iterator_tag,Value> {
#if !__TBB_TEMPLATE_FRIENDS_BROKEN
template<typename T, class A>
friend class ::tbb::concurrent_bounded_queue;
#else
public:
#endif
explicit concurrent_queue_iterator( const concurrent_queue_base_v3& queue ) :
concurrent_queue_iterator_base_v3(queue,__TBB_offsetof(concurrent_queue_base_v3::padded_page<Value>,last))
{
}
public:
concurrent_queue_iterator() {}
concurrent_queue_iterator( const concurrent_queue_iterator<Container,typename Container::value_type>& other ) :
concurrent_queue_iterator_base_v3(other)
{}
concurrent_queue_iterator& operator=( const concurrent_queue_iterator<Container,typename Container::value_type>& other ) {
concurrent_queue_iterator_base_v3::operator=(other);
return *this;
}
Value& operator*() const {
return *static_cast<Value*>(my_item);
}
Value* operator->() const {return &operator*();}
concurrent_queue_iterator& operator++() {
advance();
return *this;
}
Value* operator++(int) {
Value* result = &operator*();
operator++();
return result;
}
}; // concurrent_queue_iterator
template<typename C, typename T, typename U>
bool operator==( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j ) {
return i.my_item==j.my_item;
}
template<typename C, typename T, typename U>
bool operator!=( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j ) {
return i.my_item!=j.my_item;
}
} // namespace internal;
} // namespace tbb
#endif /* __TBB__concurrent_queue_impl_H */
tbb::internal::concurrent_queue_iterator::operator++
Value * operator++(int)
Post increment.
Definition: _concurrent_queue_impl.h:1057
tbb::strict_ppl::internal::concurrent_queue_base_v3::allocate_page
virtual page * allocate_page() __TBB_override
Definition: _concurrent_queue_impl.h:438
tbb::strict_ppl::internal::concurrent_queue_iterator_rep::concurrent_queue_iterator_rep
concurrent_queue_iterator_rep(const concurrent_queue_base_v3< T > &queue)
Definition: _concurrent_queue_impl.h:617
tbb::strict_ppl::internal::concurrent_queue_base_v3::internal_finish_clear
void internal_finish_clear()
free any remaining pages
Definition: _concurrent_queue_impl.h:574
tbb::strict_ppl::internal::micro_queue::destroyer::~destroyer
~destroyer()
Definition: _concurrent_queue_impl.h:142
tbb::internal::concurrent_queue_iterator_base
concurrent_queue_iterator_base_v3 concurrent_queue_iterator_base
Definition: _concurrent_queue_impl.h:1006
tbb::spin_mutex
A lock that occupies a single byte.
Definition: spin_mutex.h:39
tbb::strict_ppl::internal::concurrent_queue_base_v3::padded_page
micro_queue< T >::padded_page padded_page
Definition: _concurrent_queue_impl.h:435
tbb::internal::concurrent_queue_iterator::operator->
Value * operator->() const
Definition: _concurrent_queue_impl.h:1048
tbb::strict_ppl::internal::concurrent_queue_rep::index
static size_t index(ticket k)
Map ticket to an array index.
Definition: _concurrent_queue_impl.h:405
internal
Definition: _flow_graph_async_msg_impl.h:24
tbb::strict_ppl::internal::concurrent_queue_rep_base
parts of concurrent_queue_rep that do not have references to micro_queue
Definition: _concurrent_queue_impl.h:67
void
void
Definition: ittnotify_static.h:91
tbb::strict_ppl::internal::micro_queue::destroyer::destroyer
destroyer(T &value)
Definition: _concurrent_queue_impl.h:141
tbb::strict_ppl::internal::micro_queue::padded_page
Definition: _concurrent_queue_impl.h:167
tbb::internal::concurrent_queue_base_v3::my_rep
concurrent_queue_rep * my_rep
Internal representation.
Definition: _concurrent_queue_impl.h:829
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::strict_ppl::internal::is_valid_page
bool is_valid_page(const concurrent_queue_rep_base::page *p)
Definition: _concurrent_queue_impl.h:102
tbb::internal::no_copy
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:330
tbb::internal::itt_store_word_with_release
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
Definition: tbb_profiling.h:157
tbb::strict_ppl::internal::micro_queue::page
concurrent_queue_rep_base::page page
Definition: _concurrent_queue_impl.h:135
tbb::internal::concurrent_queue_base_v3::copy_specifics
copy_specifics
Definition: _concurrent_queue_impl.h:852
tbb::internal::atomic_backoff
Class that implements exponential backoff.
Definition: tbb_machine.h:348
tbb::internal::throw_exception
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
Definition: tbb_exception.h:105
tbb::strict_ppl::internal::concurrent_queue_base_v3::internal_push
void internal_push(const void *src, item_constructor_t construct_item)
Enqueue item at tail of queue.
Definition: _concurrent_queue_impl.h:469
tbb::strict_ppl::internal::concurrent_queue_page_allocator
Abstract class to define interface for page allocation/deallocation.
Definition: _concurrent_queue_impl.h:110
tbb::internal::concurrent_queue_base_v8::move_item
virtual void move_item(page &dst, size_t index, const void *src)=0
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::my_item
Value * my_item
Pointer to current item.
Definition: _concurrent_queue_impl.h:658
tbb::internal::concurrent_queue_iterator::concurrent_queue_iterator
concurrent_queue_iterator()
Definition: _concurrent_queue_impl.h:1029
tbb::strict_ppl::internal::concurrent_queue_rep
representation of concurrent_queue_base
Definition: _concurrent_queue_impl.h:61
tbb::internal::concurrent_queue_iterator::operator=
concurrent_queue_iterator & operator=(const concurrent_queue_iterator< Container, typename Container::value_type > &other)
Iterator assignment.
Definition: _concurrent_queue_impl.h:1038
tbb::internal::concurrent_queue_base_v8
For internal use only.
Definition: _concurrent_queue_impl.h:940
tbb::strict_ppl::internal::micro_queue::destroyer::my_value
T & my_value
Definition: _concurrent_queue_impl.h:139
tbb::internal::concurrent_queue_iterator::concurrent_queue_iterator
concurrent_queue_iterator(const concurrent_queue_iterator< Container, typename Container::value_type > &other)
Definition: _concurrent_queue_impl.h:1033
tbb
The graph class.
Definition: serial/tbb/parallel_for.h:46
tbb::strict_ppl::internal::concurrent_queue_iterator::operator->
Value * operator->() const
Definition: _concurrent_queue_impl.h:782
tbb::internal::concurrent_queue_base_v3
For internal use only.
Definition: _concurrent_queue_impl.h:826
tbb::strict_ppl::internal::concurrent_queue_base_v3::~concurrent_queue_base_v3
virtual ~concurrent_queue_base_v3()
Definition: _concurrent_queue_impl.h:459
tbb::internal::concurrent_queue_base_v8::concurrent_queue_base_v8
concurrent_queue_base_v8(size_t item_sz)
Definition: _concurrent_queue_impl.h:942
tbb::internal::concurrent_queue_base_v8::move_page_item
virtual void move_page_item(page &dst, size_t dindex, const page &src, size_t sindex)=0
tbb::strict_ppl::internal::concurrent_queue_rep::array
micro_queue< T > array[n_queue]
Definition: _concurrent_queue_impl.h:402
tbb::internal::concurrent_queue_rep
Internal representation of a ConcurrentQueue.
Definition: concurrent_queue.cpp:112
tbb::internal::swap
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:564
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::operator==
friend bool operator==(const concurrent_queue_iterator< C, T > &i, const concurrent_queue_iterator< C, U > &j)
Definition: _concurrent_queue_impl.h:800
tbb::internal::micro_queue
A queue using simple locking.
Definition: concurrent_queue.cpp:47
tbb::cache_aligned_allocator
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
Definition: cache_aligned_allocator.h:60
tbb::strict_ppl::internal::micro_queue_pop_finalizer
Definition: _concurrent_queue_impl.h:59
tbb::internal::concurrent_queue_base_v3::items_per_page
size_t items_per_page
Always a power of 2.
Definition: _concurrent_queue_impl.h:847
tbb::internal::spin_wait_while_eq
void spin_wait_while_eq(const volatile T &location, U value)
Spin WHILE the value of the variable is equal to a given value.
Definition: tbb_machine.h:394
d
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
Definition: ittnotify_static.h:109
tbb::strict_ppl::internal::concurrent_queue_rep::choose
micro_queue< T > & choose(ticket k)
Definition: _concurrent_queue_impl.h:409
tbb::strict_ppl::internal::concurrent_queue_base_v3::internal_size
size_t internal_size() const
Get size of queue; result may be invalid if queue is modified concurrently.
Definition: _concurrent_queue_impl.h:553
tbb::internal::concurrent_queue_iterator_base_v3::my_rep
concurrent_queue_iterator_rep * my_rep
concurrent_queue over which we are iterating.
Definition: _concurrent_queue_impl.h:963
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::my_rep
concurrent_queue_iterator_rep< Value > * my_rep
Represents concurrent_queue over which we are iterating.
Definition: _concurrent_queue_impl.h:649
tbb::strict_ppl::internal::tbb_remove_cv
Similar to C++0x std::remove_cv.
Definition: _concurrent_queue_impl.h:739
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::assign
void assign(const concurrent_queue_iterator_base_v3< Value > &other)
Assignment.
Definition: _concurrent_queue_impl.h:703
tbb::strict_ppl::internal::micro_queue::copy_item
void copy_item(page &dst, size_t dindex, const void *src, item_constructor_t construct_item)
Definition: _concurrent_queue_impl.h:145
tbb::strict_ppl::internal::micro_queue_pop_finalizer::allocator
concurrent_queue_page_allocator & allocator
Definition: _concurrent_queue_impl.h:364
tbb::strict_ppl::internal::concurrent_queue_base_v3::concurrent_queue_base_v3
concurrent_queue_base_v3()
Definition: _concurrent_queue_impl.h:506
tbb::strict_ppl::internal::concurrent_queue_iterator_rep::head_counter
ticket head_counter
Definition: _concurrent_queue_impl.h:614
tbb::strict_ppl::internal::concurrent_queue_base_v3::internal_throw_exception
void internal_throw_exception() const
Obsolete.
Definition: _concurrent_queue_impl.h:490
tbb::strict_ppl::internal::concurrent_queue_iterator_rep::my_queue
const concurrent_queue_base_v3< T > & my_queue
Definition: _concurrent_queue_impl.h:615
tbb::internal::concurrent_queue_base_v3::my_capacity
ptrdiff_t my_capacity
Capacity of the queue.
Definition: _concurrent_queue_impl.h:844
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::~concurrent_queue_iterator_base_v3
~concurrent_queue_iterator_base_v3()
Destructor.
Definition: _concurrent_queue_impl.h:688
tbb::internal::atomic_backoff::pause
void pause()
Pause for a while.
Definition: tbb_machine.h:363
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3
Constness-independent portion of concurrent_queue_iterator.
Definition: _concurrent_queue_impl.h:394
tbb::strict_ppl::internal::concurrent_queue_iterator::operator++
concurrent_queue_iterator & operator++()
Advance to next item in queue.
Definition: _concurrent_queue_impl.h:785
tbb::strict_ppl::internal::concurrent_queue_rep_base::n_queue
static const size_t n_queue
Definition: _concurrent_queue_impl.h:77
tbb::strict_ppl::internal::concurrent_queue_base_v3::page
concurrent_queue_rep< T >::page page
Definition: _concurrent_queue_impl.h:432
tbb::strict_ppl::internal::concurrent_queue_base_v3::my_rep
concurrent_queue_rep< T > * my_rep
Internal representation.
Definition: _concurrent_queue_impl.h:424
tbb::strict_ppl::internal::concurrent_queue_iterator::operator=
concurrent_queue_iterator & operator=(const concurrent_queue_iterator< Container, typename Container::value_type > &other)
Iterator assignment.
Definition: _concurrent_queue_impl.h:772
tbb::strict_ppl::internal::micro_queue_pop_finalizer::page
concurrent_queue_rep_base::page page
Definition: _concurrent_queue_impl.h:360
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::concurrent_queue_iterator_base_v3
concurrent_queue_iterator_base_v3(const concurrent_queue_iterator_base_v3 &i)
Copy constructor.
Definition: _concurrent_queue_impl.h:668
tbb::strict_ppl::internal::micro_queue_pop_finalizer::my_queue
micro_queue< T > & my_queue
Definition: _concurrent_queue_impl.h:362
tbb::strict_ppl::internal::concurrent_queue_iterator_rep::padded_page
micro_queue< T >::padded_page padded_page
Definition: _concurrent_queue_impl.h:612
tbb::strict_ppl::internal::micro_queue::assign_and_destroy_item
void assign_and_destroy_item(void *dst, page &src, size_t index)
Definition: _concurrent_queue_impl.h:156
tbb::strict_ppl::internal::micro_queue::copy_item
void copy_item(page &dst, size_t dindex, const page &src, size_t sindex, item_constructor_t construct_item)
Definition: _concurrent_queue_impl.h:149
tbb::strict_ppl::internal::tbb_remove_cv< volatile T >::type
T type
Definition: _concurrent_queue_impl.h:741
tbb::internal::acquired
Definition: tbb_profiling.h:129
tbb::internal::eid_bad_last_alloc
Definition: tbb_exception.h:69
tbb::strict_ppl::internal::micro_queue::push
void push(const void *item, ticket k, concurrent_queue_base_v3< T > &base, item_constructor_t construct_item)
Definition: _concurrent_queue_impl.h:215
tbb::internal::concurrent_queue_iterator::operator++
concurrent_queue_iterator & operator++()
Advance to next item in queue.
Definition: _concurrent_queue_impl.h:1051
tbb::strict_ppl::internal::micro_queue::tail_page
atomic< page * > tail_page
Definition: _concurrent_queue_impl.h:183
tbb::strict_ppl::internal::concurrent_queue_rep_base::page::next
page * next
Definition: _concurrent_queue_impl.h:81
tbb::internal::concurrent_queue_base_v3::padded_page
Definition: _concurrent_queue_impl.h:858
tbb::strict_ppl::internal::concurrent_queue_page_allocator::~concurrent_queue_page_allocator
virtual ~concurrent_queue_page_allocator()
Definition: _concurrent_queue_impl.h:115
tbb::internal::concurrent_queue_iterator_base_v3::operator=
concurrent_queue_iterator_base_v3 & operator=(const concurrent_queue_iterator_base_v3 &i)
Definition: _concurrent_queue_impl.h:984
tbb::move
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
tbb::strict_ppl::internal::concurrent_queue_base_v3::internal_swap
void internal_swap(concurrent_queue_base_v3 &src)
swap internal representation
Definition: _concurrent_queue_impl.h:499
tbb::strict_ppl::internal::tbb_remove_cv< const T >::type
T type
Definition: _concurrent_queue_impl.h:740
tbb::strict_ppl::internal::micro_queue::head_counter
atomic< ticket > head_counter
Definition: _concurrent_queue_impl.h:181
tbb::internal::concurrent_queue_base_v3::padded_page::last
T last
Must be last field.
Definition: _concurrent_queue_impl.h:864
lock
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 * lock
Definition: ittnotify_static.h:121
tbb::strict_ppl::internal::concurrent_queue_rep_base::page::mask
uintptr_t mask
Definition: _concurrent_queue_impl.h:82
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::operator!=
friend bool operator!=(const concurrent_queue_iterator< C, T > &i, const concurrent_queue_iterator< C, U > &j)
Definition: _concurrent_queue_impl.h:805
tbb::internal::NFS_MaxLineSize
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
Definition: tbb_stddef.h:216
tbb::internal::concurrent_queue_iterator_base_v3
Type-independent portion of concurrent_queue_iterator.
Definition: _concurrent_queue_impl.h:960
tbb::strict_ppl::internal::concurrent_queue_base_v3::internal_empty
bool internal_empty() const
check if the queue is empty; thread safe
Definition: _concurrent_queue_impl.h:565
tbb::strict_ppl::internal::concurrent_queue_base_v3::item_constructor_t
micro_queue< T >::item_constructor_t item_constructor_t
Definition: _concurrent_queue_impl.h:436
tbb::strict_ppl::internal::operator==
bool operator==(const concurrent_queue_iterator< C, T > &i, const concurrent_queue_iterator< C, U > &j)
Definition: _concurrent_queue_impl.h:800
tbb::strict_ppl::internal::micro_queue::head_page
atomic< page * > head_page
Definition: _concurrent_queue_impl.h:180
tbb::strict_ppl::internal::concurrent_queue_rep_base::item_size
size_t item_size
Size of an item.
Definition: _concurrent_queue_impl.h:94
tbb::strict_ppl::internal::tbb_remove_cv::type
T type
Definition: _concurrent_queue_impl.h:739
tbb::internal::concurrent_queue_base_v3::page
Prefix on a page.
Definition: _concurrent_queue_impl.h:838
tbb::internal::concurrent_queue_base_v8::internal_push_move
void __TBB_EXPORTED_METHOD internal_push_move(const void *src)
Enqueue item at tail of queue using move operation.
Definition: concurrent_queue.cpp:367
tbb::strict_ppl::internal::micro_queue::pop
bool pop(void *dst, ticket k, concurrent_queue_base_v3< T > &base)
Definition: _concurrent_queue_impl.h:263
tbb::strict_ppl::internal::concurrent_queue_rep_base::items_per_page
size_t items_per_page
Always a power of 2.
Definition: _concurrent_queue_impl.h:91
tbb::strict_ppl::internal::concurrent_queue_rep_base::head_counter
atomic< ticket > head_counter
Definition: _concurrent_queue_impl.h:85
tbb::internal::concurrent_queue_iterator_rep
Definition: concurrent_queue.cpp:580
tbb::strict_ppl::internal::concurrent_queue_iterator_rep::get_item
bool get_item(T *&item, size_t k)
Set item to point to kth element. Return true if at end of queue or item is marked valid; false other...
Definition: _concurrent_queue_impl.h:630
__TBB_override
#define __TBB_override
Definition: tbb_stddef.h:240
tbb::strict_ppl::internal::operator!=
bool operator!=(const concurrent_queue_iterator< C, T > &i, const concurrent_queue_iterator< C, U > &j)
Definition: _concurrent_queue_impl.h:805
tbb::internal::micro_queue_pop_finalizer
Definition: concurrent_queue.cpp:77
tbb::strict_ppl::internal::micro_queue_pop_finalizer::my_page
page * my_page
Definition: _concurrent_queue_impl.h:363
__TBB_TRY
#define __TBB_TRY
Definition: tbb_stddef.h:283
tbb::strict_ppl::internal::concurrent_queue_base_v3::assign
void assign(const concurrent_queue_base_v3 &src, item_constructor_t construct_item)
copy or move internal representation
Definition: _concurrent_queue_impl.h:589
tbb::internal::concurrent_queue_base_v8::move_content
void __TBB_EXPORTED_METHOD move_content(concurrent_queue_base_v8 &src)
move items
Definition: concurrent_queue.cpp:573
tbb::internal::concurrent_queue_base_v3::page::mask
uintptr_t mask
Definition: _concurrent_queue_impl.h:840
__TBB_offsetof
#define __TBB_offsetof(class_name, member_name)
Extended variant of the standard offsetof macro.
Definition: tbb_stddef.h:266
tbb::strict_ppl::internal::micro_queue::destroyer
Class used to ensure exception-safety of method "pop".
Definition: _concurrent_queue_impl.h:138
tbb::internal::concurrent_queue_iterator::operator*
Value & operator*() const
Reference to current item.
Definition: _concurrent_queue_impl.h:1044
tbb::strict_ppl::internal::micro_queue::padded_page::padded_page
padded_page()
Not defined anywhere - exists to quiet warnings.
tbb::internal::itt_hide_store_word
void itt_hide_store_word(T &dst, T src)
Definition: tbb_profiling.h:210
tbb::internal::concurrent_queue_iterator
Meets requirements of a forward iterator for STL.
Definition: _concurrent_queue_impl.h:821
tbb::strict_ppl::internal::concurrent_queue_iterator::operator*
Value & operator*() const
Reference to current item.
Definition: _concurrent_queue_impl.h:778
tbb::strict_ppl::internal::concurrent_queue_iterator::concurrent_queue_iterator
concurrent_queue_iterator(const concurrent_queue_iterator< Container, typename Container::value_type > &other)
Definition: _concurrent_queue_impl.h:767
tbb::internal::concurrent_queue_iterator_base_v3::concurrent_queue_iterator_base_v3
concurrent_queue_iterator_base_v3(const concurrent_queue_iterator_base_v3 &i)
Copy constructor.
Definition: _concurrent_queue_impl.h:980
tbb::internal::modulo_power_of_two
argument_integer_type modulo_power_of_two(argument_integer_type arg, divisor_integer_type divisor)
A function to compute arg modulo divisor where divisor is a power of 2.
Definition: tbb_stddef.h:382
tbb::internal::no_assign
Base class for types that should not be assigned.
Definition: tbb_stddef.h:322
tbb::strict_ppl::internal::micro_queue::invalidate_page_and_rethrow
void invalidate_page_and_rethrow(ticket k)
Definition: _concurrent_queue_impl.h:327
tbb::strict_ppl::internal::micro_queue::padded_page::last
T last
Must be last field.
Definition: _concurrent_queue_impl.h:173
tbb::internal::eid_bad_alloc
Definition: tbb_exception.h:68
tbb::strict_ppl::internal::concurrent_queue_iterator::operator++
Value * operator++(int)
Post increment.
Definition: _concurrent_queue_impl.h:791
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::advance
void advance()
Advance iterator one step towards tail of queue.
Definition: _concurrent_queue_impl.h:718
tbb::strict_ppl::internal::micro_queue::assign
micro_queue & assign(const micro_queue &src, concurrent_queue_base_v3< T > &base, item_constructor_t construct_item)
Definition: _concurrent_queue_impl.h:286
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::concurrent_queue_iterator_base_v3
concurrent_queue_iterator_base_v3()
Default constructor.
Definition: _concurrent_queue_impl.h:661
tbb::internal::releasing
Definition: tbb_profiling.h:129
tbb::internal::NFS_GetLineSize
size_t __TBB_EXPORTED_FUNC NFS_GetLineSize()
Cache/sector line size.
Definition: cache_aligned_allocator.cpp:167
tbb::strict_ppl::internal::concurrent_queue_rep_base::page
Prefix on a page.
Definition: _concurrent_queue_impl.h:80
tbb::internal::concurrent_queue_base_v8::internal_push_move_if_not_full
bool __TBB_EXPORTED_METHOD internal_push_move_if_not_full(const void *src)
Attempt to enqueue item onto queue using move operation.
Definition: concurrent_queue.cpp:495
tbb::strict_ppl::internal::ticket
size_t ticket
Definition: _concurrent_queue_impl.h:56
tbb::strict_ppl::internal::micro_queue::get_ref
static T & get_ref(page &p, size_t index)
Definition: _concurrent_queue_impl.h:176
tbb::strict_ppl::internal::concurrent_queue_base_v3
base class of concurrent_queue
Definition: _concurrent_queue_impl.h:60
tbb::strict_ppl::internal::micro_queue::make_copy
page * make_copy(concurrent_queue_base_v3< T > &base, const page *src_page, size_t begin_in_page, size_t end_in_page, ticket &g_index, item_constructor_t construct_item)
Definition: _concurrent_queue_impl.h:344
tbb::strict_ppl::internal::micro_queue_pop_finalizer::~micro_queue_pop_finalizer
~micro_queue_pop_finalizer()
Definition: _concurrent_queue_impl.h:373
tbb::strict_ppl::internal::micro_queue_pop_finalizer::micro_queue_pop_finalizer
micro_queue_pop_finalizer(micro_queue< T > &queue, concurrent_queue_base_v3< T > &b, ticket k, page *p)
Definition: _concurrent_queue_impl.h:366
tbb::strict_ppl::internal::concurrent_queue_rep_base::tail_counter
atomic< ticket > tail_counter
Definition: _concurrent_queue_impl.h:87
tbb::strict_ppl::internal::concurrent_queue_iterator
Meets requirements of a forward iterator for STL.
Definition: _concurrent_queue_impl.h:608
value
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 int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
Definition: ittnotify_static.h:192
tbb::internal::concurrent_queue_iterator::concurrent_queue_iterator
concurrent_queue_iterator(const concurrent_queue_base_v3 &queue)
Construct iterator pointing to head of queue.
Definition: _concurrent_queue_impl.h:1023
tbb::strict_ppl::internal::tbb_remove_cv< const volatile T >::type
T type
Definition: _concurrent_queue_impl.h:742
tbb::strict_ppl::internal::concurrent_queue_base_v3::deallocate_page
virtual void deallocate_page(concurrent_queue_rep_base::page *p) __TBB_override
Definition: _concurrent_queue_impl.h:444
tbb::strict_ppl::internal::micro_queue::page_mutex
spin_mutex page_mutex
Definition: _concurrent_queue_impl.h:186
tbb::internal
Identifiers declared inside namespace internal should never be used directly by client code.
Definition: atomic.h:65
tbb::strict_ppl::internal::concurrent_queue_rep_base::n_invalid_entries
atomic< size_t > n_invalid_entries
number of invalid entries in the queue
Definition: _concurrent_queue_impl.h:97
tbb::internal::last
auto last(Container &c) -> decltype(begin(c))
Definition: _range_iterator.h:40
__TBB_CATCH
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:284
p
void const char const char int ITT_FORMAT __itt_group_sync p
Definition: ittnotify_static.h:91
tbb::internal::concurrent_queue_iterator_base_v3::my_item
void * my_item
Pointer to current item.
Definition: _concurrent_queue_impl.h:974
__TBB_EXPORTED_METHOD
#define __TBB_EXPORTED_METHOD
Definition: tbb_stddef.h:98
tbb::strict_ppl::internal::micro_queue
A queue using simple locking.
Definition: _concurrent_queue_impl.h:58
tbb::strict_ppl::internal::concurrent_queue_base_v3::internal_try_pop
bool internal_try_pop(void *dst)
Attempt to dequeue item from queue.
Definition: _concurrent_queue_impl.h:524
tbb::internal::call_itt_notify
void call_itt_notify(notify_type, void *)
Definition: tbb_profiling.h:276
tbb::internal::concurrent_queue_base_v3::item_size
size_t item_size
Size of an item.
Definition: _concurrent_queue_impl.h:850
tbb::strict_ppl::internal::concurrent_queue_iterator::concurrent_queue_iterator
concurrent_queue_iterator()
Definition: _concurrent_queue_impl.h:763
tbb::internal::spin_wait_until_eq
void spin_wait_until_eq(const volatile T &location, const U value)
Spin UNTIL the value of the variable is equal to a given value.
Definition: tbb_machine.h:402
tbb::strict_ppl::internal::micro_queue_pop_finalizer::my_ticket
ticket my_ticket
Definition: _concurrent_queue_impl.h:361
tbb::spin_mutex::scoped_lock
Represents acquisition of a mutex.
Definition: spin_mutex.h:53
tbb::strict_ppl::internal::micro_queue::padded_page::operator=
void operator=(const padded_page &)
Not defined anywhere - exists to quiet warnings.
__TBB_RETHROW
#define __TBB_RETHROW()
Definition: tbb_stddef.h:286
tbb::internal::concurrent_queue_iterator_base_v3::concurrent_queue_iterator_base_v3
concurrent_queue_iterator_base_v3()
Default constructor.
Definition: _concurrent_queue_impl.h:977
tbb::strict_ppl::internal::micro_queue::spin_wait_until_my_turn
void spin_wait_until_my_turn(atomic< ticket > &counter, ticket k, concurrent_queue_rep_base &rb) const
Definition: _concurrent_queue_impl.h:203
type
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 int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
Definition: ittnotify_static.h:198
tbb::strict_ppl::internal::micro_queue::tail_counter
atomic< ticket > tail_counter
Definition: _concurrent_queue_impl.h:184
__TBB_compiler_fence
#define __TBB_compiler_fence()
Definition: icc_generic.h:51
tbb::strict_ppl::internal::concurrent_queue_iterator_rep
Definition: _concurrent_queue_impl.h:393
tbb::strict_ppl::internal::concurrent_queue_iterator_base_v3::operator=
concurrent_queue_iterator_base_v3 & operator=(const concurrent_queue_iterator_base_v3 &i)
Definition: _concurrent_queue_impl.h:673
tbb::internal::concurrent_queue_base_v3::page::next
page * next
Definition: _concurrent_queue_impl.h:839
tbb::strict_ppl::internal::concurrent_queue_page_allocator::allocate_page
virtual concurrent_queue_rep_base::page * allocate_page()=0

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.