platform/mac/SuperColliderAU/AUSDK/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 /*=============================================================================
  42         TStack.h
  43
  44 =============================================================================*/
  45
  46 #ifndef __TStack_h__
  47 #define __TStack_h__
  48
  49 #if !defined(__COREAUDIO_USE_FLAT_INCLUDES__)
  50         #include <libkern/OSAtomic.h>
  51 #else
  52         #include <DriverSynchronization.h>
  53 #endif
  54
  55 #if MAC_OS_X_VERSION_MAX_ALLOWED < MAC_OS_X_VERSION_10_4
  56         #include <CoreServices/CoreServices.h>
  57 #endif
  58
  59 //  linked list LIFO or FIFO (pop_all_reversed) stack, elements are pushed and popped atomically
  60 //  class T must implement set_next() and get_next()
  61 template <class T>
  62 class TAtomicStack {
  63 public:
  64         TAtomicStack() : mHead(NULL) { }
  65
  66         // non-atomic routines, for use when initializing/deinitializing, operate NON-atomically
  67         void    push_NA(T *item)
  68         {
  69                 item->set_next(mHead);
  70                 mHead = item;
  71         }
  72
  73         T *             pop_NA()
  74         {
  75                 T *result = mHead;
  76                 if (result)
  77                         mHead = result->get_next();
  78                 return result;
  79         }
  80
  81         bool    empty() { return mHead == NULL; }
  82
  83         // atomic routines
  84         void    push_atomic(T *item)
  85         {
  86                 T *head;
  87                 do {
  88                         head = mHead;
  89                         item->set_next(head);
  90                 } while (!compare_and_swap(head, item, &mHead));
  91         }
  92
  93         void    push_multiple_atomic(T *item)
  94                 // pushes entire linked list headed by item
  95         {
  96                 T *head, *p = item, *tail;
  97                 // find the last one -- when done, it will be linked to head
  98                 do {
  99                         tail = p;
 100                         p = p->get_next();
 101                 } while (p);
 102                 do {
 103                         head = mHead;
 104                         tail->set_next(head);
 105                 } while (!compare_and_swap(head, item, &mHead));
 106         }
 107
 108         T *             pop_atomic_single_reader()
 109                 // this may only be used when only one thread may potentially pop from the stack.
 110                 // if multiple threads may pop, this suffers from the ABA problem.
 111                 // <rdar://problem/4606346> TAtomicStack suffers from the ABA problem
 112         {
 113                 T *result;
 114                 do {
 115                         if ((result = mHead) == NULL)
 116                                 break;
 117                 } while (!compare_and_swap(result, result->get_next(), &mHead));
 118                 return result;
 119         }
 120
 121         T *             pop_atomic()
 122                 // This is inefficient for large linked lists.
 123                 // prefer pop_all() to a series of calls to pop_atomic.
 124                 // push_multiple_atomic has to traverse the entire list.
 125         {
 126                 T *result = pop_all();
 127                 if (result) {
 128                         T *next = result->get_next();
 129                         if (next)
 130                                 // push all the remaining items back onto the stack
 131                                 push_multiple_atomic(next);
 132                 }
 133                 return result;
 134         }
 135
 136         T *             pop_all()
 137         {
 138                 T *result;
 139                 do {
 140                         if ((result = mHead) == NULL)
 141                                 break;
 142                 } while (!compare_and_swap(result, NULL, &mHead));
 143                 return result;
 144         }
 145
 146         T*              pop_all_reversed()
 147         {
 148                 TAtomicStack<T> reversed;
 149                 T *p = pop_all(), *next;
 150                 while (p != NULL) {
 151                         next = p->get_next();
 152                         reversed.push_NA(p);
 153                         p = next;
 154                 }
 155                 return reversed.mHead;
 156         }
 157
 158         bool    compare_and_swap(T *oldvalue, T *newvalue, T **pvalue)
 159         {
 160 #if TARGET_OS_MAC
 161         #if __LP64__
 162                         return ::OSAtomicCompareAndSwap64Barrier(int64_t(oldvalue), int64_t(newvalue), (int64_t *)pvalue);
 163         #elif MAC_OS_X_VERSION_MAX_ALLOWED >= MAC_OS_X_VERSION_10_4
 164                         return ::OSAtomicCompareAndSwap32Barrier(int32_t(oldvalue), int32_t(newvalue), (int32_t *)pvalue);
 165         #else
 166                         return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue);
 167         #endif
 168 #else
 169                         return ::CompareAndSwap(UInt32(oldvalue), UInt32(newvalue), (UInt32 *)pvalue);
 170 #endif
 171         }
 172
 173 protected:
 174         T *             mHead;
 175 };
 176
 177 #endif // __TStack_h__