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 | |
11 | QT_BEGIN_NAMESPACE |
12 | |
13 | static_assert(std::is_nothrow_default_constructible_v<QRingChunk>); |
14 | static_assert(std::is_nothrow_move_constructible_v<QRingChunk>); |
15 | static_assert(std::is_nothrow_move_assignable_v<QRingChunk>); |
16 | |
17 | void 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 | |
25 | void 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 | |
35 | QByteArray 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 | */ |
56 | const 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 | |
73 | void 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 | |
106 | char *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 | */ |
136 | char *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 | |
164 | void 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 | |
197 | void 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 | |
207 | qint64 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 | |
238 | qint64 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 | */ |
258 | QByteArray 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 | */ |
272 | qint64 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 | */ |
300 | void 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 | */ |
319 | void 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 | */ |
333 | void 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 | |
343 | qint64 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 | |
356 | QT_END_NAMESPACE |
357 | |