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) bits(size,value)69 : bits(size, value) 70 {} 71 clear()72 void clear() 73 { bits = std::vector<bool>(bits.size(), false); } 74 reserve(int size)75 void reserve(int size) 76 { bits.reserve(size); } 77 size()78 int size() const 79 { 80 Q_ASSERT(bits.size() < INT_MAX); 81 return static_cast<int>(bits.size()); 82 } 83 resize(int newSize)84 void resize(int newSize) 85 { bits.resize(newSize); } 86 resize(int newSize,bool newValue)87 void resize(int newSize, bool newValue) 88 { bits.resize(newSize, newValue); } 89 assign(int newSize,bool value)90 void assign(int newSize, bool value) 91 { bits.assign(newSize, value); } 92 findNext(int start,bool value,bool wrapAround)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(bits.begin(), 106 std::find(bits.begin() + start, bits.end(), value)); 107 if (wrapAround && pos >= static_cast<size_t>(size())) 108 pos = std::distance(bits.begin(), 109 std::find(bits.begin(), bits.begin() + start, value)); 110 111 pos = qMin(pos, 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 at(int idx)119 bool at(int idx) const 120 { return bits.at(idx); } 121 setBit(int idx)122 void setBit(int idx) 123 { bits[idx] = true; } 124 clearBit(int idx)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