1 | // Copyright (C) 2020 The Qt Company Ltd. |
---|---|
2 | // Copyright (C) 2019 Intel Corporation. |
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 "qbitarray.h" |
6 | #include <qalgorithms.h> |
7 | #include <qdatastream.h> |
8 | #include <qdebug.h> |
9 | #include <qendian.h> |
10 | |
11 | #include <limits> |
12 | |
13 | #include <string.h> |
14 | |
15 | QT_BEGIN_NAMESPACE |
16 | |
17 | /*! |
18 | \class QBitArray |
19 | \inmodule QtCore |
20 | \brief The QBitArray class provides an array of bits. |
21 | |
22 | \ingroup tools |
23 | \ingroup shared |
24 | \reentrant |
25 | |
26 | \compares equality |
27 | |
28 | A QBitArray is an array that gives access to individual bits and |
29 | provides operators (\l{operator&()}{AND}, \l{operator|()}{OR}, |
30 | \l{operator^()}{XOR}, and \l{operator~()}{NOT}) that work on |
31 | entire arrays of bits. It uses \l{implicit sharing} (copy-on-write) |
32 | to reduce memory usage and to avoid the needless copying of data. |
33 | |
34 | The following code constructs a QBitArray containing 200 bits |
35 | initialized to false (0): |
36 | |
37 | \snippet code/src_corelib_tools_qbitarray.cpp 0 |
38 | |
39 | To initialize the bits to true, either pass \c true as second |
40 | argument to the constructor, or call fill() later on. |
41 | |
42 | QBitArray uses 0-based indexes, just like C++ arrays. To access |
43 | the bit at a particular index position, you can use operator[](). |
44 | On non-const bit arrays, operator[]() returns a reference to a |
45 | bit that can be used on the left side of an assignment. For |
46 | example: |
47 | |
48 | \snippet code/src_corelib_tools_qbitarray.cpp 1 |
49 | |
50 | For technical reasons, it is more efficient to use testBit() and |
51 | setBit() to access bits in the array than operator[](). For |
52 | example: |
53 | |
54 | \snippet code/src_corelib_tools_qbitarray.cpp 2 |
55 | |
56 | QBitArray supports \c{&} (\l{operator&()}{AND}), \c{|} |
57 | (\l{operator|()}{OR}), \c{^} (\l{operator^()}{XOR}), |
58 | \c{~} (\l{operator~()}{NOT}), as well as |
59 | \c{&=}, \c{|=}, and \c{^=}. These operators work in the same way |
60 | as the built-in C++ bitwise operators of the same name. For |
61 | example: |
62 | |
63 | \snippet code/src_corelib_tools_qbitarray.cpp 3 |
64 | |
65 | For historical reasons, QBitArray distinguishes between a null |
66 | bit array and an empty bit array. A \e null bit array is a bit |
67 | array that is initialized using QBitArray's default constructor. |
68 | An \e empty bit array is any bit array with size 0. A null bit |
69 | array is always empty, but an empty bit array isn't necessarily |
70 | null: |
71 | |
72 | \snippet code/src_corelib_tools_qbitarray.cpp 4 |
73 | |
74 | All functions except isNull() treat null bit arrays the same as |
75 | empty bit arrays; for example, QBitArray() compares equal to |
76 | QBitArray(0). We recommend that you always use isEmpty() and |
77 | avoid isNull(). |
78 | |
79 | \sa QByteArray, QList |
80 | */ |
81 | |
82 | #if QT_VERSION < QT_VERSION_CHECK(7, 0, 0) |
83 | /*! |
84 | \fn QBitArray::QBitArray(QBitArray &&other) |
85 | |
86 | Move-constructs a QBitArray instance, making it point at the same |
87 | object that \a other was pointing to. |
88 | |
89 | \since 5.2 |
90 | */ |
91 | #endif |
92 | |
93 | /*! \fn QBitArray::QBitArray() |
94 | |
95 | Constructs an empty bit array. |
96 | |
97 | \sa isEmpty() |
98 | */ |
99 | |
100 | /* |
101 | * QBitArray construction note: |
102 | * |
103 | * We overallocate the byte array by 1 byte. The first user bit is at |
104 | * d.data()[1]. On the extra first byte, we store the difference between the |
105 | * number of bits in the byte array (including this byte) and the number of |
106 | * bits in the bit array. Therefore, for a non-empty QBitArray, it's always a |
107 | * number between 8 and 15. For the empty one, d is the an empty QByteArray and |
108 | * *d.constData() is the QByteArray's terminating NUL (0) byte. |
109 | * |
110 | * This allows for fast calculation of the bit array size: |
111 | * inline qsizetype size() const { return (d.size() << 3) - *d.constData(); } |
112 | */ |
113 | |
114 | static constexpr qsizetype storage_size(qsizetype size) |
115 | { |
116 | // avoid overflow when adding 7, by doing the arithmetic in unsigned space: |
117 | return qsizetype((size_t(size) + 7) / 8); |
118 | } |
119 | |
120 | static constexpr qsizetype allocation_size(qsizetype size) |
121 | { |
122 | return size <= 0 ? 0 : storage_size(size) + 1; |
123 | } |
124 | |
125 | static void adjust_head_and_tail(char *data, qsizetype storageSize, qsizetype logicalSize) |
126 | { |
127 | quint8 *c = reinterpret_cast<quint8 *>(data); |
128 | // store the difference between storage and logical size in d[0]: |
129 | *c = quint8(size_t(storageSize) * 8 - logicalSize); |
130 | // reset unallocated bits to 0: |
131 | if (logicalSize & 7) |
132 | *(c + 1 + logicalSize / 8) &= (1 << (logicalSize & 7)) - 1; |
133 | } |
134 | |
135 | /*! |
136 | Constructs a bit array containing \a size bits. The bits are |
137 | initialized with \a value, which defaults to false (0). |
138 | */ |
139 | QBitArray::QBitArray(qsizetype size, bool value) |
140 | : d(allocation_size(size), value ? 0xFF : 0x00) |
141 | { |
142 | Q_ASSERT_X(size >= 0, "QBitArray::QBitArray", "Size must be greater than or equal to 0."); |
143 | if (size <= 0) |
144 | return; |
145 | |
146 | adjust_head_and_tail(data: d.data(), storageSize: d.size(), logicalSize: size); |
147 | } |
148 | |
149 | /*! \fn qsizetype QBitArray::size() const |
150 | |
151 | Returns the number of bits stored in the bit array. |
152 | |
153 | \sa resize() |
154 | */ |
155 | |
156 | /*! \fn qsizetype QBitArray::count() const |
157 | |
158 | Same as size(). |
159 | */ |
160 | |
161 | /*! |
162 | If \a on is true, this function returns the number of |
163 | 1-bits stored in the bit array; otherwise the number |
164 | of 0-bits is returned. |
165 | */ |
166 | qsizetype QBitArray::count(bool on) const |
167 | { |
168 | qsizetype numBits = 0; |
169 | const quint8 *bits = reinterpret_cast<const quint8 *>(d.data()) + 1; |
170 | |
171 | // the loops below will try to read from *end |
172 | // it's the QByteArray implicit NUL, so it will not change the bit count |
173 | const quint8 *const end = reinterpret_cast<const quint8 *>(d.end()); |
174 | |
175 | while (bits + 7 <= end) { |
176 | quint64 v = qFromUnaligned<quint64>(src: bits); |
177 | bits += 8; |
178 | numBits += qsizetype(qPopulationCount(v)); |
179 | } |
180 | if (bits + 3 <= end) { |
181 | quint32 v = qFromUnaligned<quint32>(src: bits); |
182 | bits += 4; |
183 | numBits += qsizetype(qPopulationCount(v)); |
184 | } |
185 | if (bits + 1 < end) { |
186 | quint16 v = qFromUnaligned<quint16>(src: bits); |
187 | bits += 2; |
188 | numBits += qsizetype(qPopulationCount(v)); |
189 | } |
190 | if (bits < end) |
191 | numBits += qsizetype(qPopulationCount(v: bits[0])); |
192 | |
193 | return on ? numBits : size() - numBits; |
194 | } |
195 | |
196 | /*! |
197 | Resizes the bit array to \a size bits. |
198 | |
199 | If \a size is greater than the current size, the bit array is |
200 | extended to make it \a size bits with the extra bits added to the |
201 | end. The new bits are initialized to false (0). |
202 | |
203 | If \a size is less than the current size, bits are removed from |
204 | the end. |
205 | |
206 | \sa size() |
207 | */ |
208 | void QBitArray::resize(qsizetype size) |
209 | { |
210 | Q_ASSERT_X(size >= 0, "QBitArray::resize", "Size must be greater than or equal to 0."); |
211 | if (size <= 0) { |
212 | d.resize(size: 0); |
213 | } else { |
214 | d.resize(size: allocation_size(size), c: 0x00); |
215 | adjust_head_and_tail(data: d.data(), storageSize: d.size(), logicalSize: size); |
216 | } |
217 | } |
218 | |
219 | /*! \fn bool QBitArray::isEmpty() const |
220 | |
221 | Returns \c true if this bit array has size 0; otherwise returns |
222 | false. |
223 | |
224 | \sa size() |
225 | */ |
226 | |
227 | /*! \fn bool QBitArray::isNull() const |
228 | |
229 | Returns \c true if this bit array is null; otherwise returns \c false. |
230 | |
231 | Example: |
232 | \snippet code/src_corelib_tools_qbitarray.cpp 5 |
233 | |
234 | Qt makes a distinction between null bit arrays and empty bit |
235 | arrays for historical reasons. For most applications, what |
236 | matters is whether or not a bit array contains any data, |
237 | and this can be determined using isEmpty(). |
238 | |
239 | \sa isEmpty() |
240 | */ |
241 | |
242 | /*! \fn bool QBitArray::fill(bool value, qsizetype size = -1) |
243 | |
244 | Sets every bit in the bit array to \a value, returning true if successful; |
245 | otherwise returns \c false. If \a size is different from -1 (the default), |
246 | the bit array is resized to \a size beforehand. |
247 | |
248 | Example: |
249 | \snippet code/src_corelib_tools_qbitarray.cpp 6 |
250 | |
251 | \sa resize() |
252 | */ |
253 | |
254 | /*! |
255 | \overload |
256 | |
257 | Sets bits at index positions \a begin up to (but not including) \a end |
258 | to \a value. |
259 | |
260 | \a begin must be a valid index position in the bit array |
261 | (0 <= \a begin < size()). |
262 | |
263 | \a end must be either a valid index position or equal to size(), in |
264 | which case the fill operation runs until the end of the array |
265 | (0 <= \a end <= size()). |
266 | |
267 | Example: |
268 | \snippet code/src_corelib_tools_qbitarray.cpp 15 |
269 | */ |
270 | |
271 | void QBitArray::fill(bool value, qsizetype begin, qsizetype end) |
272 | { |
273 | while (begin < end && begin & 0x7) |
274 | setBit(i: begin++, val: value); |
275 | qsizetype len = end - begin; |
276 | if (len <= 0) |
277 | return; |
278 | qsizetype s = len & ~qsizetype(0x7); |
279 | uchar *c = reinterpret_cast<uchar *>(d.data()); |
280 | memset(s: c + (begin >> 3) + 1, c: value ? 0xff : 0, n: s >> 3); |
281 | begin += s; |
282 | while (begin < end) |
283 | setBit(i: begin++, val: value); |
284 | } |
285 | |
286 | /*! |
287 | \fn const char *QBitArray::bits() const |
288 | \since 5.11 |
289 | |
290 | Returns a pointer to a dense bit array for this QBitArray. Bits are counted |
291 | upwards from the least significant bit in each byte. The number of bits |
292 | relevant in the last byte is given by \c{size() % 8}. |
293 | |
294 | \sa fromBits(), size() |
295 | */ |
296 | |
297 | /*! |
298 | \since 5.11 |
299 | |
300 | Creates a QBitArray with the dense bit array located at \a data, with \a |
301 | size bits. The byte array at \a data must be at least \a size / 8 (rounded up) |
302 | bytes long. |
303 | |
304 | If \a size is not a multiple of 8, this function will include the lowest |
305 | \a size % 8 bits from the last byte in \a data. |
306 | |
307 | \sa bits() |
308 | */ |
309 | QBitArray QBitArray::fromBits(const char *data, qsizetype size) |
310 | { |
311 | Q_ASSERT_X(size >= 0, "QBitArray::fromBits", "Size must be greater than or equal to 0."); |
312 | QBitArray result; |
313 | if (size <= 0) |
314 | return result; |
315 | |
316 | auto &d = result.d; |
317 | d.resize(size: allocation_size(size)); |
318 | memcpy(dest: d.data() + 1, src: data, n: d.size() - 1); |
319 | adjust_head_and_tail(data: d.data(), storageSize: d.size(), logicalSize: size); |
320 | return result; |
321 | } |
322 | |
323 | /*! |
324 | \since 6.0 |
325 | |
326 | Returns the array of bit converted to an int. The conversion is based on \a endianness. |
327 | Converts up to the first 32 bits of the array to \c quint32 and returns it, |
328 | obeying \a endianness. If \a ok is not a null pointer, and the array has more |
329 | than 32 bits, \a ok is set to false and this function returns zero; otherwise, |
330 | it's set to true. |
331 | */ |
332 | quint32 QBitArray::toUInt32(QSysInfo::Endian endianness, bool *ok) const noexcept |
333 | { |
334 | const qsizetype _size = size(); |
335 | if (_size > 32) { |
336 | if (ok) |
337 | *ok = false; |
338 | return 0; |
339 | } |
340 | |
341 | if (ok) |
342 | *ok = true; |
343 | |
344 | quint32 factor = 1; |
345 | quint32 total = 0; |
346 | for (qsizetype i = 0; i < _size; ++i, factor *= 2) { |
347 | const auto index = endianness == QSysInfo::Endian::LittleEndian ? i : (_size - i - 1); |
348 | if (testBit(i: index)) |
349 | total += factor; |
350 | } |
351 | |
352 | return total; |
353 | } |
354 | |
355 | /*! \fn bool QBitArray::isDetached() const |
356 | |
357 | \internal |
358 | */ |
359 | |
360 | /*! \fn void QBitArray::detach() |
361 | |
362 | \internal |
363 | */ |
364 | |
365 | /*! \fn void QBitArray::clear() |
366 | |
367 | Clears the contents of the bit array and makes it empty. |
368 | |
369 | \sa resize(), isEmpty() |
370 | */ |
371 | |
372 | /*! \fn void QBitArray::truncate(qsizetype pos) |
373 | |
374 | Truncates the bit array at index position \a pos. |
375 | |
376 | If \a pos is beyond the end of the array, nothing happens. |
377 | |
378 | \sa resize() |
379 | */ |
380 | |
381 | /*! \fn bool QBitArray::toggleBit(qsizetype i) |
382 | |
383 | Inverts the value of the bit at index position \a i, returning the |
384 | previous value of that bit as either true (if it was set) or false (if |
385 | it was unset). |
386 | |
387 | If the previous value was 0, the new value will be 1. If the |
388 | previous value was 1, the new value will be 0. |
389 | |
390 | \a i must be a valid index position in the bit array (i.e., 0 <= |
391 | \a i < size()). |
392 | |
393 | \sa setBit(), clearBit() |
394 | */ |
395 | |
396 | /*! \fn bool QBitArray::testBit(qsizetype i) const |
397 | |
398 | Returns \c true if the bit at index position \a i is 1; otherwise |
399 | returns \c false. |
400 | |
401 | \a i must be a valid index position in the bit array (i.e., 0 <= |
402 | \a i < size()). |
403 | |
404 | \sa setBit(), clearBit() |
405 | */ |
406 | |
407 | /*! \fn bool QBitArray::setBit(qsizetype i) |
408 | |
409 | Sets the bit at index position \a i to 1. |
410 | |
411 | \a i must be a valid index position in the bit array (i.e., 0 <= |
412 | \a i < size()). |
413 | |
414 | \sa clearBit(), toggleBit() |
415 | */ |
416 | |
417 | /*! \fn void QBitArray::setBit(qsizetype i, bool value) |
418 | |
419 | \overload |
420 | |
421 | Sets the bit at index position \a i to \a value. |
422 | */ |
423 | |
424 | /*! \fn void QBitArray::clearBit(qsizetype i) |
425 | |
426 | Sets the bit at index position \a i to 0. |
427 | |
428 | \a i must be a valid index position in the bit array (i.e., 0 <= |
429 | \a i < size()). |
430 | |
431 | \sa setBit(), toggleBit() |
432 | */ |
433 | |
434 | /*! \fn bool QBitArray::at(qsizetype i) const |
435 | |
436 | Returns the value of the bit at index position \a i. |
437 | |
438 | \a i must be a valid index position in the bit array (i.e., 0 <= |
439 | \a i < size()). |
440 | |
441 | \sa operator[]() |
442 | */ |
443 | |
444 | /*! \fn QBitRef QBitArray::operator[](qsizetype i) |
445 | |
446 | Returns the bit at index position \a i as a modifiable reference. |
447 | |
448 | \a i must be a valid index position in the bit array (i.e., 0 <= |
449 | \a i < size()). |
450 | |
451 | Example: |
452 | \snippet code/src_corelib_tools_qbitarray.cpp 7 |
453 | |
454 | The return value is of type QBitRef, a helper class for QBitArray. |
455 | When you get an object of type QBitRef, you can assign to |
456 | it, and the assignment will apply to the bit in the QBitArray |
457 | from which you got the reference. |
458 | |
459 | The functions testBit(), setBit(), and clearBit() are slightly |
460 | faster. |
461 | |
462 | \sa at(), testBit(), setBit(), clearBit() |
463 | */ |
464 | |
465 | /*! \fn bool QBitArray::operator[](qsizetype i) const |
466 | |
467 | \overload |
468 | */ |
469 | |
470 | #if QT_VERSION < QT_VERSION_CHECK(7, 0, 0) |
471 | /*! \fn QBitArray::QBitArray(const QBitArray &other) noexcept |
472 | |
473 | Constructs a copy of \a other. |
474 | |
475 | This operation takes \l{constant time}, because QBitArray is |
476 | \l{implicitly shared}. This makes returning a QBitArray from a |
477 | function very fast. If a shared instance is modified, it will be |
478 | copied (copy-on-write), and that takes \l{linear time}. |
479 | |
480 | \sa operator=() |
481 | */ |
482 | |
483 | /*! \fn QBitArray &QBitArray::operator=(const QBitArray &other) noexcept |
484 | |
485 | Assigns \a other to this bit array and returns a reference to |
486 | this bit array. |
487 | */ |
488 | |
489 | /*! \fn QBitArray &QBitArray::operator=(QBitArray &&other) |
490 | \since 5.2 |
491 | |
492 | Moves \a other to this bit array and returns a reference to |
493 | this bit array. |
494 | */ |
495 | #endif // Qt 6 |
496 | |
497 | /*! \fn void QBitArray::swap(QBitArray &other) |
498 | \since 4.8 |
499 | |
500 | Swaps bit array \a other with this bit array. This operation is very |
501 | fast and never fails. |
502 | */ |
503 | |
504 | /*! \fn bool QBitArray::operator==(const QBitArray &lhs, const QBitArray &rhs) |
505 | |
506 | Returns \c true if \a lhs is equal to \a rhs bit array; otherwise |
507 | returns \c false. |
508 | |
509 | \sa operator!=() |
510 | */ |
511 | |
512 | /*! \fn bool QBitArray::operator!=(const QBitArray &lhs, const QBitArray &rhs) |
513 | |
514 | Returns \c true if \a lhs is not equal to \a rhs bit array; |
515 | otherwise returns \c false. |
516 | |
517 | \sa operator==() |
518 | */ |
519 | |
520 | // Returns a new QBitArray that has the same size as the bigger of \a a1 and |
521 | // \a a2, but whose contents are uninitialized. |
522 | static QBitArray sizedForOverwrite(const QBitArray &a1, const QBitArray &a2) |
523 | { |
524 | QBitArray result; |
525 | const QByteArrayData &d1 = a1.data_ptr(); |
526 | const QByteArrayData &d2 = a2.data_ptr(); |
527 | qsizetype n1 = d1.size; |
528 | qsizetype n2 = d2.size; |
529 | qsizetype n = qMax(a: n1, b: n2); |
530 | |
531 | QByteArrayData bytes(n, n); |
532 | |
533 | // initialize the count of bits in the last byte (see construction note) |
534 | // and the QByteArray null termination (some of our algorithms read it) |
535 | if (n1 > n2) { |
536 | *bytes.ptr = *d1.ptr; |
537 | bytes.ptr[n1] = 0; |
538 | } else if (n2 > n1) { |
539 | *bytes.ptr = *d2.ptr; |
540 | bytes.ptr[n2] = 0; |
541 | } else if (n1) { // n1 == n2 |
542 | *bytes.ptr = qMin(a: *d1.ptr, b: *d2.ptr); |
543 | bytes.ptr[n1] = 0; |
544 | } |
545 | |
546 | result.data_ptr() = std::move(bytes); |
547 | return result; |
548 | } |
549 | |
550 | template <typename BitwiseOp> static Q_NEVER_INLINE |
551 | QBitArray &performBitwiseOperationHelper(QBitArray &out, const QBitArray &a1, |
552 | const QBitArray &a2, BitwiseOp op) |
553 | { |
554 | const QByteArrayData &d1 = a1.data_ptr(); |
555 | const QByteArrayData &d2 = a2.data_ptr(); |
556 | |
557 | // Sizes in bytes (including the initial bit difference counter) |
558 | qsizetype n1 = d1.size; |
559 | qsizetype n2 = d2.size; |
560 | Q_ASSERT(out.data_ptr().size == qMax(n1, n2)); |
561 | Q_ASSERT(out.data_ptr().size == 0 || !out.data_ptr().needsDetach()); |
562 | |
563 | // Bypass QByteArray's emptiness verification; we won't dereference |
564 | // these pointers if their size is zero. |
565 | auto dst = reinterpret_cast<uchar *>(out.data_ptr().data()); |
566 | auto p1 = reinterpret_cast<const uchar *>(d1.data()); |
567 | auto p2 = reinterpret_cast<const uchar *>(d2.data()); |
568 | |
569 | // Main: perform the operation in the range where both arrays have data |
570 | if (n1 < n2) { |
571 | std::swap(a&: n1, b&: n2); |
572 | std::swap(a&: p1, b&: p2); |
573 | } |
574 | for (qsizetype i = 1; i < n2; ++i) |
575 | dst[i] = op(p1[i], p2[i]); |
576 | |
577 | // Tail: operate as if both arrays had the same data by padding zeroes to |
578 | // the end of the shorter of the two (for std::bit_or and std::bit_xor, this is |
579 | // a memmove; for std::bit_and, it's memset to 0). |
580 | for (qsizetype i = qMax(a: n2, b: qsizetype(1)); i < n1; ++i) |
581 | dst[i] = op(p1[i], uchar(0)); |
582 | |
583 | return out; |
584 | } |
585 | |
586 | template <typename BitwiseOp> static Q_NEVER_INLINE |
587 | QBitArray &performBitwiseOperationInCopy(QBitArray &self, const QBitArray &other, BitwiseOp op) |
588 | { |
589 | QBitArray tmp(std::move(self)); |
590 | self = sizedForOverwrite(a1: tmp, a2: other); |
591 | return performBitwiseOperationHelper(self, tmp, other, op); |
592 | } |
593 | |
594 | template <typename BitwiseOp> static Q_NEVER_INLINE |
595 | QBitArray &performBitwiseOperationInPlace(QBitArray &self, const QBitArray &other, BitwiseOp op) |
596 | { |
597 | if (self.size() < other.size()) |
598 | self.resize(size: other.size()); |
599 | return performBitwiseOperationHelper(self, self, other, op); |
600 | } |
601 | |
602 | template <typename BitwiseOp> static |
603 | QBitArray &performBitwiseOperation(QBitArray &self, const QBitArray &other, BitwiseOp op) |
604 | { |
605 | if (self.data_ptr().needsDetach()) |
606 | return performBitwiseOperationInCopy(self, other, op); |
607 | return performBitwiseOperationInPlace(self, other, op); |
608 | } |
609 | |
610 | // SCARY helper |
611 | enum { InCopy, InPlace }; |
612 | static auto prepareForBitwiseOperation(QBitArray &self, QBitArray &other) |
613 | { |
614 | QByteArrayData &d1 = self.data_ptr(); |
615 | QByteArrayData &d2 = other.data_ptr(); |
616 | bool detached1 = !d1.needsDetach(); |
617 | bool detached2 = !d2.needsDetach(); |
618 | if (!detached1 && !detached2) |
619 | return InCopy; |
620 | |
621 | // at least one of the two is detached, we'll reuse its buffer |
622 | bool swap = false; |
623 | if (detached1 && detached2) { |
624 | // both are detached, so choose the larger of the two |
625 | swap = d1.allocatedCapacity() < d2.allocatedCapacity(); |
626 | } else if (detached2) { |
627 | // we can re-use other's buffer but not self's, so swap the two |
628 | swap = true; |
629 | } |
630 | if (swap) |
631 | self.swap(other); |
632 | return InPlace; |
633 | } |
634 | |
635 | template <typename BitwiseOp> static |
636 | QBitArray &performBitwiseOperation(QBitArray &self, QBitArray &other, BitwiseOp op) |
637 | { |
638 | auto choice = prepareForBitwiseOperation(self, other); |
639 | if (choice == InCopy) |
640 | return performBitwiseOperationInCopy(self, other, std::move(op)); |
641 | return performBitwiseOperationInPlace(self, other, std::move(op)); |
642 | } |
643 | |
644 | /*! |
645 | \fn QBitArray &QBitArray::operator&=(const QBitArray &other) |
646 | \fn QBitArray &QBitArray::operator&=(QBitArray &&other) |
647 | |
648 | Performs the AND operation between all bits in this bit array and |
649 | \a other. Assigns the result to this bit array, and returns a |
650 | reference to it. |
651 | |
652 | The result has the length of the longest of the two bit arrays, |
653 | with any missing bits (if one array is shorter than the other) |
654 | taken to be 0. |
655 | |
656 | Example: |
657 | \snippet code/src_corelib_tools_qbitarray.cpp 8 |
658 | |
659 | \sa operator&(), operator|=(), operator^=(), operator~() |
660 | */ |
661 | |
662 | QBitArray &QBitArray::operator&=(QBitArray &&other) |
663 | { |
664 | return performBitwiseOperation(self&: *this, other, op: std::bit_and<uchar>()); |
665 | } |
666 | |
667 | QBitArray &QBitArray::operator&=(const QBitArray &other) |
668 | { |
669 | return performBitwiseOperation(self&: *this, other, op: std::bit_and<uchar>()); |
670 | } |
671 | |
672 | /*! |
673 | \fn QBitArray &QBitArray::operator|=(const QBitArray &other) |
674 | \fn QBitArray &QBitArray::operator|=(QBitArray &&other) |
675 | |
676 | Performs the OR operation between all bits in this bit array and |
677 | \a other. Assigns the result to this bit array, and returns a |
678 | reference to it. |
679 | |
680 | The result has the length of the longest of the two bit arrays, |
681 | with any missing bits (if one array is shorter than the other) |
682 | taken to be 0. |
683 | |
684 | Example: |
685 | \snippet code/src_corelib_tools_qbitarray.cpp 9 |
686 | |
687 | \sa operator|(), operator&=(), operator^=(), operator~() |
688 | */ |
689 | |
690 | QBitArray &QBitArray::operator|=(QBitArray &&other) |
691 | { |
692 | return performBitwiseOperation(self&: *this, other, op: std::bit_or<uchar>()); |
693 | } |
694 | |
695 | QBitArray &QBitArray::operator|=(const QBitArray &other) |
696 | { |
697 | return performBitwiseOperation(self&: *this, other, op: std::bit_or<uchar>()); |
698 | } |
699 | |
700 | /*! |
701 | \fn QBitArray &QBitArray::operator^=(const QBitArray &other) |
702 | \fn QBitArray &QBitArray::operator^=(QBitArray &&other) |
703 | |
704 | Performs the XOR operation between all bits in this bit array and |
705 | \a other. Assigns the result to this bit array, and returns a |
706 | reference to it. |
707 | |
708 | The result has the length of the longest of the two bit arrays, |
709 | with any missing bits (if one array is shorter than the other) |
710 | taken to be 0. |
711 | |
712 | Example: |
713 | \snippet code/src_corelib_tools_qbitarray.cpp 10 |
714 | |
715 | \sa operator^(), operator&=(), operator|=(), operator~() |
716 | */ |
717 | |
718 | QBitArray &QBitArray::operator^=(QBitArray &&other) |
719 | { |
720 | return performBitwiseOperation(self&: *this, other, op: std::bit_xor<uchar>()); |
721 | } |
722 | |
723 | QBitArray &QBitArray::operator^=(const QBitArray &other) |
724 | { |
725 | return performBitwiseOperation(self&: *this, other, op: std::bit_xor<uchar>()); |
726 | } |
727 | |
728 | /*! |
729 | \fn QBitArray QBitArray::operator~(QBitArray a) |
730 | Returns a bit array that contains the inverted bits of the bit |
731 | array \a a. |
732 | |
733 | Example: |
734 | \snippet code/src_corelib_tools_qbitarray.cpp 11 |
735 | |
736 | \sa operator&(), operator|(), operator^() |
737 | */ |
738 | |
739 | Q_NEVER_INLINE QBitArray QBitArray::inverted_inplace() && |
740 | { |
741 | qsizetype n = d.size(); |
742 | uchar *dst = reinterpret_cast<uchar *>(data_ptr().data()); |
743 | const uchar *src = dst; |
744 | QBitArray result([&] { |
745 | if (d.isDetached() || n == 0) |
746 | return std::move(d.data_ptr()); // invert in-place |
747 | |
748 | QByteArrayData tmp(n, n); |
749 | dst = reinterpret_cast<uchar *>(tmp.data()); |
750 | return tmp; |
751 | }()); |
752 | |
753 | uchar bitdiff = 8; |
754 | if (n) |
755 | bitdiff = dst[0] = src[0]; // copy the count of bits in the last byte |
756 | |
757 | for (qsizetype i = 1; i < n; ++i) |
758 | dst[i] = ~src[i]; |
759 | |
760 | if (int tailCount = 16 - bitdiff; tailCount != 8) { |
761 | // zero the bits beyond our size in the last byte |
762 | Q_ASSERT(n > 1); |
763 | uchar tailMask = (1U << tailCount) - 1; |
764 | dst[n - 1] &= tailMask; |
765 | } |
766 | |
767 | return result; |
768 | } |
769 | |
770 | /*! |
771 | \fn QBitArray QBitArray::operator&(const QBitArray &a1, const QBitArray &a2) |
772 | \fn QBitArray QBitArray::operator&(QBitArray &&a1, const QBitArray &a2) |
773 | \fn QBitArray QBitArray::operator&(const QBitArray &a1, QBitArray &&a2) |
774 | \fn QBitArray QBitArray::operator&(QBitArray &&a1, QBitArray &&a2) |
775 | |
776 | Returns a bit array that is the AND of the bit arrays \a a1 and \a |
777 | a2. |
778 | |
779 | The result has the length of the longest of the two bit arrays, |
780 | with any missing bits (if one array is shorter than the other) |
781 | taken to be 0. |
782 | |
783 | Example: |
784 | \snippet code/src_corelib_tools_qbitarray.cpp 12 |
785 | |
786 | \sa {QBitArray::}{operator&=()}, {QBitArray::}{operator|()}, {QBitArray::}{operator^()} |
787 | */ |
788 | |
789 | QBitArray operator&(const QBitArray &a1, const QBitArray &a2) |
790 | { |
791 | QBitArray tmp = sizedForOverwrite(a1, a2); |
792 | performBitwiseOperationHelper(out&: tmp, a1, a2, op: std::bit_and<uchar>()); |
793 | return tmp; |
794 | } |
795 | |
796 | /*! |
797 | \fn QBitArray QBitArray::operator|(const QBitArray &a1, const QBitArray &a2) |
798 | \fn QBitArray QBitArray::operator|(QBitArray &&a1, const QBitArray &a2) |
799 | \fn QBitArray QBitArray::operator|(const QBitArray &a1, QBitArray &&a2) |
800 | \fn QBitArray QBitArray::operator|(QBitArray &&a1, QBitArray &&a2) |
801 | |
802 | Returns a bit array that is the OR of the bit arrays \a a1 and \a |
803 | a2. |
804 | |
805 | The result has the length of the longest of the two bit arrays, |
806 | with any missing bits (if one array is shorter than the other) |
807 | taken to be 0. |
808 | |
809 | Example: |
810 | \snippet code/src_corelib_tools_qbitarray.cpp 13 |
811 | |
812 | \sa QBitArray::operator|=(), operator&(), operator^() |
813 | */ |
814 | |
815 | QBitArray operator|(const QBitArray &a1, const QBitArray &a2) |
816 | { |
817 | QBitArray tmp = sizedForOverwrite(a1, a2); |
818 | performBitwiseOperationHelper(out&: tmp, a1, a2, op: std::bit_or<uchar>()); |
819 | return tmp; |
820 | } |
821 | |
822 | /*! |
823 | \fn QBitArray QBitArray::operator^(const QBitArray &a1, const QBitArray &a2) |
824 | \fn QBitArray QBitArray::operator^(QBitArray &&a1, const QBitArray &a2) |
825 | \fn QBitArray QBitArray::operator^(const QBitArray &a1, QBitArray &&a2) |
826 | \fn QBitArray QBitArray::operator^(QBitArray &&a1, QBitArray &&a2) |
827 | |
828 | Returns a bit array that is the XOR of the bit arrays \a a1 and \a |
829 | a2. |
830 | |
831 | The result has the length of the longest of the two bit arrays, |
832 | with any missing bits (if one array is shorter than the other) |
833 | taken to be 0. |
834 | |
835 | Example: |
836 | \snippet code/src_corelib_tools_qbitarray.cpp 14 |
837 | |
838 | \sa {QBitArray}{operator^=()}, {QBitArray}{operator&()}, {QBitArray}{operator|()} |
839 | */ |
840 | |
841 | QBitArray operator^(const QBitArray &a1, const QBitArray &a2) |
842 | { |
843 | QBitArray tmp = sizedForOverwrite(a1, a2); |
844 | performBitwiseOperationHelper(out&: tmp, a1, a2, op: std::bit_xor<uchar>()); |
845 | return tmp; |
846 | } |
847 | |
848 | /*! |
849 | \class QBitRef |
850 | \inmodule QtCore |
851 | \reentrant |
852 | \brief The QBitRef class is an internal class, used with QBitArray. |
853 | |
854 | \internal |
855 | |
856 | The QBitRef is required by the indexing [] operator on bit arrays. |
857 | It is not for use in any other context. |
858 | */ |
859 | |
860 | /*! \fn QBitRef::QBitRef (QBitArray& a, qsizetype i) |
861 | |
862 | Constructs a reference to element \a i in the QBitArray \a a. |
863 | This is what QBitArray::operator[] constructs its return value |
864 | with. |
865 | */ |
866 | |
867 | /*! \fn QBitRef::operator bool() const |
868 | |
869 | Returns the value referenced by the QBitRef. |
870 | */ |
871 | |
872 | /*! \fn bool QBitRef::operator!() const |
873 | |
874 | \internal |
875 | */ |
876 | |
877 | /*! \fn QBitRef& QBitRef::operator= (const QBitRef& v) |
878 | |
879 | Sets the value referenced by the QBitRef to that referenced by |
880 | QBitRef \a v. |
881 | */ |
882 | |
883 | /*! \fn QBitRef& QBitRef::operator= (bool v) |
884 | \overload |
885 | |
886 | Sets the value referenced by the QBitRef to \a v. |
887 | */ |
888 | |
889 | /***************************************************************************** |
890 | QBitArray stream functions |
891 | *****************************************************************************/ |
892 | |
893 | #ifndef QT_NO_DATASTREAM |
894 | /*! |
895 | \relates QBitArray |
896 | |
897 | Writes bit array \a ba to stream \a out. |
898 | |
899 | \sa {Serializing Qt Data Types}{Format of the QDataStream operators} |
900 | */ |
901 | |
902 | QDataStream &operator<<(QDataStream &out, const QBitArray &ba) |
903 | { |
904 | const qsizetype len = ba.size(); |
905 | if (out.version() < QDataStream::Qt_6_0) { |
906 | if (Q_UNLIKELY(len > qsizetype{(std::numeric_limits<qint32>::max)()})) { |
907 | out.setStatus(QDataStream::Status::SizeLimitExceeded); |
908 | return out; |
909 | } |
910 | out << quint32(len); |
911 | } else { |
912 | out << quint64(len); |
913 | } |
914 | if (len > 0) |
915 | out.writeRawData(ba.d.data() + 1, len: ba.d.size() - 1); |
916 | return out; |
917 | } |
918 | |
919 | /*! |
920 | \relates QBitArray |
921 | |
922 | Reads a bit array into \a ba from stream \a in. |
923 | |
924 | \sa {Serializing Qt Data Types}{Format of the QDataStream operators} |
925 | */ |
926 | |
927 | QDataStream &operator>>(QDataStream &in, QBitArray &ba) |
928 | { |
929 | ba.clear(); |
930 | qsizetype len; |
931 | if (in.version() < QDataStream::Qt_6_0) { |
932 | quint32 tmp; |
933 | in >> tmp; |
934 | if (Q_UNLIKELY(tmp > quint32((std::numeric_limits<qint32>::max)()))) { |
935 | in.setStatus(QDataStream::ReadCorruptData); |
936 | return in; |
937 | } |
938 | len = tmp; |
939 | } else { |
940 | quint64 tmp; |
941 | in >> tmp; |
942 | if (Q_UNLIKELY(tmp > quint64((std::numeric_limits<qsizetype>::max)()))) { |
943 | in.setStatus(QDataStream::Status::SizeLimitExceeded); |
944 | return in; |
945 | } |
946 | len = tmp; |
947 | } |
948 | if (len == 0) { |
949 | ba.clear(); |
950 | return in; |
951 | } |
952 | |
953 | const qsizetype Step = 8 * 1024 * 1024; |
954 | const qsizetype totalBytes = storage_size(size: len); |
955 | qsizetype allocated = 0; |
956 | |
957 | while (allocated < totalBytes) { |
958 | qsizetype blockSize = qMin(a: Step, b: totalBytes - allocated); |
959 | ba.d.resize(size: allocated + blockSize + 1); |
960 | if (in.readRawData(ba.d.data() + 1 + allocated, len: blockSize) != blockSize) { |
961 | ba.clear(); |
962 | in.setStatus(QDataStream::ReadPastEnd); |
963 | return in; |
964 | } |
965 | allocated += blockSize; |
966 | } |
967 | |
968 | const auto fromStream = ba.d.back(); |
969 | adjust_head_and_tail(data: ba.d.data(), storageSize: ba.d.size(), logicalSize: len); |
970 | if (ba.d.back() != fromStream) { |
971 | ba.clear(); |
972 | in.setStatus(QDataStream::ReadCorruptData); |
973 | return in; |
974 | } |
975 | return in; |
976 | } |
977 | #endif // QT_NO_DATASTREAM |
978 | |
979 | #ifndef QT_NO_DEBUG_STREAM |
980 | QDebug operator<<(QDebug dbg, const QBitArray &array) |
981 | { |
982 | QDebugStateSaver saver(dbg); |
983 | dbg.nospace() << "QBitArray("; |
984 | for (qsizetype i = 0; i < array.size();) { |
985 | if (array.testBit(i)) |
986 | dbg << '1'; |
987 | else |
988 | dbg << '0'; |
989 | i += 1; |
990 | if (!(i % 4) && (i < array.size())) |
991 | dbg << ' '; |
992 | } |
993 | dbg << ')'; |
994 | return dbg; |
995 | } |
996 | #endif |
997 | |
998 | /*! |
999 | \fn DataPtr &QBitArray::data_ptr() |
1000 | \internal |
1001 | */ |
1002 | |
1003 | /*! |
1004 | \typedef QBitArray::DataPtr |
1005 | \internal |
1006 | */ |
1007 | |
1008 | QT_END_NAMESPACE |
1009 |
Definitions
- storage_size
- allocation_size
- adjust_head_and_tail
- QBitArray
- count
- resize
- fill
- fromBits
- toUInt32
- sizedForOverwrite
- performBitwiseOperationHelper
- performBitwiseOperationInCopy
- performBitwiseOperationInPlace
- performBitwiseOperation
- prepareForBitwiseOperation
- performBitwiseOperation
- operator&=
- operator&=
- operator|=
- operator|=
- operator^=
- operator^=
- inverted_inplace
- operator&
- operator|
- operator^
- operator<<
- operator>>
Start learning QML with our Intro Training
Find out more