path: root/ovr_sdk_win_23.0.0/LibOVRKernel/Src/Kernel/OVR_Deque.h

/************************************************************************************

Filename    :   OVR_Deque.h
Content     :   Deque container
Created     :   Nov. 15, 2013
Authors     :   Dov Katz

Copyright   :   Copyright (c) Facebook Technologies, LLC and its affiliates. All rights reserved.

Licensed under the Oculus Master SDK License Version 1.0 (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

https://developer.oculus.com/licenses/oculusmastersdk-1.0

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.

*************************************************************************************/

#pragma once

#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);
}

} // namespace OVR