c++ - 环形缓冲区的有效边界检查

Question

有些人可能已经注意到我正在尝试实现一个环形缓冲区。我希望在数据结构中有一定的安全措施，同时又不会损失太多效率。

我当前的解决方案实现了两种类型的计数器，一种是索引，它是缓冲区内存中的直接偏移量，另一种是序列号，它只是一个 size_t 类型的计数器。迭代器使用序列号来访问环形缓冲区。因此，环形缓冲区必须在每次缓冲区访问时将序列号转换为缓冲区索引。这通常是相当有效的:

size_t offset = seqNum - m_tailSeq;
size_t index = (m_tailIdx + offset) % m_size;

其中seqNum是要转换的序号，m_tailSeq是缓冲区中最早元素的序号，m_tailIdx是缓冲区中最旧元素的缓冲区索引，m_size 是缓冲区内存的大小。

但是，如果我持续向缓冲区中添加元素的时间足够长，序列号就会溢出。所以我必须检查一下。当我这样做时，我短暂而甜蜜的转变变成了这个怪物:

size_type getIndex(size_type seqNum) const
{
    size_type headSeq = m_tailSeq + m_numElements;

    // sequence does not wrap around
    if (m_tailSeq < headSeq)
    {
        // bounds check
        if(m_tailSeq <= seqNum && seqNum < headSeq) {
            size_type offset = seqNum - m_tailSeq;
            return (m_tailIdx + offset) % m_size;
        } else {
            throw BaseException("RingBuffer: access out of bounds", __FILE__, __LINE__);
        }
    }
    // sequence does wrap around
    else if (headSeq < m_tailSeq)
    {
        //bounds check (inverted from above)
        if(seqNum < headSeq) {
            size_type offset = (SIZE_TYPE_MAX - m_tailSeq) + seqNum;
            return (m_tailIdx + offset) % m_size;
        } else if (seqNum >= m_tailSeq) {
            size_type offset = seqNum - m_tailSeq;
            return (m_tailIdx + offset) % m_size;
        } else {
            throw BaseException("RingBuffer: access out of bounds", __FILE__, __LINE__);
        }
    }
    else if (isEmpty()) {
        throw BaseException("RingBufferIterator: accessing empty buffer", __FILE__, __LINE__);
    }
}

这相当于两次整数加法、一次整数减法、三次整数比较和一次模运算在最好的情况下对单个缓冲区访问。不用说遍历缓冲区变得非常昂贵。然而，由于我想在高性能场景中使用这个缓冲区(即软实时应用程序中的事件队列)，我希望这个数据结构尽可能高效。

当前的用例是事件缓冲区。一个(或可能多个)系统会将事件写入缓冲区，而其他系统(多个)将按照自己的节奏处理这些事件而不删除它们。当缓冲区已满时，旧事件将被简单地覆盖。通过这种方式，我始终有最近几百个事件的记录，不同的系统可以以各自的更新率检查它们并挑选出与它们相关的事件。不同的系统将保留一个指向环形缓冲区的迭代器，以便它们知道上次从哪里停止以及从哪里恢复。当系统开始处理事件时，它需要确定它的迭代器是否仍然有效或是否已被覆盖。事件很可能一次处理成大块，因此递增和取消引用应该很快。所以基本上我们是在潜在的多线程上下文中查看 MPMC 环形缓冲区。

我自己能想到的唯一解决方案是将错误检查的负担转移到缓冲区的用户身上。 IE。用户必须首先检查(通过某种方式)缓冲区中的迭代器是否有效，确保缓冲区的某个片段保持有效，然后在不进行任何进一步检查的情况下迭代该片段。然而，这似乎很容易出错，因为我必须检查程序的多个部分而不是一个地方的访问安全性，如果我决定使缓冲区线程安全，它会变得很麻烦。

我错过了什么吗？这可以做得更好吗？我是否犯了一些初学者错误？

Answer 1

正如我在评论中提到的 unsigned integer overflow is well defined operation .在C++中实现高效的序列号是关键。所以我们可以简单地减去两个无符号整数来得到距离。然后只需将距离转发到通过边界检查通过索引实现访问的函数。一如既往，它会在所有可能的索引低于序列号最大值的一半时工作。

#include <array>
#include <climits>
#include <iostream>

unsigned int const SEQUENCE_NUMBER_FIRST = UINT_MAX-10;

class RingBuffer
{
public:
    void PushBack( char c )
    {
        GetBySeqNumber(m_tailSeq++) = c;
        if( Size() == m_buffer.size()+1 )
            PopFront();
    }
    void PopFront()
    {
        ++m_headSeq;
        if( ++m_offset % m_buffer.size() == 0 )
            m_offset = 0;
    }
    char& GetByIndex( size_t n )
    {
        if( n >= Size() )
            throw std::out_of_range("Hello, world!");
        return m_buffer[ (n+m_offset) % m_buffer.size() ];
    }
    char& GetBySeqNumber( unsigned int n )
    {
        // It is well defined operation in C++,
        // but if you try to use signed integer
        // it will become undefined behavior
        return GetByIndex( n-m_headSeq );
    }
    size_t Size() const
    {
        return m_tailSeq - m_headSeq;
    }
private:
    size_t m_offset = 0;
    unsigned int m_headSeq = SEQUENCE_NUMBER_FIRST;
    unsigned int m_tailSeq = SEQUENCE_NUMBER_FIRST;
    std::array<char,26> m_buffer;
};

int main()
{
    // initialize
    RingBuffer buf;
    for( char i=0; i<26; ++i )
        buf.PushBack( 'a'+i );

    // access trough sequence numbers
    // add or subtract one to get out of range exception
    for( unsigned int i=0; i<buf.Size(); ++i )
        std::cout << buf.GetBySeqNumber( SEQUENCE_NUMBER_FIRST+i );
    std::cout << std::endl;

    // push some more to overwrite first 10 values
    for( char i=0; i<10; ++i )
        buf.PushBack( '0'+i );

    // access trough indexes
    // add or subtract one to get out of range exception
    for( size_t i=0; i<buf.Size(); ++i )
        std::cout << buf.GetByIndex(i);
    std::cout << std::endl;

    return 0;
}