qringbuffer_p.h

/****************************************************************************
**
** Copyright (C) 2013 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>

QT_BEGIN_NAMESPACE

class QRingBuffer
{
public:
    explicit 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;
};

QT_END_NAMESPACE

#endif // QRINGBUFFER_P_H