platform/mac/SuperColliderAU/AUSDK/CAThreadSafeList.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         CAThreadSafeList.h
  43
  44 =============================================================================*/
  45
  46 #ifndef __CAThreadSafeList_h__
  47 #define __CAThreadSafeList_h__
  48
  49 #include "CAAtomicStack.h"
  50
  51 //  linked list of T's
  52 //      T must define operator ==
  53 template <class T>
  54 class TThreadSafeList {
  55 private:
  56         enum EEventType { kAdd, kRemove, kClear };
  57         class Node {
  58         public:
  59                 Node *          mNext;
  60                 EEventType      mEventType;
  61                 T                       mObject;
  62
  63                 void    set_next(Node *node) { mNext = node; }
  64                 Node *  get_next() { return mNext; }
  65         };
  66
  67 public:
  68         class iterator {
  69         public:
  70                 iterator() { }
  71                 iterator(Node *n) : mNode(n) { }
  72
  73                 bool operator == (const iterator &other) const { return this->mNode == other.mNode; }
  74                 bool operator != (const iterator &other) const { return this->mNode != other.mNode; }
  75
  76                 T & operator * () const { return mNode->mObject; }
  77
  78                 iterator & operator ++ () { mNode = mNode->get_next(); return *this; }  // preincrement
  79                 iterator operator ++ (int) { iterator tmp = *this; mNode = mNode->get_next(); return tmp; } // postincrement
  80
  81         private:
  82                 Node *          mNode;
  83         };
  84
  85         TThreadSafeList() { }
  86         ~TThreadSafeList()
  87         {
  88                 mActiveList.free_all();
  89                 mPendingList.free_all();
  90                 mFreeList.free_all();
  91         }
  92
  93         // These may be called on any thread
  94
  95         void    deferred_add(const T &obj)      // can be called on any thread
  96         {
  97                 Node *node = AllocNode();
  98                 node->mEventType = kAdd;
  99                 node->mObject = obj;
 100                 mPendingList.push_atomic(node);
 101                 //mPendingList.dump("pending after add");
 102         }
 103
 104         void    deferred_remove(const T &obj)   // can be called on any thread
 105         {
 106                 Node *node = AllocNode();
 107                 node->mEventType = kRemove;
 108                 node->mObject = obj;
 109                 mPendingList.push_atomic(node);
 110                 //mPendingList.dump("pending after remove");
 111         }
 112
 113         void    deferred_clear()                                        // can be called on any thread
 114         {
 115                 Node *node = AllocNode();
 116                 node->mEventType = kClear;
 117                 mPendingList.push_atomic(node);
 118         }
 119
 120         // These must be called from only one thread
 121
 122         void    update()                // must only be called from one thread
 123         {
 124                 NodeStack reversed;
 125                 Node *event, *node, *next;
 126                 bool workDone = false;
 127
 128                 // reverse the events so they are in order
 129                 event = mPendingList.pop_all();
 130                 while (event != NULL) {
 131                         next = event->mNext;
 132                         reversed.push_NA(event);
 133                         event = next;
 134                         workDone = true;
 135                 }
 136                 if (workDone) {
 137                         //reversed.dump("pending popped");
 138                         //mActiveList.dump("active before update");
 139
 140                         // now process them
 141                         while ((event = reversed.pop_NA()) != NULL) {
 142                                 switch (event->mEventType) {
 143                                 case kAdd:
 144                                         {
 145                                                 Node **pnode;
 146                                                 bool needToInsert = true;
 147                                                 for (pnode = mActiveList.phead(); *pnode != NULL; pnode = &node->mNext) {
 148                                                         node = *pnode;
 149                                                         if (node->mObject == event->mObject) {
 150                                                                 //printf("already active!!!\n");
 151                                                                 FreeNode(event);
 152                                                                 needToInsert = false;
 153                                                                 break;
 154                                                         }
 155                                                 }
 156                                                 if (needToInsert) {
 157                                                         // link the new event in at the end of the active list
 158                                                         *pnode = event;
 159                                                         event->mNext = NULL;
 160                                                 }
 161                                         }
 162                                         break;
 163                                 case kRemove:
 164                                         // find matching node in the active list, remove it
 165                                         for (Node **pnode = mActiveList.phead(); *pnode != NULL; ) {
 166                                                 node = *pnode;
 167                                                 if (node->mObject == event->mObject) {
 168                                                         *pnode = node->mNext;   // remove from linked list
 169                                                         FreeNode(node);
 170                                                         break;
 171                                                 }
 172                                                 pnode = &node->mNext;
 173                                         }
 174                                         // dispose the request node
 175                                         FreeNode(event);
 176                                         break;
 177                                 case kClear:
 178                                         for (node = mActiveList.head(); node != NULL; ) {
 179                                                 next = node->mNext;
 180                                                 FreeNode(node);
 181                                                 node = next;
 182                                         }
 183                                         FreeNode(event);
 184                                         break;
 185                                 default:
 186                                         //printf("invalid node type %d!\n", event->mEventType);
 187                                         break;
 188                                 }
 189                         }
 190                         //mActiveList.dump("active after update");
 191                 }
 192         }
 193
 194         iterator begin() const {
 195                 //mActiveList.dump("active at begin");
 196                 return iterator(mActiveList.head());
 197         }
 198         iterator end() const { return iterator(NULL); }
 199
 200
 201 private:
 202         Node *  AllocNode()
 203         {
 204                 Node *node = mFreeList.pop_atomic();
 205                 if (node == NULL)
 206                         node = (Node *)malloc(sizeof(Node));
 207                 return node;
 208         }
 209
 210         void    FreeNode(Node *node)
 211         {
 212                 mFreeList.push_atomic(node);
 213         }
 214
 215 private:
 216         class NodeStack : public TAtomicStack<Node> {
 217         public:
 218                 void free_all() {
 219                         Node *node;
 220                         while ((node = this->pop_NA()) != NULL)
 221                                 free(node);
 222                 }
 223
 224                 Node ** phead() { return &this->mHead; }
 225                 Node *  head() const { return this->mHead; }
 226
 227                 /*void  dump(char *label) const
 228                 {
 229                         char buf[1024];
 230                         int count = 0;
 231                         Node *node = mHead;
 232                         sprintf(buf, "%s:", label);
 233                         while (node != NULL) {
 234                                 sprintf(buf+strlen(buf), " %p/%d", node, node->mEventType);
 235                                 if (++count == 5) { sprintf(buf+strlen(buf), "..."); break; }
 236                                 node = node->mNext;
 237                         }
 238                         puts(buf);
 239                 }*/
 240
 241                 /*int size() const
 242                 {
 243                         int count = 0;
 244                         for (Node *node = mHead; node != NULL; node = node->mNext)
 245                                 ++count;
 246                         return count;
 247                 }*/
 248         };
 249
 250         NodeStack       mActiveList;    // what's actually in the container - only accessed on one thread
 251         NodeStack       mPendingList;   // add or remove requests - threadsafe
 252         NodeStack       mFreeList;              // free nodes for reuse - threadsafe
 253 };
 254
 255 #endif // __CAThreadSafeList_h__