1 /* 2 Copyright (C) 2016 Apple Inc. All Rights Reserved. 3 See LICENSE.txt for this sample’s licensing information 4 5 Abstract: 6 Part of Core Audio Public Utility Classes 7 */ 8 9 #ifndef __CAAtomicStack_h__ 10 #define __CAAtomicStack_h__ 11 12 #if !defined(__COREAUDIO_USE_FLAT_INCLUDES__) 13 #include <libkern/OSAtomic.h> 14 #else 15 #include <CAAtomic.h> 16 #endif 17 18 #if MAC_OS_X_VERSION_MAX_ALLOWED < MAC_OS_X_VERSION_10_4 19 #include <CoreServices/CoreServices.h> 20 #endif 21 22 // linked list LIFO or FIFO (pop_all_reversed) stack, elements are pushed and popped atomically 23 // class T must implement T *& next(). 24 template <class T> 25 class TAtomicStack { 26 public: TAtomicStack()27 TAtomicStack() : mHead(NULL) { } 28 29 // non-atomic routines, for use when initializing/deinitializing, operate NON-atomically push_NA(T * item)30 void push_NA(T *item) 31 { 32 item->next() = mHead; 33 mHead = item; 34 } 35 pop_NA()36 T * pop_NA() 37 { 38 T *result = mHead; 39 if (result) 40 mHead = result->next(); 41 return result; 42 } 43 empty()44 bool empty() const { return mHead == NULL; } 45 head()46 T * head() { return mHead; } 47 48 // atomic routines push_atomic(T * item)49 void push_atomic(T *item) 50 { 51 T *head_; 52 do { 53 head_ = mHead; 54 item->next() = head_; 55 } while (!compare_and_swap(head_, item, &mHead)); 56 } 57 push_multiple_atomic(T * item)58 void push_multiple_atomic(T *item) 59 // pushes entire linked list headed by item 60 { 61 T *head_, *p = item, *tail; 62 // find the last one -- when done, it will be linked to head 63 do { 64 tail = p; 65 p = p->next(); 66 } while (p); 67 do { 68 head_ = mHead; 69 tail->next() = head_; 70 } while (!compare_and_swap(head_, item, &mHead)); 71 } 72 pop_atomic_single_reader()73 T * pop_atomic_single_reader() 74 // this may only be used when only one thread may potentially pop from the stack. 75 // if multiple threads may pop, this suffers from the ABA problem. 76 // <rdar://problem/4606346> TAtomicStack suffers from the ABA problem 77 { 78 T *result; 79 do { 80 if ((result = mHead) == NULL) 81 break; 82 } while (!compare_and_swap(result, result->next(), &mHead)); 83 return result; 84 } 85 pop_atomic()86 T * pop_atomic() 87 // This is inefficient for large linked lists. 88 // prefer pop_all() to a series of calls to pop_atomic. 89 // push_multiple_atomic has to traverse the entire list. 90 { 91 T *result = pop_all(); 92 if (result) { 93 T *next = result->next(); 94 if (next) 95 // push all the remaining items back onto the stack 96 push_multiple_atomic(next); 97 } 98 return result; 99 } 100 pop_all()101 T * pop_all() 102 { 103 T *result; 104 do { 105 if ((result = mHead) == NULL) 106 break; 107 } while (!compare_and_swap(result, NULL, &mHead)); 108 return result; 109 } 110 pop_all_reversed()111 T* pop_all_reversed() 112 { 113 TAtomicStack<T> reversed; 114 T *p = pop_all(), *next; 115 while (p != NULL) { 116 next = p->next(); 117 reversed.push_NA(p); 118 p = next; 119 } 120 return reversed.mHead; 121 } 122 compare_and_swap(T * oldvalue,T * newvalue,T ** pvalue)123 static bool compare_and_swap(T *oldvalue, T *newvalue, T **pvalue) 124 { 125 #if TARGET_OS_MAC 126 #if __LP64__ 127 return ::OSAtomicCompareAndSwap64Barrier(int64_t(oldvalue), int64_t(newvalue), (int64_t *)pvalue); 128 #elif MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_4 129 return ::OSAtomicCompareAndSwap32Barrier(int32_t(oldvalue), int32_t(newvalue), (int32_t *)pvalue); 130 #else 131 return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue); 132 #endif 133 #else 134 //return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue); 135 return CAAtomicCompareAndSwap32Barrier(SInt32(oldvalue), SInt32(newvalue), (SInt32*)pvalue); 136 #endif 137 } 138 139 protected: 140 T * mHead; 141 }; 142 143 #if ((MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_5) && !TARGET_OS_WIN32) 144 #include <libkern/OSAtomic.h> 145 146 class CAAtomicStack { 147 public: CAAtomicStack(size_t nextPtrOffset)148 CAAtomicStack(size_t nextPtrOffset) : mNextPtrOffset(nextPtrOffset) { 149 /*OSQueueHead h = OS_ATOMIC_QUEUE_INIT; mHead = h;*/ 150 mHead.opaque1 = 0; mHead.opaque2 = 0; 151 } 152 // a subset of the above push_atomic(void * p)153 void push_atomic(void *p) { OSAtomicEnqueue(&mHead, p, mNextPtrOffset); } push_NA(void * p)154 void push_NA(void *p) { push_atomic(p); } 155 pop_atomic()156 void * pop_atomic() { return OSAtomicDequeue(&mHead, mNextPtrOffset); } pop_atomic_single_reader()157 void * pop_atomic_single_reader() { return pop_atomic(); } pop_NA()158 void * pop_NA() { return pop_atomic(); } 159 160 private: 161 OSQueueHead mHead; 162 size_t mNextPtrOffset; 163 }; 164 165 // a more efficient subset of TAtomicStack using OSQueue. 166 template <class T> 167 class TAtomicStack2 { 168 public: TAtomicStack2()169 TAtomicStack2() { 170 /*OSQueueHead h = OS_ATOMIC_QUEUE_INIT; mHead = h;*/ 171 mHead.opaque1 = 0; mHead.opaque2 = 0; 172 mNextPtrOffset = -1; 173 } push_atomic(T * item)174 void push_atomic(T *item) { 175 if (mNextPtrOffset < 0) { 176 T **pnext = &item->next(); // hack around offsetof not working with C++ 177 mNextPtrOffset = (Byte *)pnext - (Byte *)item; 178 } 179 OSAtomicEnqueue(&mHead, item, mNextPtrOffset); 180 } push_NA(T * item)181 void push_NA(T *item) { push_atomic(item); } 182 pop_atomic()183 T * pop_atomic() { return (T *)OSAtomicDequeue(&mHead, mNextPtrOffset); } pop_atomic_single_reader()184 T * pop_atomic_single_reader() { return pop_atomic(); } pop_NA()185 T * pop_NA() { return pop_atomic(); } 186 187 // caution: do not try to implement pop_all_reversed here. the writer could add new elements 188 // while the reader is trying to pop old ones! 189 190 private: 191 OSQueueHead mHead; 192 ssize_t mNextPtrOffset; 193 }; 194 195 #else 196 197 #define TAtomicStack2 TAtomicStack 198 199 #endif // MAC_OS_X_VERSION_MAX_ALLOWED && !TARGET_OS_WIN32 200 201 #endif // __CAAtomicStack_h__ 202