nlib
LockFree.h
Go to the documentation of this file.
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_LOCKFREE_H_
4 #define INCLUDE_NN_NLIB_LOCKFREE_H_
5 
6 #include <new>
7 #include "nn/nlib/Config.h"
8 #include "nn/nlib/TypeTraits.h"
9 #include "nn/nlib/UniquePtr.h"
11 #include "nn/nlib/Swap.h"
12 
13 NLIB_NAMESPACE_BEGIN
14 
15 template<class T1, class T2 = void>
16 struct LockFreePlaceHolder {
17  T1 data; // T1 must be POD
18  union next_type {
19  uintptr_t aba_ptr;
20  LockFreePlaceHolder<T1, T2>* raw_ptr;
21  } next;
22  T2 aux;
23  void Init(const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
24  data = elem;
25  aux = T2();
26  }
27 };
28 
29 template<class T1>
30 struct LockFreePlaceHolder<T1, void> {
31  T1 data; // T1 must be POD
32  union next_type {
33  uintptr_t aba_ptr;
34  LockFreePlaceHolder<T1, void>* raw_ptr;
35  } next;
36  void Init(const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
37  data = elem;
38  }
39 };
40 
41 template<class T1, class T2 = void>
42 class LockFreePlaceHolderPool {
43  public:
44 #if !defined(CAFE) && !defined(NN_PLATFORM_CTR)
45  // some old compilers may complain that T1 is incomplete type even if it is not.
46  NLIB_STATIC_ASSERT(IsPod<T1>::value);
47 #endif
48  LockFreePlaceHolderPool() NLIB_NOEXCEPT : invariant_(0), mask_(0), mem_(NULL) {}
49  ~LockFreePlaceHolderPool() NLIB_NOEXCEPT { delete[] mem_; }
50  errno_t Init(size_t count) NLIB_NOEXCEPT;
51  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* CalcPtr(uintptr_t aba) const NLIB_NOEXCEPT {
52  return reinterpret_cast<LockFreePlaceHolder<T1, T2>*>((aba & mask_) | invariant_);
53  }
54  NLIB_ALWAYS_INLINE bool IsNull(uintptr_t aba) const NLIB_NOEXCEPT {
55  return aba & 1;
56  }
57  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* Alloc() NLIB_NOEXCEPT NLIB_NO_TSAN {
58  LockFreePlaceHolder<T1, T2>* ptr;
59  uintptr_t expected = Load(&freelist_);
60  for (;;) {
61  if (NLIB_UNLIKELY(IsNull(expected))) return NULL;
62  ptr = this->CalcPtr(expected);
63  uintptr_t desired = Load(&ptr->next.aba_ptr);
64  if (NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1)))
65  break;
66  }
67  uintptr_t mask = mask_;
68  ptr->next.aba_ptr = (ptr->next.aba_ptr & ~mask) + (mask + 2);
69  return ptr;
70  }
71  NLIB_ALWAYS_INLINE void Free(LockFreePlaceHolder<T1, T2>* p) NLIB_NOEXCEPT NLIB_NO_TSAN {
72  uintptr_t mask = mask_;
73  uintptr_t desired = reinterpret_cast<uintptr_t>(p);
74  uintptr_t expected = Load(&freelist_);
75  uintptr_t base = (p->next.aba_ptr & ~mask) + (mask + 1);
76  for (;;) {
77  Store(&p->next.aba_ptr, base | (expected & mask));
78  // must comfirm p->next written
79  if (NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1, NLIB_ATOMIC_RELEASE)))
80  break;
81  }
82  }
83  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* AllocUnsafe() NLIB_NOEXCEPT {
84  uintptr_t expected = freelist_;
85  if (NLIB_UNLIKELY(IsNull(expected))) return NULL;
86  LockFreePlaceHolder<T1, T2>* ptr = this->CalcPtr(expected);
87  freelist_ = ptr->next.aba_ptr;
88  ptr->next.aba_ptr = 1;
89  return ptr;
90  }
91  NLIB_ALWAYS_INLINE void FreeUnsafe(LockFreePlaceHolder<T1, T2>* p) NLIB_NOEXCEPT {
92  p->next.aba_ptr = freelist_;
93  freelist_ = reinterpret_cast<uintptr_t>(p);
94  }
95  NLIB_ALWAYS_INLINE uintptr_t Load(uintptr_t* ptr) NLIB_NOEXCEPT NLIB_NO_TSAN {
96  void* val = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), NLIB_ATOMIC_RELAXED);
97  return reinterpret_cast<uintptr_t>(val);
98  }
99  NLIB_ALWAYS_INLINE uintptr_t Load(uintptr_t* ptr, int memorder) NLIB_NOEXCEPT NLIB_NO_TSAN {
100  void* val = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), memorder);
101  return reinterpret_cast<uintptr_t>(val);
102  }
103  NLIB_ALWAYS_INLINE void Store(uintptr_t* ptr, uintptr_t value) NLIB_NOEXCEPT NLIB_NO_TSAN {
104  nlib_atomic_storeptr(reinterpret_cast<void**>(ptr),
105  reinterpret_cast<void*>(value),
107  }
108  NLIB_ALWAYS_INLINE void Store(uintptr_t* ptr, uintptr_t value, int memorder)
109  NLIB_NOEXCEPT NLIB_NO_TSAN {
110  nlib_atomic_storeptr(reinterpret_cast<void**>(ptr),
111  reinterpret_cast<void*>(value),
112  memorder);
113  }
114  NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired, int weak,
115  int success_memorder, int failure_memorder)
116  NLIB_NOEXCEPT NLIB_NO_TSAN {
117  uintptr_t mask = mask_;
118  *desired = ((*desired & mask) | (mask + 1)) + (*expected & ~mask);
119  int rval = nlib_atomic_compare_exchangeptr(reinterpret_cast<void**>(ptr),
120  reinterpret_cast<void**>(expected),
121  reinterpret_cast<void*>(*desired),
122  weak, success_memorder, failure_memorder);
123  return rval;
124  }
125  NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired, int weak,
126  int success_memorder) NLIB_NOEXCEPT {
127  return Cas(ptr, expected, desired, weak, success_memorder, NLIB_ATOMIC_RELAXED);
128  }
129  NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
130  int weak) NLIB_NOEXCEPT {
131  return Cas(ptr, expected, desired, weak, NLIB_ATOMIC_RELAXED, NLIB_ATOMIC_RELAXED);
132  }
133  void SwapUnsafe(LockFreePlaceHolderPool& rhs) NLIB_NOEXCEPT { // NOLINT
134  std::swap(freelist_, rhs.freelist_);
135  std::swap(invariant_, rhs.invariant_);
136  std::swap(mask_, rhs.mask_);
137  std::swap(mem_, rhs.mem_);
138  }
139 
140  public:
141  errno_t Push(uintptr_t* stack, const T1& elem) NLIB_NOEXCEPT;
142  errno_t Pop(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT;
143  errno_t Enqueue(uintptr_t* tail, const T1& elem) NLIB_NOEXCEPT;
144  errno_t Dequeue(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT;
145  errno_t PushUnsafe(uintptr_t* stack, const T1& elem) NLIB_NOEXCEPT {
146  typedef LockFreePlaceHolder<T1, T2> item_type;
147  item_type* item_ptr = AllocUnsafe();
148  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
149 
150  // point of no failure
151  item_ptr->data = elem;
152  item_ptr->next.aba_ptr = *stack;
153  *stack = reinterpret_cast<uintptr_t>(item_ptr);
154  return 0;
155  }
156  errno_t PopUnsafe(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT {
157  if (NLIB_UNLIKELY(IsNull(*stack))) return EAGAIN;
158  LockFreePlaceHolder<T1, T2>* ptr = CalcPtr(*stack);
159  *elem = ptr->data;
160  *stack = ptr->next.aba_ptr;
161  FreeUnsafe(ptr);
162  return 0;
163  }
164  errno_t EnqueueUnsafe(uintptr_t* tail, const T1& elem) NLIB_NOEXCEPT {
165  LockFreePlaceHolder<T1, T2>* item_ptr = AllocUnsafe();
166  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
167 
168  // point of no failure
169  item_ptr->data = elem;
170  CalcPtr(*tail)->next.aba_ptr = reinterpret_cast<uintptr_t>(item_ptr);
171  *tail = reinterpret_cast<uintptr_t>(item_ptr);
172  return 0;
173  }
174  errno_t DequeueUnsafe(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT {
175  typedef LockFreePlaceHolder<T1, T2> item_type;
176  item_type* first_ptr = CalcPtr(*head);
177  item_type* last_ptr = CalcPtr(*tail);
178  if (first_ptr == last_ptr) return EAGAIN;
179 
180  uintptr_t first_next = first_ptr->next.aba_ptr;
181  item_type* first_next_ptr = CalcPtr(first_next);
182  *elem = first_next_ptr->data;
183  *head = first_next;
184  FreeUnsafe(first_ptr);
185  return 0;
186  }
187 
188  private:
189  uintptr_t freelist_;
190  uintptr_t invariant_;
191  uintptr_t mask_;
192  LockFreePlaceHolder<T1, T2>* mem_;
193  NLIB_DISALLOW_COPY_AND_ASSIGN(LockFreePlaceHolderPool);
194 };
195 
196 template<class T1, class T2>
197 errno_t LockFreePlaceHolderPool<T1, T2>::Init(size_t count) NLIB_NOEXCEPT {
198  if (NLIB_UNLIKELY(mem_)) return EALREADY;
199  LockFreePlaceHolder<T1, T2>* mem = new (std::nothrow) LockFreePlaceHolder<T1, T2>[count];
200  if (NLIB_UNLIKELY(!mem)) return ENOMEM;
201  uintptr_t freelist = 1;
202 #ifdef NLIB_64BIT
203  for (size_t j = 0; j < 4; ++j) {
204  for (size_t i = j; i < count; i += 4) {
205  mem[i].next.aba_ptr = freelist;
206  mem[i].data = T1();
207  freelist = reinterpret_cast<uintptr_t>(&mem[i]);
208  }
209  }
210 #else
211  for (size_t j = 0; j < 8; ++j) {
212  for (size_t i = j; i < count; i += 8) {
213  mem[i].next.aba_ptr = freelist;
214  mem[i].data = T1();
215  freelist = reinterpret_cast<uintptr_t>(&mem[i]);
216  }
217  }
218 #endif
219  uintptr_t first = reinterpret_cast<uintptr_t>(mem);
220  uintptr_t last = reinterpret_cast<uintptr_t>(mem + count);
221 #ifdef NLIB_64BIT
222  int sft = nlib_clz64(first ^ last);
223 #else
224  int sft = nlib_clz(first ^ last);
225 #endif
226  freelist_ = freelist;
227  mask_ = (static_cast<uintptr_t>(0) - 1) >> sft;
228  invariant_ = first & ~mask_;
229  mem_ = mem;
230  return 0;
231 }
232 
233 template<class T1, class T2>
234 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Push(
235  uintptr_t* stack, const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
236  typedef LockFreePlaceHolder<T1, T2> item_type;
237  item_type* item_ptr = Alloc();
238  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
239 
240  // point of no failure
241  item_ptr->data = elem;
242  uintptr_t mask = mask_;
243  uintptr_t desired = reinterpret_cast<uintptr_t>(item_ptr);
244  uintptr_t expected = Load(&freelist_);
245  uintptr_t base = (item_ptr->next.aba_ptr & ~mask) + (mask + 1);
246  for (;;) {
247  Store(&item_ptr->next.aba_ptr, base | (expected & mask));
248  // must comfirm p->next written
249  if (NLIB_LIKELY(Cas(stack, &expected, &desired, 1, NLIB_ATOMIC_RELEASE)))
250  break;
251  }
252  return 0;
253 }
254 
255 template<class T1, class T2>
256 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Pop(
257  uintptr_t* stack, T1* elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
258  LockFreePlaceHolder<T1, T2>* ptr;
259  uintptr_t expected = Load(stack);
260  for (;;) {
261  if (NLIB_UNLIKELY(IsNull(expected))) return EAGAIN;
262  ptr = this->CalcPtr(expected);
263  uintptr_t desired = Load(&ptr->next.aba_ptr);
264  if (NLIB_LIKELY(Cas(stack, &expected, &desired, 1)))
265  break;
266  }
267  *elem = ptr->data;
268  Free(ptr);
269  return 0;
270 }
271 
272 template<class T1, class T2>
273 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Enqueue(
274  uintptr_t* tail, const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
275  LockFreePlaceHolder<T1, T2>* item_ptr = Alloc();
276  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
277 
278  // point of no failure
279  item_ptr->Init(elem);
280 #if !defined(_M_IX86) && !defined(_M_AMD64) && !defined(__i386__) && !defined(__x86_64__)
282 #endif
283  uintptr_t last = Load(tail);
284  for (;;) {
285  uintptr_t* last_next_ptr = &CalcPtr(last)->next.aba_ptr;
286  uintptr_t last_next = Load(last_next_ptr,
287  NLIB_ATOMIC_ACQUIRE); // before last_new is loaded
288  uintptr_t last_new = Load(tail);
289  if (NLIB_LIKELY(last == last_new)) {
290  if (NLIB_LIKELY(IsNull(last_next))) {
291  if (NLIB_LIKELY(Cas(last_next_ptr, &last_next,
292  reinterpret_cast<uintptr_t*>(&item_ptr),
293  1, NLIB_ATOMIC_ACQUIRE))) {
294  // Update tail
295  Cas(tail, &last, reinterpret_cast<uintptr_t*>(&item_ptr), 0);
296  return 0;
297  }
298  } else {
299  // Update tail and retry
300  if (NLIB_LIKELY(Cas(tail, &last, &last_next, 0))) {
301  last = last_next;
302  }
303  }
304  } else {
305  last = last_new;
306  }
307  }
308 }
309 
310 template<class T1, class T2>
311 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Dequeue(
312  uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
313  typedef LockFreePlaceHolder<T1, T2> item_type;
314  // Load(head), then Load(tail)
315  uintptr_t first = Load(head, NLIB_ATOMIC_ACQUIRE);
316  uintptr_t last = Load(tail);
317  for (;;) {
318  item_type* first_ptr = CalcPtr(first);
319  item_type* last_ptr = CalcPtr(last);
320  uintptr_t first_next = Load(&first_ptr->next.aba_ptr,
321  NLIB_ATOMIC_ACQUIRE); // before first_new is loaded
322  uintptr_t first_new = Load(head);
323  if (NLIB_LIKELY(first == first_new)) {
324  if (NLIB_UNLIKELY(first_ptr == last_ptr)) {
325  if (NLIB_UNLIKELY(IsNull(first_next))) return EAGAIN;
326  // Update tail and retry
327  first = Load(head, NLIB_ATOMIC_ACQUIRE);
328  if (NLIB_LIKELY(Cas(tail, &last, &first_next, 0))) {
329  last = first_next;
330  }
331  } else {
332  item_type* first_next_ptr = CalcPtr(first_next);
333  *elem = first_next_ptr->data;
334  if (NLIB_LIKELY(Cas(head, &first, &first_next, 0))) {
335  Free(CalcPtr(first));
336  return 0;
337  }
338  first = Load(head, NLIB_ATOMIC_ACQUIRE);
339  last = Load(tail);
340  }
341  } else {
342  first = first_new;
343  last = Load(tail);
344  }
345  }
346 }
347 
348 template<size_t N>
350  public:
351  LockFreePipe() NLIB_NOEXCEPT : ofs_read_(0), ofs_write_(0) {}
352  size_t GetBufferSize() NLIB_NOEXCEPT {
353  NLIB_STATIC_ASSERT(N > 0);
354  NLIB_STATIC_ASSERT((N & (N - 1)) == 0);
355  NLIB_STATIC_ASSERT(N < INT32_MAX);
356  return N;
357  }
358  NLIB_ALWAYS_INLINE errno_t Read(void* dest, size_t nbytes) NLIB_NOEXCEPT {
359  uint32_t rofs = this->Load(&ofs_read_, NLIB_ATOMIC_RELAXED);
360  uint32_t wofs = this->Load(&ofs_write_, NLIB_ATOMIC_ACQUIRE);
361  // read ofs_write_, then read buffer_[rofs_actual]
362 
363  if (NLIB_UNLIKELY(nbytes > wofs - rofs)) return EAGAIN;
364  uint32_t rofs_actual = rofs & (N - 1);
365 
366  size_t ntail = N - rofs_actual;
367  if (ntail >= nbytes) {
368  // ARMCC needs this cast.
369  nlib_memcpy(dest,
370  nbytes,
371  reinterpret_cast<const void*>(&buffer_[rofs_actual]),
372  nbytes);
373  } else {
374  nlib_memcpy(dest,
375  nbytes,
376  reinterpret_cast<const void*>(&buffer_[rofs_actual]),
377  ntail);
378  nlib_memcpy(reinterpret_cast<void*>(reinterpret_cast<uint8_t*>(dest) + ntail),
379  nbytes - ntail,
380  reinterpret_cast<void*>(&buffer_[0]),
381  nbytes - ntail);
382  }
383  rofs += static_cast<uint32_t>(nbytes);
384 
385  // must not be reordered
386  this->Store(&ofs_read_, rofs, NLIB_ATOMIC_RELEASE);
387  return 0;
388  }
389  NLIB_ALWAYS_INLINE errno_t Write(const void* src, size_t nbytes) NLIB_NOEXCEPT {
390  uint32_t wofs = this->Load(&ofs_write_, NLIB_ATOMIC_RELAXED);
391  uint32_t rofs = this->Load(&ofs_read_, NLIB_ATOMIC_ACQUIRE);
392  // read ofs_read_, then write buffer_[wofs_actual]
393 
394  if (NLIB_UNLIKELY(nbytes > N - (wofs - rofs))) return EAGAIN;
395  uint32_t wofs_actual = wofs & (N - 1);
396 
397  size_t ntail = N - wofs_actual;
398  if (ntail >= nbytes) {
399  nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
400  nbytes,
401  src,
402  nbytes);
403  } else {
404  nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
405  ntail,
406  src,
407  ntail);
408  nlib_memcpy(reinterpret_cast<void*>(&buffer_[0]),
409  nbytes - ntail,
410  reinterpret_cast<const void*>(
411  reinterpret_cast<const uint8_t*>(src) + ntail),
412  nbytes - ntail);
413  }
414  wofs += static_cast<uint32_t>(nbytes);
415 
416  // must not be reordered
417  this->Store(&ofs_write_, wofs, NLIB_ATOMIC_RELEASE);
418  return 0;
419  }
420 
421  private:
422  NLIB_ALWAYS_INLINE uint32_t Load(uint32_t* p, int memorder) NLIB_NOEXCEPT {
423  return static_cast<uint32_t>(nlib_atomic_load32(
424  reinterpret_cast<int32_t*>(p), memorder));
425  }
426  NLIB_ALWAYS_INLINE void Store(uint32_t* p, uint32_t value, int memorder) NLIB_NOEXCEPT {
427  nlib_atomic_store32(reinterpret_cast<int32_t*>(p),
428  static_cast<int32_t>(value), memorder);
429  }
430 
431  uint32_t ofs_read_;
432  uint32_t ofs_write_;
433  uint8_t buffer_[N];
435 };
436 
437 template<class T>
439  public:
440  T* operator()() NLIB_NOEXCEPT { return new (std::nothrow) T(); }
441 };
442 
443 template<class T>
445  public:
446  void operator()(T* ptr) NLIB_NOEXCEPT { delete ptr; }
447 };
448 
449 template<class T>
451  public:
452  typedef T* PopType;
453  LockFreeStack() NLIB_NOEXCEPT : top_(0), pool_() {}
454  ~LockFreeStack() NLIB_NOEXCEPT {
455  // T is POD, and not pointer
456  }
457  // NOT thread safe
458  errno_t Init(size_t count) NLIB_NOEXCEPT {
459  errno_t e = pool_.Init(count);
460  if (NLIB_UNLIKELY(e != 0)) return e;
461  top_ = 1;
462  return 0;
463  }
464  errno_t Push(const T& x) NLIB_NOEXCEPT { return pool_.Push(&top_, x); }
465  errno_t Pop(PopType x) NLIB_NOEXCEPT { return pool_.Pop(&top_, x); }
466  // NOT thread safe
467  errno_t PushUnsafe(const T& x) NLIB_NOEXCEPT { return pool_.PushUnsafe(&top_, x); }
468  // NOT thread safe
469  errno_t PopUnsafe(PopType x) NLIB_NOEXCEPT { return pool_.PopUnsafe(&top_, x); }
470  void SwapUnsafe(LockFreeStack& rhs) NLIB_NOEXCEPT { // NOLINT
471  std::swap(top_, rhs.top_);
472  pool_.SwapUnsafe(rhs.pool_);
473  }
474 
475  private:
476  uintptr_t top_;
477  LockFreePlaceHolderPool<T> pool_;
478 };
479 
480 template<class T>
481 class LockFreeStack<T*> {
482  public:
484  LockFreeStack() NLIB_NOEXCEPT : top_(0), pool_() {}
485  ~LockFreeStack() NLIB_NOEXCEPT {
486  if (top_ != 0) {
487  T* elem;
488  while (0 == pool_.PopUnsafe(&top_, &elem)) {
489  DestructorForLockFree<T>()(elem);
490  }
491  }
492  }
493  // NOT thread safe
494  errno_t Init(size_t count) NLIB_NOEXCEPT {
495  errno_t e = pool_.Init(count);
496  if (NLIB_UNLIKELY(e != 0)) return e;
497  top_ = 1;
498  return 0;
499  }
500  errno_t Push(T* obj) NLIB_NOEXCEPT { return pool_.Push(&top_, obj); }
501  errno_t Pop(PopType& obj) NLIB_NOEXCEPT { // NOLINT
502  T* x;
503  errno_t e = pool_.Pop(&top_, &x);
504  if (e != 0) return e;
505  obj.reset(x);
506  return 0;
507  }
508  // NOT thread safe
509  errno_t PushUnsafe(T* obj) NLIB_NOEXCEPT { return pool_.PushUnsafe(&top_, obj); }
510  // NOT thread safe
511  errno_t PopUnsafe(PopType& obj) NLIB_NOEXCEPT { // NOLINT
512  T* x;
513  errno_t e = pool_.PopUnsafe(&top_, &x);
514  if (e != 0) return e;
515  obj.reset(x);
516  return 0;
517  }
518  void SwapUnsafe(LockFreeStack& rhs) NLIB_NOEXCEPT { // NOLINT
519  std::swap(top_, rhs.top_);
520  pool_.SwapUnsafe(rhs.pool_);
521  }
522 
523  private:
524  uintptr_t top_;
525  LockFreePlaceHolderPool<T*> pool_;
526 };
527 
528 template<class T>
530  public:
531  typedef T* DequeueType;
532  LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
533  ~LockFreeQueue() NLIB_NOEXCEPT {
534  // T is POD, and not pointer
535  }
536  // NOT thread safe
537  errno_t Init(size_t count) NLIB_NOEXCEPT {
538  errno_t e = pool_.Init(count + 1);
539  if (NLIB_UNLIKELY(e != 0)) return e;
540  head_ = tail_ = reinterpret_cast<uintptr_t>(pool_.AllocUnsafe());
541  return 0;
542  }
543  errno_t Enqueue(const T& x) NLIB_NOEXCEPT { return pool_.Enqueue(&tail_, x); }
544  errno_t Dequeue(DequeueType x) NLIB_NOEXCEPT { return pool_.Dequeue(&head_, &tail_, x); }
545  // NOT thread safe
546  errno_t EnqueueUnsafe(const T& x) NLIB_NOEXCEPT { return pool_.EnqueueUnsafe(&tail_, x); }
547  // NOT thread safe
548  errno_t DequeueUnsafe(DequeueType x) NLIB_NOEXCEPT {
549  return pool_.DequeueUnsafe(&head_, &tail_, x);
550  }
551  void SwapUnsafe(LockFreeQueue& rhs) NLIB_NOEXCEPT { // NOLINT
552  std::swap(head_, rhs.head_);
553  std::swap(tail_, rhs.tail_);
554  pool_.SwapUnsafe(rhs.pool_);
555  }
556 
557  private:
558  uintptr_t head_;
559  uintptr_t tail_;
560  LockFreePlaceHolderPool<T> pool_;
561 };
562 
563 template<class T>
564 class LockFreeQueue<T*> {
565  public:
567  LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
568  ~LockFreeQueue() NLIB_NOEXCEPT {
569  if (head_ != 0) {
570  T* elem;
571  while (0 == pool_.DequeueUnsafe(&head_, &tail_, &elem)) {
572  DestructorForLockFree<T>()(elem);
573  }
574  }
575  }
576  // NOT thread safe
577  errno_t Init(size_t count) NLIB_NOEXCEPT {
578  errno_t e = pool_.Init(count + 1);
579  if (NLIB_UNLIKELY(e != 0)) return e;
580  head_ = tail_ = reinterpret_cast<uintptr_t>(pool_.AllocUnsafe());
581  return 0;
582  }
583  errno_t Enqueue(T* obj) NLIB_NOEXCEPT { return pool_.Enqueue(&tail_, obj); }
584  errno_t Dequeue(DequeueType& obj) NLIB_NOEXCEPT { // NOLINT
585  T* x;
586  errno_t e = pool_.Dequeue(&head_, &tail_, &x);
587  if (e != 0) return e;
588  obj.reset(x);
589  return 0;
590  }
591  // NOT thread safe
592  errno_t EnqueueUnsafe(T* x) NLIB_NOEXCEPT { return pool_.EnqueueUnsafe(&tail_, x); }
593  // NOT thread safe
594  errno_t DequeueUnsafe(DequeueType& obj) NLIB_NOEXCEPT { // NOLINT
595  T* x;
596  errno_t e = pool_.DequeueUnsafe(&head_, &tail_, &x);
597  if (e != 0) return e;
598  obj.reset(x);
599  return 0;
600  }
601  void SwapUnsafe(LockFreeQueue& rhs) NLIB_NOEXCEPT { // NOLINT
602  std::swap(head_, rhs.head_);
603  std::swap(tail_, rhs.tail_);
604  pool_.SwapUnsafe(rhs.pool_);
605  }
606 
607  private:
608  uintptr_t head_;
609  uintptr_t tail_;
610  LockFreePlaceHolderPool<T*> pool_;
611 };
612 
613 template<class T>
614 errno_t LockFreeInit(T** ptr) NLIB_NOEXCEPT NLIB_NONNULL;
615 
616 template<class T>
617 inline errno_t LockFreeInit(T** ptr) NLIB_NOEXCEPT {
618  NLIB_EINVAL_IFNULL(ptr);
619  void* pold = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), NLIB_ATOMIC_RELAXED);
620  if (pold) return 0;
621  T* obj = ConstructorForLockFree<T>()();
622  if (!obj) {
623  pold = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), NLIB_ATOMIC_RELAXED);
624  return pold ? 0 : EAGAIN;
625  }
626  if (nlib_atomic_compare_exchangeptr(reinterpret_cast<void**>(ptr),
627  &pold, reinterpret_cast<void*>(obj), 0,
629  return 0;
630  } else {
632  return 0;
633  }
634 }
635 
636 template<class T>
638  public:
640  LockFreePriorityQueue() NLIB_NOEXCEPT : mq_() {
641  mq_.raw_handle = 0;
642  }
643  ~LockFreePriorityQueue() NLIB_NOEXCEPT {
644  if (mq_.raw_handle != 0) (void)nlib_mq_close(mq_);
645  }
646  // NOT thread safe
647  errno_t Init(size_t max_size) NLIB_NOEXCEPT {
648  // not thread safe
649  if (mq_.raw_handle != 0) return EALREADY;
650  if (max_size > INT32_MAX) return EINVAL;
651  nlib_mq_attr attr;
652  attr.flag = NLIB_MQ_LOCKFREE;
653  attr.max_msg = static_cast<int32_t>(max_size);
654  attr.destructor = LockFreePriorityQueue::dtor;
655  return nlib_mq_open(&mq_, &attr);
656  }
657  // NOT thread safe
658  errno_t Close() NLIB_NOEXCEPT {
659  // not thread safe
660  nlib_mq mq = mq_;
661  mq_.raw_handle = 0;
662  return nlib_mq_close(mq);
663  }
664  errno_t Enqueue(T* obj, int prio) NLIB_NOEXCEPT {
665  // thread safe
666  return nlib_mq_send(mq_, obj, prio);
667  }
668  errno_t Dequeue(DequeueType& obj, int* prio) NLIB_NOEXCEPT { // NOLINT
669  // thread safe
670  T* x;
671  errno_t e = nlib_mq_receive(mq_, reinterpret_cast<nlib_mq_msg*>(&x), prio);
672  if (e != 0) return e;
673  obj.reset(x);
674  return 0;
675  }
676  void SwapUnsafe(LockFreePriorityQueue& rhs) NLIB_NOEXCEPT { // NOLINT
677  nlib_mq mq = rhs.mq_;
678  rhs.mq_ = mq_;
679  mq_ = mq;
680  }
681 
682  private:
683  static void dtor(nlib_mq_msg msg) {
684  T* obj = reinterpret_cast<T*>(msg);
686  }
687 
688  nlib_mq mq_;
689 };
690 
691 namespace detail {
692 
693 class LockFreeBroadcastQueueImpl {
694  typedef LockFreePlaceHolder<const void*, int32_t> item_type;
695 
696  public:
697  LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT
698  : head_(1), tail_(1), listener_count_(0), pool_(), listeners_() {}
699  NLIB_VIS_PUBLIC ~LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT;
700  NLIB_VIS_PUBLIC errno_t Init(size_t max_size, size_t listeners) NLIB_NOEXCEPT;
701  errno_t Enqueue(const void* msg) NLIB_NOEXCEPT {
702  // thread safe
703  return pool_.Enqueue(&tail_, msg);
704  }
705  errno_t Dequeue(int32_t listener_id, const void** msg) NLIB_NOEXCEPT {
706  // thread safe if listener_id is different
707  if (NLIB_UNLIKELY(listener_id < 0) ||
708  NLIB_UNLIKELY(listener_id >= listener_count_)) return ERANGE;
709  uintptr_t& pos = listeners_[listener_id];
710  item_type* item = pool_.CalcPtr(pos);
711  uintptr_t next = item->next.aba_ptr;
712  if (pool_.IsNull(next)) return ENOENT;
713  *msg = pool_.CalcPtr(next)->data;
714  pos = next;
716  return 0;
717  }
718  NLIB_VIS_PUBLIC const void* CheckAndRemove() NLIB_NOEXCEPT;
719  errno_t DeleteUnsafe(const void** msg) NLIB_NOEXCEPT {
720  if (pool_.IsNull(head_)) return ENOENT;
721  item_type* item = pool_.CalcPtr(head_);
722  const void* p = item->data;
723  head_ = item->next.aba_ptr;
724  *msg = p;
725  return 0;
726  }
727  size_t GetListenerCount() const NLIB_NOEXCEPT { return listener_count_; }
728  void SwapUnsafe(LockFreeBroadcastQueueImpl& rhs) NLIB_NOEXCEPT { // NOLINT
729  std::swap(head_, rhs.head_);
730  std::swap(tail_, rhs.tail_);
731  std::swap(listener_count_, rhs.listener_count_);
732  pool_.SwapUnsafe(rhs.pool_);
733  listeners_.swap(rhs.listeners_);
734  }
735 
736  private:
737  uintptr_t Load(uintptr_t* p, int memorder = NLIB_ATOMIC_RELAXED) NLIB_NOEXCEPT {
738  return reinterpret_cast<uintptr_t>(nlib_atomic_loadptr(reinterpret_cast<void**>(p),
739  memorder));
740  }
741 
742  private:
743  uintptr_t head_;
744  uintptr_t tail_;
745  int32_t listener_count_;
746  LockFreePlaceHolderPool<const void*, int32_t> pool_;
747  UniquePtr<uintptr_t[]> listeners_;
748 };
749 
750 } // namespace detail
751 
752 template<class T>
754  public:
755  struct empty_func {
756  void operator()(const T*) {}
757  };
759  LockFreeBroadcastQueue() NLIB_NOEXCEPT : impl_() {}
760  ~LockFreeBroadcastQueue() NLIB_NOEXCEPT {
761  const void* p;
762  while (impl_.DeleteUnsafe(&p) == 0) {
763  DestructorForLockFree<const T>()(reinterpret_cast<const T*>(p));
764  }
765  }
766  // NOT thread safe
767  errno_t Init(size_t max_size, size_t listeners) NLIB_NOEXCEPT {
768  // not thread safe
769  return impl_.Init(max_size, listeners);
770  }
771  errno_t Enqueue(const T* obj) NLIB_NOEXCEPT {
772  // thread safe
773  return impl_.Enqueue(obj);
774  }
775  errno_t Dequeue(int32_t listener_id, DequeueType& obj) NLIB_NOEXCEPT { // NOLINT
776  // thread safe if listener_id is different
777  const void* x;
778  errno_t e = impl_.Dequeue(listener_id, &x);
779  if (e != 0) return e;
780  obj.reset(reinterpret_cast<const T*>(x));
781  const T* p = reinterpret_cast<const T*>(impl_.CheckAndRemove());
782  if (p) {
784  }
785  return 0;
786  }
787  size_t GetListenerCount() const NLIB_NOEXCEPT {
788  // thread safe
789  return impl_.GetListenerCount();
790  }
791  void SwapUnsafe(LockFreeBroadcastQueue& rhs) NLIB_NOEXCEPT { // NOLINT
792  impl_.SwapUnsafe(rhs);
793  }
794 
795  private:
796  detail::LockFreeBroadcastQueueImpl impl_;
797 };
798 
800  public:
801  class MemHolder {
802  public:
803  void* Get() NLIB_NOEXCEPT { return ptr_; }
804 
805  private:
806  void* const ptr_;
808  };
809  LockFreeUnitHeap() NLIB_NOEXCEPT : mem_(), pool_() {}
810  // NOT thread safe
811  NLIB_VIS_PUBLIC errno_t Init(size_t unit_size, size_t align,
812  size_t count) NLIB_NOEXCEPT;
814 
815  // MemHolder* x = heap.Alloc();
816  // void* ptr = x->Get(); // 'ptr' is what you want.
817  NLIB_ALWAYS_INLINE MemHolder* Alloc() NLIB_NOEXCEPT {
818  return reinterpret_cast<MemHolder*>(pool_.Alloc());
819  }
820 
821  NLIB_ALWAYS_INLINE void Free(MemHolder* p) NLIB_NOEXCEPT {
822  pool_.Free(reinterpret_cast<LockFreePlaceHolder<void*>*>(p));
823  }
824 
825  // NOT thread safe
826  // MemHolder* x = heap.Alloc();
827  // void* ptr = x->Get(); // 'ptr' is what you want.
828  NLIB_ALWAYS_INLINE MemHolder* AllocUnsafe() NLIB_NOEXCEPT {
829  return reinterpret_cast<MemHolder*>(pool_.AllocUnsafe());
830  }
831  // NOT thread safe
832  NLIB_ALWAYS_INLINE void FreeUnsafe(MemHolder* p) NLIB_NOEXCEPT {
833  pool_.FreeUnsafe(reinterpret_cast<LockFreePlaceHolder<void*>*>(p));
834  }
835  void SwapUnsafe(LockFreeUnitHeap& rhs) NLIB_NOEXCEPT { // NOLINT
836  mem_.swap(rhs.mem_);
837  pool_.SwapUnsafe(rhs.pool_);
838  }
839 
840  private:
842  LockFreePlaceHolderPool<void*> pool_;
844 };
845 
846 NLIB_NAMESPACE_END
847 
848 #endif // INCLUDE_NN_NLIB_LOCKFREE_H_
void FreeUnsafe(MemHolder *p) noexcept
This function is similar to Free(), but not thread-safe.
Definition: LockFree.h:832
errno_t PopUnsafe(PopType x) noexcept
Picks up an element from the stack and stores it in x. This is not thread-safe.
Definition: LockFree.h:469
LockFreePipe() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:351
int nlib_atomic_compare_exchangeptr(void **ptr, void **expected, void *desired, int weak, int success_memorder, int failure_memorder)
Compares and swaps atomic values. Its behavior is similar to the one for __atomic_compare_exchange_n(...
int32_t nlib_atomic_load32(const int32_t *ptr, int memorder)
Loads a value in an atomic operation. Its behavior is similar to the one for __atomic_load_n() of gcc...
#define NLIB_ALWAYS_INLINE
Indicates that the compiler is forced to perform inline expansion of functions.
Definition: Platform_unix.h:69
LockFreeQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:532
Substitute definitions for the C++11 standard header type_traits. These substitute definitions are us...
UniquePtr< const T, empty_func > DequeueType
The type for the argument of Dequeue().
Definition: LockFree.h:758
nlib_mq_msg_destructor destructor
A destructor function for a message taken from a message queue can be set or obtained.
Definition: Platform.h:1400
errno_t nlib_mq_close(nlib_mq mq)
Closes the message queue indicated with a handle.
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:145
NLIB_CHECK_RESULT errno_t nlib_mq_receive(nlib_mq mq, nlib_mq_msg *msg, int *prio)
Receives a message from a queue. It is the user&#39;s responsibility to delete the received messages usin...
errno_t Init(size_t count) noexcept
Initializes the stack. This is not thread-safe.
Definition: LockFree.h:458
T * PopType
The type for the argument of Pop() and PopUnsafe().
Definition: LockFree.h:452
#define NLIB_ATOMIC_RELEASE
Similar to __ATOMIC_RELEASE of gcc or std::memory_order_release of C++11.
LockFreeStack() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:453
~LockFreeQueue() noexcept
Destructor.
Definition: LockFree.h:533
#define NLIB_UNLIKELY(x)
Indicates to the compiler that condition x is likely to be false.
Definition: Platform_unix.h:72
A class for obtaining aligned memory.
errno_t DequeueUnsafe(DequeueType x) noexcept
Picks up an element from the queue and stores it in x. This is not thread-safe.
Definition: LockFree.h:548
size_t GetBufferSize() noexcept
Returns the buffer size. This is thread-safe.
Definition: LockFree.h:352
UniquePtr owns the pointer, and when it goes out of scope, the pointer is released by the destructor ...
Definition: UniquePtr.h:96
errno_t PushUnsafe(const T &x) noexcept
Places the element x in the stack. This is not thread-safe.
Definition: LockFree.h:467
Defines that class that is corresponding to std::unique_ptr.
NLIB_CHECK_RESULT errno_t nlib_mq_open(nlib_mq *mq, const nlib_mq_attr *attr)
Creates a message queue to be used to exchange messages across threads.
errno_t Pop(PopType x) noexcept
Picks up an element from the stack and stores it in x. This is thread-safe.
Definition: LockFree.h:465
errno_t LockFreeInit(T **ptr) noexcept
Constructs an object in a thread safe manner.
Definition: LockFree.h:617
void SwapUnsafe(LockFreePriorityQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:676
errno_t EnqueueUnsafe(const T &x) noexcept
Adds the element x to the queue. This is not thread-safe.
Definition: LockFree.h:546
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:61
A pool allocator that can allocate or free a fixed size of memory region in a lock free manner...
Definition: LockFree.h:799
int32_t max_msg
When creating a message queue, you can set the maximum number of messages.
Definition: Platform.h:1398
The specified number of listeners can obtain elements from the queue. After all the listeners have ob...
Definition: LockFree.h:753
#define NLIB_ATOMIC_ACQUIRE
Similar to __ATOMIC_ACQUIRE of gcc or std::memory_order_acquire of C++11.
MemHolder * AllocUnsafe() noexcept
This function is similar to Alloc(), but not thread-safe.
Definition: LockFree.h:828
errno_t Read(void *dest, size_t nbytes) noexcept
Reads data from a pipe. This is thread-safe.
Definition: LockFree.h:358
int32_t nlib_mq
Handle associated with a message queue. If the handle is cleared to zero (using memset()), it will always be an invalid handle.
Definition: Platform.h:1382
void * nlib_atomic_loadptr(void *const *ptr, int memorder)
Loads a value in an atomic operation. Its behavior is similar to the one for __atomic_load_n() of gcc...
void SwapUnsafe(LockFreeStack &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:470
errno_t Enqueue(T *obj, int prio) noexcept
Adds an element to the queue. This is thread-safe.
Definition: LockFree.h:664
errno_t Enqueue(const T &x) noexcept
Adds the element x to the queue. This is thread-safe.
Definition: LockFree.h:543
UniquePtr< T, DestructorForLockFree< T > > DequeueType
The type for the argument of Dequeue().
Definition: LockFree.h:639
errno_t Write(const void *src, size_t nbytes) noexcept
Writes data to a pipe. This is thread-safe.
Definition: LockFree.h:389
#define NLIB_LIKELY(x)
Indicates to the compiler that condition x is likely to be true.
Definition: Platform_unix.h:71
T * DequeueType
The type for the argument of Dequeue() and DequeueUnsafe().
Definition: LockFree.h:531
static errno_t nlib_memcpy(void *s1, size_t s1max, const void *s2, size_t n)
An implementation corresponding to N1078 memcpy_s.
Definition: Platform.h:3170
int32_t nlib_atomic_add_fetch32(int32_t *ptr, int32_t val, int memorder)
Adds atomic values. Its behavior is similar to the one for __atomic_add_fetch() of gcc...
This class implements a lock-free stack.
Definition: LockFree.h:450
void nlib_atomic_storeptr(void **ptr, void *val, int memorder)
Stores a value in an atomic operation. Its behavior is similar to the one for __atomic_store_n() of g...
size_t GetListenerCount() const noexcept
Returns the number of listeners specified in Init(). This is thread-safe.
Definition: LockFree.h:787
Class template for destructing an object. This should be specialized before use.
Definition: LockFree.h:444
void SwapUnsafe(LockFreeQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:551
void nlib_atomic_thread_fence(int memorder)
Places the specified memory barrier.
MemHolder * Alloc() noexcept
Allocates memory. This is thread-safe.
Definition: LockFree.h:817
void SwapUnsafe(LockFreeUnitHeap &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:835
Structure to store the settings and current status of a message queue.
Definition: Platform.h:1396
This class implements a lock-free queue.
Definition: LockFree.h:529
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:86
void SwapUnsafe(LockFreeBroadcastQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:791
errno_t Dequeue(DequeueType &obj, int *prio) noexcept
Picks up an element from the queue. This is thread-safe.
Definition: LockFree.h:668
A file that contains the configuration information for each development environment.
errno_t Close() noexcept
Closes the queue and restores it to the state before its initialization. This is not thread-safe...
Definition: LockFree.h:658
errno_t Init(size_t count) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:537
errno_t Dequeue(DequeueType x) noexcept
Picks up an element from the queue and stores it in x. This is thread-safe.
Definition: LockFree.h:544
Used when aligned memory needs to be obtained.
errno_t Push(const T &x) noexcept
Places the element x in the stack. This is thread-safe.
Definition: LockFree.h:464
NLIB_CHECK_RESULT errno_t nlib_mq_send(nlib_mq mq, nlib_mq_msg msg, int prio)
Sends a message to a queue.
#define NLIB_ATOMIC_RELAXED
Similar to __ATOMIC_RELAXED of gcc or std::memory_order_relaxed of C++11.
LockFreeUnitHeap() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:809
errno_t Init(size_t max_size, size_t listeners) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:767
When a single sender thread sends data and a single receiver thread receives that data...
Definition: LockFree.h:349
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:211
errno_t Init(size_t max_size) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:647
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
Definition: Config.h:136
LockFreeBroadcastQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:759
Class template for initializing an object. This should be specialized before use. ...
Definition: LockFree.h:438
~LockFreeStack() noexcept
Destructor.
Definition: LockFree.h:454
~LockFreeBroadcastQueue() noexcept
Destructor.
Definition: LockFree.h:760
errno_t Dequeue(int32_t listener_id, DequeueType &obj) noexcept
Specifies the listener and then reads an element from the queue. This is thread-safe when using a dif...
Definition: LockFree.h:775
void Free(MemHolder *p) noexcept
Frees memory. This is thread-safe.
Definition: LockFree.h:821
LockFreePriorityQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:640
#define NLIB_NONNULL
Indicates that you cannot specify NULL for all arguments.
Definition: Platform_unix.h:76
void nlib_atomic_store32(int32_t *ptr, int32_t val, int memorder)
Stores a value in an atomic operation. Its behavior is similar to the one for __atomic_store_n() of g...
int32_t flag
Settings to be used when creating a message queue. Value Description NLIB_MQ_BLOCK When reading an e...
Definition: Platform.h:1397
Wraps nlib_mq with a class implementing a lock-free queue with a priority set.
Definition: LockFree.h:637
~LockFreePriorityQueue() noexcept
Destructor.
Definition: LockFree.h:643
void * nlib_mq_msg
Type of messages stored in a message queue.
Definition: Platform.h:1388
static int nlib_clz64(uint64_t x)
Returns the number of consecutive zero bits, with respect to the most significant bit (MSB)...
Definition: Platform.h:3351
errno_t Enqueue(const T *obj) noexcept
Adds an element to the queue. This is thread-safe.
Definition: LockFree.h:771
int errno_t
Indicates with an int-type typedef that a POSIX error value is returned as the return value...
Definition: NMalloc.h:24