Ring allocator

# はじめに
リング状にメモリを管理するアロケータになります. 様々なところに利用されているにも関わらず, 各標準ライブラリに入らないのは, 用途によって最適な実装が異なり過ぎて, 汎化し難いためと思われます.
所謂, 配列でも同じことができますが, 先頭に対する操作, C++では`push_front`, `pop_front`の操作を効率的に行うために有用です.

# 確保・解放
実装は様々ですが, 一例として初期状態が次のような例を考えます. 初期状態では, リングの先頭と末尾の後ろが同じ位置にあります.

![ring00.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/fc92829b-b2d6-d37a-16ae-c134e16291dd.jpeg)

末尾に2つ要素を追加すると, 要素を入れながら末尾も移動します.
![ring01.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/efde257c-f26d-8ce8-687a-267cc8d99d45.jpeg)

次に, 先頭から要素を取り出すとき, 要素を取り出しながら先頭を移動します.
![ring02.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/c5ab49d2-699c-a232-7e8d-2f3ea1e27208.jpeg)

これらの操作を配列で実現しようとすると, コピーや`std::move`相当の操作が必要になり, 比較してコストが高くなります.


# 実装

## 固定サイズ

最も単純な, 固定サイズでPlain Old Dataに対するコードを書きます. `size_`を持っているのは, `head_`と`tail_`が等しかった場合に, 完全に空か, 満たされているかわからないからです. これも, フラグで管理したり, 用途によって最適な解放は異なります.
余談ですが, PODという名前がなくなるのは知っていますが, もっと良い名前はないでしょうか？ `TriviallyCopyable`と末尾に付けるのでしょうか.
固定サイズですと, ポインタが末尾・先頭を超えると反対に移動するだけですので簡単です.

<details><summary>Ring Allocator</summary><div>

```cpp
template<class T, u32 SIZE, class SIZE_TYPE = u32>
class FixedRingBufferPOD
{
public:
    static_assert(std::is_trivially_copyable<T>::value, "T should be trivially copyable.");
    static_assert(0 < SIZE, "SIZE should not be zero.");

    typedef FixedRingBufferPOD<T, SIZE, SIZE_TYPE> this_type;
    typedef T value_type;
    static constexpr SIZE_TYPE MaxSize = static_cast<SIZE_TYPE>(SIZE);
    typedef SIZE_TYPE size_type;

    FixedRingBufferPOD();
    FixedRingBufferPOD(this_type&& other);
    ~FixedRingBufferPOD();

    FixedRingBufferPOD& operator=(this_type&& other);

    inline size_type capacity() const;
    inline size_type size() const;
    inline bool empty() const;

    inline size_type head() const;
    size_type next(size_type pos) const;

    void push_back(const T& x);
    void pop_front();

    const value_type& front() const;
    const value_type& operator[](size_type pos) const;
private:
    FixedRingBufferPOD(const this_type&) = delete;
    this_type& operator=(const this_type& queue) = delete;

    size_type head_;
    size_type tail_;
    size_type size_;
    value_type items_[MaxSize];
};

template<class T, u32 SIZE, class SIZE_TYPE>
FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::FixedRingBufferPOD()
    : head_(0)
    , tail_(0)
    , size_(0)
    , items_{}
{
}

template<class T, u32 SIZE, class SIZE_TYPE>
FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::FixedRingBufferPOD(this_type&& other)
    : head_(other.head_)
    , tail_(other.tail_)
    , size_(other.size_)
{
    memcpy(items_, other.items_, sizeof(value_type) * MaxSize);

    other.head_ = 0;
    other.tail_ = 0;
    other.size_ = 0;
    memset(other.items_, 0, sizeof(value_type) * MaxSize);
}

template<class T, u32 SIZE, class SIZE_TYPE>
FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::~FixedRingBufferPOD()
{
}

template<class T, u32 SIZE, class SIZE_TYPE>
FixedRingBufferPOD<T, SIZE, SIZE_TYPE>& FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::operator=(this_type&& other)
{
    if(this != &other) {
        head_ = other.head_;
        tail_ = other.tail_;
        size_ = other.size_;
        memcpy(items_, other.items_, sizeof(value_type) * MaxSize);

        other.head_ = 0;
        other.tail_ = 0;
        other.size_ = 0;
        memset(other.items_, 0, sizeof(value_type) * MaxSize);
    }
    return *this;
}

template<class T, u32 SIZE, class SIZE_TYPE>
inline typename FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::size_type FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::capacity() const
{
    return MaxSize;
}

template<class T, u32 SIZE, class SIZE_TYPE>
inline typename FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::size_type FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::size() const
{
    return size_;
}

template<class T, u32 SIZE, class SIZE_TYPE>
inline bool FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::empty() const
{
    return size_ <= 0;
}

template<class T, u32 SIZE, class SIZE_TYPE>
inline typename FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::size_type FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::head() const
{
    return head_;
}

template<class T, u32 SIZE, class SIZE_TYPE>
typename FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::size_type FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::next(size_type pos) const
{
    ++pos;
    if(MaxSize<=pos){
        pos = 0;
    }
    return pos;
}

template<class T, u32 SIZE, class SIZE_TYPE>
void FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::push_back(const T& x)
{
    assert(size_ < MaxSize);
    items_[tail_] = x;
    ++tail_;
    if(MaxSize <= tail_) {
        tail_ = 0;
    }
    ++size_;
}

template<class T, u32 SIZE, class SIZE_TYPE>
void FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::pop_front()
{
    assert(0 < size_);
    ++head_;
    if(MaxSize <= head_) {
        head_ = 0;
    }
    --size_;
}

template<class T, u32 SIZE, class SIZE_TYPE>
const typename FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::value_type& FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::front() const
{
    assert(0 < size_);
    return items_[head_];
}

template<class T, u32 SIZE, class SIZE_TYPE>
const typename FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::value_type& FixedRingBufferPOD<T, SIZE, SIZE_TYPE>::operator[](size_type pos) const
{
    assert(pos < MaxSize);
    return items_[pos];
}
```
</div></details>

## 位置とサイズだけ管理
確保した位置とサイズだけ管理する, 特殊用途バージョンです.
動画像のフレームや, TCPのシーケンスなど戻らないインクリメントされる値とともに使用します. フレーム単位でメモリが必要で, そのフレームの処理が終わらないと解放できないパターンに使用します.

<details><summary>Frame Ring Allocator</summary><div>

```cpp
template<u32 MAX_FRAMES>
class FrameRingBuffer
{
public:
    typedef FrameRingBuffer<MAX_FRAMES> this_type;

    static constexpr u32 MaxFrames = MAX_FRAMES;

    FrameRingBuffer(u32 capacity);
    FrameRingBuffer(this_type&& other);
    ~FrameRingBuffer();

    this_type& operator=(this_type&& other);

    inline u32 capacity() const;
    inline u32 size() const;

    bool allocate(u32& offset, u32 size);

    void endCurrentFrame(u64 frame);
    void releaseCompletedFrames(u64 frame);

#ifdef _DEBUG
    void print();
#endif
private:
    FrameRingBuffer(const FrameRingBuffer&) = delete;
    FrameRingBuffer& operator=(FrameRingBuffer&) = delete;

    struct FrameTail
    {
        u64 frame_;
        u32 offset_;
        u32 size_;
    };

    u32 capacity_;
    u32 head_;
    u32 tail_;
    u32 totalUsed_;
    u32 currentUsed_;
    FixedRingBufferPOD<FrameTail, MaxFrames, u8> completedFrames_;
};

template<u32 MAX_FRAMES>
FrameRingBuffer<MAX_FRAMES>::FrameRingBuffer(u32 capacity)
    : capacity_(capacity)
    , head_(0)
    , tail_(0)
    , totalUsed_(0)
    , currentUsed_(0)
{
}

template<u32 MAX_FRAMES>
FrameRingBuffer<MAX_FRAMES>::~FrameRingBuffer()
{
}

template<u32 MAX_FRAMES>
FrameRingBuffer<MAX_FRAMES>::FrameRingBuffer(this_type&& other)
    : capacity_(other.capacity_)
    , head_(other.head_)
    , tail_(other.tail_)
    , totalUsed_(other.totalUsed_)
    , currentUsed_(other.currentUsed_)
    , completedFrames_(forward<decltype(completedFrames_)>(other.completedFrames_))
{
    other.capacity_ = 0;
    other.head_ = 0;
    other.tail_ = 0;
    other.totalUsed_ = 0;
    other.currentUsed_ = 0;
}

template<u32 MAX_FRAMES>
typename FrameRingBuffer<MAX_FRAMES>::this_type& FrameRingBuffer<MAX_FRAMES>::operator=(this_type&& other)
{
    if(this == &other) {
        return *this;
    }

    capacity_ = other.capacity_;
    head_ = other.head_;
    tail_ = other.tail_;
    totalUsed_ = other.totalUsed_;
    currentUsed_ = other.currentUsed_;
    completedFrames_ = forward<decltype(completedFrames_)>(other.completedFrames_);

    other.capacity_ = 0;
    other.head_ = 0;
    other.tail_ = 0;
    other.totalUsed_ = 0;
    other.currentUsed_ = 0;
    return *this;
}

template<u32 MAX_FRAMES>
inline u32 FrameRingBuffer<MAX_FRAMES>::capacity() const
{
    return capacity_;
}

template<u32 MAX_FRAMES>
inline u32 FrameRingBuffer<MAX_FRAMES>::size() const
{
    return totalUsed_;
}

template<u32 MAX_FRAMES>
bool FrameRingBuffer<MAX_FRAMES>::allocate(u32& offset, u32 size)
{
    if(0 < totalUsed_ && head_ == tail_) {
        return false;
    }
    if(head_ <= tail_) {
        //0 --- head xxx tail --- size
        if(size <= (capacity_ - tail_)) {
            //add to tail
            offset = tail_;
            tail_ += size;
            totalUsed_ += size;
            currentUsed_ += size;
            return true;

        }else if(size <= head_) {
            //fill until max and add to front
            u32 add = (capacity_ - tail_) + size;
            offset = 0;
            tail_ = size;
            totalUsed_ += add;
            currentUsed_ += add;
            return true;
        }
        return false;

    } else if(size <= (head_ - tail_)) {
        //xxx tail --- head xxx size
        offset = tail_;
        tail_ += size;
        totalUsed_ += size;
        currentUsed_ += size;
        return true;
    }
    return false;
}

template<u32 MAX_FRAMES>
void FrameRingBuffer<MAX_FRAMES>::endCurrentFrame(u64 frame)
{
    completedFrames_.push_back({frame, tail_, currentUsed_});
    currentUsed_ = 0;
}

template<u32 MAX_FRAMES>
void FrameRingBuffer<MAX_FRAMES>::releaseCompletedFrames(u64 frame)
{
    while(!completedFrames_.empty()) {
        const FrameTail& frameTail = completedFrames_.front();
        if(frame < frameTail.frame_) {
            break;
        }
        assert(frameTail.size_ <= totalUsed_);
        totalUsed_ -= frameTail.size_;
        head_ = frameTail.offset_;
        completedFrames_.pop_front();
    }
}

#ifdef _DEBUG
template<u32 MAX_FRAMES>
void FrameRingBuffer<MAX_FRAMES>::print()
{
    if(completedFrames_.size()<=0){
        return;
    }
    std::array<FrameTail, MaxFrames> frames;
    u8 pos = completedFrames_.head();
    for(u32 i=0; i<completedFrames_.size(); ++i, pos=completedFrames_.next(pos)){
        frames[i] = completedFrames_[pos];
    }
    std::sort(frames.begin(), frames.begin()+completedFrames_.size(),
        [](const FrameTail& x0, const FrameTail& x1){return x0.offset_<x1.offset_;});

    for(u32 i=0; i<completedFrames_.size(); ++i){
        u32 head = frames[i].offset_<frames[i].size_? 0 : frames[i].offset_-frames[i].size_;
        printf("|%d %lld|", head, frames[i].frame_);
    }
    printf("\n");
}
#endif
```
</div></details>

# テスト
テストパターンとしては足りていませんが, ここに載せるのならこんなものでしょう.

<details><summary>Test</summary><div>

```cpp
int main(void)
{
    FixedRingBufferPOD<s32, 4> queue;
    for(s32 i = 0; i < 4; ++i) {
        queue.push_back(i);
    }

    for(s32 i = 0; i < 2; ++i) {
        s32 x = queue.front();
        queue.pop_front();
        assert(i == x);
    }
    for(s32 i = 4; i < 6; ++i) {
        queue.push_back(i);
    }
    for(s32 i = 2; i < 6; ++i) {
        s32 x = queue.front();
        queue.pop_front();
        assert(i == x);
    }

    FrameRingBuffer<4> frameRingBuffer(7);
    bool result;
    u32 offset=0;

    for(u32 i=0; i<10; ++i){
        result = frameRingBuffer.allocate(offset, 2);
        frameRingBuffer.endCurrentFrame(i);
        assert(result);

        frameRingBuffer.print();
        if(2<=i){
            frameRingBuffer.releaseCompletedFrames(i-2);
        }
    }
    return 0;
}
```
</div></details>

# まとめ
何に使うの？というのは後日書くかもしれません.