ovr_sdk
view LibOVR/Src/Kernel/OVR_Deque.h @ 0:1b39a1b46319
initial 0.4.4
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Wed, 14 Jan 2015 06:51:16 +0200 |
| parents | |
| children |
line source
1 /************************************************************************************
3 Filename : OVR_Deque.h
4 Content : Deque container
5 Created : Nov. 15, 2013
6 Authors : Dov Katz
8 Copyright : Copyright 2014 Oculus VR, LLC All Rights reserved.
10 Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License");
11 you may not use the Oculus VR Rift SDK except in compliance with the License,
12 which is provided at the time of installation or download, or which
13 otherwise accompanies this software in either electronic or hard copy form.
15 You may obtain a copy of the License at
17 http://www.oculusvr.com/licenses/LICENSE-3.2
19 Unless required by applicable law or agreed to in writing, the Oculus VR SDK
20 distributed under the License is distributed on an "AS IS" BASIS,
21 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
22 See the License for the specific language governing permissions and
23 limitations under the License.
25 *************************************************************************************/
27 #ifndef OVR_Deque_h
28 #define OVR_Deque_h
30 #include "OVR_ContainerAllocator.h"
32 namespace OVR{
34 template <class Elem, class Allocator = ContainerAllocator<Elem> >
35 class Deque
36 {
37 public:
38 enum
39 {
40 DefaultCapacity = 500
41 };
43 Deque(int capacity = DefaultCapacity);
44 virtual ~Deque(void);
46 virtual void PushBack (const Elem &Item); // Adds Item to the end
47 virtual void PushFront (const Elem &Item); // Adds Item to the beginning
48 virtual Elem PopBack (void); // Removes Item from the end
49 virtual Elem PopFront (void); // Removes Item from the beginning
50 virtual const Elem& PeekBack (int count = 0) const; // Returns count-th Item from the end
51 virtual const Elem& PeekFront (int count = 0) const; // Returns count-th Item from the beginning
53 virtual inline size_t GetSize (void) const; // Returns Number of Elements
54 OVR_FORCE_INLINE int GetSizeI (void) const
55 {
56 return (int)GetSize();
57 }
58 virtual inline size_t GetCapacity(void) const; // Returns the maximum possible number of elements
59 virtual void Clear (void); // Remove all elements
60 virtual inline bool IsEmpty () const;
61 virtual inline bool IsFull () const;
63 protected:
64 Elem *Data; // The actual Data array
65 const int Capacity; // Deque capacity
66 int Beginning; // Index of the first element
67 int End; // Index of the next after last element
69 // Instead of calculating the number of elements, using this variable
70 // is much more convenient.
71 int ElemCount;
73 private:
74 OVR_NON_COPYABLE(Deque);
75 };
77 template <class Elem, class Allocator = ContainerAllocator<Elem> >
78 class InPlaceMutableDeque : public Deque<Elem, Allocator>
79 {
80 typedef Deque<Elem, Allocator> BaseType;
82 public:
83 InPlaceMutableDeque( int capacity = BaseType::DefaultCapacity ) : BaseType( capacity ) {}
84 virtual ~InPlaceMutableDeque() {};
86 using BaseType::PeekBack;
87 using BaseType::PeekFront;
88 virtual Elem& PeekBack (int count = 0); // Returns count-th Item from the end
89 virtual Elem& PeekFront (int count = 0); // Returns count-th Item from the beginning
90 };
92 // Same as Deque, but allows to write more elements than maximum capacity
93 // Old elements are lost as they are overwritten with the new ones
94 template <class Elem, class Allocator = ContainerAllocator<Elem> >
95 class CircularBuffer : public InPlaceMutableDeque<Elem, Allocator>
96 {
97 typedef InPlaceMutableDeque<Elem, Allocator> BaseType;
99 public:
100 CircularBuffer(int MaxSize = BaseType::DefaultCapacity) : BaseType(MaxSize) { };
101 virtual ~CircularBuffer(){}
103 // The following methods are inline as a workaround for a VS bug causing erroneous C4505 warnings
104 // See: http://stackoverflow.com/questions/3051992/compiler-warning-at-c-template-base-class
105 inline virtual void PushBack (const Elem &Item); // Adds Item to the end, overwriting the oldest element at the beginning if necessary
106 inline virtual void PushFront (const Elem &Item); // Adds Item to the beginning, overwriting the oldest element at the end if necessary
107 };
109 //----------------------------------------------------------------------------------
111 // Deque Constructor function
112 template <class Elem, class Allocator>
113 Deque<Elem, Allocator>::Deque(int capacity) :
114 Capacity( capacity ), Beginning(0), End(0), ElemCount(0)
115 {
116 Data = (Elem*) Allocator::Alloc(Capacity * sizeof(Elem));
117 }
119 // Deque Destructor function
120 template <class Elem, class Allocator>
121 Deque<Elem, Allocator>::~Deque(void)
122 {
123 Clear();
124 Allocator::Free(Data);
125 }
127 template <class Elem, class Allocator>
128 void Deque<Elem, Allocator>::Clear()
129 {
130 if (!IsEmpty())
131 {
132 if (Beginning < End)
133 {
134 // no wrap-around
135 Allocator::DestructArray(Data + Beginning, End - Beginning);
136 }
137 else
138 {
139 // wrap-around
140 Allocator::DestructArray(Data + Beginning, Capacity - Beginning);
141 Allocator::DestructArray(Data, End);
142 }
143 }
145 Beginning = 0;
146 End = 0;
147 ElemCount = 0;
148 }
150 // Push functions
151 template <class Elem, class Allocator>
152 void Deque<Elem, Allocator>::PushBack(const Elem &Item)
153 {
154 // Error Check: Make sure we aren't
155 // exceeding our maximum storage space
156 OVR_ASSERT( ElemCount < Capacity );
158 Allocator::Construct(Data + End, Item);
159 ++End;
160 ++ElemCount;
162 // Check for wrap-around
163 if (End >= Capacity)
164 End -= Capacity;
165 }
167 template <class Elem, class Allocator>
168 void Deque<Elem, Allocator>::PushFront(const Elem &Item)
169 {
170 // Error Check: Make sure we aren't
171 // exceeding our maximum storage space
172 OVR_ASSERT( ElemCount < Capacity );
174 --Beginning;
175 // Check for wrap-around
176 if (Beginning < 0)
177 Beginning += Capacity;
179 Allocator::Construct(Data + Beginning, Item);
180 ++ElemCount;
181 }
183 // Pop functions
184 template <class Elem, class Allocator>
185 Elem Deque<Elem, Allocator>::PopFront(void)
186 {
187 // Error Check: Make sure we aren't reading from an empty Deque
188 OVR_ASSERT( ElemCount > 0 );
190 Elem ReturnValue = Data[ Beginning ];
191 Allocator::Destruct(Data + Beginning);
193 ++Beginning;
194 --ElemCount;
196 // Check for wrap-around
197 if (Beginning >= Capacity)
198 Beginning -= Capacity;
200 return ReturnValue;
201 }
203 template <class Elem, class Allocator>
204 Elem Deque<Elem, Allocator>::PopBack(void)
205 {
206 // Error Check: Make sure we aren't reading from an empty Deque
207 OVR_ASSERT( ElemCount > 0 );
209 --End;
210 --ElemCount;
212 // Check for wrap-around
213 if (End < 0)
214 End += Capacity;
216 Elem ReturnValue = Data[ End ];
217 Allocator::Destruct(Data + End);
219 return ReturnValue;
220 }
222 // Peek functions
223 template <class Elem, class Allocator>
224 const Elem& Deque<Elem, Allocator>::PeekFront(int count) const
225 {
226 // Error Check: Make sure we aren't reading from an empty Deque
227 OVR_ASSERT( ElemCount > count );
229 int idx = Beginning + count;
230 if (idx >= Capacity)
231 idx -= Capacity;
232 return Data[ idx ];
233 }
235 template <class Elem, class Allocator>
236 const Elem& Deque<Elem, Allocator>::PeekBack(int count) const
237 {
238 // Error Check: Make sure we aren't reading from an empty Deque
239 OVR_ASSERT( ElemCount > count );
241 int idx = End - count - 1;
242 if (idx < 0)
243 idx += Capacity;
244 return Data[ idx ];
245 }
247 // Mutable Peek functions
248 template <class Elem, class Allocator>
249 Elem& InPlaceMutableDeque<Elem, Allocator>::PeekFront(int count)
250 {
251 // Error Check: Make sure we aren't reading from an empty Deque
252 OVR_ASSERT( BaseType::ElemCount > count );
254 int idx = BaseType::Beginning + count;
255 if (idx >= BaseType::Capacity)
256 idx -= BaseType::Capacity;
257 return BaseType::Data[ idx ];
258 }
260 template <class Elem, class Allocator>
261 Elem& InPlaceMutableDeque<Elem, Allocator>::PeekBack(int count)
262 {
263 // Error Check: Make sure we aren't reading from an empty Deque
264 OVR_ASSERT( BaseType::ElemCount > count );
266 int idx = BaseType::End - count - 1;
267 if (idx < 0)
268 idx += BaseType::Capacity;
269 return BaseType::Data[ idx ];
270 }
272 template <class Elem, class Allocator>
273 inline size_t Deque<Elem, Allocator>::GetCapacity(void) const
274 {
275 return Capacity;
276 }
278 template <class Elem, class Allocator>
279 inline size_t Deque<Elem, Allocator>::GetSize(void) const
280 {
281 return ElemCount;
282 }
284 template <class Elem, class Allocator>
285 inline bool Deque<Elem, Allocator>::IsEmpty(void) const
286 {
287 return ElemCount == 0;
288 }
290 template <class Elem, class Allocator>
291 inline bool Deque<Elem, Allocator>::IsFull(void) const
292 {
293 return ElemCount == Capacity;
294 }
296 // ******* CircularBuffer<Elem> *******
297 // Push functions
298 template <class Elem, class Allocator>
299 void CircularBuffer<Elem, Allocator>::PushBack(const Elem &Item)
300 {
301 if (this->IsFull())
302 this->PopFront();
303 BaseType::PushBack(Item);
304 }
306 template <class Elem, class Allocator>
307 void CircularBuffer<Elem, Allocator>::PushFront(const Elem &Item)
308 {
309 if (this->IsFull())
310 this->PopBack();
311 BaseType::PushFront(Item);
312 }
314 };
316 #endif