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