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
45 QT_BEGIN_NAMESPACE
46
allocate(int alloc)47 void 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
detach()55 void 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
toByteArray()67 QByteArray 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 */
readPointerAtPosition(qint64 pos,qint64 & length) const94 const 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
free(qint64 bytes)111 void 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
reserve(qint64 bytes)144 char *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 */
reserveFront(qint64 bytes)174 char *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
chop(qint64 bytes)202 void 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
clear()235 void 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
indexOf(char c,qint64 maxLength,qint64 pos) const245 qint64 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
read(char * data,qint64 maxLength)276 qint64 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 */
read()296 QByteArray 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 */
peek(char * data,qint64 maxLength,qint64 pos) const310 qint64 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 */
append(const char * data,qint64 size)338 void 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 */
append(const QByteArray & qba)357 void 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
readLine(char * data,qint64 maxLength)366 qint64 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
379 QT_END_NAMESPACE
380