HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NET_CircularBuffer.h
Go to the documentation of this file.
1 /*
2  * POPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: NET_CircularBuffer.h
7  *
8  * COMMENTS:
9  *
10  */
11 
12 #ifndef __NET_CIRCULARBUFFER_H__
13 #define __NET_CIRCULARBUFFER_H__
14 
15 #include "NET_API.h"
16 
17 #include <UT/UT_Array.h>
18 #include <UT/UT_Format.h>
19 #include <UT/UT_Debug.h>
20 
21 #include <SYS/SYS_Types.h>
22 
23 #include <utility>
24 #include <cstring>
25 
26 template <typename T>
28 {
29 public:
30  using index_t = exint;
31  using range_t = std::pair<T*, int>;
32  using const_range_t = std::pair<const T*, int>;
33 
35  {
36  clear();
37  }
38 
39  template <typename U>
41  {
42  public:
44 
45  base_iterator(const range_t& one, const range_t& two) :
46  myArrayOne(one), myArrayTwo(two), myCurrent(0)
47  {}
48  base_iterator(exint current) :
49  myArrayOne(), myArrayTwo(), myCurrent(current)
50  {}
51 
52  U* operator->() const
53  {
54  return this->item_(myCurrent);
55  }
56  U& operator*() const
57  {
58  return *(this->item_(myCurrent));
59  }
60  U& operator[](exint idx) const
61  {
62  return *(this->item_(idx));
63  }
65  {
66  ++myCurrent;
67  return *this;
68  }
70  {
71  base_iterator tmp = *this;
72  ++myCurrent;
73  return tmp;
74  }
76  {
77  --myCurrent;
78  return *this;
79  }
81  {
82  base_iterator tmp = *this;
83  --myCurrent;
84  return tmp;
85  }
87  {
88  myCurrent += n;
89  return *this;
90  }
92  {
93  base_iterator tmp = *this;
94  tmp.myCurrent += n;
95  return tmp;
96  }
98  {
99  return (*this) += (-n);
100  }
102  {
103  return (*this) + (-n);
104  }
105  bool operator==(const base_iterator& it) const
106  {
107  return myCurrent == it.myCurrent;
108  }
109  bool operator!=(const base_iterator& it) const { return !(*this == it); }
110  bool operator<(const base_iterator& it) const
111  {
112  return myCurrent < it.myCurrent;
113  }
114  bool operator<=(const base_iterator& it) const
115  {
116  return !(it < *this);
117  }
118  bool operator>(const base_iterator& it) const
119  {
120  return it < *this;
121  }
122  bool operator>=(const base_iterator& it) const
123  {
124  return !(*this < it);
125  }
126  exint operator-(const base_iterator& it) const
127  {
128  return myCurrent - it.myCurrent;
129  }
130 
131  private:
132  U* item_(exint idx) const
133  {
134  exint count = myArrayOne.second + myArrayTwo.second;
135  UT_ASSERT(myCurrent <= count);
136 
137  if (myCurrent > count)
138  return nullptr;
139 
140  if (myCurrent > myArrayOne.second)
141  {
142  exint idx = myCurrent - myArrayOne.second;
143  return myArrayTwo.first + idx;
144  }
145 
146  return myArrayOne.first + myCurrent;
147  }
148 
149  range_t myArrayOne;
150  range_t myArrayTwo;
151  exint myCurrent;
152  };
153 
154  using iterator = base_iterator<T>;
155  using const_iterator = base_iterator<const T>;
156 
157  /// @brief The first element in the buffer. Undefined behaviour if the buffer
158  /// is empty.
159  ///
160  /// @return The first element in the buffer
161  T& front() { return myData[firstIndex_()]; }
162  /// @brief The last element in the buffer. Undefined behaviour if the buffer
163  /// is empty.
164  ///
165  /// @return The last element in the buffer. Undefined behaviour if the buffer
166  /// is empty.
167  T& back() { return myData[lastIndex_()]; }
168  /// @brief The first element in the buffer. Undefined behaviour if the buffer
169  /// is empty.
170  ///
171  /// @return The first element in the buffer.
172  const T& front() const { return myData[firstIndex_()]; }
173  /// @brief The last element in the buffer. Undefined behaviour if the buffer
174  /// is empty.
175  ///
176  /// @return The last element in the buffer.
177  const T& back() const { return myData[lastIndex_()]; }
178 
179  /// @brief The begin iterator for the buffer.
180  ///
181  /// @return The begin iterator
183  /// @brief The end iterator for the buffer.
184  ///
185  /// @return The end iterator.
186  iterator end() { return iterator(size()); }
187  /// @brief The begin const iterator for the buffer.
188  ///
189  /// @return The begin const iterator.
191  {
192  return const_base_iterator(arrayOne(), arrayTwo());
193  }
194  /// @brief The end const iterator for the buffer.
195  ///
196  /// @return The end const iterator.
198  {
199  return const_base_iterator(size());
200  }
201  /// @brief Retrieve element at provided index.
202  ///
203  /// @param index The index to retrieve the element at.
204  ///
205  /// @return The element at index.
207  {
208  UT_ASSERT_P(!isEmpty());
209  index_t i = (firstIndex_() + index) % capacity();
210  return myData[i];
211  }
212  /// @brief Retrieve element at provided index.
213  ///
214  /// @param index The index to retrieve the element at.
215  ///
216  /// @return The element at index.
217  const T& operator[](int index) const
218  {
219  UT_ASSERT_P(!isEmpty());
220  index_t i = (firstIndex_() + index) % capacity();
221  return myData[i];
222  }
223 
224  /// @brief Place a single element onto the back of the buffer.
225  ///
226  /// @param data
227  void push(const T& data)
228  {
229  push(&data, 1);
230  }
231  /// @brief Place an array of elements onto the back of the buffer.
232  ///
233  /// @param data The array of elements to add to the buffer.
234  /// @param count The number of elements in the array to add.
235  void push(const T* data, exint count)
236  {
237  growIfNeeded_(count);
238 
239  UT_ASSERT(!isFull());
240  UT_ASSERT(size() + count <= maxSize());
241 
242  exint start_idx = mask_(myWrite);
243  exint end_idx = start_idx + count;
244 
245  T* start = myData.getArray() + start_idx;
246  const T* data_start = data;
247 
248  exint full_count = count;
249 
250  // Check if we need to split up the copies into two. The first being
251  // at the tail end and the second being at the beginning of the
252  // underlying array.
253  if (end_idx > capacity())
254  {
255  // Grab the chunk of data to copy
256  exint chunk = capacity() - start_idx;
257  UT_ASSERT(chunk > 0);
258  std::memcpy(start, data_start, sizeof(T) * chunk);
259 
260  full_count -= chunk;
261  start = myData.data();
262  data_start += chunk;
263  }
264 
265  // If there is anything else that needs to be copied do that at the
266  // beginning of the underlying array.
267  if (full_count > 0)
268  {
269  std::memcpy(start, data_start, sizeof(T) * full_count);
270  }
271 
272  incrementWrite_(count);
273  }
274  /// @brief Remove a single element from the front of the buffer.
275  ///
276  /// @return The element removed.
277  T pop()
278  {
279  UT_ASSERT(!isEmpty());
280  T data = myData[myRead];
281  incrementRead_(1);
282  return data;
283  }
284  /// @brief Remove multiple elements from the front of the buffer.
285  ///
286  /// @param count The number of elements to remove.
287  void pop(int count)
288  {
289  incrementRead_(count);
290  }
291 
292  /// @brief Is the buffer currently full.
293  ///
294  /// @return True if the buffer is currently full. Any new push() calls will
295  /// allocate more space.
296  bool isFull() const { return increment_(myWrite) == myRead; }
297  /// @brief Is the buffer currently empty.
298  ///
299  /// @return True if the buffer currently does not store any elements.
300  bool isEmpty() const { return myRead == myWrite; }
301  /// @brief The number of elements currently stored in the buffer.
302  ///
303  /// @return The current size of the buffer.
304  exint size() const
305  {
306  if (myWrite >= myRead)
307  return myWrite - myRead;
308  return (capacity() - myRead) + myWrite;
309  }
310  /// @brief The number of elements currently stored in the buffer.
311  ///
312  /// @return The current size of the buffer.
313  int entries() const { return size(); }
314  /// @brief The current capacity of the buffer.
315  ///
316  /// @return The total capacity of the buffer.
317  exint capacity() const { return myData.capacity(); }
318  /// @brief The absolute maximum size of the buffer. Use size() if you need
319  /// to know the current size of the buffer.
320  ///
321  /// @return The maximum size of the buffer.
323 
324  /// @brief A circular buffer can wrap around in memory. This is the first
325  /// array of continious memory. If the buffer is not currently wrapped then
326  /// the entire buffer will be present in this array and the second array
327  /// will be empty.
328  ///
329  /// @return A pair of the start of the array and the length of the first
330  /// array.
332  {
333  exint start = firstIndex_();
334  exint end = mask_(myWrite);
335  if (end < start)
336  end = capacity();
337 
338  range_t result = std::make_pair(myData.data() + start, end - start);
339  return result;
340  }
341  /// @brief Holds information about the second array of contigous data. See
342  /// arrayOne() for further details.
343  ///
344  /// @return A pair of that start of the array and the length of the
345  /// second array.
347  {
348  exint first_index = firstIndex_();
349  exint last_index = mask_(myWrite);
350  if (isEmpty() || last_index >= first_index)
351  return std::make_pair(nullptr, 0);
352 
353  range_t result = std::make_pair(myData.data(), mask_(myWrite));
354  return result;
355  }
356  /// @brief Const variant of the arrayOne().
357  ///
358  /// @return See arrayOne()
360  {
361  return arrayOne();
362  }
363  /// @brief Const variant of the arrayTwo().
364  ///
365  /// @return See arrayTwo()
367  {
368  return arrayTwo();
369  }
370  /// @brief Completely clear the buffer. This will free any currently
371  /// allocated data.
372  void clear()
373  {
374  myRead = 0;
375  myWrite = 0;
376  myData.setCapacity(0);
377  }
378 
379  /// @brief Printout debug information about this buffer.
380  void debug() const
381  {
382  UTformat(stderr, "Capacity: {}\n", capacity());
383  UTformat(stderr, "Size: {}\n", size());
384  UTformat(stderr, "Read: {} idx={}\n", myRead, mask_(myRead));
385  UTformat(stderr, "Write: {} idx={}\n", myWrite, mask_(myWrite));
386  }
387 private:
388  /// @brief Calculate the index of a value.
389  ///
390  /// @param value The value to calculate the index.
391  ///
392  /// @return The index into the buffer.
393  index_t mask_(index_t value) const
394  {
395  exint last = myData.capacity() - 1;
396  if (value > last)
397  return value - last - 1;
398  return value;
399  }
400  /// @brief Check if we need to grow our buffer. This will check against the
401  /// current size and the extra data we need for some operation. If the extra
402  /// data we need isnt available we bump the size of our buffer.
403  ///
404  /// @param count The amount of data we need available for some operation.
405  void growIfNeeded_(index_t count)
406  {
407  if (size() + count >= capacity())
408  {
409  exint new_size = UTbumpAlloc(size() + count);
410  myData.setCapacity(new_size);
411  myData.entries(new_size);
412  }
413  }
414  /// @brief The first index into our buffer.
415  ///
416  /// @return The index of the first element in our buffer.
417  index_t firstIndex_() const
418  {
419  if (isEmpty())
420  return 0;
421 
422  return mask_(myRead);
423  }
424  /// @brief The last index into our buffer. This is the last index of an
425  /// element and not the last index of our buffer. Use mask_(myWrite) if you
426  /// need the first invalid index into the buffer (used for range iterators).
427  ///
428  /// @return The last index of a valid element in the buffer.
429  index_t lastIndex_() const
430  {
431  if (isEmpty())
432  return 0;
433 
434  return mask_(myWrite - 1);
435  }
436  index_t increment_(index_t index, index_t count = 1) const
437  {
438  return mask_(index + count);
439  }
440  void incrementRead_(index_t count)
441  {
442  myRead = increment_(myRead, count);
443  }
444  void incrementWrite_(index_t count)
445  {
446  myWrite = increment_(myWrite, count);
447  }
448 
449  UT_Array<T> myData;
450  index_t myRead;
451  index_t myWrite;
452 };
453 
454 #endif // __NET_CIRCULARBUFFER_H__
455 
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
base_iterator operator+(exint n) const
void debug() const
Printout debug information about this buffer.
bool operator>(const base_iterator &it) const
const_range_t arrayTwo() const
Const variant of the arrayTwo().
bool operator!=(const base_iterator &it) const
void clear()
Completely clear the buffer. This will free any currently allocated data.
T & back()
The last element in the buffer. Undefined behaviour if the buffer is empty.
GLuint index
Definition: glew.h:1814
const_iterator begin() const
The begin const iterator for the buffer.
bool operator<(const base_iterator &it) const
int64 exint
Definition: SYS_Types.h:125
iterator end()
The end iterator for the buffer.
T pop()
Remove a single element from the front of the buffer.
std::pair< const char *, int > const_range_t
range_t arrayTwo()
Holds information about the second array of contigous data. See arrayOne() for further details...
void push(const T &data)
Place a single element onto the back of the buffer.
bool isEmpty() const
Is the buffer currently empty.
void push(const T *data, exint count)
Place an array of elements onto the back of the buffer.
const T & operator[](int index) const
Retrieve element at provided index.
base_iterator & operator+=(exint n)
base_iterator< char > iterator
base_iterator operator-(exint n) const
const_iterator end() const
The end const iterator for the buffer.
bool operator>=(const base_iterator &it) const
base_iterator(const range_t &one, const range_t &two)
GLint GLenum GLsizei GLint GLsizei const void * data
Definition: glew.h:1379
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
iterator begin()
The begin iterator for the buffer.
GLuint GLuint end
Definition: glew.h:1253
GLsizei n
Definition: glew.h:4040
exint capacity() const
The current capacity of the buffer.
bool isFull() const
Is the buffer currently full.
range_t arrayOne()
A circular buffer can wrap around in memory. This is the first array of continious memory...
exint maxSize() const
The absolute maximum size of the buffer. Use size() if you need to know the current size of the buffe...
GLuint start
Definition: glew.h:1253
bool operator<=(const base_iterator &it) const
bool operator==(const base_iterator &it) const
std::pair< char *, int > range_t
exint operator-(const base_iterator &it) const
const T & back() const
The last element in the buffer. Undefined behaviour if the buffer is empty.
base_iterator< const char > const_iterator
GLuint GLuint GLsizei count
Definition: glew.h:1253
Type-safe formatting, modeled on the Python str.format function.
size_t UTformat(FILE *file, const char *format, const Args &...args)
T & operator[](int index)
Retrieve element at provided index.
typename NET_CircularBuffer< U >::range_t range_t
GLuint64EXT * result
Definition: glew.h:14007
exint size() const
The number of elements currently stored in the buffer.
base_iterator & operator-=(exint n)
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:135
T & front()
The first element in the buffer. Undefined behaviour if the buffer is empty.
const T & front() const
The first element in the buffer. Undefined behaviour if the buffer is empty.
void pop(int count)
Remove multiple elements from the front of the buffer.
GLsizei const GLfloat * value
Definition: glew.h:1849
int entries() const
The number of elements currently stored in the buffer.
const_range_t arrayOne() const
Const variant of the arrayOne().