]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | /* |
2 | * Copyright (C) 2014 Cloudius Systems, Ltd. | |
3 | */ | |
4 | ||
5 | /* | |
6 | * Imported from OSv: | |
7 | * | |
8 | * Copyright (C) 2014 Cloudius Systems, Ltd. | |
9 | * | |
10 | * This work is open source software, licensed under the terms of the | |
11 | * BSD license as described in the LICENSE file in the top-level directory. | |
12 | */ | |
13 | ||
14 | #pragma once | |
15 | ||
16 | #include <bitset> | |
17 | #include <limits> | |
18 | ||
19 | namespace seastar { | |
20 | ||
21 | namespace bitsets { | |
22 | ||
23 | static constexpr int ulong_bits = std::numeric_limits<unsigned long>::digits; | |
24 | ||
25 | /** | |
26 | * Returns the number of leading zeros in value's binary representation. | |
27 | * | |
28 | * If value == 0 the result is undefied. If T is signed and value is negative | |
29 | * the result is undefined. | |
30 | * | |
31 | * The highest value that can be returned is std::numeric_limits<T>::digits - 1, | |
32 | * which is returned when value == 1. | |
33 | */ | |
34 | template<typename T> | |
f67539c2 | 35 | inline size_t count_leading_zeros(T value) noexcept; |
11fdf7f2 TL |
36 | |
37 | /** | |
38 | * Returns the number of trailing zeros in value's binary representation. | |
39 | * | |
40 | * If value == 0 the result is undefied. If T is signed and value is negative | |
41 | * the result is undefined. | |
42 | * | |
43 | * The highest value that can be returned is std::numeric_limits<T>::digits - 1. | |
44 | */ | |
45 | template<typename T> | |
f67539c2 | 46 | static inline size_t count_trailing_zeros(T value) noexcept; |
11fdf7f2 TL |
47 | |
48 | template<> | |
f67539c2 | 49 | inline size_t count_leading_zeros<unsigned long>(unsigned long value) noexcept |
11fdf7f2 TL |
50 | { |
51 | return __builtin_clzl(value); | |
52 | } | |
53 | ||
54 | template<> | |
f67539c2 | 55 | inline size_t count_leading_zeros<long>(long value) noexcept |
11fdf7f2 TL |
56 | { |
57 | return __builtin_clzl((unsigned long)value) - 1; | |
58 | } | |
59 | ||
60 | template<> | |
f67539c2 TL |
61 | inline size_t count_leading_zeros<unsigned long long>(unsigned long long value) noexcept |
62 | { | |
63 | return __builtin_clzll(value); | |
64 | } | |
65 | ||
66 | template<> | |
67 | inline size_t count_leading_zeros<long long>(long long value) noexcept | |
11fdf7f2 TL |
68 | { |
69 | return __builtin_clzll((unsigned long long)value) - 1; | |
70 | } | |
71 | ||
72 | template<> | |
73 | inline | |
f67539c2 | 74 | size_t count_trailing_zeros<unsigned long>(unsigned long value) noexcept |
11fdf7f2 TL |
75 | { |
76 | return __builtin_ctzl(value); | |
77 | } | |
78 | ||
79 | template<> | |
80 | inline | |
f67539c2 | 81 | size_t count_trailing_zeros<long>(long value) noexcept |
11fdf7f2 TL |
82 | { |
83 | return __builtin_ctzl((unsigned long)value); | |
84 | } | |
85 | ||
f67539c2 TL |
86 | template<> |
87 | inline | |
88 | size_t count_trailing_zeros<unsigned long long>(unsigned long long value) noexcept | |
89 | { | |
90 | return __builtin_ctzll(value); | |
91 | } | |
92 | ||
93 | template<> | |
94 | inline | |
95 | size_t count_trailing_zeros<long long>(long long value) noexcept | |
96 | { | |
97 | return __builtin_ctzll((unsigned long long)value); | |
98 | } | |
99 | ||
11fdf7f2 TL |
100 | /** |
101 | * Returns the index of the first set bit. | |
102 | * Result is undefined if bitset.any() == false. | |
103 | */ | |
104 | template<size_t N> | |
f67539c2 | 105 | static inline size_t get_first_set(const std::bitset<N>& bitset) noexcept |
11fdf7f2 TL |
106 | { |
107 | static_assert(N <= ulong_bits, "bitset too large"); | |
108 | return count_trailing_zeros(bitset.to_ulong()); | |
109 | } | |
110 | ||
111 | /** | |
112 | * Returns the index of the last set bit in the bitset. | |
113 | * Result is undefined if bitset.any() == false. | |
114 | */ | |
115 | template<size_t N> | |
f67539c2 | 116 | static inline size_t get_last_set(const std::bitset<N>& bitset) noexcept |
11fdf7f2 TL |
117 | { |
118 | static_assert(N <= ulong_bits, "bitset too large"); | |
119 | return ulong_bits - 1 - count_leading_zeros(bitset.to_ulong()); | |
120 | } | |
121 | ||
122 | template<size_t N> | |
123 | class set_iterator : public std::iterator<std::input_iterator_tag, int> | |
124 | { | |
125 | private: | |
f67539c2 | 126 | void advance() noexcept |
11fdf7f2 TL |
127 | { |
128 | if (_bitset.none()) { | |
129 | _index = -1; | |
130 | } else { | |
131 | auto shift = get_first_set(_bitset) + 1; | |
132 | _index += shift; | |
133 | _bitset >>= shift; | |
134 | } | |
135 | } | |
136 | public: | |
f67539c2 | 137 | set_iterator(std::bitset<N> bitset, int offset = 0) noexcept |
11fdf7f2 TL |
138 | : _bitset(bitset) |
139 | , _index(offset - 1) | |
140 | { | |
141 | static_assert(N <= ulong_bits, "This implementation is inefficient for large bitsets"); | |
142 | _bitset >>= offset; | |
143 | advance(); | |
144 | } | |
145 | ||
20effc67 | 146 | set_iterator& operator++() noexcept |
11fdf7f2 TL |
147 | { |
148 | advance(); | |
20effc67 TL |
149 | return *this; |
150 | } | |
151 | ||
152 | set_iterator operator++(int) noexcept | |
153 | { | |
154 | auto ret = *this; | |
155 | advance(); | |
156 | return ret; | |
11fdf7f2 TL |
157 | } |
158 | ||
f67539c2 | 159 | int operator*() const noexcept |
11fdf7f2 TL |
160 | { |
161 | return _index; | |
162 | } | |
163 | ||
f67539c2 | 164 | bool operator==(const set_iterator& other) const noexcept |
11fdf7f2 TL |
165 | { |
166 | return _index == other._index; | |
167 | } | |
168 | ||
f67539c2 | 169 | bool operator!=(const set_iterator& other) const noexcept |
11fdf7f2 TL |
170 | { |
171 | return !(*this == other); | |
172 | } | |
173 | private: | |
174 | std::bitset<N> _bitset; | |
175 | int _index; | |
176 | }; | |
177 | ||
178 | template<size_t N> | |
179 | class set_range | |
180 | { | |
181 | public: | |
182 | using iterator = set_iterator<N>; | |
183 | using value_type = int; | |
184 | ||
20effc67 | 185 | constexpr set_range(std::bitset<N> bitset, int offset = 0) noexcept |
11fdf7f2 TL |
186 | : _bitset(bitset) |
187 | , _offset(offset) | |
188 | { | |
189 | } | |
190 | ||
f67539c2 TL |
191 | iterator begin() const noexcept { return iterator(_bitset, _offset); } |
192 | iterator end() const noexcept { return iterator(0); } | |
11fdf7f2 TL |
193 | private: |
194 | std::bitset<N> _bitset; | |
195 | int _offset; | |
196 | }; | |
197 | ||
198 | template<size_t N> | |
f67539c2 | 199 | static inline set_range<N> for_each_set(std::bitset<N> bitset, int offset = 0) noexcept |
11fdf7f2 TL |
200 | { |
201 | return set_range<N>(bitset, offset); | |
202 | } | |
203 | ||
204 | } | |
205 | ||
206 | } |