1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtQml 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 The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/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 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or (at your option) the GNU General |
28 | ** Public license version 3 or any later version approved by the KDE Free |
29 | ** Qt Foundation. The licenses are as published by the Free Software |
30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
31 | ** included in the packaging of this file. Please review the following |
32 | ** information to ensure the GNU General Public License requirements will |
33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
35 | ** |
36 | ** $QT_END_LICENSE$ |
37 | ** |
38 | ****************************************************************************/ |
39 | #ifndef QV4UTIL_H |
40 | #define QV4UTIL_H |
41 | |
42 | // |
43 | // W A R N I N G |
44 | // ------------- |
45 | // |
46 | // This file is not part of the Qt API. It exists purely as an |
47 | // implementation detail. This header file may change from version to |
48 | // version without notice, or even be removed. |
49 | // |
50 | // We mean it. |
51 | // |
52 | |
53 | #include <QtCore/QBitArray> |
54 | #include <algorithm> |
55 | #include <vector> |
56 | |
57 | QT_BEGIN_NAMESPACE |
58 | |
59 | namespace QV4 { |
60 | |
61 | #if !defined(BROKEN_STD_VECTOR_BOOL_OR_BROKEN_STD_FIND) |
62 | // Sanity: |
63 | class BitVector |
64 | { |
65 | std::vector<bool> bits; |
66 | |
67 | public: |
68 | BitVector(int size = 0, bool value = false) |
69 | : bits(size, value) |
70 | {} |
71 | |
72 | void clear() |
73 | { bits = std::vector<bool>(bits.size(), false); } |
74 | |
75 | void reserve(int size) |
76 | { bits.reserve(n: size); } |
77 | |
78 | int size() const |
79 | { |
80 | Q_ASSERT(bits.size() < INT_MAX); |
81 | return static_cast<int>(bits.size()); |
82 | } |
83 | |
84 | void resize(int newSize) |
85 | { bits.resize(new_size: newSize); } |
86 | |
87 | void resize(int newSize, bool newValue) |
88 | { bits.resize(new_size: newSize, x: newValue); } |
89 | |
90 | void assign(int newSize, bool value) |
91 | { bits.assign(n: newSize, x: value); } |
92 | |
93 | int findNext(int start, bool value, bool wrapAround) const |
94 | { |
95 | // The ++operator of std::vector<bool>::iterator in libc++ has a bug when using it on an |
96 | // iterator pointing to the last element. It will not be set to ::end(), but beyond |
97 | // that. (It will be set to the first multiple of the native word size that is bigger |
98 | // than size().) |
99 | // |
100 | // See http://llvm.org/bugs/show_bug.cgi?id=19663 |
101 | // |
102 | // The work-around is to calculate the distance, and compare it to the size() to see if it's |
103 | // beyond the end, or take the minimum of the distance and the size. |
104 | |
105 | size_t pos = std::distance(first: bits.begin(), |
106 | last: std::find(first: bits.begin() + start, last: bits.end(), val: value)); |
107 | if (wrapAround && pos >= static_cast<size_t>(size())) |
108 | pos = std::distance(first: bits.begin(), |
109 | last: std::find(first: bits.begin(), last: bits.begin() + start, val: value)); |
110 | |
111 | pos = qMin(a: pos, b: static_cast<size_t>(size())); |
112 | |
113 | Q_ASSERT(pos <= static_cast<size_t>(size())); |
114 | Q_ASSERT(pos < INT_MAX); |
115 | |
116 | return static_cast<int>(pos); |
117 | } |
118 | |
119 | bool at(int idx) const |
120 | { return bits.at(n: idx); } |
121 | |
122 | void setBit(int idx) |
123 | { bits[idx] = true; } |
124 | |
125 | void clearBit(int idx) |
126 | { bits[idx] = false; } |
127 | }; |
128 | #else // Insanity: |
129 | class BitVector |
130 | { |
131 | QBitArray bits; |
132 | |
133 | public: |
134 | BitVector(int size = 0, bool value = false) |
135 | : bits(size, value) |
136 | {} |
137 | |
138 | void clear() |
139 | { bits = QBitArray(bits.size(), false); } |
140 | |
141 | void reserve(int size) |
142 | { Q_UNUSED(size); } |
143 | |
144 | int size() const |
145 | { return bits.size(); } |
146 | |
147 | void resize(int newSize) |
148 | { bits.resize(newSize); } |
149 | |
150 | void resize(int newSize, bool newValue) |
151 | { |
152 | int oldSize = bits.size(); |
153 | bits.resize(newSize); |
154 | bits.fill(newValue, oldSize, bits.size()); |
155 | } |
156 | |
157 | void assign(int newSize, bool value) |
158 | { |
159 | bits.resize(newSize); |
160 | bits.fill(value); |
161 | } |
162 | |
163 | int findNext(int start, bool value, bool wrapAround) const |
164 | { |
165 | for (int i = start, ei = size(); i < ei; ++i) { |
166 | if (at(i) == value) |
167 | return i; |
168 | } |
169 | |
170 | if (wrapAround) { |
171 | for (int i = 0, ei = start; i < ei; ++i) { |
172 | if (at(i) == value) |
173 | return i; |
174 | } |
175 | } |
176 | |
177 | return size(); |
178 | } |
179 | |
180 | bool at(int idx) const |
181 | { return bits.at(idx); } |
182 | |
183 | void setBit(int idx) |
184 | { bits[idx] = true; } |
185 | |
186 | void clearBit(int idx) |
187 | { bits[idx] = false; } |
188 | }; |
189 | #endif |
190 | |
191 | } |
192 | |
193 | QT_END_NAMESPACE |
194 | |
195 | #endif // QV4UTIL_H |
196 | |