RingBuffer 数据结构

68 阅读 0 评论 45 点赞

我是靠谱客的博主无情皮带，最近开发中收集的这篇文章主要介绍RingBuffer 数据结构，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最近在做多媒体编解码工作, 正好用到RingBuffer 数据结构, 写个blog, 共享之:

typedef unsigned long size_type;

class RingBuffer {
public:
    RingBuffer(unsigned long maxSize);

    ~RingBuffer();
    ECode Constructor();

    bool IsFull() const {
        return (m_Count == m_MaxSize);
    }

    bool IsEmpty() const {
        return (m_Count == 0);
    }

    size_type Size() const {
        return m_Count;
    }


    size_type GetPopPos() const {
        return m_PopPos;
    }

    ECode SetPopPos(unsigned long pos);

    size_type GetLastPushedSum () const {
        return (m_LastPushedSize[0] + m_LastPushedSize[1] + m_LastPushedSize[2]);
    }

    size_type Capacity() const { return m_MaxSize;}

    RingBuffer & operator=(RingBuffer &other);

    ECode Push(Byte *data, size_type length);

    ECode Pop(Byte *buf, size_type length);

    ECode CopyPopedData(unsigned long pos, unsigned long length, Byte *pOutData);

private:
    Byte               *m_pRingBuffer;      // buffer
    size_type           m_PushPos;          // 新的push位置
                                            // (popPos+count)% N

    size_type           m_PopPos;           // 新的pop位置
    size_type           m_Count;            // 有效字节数

    size_type           m_MaxSize;

    size_type           m_PushCount;
    size_type           m_LastPushedSize[3];
    IMutex             *m_pMutex;
};

关于类的实现:

RingBuffer::RingBuffer(unsigned long maxSize) :
        m_MaxSize(maxSize), m_PushPos(0), m_PopPos(0), m_Count(0), m_PushCount(0)
{
    m_LastPushedSize[0] = 0;
    m_LastPushedSize[1] = 0;
    m_LastPushedSize[2] = 0;
}

ECode RingBuffer::Constructor()
{
    if(0 == m_MaxSize) return E_INVALID_ARGUMENT;

    m_pRingBuffer = new Byte[m_MaxSize];;
    if(!m_pRingBuffer) return E_OUT_OF_MEMORY;

    memset(m_pRingBuffer, 0, m_MaxSize);

    ECode ec = CMutex::New(&m_pMutex);
    return ec;
}

RingBuffer & RingBuffer::operator=(RingBuffer &other)
{
    if (this != &other) {
        WaitResult wr;
        ECode ec = m_pMutex->Lock(&wr);
        if (FAILED(ec) || WaitResult_OK != wr) {
            return *this; // do nothing, just return.
        }

        if(other.m_Count > m_MaxSize) {
            m_pMutex->Unlock();
            return *this; // do nothing, just return.
        }

        //assure that it has enough space to copy.
        size_type rearLen = other.m_MaxSize - other.m_PopPos;
        if (rearLen >= other.m_Count) {
           memcpy(m_pRingBuffer,
                     &other.m_pRingBuffer[other.m_PopPos],
                     other.m_Count);
        } else {
           memcpy(m_pRingBuffer,
                     &other.m_pRingBuffer[other.m_PopPos],
                     rearLen);
           memcpy(m_pRingBuffer + rearLen,
                     other.m_pRingBuffer, other.m_Count - rearLen);
        }

        m_PopPos = 0;
        m_PushPos = m_Count = other.m_Count;

        m_pMutex->Unlock();
    }
    return (*this);
}

RingBuffer::~RingBuffer()
{
    m_PushPos = 0, m_PopPos = 0, m_Count = 0;
    m_pMutex->Release();
    delete [] m_pRingBuffer;
}

ECode RingBuffer::SetPopPos(unsigned long pos)
{
    WaitResult wr;
    ECode ec = m_pMutex->Lock(&wr);
    if (FAILED(ec) || WaitResult_OK != wr) {
        return ec;
    }

    m_PopPos = pos;

    m_pMutex->Unlock();
    return NOERROR;
}

ECode RingBuffer::Push(
        /* [in] */ Byte *data,
        /* [in] */ size_type length)
{
    WaitResult wr;
    ECode ec = m_pMutex->Lock(&wr);
    if (FAILED(ec) || WaitResult_OK != wr) {
        return ec;
    }

    if (data == NULL || length == 0 ||
            length > (m_MaxSize - m_Count)) {
        m_pMutex->Unlock();
        return E_INVALID_ARGUMENT;
    }

    // as length < m_MaxSize - m_Count, assure that it has enough space to push.
    size_type rearLen = m_MaxSize - m_PushPos;   // 尾部剩余空间

    if (length < rearLen) {
        memcpy(&m_pRingBuffer[m_PushPos], data, length);
        m_PushPos += length; //调整新的push位置
    }
    else if (length > rearLen) {
        memcpy(&m_pRingBuffer[m_PushPos], data, rearLen);
        memcpy(m_pRingBuffer, data + rearLen, length - rearLen);
        m_PushPos = length - rearLen;   // 调整新的push位置
    }
    else {
        memcpy(&m_pRingBuffer[m_PushPos], data, length);
        m_PushPos = 0; //调整新的push位置
    }

    m_PushCount %= 3;
    m_LastPushedSize[m_PushCount] = length;

    m_PushCount++;
    m_Count += length;
    m_pMutex->Unlock();
    return NOERROR;
}

ECode RingBuffer::Pop(
        /* [out]*/ Byte *buf,
        /* [in] */ size_type length)
{
    WaitResult wr;
    ECode ec = m_pMutex->Lock(&wr);
    if (FAILED(ec) || WaitResult_OK != wr) {
        return ec;
    }

    if (buf == NULL || length == 0 || length > m_Count) {
        m_pMutex->Unlock();
        return E_INVALID_ARGUMENT;
    }

    // as length < m_Count, assure that it has enough data to pop.
    size_type rearLen = m_MaxSize - m_PopPos;    // 尾部剩余数据
    if (length < rearLen) {
        memcpy(buf, &m_pRingBuffer[m_PopPos], length);
        m_PopPos += length;             // 调整新的pop位置
    }
    else if (length > rearLen) {
        memcpy(buf, &m_pRingBuffer[m_PopPos], rearLen);
        memcpy(buf + rearLen, m_pRingBuffer, length - rearLen);
        m_PopPos = length - rearLen;    // 调整新的pop位置
    }
    else {
        memcpy(buf, &m_pRingBuffer[m_PopPos], length);
        m_PopPos = 0;                   // 调整新的pop位置
    }

    m_Count -= length;
    m_pMutex->Unlock();
    return NOERROR;
}

ECode RingBuffer::CopyPopedData(
        /* [in] */ unsigned long pos,
        /* [in] */ unsigned long length,
        /* [out] */ Byte *pOutData)
{
    WaitResult wr;
    ECode ec = m_pMutex->Lock(&wr);
    if (FAILED(ec) || WaitResult_OK != wr) {
        return ec;
    }

    if(pos > m_MaxSize || pOutData == NULL) {
        m_pMutex->Unlock();
        return E_INVALID_ARGUMENT;
    }

    //assure that it has enough poped data to copy.
    size_type rearLen = m_MaxSize - pos;
    if (rearLen >= length) {
        memcpy(pOutData, m_pRingBuffer + pos, length);
    }
    else {
        memcpy(pOutData,
                 m_pRingBuffer + pos,
                 rearLen);

        memcpy(pOutData + rearLen,
                 m_pRingBuffer, length - rearLen);
    }

    m_pMutex->Unlock();
    return NOERROR;
}