HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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_ValArray.h"
16 
17 /// A UT_RingBuffer is an indexable queue. The buffer uses indices
18 /// that represent the insertion order of items in the buffer. The
19 /// buffer may contain "holes", which have no associated data but
20 /// still have an order number.
21 template <typename T>
23 public:
24  UT_RingBuffer();
25  UT_RingBuffer(int capacity);
27 
28  /// Null-padded insertion. If the id of the incoming object is
29  /// greater than the next order number that would be assigned
30  /// by push(), holes are created in the buffer.
31  void insert(int id, const T &data);
32  void remove(int id);
33 
34  /// Resets the buffer to an empty buffer with a 0 index
35  void clear();
36 
37  /// Pop the first element off the head of the list, moving the first entry
38  /// to the next element.
40  {
41  T data = front();
42  pop();
43  return data;
44  }
45 
46  /// Insert the data into the buffer, and return the order number that
47  /// it is assigned.
48  int push(const T &data);
49 
50  /// Pop a single element from the start of the buffer
51  void pop();
52 
53  /// Pop a single element from the back of the buffer
54  void popBack();
55 
56  /// Pop the next "number" elements from the buffer
57  void pop(int number);
58 
59  int size() const { return myLastId - myFirstId + 1; }
60  int entries() const { return size(); }
61  int peakUsage() const { return myPeak; }
62 
63  /// operator [] is the bounds checked version of the operator. The
64  /// id is the order number of the object being indexed.
65  T operator[](int id) const;
66  const T &operator()(int id) const
67  {
68  UT_ASSERT_P(id >= myFirstId && id <= myLastId);
69  return myData(idIndex(id));
70  }
71 
72  /// In order to iterate over the contents of the ring buffer
73  /// for (i = rbuf.frontId(); i <= rbuf.backId(); i++)
74  /// element = rbuf(i);
75  /// The backId is *inclusive*!!! There shouldn't be holes in the array.
76  const T &front() const { return myData(myFirst); }
77  int frontId() const { return myFirstId; }
78  const T &back() const { return myData(myLast); }
79  int backId() const { return myLastId; }
80 
81  void display() const;
82 
83 private:
84  void growIfNeeded(int number)
85  {
86  if (entries() + number > myData.entries())
87  growData(number);
88  }
89  // Grows the size of the array by the specified amount
90  void growData(int number);
91  int idIndex(int id) const
92  { return (id - myFirstId + myFirst) % myData.entries(); }
93 
94 private:
95  UT_Array<T> myData;
96  int myFirst;
97  int myLast;
98 
99  // Order numbers increase monotonically as data is added to
100  // the buffer.
101  int myFirstId;
102  int myLastId;
103 
104  int myPeak;
105 };
106 
107 template <typename T>
108 inline int
110 {
111  growIfNeeded(1);
112  myLast++;
113  if (myLast >= myData.entries())
114  myLast = 0;
115  myLastId++;
116  myData(myLast) = data;
117  return myLastId;
118 }
119 
120 template <typename T>
121 inline void
123 {
124  UT_ASSERT_P(1 <= myLastId - myFirstId + 1);
125  myFirst++;
126  if (myFirst >= myData.entries())
127  myFirst = 0;
128  myFirstId++;
129 }
130 
131 template <typename T>
132 inline void
134 {
135  UT_ASSERT_P(1 <= myLastId - myFirstId + 1);
136  myLast--;
137  if (myLast < 0)
138  myLast = myData.entries()-1;
139  myLastId--;
140 }
141 
142 #if defined( WIN32 ) || defined( LINUX ) || defined(MBSD) || defined(GAMEOS)
143  #include "UT_RingBuffer.C"
144 #endif
145 
146 #endif
147 
void display() const
T operator[](int id) const
Definition: UT_RingBuffer.C:96
void pop()
Pop a single element from the start of the buffer.
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
GLuint id
Definition: glcorearb.h:654
const T & back() const
Definition: UT_RingBuffer.h:78
int size() const
Definition: UT_RingBuffer.h:59
void insert(int id, const T &data)
Definition: UT_RingBuffer.C:39
void popBack()
Pop a single element from the back of the buffer.
GLboolean * data
Definition: glcorearb.h:130
void clear()
Resets the buffer to an empty buffer with a 0 index.
Definition: UT_RingBuffer.C:74
int peakUsage() const
Definition: UT_RingBuffer.h:61
int push(const T &data)
const T & operator()(int id) const
Definition: UT_RingBuffer.h:66
int frontId() const
Definition: UT_RingBuffer.h:77
int backId() const
Definition: UT_RingBuffer.h:79
const T & front() const
Definition: UT_RingBuffer.h:76
int entries() const
Definition: UT_RingBuffer.h:60