qringbuffer_p.h

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
** Contact: http://www.qt-project.org/legal
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Digia.  For licensing terms and
** conditions see http://qt.digia.com/licensing.  For further information
** use the contact form at http://qt.digia.com/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 2.1 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU Lesser General Public License version 2.1 requirements
** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
**
** In addition, as a special exception, Digia gives you certain additional
** rights.  These rights are described in the Digia Qt LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3.0 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU General Public License version 3.0 requirements will be
** met: http://www.gnu.org/copyleft/gpl.html.
**
**
** $QT_END_LICENSE$
**
****************************************************************************/

#ifndef QRINGBUFFER_P_H
#define QRINGBUFFER_P_H

//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists for the convenience
// of a number of Qt sources files.  This header file may change from
// version to version without notice, or even be removed.
//
// We mean it.
//

#include <QtCore/qbytearray.h>
#include <QtCore/qlist.h>

class QRingBuffer
{
public:
        inline QRingBuffer(int growth = 4096) : basicBlockSize(growth)
        {
                buffers << QByteArray();
                clear();
        }

        inline int nextDataBlockSize() const
        {
                return (tailBuffer == 0 ? tail : buffers.first().size()) - head;
        }

        inline const char * readPointer() const
        {
                return buffers.isEmpty() ? 0 : (buffers.first().constData() + head);
        }

        // access the bytes at a specified position
        // the out-variable length will contain the amount of bytes readable
        // from there, e.g. the amount still the same QByteArray
        inline const char * readPointerAtPosition(qint64 pos, qint64 & length) const
        {
                if(buffers.isEmpty())
                {
                        length = 0;
                        return 0;
                }

                if(pos >= bufferSize)
                {
                        length = 0;
                        return 0;
                }

                // special case: it is in the first buffer
                int nextDataBlockSizeValue = nextDataBlockSize();
                if(pos - head < nextDataBlockSizeValue)
                {
                        length = nextDataBlockSizeValue - pos;
                        return buffers.at(0).constData() + head + pos;
                }

                // special case: we only had one buffer and tried to read over it
                if(buffers.length() == 1)
                {
                        length = 0;
                        return 0;
                }

                // skip the first
                pos -= nextDataBlockSizeValue;

                // normal case: it is somewhere in the second to the-one-before-the-tailBuffer
                for(int i = 1; i < tailBuffer; i++)
                {
                        if(pos >= buffers[i].size())
                        {
                                pos -= buffers[i].size();
                                continue;
                        }

                        length = buffers[i].length() - pos;
                        return buffers[i].constData() + pos;
                }

                // it is in the tail buffer
                length = tail - pos;
                return buffers[tailBuffer].constData() + pos;
        }

        inline void free(int bytes)
        {
                bufferSize -= bytes;
                if(bufferSize < 0)
                        bufferSize = 0;

                for(;;)
                {
                        int nextBlockSize = nextDataBlockSize();
                        if(bytes < nextBlockSize)
                        {
                                head += bytes;
                                if(head == tail && tailBuffer == 0)
                                        head = tail = 0;
                                break;
                        }

                        bytes -= nextBlockSize;
                        if(buffers.count() == 1)
                        {
                                if(buffers.at(0).size() != basicBlockSize)
                                        buffers[0].resize(basicBlockSize);
                                head = tail = 0;
                                tailBuffer = 0;
                                break;
                        }

                        buffers.removeAt(0);
                        --tailBuffer;
                        head = 0;
                }

                if(isEmpty())
                        clear(); // try to minify/squeeze us
        }

        inline char * reserve(int bytes)
        {
                // if this is a fresh empty QRingBuffer
                if(bufferSize == 0)
                {
                        buffers[0].resize(qMax(basicBlockSize, bytes));
                        bufferSize += bytes;
                        tail = bytes;
                        return buffers[tailBuffer].data();
                }

                bufferSize += bytes;

                // if there is already enough space, simply return.
                if(tail + bytes <= buffers.at(tailBuffer).size())
                {
                        char * writePtr = buffers[tailBuffer].data() + tail;
                        tail += bytes;
                        return writePtr;
                }

                // if our buffer isn't half full yet, simply resize it.
                if(tail < buffers.at(tailBuffer).size() / 2)
                {
                        buffers[tailBuffer].resize(tail + bytes);
                        char * writePtr = buffers[tailBuffer].data() + tail;
                        tail += bytes;
                        return writePtr;
                }

                // shrink this buffer to its current size
                buffers[tailBuffer].resize(tail);

                // create a new QByteArray with the right size
                buffers << QByteArray();
                ++tailBuffer;
                buffers[tailBuffer].resize(qMax(basicBlockSize, bytes));
                tail = bytes;
                return buffers[tailBuffer].data();
        }

        inline void truncate(int pos)
        {
                if(pos < size())
                        chop(size() - pos);
        }

        inline void chop(int bytes)
        {
                bufferSize -= bytes;
                if(bufferSize < 0)
                        bufferSize = 0;

                for(;;)
                {
                        // special case: head and tail are in the same buffer
                        if(tailBuffer == 0)
                        {
                                tail -= bytes;
                                if(tail <= head)
                                        tail = head = 0;
                                return;
                        }

                        if(bytes <= tail)
                        {
                                tail -= bytes;
                                return;
                        }

                        bytes -= tail;
                        buffers.removeAt(tailBuffer);

                        --tailBuffer;
                        tail = buffers.at(tailBuffer).size();
                }

                if(isEmpty())
                        clear(); // try to minify/squeeze us
        }

        inline bool isEmpty() const
        {
                return tailBuffer == 0 && tail == 0;
        }

        inline int getChar()
        {
                if(isEmpty())
                        return -1;
                char c = *readPointer();
                free(1);
                return int(uchar(c));
        }

        inline void putChar(char c)
        {
                char * ptr = reserve(1);
                *ptr = c;
        }

        inline void ungetChar(char c)
        {
                --head;
                if(head < 0)
                {
                        buffers.prepend(QByteArray());
                        buffers[0].resize(basicBlockSize);
                        head = basicBlockSize - 1;
                        ++tailBuffer;
                }
                buffers[0][head] = c;
                ++bufferSize;
        }

        inline int size() const
        {
                return bufferSize;
        }

        inline void clear()
        {
                buffers.erase(buffers.begin() + 1, buffers.end());
                buffers[0].resize(0);
                buffers[0].squeeze();

                head = tail = 0;
                tailBuffer = 0;
                bufferSize = 0;
        }

        inline int indexOf(char c) const
        {
                int index = 0;
                for(int i = 0; i < buffers.size(); ++i)
                {
                        int start = 0;
                        int end = buffers.at(i).size();

                        if(i == 0)
                                start = head;
                        if(i == tailBuffer)
                                end = tail;
                        const char * ptr = buffers.at(i).data() + start;
                        for(int j = start; j < end; ++j)
                        {
                                if(*ptr++ == c)
                                        return index;
                                ++index;
                        }
                }
                return -1;
        }

        inline int indexOf(char c, int maxLength) const
        {
                int index = 0;
                int remain = qMin(size(), maxLength);
                for(int i = 0; remain && i < buffers.size(); ++i)
                {
                        int start = 0;
                        int end = buffers.at(i).size();

                        if(i == 0)
                                start = head;
                        if(i == tailBuffer)
                                end = tail;
                        if(remain < end - start)
                        {
                                end = start + remain;
                                remain = 0;
                        }
                        else
                        {
                                remain -= end - start;
                        }
                        const char * ptr = buffers.at(i).data() + start;
                        for(int j = start; j < end; ++j)
                        {
                                if(*ptr++ == c)
                                        return index;
                                ++index;
                        }
                }
                return -1;
        }

        inline int read(char * data, int maxLength)
        {
                int bytesToRead = qMin(size(), maxLength);
                int readSoFar = 0;
                while(readSoFar < bytesToRead)
                {
                        const char * ptr = readPointer();
                        int bytesToReadFromThisBlock = qMin(bytesToRead - readSoFar, nextDataBlockSize());
                        if(data)
                                memcpy(data + readSoFar, ptr, bytesToReadFromThisBlock);
                        readSoFar += bytesToReadFromThisBlock;
                        free(bytesToReadFromThisBlock);
                }
                return readSoFar;
        }

        inline QByteArray read(int maxLength)
        {
                QByteArray tmp;
                tmp.resize(qMin(maxLength, size()));
                read(tmp.data(), tmp.size());
                return tmp;
        }

        inline QByteArray readAll()
        {
                return read(size());
        }

        // read an unspecified amount (will read the first buffer)
        inline QByteArray read()
        {
                if(bufferSize == 0)
                        return QByteArray();

                // multiple buffers, just take the first one
                if(head == 0 && tailBuffer != 0)
                {
                        QByteArray qba = buffers.takeFirst();
                        --tailBuffer;
                        bufferSize -= qba.length();
                        return qba;
                }

                // one buffer with good value for head. Just take it.
                if(head == 0 && tailBuffer == 0)
                {
                        QByteArray qba = buffers.takeFirst();
                        qba.resize(tail);
                        buffers << QByteArray();
                        bufferSize = 0;
                        tail = 0;
                        return qba;
                }

                // Bad case: We have to memcpy.
                // We can avoid by initializing the QRingBuffer with basicBlockSize of 0
                // and only using this read() function.
                QByteArray qba(readPointer(), nextDataBlockSize());
                buffers.removeFirst();
                head = 0;
                if(tailBuffer == 0)
                {
                        buffers << QByteArray();
                        tail = 0;
                }
                else
                {
                        --tailBuffer;
                }
                bufferSize -= qba.length();
                return qba;
        }

        // append a new buffer to the end
        inline void append(const QByteArray & qba)
        {
                buffers[tailBuffer].resize(tail);
                buffers << qba;
                ++tailBuffer;
                tail = qba.length();
                bufferSize += qba.length();
        }

        inline QByteArray peek(int maxLength) const
        {
                int bytesToRead = qMin(size(), maxLength);
                if(maxLength <= 0)
                        return QByteArray();
                QByteArray ret;
                ret.resize(bytesToRead);
                int readSoFar = 0;
                for(int i = 0; readSoFar < bytesToRead && i < buffers.size(); ++i)
                {
                        int start = 0;
                        int end = buffers.at(i).size();
                        if(i == 0)
                                start = head;
                        if(i == tailBuffer)
                                end = tail;
                        const int len = qMin(ret.size() - readSoFar, end - start);
                        memcpy(ret.data() + readSoFar, buffers.at(i).constData() + start, len);
                        readSoFar += len;
                }
                Q_ASSERT(readSoFar == ret.size());
                return ret;
        }

        inline int skip(int length)
        {
                return read(0, length);
        }

        inline int readLine(char * data, int maxLength)
        {
                int index = indexOf('\n');
                if(index == -1)
                        return read(data, maxLength);
                if(maxLength <= 0)
                        return -1;

                int readSoFar = 0;
                while(readSoFar < index + 1 && readSoFar < maxLength - 1)
                {
                        int bytesToRead = qMin((index + 1) - readSoFar, nextDataBlockSize());
                        bytesToRead = qMin(bytesToRead, (maxLength - 1) - readSoFar);
                        memcpy(data + readSoFar, readPointer(), bytesToRead);
                        readSoFar += bytesToRead;
                        free(bytesToRead);
                }

                // Terminate it.
                data[readSoFar] = '\0';
                return readSoFar;
        }

        inline bool canReadLine() const
        {
                return indexOf('\n') != -1;
        }

private:
        QList<QByteArray> buffers;
        int head, tail;
        int tailBuffer; // always buffers.size() - 1
        int basicBlockSize;
        int bufferSize;
};

#endif // QRINGBUFFER_P_H