Mercurial > hg > CbC > CbC_gcc
diff libsanitizer/sanitizer_common/sanitizer_lfstack.h @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 1830386684a0 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/libsanitizer/sanitizer_common/sanitizer_lfstack.h Fri Oct 27 22:46:09 2017 +0900 @@ -0,0 +1,71 @@ +//===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===// +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Lock-free stack. +// Uses 32/17 bits as ABA-counter on 32/64-bit platforms. +// The memory passed to Push() must not be ever munmap'ed. +// The type T must contain T *next field. +// +//===----------------------------------------------------------------------===// + +#ifndef SANITIZER_LFSTACK_H +#define SANITIZER_LFSTACK_H + +#include "sanitizer_internal_defs.h" +#include "sanitizer_common.h" +#include "sanitizer_atomic.h" + +namespace __sanitizer { + +template<typename T> +struct LFStack { + void Clear() { + atomic_store(&head_, 0, memory_order_relaxed); + } + + bool Empty() const { + return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0; + } + + void Push(T *p) { + u64 cmp = atomic_load(&head_, memory_order_relaxed); + for (;;) { + u64 cnt = (cmp & kCounterMask) + kCounterInc; + u64 xch = (u64)(uptr)p | cnt; + p->next = (T*)(uptr)(cmp & kPtrMask); + if (atomic_compare_exchange_weak(&head_, &cmp, xch, + memory_order_release)) + break; + } + } + + T *Pop() { + u64 cmp = atomic_load(&head_, memory_order_acquire); + for (;;) { + T *cur = (T*)(uptr)(cmp & kPtrMask); + if (!cur) + return nullptr; + T *nxt = cur->next; + u64 cnt = (cmp & kCounterMask); + u64 xch = (u64)(uptr)nxt | cnt; + if (atomic_compare_exchange_weak(&head_, &cmp, xch, + memory_order_acquire)) + return cur; + } + } + + // private: + static const int kCounterBits = FIRST_32_SECOND_64(32, 17); + static const u64 kPtrMask = ((u64)-1) >> kCounterBits; + static const u64 kCounterMask = ~kPtrMask; + static const u64 kCounterInc = kPtrMask + 1; + + atomic_uint64_t head_; +}; +} // namespace __sanitizer + +#endif // SANITIZER_LFSTACK_H