Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
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_queueassign (const micro_queue &src, concurrent_queue_base_v3< T > &base, item_constructor_t construct_item)
 
pagemake_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< tickethead_counter
 
atomic< page * > tail_page
 
atomic< tickettail_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 ()
 Allow default construction. More...
 

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 62 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 137 of file _concurrent_queue_impl.h.

◆ page

Definition at line 139 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 290 of file _concurrent_queue_impl.h.

292 {
295 
296  const page* srcp = src.head_page;
297  if( is_valid_page(srcp) ) {
298  ticket g_index = head_counter;
299  __TBB_TRY {
301  size_t index = modulo_power_of_two( head_counter/concurrent_queue_rep_base::n_queue, base.my_rep->items_per_page );
302  size_t end_in_first_page = (index+n_items<base.my_rep->items_per_page)?(index+n_items):base.my_rep->items_per_page;
303 
304  head_page = make_copy( base, srcp, index, end_in_first_page, g_index, construct_item );
305  page* cur_page = head_page;
306 
307  if( srcp != src.tail_page ) {
308  for( srcp = srcp->next; srcp!=src.tail_page; srcp=srcp->next ) {
309  cur_page->next = make_copy( base, srcp, 0, base.my_rep->items_per_page, g_index, construct_item );
310  cur_page = cur_page->next;
311  }
312 
313  __TBB_ASSERT( srcp==src.tail_page, NULL );
314  size_t last_index = modulo_power_of_two( tail_counter/concurrent_queue_rep_base::n_queue, base.my_rep->items_per_page );
315  if( last_index==0 ) last_index = base.my_rep->items_per_page;
316 
317  cur_page->next = make_copy( base, srcp, 0, last_index, g_index, construct_item );
318  cur_page = cur_page->next;
319  }
320  tail_page = cur_page;
321  } __TBB_CATCH (...) {
322  invalidate_page_and_rethrow( g_index );
323  }
324  } else {
325  head_page = tail_page = NULL;
326  }
327  return *this;
328 }
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:365
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
#define __TBB_TRY
Definition: tbb_stddef.h:287
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:288
concurrent_queue_rep * my_rep
Internal representation.
concurrent_queue_rep_base::page page
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)
bool is_valid_page(const concurrent_queue_rep_base::page *p)

◆ 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 
)
inlineprivate

Definition at line 160 of file _concurrent_queue_impl.h.

160  {
161  T& from = get_ref(src,index);
162  destroyer d(from);
163  *static_cast<T*>(dst) = tbb::internal::move( from );
164  }
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 move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:309
static T & get_ref(page &p, size_t index)

◆ copy_item() [1/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 
)
inlineprivate

Definition at line 149 of file _concurrent_queue_impl.h.

149  {
150  construct_item( &get_ref(dst, dindex), src );
151  }
static T & get_ref(page &p, size_t index)

◆ copy_item() [2/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 
)
inlineprivate

Definition at line 153 of file _concurrent_queue_impl.h.

155  {
156  T& src_item = get_ref( const_cast<page&>(src), sindex );
157  construct_item( &get_ref(dst, dindex), static_cast<const void*>(&src_item) );
158  }
static T & get_ref(page &p, size_t index)

◆ get_ref()

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

Definition at line 180 of file _concurrent_queue_impl.h.

180  {
181  return (&static_cast<padded_page*>(static_cast<void*>(&p))->last)[index];
182  }
void const char const char int ITT_FORMAT __itt_group_sync p
auto last(Container &c) -> decltype(begin(c))

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 331 of file _concurrent_queue_impl.h.

331  {
332  // Append an invalid page at address 1 so that no more pushes are allowed.
333  page* invalid_page = (page*)uintptr_t(1);
334  {
337  page* q = tail_page;
338  if( is_valid_page(q) )
339  q->next = invalid_page;
340  else
341  head_page = invalid_page;
342  tail_page = invalid_page;
343  }
344  __TBB_RETHROW();
345 }
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
friend class scoped_lock
Definition: spin_mutex.h:180
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
concurrent_queue_rep_base::page page
bool is_valid_page(const concurrent_queue_rep_base::page *p)
#define __TBB_RETHROW()
Definition: tbb_stddef.h:290

◆ 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 348 of file _concurrent_queue_impl.h.

351 {
352  concurrent_queue_page_allocator& pa = base;
353  page* new_page = pa.allocate_page();
354  new_page->next = NULL;
355  new_page->mask = src_page->mask;
356  for( ; begin_in_page!=end_in_page; ++begin_in_page, ++g_index )
357  if( new_page->mask & uintptr_t(1)<<begin_in_page )
358  copy_item( *new_page, begin_in_page, *src_page, begin_in_page, construct_item );
359  return new_page;
360 }
void copy_item(page &dst, size_t dindex, const void *src, item_constructor_t construct_item)
concurrent_queue_rep_base::page 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 267 of file _concurrent_queue_impl.h.

267  {
273  page *p = head_page;
274  __TBB_ASSERT( p, NULL );
275  size_t index = modulo_power_of_two( k/concurrent_queue_rep_base::n_queue, base.my_rep->items_per_page );
276  bool success = false;
277  {
278  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 );
279  if( p->mask & uintptr_t(1)<<index ) {
280  success = true;
281  assign_and_destroy_item( dst, *p, index );
282  } else {
283  --base.my_rep->n_invalid_entries;
284  }
285  }
286  return success;
287 }
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:365
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
void assign_and_destroy_item(void *dst, page &src, size_t index)
void const char const char int ITT_FORMAT __itt_group_sync p
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:395
void call_itt_notify(notify_type, void *)
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:403
concurrent_queue_rep * my_rep
Internal representation.
concurrent_queue_rep_base::page page

◆ 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 219 of file _concurrent_queue_impl.h.

221 {
223  page* p = NULL;
224  size_t index = modulo_power_of_two( k/concurrent_queue_rep_base::n_queue, base.my_rep->items_per_page);
225  if( !index ) {
226  __TBB_TRY {
227  concurrent_queue_page_allocator& pa = base;
228  p = pa.allocate_page();
229  } __TBB_CATCH (...) {
230  ++base.my_rep->n_invalid_entries;
232  }
233  p->mask = 0;
234  p->next = NULL;
235  }
236 
239 
240  if( p ) {
242  page* q = tail_page;
243  if( is_valid_page(q) )
244  q->next = p;
245  else
246  head_page = p;
247  tail_page = p;
248  } else {
249  p = tail_page;
250  }
251 
252  __TBB_TRY {
253  copy_item( *p, index, item, construct_item );
254  // If no exception was thrown, mark item as present.
255  itt_hide_store_word(p->mask, p->mask | uintptr_t(1)<<index);
258  } __TBB_CATCH (...) {
259  ++base.my_rep->n_invalid_entries;
262  __TBB_RETHROW();
263  }
264 }
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:365
void copy_item(page &dst, size_t dindex, const void *src, item_constructor_t construct_item)
#define __TBB_TRY
Definition: tbb_stddef.h:287
void const char const char int ITT_FORMAT __itt_group_sync p
friend class scoped_lock
Definition: spin_mutex.h:180
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:288
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
void call_itt_notify(notify_type, void *)
void itt_hide_store_word(T &dst, T src)
concurrent_queue_rep * my_rep
Internal representation.
concurrent_queue_rep_base::page page
bool is_valid_page(const concurrent_queue_rep_base::page *p)
void spin_wait_until_my_turn(atomic< ticket > &counter, ticket k, concurrent_queue_rep_base &rb) const
#define __TBB_RETHROW()
Definition: tbb_stddef.h:290

◆ 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 207 of file _concurrent_queue_impl.h.

207  {
208  for( atomic_backoff b(true);;b.pause() ) {
209  ticket c = counter;
210  if( c==k ) return;
211  else if( c&1 ) {
212  ++rb.n_invalid_entries;
214  }
215  }
216 }
void pause()
Pause for a while.
Definition: tbb_machine.h:364
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
Class that implements exponential backoff.
Definition: tbb_machine.h:349

Friends And Related Function Documentation

◆ micro_queue_pop_finalizer< T >

template<typename T>
friend class micro_queue_pop_finalizer< T >
friend

Definition at line 169 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

◆ head_page

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

◆ page_mutex

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

Definition at line 190 of file _concurrent_queue_impl.h.

◆ tail_counter

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

◆ tail_page

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

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

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.