Jamoma API  0.6.0.a19
CAAtomicStack.h
1 /* Copyright 2007 Apple Inc. All Rights Reserved.
2 
3  Disclaimer: IMPORTANT: This Apple software is supplied to you by
4  Apple Inc. ("Apple") in consideration of your agreement to the
5  following terms, and your use, installation, modification or
6  redistribution of this Apple software constitutes acceptance of these
7  terms. If you do not agree with these terms, please do not use,
8  install, modify or redistribute this Apple software.
9 
10  In consideration of your agreement to abide by the following terms, and
11  subject to these terms, Apple grants you a personal, non-exclusive
12  license, under Apple's copyrights in this original Apple software (the
13  "Apple Software"), to use, reproduce, modify and redistribute the Apple
14  Software, with or without modifications, in source and/or binary forms;
15  provided that if you redistribute the Apple Software in its entirety and
16  without modifications, you must retain this notice and the following
17  text and disclaimers in all such redistributions of the Apple Software.
18  Neither the name, trademarks, service marks or logos of Apple Inc.
19  may be used to endorse or promote products derived from the Apple
20  Software without specific prior written permission from Apple. Except
21  as expressly stated in this notice, no other rights or licenses, express
22  or implied, are granted by Apple herein, including but not limited to
23  any patent rights that may be infringed by your derivative works or by
24  other works in which the Apple Software may be incorporated.
25 
26  The Apple Software is provided by Apple on an "AS IS" basis. APPLE
27  MAKES NO WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION
28  THE IMPLIED WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND FITNESS
29  FOR A PARTICULAR PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS USE AND
30  OPERATION ALONE OR IN COMBINATION WITH YOUR PRODUCTS.
31 
32  IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, INCIDENTAL
33  OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
34  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
35  INTERRUPTION) ARISING IN ANY WAY OUT OF THE USE, REPRODUCTION,
36  MODIFICATION AND/OR DISTRIBUTION OF THE APPLE SOFTWARE, HOWEVER CAUSED
37  AND WHETHER UNDER THEORY OF CONTRACT, TORT (INCLUDING NEGLIGENCE),
38  STRICT LIABILITY OR OTHERWISE, EVEN IF APPLE HAS BEEN ADVISED OF THE
39  POSSIBILITY OF SUCH DAMAGE.
40 */
41 #ifndef __TStack_h__
42 #define __TStack_h__
43 
44 #if !defined(__COREAUDIO_USE_FLAT_INCLUDES__)
45  #include <libkern/OSAtomic.h>
46 #else
47 // #include <DriverSynchronization.h>
48 #include <CAAtomic.h>
49 #endif
50 
51 #if MAC_OS_X_VERSION_MAX_ALLOWED < MAC_OS_X_VERSION_10_4
52  #include <CoreServices/CoreServices.h>
53 #endif
54 
55 // linked list LIFO or FIFO (pop_all_reversed) stack, elements are pushed and popped atomically
56 // class T must implement set_next() and get_next()
57 template <class T>
58 class TAtomicStack {
59 public:
60  TAtomicStack() : mHead(NULL) { }
61 
62  // non-atomic routines, for use when initializing/deinitializing, operate NON-atomically
63  void push_NA(T *item)
64  {
65  item->set_next(mHead);
66  mHead = item;
67  }
68 
69  T * pop_NA()
70  {
71  T *result = mHead;
72  if (result)
73  mHead = result->get_next();
74  return result;
75  }
76 
77  bool empty() { return mHead == NULL; }
78 
79  T * head() { return mHead; }
80 
81  // atomic routines
82  void push_atomic(T *item)
83  {
84  T *head;
85  do {
86  head = mHead;
87  item->set_next(head);
88  } while (!compare_and_swap(head, item, &mHead));
89  }
90 
91  void push_multiple_atomic(T *item)
92  // pushes entire linked list headed by item
93  {
94  T *head, *p = item, *tail;
95  // find the last one -- when done, it will be linked to head
96  do {
97  tail = p;
98  p = p->get_next();
99  } while (p);
100  do {
101  head = mHead;
102  tail->set_next(head);
103  } while (!compare_and_swap(head, item, &mHead));
104  }
105 
106  T * pop_atomic_single_reader()
107  // this may only be used when only one thread may potentially pop from the stack.
108  // if multiple threads may pop, this suffers from the ABA problem.
109  // <rdar://problem/4606346> TAtomicStack suffers from the ABA problem
110  {
111  T *result;
112  do {
113  if ((result = mHead) == NULL)
114  break;
115  } while (!compare_and_swap(result, result->get_next(), &mHead));
116  return result;
117  }
118 
119  T * pop_atomic()
120  // This is inefficient for large linked lists.
121  // prefer pop_all() to a series of calls to pop_atomic.
122  // push_multiple_atomic has to traverse the entire list.
123  {
124  T *result = pop_all();
125  if (result) {
126  T *next = result->get_next();
127  if (next)
128  // push all the remaining items back onto the stack
129  push_multiple_atomic(next);
130  }
131  return result;
132  }
133 
134  T * pop_all()
135  {
136  T *result;
137  do {
138  if ((result = mHead) == NULL)
139  break;
140  } while (!compare_and_swap(result, NULL, &mHead));
141  return result;
142  }
143 
144  T* pop_all_reversed()
145  {
146  TAtomicStack<T> reversed;
147  T *p = pop_all(), *next;
148  while (p != NULL) {
149  next = p->get_next();
150  reversed.push_NA(p);
151  p = next;
152  }
153  return reversed.mHead;
154  }
155 
156  static bool compare_and_swap(T *oldvalue, T *newvalue, T **pvalue)
157  {
158 #if TARGET_OS_MAC
159  #if __LP64__
160  return ::OSAtomicCompareAndSwap64Barrier(int64_t(oldvalue), int64_t(newvalue), (int64_t *)pvalue);
161  #elif MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_4
162  return ::OSAtomicCompareAndSwap32Barrier(int32_t(oldvalue), int32_t(newvalue), (int32_t *)pvalue);
163  #else
164  return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue);
165  #endif
166 #else
167  //return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue);
168  return CAAtomicCompareAndSwap32Barrier(SInt32(oldvalue), SInt32(newvalue), (SInt32*)pvalue);
169 #endif
170  }
171 
172 protected:
173  T * mHead;
174 };
175 
176 #if ((MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_5) && !TARGET_OS_WIN32)
177 #include <libkern/OSAtomic.h>
178 
179 class CAAtomicStack {
180 public:
181  CAAtomicStack(size_t nextPtrOffset) : mNextPtrOffset(nextPtrOffset) { /*OSQueueHead h = OS_ATOMIC_QUEUE_INIT; mHead = h;*/ mHead.opaque1 = 0; mHead.opaque2 = 0;
182  }
183  // a subset of the above
184  void push_atomic(void *p) { OSAtomicEnqueue(&mHead, p, mNextPtrOffset); }
185  void push_NA(void *p) { push_atomic(p); }
186 
187  void * pop_atomic() { return OSAtomicDequeue(&mHead, mNextPtrOffset); }
188  void * pop_atomic_single_reader() { return pop_atomic(); }
189  void * pop_NA() { return pop_atomic(); }
190 
191 private:
192  OSQueueHead mHead;
193  size_t mNextPtrOffset;
194 };
195 
196 // syntactic sugar
197 template <class T>
198 class TAtomicStack2 : public CAAtomicStack {
199 public:
200  TAtomicStack2(size_t nextPtrOffset) : CAAtomicStack(nextPtrOffset) { }
201 
202  T * pop_atomic() { return (T *)CAAtomicStack::pop_atomic(); }
203  T * pop_atomic_single_reader() { return pop_atomic(); }
204  T * pop_NA() { return pop_atomic(); }
205 };
206 
207 #endif // MAC_OS_X_VERSION_MAX_ALLOWED && !TARGET_OS_WIN32
208 
209 #endif // __TStack_h__