1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Copyright (C) 2015 Alex Trotsenko <alex1973tr@gmail.com>
5** Contact: https://www.qt.io/licensing/
6**
7** This file is part of the QtCore module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial License Usage
11** Licensees holding valid commercial Qt licenses may use this file in
12** accordance with the commercial license agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and The Qt Company. For licensing terms
15** and conditions see https://www.qt.io/terms-conditions. For further
16** information use the contact form at https://www.qt.io/contact-us.
17**
18** GNU Lesser General Public License Usage
19** Alternatively, this file may be used under the terms of the GNU Lesser
20** General Public License version 3 as published by the Free Software
21** Foundation and appearing in the file LICENSE.LGPL3 included in the
22** packaging of this file. Please review the following information to
23** ensure the GNU Lesser General Public License version 3 requirements
24** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
25**
26** GNU General Public License Usage
27** Alternatively, this file may be used under the terms of the GNU
28** General Public License version 2.0 or (at your option) the GNU General
29** Public license version 3 or any later version approved by the KDE Free
30** Qt Foundation. The licenses are as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
32** included in the packaging of this file. Please review the following
33** information to ensure the GNU General Public License requirements will
34** be met: https://www.gnu.org/licenses/gpl-2.0.html and
35** https://www.gnu.org/licenses/gpl-3.0.html.
36**
37** $QT_END_LICENSE$
38**
39****************************************************************************/
40
41#include "private/qringbuffer_p.h"
42#include "private/qbytearray_p.h"
43#include <string.h>
44
45QT_BEGIN_NAMESPACE
46
47void QRingChunk::allocate(int alloc)
48{
49 Q_ASSERT(alloc > 0 && size() == 0);
50
51 if (chunk.size() < alloc || isShared())
52 chunk = QByteArray(alloc, Qt::Uninitialized);
53}
54
55void QRingChunk::detach()
56{
57 Q_ASSERT(isShared());
58
59 const int chunkSize = size();
60 QByteArray x(chunkSize, Qt::Uninitialized);
61 ::memcpy(x.data(), chunk.constData() + headOffset, chunkSize);
62 chunk = std::move(x);
63 headOffset = 0;
64 tailOffset = chunkSize;
65}
66
67QByteArray QRingChunk::toByteArray()
68{
69 if (headOffset != 0 || tailOffset != chunk.size()) {
70 if (isShared())
71 return chunk.mid(headOffset, size());
72
73 if (headOffset != 0) {
74 char *ptr = chunk.data();
75 ::memmove(ptr, ptr + headOffset, size());
76 tailOffset -= headOffset;
77 headOffset = 0;
78 }
79
80 chunk.reserve(0); // avoid that resizing needlessly reallocates
81 chunk.resize(tailOffset);
82 }
83
84 return chunk;
85}
86
87/*!
88 \internal
89
90 Access the bytes at a specified position the out-variable length will
91 contain the amount of bytes readable from there, e.g. the amount still
92 the same QByteArray
93*/
94const char *QRingBuffer::readPointerAtPosition(qint64 pos, qint64 &length) const
95{
96 Q_ASSERT(pos >= 0);
97
98 for (const QRingChunk &chunk : buffers) {
99 length = chunk.size();
100 if (length > pos) {
101 length -= pos;
102 return chunk.data() + pos;
103 }
104 pos -= length;
105 }
106
107 length = 0;
108 return nullptr;
109}
110
111void QRingBuffer::free(qint64 bytes)
112{
113 Q_ASSERT(bytes <= bufferSize);
114
115 while (bytes > 0) {
116 const qint64 chunkSize = buffers.constFirst().size();
117
118 if (buffers.size() == 1 || chunkSize > bytes) {
119 QRingChunk &chunk = buffers.first();
120 // keep a single block around if it does not exceed
121 // the basic block size, to avoid repeated allocations
122 // between uses of the buffer
123 if (bufferSize == bytes) {
124 if (chunk.capacity() <= basicBlockSize && !chunk.isShared()) {
125 chunk.reset();
126 bufferSize = 0;
127 } else {
128 clear(); // try to minify/squeeze us
129 }
130 } else {
131 Q_ASSERT(bytes < MaxByteArraySize);
132 chunk.advance(bytes);
133 bufferSize -= bytes;
134 }
135 return;
136 }
137
138 bufferSize -= chunkSize;
139 bytes -= chunkSize;
140 buffers.removeFirst();
141 }
142}
143
144char *QRingBuffer::reserve(qint64 bytes)
145{
146 Q_ASSERT(bytes > 0 && bytes < MaxByteArraySize);
147
148 const int chunkSize = qMax(basicBlockSize, int(bytes));
149 int tail = 0;
150 if (bufferSize == 0) {
151 if (buffers.isEmpty())
152 buffers.append(QRingChunk(chunkSize));
153 else
154 buffers.first().allocate(chunkSize);
155 } else {
156 const QRingChunk &chunk = buffers.constLast();
157 // if need a new buffer
158 if (basicBlockSize == 0 || chunk.isShared() || bytes > chunk.available())
159 buffers.append(QRingChunk(chunkSize));
160 else
161 tail = chunk.size();
162 }
163
164 buffers.last().grow(bytes);
165 bufferSize += bytes;
166 return buffers.last().data() + tail;
167}
168
169/*!
170 \internal
171
172 Allocate data at buffer head
173*/
174char *QRingBuffer::reserveFront(qint64 bytes)
175{
176 Q_ASSERT(bytes > 0 && bytes < MaxByteArraySize);
177
178 const int chunkSize = qMax(basicBlockSize, int(bytes));
179 if (bufferSize == 0) {
180 if (buffers.isEmpty())
181 buffers.prepend(QRingChunk(chunkSize));
182 else
183 buffers.first().allocate(chunkSize);
184 buffers.first().grow(chunkSize);
185 buffers.first().advance(chunkSize - bytes);
186 } else {
187 const QRingChunk &chunk = buffers.constFirst();
188 // if need a new buffer
189 if (basicBlockSize == 0 || chunk.isShared() || bytes > chunk.head()) {
190 buffers.prepend(QRingChunk(chunkSize));
191 buffers.first().grow(chunkSize);
192 buffers.first().advance(chunkSize - bytes);
193 } else {
194 buffers.first().advance(-bytes);
195 }
196 }
197
198 bufferSize += bytes;
199 return buffers.first().data();
200}
201
202void QRingBuffer::chop(qint64 bytes)
203{
204 Q_ASSERT(bytes <= bufferSize);
205
206 while (bytes > 0) {
207 const qint64 chunkSize = buffers.constLast().size();
208
209 if (buffers.size() == 1 || chunkSize > bytes) {
210 QRingChunk &chunk = buffers.last();
211 // keep a single block around if it does not exceed
212 // the basic block size, to avoid repeated allocations
213 // between uses of the buffer
214 if (bufferSize == bytes) {
215 if (chunk.capacity() <= basicBlockSize && !chunk.isShared()) {
216 chunk.reset();
217 bufferSize = 0;
218 } else {
219 clear(); // try to minify/squeeze us
220 }
221 } else {
222 Q_ASSERT(bytes < MaxByteArraySize);
223 chunk.grow(-bytes);
224 bufferSize -= bytes;
225 }
226 return;
227 }
228
229 bufferSize -= chunkSize;
230 bytes -= chunkSize;
231 buffers.removeLast();
232 }
233}
234
235void QRingBuffer::clear()
236{
237 if (buffers.isEmpty())
238 return;
239
240 buffers.erase(buffers.begin() + 1, buffers.end());
241 buffers.first().clear();
242 bufferSize = 0;
243}
244
245qint64 QRingBuffer::indexOf(char c, qint64 maxLength, qint64 pos) const
246{
247 Q_ASSERT(maxLength >= 0 && pos >= 0);
248
249 if (maxLength == 0)
250 return -1;
251
252 qint64 index = -pos;
253 for (const QRingChunk &chunk : buffers) {
254 const qint64 nextBlockIndex = qMin(index + chunk.size(), maxLength);
255
256 if (nextBlockIndex > 0) {
257 const char *ptr = chunk.data();
258 if (index < 0) {
259 ptr -= index;
260 index = 0;
261 }
262
263 const char *findPtr = reinterpret_cast<const char *>(memchr(ptr, c,
264 nextBlockIndex - index));
265 if (findPtr)
266 return qint64(findPtr - ptr) + index + pos;
267
268 if (nextBlockIndex == maxLength)
269 return -1;
270 }
271 index = nextBlockIndex;
272 }
273 return -1;
274}
275
276qint64 QRingBuffer::read(char *data, qint64 maxLength)
277{
278 const qint64 bytesToRead = qMin(size(), maxLength);
279 qint64 readSoFar = 0;
280 while (readSoFar < bytesToRead) {
281 const qint64 bytesToReadFromThisBlock = qMin(bytesToRead - readSoFar,
282 nextDataBlockSize());
283 if (data)
284 memcpy(data + readSoFar, readPointer(), bytesToReadFromThisBlock);
285 readSoFar += bytesToReadFromThisBlock;
286 free(bytesToReadFromThisBlock);
287 }
288 return readSoFar;
289}
290
291/*!
292 \internal
293
294 Read an unspecified amount (will read the first buffer)
295*/
296QByteArray QRingBuffer::read()
297{
298 if (bufferSize == 0)
299 return QByteArray();
300
301 bufferSize -= buffers.constFirst().size();
302 return buffers.takeFirst().toByteArray();
303}
304
305/*!
306 \internal
307
308 Peek the bytes from a specified position
309*/
310qint64 QRingBuffer::peek(char *data, qint64 maxLength, qint64 pos) const
311{
312 Q_ASSERT(maxLength >= 0 && pos >= 0);
313
314 qint64 readSoFar = 0;
315 for (const QRingChunk &chunk : buffers) {
316 if (readSoFar == maxLength)
317 break;
318
319 qint64 blockLength = chunk.size();
320 if (pos < blockLength) {
321 blockLength = qMin(blockLength - pos, maxLength - readSoFar);
322 memcpy(data + readSoFar, chunk.data() + pos, blockLength);
323 readSoFar += blockLength;
324 pos = 0;
325 } else {
326 pos -= blockLength;
327 }
328 }
329
330 return readSoFar;
331}
332
333/*!
334 \internal
335
336 Append bytes from data to the end
337*/
338void QRingBuffer::append(const char *data, qint64 size)
339{
340 Q_ASSERT(size >= 0);
341
342 if (size == 0)
343 return;
344
345 char *writePointer = reserve(size);
346 if (size == 1)
347 *writePointer = *data;
348 else
349 ::memcpy(writePointer, data, size);
350}
351
352/*!
353 \internal
354
355 Append a new buffer to the end
356*/
357void QRingBuffer::append(const QByteArray &qba)
358{
359 if (bufferSize != 0 || buffers.isEmpty())
360 buffers.append(QRingChunk(qba));
361 else
362 buffers.last().assign(qba);
363 bufferSize += qba.size();
364}
365
366qint64 QRingBuffer::readLine(char *data, qint64 maxLength)
367{
368 Q_ASSERT(data != nullptr && maxLength > 1);
369
370 --maxLength;
371 qint64 i = indexOf('\n', maxLength);
372 i = read(data, i >= 0 ? (i + 1) : maxLength);
373
374 // Terminate it.
375 data[i] = '\0';
376 return i;
377}
378
379QT_END_NAMESPACE
380