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