summaryrefslogtreecommitdiffstats
path: root/LibOVRKernel/Src/Kernel/OVR_Deque.h
diff options
context:
space:
mode:
Diffstat (limited to 'LibOVRKernel/Src/Kernel/OVR_Deque.h')
-rw-r--r--LibOVRKernel/Src/Kernel/OVR_Deque.h316
1 files changed, 316 insertions, 0 deletions
diff --git a/LibOVRKernel/Src/Kernel/OVR_Deque.h b/LibOVRKernel/Src/Kernel/OVR_Deque.h
new file mode 100644
index 0000000..951ed84
--- /dev/null
+++ b/LibOVRKernel/Src/Kernel/OVR_Deque.h
@@ -0,0 +1,316 @@
+/************************************************************************************
+
+Filename : OVR_Deque.h
+Content : Deque container
+Created : Nov. 15, 2013
+Authors : Dov Katz
+
+Copyright : Copyright 2014 Oculus VR, LLC All Rights reserved.
+
+Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License");
+you may not use the Oculus VR Rift SDK except in compliance with the License,
+which is provided at the time of installation or download, or which
+otherwise accompanies this software in either electronic or hard copy form.
+
+You may obtain a copy of the License at
+
+http://www.oculusvr.com/licenses/LICENSE-3.2
+
+Unless required by applicable law or agreed to in writing, the Oculus VR SDK
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+
+*************************************************************************************/
+
+#ifndef OVR_Deque_h
+#define OVR_Deque_h
+
+#include "OVR_ContainerAllocator.h"
+
+namespace OVR{
+
+template <class Elem, class Allocator = ContainerAllocator<Elem> >
+class Deque
+{
+public:
+ enum
+ {
+ DefaultCapacity = 500
+ };
+
+ Deque(int capacity = DefaultCapacity);
+ virtual ~Deque(void);
+
+ virtual void PushBack (const Elem &Item); // Adds Item to the end
+ virtual void PushFront (const Elem &Item); // Adds Item to the beginning
+ virtual Elem PopBack (void); // Removes Item from the end
+ virtual Elem PopFront (void); // Removes Item from the beginning
+ virtual const Elem& PeekBack (int count = 0) const; // Returns count-th Item from the end
+ virtual const Elem& PeekFront (int count = 0) const; // Returns count-th Item from the beginning
+
+ virtual inline size_t GetSize (void) const; // Returns Number of Elements
+ OVR_FORCE_INLINE int GetSizeI (void) const
+ {
+ return (int)GetSize();
+ }
+ virtual inline size_t GetCapacity(void) const; // Returns the maximum possible number of elements
+ virtual void Clear (void); // Remove all elements
+ virtual inline bool IsEmpty () const;
+ virtual inline bool IsFull () const;
+
+protected:
+ Elem *Data; // The actual Data array
+ const int Capacity; // Deque capacity
+ int Beginning; // Index of the first element
+ int End; // Index of the next after last element
+
+ // Instead of calculating the number of elements, using this variable
+ // is much more convenient.
+ int ElemCount;
+
+private:
+ OVR_NON_COPYABLE(Deque);
+};
+
+template <class Elem, class Allocator = ContainerAllocator<Elem> >
+class InPlaceMutableDeque : public Deque<Elem, Allocator>
+{
+ typedef Deque<Elem, Allocator> BaseType;
+
+public:
+ InPlaceMutableDeque( int capacity = BaseType::DefaultCapacity ) : BaseType( capacity ) {}
+ virtual ~InPlaceMutableDeque() {};
+
+ using BaseType::PeekBack;
+ using BaseType::PeekFront;
+ virtual Elem& PeekBack (int count = 0); // Returns count-th Item from the end
+ virtual Elem& PeekFront (int count = 0); // Returns count-th Item from the beginning
+};
+
+// Same as Deque, but allows to write more elements than maximum capacity
+// Old elements are lost as they are overwritten with the new ones
+template <class Elem, class Allocator = ContainerAllocator<Elem> >
+class CircularBuffer : public InPlaceMutableDeque<Elem, Allocator>
+{
+ typedef InPlaceMutableDeque<Elem, Allocator> BaseType;
+
+public:
+ CircularBuffer(int MaxSize = BaseType::DefaultCapacity) : BaseType(MaxSize) { };
+ virtual ~CircularBuffer(){}
+
+ // The following methods are inline as a workaround for a VS bug causing erroneous C4505 warnings
+ // See: http://stackoverflow.com/questions/3051992/compiler-warning-at-c-template-base-class
+ inline virtual void PushBack (const Elem &Item); // Adds Item to the end, overwriting the oldest element at the beginning if necessary
+ inline virtual void PushFront (const Elem &Item); // Adds Item to the beginning, overwriting the oldest element at the end if necessary
+};
+
+//----------------------------------------------------------------------------------
+
+// Deque Constructor function
+template <class Elem, class Allocator>
+Deque<Elem, Allocator>::Deque(int capacity) :
+Capacity( capacity ), Beginning(0), End(0), ElemCount(0)
+{
+ Data = (Elem*) Allocator::Alloc(Capacity * sizeof(Elem));
+}
+
+// Deque Destructor function
+template <class Elem, class Allocator>
+Deque<Elem, Allocator>::~Deque(void)
+{
+ Clear();
+ Allocator::Free(Data);
+}
+
+template <class Elem, class Allocator>
+void Deque<Elem, Allocator>::Clear()
+{
+ if (!IsEmpty())
+ {
+ if (Beginning < End)
+ {
+ // no wrap-around
+ Allocator::DestructArray(Data + Beginning, End - Beginning);
+ }
+ else
+ {
+ // wrap-around
+ Allocator::DestructArray(Data + Beginning, Capacity - Beginning);
+ Allocator::DestructArray(Data, End);
+ }
+ }
+
+ Beginning = 0;
+ End = 0;
+ ElemCount = 0;
+}
+
+// Push functions
+template <class Elem, class Allocator>
+void Deque<Elem, Allocator>::PushBack(const Elem &Item)
+{
+ // Error Check: Make sure we aren't
+ // exceeding our maximum storage space
+ OVR_ASSERT( ElemCount < Capacity );
+
+ Allocator::Construct(Data + End, Item);
+ ++End;
+ ++ElemCount;
+
+ // Check for wrap-around
+ if (End >= Capacity)
+ End -= Capacity;
+}
+
+template <class Elem, class Allocator>
+void Deque<Elem, Allocator>::PushFront(const Elem &Item)
+{
+ // Error Check: Make sure we aren't
+ // exceeding our maximum storage space
+ OVR_ASSERT( ElemCount < Capacity );
+
+ --Beginning;
+ // Check for wrap-around
+ if (Beginning < 0)
+ Beginning += Capacity;
+
+ Allocator::Construct(Data + Beginning, Item);
+ ++ElemCount;
+}
+
+// Pop functions
+template <class Elem, class Allocator>
+Elem Deque<Elem, Allocator>::PopFront(void)
+{
+ // Error Check: Make sure we aren't reading from an empty Deque
+ OVR_ASSERT( ElemCount > 0 );
+
+ Elem ReturnValue = Data[ Beginning ];
+ Allocator::Destruct(Data + Beginning);
+
+ ++Beginning;
+ --ElemCount;
+
+ // Check for wrap-around
+ if (Beginning >= Capacity)
+ Beginning -= Capacity;
+
+ return ReturnValue;
+}
+
+template <class Elem, class Allocator>
+Elem Deque<Elem, Allocator>::PopBack(void)
+{
+ // Error Check: Make sure we aren't reading from an empty Deque
+ OVR_ASSERT( ElemCount > 0 );
+
+ --End;
+ --ElemCount;
+
+ // Check for wrap-around
+ if (End < 0)
+ End += Capacity;
+
+ Elem ReturnValue = Data[ End ];
+ Allocator::Destruct(Data + End);
+
+ return ReturnValue;
+}
+
+// Peek functions
+template <class Elem, class Allocator>
+const Elem& Deque<Elem, Allocator>::PeekFront(int count) const
+{
+ // Error Check: Make sure we aren't reading from an empty Deque
+ OVR_ASSERT( ElemCount > count );
+
+ int idx = Beginning + count;
+ if (idx >= Capacity)
+ idx -= Capacity;
+ return Data[ idx ];
+}
+
+template <class Elem, class Allocator>
+const Elem& Deque<Elem, Allocator>::PeekBack(int count) const
+{
+ // Error Check: Make sure we aren't reading from an empty Deque
+ OVR_ASSERT( ElemCount > count );
+
+ int idx = End - count - 1;
+ if (idx < 0)
+ idx += Capacity;
+ return Data[ idx ];
+}
+
+// Mutable Peek functions
+template <class Elem, class Allocator>
+Elem& InPlaceMutableDeque<Elem, Allocator>::PeekFront(int count)
+{
+ // Error Check: Make sure we aren't reading from an empty Deque
+ OVR_ASSERT( BaseType::ElemCount > count );
+
+ int idx = BaseType::Beginning + count;
+ if (idx >= BaseType::Capacity)
+ idx -= BaseType::Capacity;
+ return BaseType::Data[ idx ];
+}
+
+template <class Elem, class Allocator>
+Elem& InPlaceMutableDeque<Elem, Allocator>::PeekBack(int count)
+{
+ // Error Check: Make sure we aren't reading from an empty Deque
+ OVR_ASSERT( BaseType::ElemCount > count );
+
+ int idx = BaseType::End - count - 1;
+ if (idx < 0)
+ idx += BaseType::Capacity;
+ return BaseType::Data[ idx ];
+}
+
+template <class Elem, class Allocator>
+inline size_t Deque<Elem, Allocator>::GetCapacity(void) const
+{
+ return Capacity;
+}
+
+template <class Elem, class Allocator>
+inline size_t Deque<Elem, Allocator>::GetSize(void) const
+{
+ return ElemCount;
+}
+
+template <class Elem, class Allocator>
+inline bool Deque<Elem, Allocator>::IsEmpty(void) const
+{
+ return ElemCount == 0;
+}
+
+template <class Elem, class Allocator>
+inline bool Deque<Elem, Allocator>::IsFull(void) const
+{
+ return ElemCount == Capacity;
+}
+
+// ******* CircularBuffer<Elem> *******
+// Push functions
+template <class Elem, class Allocator>
+void CircularBuffer<Elem, Allocator>::PushBack(const Elem &Item)
+{
+ if (this->IsFull())
+ this->PopFront();
+ BaseType::PushBack(Item);
+}
+
+template <class Elem, class Allocator>
+void CircularBuffer<Elem, Allocator>::PushFront(const Elem &Item)
+{
+ if (this->IsFull())
+ this->PopBack();
+ BaseType::PushFront(Item);
+}
+
+};
+
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-28 15:45:56 +0000