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

PeterCDMcLean / BitLib / 15624655410

13 Jun 2025 01:54AM UTC coverage: 53.519% (+0.7%) from 52.785%
15624655410

push

github

web-flow
Small buffer optimization (#16)

* Remove alignment. Expose algorithm issues with differing types

* Add iterator adapter class (big to small)

* Use new iterator adapter. Set more default words to uintptr_t

* Add dispatch to workflow trigger options

* Dummy change

* Try rerranging

* Remove distinct iterator adapter test target

* Try GLIBCXX_RELEASE macro

* Fix type for test

* bit_reference now templated on ref type to allow for it to wrap proxy references

* Now with proxy reference and proxy pointer

* Fix some ops

* Remove wider_t narrower_t

* Small buffer optimized dynamic bit array

* Clean up more of bit_details

* small improvement to bitsof

* Don't measure coverage on tests (too error prone)

* Adapter prelude wip

* Add test for mixed type equals

* Adapted copy

* Test adapted copy

* Fix conversion from adapter back to iterator

* Remove unnecessary return type template parameter

10266 of 19000 branches covered (54.03%)

Branch coverage included in aggregate %.

771 of 792 new or added lines in 20 files covered. (97.35%)

1 existing line in 1 file now uncovered.

5880 of 11169 relevant lines covered (52.65%)

4735435.26 hits per line

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

87.5
/include/bitlib/bit-containers/bit_array_dynamic_extent.hpp
1
// ================================= BIT_ARRAY =================================== //
2
// Project:     The Experimental Bit Algorithms Library
3
// \file        bit_array.hpp
4
// Description: Implementation of bit_array
5
// Creator:     Vincent Reverdy
6
// Contributor: Peter McLean [2025]
7
// License:     BSD 3-Clause License
8
// ========================================================================== //
9
#ifndef _BIT_ARRAY_DYNAMIC_EXTENT_HPP_INCLUDED
10
#define _BIT_ARRAY_DYNAMIC_EXTENT_HPP_INCLUDED
11

12
#include <algorithm>
13
#include <cstddef>
14
#include <cstring>  // memcpy
15
#include <initializer_list>
16
#include <memory>
17
#include <new>
18
#include <span>  // std::dynamic_extent
19
#include <stdexcept>
20

21
#include "bitlib/bit-algorithms/bit_algorithm.hpp"
22
#include "bitlib/bit-containers/bit_array.hpp"
23
#include "bitlib/bit-containers/bit_array_base.hpp"
24
#include "bitlib/bit-containers/bit_bitsof.hpp"
25
#include "bitlib/bit-containers/bit_span.hpp"
26
#include "bitlib/bit-iterator/bit.hpp"
27
#include "bitlib/bit_concepts.hpp"
28

29
namespace bit {
30
namespace detail {
31
template <typename value_type, typename word_type>
32
using bit_array_it = typename std::conditional<std::is_same_v<value_type, bit_value>,
33
                                               bit_iterator<word_type*>,
34
                                               word_type*>::type;
35
template <typename value_type, typename word_type>
36
using bit_array_cit = typename std::conditional<std::is_same_v<value_type, bit_value>,
37
                                                bit_iterator<const word_type*>,
38
                                                const word_type*>::type;
39
}  // namespace detail
40
template <typename T, typename W>
41
class bit_array<T, std::dynamic_extent, W>
42
    : public bit_array_base<bit_array<T, std::dynamic_extent, W>, T, std::dynamic_extent, W, detail::bit_array_it<T, W>, detail::bit_array_cit<T, W>> {
43
 public:
44
  using base = bit_array_base<bit_array<T, std::dynamic_extent, W>, T, std::dynamic_extent, W, detail::bit_array_it<T, W>, detail::bit_array_cit<T, W>>;
45
  using base::end;
46
  using typename base::const_iterator;
47
  using typename base::const_pointer;
48
  using typename base::const_reference;
49
  using typename base::difference_type;
50
  using typename base::iterator;
51
  using typename base::pointer;
52
  using typename base::reference;
53
  using typename base::size_type;
54
  using typename base::value_type;
55
  using typename base::word_type;
56

57
 private:
58
  using word_type_ptr = std::unique_ptr<word_type[]>;
59
  static const size_type FixedWords = sizeof(word_type_ptr) / sizeof(word_type);
60
  static const size_type FixedBits = FixedWords * bitsof<word_type>();
61

62
  const size_type m_size;
63

64
  union Storage {
65
    word_type_ptr pointer;
66
    word_type fixed[FixedWords];
67

68
    Storage(size_type words) {
98✔
69
      if (words > FixedWords) {
98!
70
        new (&pointer) word_type_ptr(new word_type[words]);
8✔
71
      } else {
45✔
72
        for (size_type i = 0; i < words; ++i) {
182✔
73
          new (&fixed[i]) word_type();
92✔
74
        }
46✔
75
      }
45✔
76
    }
98✔
77

78
    Storage(size_type words, Storage&& other) {
8✔
79
      if (words > FixedWords) {
8!
NEW
80
        new (&pointer) word_type_ptr(std::move(other.pointer));
×
NEW
81
        other.pointer = nullptr;  // Prevent double deletion
×
82
      } else {
4✔
83
        for (size_type i = 0; i < words; ++i) {
16✔
84
          new (&fixed[i]) word_type(std::move(other.fixed[i]));
8✔
85
        }
4✔
86
      }
4✔
87
    }
8✔
88

89
    Storage(size_type words, const Storage& other) {
4✔
90
      if (words > FixedWords) {
4!
NEW
91
        new (&pointer) word_type_ptr(new word_type[words]);
×
NEW
92
        std::memcpy(pointer.get(), other.pointer.get(), words * sizeof(word_type));
×
93
      } else {
2✔
94
        for (size_type i = 0; i < words; ++i) {
8✔
95
          new (&fixed[i]) word_type(other.fixed[i]);
4✔
96
        }
2✔
97
      }
2✔
98
    }
4✔
99
    template <typename U>
100
    Storage(size_type words, const U& val) {
101
      if (words > FixedWords) {
102
        new (&pointer) word_type_ptr(new word_type[words](val));
103
      } else {
104
        for (size_type i = 0; i < words; ++i) {
105
          new (&fixed[i]) word_type(val);
106
        }
107
      }
108
    }
109
    Storage() = delete;
110
    ~Storage() {}
165✔
111
  } storage;
112

113
  static constexpr size_type Words(size_type N) {
332✔
114
    return (N * bitsof<value_type>() + bitsof<word_type>() - 1) / bitsof<word_type>();
332✔
115
  };
166✔
116
  /*
117
  constexpr size_type Words() const {
118
    return Words(m_size);
119
  }*/
120

121
 public:
122
  ~bit_array() {
110✔
123
    if (size() > FixedBits) {
110!
124
      storage.pointer.~unique_ptr();
8✔
125
    } else {
51✔
126
      for (size_type i = 0; i < Words(size()); ++i) {
206✔
127
        storage.fixed[i].~word_type();
104✔
128
      }
52✔
129
    }
51✔
130
  }
110✔
131

132
  /*
133
  * Constructors, copies and moves...
134
  */
135
  bit_array() = delete;
136

137
  constexpr bit_array(const size_type size)
27✔
138
      : m_size(size), storage(Words(size)) {
54✔
139
  }
54✔
140

141
  template <std::integral U>
142
  constexpr bit_array(const size_type size, const U& integral)
143
      : bit_array(size) {
144
    assert(bitsof<U>() <= size);
145
    if (size() > FixedBits) {
146
      std::memcpy(storage.pointer, &integral, sizeof(integral));
147
    } else {
148
      std::memcpy(storage.fixed, &integral, sizeof(integral));
149
    }
150
    bool sign_extend = false;
151
    if constexpr (std::is_signed_v<U>) {
152
      sign_extend = (integral & (1 << (bitsof<U>() - 1))) ? true : false;
153
    }
154
    if (sign_extend) {
155
      for (auto it = begin() + bitsof<U>(); it != end(); ++it) {
156
        *it = bit1;
157
      }
158
    } else {
159
      for (auto it = begin() + bitsof<U>(); it != end(); ++it) {
160
        *it = bit0;
161
      }
162
    }
163
  }
164

165
  constexpr bit_array(const size_type size, const word_type val)
166
      : m_size(size), storage(Words(size), val) {
167
  }
168

169
  constexpr bit_array(const size_type size, const value_type bit_val)
22✔
170
    requires(!std::is_same<value_type, word_type>::value)
171
      : m_size(size), storage(Words(size)) {
44✔
172
    this->fill(bit_val);
44✔
173
  }
44✔
174

175
  constexpr bit_array(const bit_array<T, std::dynamic_extent, W>& other)
2✔
176
      : m_size(other.size()), storage(Words(size()), other.storage) {
4✔
177
  }
4✔
178

179
  constexpr bit_array(const bit_sized_range auto& other)
180
      : bit_array(other.size()) {
181
    ::bit::copy(other.begin(), other.end(), this->begin());
182
  }
183

184
  constexpr bit_array(bit_array<T, std::dynamic_extent, W>&& other)
4✔
185
      : m_size(other.size()), storage(Words(size()), std::move(other.storage)) {
8✔
186
  }
8✔
187

188
  constexpr bit_array(const std::initializer_list<value_type> init)
12✔
189
    requires(!std::is_same_v<value_type, word_type>)
190
      : bit_array(init.size()) {
24✔
191
    std::copy(init.begin(), init.end(), this->begin());
24✔
192
  }
24✔
193

194
#if 0
195
  No known conversion from bool to bit_value
196
  bit_value has explicit constructor from bool to bit_value so this doesnt work
197
  constexpr bit_array<std::dynamic_extent,W>::bit_array(const std::initializer_list<bool> init)
198
      : storage(std::make_unique<word_type[]>(Words(init.size()))),
199
        m_size(init.size()) {
200
    std::copy(init.begin(), init.end(), this->begin());
201
  }
202
#endif
203

204
  template <typename U>
205
  constexpr bit_array(const std::initializer_list<U> init)
1✔
206
      : bit_array(bitsof<U>() * init.size()) {
2✔
207
    std::copy(init.begin(), init.end(), data());
2✔
208
  }
2✔
209

210
  constexpr bit_array(const std::string_view s)
2✔
211
    requires(std::is_same_v<value_type, bit_value>)
212
      : bit_array((std::count(s.begin(), s.end(), '0') + std::count(s.begin(), s.end(), '1'))) {
4✔
213
    size_type i = 0;
4✔
214
    for (char c : s) {
32✔
215
      if (c == '0') {
30✔
216
        begin()[i++] = bit0;
14✔
217
      } else if (c == '1') {
16!
218
        begin()[i++] = bit1;
16✔
219
      }
8✔
220
    }
15✔
221
  }
4✔
222

223
  /*
224
   * Assignment
225
   */
226
  constexpr bit_array<T, std::dynamic_extent, W>& operator=(const bit_array<T, std::dynamic_extent, W>& other) {
6✔
227
    if (nullptr == data() || size() != other.size()) {
6!
228
      throw std::invalid_argument("Cannot reassign bit_array<std::dynamic_extent,V,W> size");
4✔
229
    }
2✔
230
    if (this == &other) [[unlikely]] {
2!
NEW
231
      return *this;
×
232
    }
233
    std::copy(other.begin(), other.end(), this->begin());
2✔
234
    return *this;
2✔
235
  }
1✔
236

237
  constexpr bit_array<T, std::dynamic_extent, W>& operator=(const bit_sized_range auto& other) {
4✔
238
    if (other.size() != this->size()) [[unlikely]] {
4✔
239
      throw std::invalid_argument("other bit_range contains an invalid number of bits for bit_array.");
2✔
240
    }
1✔
241
    ::bit::copy(other.begin(), other.end(), this->begin());
2✔
242
    return *this;
3✔
243
  };
2✔
244

245
  constexpr bit_array<T, std::dynamic_extent, W>& operator=(bit_array<T, std::dynamic_extent, W>&& other) {
8✔
246
    if (nullptr == data() || size() != other.size()) {
8!
247
      throw std::invalid_argument("Cannot reassign bit_array<std::dynamic_extent,V,W> size");
2✔
248
    }
1✔
249
    bit_array<T, std::dynamic_extent, W> temp(std::move(other));
6✔
250
    swap(temp);
6✔
251
    return *this;
9✔
252
  }
7✔
253

254
  /*
255
   * Element Access
256
   */
257
  constexpr word_type* data() noexcept {
36✔
258
    if (size() > FixedBits) {
36!
NEW
259
      return storage.pointer.get();
×
260
    } else {
18✔
261
      return storage.fixed;
36✔
262
    }
18✔
263
  }
18✔
264

265
  constexpr const word_type* data() const noexcept {
266
    if (size() > FixedBits) {
267
      return storage.pointer.get();
268
    } else {
269
      return storage.fixed;
270
    }
271
  }
272

273
  /*
274
   * Iterators
275
   */
276
  constexpr iterator begin() noexcept {
1,702✔
277
    if (size() > FixedBits) {
1,702!
278
      return iterator(storage.pointer.get());
842✔
279
    } else {
430✔
280
      return iterator(storage.fixed);
860✔
281
    }
430✔
282
  }
851✔
283

284
  constexpr const_iterator begin() const noexcept {
44✔
285
    if (size() > FixedBits) {
44!
NEW
286
      return const_iterator(storage.pointer.get());
×
287
    } else {
22✔
288
      return const_iterator(storage.fixed);
44✔
289
    }
22✔
290
  }
22✔
291

292
  /*
293
   * Capacity
294
   */
295
  constexpr size_type size() const noexcept {
2,620✔
296
    return m_size;
2,620✔
297
  }
1,310✔
298

299
  /*
300
   * Operations
301
   */
302
  constexpr void swap(bit_array<T, std::dynamic_extent, W>& other) noexcept {
8✔
303
    assert(size() == other.size());
8!
304
    if (size() > FixedBits) {
8!
NEW
305
      std::swap(this->storage.pointer, other.storage.pointer);
×
306
    } else {
4✔
307
      for (size_type i = 0; i < Words(size()); ++i) {
16✔
308
        std::swap(this->storage.fixed[i], other.storage.fixed[i]);
8✔
309
      }
4✔
310
    }
4✔
311
  }
8✔
312
};
313

314
static_assert(bit_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_range concept!");
315
static_assert(bit_sized_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_sized_range concept!");
316
#ifdef CONTIGUOUS_RANGE
317
static_assert(bit_contiguous_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_range concept!");
318
static_assert(bit_contiguous_sized_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_sized_range concept!");
319
#endif
320

321
// ========================================================================== //
322
}  // namespace bit
323

324
#endif  // _BIT_ARRAY_DYNAMIC_EXTENT_HPP_INCLUDED
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