ovr_sdk

annotate LibOVR/Src/Kernel/OVR_Deque.h @ 0:1b39a1b46319

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