From df4f334ad0473f4f6cc9a9388bed8f3c9a19f8b8 Mon Sep 17 00:00:00 2001 From: Alex Trotsenko Date: Sat, 21 Jun 2014 14:30:30 +0300 Subject: Rewrite QRingBuffer QRingBuffer is a fully inlined class used in many I/O classes. So, it must be as fast and small as possible. To this end, a lot of unnecessary special cases were replaced by generic structures. Change-Id: Ic189ced3b200924da158ce511d69d324337d01b6 Reviewed-by: Oswald Buddenhagen --- src/corelib/tools/qringbuffer_p.h | 279 ++++++++++++-------------------------- 1 file changed, 88 insertions(+), 191 deletions(-) (limited to 'src/corelib/tools/qringbuffer_p.h') diff --git a/src/corelib/tools/qringbuffer_p.h b/src/corelib/tools/qringbuffer_p.h index afd15c85ea..5aa1f165be 100644 --- a/src/corelib/tools/qringbuffer_p.h +++ b/src/corelib/tools/qringbuffer_p.h @@ -61,9 +61,9 @@ QT_BEGIN_NAMESPACE class QRingBuffer { public: - explicit inline QRingBuffer(int growth = 4096) : basicBlockSize(growth) { - buffers << QByteArray(); - clear(); + explicit inline QRingBuffer(int growth = 4096) : + head(0), tail(0), tailBuffer(0), basicBlockSize(growth), bufferSize(0) { + buffers.append(QByteArray()); } inline int nextDataBlockSize() const { @@ -78,115 +78,65 @@ public: // 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 < 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; + if (pos >= 0) { + pos += head; + for (int i = 0; i < buffers.size(); ++i) { + length = (i == tailBuffer ? tail : buffers[i].size()); + if (length > pos) { + length -= pos; + return buffers[i].constData() + pos; + } + pos -= length; } - - length = buffers[i].length() - pos; - return buffers[i].constData() + pos; } - // it is in the tail buffer - length = tail - pos; - return buffers[tailBuffer].constData() + pos; + length = 0; + return 0; } 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; + while (bytes > 0) { + int blockSize = buffers.first().size() - head; + + if (tailBuffer == 0 || blockSize > bytes) { + bufferSize -= bytes; + if (bufferSize <= 0) + clear(); // try to minify/squeeze us + else + head += bytes; + return; } - buffers.removeAt(0); + bufferSize -= blockSize; + bytes -= blockSize; + buffers.removeFirst(); --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 (bytes <= 0) + return 0; - // 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 need buffer reallocation + if (tail + bytes > buffers.last().size()) { + if (tail >= basicBlockSize) { + // shrink this buffer to its current size + buffers.last().resize(tail); - // 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; + // create a new QByteArray + buffers.append(QByteArray()); + ++tailBuffer; + tail = 0; + } + buffers.last().resize(qMax(basicBlockSize, tail + bytes)); } - // 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(); + char *writePtr = buffers.last().data() + tail; + bufferSize += bytes; + tail += bytes; + return writePtr; } inline void truncate(int pos) { @@ -195,33 +145,22 @@ public: } 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; + while (bytes > 0) { + if (tailBuffer == 0 || tail > bytes) { + bufferSize -= bytes; + if (bufferSize <= 0) + clear(); // try to minify/squeeze us + else + tail -= bytes; return; } + bufferSize -= tail; bytes -= tail; - buffers.removeAt(tailBuffer); - + buffers.removeLast(); --tailBuffer; - tail = buffers.at(tailBuffer).size(); + tail = buffers.last().size(); } - - if (isEmpty()) - clear(); // try to minify/squeeze us } inline bool isEmpty() const { @@ -245,11 +184,11 @@ public: --head; if (head < 0) { buffers.prepend(QByteArray()); - buffers[0].resize(basicBlockSize); + buffers.first().resize(basicBlockSize); head = basicBlockSize - 1; ++tailBuffer; } - buffers[0][head] = c; + buffers.first()[head] = c; ++bufferSize; } @@ -259,8 +198,7 @@ public: inline void clear() { buffers.erase(buffers.begin() + 1, buffers.end()); - buffers[0].resize(0); - buffers[0].squeeze(); + buffers.first().clear(); head = tail = 0; tailBuffer = 0; @@ -269,47 +207,34 @@ public: inline int indexOf(char c) const { int index = 0; + int j = head; 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) { + const char *ptr = buffers[i].constData() + j; + j = index + (i == tailBuffer ? tail : buffers[i].size()) - j; + + while (index < j) { if (*ptr++ == c) return index; ++index; } + j = 0; } 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) { + int j = head; + for (int i = 0; index < maxLength && i < buffers.size(); ++i) { + const char *ptr = buffers[i].constData() + j; + j = qMin(index + (i == tailBuffer ? tail : buffers[i].size()) - j, maxLength); + + while (index < j) { if (*ptr++ == c) return index; ++index; } + j = 0; } return -1; } @@ -318,10 +243,9 @@ public: 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); + memcpy(data + readSoFar, readPointer(), bytesToReadFromThisBlock); readSoFar += bytesToReadFromThisBlock; free(bytesToReadFromThisBlock); } @@ -333,37 +257,19 @@ public: 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; - } + QByteArray qba(buffers.takeFirst()); - // 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; + qba.reserve(0); // avoid that resizing needlessly reallocates if (tailBuffer == 0) { - buffers << QByteArray(); + qba.resize(tail); tail = 0; + buffers.append(QByteArray()); } else { --tailBuffer; } - bufferSize -= qba.length(); + qba.remove(0, head); // does nothing if head is 0 + head = 0; + bufferSize -= qba.size(); return qba; } @@ -373,11 +279,11 @@ public: buffers.last() = qba; } else { buffers.last().resize(tail); - buffers << qba; + buffers.append(qba); ++tailBuffer; } - tail = qba.length(); - bufferSize += qba.length(); + tail = qba.size(); + bufferSize += tail; } inline int skip(int length) { @@ -385,35 +291,26 @@ public: } inline int readLine(char *data, int maxLength) { - int index = indexOf('\n'); - if (index == -1) - return read(data, maxLength); - if (maxLength <= 0) + if (!data || --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); - } + int i = indexOf('\n', maxLength); + i = read(data, i >= 0 ? (i + 1) : maxLength); // Terminate it. - data[readSoFar] = '\0'; - return readSoFar; + data[i] = '\0'; + return i; } inline bool canReadLine() const { - return indexOf('\n') != -1; + return indexOf('\n') >= 0; } private: QList buffers; int head, tail; int tailBuffer; // always buffers.size() - 1 - int basicBlockSize; + const int basicBlockSize; int bufferSize; }; -- cgit v1.2.3