3 Abstract: Part of CoreAudio Utility Classes
6 Disclaimer: IMPORTANT: This Apple software is supplied to you by Apple
7 Inc. ("Apple") in consideration of your agreement to the following
8 terms, and your use, installation, modification or redistribution of
9 this Apple software constitutes acceptance of these terms. If you do
10 not agree with these terms, please do not use, install, modify or
11 redistribute this Apple software.
13 In consideration of your agreement to abide by the following terms, and
14 subject to these terms, Apple grants you a personal, non-exclusive
15 license, under Apple's copyrights in this original Apple software (the
16 "Apple Software"), to use, reproduce, modify and redistribute the Apple
17 Software, with or without modifications, in source and/or binary forms;
18 provided that if you redistribute the Apple Software in its entirety and
19 without modifications, you must retain this notice and the following
20 text and disclaimers in all such redistributions of the Apple Software.
21 Neither the name, trademarks, service marks or logos of Apple Inc. may
22 be used to endorse or promote products derived from the Apple Software
23 without specific prior written permission from Apple. Except as
24 expressly stated in this notice, no other rights or licenses, express or
25 implied, are granted by Apple herein, including but not limited to any
26 patent rights that may be infringed by your derivative works or by other
27 works in which the Apple Software may be incorporated.
29 The Apple Software is provided by Apple on an "AS IS" basis. APPLE
30 MAKES NO WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION
31 THE IMPLIED WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND FITNESS
32 FOR A PARTICULAR PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS USE AND
33 OPERATION ALONE OR IN COMBINATION WITH YOUR PRODUCTS.
35 IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, INCIDENTAL
36 OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
37 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
38 INTERRUPTION) ARISING IN ANY WAY OUT OF THE USE, REPRODUCTION,
39 MODIFICATION AND/OR DISTRIBUTION OF THE APPLE SOFTWARE, HOWEVER CAUSED
40 AND WHETHER UNDER THEORY OF CONTRACT, TORT (INCLUDING NEGLIGENCE),
41 STRICT LIABILITY OR OTHERWISE, EVEN IF APPLE HAS BEEN ADVISED OF THE
42 POSSIBILITY OF SUCH DAMAGE.
44 Copyright (C) 2014 Apple Inc. All Rights Reserved.
47 #ifndef __CAAtomicStack_h__
48 #define __CAAtomicStack_h__
50 #if !defined(__COREAUDIO_USE_FLAT_INCLUDES__)
51 #include <libkern/OSAtomic.h>
56 #if MAC_OS_X_VERSION_MAX_ALLOWED < MAC_OS_X_VERSION_10_4
57 #include <CoreServices/CoreServices.h>
60 // linked list LIFO or FIFO (pop_all_reversed) stack, elements are pushed and popped atomically
61 // class T must implement T *& next().
65 TAtomicStack() : mHead(NULL) { }
67 // non-atomic routines, for use when initializing/deinitializing, operate NON-atomically
78 mHead = result->next();
82 bool empty() const { return mHead == NULL; }
84 T * head() { return mHead; }
87 void push_atomic(T *item)
93 } while (!compare_and_swap(head_, item, &mHead));
96 void push_multiple_atomic(T *item)
97 // pushes entire linked list headed by item
99 T *head_, *p = item, *tail;
100 // find the last one -- when done, it will be linked to head
107 tail->next() = head_;
108 } while (!compare_and_swap(head_, item, &mHead));
111 T * pop_atomic_single_reader()
112 // this may only be used when only one thread may potentially pop from the stack.
113 // if multiple threads may pop, this suffers from the ABA problem.
114 // <rdar://problem/4606346> TAtomicStack suffers from the ABA problem
118 if ((result = mHead) == NULL)
120 } while (!compare_and_swap(result, result->next(), &mHead));
125 // This is inefficient for large linked lists.
126 // prefer pop_all() to a series of calls to pop_atomic.
127 // push_multiple_atomic has to traverse the entire list.
129 T *result = pop_all();
131 T *next = result->next();
133 // push all the remaining items back onto the stack
134 push_multiple_atomic(next);
143 if ((result = mHead) == NULL)
145 } while (!compare_and_swap(result, NULL, &mHead));
149 T* pop_all_reversed()
151 TAtomicStack<T> reversed;
152 T *p = pop_all(), *next;
158 return reversed.mHead;
161 static bool compare_and_swap(T *oldvalue, T *newvalue, T **pvalue)
165 return ::OSAtomicCompareAndSwap64Barrier(int64_t(oldvalue), int64_t(newvalue), (int64_t *)pvalue);
166 #elif MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_4
167 return ::OSAtomicCompareAndSwap32Barrier(int32_t(oldvalue), int32_t(newvalue), (int32_t *)pvalue);
169 return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue);
172 //return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue);
173 return CAAtomicCompareAndSwap32Barrier(SInt32(oldvalue), SInt32(newvalue), (SInt32*)pvalue);
181 #if ((MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_5) && !TARGET_OS_WIN32)
182 #include <libkern/OSAtomic.h>
184 class CAAtomicStack {
186 CAAtomicStack(size_t nextPtrOffset) : mNextPtrOffset(nextPtrOffset) {
187 /*OSQueueHead h = OS_ATOMIC_QUEUE_INIT; mHead = h;*/
188 mHead.opaque1 = 0; mHead.opaque2 = 0;
190 // a subset of the above
191 void push_atomic(void *p) { OSAtomicEnqueue(&mHead, p, mNextPtrOffset); }
192 void push_NA(void *p) { push_atomic(p); }
194 void * pop_atomic() { return OSAtomicDequeue(&mHead, mNextPtrOffset); }
195 void * pop_atomic_single_reader() { return pop_atomic(); }
196 void * pop_NA() { return pop_atomic(); }
200 size_t mNextPtrOffset;
203 // a more efficient subset of TAtomicStack using OSQueue.
205 class TAtomicStack2 {
208 /*OSQueueHead h = OS_ATOMIC_QUEUE_INIT; mHead = h;*/
209 mHead.opaque1 = 0; mHead.opaque2 = 0;
212 void push_atomic(T *item) {
213 if (mNextPtrOffset < 0) {
214 T **pnext = &item->next(); // hack around offsetof not working with C++
215 mNextPtrOffset = (Byte *)pnext - (Byte *)item;
217 OSAtomicEnqueue(&mHead, item, mNextPtrOffset);
219 void push_NA(T *item) { push_atomic(item); }
221 T * pop_atomic() { return (T *)OSAtomicDequeue(&mHead, mNextPtrOffset); }
222 T * pop_atomic_single_reader() { return pop_atomic(); }
223 T * pop_NA() { return pop_atomic(); }
225 // caution: do not try to implement pop_all_reversed here. the writer could add new elements
226 // while the reader is trying to pop old ones!
230 ssize_t mNextPtrOffset;
235 #define TAtomicStack2 TAtomicStack
237 #endif // MAC_OS_X_VERSION_MAX_ALLOWED && !TARGET_OS_WIN32
239 #endif // __CAAtomicStack_h__