1 /* 2 File: CAThreadSafeList.h 3 Abstract: Part of CoreAudio Utility Classes 4 Version: 1.1 5 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. 12 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. 28 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. 34 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. 43 44 Copyright (C) 2014 Apple Inc. All Rights Reserved. 45 46 */ 47 #ifndef __CAThreadSafeList_h__ 48 #define __CAThreadSafeList_h__ 49 50 #include "CAAtomicStack.h" 51 52 // linked list of T's 53 // T must define operator == 54 template <class T> 55 class TThreadSafeList { 56 private: 57 enum EEventType { kAdd, kRemove, kClear }; 58 class Node { 59 public: 60 Node * mNext; 61 EEventType mEventType; 62 T mObject; 63 next()64 Node *& next() { return mNext; } 65 }; 66 67 public: 68 class iterator { 69 public: iterator()70 iterator() { } iterator(Node * n)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->next(); return *this; } // preincrement 79 iterator operator ++ (int) { iterator tmp = *this; mNode = mNode->next(); return tmp; } // postincrement 80 81 private: 82 Node * mNode; 83 }; 84 TThreadSafeList()85 TThreadSafeList() { } ~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 deferred_add(const T & obj)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 deferred_remove(const T & obj)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 deferred_clear()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 update()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 begin()194 iterator begin() const { 195 //mActiveList.dump("active at begin"); 196 return iterator(mActiveList.head()); 197 } end()198 iterator end() const { return iterator(NULL); } 199 200 201 private: AllocNode()202 Node * AllocNode() 203 { 204 Node *node = mFreeList.pop_atomic(); 205 if (node == NULL) 206 node = (Node *)CA_malloc(sizeof(Node)); 207 return node; 208 } 209 FreeNode(Node * node)210 void FreeNode(Node *node) 211 { 212 mFreeList.push_atomic(node); 213 } 214 215 private: 216 class NodeStack : public TAtomicStack<Node> { 217 public: free_all()218 void free_all() { 219 Node *node; 220 while ((node = this->pop_NA()) != NULL) 221 free(node); 222 } 223 phead()224 Node ** phead() { return &this->mHead; } head()225 Node * head() const { return this->mHead; } 226 }; 227 228 NodeStack mActiveList; // what's actually in the container - only accessed on one thread 229 NodeStack mPendingList; // add or remove requests - threadsafe 230 NodeStack mFreeList; // free nodes for reuse - threadsafe 231 }; 232 233 #endif // __CAThreadSafeList_h__ 234