3 #ifndef INCLUDE_NN_NLIB_LOCKFREE_H_
4 #define INCLUDE_NN_NLIB_LOCKFREE_H_
14 template<
class T1,
class T2 =
void>
15 struct LockFreePlaceHolder {
19 LockFreePlaceHolder<T1, T2>* raw_ptr;
29 struct LockFreePlaceHolder<T1, void> {
33 LockFreePlaceHolder<T1, void>* raw_ptr;
40 template<
class T1,
class T2 =
void>
41 class LockFreePlaceHolderPool {
44 LockFreePlaceHolderPool()
NLIB_NOEXCEPT : invariant_(0), mask_(0), mem_(NULL) {}
47 NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* CalcPtr(uintptr_t aba)
const NLIB_NOEXCEPT {
48 return reinterpret_cast<LockFreePlaceHolder<T1, T2>*
>((aba & mask_) | invariant_);
54 LockFreePlaceHolder<T1, T2>* ptr;
55 uintptr_t expected = Load(&freelist_);
58 ptr = this->CalcPtr(expected);
59 uintptr_t desired = Load(&ptr->next.aba_ptr);
60 if (
NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1)))
63 uintptr_t mask = mask_;
64 ptr->next.aba_ptr = (ptr->next.aba_ptr & ~mask) + (mask + 2);
68 uintptr_t mask = mask_;
69 uintptr_t desired =
reinterpret_cast<uintptr_t
>(p);
70 uintptr_t expected = Load(&freelist_);
71 uintptr_t base = (p->next.aba_ptr & ~mask) + (mask + 1);
73 Store(&p->next.aba_ptr, base | (expected & mask));
80 uintptr_t expected = freelist_;
82 LockFreePlaceHolder<T1, T2>* ptr = this->CalcPtr(expected);
83 freelist_ = ptr->next.aba_ptr;
84 ptr->next.aba_ptr = 1;
88 p->next.aba_ptr = freelist_;
89 freelist_ =
reinterpret_cast<uintptr_t
>(p);
93 return reinterpret_cast<uintptr_t
>(val);
97 return reinterpret_cast<uintptr_t
>(val);
101 reinterpret_cast<void*>(value),
106 reinterpret_cast<void*>(value),
109 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
111 uintptr_t mask = mask_;
112 *desired = ((*desired & mask) | (mask + 1)) + (*expected & ~mask);
114 reinterpret_cast<void**>(expected),
115 reinterpret_cast<void*>(*desired),
116 weak, success_memorder, failure_memorder);
119 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
127 void SwapUnsafe(LockFreePlaceHolderPool& rhs)
NLIB_NOEXCEPT {
128 uintptr_t freelist = rhs.freelist_;
129 uintptr_t invariant = rhs.invariant_;
130 uintptr_t mask = rhs.mask_;
131 LockFreePlaceHolder<T1, T2>* mem = rhs.mem_;
132 rhs.freelist_ = freelist_;
133 rhs.invariant_ = invariant_;
136 freelist_ = freelist;
137 invariant_ = invariant;
147 errno_t PushUnsafe(uintptr_t* stack,
const T1& elem) NLIB_NOEXCEPT {
148 typedef LockFreePlaceHolder<T1, T2> item_type;
149 item_type* item_ptr = AllocUnsafe();
153 item_ptr->data = elem;
154 item_ptr->next.aba_ptr = *stack;
155 *stack =
reinterpret_cast<uintptr_t
>(item_ptr);
158 errno_t PopUnsafe(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT {
160 LockFreePlaceHolder<T1, T2>* ptr = CalcPtr(*stack);
162 *stack = ptr->next.aba_ptr;
166 errno_t EnqueueUnsafe(uintptr_t* tail,
const T1& elem) NLIB_NOEXCEPT {
167 LockFreePlaceHolder<T1, T2>* item_ptr = AllocUnsafe();
171 item_ptr->data = elem;
172 CalcPtr(*tail)->next.aba_ptr = reinterpret_cast<uintptr_t>(item_ptr);
173 *tail =
reinterpret_cast<uintptr_t
>(item_ptr);
176 errno_t DequeueUnsafe(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT {
177 typedef LockFreePlaceHolder<T1, T2> item_type;
178 item_type* first_ptr = CalcPtr(*head);
179 item_type* last_ptr = CalcPtr(*tail);
180 if (first_ptr == last_ptr)
return EAGAIN;
182 uintptr_t first_next = first_ptr->next.aba_ptr;
183 item_type* first_next_ptr = CalcPtr(first_next);
184 *elem = first_next_ptr->data;
186 FreeUnsafe(first_ptr);
192 uintptr_t invariant_;
194 LockFreePlaceHolder<T1, T2>* mem_;
198 template<
class T1,
class T2>
199 errno_t LockFreePlaceHolderPool<T1, T2>::Init(
size_t count) NLIB_NOEXCEPT {
201 LockFreePlaceHolder<T1, T2>* mem =
new (std::nothrow) LockFreePlaceHolder<T1, T2>[count];
203 uintptr_t freelist = 1;
205 for (
size_t j = 0; j < 4; ++j) {
206 for (
size_t i = j; i < count; i += 4) {
207 mem[i].next.aba_ptr = freelist;
209 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
213 for (
size_t j = 0; j < 8; ++j) {
214 for (
size_t i = j; i < count; i += 8) {
215 mem[i].next.aba_ptr = freelist;
217 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
221 uintptr_t first =
reinterpret_cast<uintptr_t
>(mem);
222 uintptr_t last =
reinterpret_cast<uintptr_t
>(mem + count);
228 freelist_ = freelist;
229 mask_ = (
static_cast<uintptr_t
>(0) - 1) >> sft;
230 invariant_ = first & ~mask_;
235 template<
class T1,
class T2>
237 const T1& elem) NLIB_NOEXCEPT {
238 typedef LockFreePlaceHolder<T1, T2> item_type;
239 item_type* item_ptr = Alloc();
243 item_ptr->data = elem;
244 uintptr_t mask = mask_;
245 uintptr_t desired =
reinterpret_cast<uintptr_t
>(item_ptr);
246 uintptr_t expected = Load(&freelist_);
247 uintptr_t base = (item_ptr->next.aba_ptr & ~mask) + (mask + 1);
249 Store(&item_ptr->next.aba_ptr, base | (expected & mask));
257 template<
class T1,
class T2>
259 T1* elem) NLIB_NOEXCEPT {
260 LockFreePlaceHolder<T1, T2>* ptr;
261 uintptr_t expected = Load(stack);
264 ptr = this->CalcPtr(expected);
265 uintptr_t desired = Load(&ptr->next.aba_ptr);
266 if (
NLIB_LIKELY(Cas(stack, &expected, &desired, 1)))
274 template<
class T1,
class T2>
276 const T1& elem) NLIB_NOEXCEPT {
277 LockFreePlaceHolder<T1, T2>* item_ptr = Alloc();
281 item_ptr->Init(elem);
282 #if !defined(_M_IX86) && !defined(_M_AMD64) && !defined(__i386__) && !defined(__x86_64__)
285 uintptr_t last = Load(tail);
287 uintptr_t* last_next_ptr = &CalcPtr(last)->next.aba_ptr;
288 uintptr_t last_next = Load(last_next_ptr,
290 uintptr_t last_new = Load(tail);
294 reinterpret_cast<uintptr_t*>(&item_ptr),
297 Cas(tail, &last, reinterpret_cast<uintptr_t*>(&item_ptr), 0);
302 if (
NLIB_LIKELY(Cas(tail, &last, &last_next, 0))) {
312 template<
class T1,
class T2>
315 T1* elem) NLIB_NOEXCEPT {
316 typedef LockFreePlaceHolder<T1, T2> item_type;
319 uintptr_t last = Load(tail);
321 item_type* first_ptr = CalcPtr(first);
322 item_type* last_ptr = CalcPtr(last);
323 uintptr_t first_next = Load(&first_ptr->next.aba_ptr,
325 uintptr_t first_new = Load(head);
331 if (
NLIB_LIKELY(Cas(tail, &last, &first_next, 0))) {
335 item_type* first_next_ptr = CalcPtr(first_next);
336 *elem = first_next_ptr->data;
337 if (
NLIB_LIKELY(Cas(head, &first, &first_next, 0))) {
338 Free(CalcPtr(first));
367 uint32_t rofs_actual = rofs & (N - 1);
369 size_t ntail = N - rofs_actual;
370 if (ntail >= nbytes) {
374 reinterpret_cast<const void*>(&buffer_[rofs_actual]),
379 reinterpret_cast<const void*>(&buffer_[rofs_actual]),
381 nlib_memcpy(reinterpret_cast<void*>(reinterpret_cast<uint8_t*>(dest) + ntail),
383 reinterpret_cast<void*>(&buffer_[0]),
386 rofs +=
static_cast<uint32_t
>(nbytes);
397 if (
NLIB_UNLIKELY(nbytes > N - (wofs - rofs)))
return EAGAIN;
398 uint32_t wofs_actual = wofs & (N - 1);
400 size_t ntail = N - wofs_actual;
401 if (ntail >= nbytes) {
402 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
407 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
413 reinterpret_cast<const void*>(
414 reinterpret_cast<const uint8_t*>(src) + ntail),
417 wofs +=
static_cast<uint32_t
>(nbytes);
427 reinterpret_cast<int32_t*>(p), memorder));
429 NLIB_ALWAYS_INLINE void Store(uint32_t* p, uint32_t value,
int memorder) NLIB_NOEXCEPT {
431 static_cast<int32_t>(value), memorder);
443 T* operator()() NLIB_NOEXCEPT {
return new (std::nothrow) T(); }
449 void operator()(T* ptr) NLIB_NOEXCEPT {
delete ptr; }
467 errno_t Push(
const T& x) NLIB_NOEXCEPT {
return pool_.Push(&top_, x); }
468 errno_t Pop(PopType x) NLIB_NOEXCEPT {
return pool_.Pop(&top_, x); }
476 LockFreePlaceHolderPool<T> pool_;
480 class LockFreeStack<T*> {
482 typedef UniquePtr<T, DestructorForLockFree<T> > PopType;
483 LockFreeStack() NLIB_NOEXCEPT : top_(0), pool_() {}
484 ~LockFreeStack() NLIB_NOEXCEPT {
487 while (0 == pool_.PopUnsafe(&top_, &elem)) {
488 DestructorForLockFree<T>()(elem);
493 errno_t Init(
size_t count) NLIB_NOEXCEPT {
499 errno_t Push(T* obj) NLIB_NOEXCEPT {
return pool_.Push(&top_, obj); }
500 errno_t Pop(PopType& obj) NLIB_NOEXCEPT {
502 errno_t e = pool_.Pop(&top_, &x);
503 if (e != 0)
return e;
508 errno_t PushUnsafe(T* obj) NLIB_NOEXCEPT {
return pool_.PushUnsafe(&top_, obj); }
510 errno_t PopUnsafe(PopType& obj) NLIB_NOEXCEPT {
512 errno_t e = pool_.PopUnsafe(&top_, &x);
513 if (e != 0)
return e;
520 LockFreePlaceHolderPool<T*> pool_;
533 errno_t e = pool_.Init(count + 1);
535 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
539 errno_t Dequeue(DequeueType x) NLIB_NOEXCEPT {
return pool_.Dequeue(&head_, &tail_, x); }
544 return pool_.DequeueUnsafe(&head_, &tail_, x);
550 LockFreePlaceHolderPool<T> pool_;
554 class LockFreeQueue<T*> {
556 typedef UniquePtr<T, DestructorForLockFree<T> > DequeueType;
557 LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
558 ~LockFreeQueue() NLIB_NOEXCEPT {
561 while (0 == pool_.DequeueUnsafe(&head_, &tail_, &elem)) {
562 DestructorForLockFree<T>()(elem);
567 errno_t Init(
size_t count) NLIB_NOEXCEPT {
568 errno_t e = pool_.Init(count + 1);
570 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
573 errno_t Enqueue(T* obj) NLIB_NOEXCEPT {
return pool_.Enqueue(&tail_, obj); }
574 errno_t Dequeue(DequeueType& obj) NLIB_NOEXCEPT {
576 errno_t e = pool_.Dequeue(&head_, &tail_, &x);
577 if (e != 0)
return e;
582 errno_t EnqueueUnsafe(T* x) NLIB_NOEXCEPT {
return pool_.EnqueueUnsafe(&tail_, x); }
584 errno_t DequeueUnsafe(DequeueType& obj) NLIB_NOEXCEPT {
586 errno_t e = pool_.DequeueUnsafe(&head_, &tail_, &x);
587 if (e != 0)
return e;
595 LockFreePlaceHolderPool<T*> pool_;
603 NLIB_EINVAL_IFNULL(ptr);
609 return pold ? 0 : EAGAIN;
612 &pold, reinterpret_cast<void*>(obj), 0,
634 if (mq_.raw_handle != 0)
return EALREADY;
635 if (max_size > INT32_MAX)
return EINVAL;
637 attr.
flag = NLIB_MQ_LOCKFREE;
638 attr.
max_msg =
static_cast<int32_t
>(max_size);
639 attr.
destructor = LockFreePriorityQueue::dtor;
657 if (e != 0)
return e;
664 T* obj =
reinterpret_cast<T*
>(msg);
673 class LockFreeBroadcastQueueImpl {
674 typedef LockFreePlaceHolder<const void*, int32_t> item_type;
677 LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT
678 : head_(1), tail_(1), listener_count_(0), pool_(), listeners_() {}
679 ~LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT {}
681 errno_t Enqueue(
const void* msg) NLIB_NOEXCEPT {
683 return pool_.Enqueue(&tail_, msg);
685 errno_t Dequeue(int32_t listener_id,
const void** msg) NLIB_NOEXCEPT {
688 NLIB_UNLIKELY(listener_id >= listener_count_))
return ERANGE;
689 uintptr_t& pos = listeners_[listener_id];
690 item_type* item = pool_.CalcPtr(pos);
691 uintptr_t next = item->next.aba_ptr;
692 if (pool_.IsNull(next))
return ENOENT;
693 *msg = pool_.CalcPtr(next)->data;
699 errno_t DeleteUnsafe(const
void** msg) NLIB_NOEXCEPT {
700 if (pool_.IsNull(head_))
return ENOENT;
701 item_type* item = pool_.CalcPtr(head_);
702 const void* p = item->data;
703 head_ = item->next.aba_ptr;
707 size_t GetListenerCount() const NLIB_NOEXCEPT {
return listener_count_; }
718 int32_t listener_count_;
719 LockFreePlaceHolderPool<const void*, int32_t> pool_;
720 UniquePtr<uintptr_t[]> listeners_;
729 void operator()(
const T*) {}
735 while (impl_.DeleteUnsafe(&p) == 0) {
742 return impl_.Init(max_size, listeners);
746 return impl_.Enqueue(obj);
751 errno_t e = impl_.Dequeue(listener_id, &x);
752 if (e != 0)
return e;
753 obj.reset(reinterpret_cast<const T*>(x));
754 const T* p =
reinterpret_cast<const T*
>(impl_.CheckAndRemove());
762 return impl_.GetListenerCount();
766 detail::LockFreeBroadcastQueueImpl impl_;
773 void* Get() NLIB_NOEXCEPT {
return ptr_; }
788 return reinterpret_cast<MemHolder*
>(pool_.Alloc());
792 pool_.Free(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
799 return reinterpret_cast<MemHolder*
>(pool_.AllocUnsafe());
803 pool_.FreeUnsafe(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
808 LockFreePlaceHolderPool<void*> pool_;
814 #endif // INCLUDE_NN_NLIB_LOCKFREE_H_
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
void FreeUnsafe(MemHolder *p) noexcept
Free()と同様ですが、スレッドセーフではありません。
errno_t PopUnsafe(PopType x) noexcept
スタックから要素を取り出してxに格納します。スレッドセーフではありません。
LockFreePipe() noexcept
デフォルトコンストラクタです。
LockFreeQueue() noexcept
デフォルトコンストラクタです。
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
UniquePtr< const T, empty_func > DequeueType
Dequeue(), DequeueUnsafe()の引数となる型です
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
errno_t Init(size_t count) noexcept
スタックを初期化します。スレッドセーフではありません。
T * PopType
Pop(), PopUnsafe()の引数となる型です
LockFreeStack() noexcept
デフォルトコンストラクタです。
~LockFreeQueue() noexcept
デストラクタです。
errno_t DequeueUnsafe(DequeueType x) noexcept
キューから要素を取り出してxに格納します。スレッドセーフではありません。
size_t GetBufferSize() noexcept
バッファ・サイズを返します。スレッドセーフです。
UniquePtrはポインタの所有権を保持し、UniquePtrがスコープから出るときにデストラクタでポインタをDELで指...
errno_t PushUnsafe(const T &x) noexcept
スタックに要素xを積みます。スレッドセーフではありません。
std::unique_ptrに相当するクラスが定義されています。
errno_t Pop(PopType x) noexcept
スタックから要素を取り出してxに格納します。スレッドセーフです。
errno_t LockFreeInit(T **ptr) noexcept
スレッドセーフにオブジェクトの構築を行います。
errno_t EnqueueUnsafe(const T &x) noexcept
キューに要素xを追加します。スレッドセーフではありません。
固定メモリサイズの領域を確保・解放をロックフリーで行うことのできるプールアロケータです。 ...
指定された数のリスナーがキューから要素を取得できます。全てのリスナーが取得後、要素はキューから削除さ...
MemHolder * AllocUnsafe() noexcept
Alloc()と同様ですが、スレッドセーフではありません。
errno_t Read(void *dest, size_t nbytes) noexcept
データをパイプから読み込みます。スレッドセーフです。
errno_t Enqueue(T *obj, int prio) noexcept
キューに要素を追加します。スレッドセーフです。
errno_t Enqueue(const T &x) noexcept
キューに要素xを追加します。スレッドセーフです。
UniquePtr< T, DestructorForLockFree< T > > DequeueType
Dequeue(), DequeueUnsafe()の引数となる型です
errno_t Write(const void *src, size_t nbytes) noexcept
データをパイプに書き込みます。スレッドセーフです。
T * DequeueType
Dequeue(), DequeueUnsafe()の引数となる型です
オブジェクトをデストラクトするためのクラステンプレートです。特殊化して利用します。 ...
MemHolder * Alloc() noexcept
メモリを割り当てます。返されたオブジェクトへのポインタに対してGet()を実行することで割り当てた領域を得...
メッセージキューの設定や現在の状態を格納する構造体です。
size_t GetListenerCount() const noexcept
Init()で指定したリスナーの数を返します。スレッドセーフです。
errno_t Dequeue(DequeueType &obj, int *prio) noexcept
キューから要素を取り出します。スレッドセーフです。
errno_t Close() noexcept
キューをクローズし初期化前の状態にします。スレッドセーフではありません。
errno_t Init(size_t count) noexcept
キューを初期化します。スレッドセーフではありません。
errno_t Dequeue(DequeueType x) noexcept
キューから要素を取り出してxに格納します。スレッドセーフです。
errno_t Push(const T &x) noexcept
スタックに要素xを積みます。スレッドセーフです。
LockFreeUnitHeap() noexcept
デフォルトコンストラクタです。
errno_t Init(size_t max_size, size_t listeners) noexcept
キューを初期化します。スレッドセーフではありません。
~LockFreeUnitHeap() noexcept
デストラクタです。
データの送り手側のスレッドと受け手側のスレッドがそれぞれ1つずつの場合、このクラスを用いてロックフリー...
errno_t Init(size_t max_size) noexcept
キューを初期化します。スレッドセーフではありません。
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
LockFreeBroadcastQueue() noexcept
デフォルトコンストラクタです。
オブジェクトを初期化するためのクラステンプレートです。特殊化して利用します。
~LockFreeStack() noexcept
デストラクタです。
~LockFreeBroadcastQueue() noexcept
デストラクタです。
errno_t Dequeue(int32_t listener_id, DequeueType &obj) noexcept
リスナーを指定してキューから要素を読み込みます。異なるlistener_idを利用している場合はスレッドセーフで...
void Free(MemHolder *p) noexcept
メモリを解放します。スレッドセーフです。
LockFreePriorityQueue() noexcept
デフォルトコンストラクタです。
ロックフリーな優先度つきキューを実装したクラスで、nlib_mqをラップしています。
~LockFreePriorityQueue() noexcept
デストラクタです。
errno_t Enqueue(const T *obj) noexcept
キューに要素を追加します。スレッドセーフです。