1 /* 2 * DQt - D bindings for the Qt Toolkit 3 * 4 * GNU Lesser General Public License Usage 5 * This file may be used under the terms of the GNU Lesser 6 * General Public License version 3 as published by the Free Software 7 * Foundation and appearing in the file LICENSE.LGPL3 included in the 8 * packaging of this file. Please review the following information to 9 * ensure the GNU Lesser General Public License version 3 requirements 10 * will be met: https://www.gnu.org/licenses/lgpl-3.0.html. 11 */ 12 module qt.core.algorithms; 13 extern(C++): 14 15 import core.bitop; 16 import core.stdc.config; 17 import qt.config; 18 import qt.core.global; 19 import qt.helpers; 20 import std.traits; 21 22 extern(D) private Signed!T signed(T)(T val) 23 { 24 return Signed!T(val); 25 } 26 27 /+ #if __has_include(<bit>) && __cplusplus > 201703L 28 #endif 29 30 #ifdef Q_CC_MSVC 31 #endif +/ 32 33 34 extern(D) void qDeleteAll(ForwardIterator)(ForwardIterator begin, ForwardIterator end) 35 { 36 import core.stdcpp.new_; 37 38 while (begin != end) { 39 cpp_delete(*begin); 40 ++begin; 41 } 42 } 43 44 pragma(inline, true) void qDeleteAll(Container)(ref Container c) 45 { 46 qDeleteAll(c.begin(), c.end()); 47 } 48 49 /* 50 Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API 51 and may be changed from version to version or even be completely removed. 52 */ 53 /+ namespace QAlgorithmsPrivate { 54 55 #ifdef Q_CC_CLANG 56 // Clang had a bug where __builtin_ctz/clz/popcount were not marked as constexpr. 57 # if (defined __apple_build_version__ && __clang_major__ >= 7) || (Q_CC_CLANG >= 307) 58 # define QT_HAS_CONSTEXPR_BUILTINS 59 # endif 60 #elif defined(Q_CC_MSVC) && !defined(Q_CC_INTEL) && !defined(Q_PROCESSOR_ARM) 61 # define QT_HAS_CONSTEXPR_BUILTINS 62 #elif defined(Q_CC_GNU) 63 # define QT_HAS_CONSTEXPR_BUILTINS 64 #endif 65 66 #if defined QT_HAS_CONSTEXPR_BUILTINS 67 #if defined(Q_CC_GNU) || defined(Q_CC_CLANG) 68 # define QT_HAS_BUILTIN_CTZS 69 constexpr Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept 70 { 71 # if __has_builtin(__builtin_ctzs) 72 return __builtin_ctzs(v); 73 # else 74 return __builtin_ctz(v); 75 # endif 76 } 77 #define QT_HAS_BUILTIN_CLZS 78 constexpr Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept 79 { 80 # if __has_builtin(__builtin_clzs) 81 return __builtin_clzs(v); 82 # else 83 return __builtin_clz(v) - 16U; 84 # endif 85 } 86 #define QT_HAS_BUILTIN_CTZ 87 constexpr Q_ALWAYS_INLINE uint qt_builtin_ctz(quint32 v) noexcept 88 { 89 return __builtin_ctz(v); 90 } 91 #define QT_HAS_BUILTIN_CLZ 92 constexpr Q_ALWAYS_INLINE uint qt_builtin_clz(quint32 v) noexcept 93 { 94 return __builtin_clz(v); 95 } 96 #define QT_HAS_BUILTIN_CTZLL 97 constexpr Q_ALWAYS_INLINE uint qt_builtin_ctzll(quint64 v) noexcept 98 { 99 return __builtin_ctzll(v); 100 } 101 #define QT_HAS_BUILTIN_CLZLL 102 constexpr Q_ALWAYS_INLINE uint qt_builtin_clzll(quint64 v) noexcept 103 { 104 return __builtin_clzll(v); 105 } 106 #define QALGORITHMS_USE_BUILTIN_POPCOUNT 107 constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint32 v) noexcept 108 { 109 return __builtin_popcount(v); 110 } 111 constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint8 v) noexcept 112 { 113 return __builtin_popcount(v); 114 } 115 constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint16 v) noexcept 116 { 117 return __builtin_popcount(v); 118 } 119 #define QALGORITHMS_USE_BUILTIN_POPCOUNTLL 120 constexpr Q_ALWAYS_INLINE uint qt_builtin_popcountll(quint64 v) noexcept 121 { 122 return __builtin_popcountll(v); 123 } 124 #elif defined(Q_CC_MSVC) && !defined(Q_PROCESSOR_ARM) 125 #define QT_HAS_BUILTIN_CTZ 126 Q_ALWAYS_INLINE unsigned long qt_builtin_ctz(quint32 val) 127 { 128 unsigned long result; 129 _BitScanForward(&result, val); 130 return result; 131 } 132 #define QT_HAS_BUILTIN_CLZ 133 Q_ALWAYS_INLINE unsigned long qt_builtin_clz(quint32 val) 134 { 135 unsigned long result; 136 _BitScanReverse(&result, val); 137 // Now Invert the result: clz will count *down* from the msb to the lsb, so the msb index is 31 138 // and the lsb index is 0. The result for the index when counting up: msb index is 0 (because it 139 // starts there), and the lsb index is 31. 140 result ^= sizeof(quint32) * 8 - 1; 141 return result; 142 } 143 #if Q_PROCESSOR_WORDSIZE == 8 144 // These are only defined for 64bit builds. 145 #define QT_HAS_BUILTIN_CTZLL 146 Q_ALWAYS_INLINE unsigned long qt_builtin_ctzll(quint64 val) 147 { 148 unsigned long result; 149 _BitScanForward64(&result, val); 150 return result; 151 } 152 // MSVC calls it _BitScanReverse and returns the carry flag, which we don't need 153 #define QT_HAS_BUILTIN_CLZLL 154 Q_ALWAYS_INLINE unsigned long qt_builtin_clzll(quint64 val) 155 { 156 unsigned long result; 157 _BitScanReverse64(&result, val); 158 // see qt_builtin_clz 159 result ^= sizeof(quint64) * 8 - 1; 160 return result; 161 } 162 #endif // MSVC 64bit 163 # define QT_HAS_BUILTIN_CTZS 164 Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept 165 { 166 return qt_builtin_ctz(v); 167 } 168 #define QT_HAS_BUILTIN_CLZS 169 Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept 170 { 171 return qt_builtin_clz(v) - 16U; 172 } 173 174 // Neither MSVC nor the Intel compiler define a macro for the POPCNT processor 175 // feature, so we're using either the SSE4.2 or the AVX macro as a proxy (Clang 176 // does define the macro). It's incorrect for two reasons: 177 // 1. It's a separate bit in CPUID, so a processor could implement SSE4.2 and 178 // not POPCNT, but that's unlikely to happen. 179 // 2. There are processors that support POPCNT but not AVX (Intel Nehalem 180 // architecture), but unlike the other compilers, MSVC has no option 181 // to generate code for those processors. 182 // So it's an acceptable compromise. 183 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 184 // We use C++20 <bit> operations instead which ensures constexpr popcount 185 #elif defined(__AVX__) || defined(__SSE4_2__) || defined(__POPCNT__) 186 #define QT_POPCOUNT_CONSTEXPR 187 #define QT_POPCOUNT_RELAXED_CONSTEXPR 188 #define QALGORITHMS_USE_BUILTIN_POPCOUNT 189 #define QALGORITHMS_USE_BUILTIN_POPCOUNTLL 190 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint32 v) noexcept 191 { 192 return __popcnt(v); 193 } 194 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint8 v) noexcept 195 { 196 return __popcnt16(v); 197 } 198 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint16 v) noexcept 199 { 200 return __popcnt16(v); 201 } 202 Q_ALWAYS_INLINE uint qt_builtin_popcountll(quint64 v) noexcept 203 { 204 #if Q_PROCESSOR_WORDSIZE == 8 205 return __popcnt64(v); 206 #else 207 return __popcnt(quint32(v)) + __popcnt(quint32(v >> 32)); 208 #endif // MSVC 64bit 209 } 210 211 #endif // __AVX__ || __SSE4_2__ || __POPCNT__ 212 213 #endif // MSVC 214 #endif // QT_HAS_CONSTEXPR_BUILTINS 215 216 #ifndef QT_POPCOUNT_CONSTEXPR 217 #define QT_POPCOUNT_CONSTEXPR constexpr 218 #define QT_POPCOUNT_RELAXED_CONSTEXPR constexpr 219 #endif 220 221 } +/ //namespace QAlgorithmsPrivate 222 223 /+ Q_DECL_CONST_FUNCTION +/ pragma(inline, true) uint qPopulationCount(quint32 v)/+ noexcept+/ 224 { 225 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 226 return std::popcount(v); 227 #elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT +/ 228 return popcnt(v); 229 /+ #else 230 // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 231 return 232 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + 233 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + 234 (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; 235 #endif +/ 236 } 237 238 /+ Q_DECL_CONST_FUNCTION +/ pragma(inline, true) uint qPopulationCount(quint8 v)/+ noexcept+/ 239 { 240 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 241 return std::popcount(v); 242 #elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT +/ 243 return popcnt(v); 244 /+ #else 245 return 246 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; 247 #endif +/ 248 } 249 250 /+ Q_DECL_CONST_FUNCTION +/ pragma(inline, true) uint qPopulationCount(quint16 v)/+ noexcept+/ 251 { 252 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 253 return std::popcount(v); 254 #elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT +/ 255 return popcnt(v); 256 /+ #else 257 return 258 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + 259 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; 260 #endif +/ 261 } 262 263 /+ Q_DECL_CONST_FUNCTION +/ pragma(inline, true) uint qPopulationCount(quint64 v)/+ noexcept+/ 264 { 265 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 266 return std::popcount(v); 267 #elif defined QALGORITHMS_USE_BUILTIN_POPCOUNTLL +/ 268 return popcnt(v); 269 /+ #else 270 return 271 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + 272 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + 273 (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + 274 (((v >> 36) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + 275 (((v >> 48) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + 276 (((v >> 60) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; 277 #endif +/ 278 } 279 280 /+ Q_DECL_CONST_FUNCTION +/ pragma(inline, true) uint qPopulationCount(cpp_ulong v)/+ noexcept+/ 281 { 282 return qPopulationCount(static_cast!(quint64)(v)); 283 } 284 285 /+ #if defined(QALGORITHMS_USE_BUILTIN_POPCOUNT) 286 #undef QALGORITHMS_USE_BUILTIN_POPCOUNT 287 #endif 288 #undef QT_POPCOUNT_CONSTEXPR +/ 289 290 extern(C++, "QtPrivate") { 291 pragma(inline, true) uint qConstexprCountTrailingZeroBits(quint32 v)/+ noexcept+/ 292 { 293 // see http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel 294 uint c = 32; // c will be the number of zero bits on the right 295 v &= -signed(v); 296 if (v) c--; 297 if (v & 0x0000FFFF) c -= 16; 298 if (v & 0x00FF00FF) c -= 8; 299 if (v & 0x0F0F0F0F) c -= 4; 300 if (v & 0x33333333) c -= 2; 301 if (v & 0x55555555) c -= 1; 302 return c; 303 } 304 305 pragma(inline, true) uint qConstexprCountTrailingZeroBits(quint64 v)/+ noexcept+/ 306 { 307 quint32 x = static_cast!(quint32)(v); 308 return x ? qConstexprCountTrailingZeroBits(x) 309 : 32 + qConstexprCountTrailingZeroBits(static_cast!(quint32)(v >> 32)); 310 } 311 312 pragma(inline, true) uint qConstexprCountTrailingZeroBits(quint8 v)/+ noexcept+/ 313 { 314 uint c = 8; // c will be the number of zero bits on the right 315 v &= -int(signed(v)); 316 if (v) c--; 317 if (v & 0x0000000F) c -= 4; 318 if (v & 0x00000033) c -= 2; 319 if (v & 0x00000055) c -= 1; 320 return c; 321 } 322 323 pragma(inline, true) uint qConstexprCountTrailingZeroBits(quint16 v)/+ noexcept+/ 324 { 325 uint c = 16; // c will be the number of zero bits on the right 326 v &= -int(signed(v)); 327 if (v) c--; 328 if (v & 0x000000FF) c -= 8; 329 if (v & 0x00000F0F) c -= 4; 330 if (v & 0x00003333) c -= 2; 331 if (v & 0x00005555) c -= 1; 332 return c; 333 } 334 335 // Disabled as a workaround for https://issues.dlang.org/show_bug.cgi?id=22813 336 /*pragma(inline, true) uint qConstexprCountTrailingZeroBits(cpp_ulong v)/+ noexcept+/ 337 { 338 return qConstexprCountTrailingZeroBits(QIntegerForSizeof!(cpp_long).Unsigned(v)); 339 }*/ 340 } 341 342 pragma(inline, true) uint qCountTrailingZeroBits(quint32 v)/+ noexcept+/ 343 { 344 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 345 return std::countr_zero(v); 346 #elif defined(QT_HAS_BUILTIN_CTZ) +/ 347 return v ? bsf(v) : 32U; 348 /+ #else 349 return QtPrivate::qConstexprCountTrailingZeroBits(v); 350 #endif +/ 351 } 352 353 pragma(inline, true) uint qCountTrailingZeroBits(quint8 v)/+ noexcept+/ 354 { 355 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 356 return std::countr_zero(v); 357 #elif defined(QT_HAS_BUILTIN_CTZ) +/ 358 return v ? bsf(v) : 8U; 359 /+ #else 360 return QtPrivate::qConstexprCountTrailingZeroBits(v); 361 #endif +/ 362 } 363 364 pragma(inline, true) uint qCountTrailingZeroBits(quint16 v)/+ noexcept+/ 365 { 366 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 367 return std::countr_zero(v); 368 #elif defined(QT_HAS_BUILTIN_CTZS) +/ 369 return v ? bsf(v) : 16U; 370 /+ #else 371 return QtPrivate::qConstexprCountTrailingZeroBits(v); 372 #endif +/ 373 } 374 375 pragma(inline, true) uint qCountTrailingZeroBits(quint64 v)/+ noexcept+/ 376 { 377 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 378 return std::countr_zero(v); 379 #elif defined(QT_HAS_BUILTIN_CTZLL) +/ 380 return v ? bsf(v) : 64; 381 /+ #else 382 return QtPrivate::qConstexprCountTrailingZeroBits(v); 383 #endif +/ 384 } 385 386 pragma(inline, true) uint qCountTrailingZeroBits(cpp_ulong v)/+ noexcept+/ 387 { 388 return qCountTrailingZeroBits(QIntegerForSizeof!(cpp_long).Unsigned(v)); 389 } 390 391 pragma(inline, true) uint qCountLeadingZeroBits(quint32 v)/+ noexcept+/ 392 { 393 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 394 return std::countl_zero(v); 395 #elif defined(QT_HAS_BUILTIN_CLZ) +/ 396 return v ? 31U - bsr(v) : 32U; 397 /+ #else 398 // Hacker's Delight, 2nd ed. Fig 5-16, p. 102 399 v = v | (v >> 1); 400 v = v | (v >> 2); 401 v = v | (v >> 4); 402 v = v | (v >> 8); 403 v = v | (v >> 16); 404 return qPopulationCount(~v); 405 #endif +/ 406 } 407 408 pragma(inline, true) uint qCountLeadingZeroBits(quint8 v)/+ noexcept+/ 409 { 410 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 411 return std::countl_zero(v); 412 #elif defined(QT_HAS_BUILTIN_CLZ) +/ 413 return v ? 7U - bsr(v) : 8U; 414 /+ #else 415 v = v | (v >> 1); 416 v = v | (v >> 2); 417 v = v | (v >> 4); 418 return qPopulationCount(static_cast<quint8>(~v)); 419 #endif +/ 420 } 421 422 pragma(inline, true) uint qCountLeadingZeroBits(quint16 v)/+ noexcept+/ 423 { 424 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 425 return std::countl_zero(v); 426 #elif defined(QT_HAS_BUILTIN_CLZS) +/ 427 return v ? 15U - bsr(v) : 16U; 428 /+ #else 429 v = v | (v >> 1); 430 v = v | (v >> 2); 431 v = v | (v >> 4); 432 v = v | (v >> 8); 433 return qPopulationCount(static_cast<quint16>(~v)); 434 #endif +/ 435 } 436 437 pragma(inline, true) uint qCountLeadingZeroBits(quint64 v)/+ noexcept+/ 438 { 439 /+ #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L 440 return std::countl_zero(v); 441 #elif defined(QT_HAS_BUILTIN_CLZLL) +/ 442 return v ? 63U - bsr(v) : 64U; 443 /+ #else 444 v = v | (v >> 1); 445 v = v | (v >> 2); 446 v = v | (v >> 4); 447 v = v | (v >> 8); 448 v = v | (v >> 16); 449 v = v | (v >> 32); 450 return qPopulationCount(~v); 451 #endif +/ 452 } 453 454 pragma(inline, true) uint qCountLeadingZeroBits(cpp_ulong v)/+ noexcept+/ 455 { 456 return qCountLeadingZeroBits(QIntegerForSizeof!(cpp_long).Unsigned(v)); 457 } 458 459 /+ #undef QT_POPCOUNT_RELAXED_CONSTEXPR +/ 460 461