Qt 4.8
qringbuffer_p.h
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtCore module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #ifndef QRINGBUFFER_P_H
43 #define QRINGBUFFER_P_H
44 
45 //
46 // W A R N I N G
47 // -------------
48 //
49 // This file is not part of the Qt API. It exists for the convenience
50 // of a number of Qt sources files. This header file may change from
51 // version to version without notice, or even be removed.
52 //
53 // We mean it.
54 //
55 
56 #include <QtCore/qbytearray.h>
57 #include <QtCore/qlist.h>
58 
60 
62 {
63 public:
64  inline QRingBuffer(int growth = 4096) : basicBlockSize(growth) {
65  buffers << QByteArray();
66  clear();
67  }
68 
69  inline int nextDataBlockSize() const {
70  return (tailBuffer == 0 ? tail : buffers.first().size()) - head;
71  }
72 
73  inline const char *readPointer() const {
74  return buffers.isEmpty() ? 0 : (buffers.first().constData() + head);
75  }
76 
77  // access the bytes at a specified position
78  // the out-variable length will contain the amount of bytes readable
79  // from there, e.g. the amount still the same QByteArray
80  inline const char *readPointerAtPosition(qint64 pos, qint64 &length) const {
81  if (buffers.isEmpty()) {
82  length = 0;
83  return 0;
84  }
85 
86  if (pos >= bufferSize) {
87  length = 0;
88  return 0;
89  }
90 
91  // special case: it is in the first buffer
92  int nextDataBlockSizeValue = nextDataBlockSize();
93  if (pos - head < nextDataBlockSizeValue) {
94  length = nextDataBlockSizeValue - pos;
95  return buffers.at(0).constData() + head + pos;
96  }
97 
98  // special case: we only had one buffer and tried to read over it
99  if (buffers.length() == 1) {
100  length = 0;
101  return 0;
102  }
103 
104  // skip the first
105  pos -= nextDataBlockSizeValue;
106 
107  // normal case: it is somewhere in the second to the-one-before-the-tailBuffer
108  for (int i = 1; i < tailBuffer; i++) {
109  if (pos >= buffers[i].size()) {
110  pos -= buffers[i].size();
111  continue;
112  }
113 
114  length = buffers[i].length() - pos;
115  return buffers[i].constData() + pos;
116  }
117 
118  // it is in the tail buffer
119  length = tail - pos;
120  return buffers[tailBuffer].constData() + pos;
121  }
122 
123  inline void free(int bytes) {
124  bufferSize -= bytes;
125  if (bufferSize < 0)
126  bufferSize = 0;
127 
128  for (;;) {
129  int nextBlockSize = nextDataBlockSize();
130  if (bytes < nextBlockSize) {
131  head += bytes;
132  if (head == tail && tailBuffer == 0)
133  head = tail = 0;
134  break;
135  }
136 
137  bytes -= nextBlockSize;
138  if (buffers.count() == 1) {
139  if (buffers.at(0).size() != basicBlockSize)
140  buffers[0].resize(basicBlockSize);
141  head = tail = 0;
142  tailBuffer = 0;
143  break;
144  }
145 
146  buffers.removeAt(0);
147  --tailBuffer;
148  head = 0;
149  }
150 
151  if (isEmpty())
152  clear(); // try to minify/squeeze us
153  }
154 
155  inline char *reserve(int bytes) {
156  // if this is a fresh empty QRingBuffer
157  if (bufferSize == 0) {
158  buffers[0].resize(qMax(basicBlockSize, bytes));
159  bufferSize += bytes;
160  tail = bytes;
161  return buffers[tailBuffer].data();
162  }
163 
164  bufferSize += bytes;
165 
166  // if there is already enough space, simply return.
167  if (tail + bytes <= buffers.at(tailBuffer).size()) {
168  char *writePtr = buffers[tailBuffer].data() + tail;
169  tail += bytes;
170  return writePtr;
171  }
172 
173  // if our buffer isn't half full yet, simply resize it.
174  if (tail < buffers.at(tailBuffer).size() / 2) {
175  buffers[tailBuffer].resize(tail + bytes);
176  char *writePtr = buffers[tailBuffer].data() + tail;
177  tail += bytes;
178  return writePtr;
179  }
180 
181  // shrink this buffer to its current size
182  buffers[tailBuffer].resize(tail);
183 
184  // create a new QByteArray with the right size
185  buffers << QByteArray();
186  ++tailBuffer;
187  buffers[tailBuffer].resize(qMax(basicBlockSize, bytes));
188  tail = bytes;
189  return buffers[tailBuffer].data();
190  }
191 
192  inline void truncate(int pos) {
193  if (pos < size())
194  chop(size() - pos);
195  }
196 
197  inline void chop(int bytes) {
198  bufferSize -= bytes;
199  if (bufferSize < 0)
200  bufferSize = 0;
201 
202  for (;;) {
203  // special case: head and tail are in the same buffer
204  if (tailBuffer == 0) {
205  tail -= bytes;
206  if (tail <= head)
207  tail = head = 0;
208  return;
209  }
210 
211  if (bytes <= tail) {
212  tail -= bytes;
213  return;
214  }
215 
216  bytes -= tail;
218 
219  --tailBuffer;
221  }
222 
223  if (isEmpty())
224  clear(); // try to minify/squeeze us
225  }
226 
227  inline bool isEmpty() const {
228  return tailBuffer == 0 && tail == 0;
229  }
230 
231  inline int getChar() {
232  if (isEmpty())
233  return -1;
234  char c = *readPointer();
235  free(1);
236  return int(uchar(c));
237  }
238 
239  inline void putChar(char c) {
240  char *ptr = reserve(1);
241  *ptr = c;
242  }
243 
244  inline void ungetChar(char c) {
245  --head;
246  if (head < 0) {
248  buffers[0].resize(basicBlockSize);
249  head = basicBlockSize - 1;
250  ++tailBuffer;
251  }
252  buffers[0][head] = c;
253  ++bufferSize;
254  }
255 
256  inline int size() const {
257  return bufferSize;
258  }
259 
260  inline void clear() {
261  buffers.erase(buffers.begin() + 1, buffers.end());
262  buffers[0].resize(0);
263  buffers[0].squeeze();
264 
265  head = tail = 0;
266  tailBuffer = 0;
267  bufferSize = 0;
268  }
269 
270  inline int indexOf(char c) const {
271  int index = 0;
272  for (int i = 0; i < buffers.size(); ++i) {
273  int start = 0;
274  int end = buffers.at(i).size();
275 
276  if (i == 0)
277  start = head;
278  if (i == tailBuffer)
279  end = tail;
280  const char *ptr = buffers.at(i).data() + start;
281  for (int j = start; j < end; ++j) {
282  if (*ptr++ == c)
283  return index;
284  ++index;
285  }
286  }
287  return -1;
288  }
289 
290  inline int indexOf(char c, int maxLength) const {
291  int index = 0;
292  int remain = qMin(size(), maxLength);
293  for (int i = 0; remain && i < buffers.size(); ++i) {
294  int start = 0;
295  int end = buffers.at(i).size();
296 
297  if (i == 0)
298  start = head;
299  if (i == tailBuffer)
300  end = tail;
301  if (remain < end - start) {
302  end = start + remain;
303  remain = 0;
304  } else {
305  remain -= end - start;
306  }
307  const char *ptr = buffers.at(i).data() + start;
308  for (int j = start; j < end; ++j) {
309  if (*ptr++ == c)
310  return index;
311  ++index;
312  }
313  }
314  return -1;
315  }
316 
317  inline int read(char *data, int maxLength) {
318  int bytesToRead = qMin(size(), maxLength);
319  int readSoFar = 0;
320  while (readSoFar < bytesToRead) {
321  const char *ptr = readPointer();
322  int bytesToReadFromThisBlock = qMin(bytesToRead - readSoFar, nextDataBlockSize());
323  if (data)
324  memcpy(data + readSoFar, ptr, bytesToReadFromThisBlock);
325  readSoFar += bytesToReadFromThisBlock;
326  free(bytesToReadFromThisBlock);
327  }
328  return readSoFar;
329  }
330 
331  inline QByteArray read(int maxLength) {
332  QByteArray tmp;
333  tmp.resize(qMin(maxLength, size()));
334  read(tmp.data(), tmp.size());
335  return tmp;
336  }
337 
338  inline QByteArray readAll() {
339  return read(size());
340  }
341 
342  // read an unspecified amount (will read the first buffer)
343  inline QByteArray read() {
344  if (bufferSize == 0)
345  return QByteArray();
346 
347  // multiple buffers, just take the first one
348  if (head == 0 && tailBuffer != 0) {
349  QByteArray qba = buffers.takeFirst();
350  --tailBuffer;
351  bufferSize -= qba.length();
352  return qba;
353  }
354 
355  // one buffer with good value for head. Just take it.
356  if (head == 0 && tailBuffer == 0) {
357  QByteArray qba = buffers.takeFirst();
358  qba.resize(tail);
359  buffers << QByteArray();
360  bufferSize = 0;
361  tail = 0;
362  return qba;
363  }
364 
365  // Bad case: We have to memcpy.
366  // We can avoid by initializing the QRingBuffer with basicBlockSize of 0
367  // and only using this read() function.
370  head = 0;
371  if (tailBuffer == 0) {
372  buffers << QByteArray();
373  tail = 0;
374  } else {
375  --tailBuffer;
376  }
377  bufferSize -= qba.length();
378  return qba;
379  }
380 
381  // append a new buffer to the end
382  inline void append(const QByteArray &qba) {
383  buffers[tailBuffer].resize(tail);
384  buffers << qba;
385  ++tailBuffer;
386  tail = qba.length();
387  bufferSize += qba.length();
388  }
389 
390  inline QByteArray peek(int maxLength) const {
391  int bytesToRead = qMin(size(), maxLength);
392  if(maxLength <= 0)
393  return QByteArray();
394  QByteArray ret;
395  ret.resize(bytesToRead);
396  int readSoFar = 0;
397  for (int i = 0; readSoFar < bytesToRead && i < buffers.size(); ++i) {
398  int start = 0;
399  int end = buffers.at(i).size();
400  if (i == 0)
401  start = head;
402  if (i == tailBuffer)
403  end = tail;
404  const int len = qMin(ret.size()-readSoFar, end-start);
405  memcpy(ret.data()+readSoFar, buffers.at(i).constData()+start, len);
406  readSoFar += len;
407  }
408  Q_ASSERT(readSoFar == ret.size());
409  return ret;
410  }
411 
412  inline int skip(int length) {
413  return read(0, length);
414  }
415 
416  inline int readLine(char *data, int maxLength) {
417  int index = indexOf('\n');
418  if (index == -1)
419  return read(data, maxLength);
420  if (maxLength <= 0)
421  return -1;
422 
423  int readSoFar = 0;
424  while (readSoFar < index + 1 && readSoFar < maxLength - 1) {
425  int bytesToRead = qMin((index + 1) - readSoFar, nextDataBlockSize());
426  bytesToRead = qMin(bytesToRead, (maxLength - 1) - readSoFar);
427  memcpy(data + readSoFar, readPointer(), bytesToRead);
428  readSoFar += bytesToRead;
429  free(bytesToRead);
430  }
431 
432  // Terminate it.
433  data[readSoFar] = '\0';
434  return readSoFar;
435  }
436 
437  inline bool canReadLine() const {
438  return indexOf('\n') != -1;
439  }
440 
441 private:
443  int head, tail;
444  int tailBuffer; // always buffers.size() - 1
447 };
448 
450 
451 #endif // QRINGBUFFER_P_H
unsigned char c[8]
Definition: qnumeric_p.h:62
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
char * data()
Returns a pointer to the data stored in the byte array.
Definition: qbytearray.h:429
const char * readPointer() const
Definition: qringbuffer_p.h:73
int indexOf(char c, int maxLength) const
void append(const QByteArray &qba)
QByteArray readAll()
int nextDataBlockSize() const
Definition: qringbuffer_p.h:69
The QByteArray class provides an array of bytes.
Definition: qbytearray.h:135
QByteArray peek(int maxLength) const
iterator begin()
Returns an STL-style iterator pointing to the first item in the list.
Definition: qlist.h:267
int count(const T &t) const
Returns the number of occurrences of value in the list.
Definition: qlist.h:891
bool isEmpty() const
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
void ungetChar(char c)
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
bool isEmpty() const
Returns true if the list contains no items; otherwise returns false.
Definition: qlist.h:152
const T & head() const
unsigned char uchar
Definition: qglobal.h:994
char * reserve(int bytes)
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
T takeFirst()
Removes the first item in the list and returns it.
Definition: qlist.h:489
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the list...
Definition: qlist.h:270
void prepend(const T &t)
Inserts value at the beginning of the list.
Definition: qlist.h:541
const T & at(int i) const
Returns the item at index position i in the list.
Definition: qlist.h:468
static const char * data(const QByteArray &arr)
void removeFirst()
Removes the first item in the list.
Definition: qlist.h:286
const T * ptr(const T &t)
__int64 qint64
Definition: qglobal.h:942
int length() const
Same as size().
Definition: qbytearray.h:356
T & first()
Returns a reference to the first item in the list.
Definition: qlist.h:282
const char * constData() const
Returns a pointer to the data stored in the byte array.
Definition: qbytearray.h:433
iterator erase(iterator pos)
Removes the item associated with the iterator pos from the list, and returns an iterator to the next ...
Definition: qlist.h:464
int readLine(char *data, int maxLength)
void truncate(int pos)
void free(int bytes)
void chop(int bytes)
const char * readPointerAtPosition(qint64 pos, qint64 &length) const
Definition: qringbuffer_p.h:80
void putChar(char c)
QByteArray read()
QByteArray read(int maxLength)
int length() const
This function is identical to count().
Definition: qlist.h:281
void resize(int size)
Sets the size of the byte array to size bytes.
int size() const
Returns the number of items in the list.
Definition: qlist.h:137
bool canReadLine() const
int skip(int length)
int size() const
Returns the number of bytes in this byte array.
Definition: qbytearray.h:402
int read(char *data, int maxLength)
quint16 index
int indexOf(char c) const
QList< QByteArray > buffers
static const KeyPair *const end
QRingBuffer(int growth=4096)
Definition: qringbuffer_p.h:64
int size() const
void removeAt(int i)
Removes the item at index position i.
Definition: qlist.h:480