Jamoma API  0.6.0.a19
TTQueue.h
1 /*
2  * Jamoma Foundation
3  * Copyright © 2011, Timothy Place
4  *
5  * License: This code is licensed under the terms of the "New BSD License"
6  * http://creativecommons.org/licenses/BSD/
7  */
8 
9 #ifndef __TT_QUEUE_H__
10 #define __TT_QUEUE_H__
11 
12 #include "TTBase.h"
13 #include "TTThread.h"
14 #include "TTList.h"
15 #include "TTObjectBase.h"
16 
17 
18 #if OLD
19 
20 /*
21  The old TTQueue class (circa 2008) was unused, and was designed specificaly to be used only for getting things
22  from an other thread onto the main thread.
23 
24  The new TTQueue class is more general, and is designed as a non-blocking circular buffer for getting
25  events from thread A to thread B where the neither of the threads are required to be the main thread.
26 
27  A specific use of this queue to get things to the main thread can be created and would then use this
28  newer version of the class.
29 */
30 
31 
32 
33 /****************************************************************************************************/
34 // Class Specification
35 
36 /**
37  The TTQueue class implements a message queue for TTBlue objects.
38 
39  Instead of sending a message directly to an object, it can be sent to the queue. The queue
40  will then send the message to the object from the queue's thread when the queue is serviced.
41 
42  The implementation uses a set of related lists; one for the object, one for the message, and
43  one for the value argument to the message.
44 */
45 class TTFOUNDATION_EXPORT TTQueue : public TTBase {
46 private:
47  TTThread* queueThread;
48  TTList* queueEventObjects;
49  TTList* queueEventMethods;
50  TTList* queueEventValues;
51  TTUInt16 throttle; ///< Maximum number of events to process in one shot
52 
53 public:
54  TTQueue();
55  virtual ~TTQueue();
56 
57  /** This is them main loop that runs the queue */
58  void* run();
59 
60  /** Add a call to the back of the queue. Will trigger the queue to be serviced if it isn't
61  already scheduled. */
62  void queueToBack(TTObject& anObject, TTSymbol aMessage, TTValue& aValue);
63  //void queueToFront(TTMethod method, TTValue& value);
64 };
65 
66 #else
67 
68 
69 /****************************************************************************************************/
70 // Class Specification
71 
72 
73 // The problem with this is that it won't be fast enough for audio because everything has to go
74 // through the message passing interface.
75 //
76 // But...
77 //
78 // The reader doesn't have to actually do that.
79 // It can just pull the value and then decide what to do with it.
80 // So maybe this is entirely overkill for the TTQueue, and is actually better off in the TTMainQueue
81 // implementation...
82 //
83 //class TTFOUNDATION_EXPORT TTQueueItem : public TTBase {
84 // TTObjectPtr mObject; // the object to which to send the message
85 // TTSymbolRef mKind; // 'attribute' or 'message'
86 // TTSymbolRef mName; // the name of the attribute or message
87 // TTValue mValue; // the arguments to send to the attribute or message
88 //};
89 
90 
91 /**
92  The TTQueue class implements a non-blocking circular queue for passing events across threads.
93  The items in the queue are TTValues.
94  What is contained in the TTValue will be specific to whatever is using the queue.
95 
96  This is based on "Efficient Adaptations of Non-Blocking Buffer for Event Message Communication
97  between Real-Time Threads" by Kim, Colmenares, and Rim from the proceedings of the 10th IEEE
98  International Symposium on Object and Component-Oriented Real-Time Distributed Computing.
99 
100  One important difference is that we copy data at both the insert() and the read(), rather than
101  referencing a pointer at insert() and copying only at read().
102  The reason for this is that we could easily put something on the queue (i.e. a reference to an object)
103  that is temporary (alloc'd on the stack, for example) and then disappears prior to being serviced.
104 
105 
106  There are other implementations of a lock-free queue/FIFO that should be referenced:
107 
108 
109  1. PortAudio (pa_ringbuffer.h/.c) does things a little bit differently, for example.
110  Similar to what we have done, the memory for the items in the buffer is owned by the buffer.
111  The counters are not implemented with OS-level atomic operations, but the reads and writes
112  into the buffer are done using OS-level memory barriers.
113  Question: Because of our use of the atomic operations on the counters, do we still need to use memory barriers?
114  Reference: http://www.rossbencina.com/code/lockfree
115 
116 
117  2. SuperCollider is more like a hybrid of the PortAudio approach and the NBB implementation
118  on which this class is currently based. The implementation can be found in common/Headers/server/MsgFifo.h.
119  One cool thing is that it uses a template class in C++ so that the queue could hold any type of items, rather than
120  restricted to a type or even a container like we do with TTValue.
121 
122  TODO: we should do this template thing like SC
123 
124  SC does not have the busy/retry ability that we have, but it also might be quicker because there is only one
125  atomic increment at write instead of two.
126  Instead of using an atomic increment, however, it is using OSAtomicCompareAndSwap32Barrier -- apparently for legacy reasons.
127 
128  Additionally it does in enforce a memory barrier on the Mac by issuing __sync_synchronize() in the
129  equivalents of both insert() and read().
130 
131  Unlike NBB, based on a first reading of the code, it looks like it uses shared references rather than copying by value.
132  It looks like this is true for *both* read (perform) and insert (write), which means that the heap usage is not
133  kept isolated as argued to be the most important factor in the NBB paper.
134  */
135 class TTFOUNDATION_EXPORT TTQueue {
136 private:
137  // Counters used to ensure that the producer (calling insert()) and the consumer (calling read())
138  // are always accessing different slots in the circular buffer
139 
140  // counters must be *aligned* single-word integers
141 
142  TTAtomicUInt mUpdateCounter; // UC -- only modified by the producer
143  TTAtomicUInt mAcknowledgementCounter; // AC -- only modified by the consumer
144  TTVector mBuffer; // Using a std::vector of TTValues right now -- not sure this is best choice?
145  TTUInt32 mSize; // count of slots in mBuffer -- should be power of 2, will use as a bitmask
146  TTUInt32 mTwiceSize; // 2 * mBufferSize, cached for performance
147 
148  enum InsertStatus {
149  kBufferInsertSuccessful = 0,
150  kBufferFull,
151  kBufferFullButCurrentlyReading
152  };
153 
154  enum ReadStatus {
155  kBufferReadSuccessful = 0,
156  kBufferEmpty,
157  kBufferEmptyButCurrentlyWriting
158  };
159 
160 
161 public:
162  TTQueue();
163  virtual ~TTQueue();
164 
165  /** attribute accessor */
166  TTErr resize(TTUInt32 aNewSize);
167  TTErr size(TTUInt32& returnedSize);
168 
169  /** add an item to the queue. */
170  InsertStatus insert(const TTValue& anItem);
171 
172  /** get the next event and pop it from the queue. */
173  ReadStatus read(TTValue& returnedItem);
174 
175 
176 };
177 
178 
179 
180 #endif
181 
182 
183 #endif // __TT_QUEUE_H__
std::uint16_t TTUInt16
16 bit unsigned integer
Definition: TTBase.h:176
The Jamoma Object Base Class.
Create and use Jamoma object instances.
Definition: TTObject.h:29
Jamoma's lowest-level base class and related infrastructure.
The TTSymbol class is used to represent a string and efficiently pass and compare that string...
Definition: TTSymbol.h:26
TTErr
Jamoma Error Codes Enumeration of error codes that might be returned by any of the TTBlue functions a...
Definition: TTBase.h:342
std::uint32_t TTUInt32
32 bit unsigned integer
Definition: TTBase.h:178
[doxygenAppendixC_copyExample]
Definition: TTValue.h:34
The TTQueue class implements a non-blocking circular queue for passing events across threads...
Definition: TTQueue.h:135