1// Copyright (C) 2021 The Qt Company Ltd.
2// Copyright (C) 2015 Alex Trotsenko <alex1973tr@gmail.com>
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
4
5#include "private/qringbuffer_p.h"
6#include "private/qbytearray_p.h"
7
8#include <type_traits>
9
10#include <string.h>
11
12QT_BEGIN_NAMESPACE
13
14static_assert(std::is_nothrow_default_constructible_v<QRingChunk>);
15static_assert(std::is_nothrow_move_constructible_v<QRingChunk>);
16static_assert(std::is_nothrow_move_assignable_v<QRingChunk>);
17
18void QRingChunk::allocate(qsizetype alloc)
19{
20 Q_ASSERT(alloc > 0 && size() == 0);
21
22 if (chunk.size() < alloc || isShared())
23 chunk = QByteArray(alloc, Qt::Uninitialized);
24}
25
26void QRingChunk::detach()
27{
28 Q_ASSERT(isShared());
29
30 const qsizetype chunkSize = size();
31 chunk = QByteArray(std::as_const(t&: *this).data(), chunkSize);
32 headOffset = 0;
33 tailOffset = chunkSize;
34}
35
36QByteArray QRingChunk::toByteArray() &&
37{
38 // ### Replace with std::move(chunk).sliced(head(), size()) once sliced()&& is available
39 if (headOffset != 0 || tailOffset != chunk.size()) {
40 if (isShared())
41 return chunk.sliced(pos: head(), n: size());
42
43 chunk.resize(size: tailOffset);
44 chunk.remove(index: 0, len: headOffset);
45 }
46
47 return std::move(chunk);
48}
49
50/*!
51 \internal
52
53 Access the bytes at a specified position the out-variable length will
54 contain the amount of bytes readable from there, e.g. the amount still
55 the same QByteArray
56*/
57const char *QRingBuffer::readPointerAtPosition(qint64 pos, qint64 &length) const
58{
59 Q_ASSERT(pos >= 0);
60
61 for (const QRingChunk &chunk : buffers) {
62 length = chunk.size();
63 if (length > pos) {
64 length -= pos;
65 return chunk.data() + pos;
66 }
67 pos -= length;
68 }
69
70 length = 0;
71 return nullptr;
72}
73
74void QRingBuffer::free(qint64 bytes)
75{
76 Q_ASSERT(bytes <= bufferSize);
77
78 while (bytes > 0) {
79 const qint64 chunkSize = buffers.constFirst().size();
80
81 if (buffers.size() == 1 || chunkSize > bytes) {
82 QRingChunk &chunk = buffers.first();
83 // keep a single block around if it does not exceed
84 // the basic block size, to avoid repeated allocations
85 // between uses of the buffer
86 if (bufferSize == bytes) {
87 if (chunk.capacity() <= basicBlockSize && !chunk.isShared()) {
88 chunk.reset();
89 bufferSize = 0;
90 } else {
91 clear(); // try to minify/squeeze us
92 }
93 } else {
94 Q_ASSERT(bytes < MaxByteArraySize);
95 chunk.advance(offset: bytes);
96 bufferSize -= bytes;
97 }
98 return;
99 }
100
101 bufferSize -= chunkSize;
102 bytes -= chunkSize;
103 buffers.removeFirst();
104 }
105}
106
107char *QRingBuffer::reserve(qint64 bytes)
108{
109 Q_ASSERT(bytes > 0 && bytes < MaxByteArraySize);
110
111 const qsizetype chunkSize = qMax(a: qint64(basicBlockSize), b: bytes);
112 qsizetype tail = 0;
113 if (bufferSize == 0) {
114 if (buffers.isEmpty())
115 buffers.append(t: QRingChunk(chunkSize));
116 else
117 buffers.first().allocate(alloc: chunkSize);
118 } else {
119 const QRingChunk &chunk = buffers.constLast();
120 // if need a new buffer
121 if (basicBlockSize == 0 || chunk.isShared() || bytes > chunk.available())
122 buffers.append(t: QRingChunk(chunkSize));
123 else
124 tail = chunk.size();
125 }
126
127 buffers.last().grow(offset: bytes);
128 bufferSize += bytes;
129 return buffers.last().data() + tail;
130}
131
132/*!
133 \internal
134
135 Allocate data at buffer head
136*/
137char *QRingBuffer::reserveFront(qint64 bytes)
138{
139 Q_ASSERT(bytes > 0 && bytes < MaxByteArraySize);
140
141 const qsizetype chunkSize = qMax(a: qint64(basicBlockSize), b: bytes);
142 if (bufferSize == 0) {
143 if (buffers.isEmpty())
144 buffers.prepend(t: QRingChunk(chunkSize));
145 else
146 buffers.first().allocate(alloc: chunkSize);
147 buffers.first().grow(offset: chunkSize);
148 buffers.first().advance(offset: chunkSize - bytes);
149 } else {
150 const QRingChunk &chunk = buffers.constFirst();
151 // if need a new buffer
152 if (basicBlockSize == 0 || chunk.isShared() || bytes > chunk.head()) {
153 buffers.prepend(t: QRingChunk(chunkSize));
154 buffers.first().grow(offset: chunkSize);
155 buffers.first().advance(offset: chunkSize - bytes);
156 } else {
157 buffers.first().advance(offset: -bytes);
158 }
159 }
160
161 bufferSize += bytes;
162 return buffers.first().data();
163}
164
165void QRingBuffer::chop(qint64 bytes)
166{
167 Q_ASSERT(bytes <= bufferSize);
168
169 while (bytes > 0) {
170 const qsizetype chunkSize = buffers.constLast().size();
171
172 if (buffers.size() == 1 || chunkSize > bytes) {
173 QRingChunk &chunk = buffers.last();
174 // keep a single block around if it does not exceed
175 // the basic block size, to avoid repeated allocations
176 // between uses of the buffer
177 if (bufferSize == bytes) {
178 if (chunk.capacity() <= basicBlockSize && !chunk.isShared()) {
179 chunk.reset();
180 bufferSize = 0;
181 } else {
182 clear(); // try to minify/squeeze us
183 }
184 } else {
185 Q_ASSERT(bytes < MaxByteArraySize);
186 chunk.grow(offset: -bytes);
187 bufferSize -= bytes;
188 }
189 return;
190 }
191
192 bufferSize -= chunkSize;
193 bytes -= chunkSize;
194 buffers.removeLast();
195 }
196}
197
198void QRingBuffer::clear()
199{
200 if (buffers.isEmpty())
201 return;
202
203 buffers.erase(abegin: buffers.begin() + 1, aend: buffers.end());
204 buffers.first().clear();
205 bufferSize = 0;
206}
207
208qint64 QRingBuffer::indexOf(char c, qint64 maxLength, qint64 pos) const
209{
210 Q_ASSERT(maxLength >= 0 && pos >= 0);
211
212 if (maxLength == 0)
213 return -1;
214
215 qint64 index = -pos;
216 for (const QRingChunk &chunk : buffers) {
217 const qint64 nextBlockIndex = qMin(a: index + chunk.size(), b: maxLength);
218
219 if (nextBlockIndex > 0) {
220 const char *ptr = chunk.data();
221 if (index < 0) {
222 ptr -= index;
223 index = 0;
224 }
225
226 const char *findPtr = reinterpret_cast<const char *>(memchr(s: ptr, c: c,
227 n: nextBlockIndex - index));
228 if (findPtr)
229 return qint64(findPtr - ptr) + index + pos;
230
231 if (nextBlockIndex == maxLength)
232 return -1;
233 }
234 index = nextBlockIndex;
235 }
236 return -1;
237}
238
239qint64 QRingBuffer::read(char *data, qint64 maxLength)
240{
241 const qint64 bytesToRead = qMin(a: size(), b: maxLength);
242 qint64 readSoFar = 0;
243 while (readSoFar < bytesToRead) {
244 const qint64 bytesToReadFromThisBlock = qMin(a: bytesToRead - readSoFar,
245 b: nextDataBlockSize());
246 if (data)
247 memcpy(dest: data + readSoFar, src: readPointer(), n: bytesToReadFromThisBlock);
248 readSoFar += bytesToReadFromThisBlock;
249 free(bytes: bytesToReadFromThisBlock);
250 }
251 return readSoFar;
252}
253
254/*!
255 \internal
256
257 Read an unspecified amount (will read the first buffer)
258*/
259QByteArray QRingBuffer::read()
260{
261 if (bufferSize == 0)
262 return QByteArray();
263
264 bufferSize -= buffers.constFirst().size();
265 return buffers.takeFirst().toByteArray();
266}
267
268/*!
269 \internal
270
271 Peek the bytes from a specified position
272*/
273qint64 QRingBuffer::peek(char *data, qint64 maxLength, qint64 pos) const
274{
275 Q_ASSERT(maxLength >= 0 && pos >= 0);
276
277 qint64 readSoFar = 0;
278 for (const QRingChunk &chunk : buffers) {
279 if (readSoFar == maxLength)
280 break;
281
282 qint64 blockLength = chunk.size();
283 if (pos < blockLength) {
284 blockLength = qMin(a: blockLength - pos, b: maxLength - readSoFar);
285 memcpy(dest: data + readSoFar, src: chunk.data() + pos, n: blockLength);
286 readSoFar += blockLength;
287 pos = 0;
288 } else {
289 pos -= blockLength;
290 }
291 }
292
293 return readSoFar;
294}
295
296/*!
297 \internal
298
299 Append bytes from data to the end
300*/
301void QRingBuffer::append(const char *data, qint64 size)
302{
303 Q_ASSERT(size >= 0);
304
305 if (size == 0)
306 return;
307
308 char *writePointer = reserve(bytes: size);
309 if (size == 1)
310 *writePointer = *data;
311 else
312 ::memcpy(dest: writePointer, src: data, n: size);
313}
314
315/*!
316 \internal
317
318 Append a new buffer to the end
319*/
320void QRingBuffer::append(const QByteArray &qba)
321{
322 if (bufferSize != 0 || buffers.isEmpty())
323 buffers.append(t: QRingChunk(qba));
324 else
325 buffers.last().assign(qba);
326 bufferSize += qba.size();
327}
328
329/*!
330 \internal
331
332 Append a new buffer to the end
333*/
334void QRingBuffer::append(QByteArray &&qba)
335{
336 const auto qbaSize = qba.size();
337 if (bufferSize != 0 || buffers.isEmpty())
338 buffers.emplace_back(args: std::move(qba));
339 else
340 buffers.last().assign(qba: std::move(qba));
341 bufferSize += qbaSize;
342}
343
344qint64 QRingBuffer::readLine(char *data, qint64 maxLength)
345{
346 Q_ASSERT(data != nullptr && maxLength > 1);
347
348 --maxLength;
349 qint64 i = indexOf(c: '\n', maxLength);
350 i = read(data, maxLength: i >= 0 ? (i + 1) : maxLength);
351
352 // Terminate it.
353 data[i] = '\0';
354 return i;
355}
356
357QT_END_NAMESPACE
358

source code of qtbase/src/corelib/tools/qringbuffer.cpp