/proc/self/cwd/external/re2~/re2/bitmap256.h
Line | Count | Source |
1 | | // Copyright 2016 The RE2 Authors. All Rights Reserved. |
2 | | // Use of this source code is governed by a BSD-style |
3 | | // license that can be found in the LICENSE file. |
4 | | |
5 | | #ifndef RE2_BITMAP256_H_ |
6 | | #define RE2_BITMAP256_H_ |
7 | | |
8 | | #include <stdint.h> |
9 | | #include <string.h> |
10 | | |
11 | | #include "absl/log/absl_check.h" |
12 | | #include "absl/log/absl_log.h" |
13 | | |
14 | | #ifdef _MSC_VER |
15 | | #include <intrin.h> |
16 | | #endif |
17 | | |
18 | | namespace re2 { |
19 | | |
20 | | class Bitmap256 { |
21 | | public: |
22 | 0 | Bitmap256() { |
23 | 0 | Clear(); |
24 | 0 | } |
25 | | |
26 | | // Clears all of the bits. |
27 | 0 | void Clear() { |
28 | 0 | memset(words_, 0, sizeof words_); |
29 | 0 | } |
30 | | |
31 | | // Tests the bit with index c. |
32 | | bool Test(int c) const { |
33 | | ABSL_DCHECK_GE(c, 0); |
34 | | ABSL_DCHECK_LE(c, 255); |
35 | | |
36 | | return (words_[c / 64] & (uint64_t{1} << (c % 64))) != 0; |
37 | | } |
38 | | |
39 | | // Sets the bit with index c. |
40 | | void Set(int c) { |
41 | | ABSL_DCHECK_GE(c, 0); |
42 | | ABSL_DCHECK_LE(c, 255); |
43 | | |
44 | | words_[c / 64] |= (uint64_t{1} << (c % 64)); |
45 | | } |
46 | | |
47 | | // Finds the next non-zero bit with index >= c. |
48 | | // Returns -1 if no such bit exists. |
49 | | int FindNextSetBit(int c) const; |
50 | | |
51 | | private: |
52 | | // Finds the least significant non-zero bit in n. |
53 | | static int FindLSBSet(uint64_t n) { |
54 | | ABSL_DCHECK_NE(n, uint64_t{0}); |
55 | | #if defined(__GNUC__) |
56 | | return __builtin_ctzll(n); |
57 | | #elif defined(_MSC_VER) && defined(_M_X64) |
58 | | unsigned long c; |
59 | | _BitScanForward64(&c, n); |
60 | | return static_cast<int>(c); |
61 | | #elif defined(_MSC_VER) && defined(_M_IX86) |
62 | | unsigned long c; |
63 | | if (static_cast<uint32_t>(n) != 0) { |
64 | | _BitScanForward(&c, static_cast<uint32_t>(n)); |
65 | | return static_cast<int>(c); |
66 | | } else { |
67 | | _BitScanForward(&c, static_cast<uint32_t>(n >> 32)); |
68 | | return static_cast<int>(c) + 32; |
69 | | } |
70 | | #else |
71 | | int c = 63; |
72 | | for (int shift = 1 << 5; shift != 0; shift >>= 1) { |
73 | | uint64_t word = n << shift; |
74 | | if (word != 0) { |
75 | | n = word; |
76 | | c -= shift; |
77 | | } |
78 | | } |
79 | | return c; |
80 | | #endif |
81 | | } |
82 | | |
83 | | uint64_t words_[4]; |
84 | | }; |
85 | | |
86 | | } // namespace re2 |
87 | | |
88 | | #endif // RE2_BITMAP256_H_ |