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

PeterCDMcLean / BitLib / 15599073802

12 Jun 2025 01:00AM UTC coverage: 53.427% (+0.6%) from 52.785%
15599073802

Pull #16

github

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

10022 of 18552 branches covered (54.02%)

Branch coverage included in aggregate %.

724 of 745 new or added lines in 20 files covered. (97.18%)

3 existing lines in 2 files now uncovered.

5831 of 11120 relevant lines covered (52.44%)

4634541.42 hits per line

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

56.65
/include/bitlib/bit-iterator/bit_iterator.hpp
1
// ============================== BIT ITERATOR ============================== //
2
// Project:         The C++ Bit Library
3
// Name:            bit_iterator.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_HPP_INCLUDED
10
#define _BIT_ITERATOR_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 <class Iterator>
35
class bit_iterator
36
{
37
  template <class>
38
  friend class bit_iterator;
39

40
  // Assertions
41
 private:
42
  using _traits_t = _cv_iterator_traits<Iterator>;
43
  static_assert(binary_digits<std::iter_value_t<Iterator>>::value, "");
44

45
  // Types
46
 public:
47
  using iterator_type = Iterator;
48
  using word_type = std::iter_value_t<Iterator>;
49
  using iterator_category = typename _traits_t::iterator_category;
50
  using value_type = bit_value;
51
  using difference_type = std::ptrdiff_t;
52
  using pointer = bit_pointer<word_type>;
53
  using reference = bit_reference<typename _traits_t::reference>;  // typename _traits_t::reference;
54
  using size_type = std::size_t;
55
  using mask_type = std::make_unsigned_t<std::remove_cv_t<word_type>>;
56

57
  // Lifecycle
58
 public:
59
  constexpr bit_iterator();
60
  constexpr bit_iterator(const bit_iterator<Iterator>& other);
61
  template <class T>
62
  constexpr bit_iterator(const bit_iterator<T>& other)
63
    requires std::constructible_from<iterator_type, T>;
64
  explicit constexpr bit_iterator(iterator_type i);
65
  constexpr bit_iterator(iterator_type i, size_type pos);
66
  explicit constexpr bit_iterator(const pointer& ptr)
67
    requires std::constructible_from<iterator_type, word_type*>;
68

69
  // Assignment
70
 public:
71
  constexpr bit_iterator& operator=(const bit_iterator<Iterator>& other);
72
  template <class T>
73
  constexpr bit_iterator& operator=(const bit_iterator<T>& other);
74

75
  // Access
76
 public:
77
  constexpr reference operator*() const noexcept;
78
  constexpr pointer operator->() const noexcept;
79
  constexpr reference operator[](difference_type n) const;
80

81
  // Increment and decrement operators
82
 public:
83
  constexpr bit_iterator& operator++();
84
  constexpr bit_iterator& operator--();
85
  constexpr bit_iterator operator++(int);
86
  constexpr bit_iterator operator--(int);
87
  constexpr bit_iterator operator+(difference_type n) const;
88
  constexpr bit_iterator operator-(difference_type n) const;
89
  constexpr bit_iterator& operator+=(difference_type n);
90
  constexpr bit_iterator& operator-=(difference_type n);
91
  constexpr difference_type operator-(const bit_iterator&) const;
92

93
  // Underlying details
94
 public:
95
  constexpr iterator_type base() const;
96
  constexpr iterator_type address() const;
97
  constexpr size_type position() const noexcept;
98

99
  auto operator<=>(const bit_iterator&) const = default;
100
  // Implementation details: data members
101
 private:
102
  iterator_type _current;
103
  size_type _position;
104

105
  // Non-member arithmetic operators
106
  template <class T>
107
  friend constexpr bit_iterator<T> operator+(
108
      typename bit_iterator<T>::difference_type n,
109
      const bit_iterator<T>& i);
110
  template <class T, class U>
111
  friend constexpr typename std::common_type<
112
      typename bit_iterator<T>::difference_type,
113
      typename bit_iterator<U>::difference_type>::type
114
  operator-(
115
      const bit_iterator<T>& lhs,
116
      const bit_iterator<U>& rhs);
117
};
118
/* ************************************************************************** */
119

120

121

122
// ------------------------ BIT ITERATOR: LIFECYCLE ------------------------- //
123
// Implicitly default constructs a bit iterator
124
template <class Iterator>
125
constexpr bit_iterator<Iterator>::bit_iterator()
126
    : _current(), _position() {
127
}
128

129
// Implicitly constructs a bit iterator from another bit iterator
130
template <class Iterator>
131
constexpr bit_iterator<Iterator>::bit_iterator(const bit_iterator<Iterator>& other)
7,466,607✔
132
    : _current(other.base()), _position(other.position()) {
15,611,451✔
133
  assert(_position < bitsof<word_type>());
15,611,451!
134
}
15,611,451✔
135

136
template <class Iterator>
137
template <class T>
138
constexpr bit_iterator<Iterator>::bit_iterator(const bit_iterator<T>& other)
51,744✔
139
  requires std::constructible_from<iterator_type, T>
140
    : _current(other.base()), _position(other.position()) {
102,797✔
141
  assert(_position < bitsof<word_type>());
102,797!
142
}
102,797✔
143

144
// Explicitly constructs an aligned bit iterator from an iterator
145
template <class Iterator>
146
constexpr bit_iterator<Iterator>::bit_iterator(const iterator_type i)
12,897,004✔
147
    : _current(i), _position(0) {
25,795,270✔
148
}
25,795,270✔
149

150
// Explicitly constructs an unaligned bit iterator from an iterator
151
template <class Iterator>
152
constexpr bit_iterator<Iterator>::bit_iterator(const iterator_type i, size_type pos)
1,593,337✔
153
    : _current(i), _position((assert(pos < binary_digits<word_type>::value), pos)) {
3,429,648!
154
}
3,429,648✔
155

156
// Explicitly constructs an unaligned bit iterator from a pointer
157
template <class Iterator>
158
constexpr bit_iterator<Iterator>::bit_iterator(const pointer& ptr)
255✔
159
  requires std::constructible_from<iterator_type, word_type*>
160
    : _current(ptr._current), _position(ptr.position()) {
554✔
161
  assert(_position < bitsof<word_type>());
554!
162
}
554✔
163
// -------------------------------------------------------------------------- //
164

165

166

167
// ------------------------ BIT ITERATOR: ASSIGNMENT ------------------------ //
168
// Assigns a bit iterator to the bit iterator
169
template <class Iterator>
170
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator=(
112,333✔
171
    const bit_iterator<Iterator>& other) {
122,101✔
172
  _current = other._current;
234,434✔
173
  _position = other._position;
234,434✔
174
  assert(_position < bitsof<word_type>());
234,434!
175
  return *this;
234,434✔
176
}
122,101✔
177

178
// Assigns a bit iterator to the bit iterator
179
template <class Iterator>
180
template <class T>
181
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator=(
182
    const bit_iterator<T>& other) {
183
  _current = other._current;
184
  _position = other._position;
185
  assert(_position < bitsof<word_type>());
186
  return *this;
187
}
188
// -------------------------------------------------------------------------- //
189

190

191

192
// -------------------------- BIT ITERATOR: ACCESS -------------------------- //
193
// Gets a bit reference from the bit iterator
194
template <class Iterator>
195
constexpr typename bit_iterator<Iterator>::reference
196
bit_iterator<Iterator>::operator*() const noexcept {
4,294,967,294✔
197
  return reference(*_current, _position);
4,294,967,294✔
198
}
2,147,483,647✔
199

200
// Gets a pointer to a bit
201
template <class Iterator>
202
constexpr typename bit_iterator<Iterator>::pointer bit_iterator<Iterator>::operator->() const noexcept {
203
  return pointer(&*_current, _position);
204
}
205

206
// Gets a bit reference, decrementing or incrementing the iterator
207
template <class Iterator>
208
constexpr typename bit_iterator<Iterator>::reference bit_iterator<Iterator>::operator[](difference_type n) const {
22,486,897✔
209
  constexpr difference_type digits = binary_digits<word_type>::value;
22,486,897✔
210
  const difference_type sum = _position + n;
22,486,897✔
211
  difference_type diff = sum / digits;
22,486,897✔
212
  if (sum < 0 && diff * digits != sum) {
22,486,897!
UNCOV
213
    --diff;
×
214
  }
215
  return reference(*std::next(_current, diff), sum - diff * digits);
44,973,345✔
216
}
11,243,673✔
217
// -------------------------------------------------------------------------- //
218

219

220

221
// ------------- BIT ITERATOR: INCREMENT AND DECREMENT OPERATORS ------------ //
222
// Increments the bit iterator and returns it
223
template <class Iterator>
224
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator++() {
4,294,967,294✔
225
  constexpr size_type digits = binary_digits<word_type>::value;
4,294,967,294✔
226
  if (_position + 1 < digits) {
4,294,967,294!
227
    ++_position;
4,294,967,294✔
228
  } else {
2,147,483,647✔
229
    ++_current;
171,151,679✔
230
    _position = 0;
171,151,679✔
231
  }
85,467,496✔
232
  return *this;
4,294,967,294✔
233
}
2,147,483,647✔
234

235
// Decrements the bit iterator and returns it
236
template <class Iterator>
237
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator--() {
238
  constexpr size_type digits = binary_digits<word_type>::value;
239
  if (_position) {
240
    --_position;
241
  } else {
242
    --_current;
243
    _position = digits - 1;
244
  }
245
  return *this;
246
}
247

248
// Increments the bit iterator and returns the old one
249
template <class Iterator>
250
constexpr bit_iterator<Iterator> bit_iterator<Iterator>::operator++(int) {
251
  bit_iterator old = *this;
252
  ++(*this);
253
  return old;
254
}
255

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

264
// Looks forward several bits and gets an iterator at this position
265
template <class Iterator>
266
constexpr bit_iterator<Iterator> bit_iterator<Iterator>::operator+(difference_type n) const {
2,187,016✔
267
  constexpr difference_type digits = binary_digits<word_type>::value;
2,187,016✔
268
  const difference_type sum = _position + n;
2,187,016✔
269
  difference_type diff = sum / digits;
2,187,016✔
270
  if (sum < 0 && diff * digits != sum) {
2,187,016!
UNCOV
271
    --diff;
×
272
  }
273
  return bit_iterator(std::next(_current, diff), sum - diff * digits);
4,397,338✔
274
}
1,081,855✔
275

276
// Looks backward several bits and gets an iterator at this position
277
template <class Iterator>
278
constexpr bit_iterator<Iterator> bit_iterator<Iterator>::operator-(difference_type n) const {
920,601✔
279
  constexpr difference_type digits = binary_digits<word_type>::value;
920,601✔
280
  const difference_type sum = _position - n;
920,601✔
281
  difference_type diff = sum / digits;
920,601✔
282
  if (sum < 0 && diff * digits != sum) {
920,601✔
283
    --diff;
709,626✔
284
  }
487,983✔
285
  return bit_iterator(std::next(_current, diff), sum - diff * digits);
1,575,139✔
286
}
593,332✔
287

288
// Increments the iterator by several bits and returns it
289
template <class Iterator>
290
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator+=(difference_type n) {
1,968,240✔
291
  constexpr difference_type digits = binary_digits<word_type>::value;
1,968,240✔
292
  const difference_type sum = _position + n;
1,968,240✔
293
  difference_type diff = sum / digits;
1,968,240✔
294
  if (sum < 0 && diff * digits != sum) {
1,968,240!
295
    --diff;
525,362✔
296
  }
393,922✔
297
  _current = std::next(_current, diff);
3,193,433✔
298
  _position = (sum - diff * digits);
1,968,240✔
299
  return *this;
3,193,433✔
300
}
743,047✔
301

302
// Decrements the iterator by several bits and returns it
303
template <class Iterator>
304
constexpr bit_iterator<Iterator>& bit_iterator<Iterator>::operator-=(difference_type n) {
281,092✔
305
  constexpr difference_type digits = binary_digits<word_type>::value;
281,092✔
306
  const difference_type sum = _position - n;
281,092✔
307
  difference_type diff = sum / digits;
281,092✔
308
  if (sum < 0 && diff * digits != sum) {
281,092✔
309
    --diff;
196,971✔
310
  }
97,488✔
311
  _current = std::next(_current, diff);
423,506✔
312
  _position = (sum - diff * digits);
281,092✔
313
  return *this;
423,506✔
314
}
138,678✔
315
// -------------------------------------------------------------------------- //
316

317
template <class Iterator>
318
constexpr bit_iterator<Iterator>::difference_type
319
bit_iterator<Iterator>::operator-(const bit_iterator<Iterator>& other) const {
2,020,836✔
320
  constexpr difference_type digits = binary_digits<word_type>::value;
2,020,836✔
321
  return (_current - other._current) * digits + (_position - other._position);
2,020,836✔
322
}
1,002,680✔
323

324
// -------------------- BIT ITERATOR: UNDERLYING DETAILS -------------------- //
325
// Returns a copy of the underlying iterator
326
template <class Iterator>
327
constexpr typename bit_iterator<Iterator>::iterator_type bit_iterator<Iterator>::base() const {
66,195,299✔
328
  return _current;
66,195,299✔
329
}
33,753,650✔
330

331
template <class Iterator>
332
constexpr typename bit_iterator<Iterator>::iterator_type bit_iterator<Iterator>::address() const {
333
  return _current;
334
}
335

336
// Returns the position of the bit within the underlying word
337
template <class Iterator>
338
constexpr typename bit_iterator<Iterator>::size_type bit_iterator<Iterator>::position() const noexcept {
45,722,293✔
339
  return _position;
45,722,293✔
340
}
22,771,287✔
341

342
// -------------- BIT ITERATOR: NON-MEMBER ARITHMETIC OPERATORS ------------- //
343
// Advances the bit iterator several times
344
template <class T>
345
constexpr bit_iterator<T> operator+(typename bit_iterator<T>::difference_type n, const bit_iterator<T>& i) {
346
  return i + n;
347
}
348

349
// Computes the distance in bits separating two bit iterators
350
template <class T, class U>
351
constexpr typename std::common_type<
352
    typename bit_iterator<T>::difference_type,
353
    typename bit_iterator<U>::difference_type>::type
354
operator-(const bit_iterator<T>& lhs, const bit_iterator<U>& rhs) {
355
  using lhs_utype = typename bit_iterator<T>::word_type;
356
  using rhs_utype = typename bit_iterator<U>::word_type;
357
  using lhs_type = typename bit_iterator<T>::difference_type;
358
  using rhs_type = typename bit_iterator<U>::difference_type;
359
  using difference_type = typename std::common_type<lhs_type, rhs_type>::type;
360
  constexpr difference_type lhs_digits = binary_digits<lhs_utype>::value;
361
  constexpr difference_type rhs_digits = binary_digits<rhs_utype>::value;
362
  constexpr difference_type digits = rhs_digits;
363
  static_assert(lhs_digits == rhs_digits, "");
364
  const difference_type main = lhs._current - rhs._current;
365
  return main * digits + (lhs._position - rhs._position);
366
}
367

368
static_assert(bit_iterator_c<bit_iterator<uint8_t*>>, "bit_iterator does not satisfy bit_iterator_c concept!");
369
static_assert(bit_pointer_c<bit_pointer<uint8_t>, bit_reference<uint8_t&>>, "bit_pointer does not satisfy bit_pointer_c concept!");
370
static_assert(bit_iterator_c<bit_pointer<uint8_t>>, "bit_pointer does not satisfy bit_iterator_c concept!");
371

372
// ========================================================================== //
373
} // namespace bit
374
#endif // _BIT_ITERATOR_HPP_INCLUDED
375
// ========================================================================== //
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