Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
tbb::internal::micro_queue Struct Reference

A queue using simple locking. More...

Collaboration diagram for tbb::internal::micro_queue:

Public Types

typedef concurrent_queue_base::page page
 

Public Member Functions

void push (const void *item, ticket k, concurrent_queue_base &base, concurrent_queue_base::copy_specifics op_type)
 
void abort_push (ticket k, concurrent_queue_base &base)
 
bool pop (void *dst, ticket k, concurrent_queue_base &base)
 
micro_queueassign (const micro_queue &src, concurrent_queue_base &base, concurrent_queue_base::copy_specifics op_type)
 
pagemake_copy (concurrent_queue_base &base, const page *src_page, size_t begin_in_page, size_t end_in_page, ticket &g_index, concurrent_queue_base::copy_specifics op_type)
 
void make_invalid (ticket k)
 

Public Attributes

atomic< page * > head_page
 
atomic< tickethead_counter
 
atomic< page * > tail_page
 
atomic< tickettail_counter
 
spin_mutex page_mutex
 

Friends

class micro_queue_pop_finalizer
 

Detailed Description

A queue using simple locking.

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

Definition at line 51 of file concurrent_queue.cpp.

Member Typedef Documentation

◆ page

Member Function Documentation

◆ abort_push()

void tbb::internal::micro_queue::abort_push ( ticket  k,
concurrent_queue_base base 
)

Definition at line 230 of file concurrent_queue.cpp.

230  {
231  push(NULL, k, base, concurrent_queue_base::copy);
232 }
void push(const void *item, ticket k, concurrent_queue_base &base, concurrent_queue_base::copy_specifics op_type)

References tbb::internal::concurrent_queue_base_v3::copy, and push().

Referenced by tbb::internal::concurrent_queue_base_v3::internal_insert_item().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ assign()

micro_queue & tbb::internal::micro_queue::assign ( const micro_queue src,
concurrent_queue_base base,
concurrent_queue_base::copy_specifics  op_type 
)

Definition at line 257 of file concurrent_queue.cpp.

259 {
260  head_counter = src.head_counter;
261  tail_counter = src.tail_counter;
262 
263  const page* srcp = src.head_page;
264  if( srcp ) {
265  ticket g_index = head_counter;
266  __TBB_TRY {
268  size_t index = modulo_power_of_two( head_counter/concurrent_queue_rep::n_queue, base.items_per_page );
269  size_t end_in_first_page = (index+n_items<base.items_per_page)?(index+n_items):base.items_per_page;
270 
271  head_page = make_copy( base, srcp, index, end_in_first_page, g_index, op_type );
272  page* cur_page = head_page;
273 
274  if( srcp != src.tail_page ) {
275  for( srcp = srcp->next; srcp!=src.tail_page; srcp=srcp->next ) {
276  cur_page->next = make_copy( base, srcp, 0, base.items_per_page, g_index, op_type );
277  cur_page = cur_page->next;
278  }
279 
280  __TBB_ASSERT( srcp==src.tail_page, NULL );
281 
282  size_t last_index = modulo_power_of_two( tail_counter/concurrent_queue_rep::n_queue, base.items_per_page );
283  if( last_index==0 ) last_index = base.items_per_page;
284 
285  cur_page->next = make_copy( base, srcp, 0, last_index, g_index, op_type );
286  cur_page = cur_page->next;
287  }
288  tail_page = cur_page;
289  } __TBB_CATCH(...) {
290  make_invalid( g_index );
291  __TBB_RETHROW();
292  }
293  } else {
294  head_page = tail_page = NULL;
295  }
296  return *this;
297 }
concurrent_queue_base::page page
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
static const size_t n_queue
Must be power of 2.
page * make_copy(concurrent_queue_base &base, const page *src_page, size_t begin_in_page, size_t end_in_page, ticket &g_index, concurrent_queue_base::copy_specifics op_type)
#define __TBB_RETHROW()
Definition: tbb_stddef.h:290

References __TBB_ASSERT, __TBB_CATCH, __TBB_RETHROW, __TBB_TRY, head_counter, head_page, tbb::internal::concurrent_queue_base_v3::items_per_page, make_copy(), make_invalid(), tbb::internal::modulo_power_of_two(), tbb::internal::concurrent_queue_rep::n_queue, tbb::internal::concurrent_queue_base_v3::page::next, tail_counter, and tail_page.

Referenced by tbb::internal::concurrent_queue_base_v3::internal_assign().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ make_copy()

concurrent_queue_base::page * tbb::internal::micro_queue::make_copy ( concurrent_queue_base base,
const page src_page,
size_t  begin_in_page,
size_t  end_in_page,
ticket g_index,
concurrent_queue_base::copy_specifics  op_type 
)

Definition at line 299 of file concurrent_queue.cpp.

302 {
303  page* new_page = base.allocate_page();
304  new_page->next = NULL;
305  new_page->mask = src_page->mask;
306  for( ; begin_in_page!=end_in_page; ++begin_in_page, ++g_index )
307  if( new_page->mask & uintptr_t(1)<<begin_in_page ) {
308  if( concurrent_queue_base::copy == op_type ) {
309  base.copy_page_item( *new_page, begin_in_page, *src_page, begin_in_page );
310  } else {
311  __TBB_ASSERT( concurrent_queue_base::move == op_type, NULL );
312  static_cast<concurrent_queue_base_v8&>(base).move_page_item( *new_page, begin_in_page, *src_page, begin_in_page );
313  }
314  }
315  return new_page;
316 }
concurrent_queue_base::page page
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169

References __TBB_ASSERT, tbb::internal::concurrent_queue_base_v3::allocate_page(), tbb::internal::concurrent_queue_base_v3::copy, tbb::internal::concurrent_queue_base_v3::copy_page_item(), tbb::internal::concurrent_queue_base_v3::page::mask, tbb::internal::concurrent_queue_base_v3::move, and tbb::internal::concurrent_queue_base_v3::page::next.

Referenced by assign().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ make_invalid()

void tbb::internal::micro_queue::make_invalid ( ticket  k)

Definition at line 318 of file concurrent_queue.cpp.

319 {
320  static concurrent_queue_base::page dummy = {static_cast<page*>((void*)1), 0};
321  // mark it so that no more pushes are allowed.
322  static_invalid_page = &dummy;
323  {
326  if( page* q = tail_page )
327  q->next = static_cast<page*>(static_invalid_page);
328  else
329  head_page = static_cast<page*>(static_invalid_page);
330  tail_page = static_cast<page*>(static_invalid_page);
331  }
332 }
concurrent_queue_base::page page
static void * static_invalid_page
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
static const size_t n_queue
Must be power of 2.

References head_page, lock, tbb::internal::concurrent_queue_rep::n_queue, page_mutex, tbb::internal::static_invalid_page, tail_counter, and tail_page.

Referenced by assign(), and push().

Here is the caller graph for this function:

◆ pop()

bool tbb::internal::micro_queue::pop ( void dst,
ticket  k,
concurrent_queue_base base 
)

Definition at line 234 of file concurrent_queue.cpp.

234  {
238  page *p = head_page;
239  __TBB_ASSERT( p, NULL );
240  size_t index = modulo_power_of_two( k/concurrent_queue_rep::n_queue, base.items_per_page );
241  bool success = false;
242  {
243  micro_queue_pop_finalizer finalizer( *this, base, k+concurrent_queue_rep::n_queue, index==base.items_per_page-1 ? p : NULL );
244  if( p->mask & uintptr_t(1)<<index ) {
245  success = true;
246  ITT_NOTIFY( sync_acquired, dst );
247  ITT_NOTIFY( sync_acquired, head_page );
248  base.assign_and_destroy_item( dst, *p, index );
250  } else {
251  --base.my_rep->n_invalid_entries;
252  }
253  }
254  return success;
255 }
concurrent_queue_base::page page
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 const char const char int ITT_FORMAT __itt_group_sync p
static const size_t n_queue
Must be power of 2.
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 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 sync_releasing
#define ITT_NOTIFY(name, obj)
Definition: itt_notify.h:120
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

References __TBB_ASSERT, tbb::internal::concurrent_queue_base_v3::assign_and_destroy_item(), head_counter, head_page, tbb::internal::concurrent_queue_base_v3::items_per_page, ITT_NOTIFY, tbb::internal::modulo_power_of_two(), tbb::internal::concurrent_queue_base_v3::my_rep, tbb::internal::concurrent_queue_rep::n_invalid_entries, tbb::internal::concurrent_queue_rep::n_queue, p, tbb::internal::spin_wait_until_eq(), tbb::internal::spin_wait_while_eq(), sync_releasing, and tail_counter.

Referenced by tbb::internal::concurrent_queue_base_v3::internal_pop(), and tbb::internal::concurrent_queue_base_v3::internal_pop_if_present().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ push()

void tbb::internal::micro_queue::push ( const void item,
ticket  k,
concurrent_queue_base base,
concurrent_queue_base::copy_specifics  op_type 
)

Definition at line 165 of file concurrent_queue.cpp.

166  {
168  page* p = NULL;
169  // find index on page where we would put the data
170  size_t index = modulo_power_of_two( k/concurrent_queue_rep::n_queue, base.items_per_page );
171  if( !index ) { // make a new page
172  __TBB_TRY {
173  p = base.allocate_page();
174  } __TBB_CATCH(...) {
175  ++base.my_rep->n_invalid_entries;
176  make_invalid( k );
177  __TBB_RETHROW();
178  }
179  p->mask = 0;
180  p->next = NULL;
181  }
182 
183  // wait for my turn
184  if( tail_counter!=k ) // The developer insisted on keeping first check out of the backoff loop
185  for( atomic_backoff b(true);;b.pause() ) {
187  if( tail==k ) break;
188  else if( tail&0x1 ) {
189  // no memory. throws an exception; assumes concurrent_queue_rep::n_queue>1
190  ++base.my_rep->n_invalid_entries;
192  }
193  }
194 
195  if( p ) { // page is newly allocated; insert in micro_queue
197  if( page* q = tail_page )
198  q->next = p;
199  else
200  head_page = p;
201  tail_page = p;
202  }
203 
204  if (item) {
205  p = tail_page;
206  ITT_NOTIFY( sync_acquired, p );
207  __TBB_TRY {
208  if( concurrent_queue_base::copy == op_type ) {
209  base.copy_item( *p, index, item );
210  } else {
211  __TBB_ASSERT( concurrent_queue_base::move == op_type, NULL );
212  static_cast<concurrent_queue_base_v8&>(base).move_item( *p, index, item );
213  }
214  } __TBB_CATCH(...) {
215  ++base.my_rep->n_invalid_entries;
217  __TBB_RETHROW();
218  }
220  // If no exception was thrown, mark item as present.
221  p->mask |= uintptr_t(1)<<index;
222  }
223  else // no item; this was called from abort_push
224  ++base.my_rep->n_invalid_entries;
225 
227 }
concurrent_queue_base::page page
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
void const char const char int ITT_FORMAT __itt_group_sync p
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
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
static const size_t n_queue
Must be power of 2.
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_id __itt_string_handle __itt_metadata_type size_t void ITT_FORMAT p const __itt_domain __itt_id __itt_string_handle const wchar_t size_t ITT_FORMAT lu const __itt_domain __itt_id __itt_relation __itt_id tail
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 sync_releasing
#define ITT_NOTIFY(name, obj)
Definition: itt_notify.h:120
#define __TBB_RETHROW()
Definition: tbb_stddef.h:290

References __TBB_ASSERT, __TBB_CATCH, __TBB_RETHROW, __TBB_TRY, tbb::internal::concurrent_queue_base_v3::allocate_page(), tbb::internal::concurrent_queue_base_v3::copy, tbb::internal::concurrent_queue_base_v3::copy_item(), tbb::internal::eid_bad_last_alloc, head_page, tbb::internal::concurrent_queue_base_v3::items_per_page, ITT_NOTIFY, lock, make_invalid(), tbb::internal::modulo_power_of_two(), tbb::internal::concurrent_queue_base_v3::move, tbb::internal::concurrent_queue_base_v3::my_rep, tbb::internal::concurrent_queue_rep::n_invalid_entries, tbb::internal::concurrent_queue_rep::n_queue, p, page_mutex, tbb::internal::atomic_backoff::pause(), sync_releasing, tail, tail_counter, tail_page, and tbb::internal::throw_exception().

Referenced by abort_push(), tbb::internal::concurrent_queue_base_v3::internal_insert_if_not_full(), and tbb::internal::concurrent_queue_base_v3::internal_insert_item().

Here is the call graph for this function:
Here is the caller graph for this function:

Friends And Related Function Documentation

◆ micro_queue_pop_finalizer

friend class micro_queue_pop_finalizer
friend

Definition at line 54 of file concurrent_queue.cpp.

Member Data Documentation

◆ head_counter

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

◆ head_page

◆ page_mutex

spin_mutex tbb::internal::micro_queue::page_mutex

◆ tail_counter

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

Definition at line 60 of file concurrent_queue.cpp.

Referenced by assign(), make_invalid(), pop(), and push().

◆ tail_page


The documentation for this struct 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.