HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_RingBuffer.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY 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: UT_RingBuffer.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_RingBuffer__
12 #define __UT_RingBuffer__
13 
14 #include "UT_API.h"
15 #include "UT_Array.h"
16 #include "UT_NonCopyable.h"
17 #include <SYS/SYS_Compiler.h>
18 #include <utility>
19 
20 /// A UT_RingBuffer is an indexable queue. The buffer uses indices
21 /// that represent the insertion order of items in the buffer. The
22 /// buffer may contain "holes", which have no associated data but
23 /// still have an order number.
24 template <typename T>
26 {
27 public:
28  UT_RingBuffer();
29  UT_RingBuffer(int capacity);
31 
33 
34  /// Null-padded insertion. If the id of the incoming object is
35  /// greater than the next order number that would be assigned
36  /// by push(), holes are created in the buffer.
37  /// @{
38  void insert(int id, const T &data)
39  { insertImpl(id, data); }
40  void insert(int id, T &&data)
41  { insertImpl(id, std::move(data)); }
42  /// @}
43 
44  /// Remove item with id
45  void remove(int id);
46 
47  /// Resets the buffer to an empty buffer with a 0 index
48  void clear();
49 
50  /// Pop the first element off the head of the list, moving the first entry
51  /// to the next element.
54  {
55  T data = std::move(myData(myFirst));
56  pop();
57  return data;
58  }
59 
60  /// Insert the data into the buffer, and return the order number that
61  /// it is assigned.
62  /// @{
63  int push(const T &data) { return pushImpl(data); }
64  int push(T &&data) { return pushImpl(std::move(data)); }
65  /// @}
66 
67  /// Pop a single element from the start of the buffer
68  void pop();
69 
70  /// Pop a single element from the back of the buffer
71  void popBack();
72 
73  /// Pop the next "number" elements from the buffer
74  void pop(int number);
75 
76  int size() const { return myLastId - myFirstId + 1; }
77  int entries() const { return size(); }
78  int peakUsage() const { return myPeak; }
79 
80  /// operator [] is the bounds checked version of the operator. The
81  /// id is the order number of the object being indexed.
82  T operator[](int id) const;
83  const T &operator()(int id) const
84  {
85  UT_ASSERT_P(id >= myFirstId && id <= myLastId);
86  return myData(idIndex(id));
87  }
88 
89  /// In order to iterate over the contents of the ring buffer
90  /// for (i = rbuf.frontId(); i <= rbuf.backId(); i++)
91  /// element = rbuf(i);
92  /// The backId is *inclusive*!!! There shouldn't be holes in the array.
93  const T &front() const { return myData(myFirst); }
94  int frontId() const { return myFirstId; }
95  const T &back() const { return myData(myLast); }
96  int backId() const { return myLastId; }
97 
98  void display() const;
99 
100 private:
101  void growIfNeeded(int number)
102  {
103  if (entries() + number > myData.entries())
104  growData(number);
105  }
106  // Grows the size of the array by the specified amount
107  void growData(int number);
108  int idIndex(int id) const
109  { return (id - myFirstId + myFirst) % myData.entries(); }
110 
111  template <typename S>
112  void insertImpl(int id, S &&data);
113  template <typename S>
114  int pushImpl(S &&data);
115 
116 private:
117  UT_Array<T> myData;
118  int myFirst;
119  int myLast;
120 
121  // Order numbers increase monotonically as data is added to
122  // the buffer.
123  int myFirstId;
124  int myLastId;
125 
126  int myPeak;
127 };
128 
129 template <typename T>
130 template <typename S>
131 inline int
133 {
134  growIfNeeded(1);
135  myLast++;
136  if (myLast >= myData.entries())
137  myLast = 0;
138  myLastId++;
139  myData(myLast) = std::forward<S>(data);
140  return myLastId;
141 }
142 
143 template <typename T>
144 inline void
146 {
147  UT_ASSERT_P(1 <= myLastId - myFirstId + 1);
148  myFirst++;
149  if (myFirst >= myData.entries())
150  myFirst = 0;
151  myFirstId++;
152 }
153 
154 template <typename T>
155 inline void
157 {
158  UT_ASSERT_P(1 <= myLastId - myFirstId + 1);
159  myLast--;
160  if (myLast < 0)
161  myLast = myData.entries()-1;
162  myLastId--;
163 }
164 
165 #include "UT_RingBuffer.C"
166 
167 #endif
168 
void
Definition: png.h:1083
SYS_NO_DISCARD_RESULT T popFirst()
Definition: UT_RingBuffer.h:53
GLboolean * data
Definition: glcorearb.h:131
void display() const
T operator[](int id) const
Definition: UT_RingBuffer.C:98
void pop()
Pop a single element from the start of the buffer.
int push(T &&data)
Definition: UT_RingBuffer.h:64
const T & back() const
Definition: UT_RingBuffer.h:95
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
void insert(int id, T &&data)
Definition: UT_RingBuffer.h:40
int size() const
Definition: UT_RingBuffer.h:76
#define UT_NON_COPYABLE(CLASS)
Define deleted copy constructor and assignment operator inside a class.
#define SYS_NO_DISCARD_RESULT
Definition: SYS_Compiler.h:93
GLuint id
Definition: glcorearb.h:655
void insert(int id, const T &data)
Definition: UT_RingBuffer.h:38
void popBack()
Pop a single element from the back of the buffer.
void clear()
Resets the buffer to an empty buffer with a 0 index.
Definition: UT_RingBuffer.C:76
int peakUsage() const
Definition: UT_RingBuffer.h:78
int push(const T &data)
Definition: UT_RingBuffer.h:63
const T & operator()(int id) const
Definition: UT_RingBuffer.h:83
int frontId() const
Definition: UT_RingBuffer.h:94
int backId() const
Definition: UT_RingBuffer.h:96
const T & front() const
Definition: UT_RingBuffer.h:93
Definition: format.h:895
int entries() const
Definition: UT_RingBuffer.h:77