c++ Type Erasure 활용

 

이전 글에서 만든 표준 c++ 기반의 Slot Delegate를 이용해서 예전에 만들었던 Signal 부분도 표준 c++로 바꾸려다 보니, 또 다른 종류의 Type Erasure를 사용하면 쉽게 해결되는 부분을 발견하였다. 그것은 Slot이 shared_ptr<>인 경우 Signal container에서 자동으로 life-cycle을 tracking 해서 dangling pointer를 없애주는 부분이다.

이 놈도 Delegate 만큼이나 흥미로운 놈이다. c++17의 std::any와 비슷하지만 사용법이 다르다. 옛날 옛적엔 서로 다른 type의 객체를 컨테이너에 가두고 뺑뺑이 돌리기 위해 void*를 사용했었는데, 이제는 이 놈을 사용하는게 좋겠다. 아래에 std::shared_ptr<>를 가지고 AnySharedPtr 라는 Type Erasure를 구현한 예를 보였다. 사용하기는 편하지만, 이 놈의 단점은 객체를 저장하기 위해 memory allocation이 필요하고 이에 따라 성능에도 악영향을 준다. 아무튼 Signal에서 shared_ptr<>가 reset 되거나 scope을 벗어나는 경우, p.get()과 p.use_count() 정보 만으로도 해당 Slot을 자동 제거해 줄 수 있다. 

이 놈이 재미있는 것은 Delegate 처럼 상속을 사용하지 않는다(내부에서만 사용함). std::function<> 류의 Delegate은 함수형의 any callables를 대신하기 위해 사용되는데 비해, 이 놈은 std::any와 같이 any 객체에 사용될 수 있다. 하지만, std::any와는 달리 std::any_cast<>를 사용할 필요가 없다. 돌려서 말하면, Delegate와 마찬가지로 type이 지워져서 객체 type을 정확히 알아야 하는 경우엔 사용할 수가 없다. 

또한, Visitor Pattern을 사용하지 않고도 공통 interface만 있으면 서로 다른 유형의 객체를 std::vector<>와 같은 컨테이너에 담아서 반복 작업을 돌릴 수 있다. 아래의 예를 보는게 이해가 빠를 것이다.

#include <memory>

// Type Erasure for any type of std::shared_ptr<>s.
//
// - typical usage: save any types to a container and iterate some common works.
//   std::vector<AnysharedPtr> shared_pointers;

class AnySharedPtr
{
  class Concept
  {
  public:
    auto clone() const { return std::unique_ptr<Concept>(clone_impl()); }

    // Interface methods for Any types. (e.g. std::shared_ptr<> here)
    // - the return type is limited to basic POD types: the original type is erased.
    virtual void* get() const = 0; // NB: the original pointer type is erased.
    virtual long use_count() const = 0;

  protected:
    // Virtual constructor idiom
    virtual Concept* clone_impl() const = 0; // virtual copy constructor - base return
  };

  template <typename TM>
  class Model : public Concept
  {
  public:
    Model(TM&& obj) : m_model(std::forward<TM>(obj)) {}

  protected:
    // Virtual constructor idiom
    Model* clone_impl() const override { return new Model(*this); } // covariant return

    // Interface methods for Any types. (e.g. std::shared_ptr<> here)
    void* get() const override { return m_model.get(); }
    long use_count() const override { return m_model.use_count(); }

  private:
    TM m_model;
  };

public:
  // The rule of five is applied to use std::unique_ptr<> as a member variable.
  AnySharedPtr() = default;
  AnySharedPtr(const AnySharedPtr& rhs) : m_concept(rhs.m_concept->clone()) {}
  // Non-const constructor is required here to prevent the perfect forwarding constuctor.
  AnySharedPtr(AnySharedPtr &rhs) : AnySharedPtr(static_cast<const AnySharedPtr&>(rhs)) {}
  AnySharedPtr(AnySharedPtr&&) = default;
  template <typename TM> // perfect forwarding constructor
  AnySharedPtr(TM&& obj) : m_concept(std::make_unique<Model<TM>>(std::forward<TM>(obj))) {}
  ~AnySharedPtr() = default;

  AnySharedPtr& operator=(const AnySharedPtr& rhs)
  { m_concept = rhs.m_concept->clone(); return *this; }
  AnySharedPtr& operator=(AnySharedPtr& rhs)
  { return operator=(static_cast<const AnySharedPtr&>(rhs)); }
  AnySharedPtr& operator=(AnySharedPtr&&) = default;
  template <typename TM> // perfect forwarding assignment operator
  AnySharedPtr& operator=(TM&& obj)
  { m_concept = std::make_unique<Model<TM>>(std::forward<TM>(obj)); return *this; }

  // Interface methods for Any types. (e.g. std::shared_ptr<> here)
  void* get() const { return m_concept->get(); }
  long use_count() const { return m_concept->use_count(); }

private:
  std::unique_ptr<Concept> m_concept; // storage for type erasure
};

int main()
{
  std::shared_ptr<int> si = std::make_shared<int>(10), si_copy1 = si, si_copy2 = si_copy1;
  std::shared_ptr<std::string> ss = std::make_shared<std::string>("hello"), ss_copy = ss;
  
  std::vector<AnySharedPtr> any_ptrs;
  any_ptrs.push_back(si); any_ptrs.push_back(ss);
  for(auto p : any_ptrs) { std::cout << "Ptr: " << p.get() << ", " << p.use_count() << '\n'; }
  
  return 0;
}

Slot - Delegate의 재 발명

Signals and Slots를 구현해 본지 2년이 됐는데 문득 아쉬웠던 부분 들이 떠올라서 심심삼아 바퀴를 다시 발명해 보기로 했다. Signals and Slots는 Multicast Delegate와 비슷한 개념이다. Delegate의 특별한 응용 분야라고 생각할 수도 있다. 그래서, 일단 Delegate 구현시 부족했던 부분을 다시 채워 보기로 했다.

이전 버전에서는 Slot이 독립적인 Delegate 역할을 하는데는 한계가 있었다. 가장 찜찜했던 부분은 역시나 표준 c++을 따르지 않는 것이었다. 문제는 표준 c++에서 멤버 함수의 pointer를 직접 저장할 수 있는 방법이 없다는 것이다. Template을 이용해서 멤버 함수를 컴파일러가 바인딩하도록 해주면 실행 속도도 빨라지고 문제가 해결되긴 하지만 Delegate 사용시 interface가 매우 불편하다. 궁극적으로 Qt의 Signals and Slots 스타일로 사용할 수 없다. 사실, reinterpret_cast<>나 union을 이용해서 type-punning(억지로 형 바꾸기)한 변수들을 사용하는 부분은 모두 표준 c++에 위배된다. 억지로 바꾸려다 형 한테 맞는다???

흠, 혹시나해서 구글링해 보니 그 간에도 수 많은 넘들이 자신 만의 Delegate을 발명하고 있더라. Delegate가 흥미로운 놈인건 사실이다. 특히나 c++을 배우고 있다면 한번 쯤 자신의 바퀴를 발명해 보기 바란다. c++ 언어 자체가 계속 버전업 되다 보니 새로운 방식으로 도전해 보는 이들도 있다. 이를 테면 c++20의 concept을 활용해 볼 수도 있겠다. 여기서는 너무 멀리는 가지 않고 c++17의 if constexpr와 std::invocable을 이용해서 코드를 단순화 시켰다. 

근본적인 문제를 해결했는데, c++ 표준에서 함수/멤버 함수 pointer는 void* 포인터로 저장할 수 없지만, object instance는 void* 포인터로 저장할 수 있다는 점을 이용한 것이다. void*는 객체를 저장하기 위한 포인터이기 때문에, 비객체 포인터를 void*에 강제 할당하는 것은 표준 c++에서 벗어난다. 여기를 보면 c++ 객체에 대해 올바르게 이해할 수 있다. 또, 억지로 형 바꾸기를 하면 안되는 이유도 알 수 있다.  즉, 함수/멤버 함수 포인터를 객체 class로 감싸주면 void*에 저장할 수 있게 된다.

void*에 데이터를 저장하게 되면 객체들의 type을 모두 잃어 버리게 되는데, template type deduction을 이용해서 type을 복원해 주어야 한다. 형을 지웠다가 다시 쓸 수 있게 하는 넘들을 Type Erasure(형 지우개)라 하더라. Delegate Pattern에서는 inheritance를 사용하는데 다중 상속시 발생하는 문제와  virtual table 참조에 의한 성능 문제 때문에 자신 만의 Delegate를 만드는 넘들이 생겨났다. 

이렇게 만들어진 Delegate는 실상 std::function<>을 다시 발명한 것이다. 원래 std::function<>이 표준 Delegate인 셈이다. 하지만, std::function<>은 상당히 무겁고 느린 편이다. 더구나 안전을 보장하기 위해 모든 Callable 객체를 복사해 두기 때문에, Callable 객체들을 비교해야 한다면 추가적인 성능 부담이 생길 수 밖에 없는 구조다. 여기를 보니까 std::function<>을 다시 발명하고자 할 때 고려해야 할 점들을 잘 정리했더라. lambda도 Delegate의 역할을 일정부분 수행할 수는 있지만 Signals & Slots를 포함한 다양한 분야에 적용하는데 한계가 있다.

결론적으로, 아래와 같이  Slot이라는 나만의 Delegate를 다시 만들었다. SBO(Small Buffer Optimization) 라든가 Placement new라든가 하는 소소한 기법들이 들어가 있다. 사용법은 std::function<>과 거의 동일하고, 멤버 함수의 경우 std::bind<>를 사용하지 않고도 바로 초기화해서 사용할 수 있다. 

재미삼아 만들긴 했지만 이전 버전과 비교해서 여러가지 감안해도 두배 이상 소스가 늘어났다. 표준을 따르는게 얼마나 고된 일인가? 그니까 표준을 잘 만들어라~!!!

// Slot (Delegate or Callback) C++ Implementation
//
// This program is copyright (c) 2020 by Umundu @ https://zapary.blogspot.com .
// It is distributed under the terms of the GNU LGPL version 3, as detailed in
// https://opensource.org/licenses/lgpl-3.0.html .
//
// There are so many c++ Delegate implementaions. -  What's the point in this Slot?
// => Make simple interface without losing performance while keeping c++ standard.
//
//  o Simple usage can be extended to Signals and Slots(Qt) style interface: e.g)
//    Slot<double(int)> s1, s2(&obj, &Derived::doWork), s3([&c](int i){ return c+i; }), s4;
//    s1 = lambda; s4 = free_function; double result = s3(100);
//  o Comparison of two Slots is based on the IDs that are created from the source objects.
//  o Can be used as a light weight version of std::function<>.
//
//  * Compiler requirements: c++17 - supporting c++11 could be handy by replacing two parts:
//    - std::is_invocable_r<> => can be replaced to std::is_convertible<> things.
//    - if constexpr()        => can be replaced by using the SNIFAE.

#include <functional>
#include <memory>

template <typename T> class Slot;
template <typename TR, typename... TAs>
class Slot<TR(TAs...)>
{
  static constexpr size_t BufferMaxSize = 32;
  using TypeID = size_t;
  using TypePF = TR(*)(TAs...);
  using TypeCallback = TR(*)(void*, TAs&&...);
  using TypeCleaner = void(*)(void*);
  using TypeOPF = struct { TypePF pf; };

  // All the callables should be std::is_invocable_r<TR, TO, TAs...> OK.
  // Non-static member function is the most special citizen among the callables.
  // Comparing with the type of a function pointer(TypePF):
  //   Callables =>  |free fn|static member fn|lambda w/o capture|functor & lambda w/ capture
  //   is_same       |  yes  |      yes       |       no         |     no
  //   is_assignable |  yes  |      yes       |       yes        |     no
  template <typename T>
  using TypeIfFunction = typename std::enable_if<std::is_assignable<TypePF&, T>{}>::type;
  template <typename T>
  using TypeIfFunctor = typename std::enable_if<!std::is_assignable<TypePF&, T>{}
    && !std::is_same<std::decay<Slot>::type, std::decay<T>::type>{} // use default ctors.
    && std::is_invocable_r<TR, T, TAs...>{}>::type; // since c++17.

public:
  // Use default constructors for Slot according to the rule of zero.
  Slot() = default;
  Slot(const std::nullptr_t) noexcept : Slot() {};

  // for free functions, lambdas without capture and static member functions.
  template <typename TF, typename = TypeIfFunction<TF>>
  explicit Slot(TF pf) noexcept { bind(pf); }

  // for functors including lambdas with capture and std::function<>.
  template <typename TF, typename = TypeIfFunctor<TF>>
  Slot(TF&& pobj) noexcept { bind(std::forward<TF>(pobj)); }

  // for static member functions
  template <typename TB>
  explicit Slot(TB*, TypePF pmf) noexcept { bind(pmf); }

  // for non-static member functions
  template <typename TB, typename TO>
  Slot(TO* pobj, TR(TB::*pmf)(TAs...)) noexcept { bind(pobj, pmf); }
  template <typename TB, typename TO>
  Slot(const TO* pobj, TR(TB::*pmf)(TAs...) const) noexcept { bind(pobj, pmf); }

  Slot& operator=(TypePF pf) { bind(pf); return *this; }
  template <typename TF, typename = TypeIfFunctor<TF>>
  Slot& operator=(TF&& fn) noexcept { bind(std::forward<TF>(fn)); return *this; }

  explicit operator bool() const { return m_obj; }
  bool operator==(const Slot& rhs) const { return m_id == rhs.m_id; }
  bool operator!=(const Slot& rhs) const { return !operator==(rhs); }
  bool operator==(const std::nullptr_t) const { return !m_obj; }
  bool operator!=(const std::nullptr_t) const { return m_obj; }

  TypeID id() const { return m_id; }
  TR operator()(TAs&&... args) const noexcept { return emit(std::forward<TAs>(args)...); }
  TR emit(TAs&&... args) const noexcept
  {
    if(!m_obj) return TR();
    if(m_callback) return m_callback(m_obj, std::forward<TAs>(args)...);
    return (*static_cast<TypeOPF*>(m_obj)->pf) (std::forward<TAs>(args)...);
  }

protected:
  void bind(TypePF pf) noexcept
  {
    m_id = hash(reinterpret_cast<void*>(pf), nullptr);
    // Using storage for function pointer types is a design choice(cf. using template).
    // NB: type-punning by reinterpret_cast<> for a function pointer violates the c++ standard.
    store<TypeOPF>(std::move(TypeOPF{pf}));
  }

  template <typename TF, typename = TypeIfFunctor<TF>>
  void bind(TF&& fn) noexcept
  {
    using typeF = typename std::decay<TF>::type;
    // NB: any valid objects can be referenced to the generic pointer(void*).
    //   - functions, member functions and references are not objects.
    //   - so their pointers can't be converted to the generic pointer.
    m_obj = &fn;
    auto pmf = &typeF::operator();
    m_id = hash(m_obj, reinterpret_cast<void*>(reinterpret_cast<void(*&)()>(pmf)));
    m_callback = callFunctor<typeF>;
    // Storage is required for RValue lambdas with capture.
    // LValue functors including lambdas with capture can be called directly.
    if constexpr(!std::is_reference<TF>{}) store<typeF>(std::move(fn)); // since c++17.
  }

  template <typename TB, typename TPMF>
  void bind(TB&& pobj, TPMF&& pmf) noexcept
  {
    using typeTB = typename std::decay<TB>::type;
    using typeMF = struct { typeTB obj; typename std::decay<TPMF>::type pmf; };
    // Somthing weird but possible way.
    m_id = hash(pobj, reinterpret_cast<void*>(reinterpret_cast<void(*&)()>(pmf)));
    m_callback = callMember<typeMF>;
    // Using storage for non-static member functions is a design choice.
    // This is trade-off in using interfaces between fast but inconvenient template style
    // versus rather slow but more convenient std::function<> style.
    // NB: type-punning by reinterpret_cast<> for pointer to member functions violates
    //     the c++ standard.
    store<typeMF>(std::move(typeMF{std::forward<TB>(pobj), std::forward<TPMF>(pmf)}));
  }

private:
  size_t hash(const void* obj, const void* pmf) const
  { return reinterpret_cast<size_t>(obj) ^ reinterpret_cast<size_t>(pmf); }

  template <typename TF>
  static TR callFunctor(void* vobj, TAs&&... args) noexcept  // Why static?
  { return (static_cast<TF*>(vobj)->operator())(std::forward<TAs>(args)...); }

  template <typename TP>
  static TR callMember(void* vobj, TAs&&... args) noexcept   // Why static? => Your homework!
  {
    TP* pobj = static_cast<TP*>(vobj);
    return (pobj->obj->*pobj->pmf)(std::forward<TAs>(args)...);
  }

  template <typename TF>
  void store(TF&& fn)
  {
    using typeF = typename std::decay<TF>::type;
    // Use a fixed small buffer for normal cases - so called SBO(Small Buffer Optimization).
    if constexpr(sizeof(typeF) <= BufferMaxSize) {  // since c++17.
      m_size = sizeof(typeF);
      if(m_cleaner) m_cleaner(&m_buffer);
      new (m_buffer) typeF(std::move(fn));
      m_obj = m_buffer;
      m_cleaner = cleaner<TF>;
    }
    // Allocate heap memory only if the current buffer does not fit.
    else {
      if(sizeof(typeF) > m_size || m_data.use_count() > 1) {
        m_size = sizeof(typeF);
        m_data.reset(operator new(m_size), deleter<TF>);
      }
      else m_cleaner(m_data.get());
      new (m_data.get()) typeF(std::move(fn));
      m_obj = m_data.get();
      m_cleaner = cleaner<TF>;
    }
  }

  template <typename T>
  static void cleaner(void* p) { static_cast<T*>(p)->~T(); }
  template <typename T>
  static void deleter(void* p) { static_cast<T*>(p)->~T(); operator delete(p); }

private:
  void* m_obj{nullptr};                    // object pointer
  TypeCallback m_callback{nullptr};        // callback pointer
  TypeCleaner m_cleaner{nullptr};          // pointer to a storage cleaner
  char m_buffer[BufferMaxSize];            // small buffer storage
  std::shared_ptr<void> m_data{nullptr};   // big data storage
  size_t m_size{0};                        // size of data storage
  TypeID m_id{0};                          // Slot id
};

Circular Queue와 Iterator

Circular Queue(Buffer)를 c++로 구현해 보았다. Ring Buffer로 오래 전부터 네트워크 프로그램에서 많이 사용하던 놈이다. 컨테이너 Class 들은 c++을 배우고, 또 적응하는데 매우 도움이 된다. 단지 공부하려고 만든 것은 아니고 실시간 차트 데이터를 저장하는데 적용해 보려고 만든 것이다.

그 간에는 std::deque을 사용했었는데 뒤에서 채우고 앞에서 지우는 식으로 고정크기를 유지했는데, 메모리 관리를 내 맘대로 못하는게 문제였고 성능 문제가 생길 수 밖에 없었다.  아예 첨부터 고정크기 메모리를 할당해서 사용하는게 효율적이고, 실시간 데이터는 시간 단위로 저장하면 되기 때문에 필요한 메모리 크기를 사전에 예측할 수 있다. 결론은 피부로 느낄만큼 성능향상 효과가 있더라.

성능을 높이는 김에 메모리 할당 외에 fast modulo 함수를 사용했다. Circular Buffer의 특성상 메모리 상에서 현재 데이터의 위치를 빠르게 알아내야 하는데 나머지(%) 연산을 해야만 한다. 다행히도 나누는 수가 양수이고 2의 거듭제곱(power of 2)이라면 bit 연산으로 나머지를 빠르게 계산할 수 있다. 여기서 나누는 수는 고정크기 용량 또는 최대 저장 크기이다. 그리고, 사용자가 용량을 적당히 지정하더라도 무조건 가까운 크기의 2의 거듭제곱으로 용량을 설정하도록 하였다. 이렇게 하지 않으면 나머지 연산 결과가 엉뚱하게 나오기 때문이다.

Circular Queue

// Circular Queue(Buffer) and Circular Iterator C++ Implementation
//
// This program is copyright (c) 2019 by Umundu @ https://zapary.blogspot.com .
// It is distributed under the terms of the GNU LGPL version 3, as detailed in
// https://opensource.org/licenses/lgpl-3.0.html .

#include <memory>

template<typename TC>
class CircularIterator;

template<typename TD>
class CircularQueue
{
public:
  using value_type      = TD;
  using reference       = TD&;
  using const_reference = TD const&;
  using pointer         = TD*;
  using const_pointer   = TD const*;
  using difference_type = std::ptrdiff_t;
  using size_type       = std::size_t;
  using iterator        = CircularIterator<CircularQueue>;
  using const_iterator  = CircularIterator<const CircularQueue>;
  using riterator       = std::reverse_iterator<iterator>;
  using const_riterator = std::reverse_iterator<const_iterator>;

public:
  CircularQueue() = default;
  CircularQueue(size_type capacity)
    : m_capacity(toPow2(capacity)), m_data(new TD[m_capacity]{}) {}
  template<typename TI>
  CircularQueue(TI b, TI e)
    : m_capacity(toPow2(std::distance(b, e))), m_data(new TD[m_capacity]{})
  { for(auto it = b; it != e; ++it) push_back(*it); }
  CircularQueue(std::initializer_list<TD> const& il)
    : CircularQueue(std::begin(il), std::end(il)) {}
  ~CircularQueue() { destroy(); }

  CircularQueue(const CircularQueue& cq)
    : m_capacity(cq.m_capacity), m_nDequeue(cq.m_nDequeue), m_nOverflow(cq.m_nOverflow),
      m_nUnderflow(cq.m_nUnderflow), m_nRemoved(cq.m_nRemoved), m_data(new TD[m_capacity]{})
  {
    try {
      for(size_type i = 0; i < cq.m_size; ++i) push_back(cq[i]);
      // Note: m_capacity and m_size are already set.
      //       m_head and m_tail should be reset automatically in updateSize().
      m_nEnqueue = cq.m_nEnqueue;
    }
    catch(...) { destroy(); throw; }
  }
  CircularQueue& operator=(const CircularQueue& cq)
  {
    if(this != &cq) { CircularQueue<TD> tmp(cq); tmp.swap(*this); }
    return *this;
  }
  CircularQueue(CircularQueue&& cq) noexcept { cq.swap(*this); }
  CircularQueue& operator=(CircularQueue&& cq) noexcept { cq.swap(*this); return *this; }

  bool            empty() const    { return !m_size; }
  bool            full() const     { return m_size == m_capacity - 1; }
  size_type       size() const     { return m_size; }
  size_type       capacity() const { return m_capacity - 1; } // for iterators
  size_type       removed() const  { return m_nRemoved; }

  reference       at(size_type idx)
                  { validate(idx); return *(m_data + modCapacity(m_head + idx)); }
  const_reference at(size_type idx) const
                  { validate(idx); return *(m_data + modCapacity(m_head + idx)); }
  reference       operator[](size_type idx) { return *(m_data + modCapacity(m_head + idx)); }
  const_reference operator[](size_type idx) const
                  { return *(m_data + modCapacity(m_head + idx)); }
  reference       front()          { return *(m_data + m_head); }
  const_reference front() const    { return *(m_data + m_head); }
  reference       back()           { return *(m_data + (m_tail ? m_tail - 1 : m_capacity - 1)); }
  const_reference back() const     { return *(m_data + (m_tail ? m_tail - 1 : m_capacity - 1)); }

  iterator        begin()          { return iterator(this, m_data + m_head); }
  riterator       rbegin()         { return riterator(end()); }
  const_iterator  begin() const    { return const_iterator(this, m_data + m_head); }
  const_riterator rbegin() const   { return const_riterator(end()); }
  iterator        end()            { return iterator(this, m_data + m_tail); }
  riterator       rend()           { return riterator(begin()); }
  const_iterator  end() const      { return const_iterator(this, m_data + m_tail); }
  const_riterator rend() const     { return const_riterator(begin()); }
  const_iterator  cbegin() const   { return begin(); }
  const_riterator crbegin() const  { return rbegin(); }
  const_iterator  cend() const     { return end(); }
  const_riterator crend() const    { return rend(); }

  void enqueue(const value_type& item) { push_back(item); }
  void enqueue(value_type&& item) noexcept { move_back(std::move(item)); }
  template<typename... TAs>
  void enqueue(TAs&&... args) noexcept { emplace_back(std::move(args)...); }

  TD dequeue() noexcept
  {
    if(!m_size) {
      ++m_nUnderflow;
      return TD{};
    }

    TD item = std::move(*(m_data + m_head));
    m_head = modCapacity(++m_head);
    --m_size;
    ++m_nDequeue;
    ++m_nRemoved;
    return item; // Respect RVO for local objects.
  }

  void reserve(size_type capacity)
  {
    if(m_capacity >= capacity) return;
    capacity = toPow2(capacity);
    reserveData(capacity);
  }

private:
  // Return a number with a power of 2 that is larger but the most adjacent to a given value.
  size_type toPow2(size_type value) const
  {
    int hbit = 0;
    for(; value != 1; ++hbit) value >>= 1;
    return (size_type(1 << hbit) == value) ? value : 1 << (hbit + 1);
  }
  // Return a fast modulo. m_capacity is assumed a power of 2 and positive number.
  size_type modCapacity(size_type num) const { return num & (m_capacity - 1); }

  void validate(size_type idx) const
  { if(idx >= m_size || !m_capacity) throw std::out_of_range("Error: index out of range."); }

  void updateSize()
  {
    ++m_nEnqueue;
    m_tail = modCapacity(++m_tail);

    // If Queue is full(or empty) head and tail are same. This makes iterators useless.
    if(m_size == m_capacity - 1) {
      ++m_nRemoved;
      ++m_nOverflow;
      m_head = modCapacity(m_tail + 1); // Make head != tail for iterators.
    }
    else ++m_size;
  }

  void push_back(const TD& item) { *(m_data + m_tail) = item; updateSize(); }
  void move_back(TD&& item) noexcept { *(m_data + m_tail) = std::move(item); updateSize(); }
  template<typename... TAs>
  void emplace_back(TAs&&... args) noexcept
  { *(m_data + m_tail) = TD(std::move(args)...); updateSize(); }

  void reserveData(size_type capacity)
  {
    CircularQueue<TD> tmp(capacity);
    restoreData(tmp);
    tmp.swap(*this);
  }

  void restoreData(CircularQueue<TD>& cq)
  {
    if(!m_size) return;
    for(size_type i = 0; i < m_size; ++i) cq.move_back(std::move((*this)[i]));
    // Note: m_capacity and m_size are already set.
    //       m_head and m_tail should be reset automatically in updateSize().
    cq.m_nEnqueue   = m_nEnqueue;
    cq.m_nDequeue   = m_nDequeue;
    cq.m_nOverflow  = m_nOverflow;
    cq.m_nUnderflow = m_nUnderflow;
    cq.m_nRemoved   = m_nRemoved;
  }

  void swap(CircularQueue& cq) noexcept
  {
    std::swap(m_capacity,   cq.m_capacity);
    std::swap(m_size,       cq.m_size);
    std::swap(m_head,       cq.m_head);
    std::swap(m_tail,       cq.m_tail);
    std::swap(m_nEnqueue,   cq.m_nEnqueue);
    std::swap(m_nDequeue,   cq.m_nDequeue);
    std::swap(m_nOverflow,  cq.m_nOverflow);
    std::swap(m_nUnderflow, cq.m_nUnderflow);
    std::swap(m_nRemoved,   cq.m_nRemoved);
    std::swap(m_data,       cq.m_data);
  }

  void destroy() { std::unique_ptr<TD, Deleter> deleter(m_data, Deleter()); }

private:
  struct Deleter { void operator()(TD* data) const { delete[] data; } };

  size_type m_capacity{0};   // queue capacity
  size_type m_size{0};       // current data size
  size_type m_head{0};       // head index
  size_type m_tail{0};       // tail index
  size_type m_nEnqueue{0};   // enqueued data size(m_size + m_nRemoved)
  size_type m_nDequeue{0};   // dequeued data size
  size_type m_nOverflow{0};  // overflowed data size
  size_type m_nUnderflow{0}; // underflowed data size
  size_type m_nRemoved{0};   // removed(m_nOverflow + m_nDequeue) data size
  TD* m_data{nullptr};       // data storage

  friend iterator;
  friend const_iterator;
};

Circular Iterator

만드는 김에 iterator까지 만들어 보았다. 로직이 간단하지는 않아서 애를 좀 먹었다. STL 표준 iterator들은 컨테이너의 begin()과 end() 함수만으로 동작하는데, Circular Queue의 경우 두 함수가 동일한 메모리 주소를 갖는 경우가 생기기 때문에 구현하기 어렵다. 즉, Queue가 비어 있거나 꽉찼을 때 head와 tail 위치가 같아진다. loop를 아예 돌릴 수 없거나 무한 loop를 돌게 되는 상황에 빠진다.

나의 해결 방법은 head와 tail이 같아지지 않도록 하여 정확히 1 cycle의 loop이 돌게 하였다. 대신 최대 데이터 크기는 고정 용량 크기 보다 1개 줄어든다.

// Circular Queue(Buffer) and Circular Iterator C++ Implementation
//
// This program is copyright (c) 2019 by Umundu @ https://zapary.blogspot.com .
// It is distributed under the terms of the GNU LGPL version 3, as detailed in
// https://opensource.org/licenses/lgpl-3.0.html .

#include "CircularQueue.h"

template<typename TC>
class CircularIterator
{
public: // Should be public!
  using iterator_category = std::random_access_iterator_tag;
  using value_type        = typename TC::value_type;
  using pointer           = typename TC::pointer;
  using difference_type   = typename TC::difference_type;
  using size_type         = typename TC::size_type;
  using reference         = typename TC::reference;

public:
  CircularIterator() = default;
  CircularIterator(const CircularIterator& it) : m_cque{it.m_cque}, m_it{it.m_it} {}
  CircularIterator(TC* co, const pointer po) : m_cque{co}, m_it{po} {}

  CircularIterator& operator=(const CircularIterator& it)
  {
    if(this == &it) return *this;
    m_cque = it.m_cque;
    m_it = it.m_it;
    return *this;
  }

  reference operator*() const { return *m_it; }
  pointer operator->() const { return &(operator*()); }

  CircularIterator& operator++() {
    if(++m_it == m_cque->m_data + m_cque->m_capacity) m_it = m_cque->m_data;
    return *this;
  }
  CircularIterator operator++(int) {
    CircularIterator tmp = *this;
    ++*this;
    return tmp;
  }
  CircularIterator& operator--() {
    if(m_it == m_cque->m_data) m_it = m_cque->m_data + m_cque->m_capacity;
    --m_it; // note!
    return *this;
  }
  CircularIterator operator--(int) {
    CircularIterator tmp = *this;
    --*this;
    return tmp;
  }

  CircularIterator& operator+=(difference_type n) {
    if(n > 0) m_it = m_cque->m_data + m_cque->modCapacity(m_it - m_cque->m_data + n);
    else if(n < 0) *this -= -n;
    return *this;
  }
  CircularIterator& operator-=(difference_type n) {
    if(n > 0) {
      difference_type idx = m_it - m_cque->m_data;
      m_it = m_cque->m_data +
             (n > idx ? m_cque->m_capacity - m_cque->modCapacity(n - idx) : idx - n);
    }
    else if(n < 0) *this += -n;
    return *this;
  }
  CircularIterator operator+(difference_type n) const { return CircularIterator(*this) += n; }
  CircularIterator operator-(difference_type n) const { return CircularIterator(*this) -= n; }
  difference_type operator+(CircularIterator& it) const
  { return m_cque->modCapacity(index(m_it) + index(it.m_it)); }
  difference_type operator-(CircularIterator& it) const
  { return index(m_it) - index(it.m_it); }

  reference operator[](difference_type n) const { return *(*this + n); }

  bool operator!() const { return !m_it; }
  bool operator==(const CircularIterator& it) const { return m_it == it.m_it; }
  bool operator!=(const CircularIterator& it) const { return !operator==(it); }

  bool operator<(const CircularIterator<TC>& it) const
  { return (index(m_it) < index(it.m_it)); }
  bool operator>(const CircularIterator<TC>& it) const
  { return (index(m_it) > index(it.m_it)); }
  bool operator<=(const CircularIterator& it) const { return !(operator>(it)); }
  bool operator>=(const CircularIterator& it) const { return !(operator<(it)); }

private:
  difference_type index(const pointer& it) const
  {
    difference_type idx = it - m_cque->m_data - m_cque->m_head;
    return idx < 0 ? m_cque->m_capacity + idx : idx;
  }

  const TC* m_cque{nullptr}; // CircularQueue
  pointer   m_it{nullptr};   // iterator
};

Test 결과

테스트 결과만 아래에 보였다. 잘 돌아간다~!!!

===============[[  Queue: 0x7ffcd5d379a0 Status  ]]===============
=== Queue capacity(the maximum data size)        : 15
=== Current(queue keeping) data size             : 15
=== Enqueued(= Current + Removed) size           : 46
=== Dequeued size                                : 15
*** Overflowed(starving capacity) size           : 16
*** Underflowed(starving enque data) size        : 5
*** Removed(= Dequeued + Overflowed) size        : 31
=== Head/Front(next dequeue point) index (value) : 3 (8)
=== Back(the last data point) index (value)      : 1 (-48)
=== Tail(next enqueue point) index               : 2
-------------< Storage Data in memory address order >-------------
-49, -48, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, 
-------------<    Current Data in enqueued order    >-------------
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, 
==================================================================

*** for-loop test on a Circular Queue
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, index loop
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, auto iterator
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, iterator
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, const iterator
-48, -49, -50, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, reverse iterator
-48, -49, -50, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, c-r iterator
-50, -49, -48, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, std::sort()

Tip: 함수 성능 측정을 위한 Simple Timer

가끔 함수 성능 측정을 해야 하는데 아래와 같은 Simple Timer 하나 장만해 두면 편하다.

#include <chrono>
#include <thread>

using namespace std::chrono_literals;
// Simple Timer
class Timer {
  using TClock = std::chrono::high_resolution_clock;
  using TTime = decltype(TClock::now());

public:
  Timer() : m_start(TClock::now()) {}
  operator long()
  {
    auto interval = std::chrono::duration_cast<std::chrono::microseconds>
                    (TClock::now() - m_start).count();
    reset();
    return interval;
  }
  void reset() { m_start = TClock::now(); }

private:
  TTime m_start;
};

아래와 같이 간단하게 사용할 수 있다.

void main()
{
  Timer now;
  for(size_t i = 0; i < 1000; ++i) [] { std::this_thread::sleep_for(2ms); };
  std::cout << "f1: " << now << '\n';

  for(size_t i = 0; i < 1000; ++i) [] { std::this_thread::sleep_for(3ms);};
  std::cout << "f2: " << now << '\n';
}