回环缓冲区,环形缓冲区(CPP)

#include <tchar.h>
#include <stdio.h>
#include <iostream>
#include <memory>
#include <Windows.h>

template < typename T >
class CCricuitQueue
{
public:
    CCricuitQueue() : m_pData( nullptr ), m_nLength( 0 ), m_nSize( 0 ), m_nHead( 0 ), m_nTail( 0 )
    {
        InitializeCriticalSection(&m_cs);
    }
    virtual ~CCricuitQueue()
    {
        if( m_pData ) delete [] m_pData;
        DeleteCriticalSection( &m_cs );
    }
    
    //描述:创建缓冲区
    //参数:
    //      nSize : 欲创建的缓冲区大小
    //返回值:是否创建成功
    bool Create( size_t nSize )
    {
        EnterCriticalSection( &m_cs );
        T * pData = new(std::nothrow) T[nSize];
        if( !pData )
        {
            LeaveCriticalSection( &m_cs );
            return false;
        }

        if( m_pData ) delete [] m_pData;
        m_pData         = pData;
        m_nSize         = nSize;
        LeaveCriticalSection( &m_cs );
        return true;
    }
    
    //描述:清空缓冲区
    inline void Clear()
    {
        EnterCriticalSection( &m_cs );
        
        m_nLength       = 0;
        m_nHead         = 0;
        m_nTail         = 0;

        LeaveCriticalSection( &m_cs );
    }
    
    //描述:获取缓冲区的空闲空间尺寸
    //返回值:缓冲区的空闲空间尺寸
    inline size_t GetSpace()
    {
        EnterCriticalSection( &m_cs );
        
        size_t nRet = m_nSize - m_nLength;

        LeaveCriticalSection( &m_cs );

        return nRet;
    }
    
    //描述:获取缓冲区的真实数据尺寸
    //返回值:缓冲区的真实数据尺寸
    inline size_t GetLength()
    {
        EnterCriticalSection( &m_cs );
        
        size_t nRet = m_nLength;

        LeaveCriticalSection( &m_cs );

        return nRet;
    }
    
    //描述:获取缓冲区的尺寸
    //返回值:缓冲区的尺寸
    inline size_t GetCapacity()
    {
        EnterCriticalSection( &m_cs );
        
        size_t nRet = m_nSize;

        LeaveCriticalSection( &m_cs );

        return nRet;
    }
    
    //描述:获取可读缓冲区的指针
    //返回值:可读缓冲区的指针
    inline T * GetReadPtr()
    {
        EnterCriticalSection( &m_cs );
        
        T * pRet = m_pData + m_nHead;

        LeaveCriticalSection( &m_cs );

        return pRet;
    }
    
    //描述:获取可写缓冲区的指针
    //返回值:可写缓冲区的指针
    inline T * GetWritePtr()
    {
        EnterCriticalSection( &m_cs );
        
        T * pRet = m_pData + m_nTail;

        LeaveCriticalSection( &m_cs );

        return pRet;
    }
    
    //描述:获取缓冲区中可读取的数据量大小
    //返回值:可读数据量
    inline size_t GetReadableLength()
    {
        EnterCriticalSection( &m_cs );
        size_t nRet;

        if( m_nHead == m_nTail )        nRet = GetLength() > 0 ? m_nSize - m_nHead : 0;
        else if( m_nHead < m_nTail )    nRet = m_nTail - m_nHead;
        else                            nRet = m_nSize - m_nHead;

        LeaveCriticalSection( &m_cs );

        return nRet;
    }
    
    //描述:获取缓冲区中可写入的数据量大小
    //返回值:可写数据量
    inline size_t GetWritableLength()
    {
        EnterCriticalSection( &m_cs );
        size_t nRet;

        if( m_nHead == m_nTail )        nRet = GetLength() > 0 ? 0 : m_nSize - m_nTail;
        else if( m_nHead < m_nTail )    nRet = m_nSize - m_nTail;
        else                            nRet = m_nHead - m_nTail;

        LeaveCriticalSection( &m_cs );

        return nRet;
    }
    
    //描述:从读取位置擦除一定数量的元素
    //参数:
    //      nSize   : 写入的擦除大小
    //返回值:操作是否成功
    inline bool Erase( size_t nSize )
    {
        if( nSize > GetLength() ) return false;

        EnterCriticalSection( &m_cs );

        m_nHead     += nSize;
        if( m_nSize != 0 ) m_nHead %= m_nSize;
        m_nLength   -= nSize;

        LeaveCriticalSection( &m_cs );

        return true;
    }
    
    //描述:将数据写入缓冲区中
    //参数:
    //      pTar    : 源输入缓冲区
    //      nSize   : 写入的数据大小
    //返回值:操作是否成功
    inline bool Enqueue( const T * pSrc, size_t nSize )
    {
        EnterCriticalSection( &m_cs );
        
        if( GetSpace() < nSize )
        {
            LeaveCriticalSection( &m_cs );
            return false;
        }

        if( pSrc )
        {
            if( m_nHead <= m_nTail )
            {
                //计算尾部空闲空间量
                size_t nBackSpaceCount = m_nSize - m_nTail;

                if( nBackSpaceCount >= nSize )
                {
                    //尾部空闲空间充足直接拷贝数据
                    memcpy( m_pData + m_nTail, pSrc, sizeof(T) * nSize );
                }
                else
                {
                    //尾部空闲空间不足分段拷贝数据
                    memcpy( m_pData + m_nTail, pSrc, sizeof(T) * nBackSpaceCount );
                    memcpy( m_pData, pSrc + nBackSpaceCount, sizeof(T) * ( nSize - nBackSpaceCount ) );
                }
            }
            else
            {
                memcpy( m_pData + m_nTail, pSrc, sizeof(T) * nSize );
            }
        }

        m_nTail     += nSize;
        m_nTail     %= m_nSize;
        m_nLength   += nSize;

        LeaveCriticalSection( &m_cs );

        return true;
    }
    
    //描述:取出数据并从缓冲区中删除数据
    //参数:
    //      pTar    : 目标输出缓冲区
    //      nSize   : 取出的数据大小
    //返回值:操作是否成功
    inline bool Dequeue( T * pTar, size_t nSize )
    {
        EnterCriticalSection( &m_cs );

        if( !Peek( pTar, nSize ) )
        {
            LeaveCriticalSection( &m_cs );
            return false;
        }

        m_nHead     += nSize;
        if( m_nSize != 0 ) m_nHead %= m_nSize;
        m_nLength   -= nSize;
        LeaveCriticalSection( &m_cs );

        return true;
    }
    
    //描述:取出数据但不从缓冲区中删除数据
    //参数:
    //      pTar    : 目标输出缓冲区
    //      nSize   : 取出的数据大小
    //      nOffset : 偏移
    //返回值:操作是否成功
    inline bool Peek( T * pTar, size_t nSize, size_t nOffset = 0 )
    {
        EnterCriticalSection( &m_cs );

        //如果真实数据长度不够,则返回失败
        if( m_nLength < nSize + nOffset )
        {
            LeaveCriticalSection( &m_cs );
            return false;
        }

        if( pTar )
        {
            //如果头在尾前面,则真实数据是非分段的,直接拷贝
            if( m_nHead < m_nTail )
            {
                memcpy( pTar, m_pData + m_nHead + nOffset, sizeof(T) * nSize );
            }
            //否则真实数据是分段的
            else
            {
                //如果尾部有足够的数据量够读取,则直接读取
                size_t stBackDataCount = GetBackDataCount();
                if( stBackDataCount >= nSize + nOffset )
                {
                    memcpy( pTar, m_pData + m_nHead + nOffset, sizeof(T) * nSize );
                }
                else
                {
                    //如果尾部数据量大于偏移量,则需要从尾部读取一部分数据
                    if( stBackDataCount > nOffset )
                    {
                        size_t stBackDataNeedCopy = stBackDataCount - nOffset;
                        //从尾部读取一部分数据
                        memcpy( pTar, m_pData + m_nHead + nOffset, sizeof(T) * stBackDataNeedCopy );
                        //从头部读取一部分数据
                        memcpy( pTar + stBackDataNeedCopy, m_pData, sizeof(T) * ( nSize - stBackDataNeedCopy ) );
                    }
                    else
                    {
                        //否则可以直接从前端读取数据
                        memcpy( pTar, m_pData + ( nOffset - stBackDataCount ), sizeof(T) * nSize );
                    }
                }
            }
        }

        LeaveCriticalSection( &m_cs );

        return true;
    }
    
    //描述:整理真实数据为平坦模式
    //返回值:操作是否成功
    inline bool Flat()
    {
        if( GetLength() == 0 ) return false;

        EnterCriticalSection( &m_cs );
        if( m_nHead == 0 )
        {
            LeaveCriticalSection( &m_cs );
            return true;
        }
        else if( m_nHead < m_nTail )
        {
            memmove( m_pData, m_pData + m_nHead, m_nLength * sizeof(T) );
        }
        else
        {
            size_t stFrontDataCount = m_nTail;
            size_t stBackDataCount = m_nSize - m_nHead;
            T * pT( new(std::nothrow) T[stFrontDataCount] );
            if( pT == nullptr ) return false;
            memcpy( pT,  m_pData, sizeof(T) * stFrontDataCount );
            memmove( m_pData, m_pData + m_nHead, sizeof(T) * ( stBackDataCount ) );
            memcpy( m_pData + stBackDataCount, pT, stFrontDataCount );
            delete [] pT;
        }

        m_nHead = 0;
        m_nTail = m_nLength;

        LeaveCriticalSection( &m_cs );

        return true;
    }
protected:
    //描述:获取尾部空闲缓冲区的大小
    //返回值:尾部空闲缓冲区的大小
    inline size_t GetBackDataCount()
    {
        EnterCriticalSection( &m_cs );
        
        size_t nRet = m_nSize - m_nHead;

        LeaveCriticalSection( &m_cs );

        return nRet;
    }
protected:
    CRITICAL_SECTION    m_cs;               //多线程时保护数据使用的临界段
    T                   * m_pData;          //原始缓冲区指针
    size_t              m_nLength;          //真实数据的长度
    size_t              m_nSize;            //缓冲区大小
    size_t              m_nHead;            //头指针
    size_t              m_nTail;            //尾指针
};

template < typename T >
class CCricuitQueueEx :
    public CCricuitQueue<T>
{
public:
    CCricuitQueueEx() : m_nExtraSize( 0 ) {}

    //描述:创建回环缓冲区,并创建一块指定大小的扩展缓冲区
    //参数:
    //      nSize           : 回环缓冲区大小
    //      nExtraSize      : 扩展缓冲区大小
    void Create( size_t nSize, size_t nExtraSize = 0 )
    {
        EnterCriticalSection( &m_cs );
        if( m_pData ) delete [] m_pData;

        m_pData         = new T[nSize + nExtraSize];
        m_nSize         = nSize;
        m_nExtraSize    = nExtraSize;
        LeaveCriticalSection( &m_cs );
    }

    //描述:获得读取指针.如果有必要,会将尽可能多的数据移至扩展内存中以便能够读取更多数据
    //返回值:可读缓冲区的指针
    inline T * GetReadPtr()
    {
        EnterCriticalSection( &m_cs );
        
        T * pRet = m_pData + m_nHead;

        size_t nSplitFirstDataCount;
        if( m_nHead > m_nTail && (nSplitFirstDataCount = m_nSize - m_nHead) < m_nExtraSize )
        {
            memcpy( m_pData + m_nSize, m_pData, sizeof(T) * ( m_nExtraSize - nSplitFirstDataCount ) );
        }

        LeaveCriticalSection( &m_cs );

        return pRet;
    }

    //描述:将头部指定长度数据拷贝到扩展块中
    //参数:
    //      nSize : 要拷贝的数据长度
    inline void CopyHeadDataToExtraBuffer( size_t nSize )
    {
        EnterCriticalSection( &m_cs );

        if( nSize > m_nExtraSize ) nSize = m_nExtraSize;

        memcpy( m_pData + m_nSize, m_pData, nSize );

        LeaveCriticalSection( &m_cs );
    }
protected:
    size_t              m_nExtraSize;       //扩展块大小(扩展块用于读取的时候能多读数据)
};

template < typename T >
class CCricuitBuffer :
    public CCricuitQueue<T>
{
public:
    CCricuitBuffer( size_t nMaxSize = 0, size_t nStepSize = 0x100 )
        : m_nMaxSize( nMaxSize ), m_nStepSize( nStepSize ) {}
    //描述:调整缓冲区尺寸
    //参数:
    //      nSize : 欲设置的缓冲区目标尺寸, 0为调整为最合适尺寸(当前真实数据尺寸)
    //      bForce : 欲设置的缓冲区目标尺寸比原始缓冲区尺寸要小的情况下,是否继续调整,
    //返回值:操作是否成功
    inline bool Resize( size_t nSize = 0, bool bForceCapacity = false, bool bForceMaxSize = false )
    {
        //如果已限制最大尺寸且新尺寸超过最大尺寸由
        size_t nMaxSize = GetMaxSize();
        if( nMaxSize < nSize && nMaxSize != 0 && !bForceMaxSize ) return false;
        //如果欲调整的缓冲区尺寸小于原缓冲区尺寸,且非强制调整,则直接返回
        size_t nCapacity = GetCapacity();
        if( nSize < nCapacity && nSize != 0 && !bForceCapacity ) return false;
        
        //如果新尺寸小于真实数据尺寸,则调整失败
        size_t nLength = GetLength();
        if( nSize == 0 ) nSize = nLength;           //如果设置为0,则为调整至真实数据尺寸
        else if( nLength > nSize ) return false;

        //申请空间并拷贝数据到空间
        T * pData = new(std::nothrow) T[nSize];
        if( !pData ) return false;
        if( !Dequeue( pData, nLength ) )
        {
            delete [] pData;
            return false;
        }

        //设置新的成员值
        EnterCriticalSection( &m_cs );
        if( m_pData ) delete [] m_pData;
        m_pData         = pData;
        m_nSize         = nSize;
        m_nHead         = 0;
        m_nTail         = nLength;
        m_nLength       = nLength;
        LeaveCriticalSection( &m_cs );
        return true;
    }
    
    //描述:将数据写入缓冲区中,如果缓冲区大小不够,则调整大小
    //参数:
    //      pTar    : 源输入缓冲区
    //      nSize   : 写入的数据大小
    //返回值:操作是否成功
    inline bool Enqueue( const T * pSrc, size_t nSize )
    {
        size_t nSpace = GetSpace();
        if( nSize > nSpace )
        {
            size_t nLength = GetLength();
            size_t nDataSize = nLength + nSize;
            size_t nSizeRequest = ( m_nStepSize == 0 )
                ? nDataSize
                : ( nDataSize + m_nStepSize - 1 ) / m_nStepSize * m_nStepSize;
            if( !Resize( nSizeRequest ) )
            {
                size_t nMaxSize = GetMaxSize();
                if( nDataSize < nMaxSize && nSizeRequest > nMaxSize ) nSizeRequest = nMaxSize;
                if( !Resize( nSizeRequest ) ) return false;
            }
        }
        return CCricuitQueue<T>::Enqueue( pSrc, nSize );
    }
    
    //描述:设置缓冲区的最大尺寸
    //返回值:是否设置成功(非强制情况下总是成功)
    bool SetMaxSize( size_t nMaxSize = 0, bool bForce = false )
    {
        EnterCriticalSection( &m_cs );
        size_t nSize = m_nSize;
        LeaveCriticalSection( &m_cs );

        //如果新的最大尺寸小于当前尺寸且需要强制
        if( nMaxSize < nSize && bForce)
        {
            //如果重新分配大小失败则返回FALSE
            //Resize 内部会和真实的数据大小进行比较
            if( !Resize( nMaxSize, bForce ) )
                return false;
        }
        
        EnterCriticalSection( &m_cs );
        m_nMaxSize = nMaxSize;
        LeaveCriticalSection( &m_cs );

        return true;
    }

    //描述:获取缓冲区的最大尺寸
    //返回值:缓冲区的最大尺寸
    inline size_t GetMaxSize()
    {
        EnterCriticalSection( &m_cs );
        size_t nRet = m_nMaxSize;
        LeaveCriticalSection( &m_cs );
        return nRet;
    }

    //描述:设置和获得原始缓冲区的步进尺寸
    size_t SetStepSize(size_t nStepSize = 0)
    {
        EnterCriticalSection( &m_cs );
        size_t nRet = m_nStepSize;
        m_nStepSize = nStepSize;
        LeaveCriticalSection( &m_cs );
        return nRet;
    }

    inline bool Write( const T * pSrc, size_t nSize ) { return Enqueue( pSrc, nSize ); }
    inline bool Read( T * pTar, size_t nSize ) { return Dequeue( pTar, nSize ); }
private:
    size_t              m_nMaxSize;         //缓冲区的最大尺寸, 0 为无限大
    size_t              m_nStepSize;        //缓冲区在自动调整大小时的步进长度
};




//测试代码
int _tmain()
{
    setlocale(LC_ALL, "");

    CCricuitQueueEx<char> CriQue;
    CriQue.Create(0x100);

    {   // m_nHead < m_nTail
        char szBuf[0x100];
        strcpy_s(szBuf, sizeof(szBuf), "TestData");
        CriQue.Enqueue(szBuf, 0x20);

        memset(szBuf, 0, sizeof(szBuf));
        if( CriQue.Peek(szBuf, 0x04) )
            printf("%s\r\n", szBuf);
    
        memset(szBuf, 0, sizeof(szBuf));
        if( CriQue.Dequeue(szBuf, 0x04) )
            printf("%s\r\n", szBuf);

        memset(szBuf, 0, sizeof(szBuf));
        if( CriQue.Peek(szBuf, 0x20) )                  //Failed
            printf("%s\r\n", szBuf);

        memset(szBuf, 0, sizeof(szBuf));
        if( CriQue.Dequeue(szBuf, 0x20) )               //Failed
            printf("%s\r\n", szBuf);
        memset(szBuf, 0, sizeof(szBuf));
        if( CriQue.Dequeue(szBuf, 0x20 - 0x04 ) )
            printf("%s\r\n", szBuf);
    }

    {
        CCricuitQueue<char> cq;
        cq.Create( 0x400 );
        char szBuf[0x100];
        strcpy_s(szBuf, sizeof(szBuf), "TestData");
        cq.Enqueue( szBuf, strlen(szBuf) + 1 );
        cq.Erase( 2 );
        cq.Erase( 20 );      //Failed
        bool b = cq.Dequeue(szBuf, cq.GetLength() );
        if( b ) printf("%s\r\n", szBuf);
    }

    {
        // m_nHead > m_nTail
        char szBuf[0x100];
        strcpy_s(szBuf, sizeof(szBuf), "TestData");
        CriQue.Enqueue(szBuf, sizeof(szBuf));

        printf("%s\r\n", CriQue.GetReadPtr());
        
        memset(szBuf, 0, sizeof(szBuf));
        if( CriQue.Dequeue(szBuf, sizeof(szBuf) ) )
            printf("%s\r\n", szBuf);
    }

    {
        CCricuitBuffer<char> CriBuf;
        printf("Size : %d\r\n", CriBuf.GetCapacity());
        char szBuf[MAX_PATH];
        strcpy_s(szBuf, sizeof(szBuf), "TestData");
        bool b = CriBuf.Write( szBuf, 100 );
        printf("Length : %5d |Free : %5d | Size : %5d |\r\n", CriBuf.GetLength(), CriBuf.GetSpace(), CriBuf.GetCapacity());
        b = CriBuf.Write( szBuf, 100 );
        printf("Length : %5d |Free : %5d | Size : %5d |\r\n", CriBuf.GetLength(), CriBuf.GetSpace(), CriBuf.GetCapacity());
        b = CriBuf.Write( szBuf, MAX_PATH );
        printf("Length : %5d |Free : %5d | Size : %5d |\r\n", CriBuf.GetLength(), CriBuf.GetSpace(), CriBuf.GetCapacity());
        CriBuf.Clear();
    }

    {
        CCricuitBuffer<char> CriBuf;
        printf("Size : %d\r\n", CriBuf.GetCapacity());
        CriBuf.Resize( 20 );
        printf("Size : %d\r\n", CriBuf.GetCapacity());
        char szBuf[20];
        CriBuf.Write(szBuf, 10);
        CriBuf.Read(szBuf, 10);

        strcpy_s(szBuf, sizeof(szBuf), "1234567890qwertyuio");
        CriBuf.Write(szBuf, sizeof(szBuf));
        bool b = CriBuf.Resize( 15, true );
        printf("resize : %d | size : %d\r\n",b, CriBuf.GetCapacity());
        memset(szBuf, 0 ,sizeof(szBuf));
        CriBuf.Read(szBuf, sizeof(szBuf));
        printf("%s\r\n",szBuf);
        b = CriBuf.Resize( 15, true );
        printf("resize : %d | size : %d\r\n",b, CriBuf.GetCapacity());
    }

    {
        CCricuitBuffer<char> CriBuf;
        CriBuf.SetMaxSize( 0x401 );
        //CriBuf.SetStepSize(0);

        char szBuf[500];
        bool b = CriBuf.Write(szBuf, sizeof(szBuf));
        printf("Write : %d | Length : %5d |Free : %5d | Size : %5d |\r\n",
            b, CriBuf.GetLength(), CriBuf.GetSpace(), CriBuf.GetCapacity());
        b = CriBuf.Write(szBuf, sizeof(szBuf));
        printf("Write : %d | Length : %5d |Free : %5d | Size : %5d |\r\n",
            b, CriBuf.GetLength(), CriBuf.GetSpace(), CriBuf.GetCapacity());
        b = CriBuf.Write(szBuf, sizeof(szBuf));
        printf("Write : %d | Length : %5d |Free : %5d | Size : %5d |\r\n",
            b, CriBuf.GetLength(), CriBuf.GetSpace(), CriBuf.GetCapacity());
        b = CriBuf.Write(szBuf, 1);
        printf("Write : %d | Length : %5d |Free : %5d | Size : %5d |\r\n",
            b, CriBuf.GetLength(), CriBuf.GetSpace(), CriBuf.GetCapacity());
        
    }

    //读取数据带偏移测试 和 整理内存
    {
        CCricuitQueue<char> CirQue;
        CirQue.Create( 10 );
        //让前指针移到后面
        char chBuf[10];
        for(__int8 i = 0; i < 8; ++i) chBuf[i] = i;

        CirQue.Enqueue(chBuf, 6);
        CirQue.Dequeue(chBuf, 2);
        //整理非跨段数据
        CirQue.Flat();
        CirQue.Dequeue(chBuf, 4);

        for(__int8 i = 0; i < 8; ++i) chBuf[i] = i;
        CirQue.Enqueue( chBuf, 8 );
        //取出无偏移跨段数据  [2,4]
        CirQue.Peek( chBuf, 6 );
        //取出有偏移非跨段数据  [0, 2(2)]
        CirQue.Peek( chBuf, 2, 2 );
        //取出有偏移跨段数据 [ 2, 2(2) ]
        CirQue.Peek( chBuf, 4, 2 );
        //取出有偏移过长数据失败 [ 6, 2(2) ]
        bool bResult = CirQue.Peek( chBuf, 8, 2 );

        //整理跨段数据
        CirQue.Flat();
    }

    getchar();
    return 0;
}