1// tRingBuffer.h 
2// 
3// A ring (or circular) buffer works like a capacitor in that it can temporarily absorb the shock of a large influx 
4// of data, but needs to be emptied eventually. The read rate must on average be >= to the write rate if you want to 
5// avoid a stall. Fortunately, unlike real capacitors, they do not leak information over time. 
6//  
7// Copyright (c) 2016, 2017 Tristan Grimmer. 
8// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
9// granted, provided that the above copyright notice and this permission notice appear in all copies. 
10// 
11// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
12// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
13// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
14// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
15// PERFORMANCE OF THIS SOFTWARE. 
16 
17#pragma once 
18#include <Foundation/tAssert.h> 
19#include <Foundation/tStandard.h> 
20 
21 
22// tRingBuffer allows you to append one or more items (of user-specified type) to the tail of the ring, remove one or 
23// more items from the head of the ring, and randomly access any stored item for read/write. 
24template<typename T> class tRingBuffer 
25{  
26public: 
27 tRingBuffer() : OwnsBuffer(false), Capacity(0), Buffer(nullptr), Head(nullptr), Tail(nullptr) { } 
28 tRingBuffer(int capacity) /* Buffer is owned by tRingBuffer. */ : OwnsBuffer(false), Capacity(0), Buffer(nullptr), Head(nullptr), Tail(nullptr) { Set(capacity); } 
29 tRingBuffer(T* const buffer, int capacity) /* Buffer ownership is external. */ : OwnsBuffer(false), Capacity(0), Buffer(nullptr), Head(nullptr), Tail(nullptr) { Set(buffer, capacity); } 
30 
31 void Set(int capacity); // Buffer is owned by tRingBuffer. 
32 void Set(T* const buffer, int capacity); // Buffer is owned by tRingBuffer. 
33 void Clear(); 
34 bool IsValid() const { return Buffer ? true : false; } 
35 
36 int GetNumItems() const; 
37 int GetCapacity() const { return Capacity; } 
38 int GetRoom() const /* Returns how many items can be successfully appended. */ { return Capacity - GetNumItems(); } 
39 bool IsEmpty() const /* An invalid ring buffer always returns true. */ { return !Buffer || ((Tail != nullptr) && (Head == nullptr)); } 
40 bool IsFull() const /* An invalid ring buffer always returns true. */ { return !Buffer || ((Head != nullptr) && (Tail == nullptr)); } 
41 
42 // There are two versions each of append and remove. One for single items and one for multiple. The multiple item 
43 // versions are faster than multiple single item appends or removes because they perform the operation with either a 
44 // single or double tight loop of item copying. If you know the type T can be memory copied (POD types and such), 
45 // set useMemCpy to true for increased performance. Returns success for the single item versions, and number items 
46 // appended or removed for the multiple item versions. 
47 bool Append(const T& item); 
48 int Append(const T* items, int numItems, bool useMemCpy = false); 
49 bool Remove(T& item); 
50 int Remove(T* items, int numItems, bool useMemCpy = false); 
51 
52 // These two functions are for testing and verification and need not be called for production use. They return -1 
53 // if the head or tail is invalid. 
54 int GetHeadIndex() const { if (!Head) return -1; return int(Head - Buffer); } 
55 int GetTailIndex() const { if (!Tail) return -1; return int(Tail - Buffer); } 
56 
57private: 
58 bool OwnsBuffer; // True if this object owns the buffer. 
59 int Capacity; // Maximum number of items that may be stored. 
60 T* Buffer; // If null the whole object is invalid. 
61 
62 // There are few choices regarding head and tail here. I wanted to use the full capacity rather than making 
63 // head == tail represent 'empty' or something. In the following implementation the head always represents the read 
64 // location, and is null if nothing can be read. The tail always represents the write location, and is null if 
65 // nothing can be written. As such, if buffer is null (invalid ring buffer), both head and tail are null. For valid 
66 // ring buffers the following is true. An empty buffer has a non-null tail and a null head. That is, you can write but 
67 // not read. A full buffer has a non-null head and a null tail. That is, you can read but not write. eg. 
68 // - - - - - - 0 items. 
69 // T H=null 
70 // 
71 // - - X - - - 1 item. 
72 // H T 
73 // 
74 // - - X X - - 2 items. 
75 // H T 
76 // 
77 // X - X X X X 5 items. 
78 // T H 
79 // 
80 // X X X X X X 6 items (full). 
81 // H T=null. 
82 T* Head; // Points to where you can read from. 
83 T* Tail; // Points to where you can write to. 
84}; 
85template<typename T> using tRing = tRingBuffer<T>; 
86 
87 
88// Implementation below this line. 
89 
90 
91template<typename T> inline void tRingBuffer<T>::Set(int capacity) 
92{ 
93 Clear(); 
94 tAssert(capacity > 0); 
95 Capacity = capacity; 
96 Buffer = new T[capacity]; 
97 
98 // We're empty so read head is null, and write tail is valid. 
99 Tail = Buffer; 
100 OwnsBuffer = true; 
101} 
102 
103 
104template<typename T> inline void tRingBuffer<T>::Set(T* const buffer, int capacity) 
105{ 
106 Clear(); 
107 tAssert((capacity > 0) && buffer); 
108 Capacity = capacity; 
109 Buffer = buffer; 
110 Tail = Buffer; 
111 OwnsBuffer = false; 
112} 
113 
114 
115template<typename T> inline void tRingBuffer<T>::Clear() 
116{ 
117 if (OwnsBuffer) 
118 delete Buffer; 
119 Buffer = nullptr; 
120 Head = nullptr; 
121 Tail = nullptr; 
122 OwnsBuffer = false; 
123 Capacity = 0; 
124} 
125 
126 
127template<typename T> inline int tRingBuffer<T>::GetNumItems() const 
128{ 
129 if (!Head) 
130 return 0; 
131 
132 if (!Tail) 
133 return Capacity; 
134 
135 if (Head > Tail) 
136 return Capacity - int(Head - Tail); 
137  
138 return int(Tail - Head); 
139} 
140 
141 
142template<typename T> inline bool tRingBuffer<T>::Append(const T& item) 
143{ 
144 if (!Tail) 
145 return false; 
146 
147 *Tail = item; 
148 if (!Head) 
149 Head = Tail; 
150 
151 Tail++; 
152 if (Tail == Buffer+Capacity) 
153 Tail = Buffer; 
154 
155 // Are we full? 
156 if (Tail == Head) 
157 Tail = nullptr; 
158 
159 return true; 
160} 
161 
162 
163template<typename T> inline int tRingBuffer<T>::Append(const T* items, int numItems, bool useMemCpy) 
164{ 
165 // This could have been written naively by just sequentially calling the Append(T) above. The reason 
166 // it is so complicated is because it organized the writes into two separate tight copy loops. 
167 int room = GetRoom(); 
168 int numAppended = 0; 
169 if (!items || (numItems <= 0) || (room <= 0)) 
170 return numAppended; 
171 
172 int numToAppend = (numItems < room) ? numItems : room; 
173 
174 // We may need two memcpy/write-loops if we go past the end. 
175 int loopAvail = 0; 
176 if (Tail > Head) // This works if pHead is nullptr as well. 
177 loopAvail = int((Buffer+Capacity) - Tail); 
178 int itemCount = (numToAppend < loopAvail) ? numToAppend : loopAvail; 
179 
180 // Copy loop 1. 
181 if (useMemCpy) 
182 tStd::tMemcpy(Tail, items, itemCount*sizeof(T)); 
183 else 
184 for (int i = 0; i < itemCount; i++) 
185 *(Tail+i) = *(items+i); 
186 
187 if (!Head && itemCount) 
188 Head = Tail; 
189 
190 numAppended += itemCount; 
191 Tail += itemCount; 
192 if (Tail == Buffer+Capacity) 
193 Tail = Buffer; 
194 
195 // Are we full? 
196 if (Tail == Head) 
197 { 
198 Tail = nullptr; 
199 return numAppended; 
200 } 
201 
202 numToAppend -= itemCount; 
203 if (numToAppend == 0) 
204 return numAppended; 
205 
206 // At this point we still have more to append and we have looped around into 'tail < head' territory. 
207 items += numAppended; 
208 loopAvail = int(Head - Tail); 
209 itemCount = (numToAppend < loopAvail) ? numToAppend : loopAvail; 
210 
211 // Copy loop 2. 
212 if (useMemCpy) 
213 tStd::tMemcpy(Buffer, items, itemCount*sizeof(T)); 
214 else 
215 for (int i = 0; i < itemCount; i++) 
216 *(Buffer+i) = *(items+i); 
217 
218 if (!Head && itemCount) 
219 Head = Tail; 
220 
221 numAppended += itemCount; 
222 Tail += itemCount; 
223 
224 // Are we full? 
225 if (Tail == Head) 
226 Tail = nullptr; 
227 
228 return numAppended; 
229} 
230 
231 
232template<typename T> inline bool tRingBuffer<T>::Remove(T& item) 
233{ 
234 if (!Head) 
235 return false; 
236 
237 item = *Head; 
238 if (!Tail) 
239 Tail = Head; 
240 
241 Head++; 
242 if (Head == Buffer+Capacity) 
243 Head = Buffer; 
244 
245 // Are we empty? 
246 if (Head == Tail) 
247 Head = nullptr; 
248 
249 return true; 
250} 
251 
252 
253template<typename T> inline int tRingBuffer<T>::Remove(T* items, int numItems, bool useMemCpy) 
254{ 
255 // This could have been written naively by just sequentially calling the Remove(T) above. The reason 
256 // it is so complicated is because it organized the writes into two separate tight copy loops. 
257 int avail = GetNumItems(); 
258 int numRemoved = 0; 
259 if (!items || (numItems <= 0) || (avail <= 0)) 
260 return numRemoved; 
261 
262 int numToRemove = (numItems < avail) ? numItems : avail; 
263 
264 // We may need two memcpy/write-loops if we go past the end. 
265 int loopAvail = 0; 
266 if (Head > Tail) // This works if pTail is nullptr as well. 
267 loopAvail = int((Buffer+Capacity) - Head); 
268 int itemCount = (numToRemove < loopAvail) ? numToRemove : loopAvail; 
269 
270 // Copy loop 1. 
271 if (useMemCpy) 
272 tStd::tMemcpy(items, Head, itemCount*sizeof(T)); 
273 else 
274 for (int i = 0; i < itemCount; i++) 
275 *(items+i) = *(Head+i); 
276 
277 if (!Tail && itemCount) 
278 Tail = Head; 
279 
280 numRemoved += itemCount; 
281 Head += itemCount; 
282 if (Head == Buffer+Capacity) 
283 Head = Buffer; 
284 
285 // Are we empty? 
286 if (Head == Tail) 
287 { 
288 Head = nullptr; 
289 return numRemoved; 
290 } 
291 
292 numToRemove -= itemCount; 
293 if (numToRemove == 0) 
294 return numRemoved; 
295 
296 // At this point we still have more to remove and we have looped around into 'head < tail' territory. 
297 items += numRemoved; 
298 loopAvail = int(Tail - Head); 
299 itemCount = (numToRemove < loopAvail) ? numToRemove : loopAvail; 
300 
301 // Copy loop 2. 
302 if (useMemCpy) 
303 tStd::tMemcpy(items, Buffer, itemCount*sizeof(T)); 
304 else 
305 for (int i = 0; i < itemCount; i++) 
306 *(items+i) = *(Buffer+i); 
307 
308 if (!Tail && itemCount) 
309 Tail = Head; 
310 
311 numRemoved += itemCount; 
312 Head += itemCount; 
313 
314 // Are we empty? 
315 if (Head == Tail) 
316 Head = nullptr; 
317 
318 return numRemoved; 
319} 
320