Seastar
High performance C++ framework for concurrent servers
bitset-iter.hh
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#ifndef SEASTAR_MODULE
17#include <bitset>
18#include <limits>
19#include <seastar/util/modules.hh>
20#endif
21
22namespace seastar {
23
24namespace bitsets {
25
26static constexpr int ulong_bits = std::numeric_limits<unsigned long>::digits;
27
37template<typename T>
38size_t count_leading_zeros(T value) noexcept;
39
48template<typename T>
49size_t count_trailing_zeros(T value) noexcept;
50
51template<>
52inline size_t count_leading_zeros<unsigned long>(unsigned long value) noexcept
53{
54 return __builtin_clzl(value);
55}
56
57template<>
58inline size_t count_leading_zeros<long>(long value) noexcept
59{
60 return __builtin_clzl((unsigned long)value) - 1;
61}
62
63template<>
64inline size_t count_leading_zeros<unsigned long long>(unsigned long long value) noexcept
65{
66 return __builtin_clzll(value);
67}
68
69template<>
70inline size_t count_leading_zeros<long long>(long long value) noexcept
71{
72 return __builtin_clzll((unsigned long long)value) - 1;
73}
74
75template<>
76inline
77size_t count_trailing_zeros<unsigned long>(unsigned long value) noexcept
78{
79 return __builtin_ctzl(value);
80}
81
82template<>
83inline
84size_t count_trailing_zeros<long>(long value) noexcept
85{
86 return __builtin_ctzl((unsigned long)value);
87}
88
89template<>
90inline
91size_t count_trailing_zeros<unsigned long long>(unsigned long long value) noexcept
92{
93 return __builtin_ctzll(value);
94}
95
96template<>
97inline
98size_t count_trailing_zeros<long long>(long long value) noexcept
99{
100 return __builtin_ctzll((unsigned long long)value);
101}
102
107template<size_t N>
108inline size_t get_first_set(const std::bitset<N>& bitset) noexcept
109{
110 static_assert(N <= ulong_bits, "bitset too large");
111 return count_trailing_zeros(bitset.to_ulong());
112}
113
118template<size_t N>
119inline size_t get_last_set(const std::bitset<N>& bitset) noexcept
120{
121 static_assert(N <= ulong_bits, "bitset too large");
122 return ulong_bits - 1 - count_leading_zeros(bitset.to_ulong());
123}
124
125SEASTAR_MODULE_EXPORT_BEGIN
126
127template<size_t N>
129{
130private:
131 void advance() noexcept
132 {
133 if (_bitset.none()) {
134 _index = -1;
135 } else {
136 auto shift = get_first_set(_bitset) + 1;
137 _index += shift;
138 _bitset >>= shift;
139 }
140 }
141public:
142 using iterator_category = std::input_iterator_tag;
143 using value_type = int;
144 using difference_type = std::ptrdiff_t;
145 using pointer = int*;
146 using reference = int&;
147
148 set_iterator(std::bitset<N> bitset, int offset = 0) noexcept
149 : _bitset(bitset)
150 , _index(offset - 1)
151 {
152 static_assert(N <= ulong_bits, "This implementation is inefficient for large bitsets");
153 _bitset >>= offset;
154 advance();
155 }
156
157 set_iterator& operator++() noexcept
158 {
159 advance();
160 return *this;
161 }
162
163 set_iterator operator++(int) noexcept
164 {
165 auto ret = *this;
166 advance();
167 return ret;
168 }
169
170 int operator*() const noexcept
171 {
172 return _index;
173 }
174
175 bool operator==(const set_iterator& other) const noexcept
176 {
177 return _index == other._index;
178 }
179
180 bool operator!=(const set_iterator& other) const noexcept
181 {
182 return !(*this == other);
183 }
184private:
185 std::bitset<N> _bitset;
186 int _index;
187};
188
189template<size_t N>
191{
192public:
194 using value_type = int;
195
196 constexpr set_range(std::bitset<N> bitset, int offset = 0) noexcept
197 : _bitset(bitset)
198 , _offset(offset)
199 {
200 }
201
202 iterator begin() const noexcept { return iterator(_bitset, _offset); }
203 iterator end() const noexcept { return iterator(0); }
204private:
205 std::bitset<N> _bitset;
206 int _offset;
207};
208
209template<size_t N>
210inline set_range<N> for_each_set(std::bitset<N> bitset, int offset = 0) noexcept
211{
212 return set_range<N>(bitset, offset);
213}
214
215SEASTAR_MODULE_EXPORT_END
216
217}
218
219}
Definition: bitset-iter.hh:129
Definition: bitset-iter.hh:191
Seastar API namespace.
Definition: abort_on_ebadf.hh:26