Jamoma API  0.6.0.a19
TTFifo.h
1 /*
2  * TTFoundation First-in/First-out buffer
3  * Copyright 2011 by 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_FIFO_H__
10 #define __TT_FIFO_H__
11 
12 #include "TTBase.h"
13 #include "TTLimits.h"
14 
15 
16 /** First-in/First-out buffer that is non-blocking and thread-safe for writing from a single thread
17  and reading from another (possibly different) single thread.
18 
19  @seealso TTQueue
20  */
21 
22 template<class T>
23 class TTFifo {
24 
25 protected:
26 
27  typedef T TTFifoItem;
28  typedef std::vector<TTFifoItem> TTFifoItemVector;
29  //typedef TTFifoItemVector::iterator TTFifoItemIter;
30 
31  TTAtomicUInt mUpdateCounter; ///< UC -- only modified by the producer
32  TTAtomicUInt mAcknowledgementCounter; ///< AC -- only modified by the consumer
33  TTUInt32 mSlotCount; ///< count of slots in mBuffer -- should be power of 2, will use as a bitmask
34  TTUInt32 mDoubleSlotCount; ///< 2 * mBufferSize, cached for performance
35  TTFifoItemVector mSlots;
36 
37 public:
38 
39  TTFifo(int initialSlotCount)
40  {
41  resize(initialSlotCount);
42  }
43 
44 
45  virtual ~TTFifo()
46  {
47 
48  }
49 
50 
51  /** Change the number of slots in the circular queue.
52  This method should be used with extreme caution as it is not thread-safe
53  with regards to the push() and pop() methods.
54 
55  @param newSlotCount Must be a power of two.
56  If the argument provided is not a power-of-two,
57  it will be increased to the next-higher power of two upon return.
58  */
59  void resize(TTUInt32& newSlotCount)
60  {
61  TTLimitPowerOfTwo(newSlotCount);
62 
63  mSlotCount = newSlotCount;
64  mDoubleSlotCount = newSlotCount*2;
65  mSlots.resize(mDoubleSlotCount);
66  }
67 
68 
69  int size()
70  {
71  return mSlotCount;
72  }
73 
74 
75  enum TTFifoWriteStatus {
76  kBufferWriteSuccessful = 0,
77  kBufferFull,
78  kBufferFullButCurrentlyReading
79  };
80 
81 
82  /** Copy an item into the queue. */
83  TTFifoWriteStatus push(const T& item)
84  {
85  TTUInt32 lastUpdateCounter = mUpdateCounter;
86  TTUInt32 lastAcknowledgementCounter = mAcknowledgementCounter; // this read should be atomic
87  TTInt32 counterDifference = lastUpdateCounter - lastAcknowledgementCounter;
88  TTInt32 index;
89  TTInt32 twicesize = mDoubleSlotCount;
90  TTInt32 size = mSlotCount;
91 
92  if (counterDifference == twicesize)
93  return kBufferFull;
94  if (counterDifference == twicesize-1)
95  return kBufferFullButCurrentlyReading;
96 
97  TTAtomicIncrementWithBarrier(mUpdateCounter); // now odd, indicating that we are in the middle of an insertion
98 
99  index = (lastUpdateCounter/2) & (size-1); // fast modulo for power of 2
100  mSlots[index] = item; // copy
101 
102  TTAtomicIncrementWithBarrier(mUpdateCounter); // now even, indicating that the insertion has completed
103  return kBufferWriteSuccessful;
104  }
105 
106 
107  enum TTFifoReadStatus {
108  kBufferReadSuccessful = 0,
109  kBufferEmpty,
110  kBufferEmptyButCurrentlyWriting
111  };
112 
113 
114  /** Copy the next item and pop it from the queue. */
115  TTFifoReadStatus pop(T& item)
116  {
117  TTUInt32 lastUpdateCounter = mUpdateCounter; // this read should be atomic
118  TTUInt32 lastAcknowledgementCounter = mAcknowledgementCounter;
119  TTInt32 index;
120  TTInt32 size = mSlotCount;
121 
122  if (lastUpdateCounter == lastAcknowledgementCounter)
123  return kBufferEmpty;
124  if (lastUpdateCounter - lastAcknowledgementCounter == 1)
125  return kBufferEmptyButCurrentlyWriting;
126 
127  TTAtomicIncrementWithBarrier(mAcknowledgementCounter); // now odd, indicating that we are in the middle of a read
128 
129  index = (lastAcknowledgementCounter/2) & (size-1); // fast modulo for power of 2
130  item = mSlots[index]; // copy
131 
132  TTAtomicIncrementWithBarrier(mAcknowledgementCounter); // now even, indicating that the read has completed
133  return kBufferReadSuccessful;
134  }
135 
136 };
137 
138 
139 #endif // __TT_FIFO_H__
140 
TTFifoWriteStatus push(const T &item)
Copy an item into the queue.
Definition: TTFifo.h:83
Limiting and Constraining Utilities.
TTFifoReadStatus pop(T &item)
Copy the next item and pop it from the queue.
Definition: TTFifo.h:115
void resize(TTUInt32 &newSlotCount)
Change the number of slots in the circular queue.
Definition: TTFifo.h:59
Jamoma's lowest-level base class and related infrastructure.
std::int32_t TTInt32
32 bit signed integer
Definition: TTBase.h:177
TTAtomicUInt mUpdateCounter
UC – only modified by the producer.
Definition: TTFifo.h:31
TTAtomicUInt mAcknowledgementCounter
AC – only modified by the consumer.
Definition: TTFifo.h:32
std::uint32_t TTUInt32
32 bit unsigned integer
Definition: TTBase.h:178
First-in/First-out buffer that is non-blocking and thread-safe for writing from a single thread and r...
Definition: TTFifo.h:23
TTUInt32 mSlotCount
count of slots in mBuffer – should be power of 2, will use as a bitmask
Definition: TTFifo.h:33
TTUInt32 mDoubleSlotCount
2 * mBufferSize, cached for performance
Definition: TTFifo.h:34