1 | // Copyright (C) 2019 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | #ifndef QV4UTIL_H |
4 | #define QV4UTIL_H |
5 | |
6 | // |
7 | // W A R N I N G |
8 | // ------------- |
9 | // |
10 | // This file is not part of the Qt API. It exists purely as an |
11 | // implementation detail. This header file may change from version to |
12 | // version without notice, or even be removed. |
13 | // |
14 | // We mean it. |
15 | // |
16 | |
17 | #include <QtCore/QBitArray> |
18 | #include <QtCore/private/qglobal_p.h> |
19 | #include <algorithm> |
20 | #include <vector> |
21 | |
22 | QT_BEGIN_NAMESPACE |
23 | |
24 | namespace QV4 { |
25 | |
26 | #if !defined(BROKEN_STD_VECTOR_BOOL_OR_BROKEN_STD_FIND) |
27 | // Sanity: |
28 | class BitVector |
29 | { |
30 | std::vector<bool> bits; |
31 | |
32 | public: |
33 | BitVector(int size = 0, bool value = false) |
34 | : bits(size, value) |
35 | {} |
36 | |
37 | void clear() |
38 | { bits = std::vector<bool>(bits.size(), false); } |
39 | |
40 | void reserve(int size) |
41 | { bits.reserve(n: size); } |
42 | |
43 | int size() const |
44 | { |
45 | Q_ASSERT(bits.size() < INT_MAX); |
46 | return static_cast<int>(bits.size()); |
47 | } |
48 | |
49 | void resize(int newSize) |
50 | { bits.resize(new_size: newSize); } |
51 | |
52 | void resize(int newSize, bool newValue) |
53 | { bits.resize(new_size: newSize, x: newValue); } |
54 | |
55 | void assign(int newSize, bool value) |
56 | { bits.assign(n: newSize, x: value); } |
57 | |
58 | int findNext(int start, bool value, bool wrapAround) const |
59 | { |
60 | // The ++operator of std::vector<bool>::iterator in libc++ has a bug when using it on an |
61 | // iterator pointing to the last element. It will not be set to ::end(), but beyond |
62 | // that. (It will be set to the first multiple of the native word size that is bigger |
63 | // than size().) |
64 | // |
65 | // See http://llvm.org/bugs/show_bug.cgi?id=19663 |
66 | // |
67 | // The work-around is to calculate the distance, and compare it to the size() to see if it's |
68 | // beyond the end, or take the minimum of the distance and the size. |
69 | |
70 | size_t pos = std::distance(first: bits.begin(), |
71 | last: std::find(first: bits.begin() + start, last: bits.end(), val: value)); |
72 | if (wrapAround && pos >= static_cast<size_t>(size())) |
73 | pos = std::distance(first: bits.begin(), |
74 | last: std::find(first: bits.begin(), last: bits.begin() + start, val: value)); |
75 | |
76 | pos = qMin(a: pos, b: static_cast<size_t>(size())); |
77 | |
78 | Q_ASSERT(pos <= static_cast<size_t>(size())); |
79 | Q_ASSERT(pos < INT_MAX); |
80 | |
81 | return static_cast<int>(pos); |
82 | } |
83 | |
84 | bool at(int idx) const |
85 | { return bits.at(n: idx); } |
86 | |
87 | void setBit(int idx) |
88 | { bits[idx] = true; } |
89 | |
90 | void clearBit(int idx) |
91 | { bits[idx] = false; } |
92 | }; |
93 | #else // Insanity: |
94 | class BitVector |
95 | { |
96 | QBitArray bits; |
97 | |
98 | public: |
99 | BitVector(int size = 0, bool value = false) |
100 | : bits(size, value) |
101 | {} |
102 | |
103 | void clear() |
104 | { bits = QBitArray(bits.size(), false); } |
105 | |
106 | void reserve(int size) |
107 | { Q_UNUSED(size); } |
108 | |
109 | int size() const |
110 | { return bits.size(); } |
111 | |
112 | void resize(int newSize) |
113 | { bits.resize(newSize); } |
114 | |
115 | void resize(int newSize, bool newValue) |
116 | { |
117 | int oldSize = bits.size(); |
118 | bits.resize(newSize); |
119 | bits.fill(newValue, oldSize, bits.size()); |
120 | } |
121 | |
122 | void assign(int newSize, bool value) |
123 | { |
124 | bits.resize(newSize); |
125 | bits.fill(value); |
126 | } |
127 | |
128 | int findNext(int start, bool value, bool wrapAround) const |
129 | { |
130 | for (int i = start, ei = size(); i < ei; ++i) { |
131 | if (at(i) == value) |
132 | return i; |
133 | } |
134 | |
135 | if (wrapAround) { |
136 | for (int i = 0, ei = start; i < ei; ++i) { |
137 | if (at(i) == value) |
138 | return i; |
139 | } |
140 | } |
141 | |
142 | return size(); |
143 | } |
144 | |
145 | bool at(int idx) const |
146 | { return bits.at(idx); } |
147 | |
148 | void setBit(int idx) |
149 | { bits[idx] = true; } |
150 | |
151 | void clearBit(int idx) |
152 | { bits[idx] = false; } |
153 | }; |
154 | #endif |
155 | |
156 | } |
157 | |
158 | QT_END_NAMESPACE |
159 | |
160 | #endif // QV4UTIL_H |
161 | |