Daily bump.
[official-gcc.git] / libsanitizer / sanitizer_common / sanitizer_lfstack.h
blob8033b9a7f9cf54621e1330081fd3b5859b4b0dc5
1 //===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===//
2 //
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
5 //
6 //===----------------------------------------------------------------------===//
7 //
8 // Lock-free stack.
9 // Uses 32/17 bits as ABA-counter on 32/64-bit platforms.
10 // The memory passed to Push() must not be ever munmap'ed.
11 // The type T must contain T *next field.
13 //===----------------------------------------------------------------------===//
15 #ifndef SANITIZER_LFSTACK_H
16 #define SANITIZER_LFSTACK_H
18 #include "sanitizer_internal_defs.h"
19 #include "sanitizer_common.h"
20 #include "sanitizer_atomic.h"
22 namespace __sanitizer {
24 template<typename T>
25 struct LFStack {
26 void Clear() {
27 atomic_store(&head_, 0, memory_order_relaxed);
30 bool Empty() const {
31 return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0;
34 void Push(T *p) {
35 u64 cmp = atomic_load(&head_, memory_order_relaxed);
36 for (;;) {
37 u64 cnt = (cmp & kCounterMask) + kCounterInc;
38 u64 xch = (u64)(uptr)p | cnt;
39 p->next = (T*)(uptr)(cmp & kPtrMask);
40 if (atomic_compare_exchange_weak(&head_, &cmp, xch,
41 memory_order_release))
42 break;
46 T *Pop() {
47 u64 cmp = atomic_load(&head_, memory_order_acquire);
48 for (;;) {
49 T *cur = (T*)(uptr)(cmp & kPtrMask);
50 if (cur == 0)
51 return 0;
52 T *nxt = cur->next;
53 u64 cnt = (cmp & kCounterMask);
54 u64 xch = (u64)(uptr)nxt | cnt;
55 if (atomic_compare_exchange_weak(&head_, &cmp, xch,
56 memory_order_acquire))
57 return cur;
61 // private:
62 static const int kCounterBits = FIRST_32_SECOND_64(32, 17);
63 static const u64 kPtrMask = ((u64)-1) >> kCounterBits;
64 static const u64 kCounterMask = ~kPtrMask;
65 static const u64 kCounterInc = kPtrMask + 1;
67 atomic_uint64_t head_;
69 } // namespace __sanitizer
71 #endif // #ifndef SANITIZER_LFSTACK_H