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
15QT_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
114static 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
120static constexpr qsizetype allocation_size(qsizetype size)
121{
122 return size <= 0 ? 0 : storage_size(size) + 1;
123}
124
125static 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*/
139QBitArray::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*/
166qsizetype 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*/
208void 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
271void 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 */
309QBitArray 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*/
332quint32 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.
522static 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
550template <typename BitwiseOp> static Q_NEVER_INLINE
551QBitArray &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
586template <typename BitwiseOp> static Q_NEVER_INLINE
587QBitArray &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
594template <typename BitwiseOp> static Q_NEVER_INLINE
595QBitArray &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
602template <typename BitwiseOp> static
603QBitArray &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
611enum { InCopy, InPlace };
612static 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
635template <typename BitwiseOp> static
636QBitArray &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
662QBitArray &QBitArray::operator&=(QBitArray &&other)
663{
664 return performBitwiseOperation(self&: *this, other, op: std::bit_and<uchar>());
665}
666
667QBitArray &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
690QBitArray &QBitArray::operator|=(QBitArray &&other)
691{
692 return performBitwiseOperation(self&: *this, other, op: std::bit_or<uchar>());
693}
694
695QBitArray &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
718QBitArray &QBitArray::operator^=(QBitArray &&other)
719{
720 return performBitwiseOperation(self&: *this, other, op: std::bit_xor<uchar>());
721}
722
723QBitArray &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
739Q_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
789QBitArray 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
815QBitArray 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
841QBitArray 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
902QDataStream &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
927QDataStream &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
980QDebug 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
1008QT_END_NAMESPACE
1009

Provided by KDAB

Privacy Policy
Start learning QML with our Intro Training
Find out more

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