Initial import from the monolithic Qt.

This is the beginning of revision history for this module. If you
want to look at revision history older than this, please refer to the
Qt Git wiki for how to use Git history grafting. At the time of
writing, this wiki is located here:

http://qt.gitorious.org/qt/pages/GitIntroductionWithQt

If you have already performed the grafting and you don't see any
history beyond this commit, try running "git log" with the "--follow"
argument.

Branched from the monolithic repo, Qt master branch, at commit
896db169ea224deb96c59ce8af800d019de63f12

1 files changed, 451 insertions, 0 deletions

diff --git a/src/corelib/tools/qringbuffer_p.h b/src/corelib/tools/qringbuffer_p.h
new file mode 100644
index 0000000000..53bbd58883
--- /dev/null
+++ b/src/corelib/tools/qringbuffer_p.h
@@ -0,0 +1,451 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** 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, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $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:
+    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