• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

PeterCDMcLean / BitLib / 15380630124

01 Jun 2025 11:33PM UTC coverage: 52.575% (-0.2%) from 52.785%
15380630124

Pull #16

github

web-flow
Merge b85ad7435 into a32e9aeba
Pull Request #16: Small buffer optimization

8860 of 16682 branches covered (53.11%)

Branch coverage included in aggregate %.

99 of 107 new or added lines in 8 files covered. (92.52%)

1 existing line in 1 file now uncovered.

5502 of 10635 relevant lines covered (51.73%)

7820224.37 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

65.43
/include/bitlib/bit-iterator/bit_iterator_adapter.hpp
1
// ============================== BIT ITERATOR ============================== //
2
// Project:         The C++ Bit Library
3
// Name:            bit_iterator_adapter.hpp
4
// Description:     A class representing an iterator on bit sequences
5
// Creator:         Vincent Reverdy
6
// Contributor(s):  Vincent Reverdy [2015-2017]
7
// License:         BSD 3-Clause License
8
// ========================================================================== //
9
#ifndef _BIT_ITERATOR_ADAPTER_HPP_INCLUDED
10
#define _BIT_ITERATOR_ADAPTER_HPP_INCLUDED
11
// ========================================================================== //
12

13

14

15
// ================================ PREAMBLE ================================ //
16
// C++ standard library
17
#include <compare>
18
#include <concepts>
19
#include <cstddef>
20
#include <iterator>
21
#include <type_traits>
22

23
#include "bitlib/bit-containers/bit_bitsof.hpp"
24
#include "bitlib/bit_concepts.hpp"
25
// Project sources
26
#include "bit_details.hpp"
27
#include "bit_reference.hpp"
28
// Third-party libraries
29
// Miscellaneous
30
namespace bit {
31

32
/* ****************************** BIT ITERATOR ****************************** */
33
// Bit iterator class definition
34
template <typename Iterator, typename BaseIterator>
35
class bit_iterator_adapter {
36
  template <typename, typename>
37
  friend class bit_iterator_adapter;
38

39
  // Assertions
40
 private:
41
  using _traits_t = _cv_iterator_traits<Iterator>;
42
  static constexpr bool big_to_small = sizeof(typename _cv_iterator_traits<BaseIterator>::value_type) >
43
                                       sizeof(typename _cv_iterator_traits<Iterator>::value_type);
44
  static constexpr size_t ratio = big_to_small ? (sizeof(typename _cv_iterator_traits<BaseIterator>::value_type) /
45
                                                  sizeof(typename _cv_iterator_traits<Iterator>::value_type))
46
                                               : (sizeof(typename _cv_iterator_traits<Iterator>::value_type) /
47
                                                  sizeof(typename _cv_iterator_traits<BaseIterator>::value_type));
48

49
  // Types
50
 public:
51
  using iterator_type = Iterator;
52
  using base_iterator_type = BaseIterator;
53
  using word_type = typename _traits_t::value_type;
54
  using iterator_category = typename _traits_t::iterator_category;
55
  using value_type = typename _traits_t::value_type;
56
  using difference_type = std::ptrdiff_t;
57
  using pointer = typename _traits_t::pointer;
58
  using reference = typename _traits_t::reference;
59
  using size_type = std::size_t;
60

61
  // Lifecycle
62
 public:
63
  constexpr bit_iterator_adapter();
64
  constexpr bit_iterator_adapter(const bit_iterator_adapter<Iterator, BaseIterator>& other);
65
  template <typename T, typename U>
66
  constexpr bit_iterator_adapter(const bit_iterator_adapter<T, U>& other)
67
    requires std::constructible_from<iterator_type, T>;
68
  explicit constexpr bit_iterator_adapter(iterator_type i);
69
  constexpr bit_iterator_adapter(base_iterator_type i, size_type pos = 0);
70
  explicit constexpr bit_iterator_adapter(const pointer& ptr)
71
    requires std::constructible_from<iterator_type, word_type*>;
72

73
  // Assignment
74
 public:
75
  constexpr bit_iterator_adapter& operator=(const bit_iterator_adapter<Iterator, BaseIterator>& other);
76
  template <typename T, typename U>
77
  constexpr bit_iterator_adapter& operator=(const bit_iterator_adapter<T, U>& other);
78

79
  // Access
80
 public:
81
  constexpr reference operator*() const noexcept;
82
  constexpr pointer operator->() const noexcept;
83
  constexpr reference operator[](difference_type n) const;
84

85
  // Increment and decrement operators
86
 public:
87
  constexpr bit_iterator_adapter& operator++();
88
  constexpr bit_iterator_adapter& operator--();
89
  constexpr bit_iterator_adapter operator++(int);
90
  constexpr bit_iterator_adapter operator--(int);
91
  constexpr bit_iterator_adapter operator+(difference_type n) const;
92
  constexpr bit_iterator_adapter operator-(difference_type n) const;
93
  constexpr bit_iterator_adapter& operator+=(difference_type n);
94
  constexpr bit_iterator_adapter& operator-=(difference_type n);
95
  constexpr difference_type operator-(const bit_iterator_adapter&) const;
96

97
  // Underlying details
98
 public:
99
  constexpr base_iterator_type base() const;
100
  constexpr size_type position() const noexcept;
101

102
  bool operator==(const bit_iterator_adapter&) const = default;
5✔
103
  auto operator<=>(const bit_iterator_adapter&) const = default;
104
  // Implementation details: data members
105
 private:
106
  base_iterator_type _current;
1✔
107
  size_type _position;
1✔
108

109
  // Non-member arithmetic operators
110
  template <typename T, typename U>
111
  friend constexpr bit_iterator_adapter<T, U> operator+(
112
      typename bit_iterator_adapter<T, U>::difference_type n,
113
      const bit_iterator_adapter<T, U>& i);
114
  template <typename T, typename U, typename V, typename W>
115
  friend constexpr typename std::common_type<
116
      typename bit_iterator_adapter<T, U>::difference_type,
117
      typename bit_iterator_adapter<V, W>::difference_type>::type
118
  operator-(
119
      const bit_iterator_adapter<T, U>& lhs,
120
      const bit_iterator_adapter<V, W>& rhs);
121
};
122
/* ************************************************************************** */
123

124

125

126
// ------------------------ BIT ITERATOR: LIFECYCLE ------------------------- //
127
// Implicitly default constructs a bit iterator
128
template <typename Iterator, typename BaseIterator>
129
constexpr bit_iterator_adapter<Iterator, BaseIterator>::bit_iterator_adapter()
130
    : _current(), _position() {
131
}
132

133
// Implicitly constructs a bit iterator from another bit iterator
134
template <typename Iterator, typename BaseIterator>
135
constexpr bit_iterator_adapter<Iterator, BaseIterator>::bit_iterator_adapter(const bit_iterator_adapter<Iterator, BaseIterator>& other)
25✔
136
    : _current(other.base()), _position(other.position()) {
50✔
137
  assert(_position < ratio);
50!
138
}
50✔
139

140
template <typename Iterator, typename BaseIterator>
141
template <typename T, typename U>
142
constexpr bit_iterator_adapter<Iterator, BaseIterator>::bit_iterator_adapter(const bit_iterator_adapter<T, U>& other)
143
  requires std::constructible_from<iterator_type, T>
144
    : _current(other.base()), _position(other.position()) {
145
  assert(_position < ratio);
146
}
147

148
// Explicitly constructs an aligned bit iterator from an iterator
149
template <typename Iterator, typename BaseIterator>
150
constexpr bit_iterator_adapter<Iterator, BaseIterator>::bit_iterator_adapter(const iterator_type i)
151
    : _current(reinterpret_cast<BaseIterator>(i)), _position(0) {
152
}
153

154
// Explicitly constructs an unaligned bit iterator from an iterator
155
template <typename Iterator, typename BaseIterator>
156
constexpr bit_iterator_adapter<Iterator, BaseIterator>::bit_iterator_adapter(const base_iterator_type i, size_type pos)
4✔
157
    : _current(i), _position((assert(pos < binary_digits<word_type>::value), pos)) {
8!
158
}
8✔
159

160
// Explicitly constructs an unaligned bit iterator from a pointer
161
template <typename Iterator, typename BaseIterator>
162
constexpr bit_iterator_adapter<Iterator, BaseIterator>::bit_iterator_adapter(const pointer& ptr)
163
  requires std::constructible_from<iterator_type, word_type*>
164
    : _current(ptr._current), _position(ptr.position()) {
165
  assert(_position < ratio);
166
}
167
// -------------------------------------------------------------------------- //
168

169

170

171
// ------------------------ BIT ITERATOR: ASSIGNMENT ------------------------ //
172
// Assigns a bit iterator to the bit iterator
173
template <typename Iterator, typename BaseIterator>
174
constexpr bit_iterator_adapter<Iterator, BaseIterator>& bit_iterator_adapter<Iterator, BaseIterator>::operator=(
NEW
175
    const bit_iterator_adapter<Iterator, BaseIterator>& other) {
NEW
176
  _current = other._current;
×
NEW
177
  _position = other._position;
×
NEW
178
  assert(_position < ratio);
×
NEW
179
  return *this;
×
NEW
180
}
181

182
// Assigns a bit iterator to the bit iterator
183
template <typename Iterator, typename BaseIterator>
184
template <typename T, typename U>
185
constexpr bit_iterator_adapter<Iterator, BaseIterator>& bit_iterator_adapter<Iterator, BaseIterator>::operator=(
186
    const bit_iterator_adapter<T, U>& other) {
187
  _current = other._current;
188
  _position = other._position;
189
  assert(_position < ratio);
190
  return *this;
191
}
192
// -------------------------------------------------------------------------- //
193

194

195

196
// -------------------------- BIT ITERATOR: ACCESS -------------------------- //
197
// Gets a bit reference from the bit iterator
198
template <typename Iterator, typename BaseIterator>
199
constexpr typename bit_iterator_adapter<Iterator, BaseIterator>::reference
200
bit_iterator_adapter<Iterator, BaseIterator>::operator*() const noexcept {
14✔
201
  return reference(reinterpret_cast<word_type*>(&(*_current))[_position]);
14✔
202
}
7✔
203

204
// Gets a pointer to a bit
205
template <typename Iterator, typename BaseIterator>
206
constexpr typename bit_iterator_adapter<Iterator, BaseIterator>::pointer bit_iterator_adapter<Iterator, BaseIterator>::operator->() const noexcept {
207
  return pointer(&reinterpret_cast<word_type*>(&(*_current))[_position]);
208
}
209

210
// Gets a bit reference, decrementing or incrementing the iterator
211
template <typename Iterator, typename BaseIterator>
212
constexpr typename bit_iterator_adapter<Iterator, BaseIterator>::reference bit_iterator_adapter<Iterator, BaseIterator>::operator[](difference_type n) const {
213
  const difference_type sum = _position + n;
214
  difference_type diff = sum / ratio;
215
  if (sum < 0 && diff * ratio != sum) {
216
    --diff;
217
  }
218
  return reference(reinterpret_cast<Iterator>(&(*std::next(_current, diff)))[sum - diff * ratio]);
219
}
220
// -------------------------------------------------------------------------- //
221

222

223

224
// ------------- BIT ITERATOR: INCREMENT AND DECREMENT OPERATORS ------------ //
225
// Increments the bit iterator and returns it
226
template <typename Iterator, typename BaseIterator>
227
constexpr bit_iterator_adapter<Iterator, BaseIterator>& bit_iterator_adapter<Iterator, BaseIterator>::operator++() {
4✔
228
  if (_position + 1 < ratio) {
4!
229
    ++_position;
2✔
230
  } else {
1✔
231
    ++_current;
2✔
232
    _position = 0;
2✔
233
  }
1✔
234
  return *this;
4✔
235
}
2✔
236

237
// Decrements the bit iterator and returns it
238
template <typename Iterator, typename BaseIterator>
239
constexpr bit_iterator_adapter<Iterator, BaseIterator>& bit_iterator_adapter<Iterator, BaseIterator>::operator--() {
240
  if (_position) {
241
    --_position;
242
  } else {
243
    --_current;
244
    _position = ratio - 1;
245
  }
246
  return *this;
247
}
248

249
// Increments the bit iterator and returns the old one
250
template <typename Iterator, typename BaseIterator>
251
constexpr bit_iterator_adapter<Iterator, BaseIterator> bit_iterator_adapter<Iterator, BaseIterator>::operator++(int) {
2✔
252
  bit_iterator_adapter old = *this;
2✔
253
  ++(*this);
2✔
254
  return old;
3✔
255
}
1✔
256

257
// Decrements the bit iterator and returns the old one
258
template <typename Iterator, typename BaseIterator>
259
constexpr bit_iterator_adapter<Iterator, BaseIterator> bit_iterator_adapter<Iterator, BaseIterator>::operator--(int) {
260
  bit_iterator_adapter old = *this;
261
  --(*this);
262
  return old;
263
}
264

265
// Looks forward several bits and gets an iterator at this position
266
template <typename Iterator, typename BaseIterator>
267
constexpr bit_iterator_adapter<Iterator, BaseIterator> bit_iterator_adapter<Iterator, BaseIterator>::operator+(difference_type n) const {
268
  const difference_type sum = _position + n;
269
  difference_type diff = sum / ratio;
270
  if (sum < 0 && diff * ratio != sum) {
271
    --diff;
272
  }
273
  return bit_iterator_adapter(&reinterpret_cast<Iterator>(&(*std::next(_current, diff)))[sum - diff * ratio], sum - diff * ratio);
274
}
275

276
// Looks backward several bits and gets an iterator at this position
277
template <typename Iterator, typename BaseIterator>
278
constexpr bit_iterator_adapter<Iterator, BaseIterator> bit_iterator_adapter<Iterator, BaseIterator>::operator-(difference_type n) const {
279
  const difference_type sum = _position - n;
280
  difference_type diff = sum / ratio;
281
  if (sum < 0 && diff * ratio != sum) {
282
    --diff;
283
  }
284
  return bit_iterator_adapter(&reinterpret_cast<Iterator>(&(*std::next(_current, diff)))[sum - diff * ratio], sum - diff * ratio);
285
}
286

287
// Increments the iterator by several bits and returns it
288
template <typename Iterator, typename BaseIterator>
289
constexpr bit_iterator_adapter<Iterator, BaseIterator>& bit_iterator_adapter<Iterator, BaseIterator>::operator+=(difference_type n) {
2✔
290
  const difference_type sum = _position + n;
2✔
291
  difference_type diff = sum / ratio;
2✔
292
  if (sum < 0 && diff * ratio != sum) {
2!
NEW
293
    --diff;
×
NEW
294
  }
295
  _current = std::next(_current, diff);
3✔
296
  _position = (sum - diff * ratio);
2✔
297
  return *this;
3✔
298
}
1✔
299

300
// Decrements the iterator by several bits and returns it
301
template <typename Iterator, typename BaseIterator>
302
constexpr bit_iterator_adapter<Iterator, BaseIterator>& bit_iterator_adapter<Iterator, BaseIterator>::operator-=(difference_type n) {
303
  const difference_type sum = _position - n;
304
  difference_type diff = sum / ratio;
305
  if (sum < 0 && diff * ratio != sum) {
306
    --diff;
307
  }
308
  _current = std::next(_current, diff);
309
  _position = (sum - diff * ratio);
310
  return *this;
311
}
312
// -------------------------------------------------------------------------- //
313

314
template <typename Iterator, typename BaseIterator>
315
constexpr bit_iterator_adapter<Iterator, BaseIterator>::difference_type
316
bit_iterator_adapter<Iterator, BaseIterator>::operator-(const bit_iterator_adapter<Iterator, BaseIterator>& other) const {
6✔
317
  return (_current - other._current) * ratio + (_position - other._position);
6✔
318
}
3✔
319

320
// -------------------- BIT ITERATOR: UNDERLYING DETAILS -------------------- //
321
// Returns a copy of the underlying iterator
322
template <typename Iterator, typename BaseIterator>
323
constexpr typename bit_iterator_adapter<Iterator, BaseIterator>::base_iterator_type bit_iterator_adapter<Iterator, BaseIterator>::base() const {
50✔
324
  return _current;
50✔
325
}
25✔
326

327
// Returns the position of the bit within the underlying word
328
template <typename Iterator, typename BaseIterator>
329
constexpr typename bit_iterator_adapter<Iterator, BaseIterator>::size_type bit_iterator_adapter<Iterator, BaseIterator>::position() const noexcept {
50✔
330
  return _position;
50✔
331
}
25✔
332

333
// -------------- BIT ITERATOR: NON-MEMBER ARITHMETIC OPERATORS ------------- //
334
// Advances the bit iterator several times
335
template <typename T, typename U>
336
constexpr bit_iterator_adapter<T, U> operator+(typename bit_iterator_adapter<T, U>::difference_type n, const bit_iterator_adapter<T, U>& i) {
337
  return i + n;
338
}
339

340
// Computes the distance in bits separating two bit iterators
341
template <typename T, typename U, typename V, typename W>
342
constexpr typename std::common_type<
343
    typename bit_iterator_adapter<T, U>::difference_type,
344
    typename bit_iterator_adapter<V, W>::difference_type>::type
345
operator-(const bit_iterator_adapter<T, U>& lhs, const bit_iterator_adapter<V, W>& rhs) {
346
  using lhs_utype = typename bit_iterator_adapter<T, U>::word_type;
347
  using rhs_utype = typename bit_iterator_adapter<V, W>::word_type;
348
  using lhs_type = typename bit_iterator_adapter<T, U>::difference_type;
349
  using rhs_type = typename bit_iterator_adapter<V, W>::difference_type;
350
  using size_type = typename std::common_type<typename bit_iterator_adapter<T, U>::size_type,
351
                                              typename bit_iterator_adapter<V, W>::size_type>::type;
352
  using difference_type = typename std::common_type<typename bit_iterator_adapter<T, U>::difference_type,
353
                                                    typename bit_iterator_adapter<V, W>::difference_type>::type;
354
  constexpr size_type lhs_ratio = bit_iterator_adapter<T, U>::ratio;
355
  constexpr size_type rhs_ratio = bit_iterator_adapter<V, W>::ratio;
356
  static_assert(lhs_ratio == rhs_ratio, "");
357
  const difference_type main = lhs._current - rhs._current;
358
  return main * lhs_ratio + (lhs._position - rhs._position);
359
}
360

361
//static_assert(bit_iterator_adapter_c<bit_iterator_adapter<uint8_t*>>, "bit_iterator_adapter does not satisfy bit_iterator_adapter_c concept!");
362
//static_assert(bit_pointer_c<bit_pointer<uint8_t>, bit_reference<uint8_t>>, "bit_pointer does not satisfy bit_pointer_c concept!");
363
//static_assert(bit_iterator_adapter_c<bit_pointer<uint8_t>>, "bit_pointer does not satisfy bit_iterator_adapter_c concept!");
364

365
// ========================================================================== //
366
} // namespace bit
367
#endif // _BIT_ITERATOR_ADAPTER_HPP_INCLUDED
368
// ========================================================================== //
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc