48 // LockFreeStacks support polymorphic elements. Because the objects
49 // in a stack are externally managed, rather than being embedded
50 // values in the stack, the actual type of such objects may be more
51 // specific than the stack's element type.
52 //
53 // \tparam T is the class of the elements in the stack.
54 //
55 // \tparam next_ptr is a function pointer. Applying this function to
56 // an object of type T must return a pointer to the list entry member
57 // of the object associated with the LockFreeStack type.
58 template<typename T, T* volatile* (*next_ptr)(T&)>
59 class LockFreeStack {
60 T* volatile _top;
61
62 void prepend_impl(T* first, T* last) {
63 T* cur = top();
64 T* old;
65 do {
66 old = cur;
67 set_next(*last, cur);
68 cur = Atomic::cmpxchg(first, &_top, cur);
69 } while (old != cur);
70 }
71
72 // Noncopyable.
73 LockFreeStack(const LockFreeStack&);
74 LockFreeStack& operator=(const LockFreeStack&);
75
76 public:
77 LockFreeStack() : _top(NULL) {}
78 ~LockFreeStack() { assert(empty(), "stack not empty"); }
79
80 // Atomically removes the top object from this stack and returns a
81 // pointer to that object, or NULL if this stack is empty. Acts as a
82 // full memory barrier. Subject to ABA behavior; callers must ensure
83 // usage is safe.
84 T* pop() {
85 T* result = top();
86 T* old;
87 do {
88 old = result;
89 T* new_top = NULL;
90 if (result != NULL) {
91 new_top = next(*result);
92 }
93 // CAS even on empty pop, for consistent membar bahavior.
94 result = Atomic::cmpxchg(new_top, &_top, result);
95 } while (result != old);
96 if (result != NULL) {
97 set_next(*result, NULL);
98 }
99 return result;
100 }
101
102 // Atomically exchange the list of elements with NULL, returning the old
103 // list of elements. Acts as a full memory barrier.
104 // postcondition: empty()
105 T* pop_all() {
106 return Atomic::xchg(&_top, (T*)NULL);
107 }
108
109 // Atomically adds value to the top of this stack. Acts as a full
110 // memory barrier.
111 void push(T& value) {
112 assert(next(value) == NULL, "precondition");
113 prepend_impl(&value, &value);
114 }
|
48 // LockFreeStacks support polymorphic elements. Because the objects
49 // in a stack are externally managed, rather than being embedded
50 // values in the stack, the actual type of such objects may be more
51 // specific than the stack's element type.
52 //
53 // \tparam T is the class of the elements in the stack.
54 //
55 // \tparam next_ptr is a function pointer. Applying this function to
56 // an object of type T must return a pointer to the list entry member
57 // of the object associated with the LockFreeStack type.
58 template<typename T, T* volatile* (*next_ptr)(T&)>
59 class LockFreeStack {
60 T* volatile _top;
61
62 void prepend_impl(T* first, T* last) {
63 T* cur = top();
64 T* old;
65 do {
66 old = cur;
67 set_next(*last, cur);
68 cur = Atomic::cmpxchg(&_top, cur, first);
69 } while (old != cur);
70 }
71
72 // Noncopyable.
73 LockFreeStack(const LockFreeStack&);
74 LockFreeStack& operator=(const LockFreeStack&);
75
76 public:
77 LockFreeStack() : _top(NULL) {}
78 ~LockFreeStack() { assert(empty(), "stack not empty"); }
79
80 // Atomically removes the top object from this stack and returns a
81 // pointer to that object, or NULL if this stack is empty. Acts as a
82 // full memory barrier. Subject to ABA behavior; callers must ensure
83 // usage is safe.
84 T* pop() {
85 T* result = top();
86 T* old;
87 do {
88 old = result;
89 T* new_top = NULL;
90 if (result != NULL) {
91 new_top = next(*result);
92 }
93 // CAS even on empty pop, for consistent membar bahavior.
94 result = Atomic::cmpxchg(&_top, result, new_top);
95 } while (result != old);
96 if (result != NULL) {
97 set_next(*result, NULL);
98 }
99 return result;
100 }
101
102 // Atomically exchange the list of elements with NULL, returning the old
103 // list of elements. Acts as a full memory barrier.
104 // postcondition: empty()
105 T* pop_all() {
106 return Atomic::xchg(&_top, (T*)NULL);
107 }
108
109 // Atomically adds value to the top of this stack. Acts as a full
110 // memory barrier.
111 void push(T& value) {
112 assert(next(value) == NULL, "precondition");
113 prepend_impl(&value, &value);
114 }
|