tbb::strict_ppl::internal::micro_queue< T > Class Template Reference

A queue using simple locking. More...

`#include <_concurrent_queue_impl.h>`

Inheritance diagram for tbb::strict_ppl::internal::micro_queue< T >:
Collaboration diagram for tbb::strict_ppl::internal::micro_queue< T >:

## Classes

class | destroyer
| Class used to ensure exception-safety of method "pop". More...
struct | padded_page

## Public Types

typedef void(* | item_constructor_t) (T *location, const void *src)

## Public Member Functions

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)

## Static Public Member Functions

static T & | get_ref (page &p, size_t index)

## Public Attributes

atomic< page * > | head_page
atomic< ticket > | head_counter
atomic< page * > | tail_page
atomic< ticket > | tail_counter
spin_mutex | page_mutex

## Private Types

typedef concurrent_queue_rep_base::page | page

## Private Member Functions

void | copy_item (page &dst, size_t dindex, const void *src, item_constructor_t construct_item)
void | copy_item (page &dst, size_t dindex, const page &src, size_t sindex, item_constructor_t construct_item)
void | assign_and_destroy_item (void *dst, page &src, size_t index)
void | spin_wait_until_my_turn (atomic< ticket > &counter, ticket k, concurrent_queue_rep_base &rb) const
Private Member Functions inherited from tbb::internal::no_copy
| no_copy (const no_copy &)=delete
| no_copy ()=default

## Friends

class | micro_queue_pop_finalizer< T >

## Detailed Description

### template<typename T>
class tbb::strict_ppl::internal::micro_queue< T >

A queue using simple locking.

For efficiency, this class has no constructor. The caller is expected to zero-initialize it.

Definition at line 58 of file _concurrent_queue_impl.h.

## Member Typedef Documentation

## item_constructor_t

template<typename T>

typedef void(* tbb::strict_ppl::internal::micro_queue< T >::item_constructor_t) (T *location, const void *src)

Definition at line 133 of file _concurrent_queue_impl.h.

## page

template<typename T>

typedef concurrent_queue_rep_base::page tbb::strict_ppl::internal::micro_queue< T >::page

private

Definition at line 135 of file _concurrent_queue_impl.h.

## Member Function Documentation

## assign()

template<typename T>

micro_queue< T > & tbb::strict_ppl::internal::micro_queue< T >::assign | ( | const micro_queue< T > & | src,
|  | concurrent_queue_base_v3< T > & | base,
|  | item_constructor_t | construct_item
| ) |  |

Definition at line 286 of file _concurrent_queue_impl.h.

{
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;
}

## assign_and_destroy_item()

template<typename T>

void tbb::strict_ppl::internal::micro_queue< T >::assign_and_destroy_item | ( | void * | dst,
|  | page & | src,
|  | size_t | index
| ) |  |

inline private

Definition at line 156 of file _concurrent_queue_impl.h.

{
T& from = get_ref(src,index);
destroyer d(from);
*static_cast<T*>(dst) = tbb::internal::move( from );
}

## copy_item() [1/2]

template<typename T>

void tbb::strict_ppl::internal::micro_queue< T >::copy_item | ( | page & | dst,
|  | size_t | dindex,
|  | const page & | src,
|  | size_t | sindex,
|  | item_constructor_t | construct_item
| ) |  |

inline private

Definition at line 149 of file _concurrent_queue_impl.h.

{
T& src_item = get_ref( const_cast<page&>(src), sindex );
construct_item( &get_ref(dst, dindex), static_cast<const void*>(&src_item) );
}

## copy_item() [2/2]

template<typename T>

void tbb::strict_ppl::internal::micro_queue< T >::copy_item | ( | page & | dst,
|  | size_t | dindex,
|  | const void * | src,
|  | item_constructor_t | construct_item
| ) |  |

inline private

Definition at line 145 of file _concurrent_queue_impl.h.

{
construct_item( &get_ref(dst, dindex), src );
}

## get_ref()

template<typename T>

static T& tbb::strict_ppl::internal::micro_queue< T >::get_ref | ( | page & | p,
|  | size_t | index
| ) |  |

inline static

Definition at line 176 of file _concurrent_queue_impl.h.

{
return (&static_cast<padded_page*>(static_cast<void*>(&p))->last)[index];
}

Referenced by tbb::strict_ppl::internal::concurrent_queue_iterator_rep< Value >::get_item().

Here is the caller graph for this function:

## invalidate_page_and_rethrow()

template<typename T >

void tbb::strict_ppl::internal::micro_queue< T >::invalidate_page_and_rethrow | ( | ticket | k | ) |

Definition at line 327 of file _concurrent_queue_impl.h.

{
// 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();
}

## make_copy()

template<typename T>

concurrent_queue_rep_base::page * tbb::strict_ppl::internal::micro_queue< T >::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 at line 344 of file _concurrent_queue_impl.h.

{
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;
}

## pop()

template<typename T>

bool tbb::strict_ppl::internal::micro_queue< T >::pop | ( | void * | dst,
|  | ticket | k,
|  | concurrent_queue_base_v3< T > & | base
| ) |  |

Definition at line 263 of file _concurrent_queue_impl.h.

{
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;
}

## push()

template<typename T>

void tbb::strict_ppl::internal::micro_queue< T >::push | ( | const void * | item,
|  | ticket | k,
|  | concurrent_queue_base_v3< T > & | base,
|  | item_constructor_t | construct_item
| ) |  |

Definition at line 215 of file _concurrent_queue_impl.h.

{
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();
}
}

## spin_wait_until_my_turn()

template<typename T >

void tbb::strict_ppl::internal::micro_queue< T >::spin_wait_until_my_turn | ( | atomic< ticket > & | counter,
|  | ticket | k,
|  | concurrent_queue_rep_base & | rb
| ) |  | const

private

Definition at line 203 of file _concurrent_queue_impl.h.

{
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 );
}
}
}

## Friends And Related Function Documentation

## micro_queue_pop_finalizer< T >

template<typename T>

friend class micro_queue_pop_finalizer< T >

friend

Definition at line 165 of file _concurrent_queue_impl.h.

## Member Data Documentation

## head_counter

template<typename T>

atomic<ticket> tbb::strict_ppl::internal::micro_queue< T >::head_counter

Definition at line 181 of file _concurrent_queue_impl.h.

Referenced by tbb::strict_ppl::internal::micro_queue< Value >::assign().

## head_page

template<typename T>

atomic<page*> tbb::strict_ppl::internal::micro_queue< T >::head_page

Definition at line 180 of file _concurrent_queue_impl.h.

Referenced by tbb::strict_ppl::internal::micro_queue< Value >::assign().

## page_mutex

template<typename T>

spin_mutex tbb::strict_ppl::internal::micro_queue< T >::page_mutex

Definition at line 186 of file _concurrent_queue_impl.h.

## tail_counter

template<typename T>

atomic<ticket> tbb::strict_ppl::internal::micro_queue< T >::tail_counter

Definition at line 184 of file _concurrent_queue_impl.h.

Referenced by tbb::strict_ppl::internal::micro_queue< Value >::assign().

## tail_page

template<typename T>

atomic<page*> tbb::strict_ppl::internal::micro_queue< T >::tail_page

Definition at line 183 of file _concurrent_queue_impl.h.

Referenced by tbb::strict_ppl::internal::micro_queue< Value >::assign().

The documentation for this class was generated from the following file:

- _concurrent_queue_impl.h

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::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::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::internal::micro_queue::tail_page
atomic< page * > tail_page
Definition: concurrent_queue.cpp:55
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::internal::concurrent_queue_rep::n_invalid_entries
atomic< size_t > n_invalid_entries
Definition: concurrent_queue.cpp:131
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::spin_mutex::scoped_lock
friend class scoped_lock
Definition: spin_mutex.h:179
tbb::internal::atomic_backoff::pause
void pause()
Pause for a while.
Definition: tbb_machine.h:363
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::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::internal::acquired
Definition: tbb_profiling.h:129
tbb::internal::eid_bad_last_alloc
Definition: tbb_exception.h:69
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::move
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
tbb::strict_ppl::internal::micro_queue::head_counter
atomic< ticket > head_counter
Definition: _concurrent_queue_impl.h:181
tbb::internal::micro_queue::head_page
atomic< page * > head_page
Definition: concurrent_queue.cpp:52
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::micro_queue::head_page
atomic< page * > head_page
Definition: _concurrent_queue_impl.h:180
tbb::internal::micro_queue::tail_counter
atomic< ticket > tail_counter
Definition: concurrent_queue.cpp:56
tbb::internal::micro_queue::head_counter
atomic< ticket > head_counter
Definition: concurrent_queue.cpp:53
tbb::internal::micro_queue_pop_finalizer
Definition: concurrent_queue.cpp:77
__TBB_TRY
#define __TBB_TRY
Definition: tbb_stddef.h:283
tbb::internal::itt_hide_store_word
void itt_hide_store_word(T &dst, T src)
Definition: tbb_profiling.h:210
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::strict_ppl::internal::micro_queue::invalidate_page_and_rethrow
void invalidate_page_and_rethrow(ticket k)
Definition: _concurrent_queue_impl.h:327
tbb::internal::ticket
size_t ticket
Definition: concurrent_queue.cpp:42
tbb::internal::releasing
Definition: tbb_profiling.h:129
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::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::page_mutex
spin_mutex page_mutex
Definition: _concurrent_queue_impl.h:186
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::call_itt_notify
void call_itt_notify(notify_type, void *)
Definition: tbb_profiling.h:276
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_RETHROW
#define __TBB_RETHROW()
Definition: tbb_stddef.h:286
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
tbb::strict_ppl::internal::micro_queue::tail_counter
atomic< ticket > tail_counter
Definition: _concurrent_queue_impl.h:184

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.