ovr_sdk
diff 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 diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/LibOVR/Src/Kernel/OVR_Deque.h Wed Jan 14 06:51:16 2015 +0200 1.3 @@ -0,0 +1,316 @@ 1.4 +/************************************************************************************ 1.5 + 1.6 +Filename : OVR_Deque.h 1.7 +Content : Deque container 1.8 +Created : Nov. 15, 2013 1.9 +Authors : Dov Katz 1.10 + 1.11 +Copyright : Copyright 2014 Oculus VR, LLC All Rights reserved. 1.12 + 1.13 +Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); 1.14 +you may not use the Oculus VR Rift SDK except in compliance with the License, 1.15 +which is provided at the time of installation or download, or which 1.16 +otherwise accompanies this software in either electronic or hard copy form. 1.17 + 1.18 +You may obtain a copy of the License at 1.19 + 1.20 +http://www.oculusvr.com/licenses/LICENSE-3.2 1.21 + 1.22 +Unless required by applicable law or agreed to in writing, the Oculus VR SDK 1.23 +distributed under the License is distributed on an "AS IS" BASIS, 1.24 +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1.25 +See the License for the specific language governing permissions and 1.26 +limitations under the License. 1.27 + 1.28 +*************************************************************************************/ 1.29 + 1.30 +#ifndef OVR_Deque_h 1.31 +#define OVR_Deque_h 1.32 + 1.33 +#include "OVR_ContainerAllocator.h" 1.34 + 1.35 +namespace OVR{ 1.36 + 1.37 +template <class Elem, class Allocator = ContainerAllocator<Elem> > 1.38 +class Deque 1.39 +{ 1.40 +public: 1.41 + enum 1.42 + { 1.43 + DefaultCapacity = 500 1.44 + }; 1.45 + 1.46 + Deque(int capacity = DefaultCapacity); 1.47 + virtual ~Deque(void); 1.48 + 1.49 + virtual void PushBack (const Elem &Item); // Adds Item to the end 1.50 + virtual void PushFront (const Elem &Item); // Adds Item to the beginning 1.51 + virtual Elem PopBack (void); // Removes Item from the end 1.52 + virtual Elem PopFront (void); // Removes Item from the beginning 1.53 + virtual const Elem& PeekBack (int count = 0) const; // Returns count-th Item from the end 1.54 + virtual const Elem& PeekFront (int count = 0) const; // Returns count-th Item from the beginning 1.55 + 1.56 + virtual inline size_t GetSize (void) const; // Returns Number of Elements 1.57 + OVR_FORCE_INLINE int GetSizeI (void) const 1.58 + { 1.59 + return (int)GetSize(); 1.60 + } 1.61 + virtual inline size_t GetCapacity(void) const; // Returns the maximum possible number of elements 1.62 + virtual void Clear (void); // Remove all elements 1.63 + virtual inline bool IsEmpty () const; 1.64 + virtual inline bool IsFull () const; 1.65 + 1.66 +protected: 1.67 + Elem *Data; // The actual Data array 1.68 + const int Capacity; // Deque capacity 1.69 + int Beginning; // Index of the first element 1.70 + int End; // Index of the next after last element 1.71 + 1.72 + // Instead of calculating the number of elements, using this variable 1.73 + // is much more convenient. 1.74 + int ElemCount; 1.75 + 1.76 +private: 1.77 + OVR_NON_COPYABLE(Deque); 1.78 +}; 1.79 + 1.80 +template <class Elem, class Allocator = ContainerAllocator<Elem> > 1.81 +class InPlaceMutableDeque : public Deque<Elem, Allocator> 1.82 +{ 1.83 + typedef Deque<Elem, Allocator> BaseType; 1.84 + 1.85 +public: 1.86 + InPlaceMutableDeque( int capacity = BaseType::DefaultCapacity ) : BaseType( capacity ) {} 1.87 + virtual ~InPlaceMutableDeque() {}; 1.88 + 1.89 + using BaseType::PeekBack; 1.90 + using BaseType::PeekFront; 1.91 + virtual Elem& PeekBack (int count = 0); // Returns count-th Item from the end 1.92 + virtual Elem& PeekFront (int count = 0); // Returns count-th Item from the beginning 1.93 +}; 1.94 + 1.95 +// Same as Deque, but allows to write more elements than maximum capacity 1.96 +// Old elements are lost as they are overwritten with the new ones 1.97 +template <class Elem, class Allocator = ContainerAllocator<Elem> > 1.98 +class CircularBuffer : public InPlaceMutableDeque<Elem, Allocator> 1.99 +{ 1.100 + typedef InPlaceMutableDeque<Elem, Allocator> BaseType; 1.101 + 1.102 +public: 1.103 + CircularBuffer(int MaxSize = BaseType::DefaultCapacity) : BaseType(MaxSize) { }; 1.104 + virtual ~CircularBuffer(){} 1.105 + 1.106 + // The following methods are inline as a workaround for a VS bug causing erroneous C4505 warnings 1.107 + // See: http://stackoverflow.com/questions/3051992/compiler-warning-at-c-template-base-class 1.108 + inline virtual void PushBack (const Elem &Item); // Adds Item to the end, overwriting the oldest element at the beginning if necessary 1.109 + inline virtual void PushFront (const Elem &Item); // Adds Item to the beginning, overwriting the oldest element at the end if necessary 1.110 +}; 1.111 + 1.112 +//---------------------------------------------------------------------------------- 1.113 + 1.114 +// Deque Constructor function 1.115 +template <class Elem, class Allocator> 1.116 +Deque<Elem, Allocator>::Deque(int capacity) : 1.117 +Capacity( capacity ), Beginning(0), End(0), ElemCount(0) 1.118 +{ 1.119 + Data = (Elem*) Allocator::Alloc(Capacity * sizeof(Elem)); 1.120 +} 1.121 + 1.122 +// Deque Destructor function 1.123 +template <class Elem, class Allocator> 1.124 +Deque<Elem, Allocator>::~Deque(void) 1.125 +{ 1.126 + Clear(); 1.127 + Allocator::Free(Data); 1.128 +} 1.129 + 1.130 +template <class Elem, class Allocator> 1.131 +void Deque<Elem, Allocator>::Clear() 1.132 +{ 1.133 + if (!IsEmpty()) 1.134 + { 1.135 + if (Beginning < End) 1.136 + { 1.137 + // no wrap-around 1.138 + Allocator::DestructArray(Data + Beginning, End - Beginning); 1.139 + } 1.140 + else 1.141 + { 1.142 + // wrap-around 1.143 + Allocator::DestructArray(Data + Beginning, Capacity - Beginning); 1.144 + Allocator::DestructArray(Data, End); 1.145 + } 1.146 + } 1.147 + 1.148 + Beginning = 0; 1.149 + End = 0; 1.150 + ElemCount = 0; 1.151 +} 1.152 + 1.153 +// Push functions 1.154 +template <class Elem, class Allocator> 1.155 +void Deque<Elem, Allocator>::PushBack(const Elem &Item) 1.156 +{ 1.157 + // Error Check: Make sure we aren't 1.158 + // exceeding our maximum storage space 1.159 + OVR_ASSERT( ElemCount < Capacity ); 1.160 + 1.161 + Allocator::Construct(Data + End, Item); 1.162 + ++End; 1.163 + ++ElemCount; 1.164 + 1.165 + // Check for wrap-around 1.166 + if (End >= Capacity) 1.167 + End -= Capacity; 1.168 +} 1.169 + 1.170 +template <class Elem, class Allocator> 1.171 +void Deque<Elem, Allocator>::PushFront(const Elem &Item) 1.172 +{ 1.173 + // Error Check: Make sure we aren't 1.174 + // exceeding our maximum storage space 1.175 + OVR_ASSERT( ElemCount < Capacity ); 1.176 + 1.177 + --Beginning; 1.178 + // Check for wrap-around 1.179 + if (Beginning < 0) 1.180 + Beginning += Capacity; 1.181 + 1.182 + Allocator::Construct(Data + Beginning, Item); 1.183 + ++ElemCount; 1.184 +} 1.185 + 1.186 +// Pop functions 1.187 +template <class Elem, class Allocator> 1.188 +Elem Deque<Elem, Allocator>::PopFront(void) 1.189 +{ 1.190 + // Error Check: Make sure we aren't reading from an empty Deque 1.191 + OVR_ASSERT( ElemCount > 0 ); 1.192 + 1.193 + Elem ReturnValue = Data[ Beginning ]; 1.194 + Allocator::Destruct(Data + Beginning); 1.195 + 1.196 + ++Beginning; 1.197 + --ElemCount; 1.198 + 1.199 + // Check for wrap-around 1.200 + if (Beginning >= Capacity) 1.201 + Beginning -= Capacity; 1.202 + 1.203 + return ReturnValue; 1.204 +} 1.205 + 1.206 +template <class Elem, class Allocator> 1.207 +Elem Deque<Elem, Allocator>::PopBack(void) 1.208 +{ 1.209 + // Error Check: Make sure we aren't reading from an empty Deque 1.210 + OVR_ASSERT( ElemCount > 0 ); 1.211 + 1.212 + --End; 1.213 + --ElemCount; 1.214 + 1.215 + // Check for wrap-around 1.216 + if (End < 0) 1.217 + End += Capacity; 1.218 + 1.219 + Elem ReturnValue = Data[ End ]; 1.220 + Allocator::Destruct(Data + End); 1.221 + 1.222 + return ReturnValue; 1.223 +} 1.224 + 1.225 +// Peek functions 1.226 +template <class Elem, class Allocator> 1.227 +const Elem& Deque<Elem, Allocator>::PeekFront(int count) const 1.228 +{ 1.229 + // Error Check: Make sure we aren't reading from an empty Deque 1.230 + OVR_ASSERT( ElemCount > count ); 1.231 + 1.232 + int idx = Beginning + count; 1.233 + if (idx >= Capacity) 1.234 + idx -= Capacity; 1.235 + return Data[ idx ]; 1.236 +} 1.237 + 1.238 +template <class Elem, class Allocator> 1.239 +const Elem& Deque<Elem, Allocator>::PeekBack(int count) const 1.240 +{ 1.241 + // Error Check: Make sure we aren't reading from an empty Deque 1.242 + OVR_ASSERT( ElemCount > count ); 1.243 + 1.244 + int idx = End - count - 1; 1.245 + if (idx < 0) 1.246 + idx += Capacity; 1.247 + return Data[ idx ]; 1.248 +} 1.249 + 1.250 +// Mutable Peek functions 1.251 +template <class Elem, class Allocator> 1.252 +Elem& InPlaceMutableDeque<Elem, Allocator>::PeekFront(int count) 1.253 +{ 1.254 + // Error Check: Make sure we aren't reading from an empty Deque 1.255 + OVR_ASSERT( BaseType::ElemCount > count ); 1.256 + 1.257 + int idx = BaseType::Beginning + count; 1.258 + if (idx >= BaseType::Capacity) 1.259 + idx -= BaseType::Capacity; 1.260 + return BaseType::Data[ idx ]; 1.261 +} 1.262 + 1.263 +template <class Elem, class Allocator> 1.264 +Elem& InPlaceMutableDeque<Elem, Allocator>::PeekBack(int count) 1.265 +{ 1.266 + // Error Check: Make sure we aren't reading from an empty Deque 1.267 + OVR_ASSERT( BaseType::ElemCount > count ); 1.268 + 1.269 + int idx = BaseType::End - count - 1; 1.270 + if (idx < 0) 1.271 + idx += BaseType::Capacity; 1.272 + return BaseType::Data[ idx ]; 1.273 +} 1.274 + 1.275 +template <class Elem, class Allocator> 1.276 +inline size_t Deque<Elem, Allocator>::GetCapacity(void) const 1.277 +{ 1.278 + return Capacity; 1.279 +} 1.280 + 1.281 +template <class Elem, class Allocator> 1.282 +inline size_t Deque<Elem, Allocator>::GetSize(void) const 1.283 +{ 1.284 + return ElemCount; 1.285 +} 1.286 + 1.287 +template <class Elem, class Allocator> 1.288 +inline bool Deque<Elem, Allocator>::IsEmpty(void) const 1.289 +{ 1.290 + return ElemCount == 0; 1.291 +} 1.292 + 1.293 +template <class Elem, class Allocator> 1.294 +inline bool Deque<Elem, Allocator>::IsFull(void) const 1.295 +{ 1.296 + return ElemCount == Capacity; 1.297 +} 1.298 + 1.299 +// ******* CircularBuffer<Elem> ******* 1.300 +// Push functions 1.301 +template <class Elem, class Allocator> 1.302 +void CircularBuffer<Elem, Allocator>::PushBack(const Elem &Item) 1.303 +{ 1.304 + if (this->IsFull()) 1.305 + this->PopFront(); 1.306 + BaseType::PushBack(Item); 1.307 +} 1.308 + 1.309 +template <class Elem, class Allocator> 1.310 +void CircularBuffer<Elem, Allocator>::PushFront(const Elem &Item) 1.311 +{ 1.312 + if (this->IsFull()) 1.313 + this->PopBack(); 1.314 + BaseType::PushFront(Item); 1.315 +} 1.316 + 1.317 +}; 1.318 + 1.319 +#endif