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

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