14949319596

Committed 10 May 2025 09:32PM UTC coverage: 96.898% (-0.1%) from 97.036%

Build # 14949319596

Build Type

Pull #8

github

Committed by

web-flow

Commit Message

Merge 153e605bc into a837637fd

Pull Request Pull Request #8: Common bit array base

Run Details

171 of 179 new or added lines in 5 files covered. (95.53%)

1 existing line in 1 file now uncovered.

1312 of 1354 relevant lines covered (96.9%)

16164538.6 hits per line

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

96.84

/include/bitlib/bit-containers/bit_array_dynamic_extent.hpp

// ================================= BIT_ARRAY =================================== //
// Project:     The Experimental Bit Algorithms Library
// \file        bit_array.hpp
// Description: Implementation of bit_array
// Creator:     Vincent Reverdy
// Contributor: Peter McLean [2025]
// License:     BSD 3-Clause License
// ========================================================================== //
#ifndef _BIT_ARRAY_DYNAMIC_EXTENT_HPP_INCLUDED
#define _BIT_ARRAY_DYNAMIC_EXTENT_HPP_INCLUDED

#include <algorithm>
#include <cstddef>
#include <cstring>  // memcpy
#include <initializer_list>
#include <memory>
#include <new>
#include <span>  // std::dynamic_extent
#include <stdexcept>

#include "bitlib/bit-algorithms/bit_algorithm.hpp"
#include "bitlib/bit-containers/bit_array.hpp"
#include "bitlib/bit-containers/bit_array_base.hpp"
#include "bitlib/bit-containers/bit_bitsof.hpp"
#include "bitlib/bit-containers/bit_span.hpp"
#include "bitlib/bit-iterator/bit.hpp"

namespace bit {
namespace detail {
template <typename value_type, typename word_type>
using bit_array_it = typename std::conditional<std::is_same_v<value_type, bit_value>,
                                               bit_iterator<word_type*>,
                                               word_type*>::type;
template <typename value_type, typename word_type>
using bit_array_cit = typename std::conditional<std::is_same_v<value_type, bit_value>,
                                                bit_iterator<const word_type*>,
                                                const word_type*>::type;
}  // namespace detail
template <typename T, std::align_val_t V, typename W>
class bit_array<T, std::dynamic_extent, V, W>
    : public bit_array_base<bit_array<T, std::dynamic_extent, V, W>, T, W, detail::bit_array_it<T, W>, detail::bit_array_cit<T, W>> {
 public:
  using base = bit_array_base<bit_array<T, std::dynamic_extent, V, W>, T, W, detail::bit_array_it<T, W>, detail::bit_array_cit<T, W>>;
  using typename base::const_iterator;
  using typename base::const_pointer;
  using typename base::const_reference;
  using typename base::difference_type;
  using typename base::iterator;
  using typename base::pointer;
  using typename base::reference;
  using typename base::size_type;
  using typename base::value_type;
  using typename base::word_type;

 private:
  struct deleter {
    size_type words;
    void operator()(word_type* const p) const {
      for (size_type i = 0; i < words; ++i) {
        (p + i)->~word_type();
      }
      ::operator delete(p, V);
    }
  };

  const size_type m_size;
  const std::unique_ptr<word_type[], deleter> storage;

 protected:
  static constexpr size_type Words(size_type N) {
    return (N * bitsof<value_type>() + bitsof<word_type>() - 1) / bitsof<word_type>();
  };

 private:
  static constexpr size_t AlignedBytes(size_t N) {
    return (Words(N) * sizeof(word_type) + static_cast<size_t>(V) - 1) & ~(static_cast<size_t>(V) - 1);
  };

 public:
  /*
  * Constructors, copies and moves...
  */
  bit_array() = delete;

  constexpr bit_array(const size_type size)
      : m_size(size),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    //std::uninitialized_fill_n(this->begin(), Words(m_size), word_type());
    for (size_type i = 0; i < Words(m_size); ++i) {
      new (storage.get() + i) word_type();
    }
  }

  template <std::integral U>
  constexpr bit_array(const size_type size, const U& integral)
      : m_size(size),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    assert(bitsof<U>() <= size);
    for (size_type i = 0; i < Words(m_size); ++i) {
      new (storage.get() + i) word_type();
    }
    std::memcpy(storage.get(), &integral, sizeof(integral));
    bool sign_extend = false;
    if constexpr (std::is_signed_v<U>) {
      sign_extend = (integral & (1 << (bitsof<U>() - 1))) ? true : false;
    }
    if (sign_extend) {
      for (auto it = begin() + bitsof<U>(); it != end(); ++it) {
        *it = bit1;
      }
    } else {
      for (auto it = begin() + bitsof<U>(); it != end(); ++it) {
        *it = bit0;
      }
    }
  }

  constexpr bit_array(const size_type size, const value_type bit_val)
      : m_size(size),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    if constexpr (std::is_same<value_type, word_type>::value) {
      for (size_type i = 0; i < Words(m_size); ++i) {
        new (storage.get() + i) word_type(bit_val);
      }
    } else {
      for (size_type i = 0; i < Words(m_size); ++i) {
        new (storage.get() + i) word_type();
      }
      this->fill(bit_val);
    }
  }

  constexpr bit_array(const bit_array<T, std::dynamic_extent, V, W>& other)
      : m_size(other.size()),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    for (size_type i = 0; i < Words(m_size); ++i) {
      new (storage.get() + i) word_type(*(other.storage.get() + i));
    }
  }

  constexpr bit_array(const bit_array<T, std::dynamic_extent, V, W>&& other)
      : m_size(other.size()),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    for (size_type i = 0; i < Words(m_size); ++i) {
      new (storage.get() + i) word_type(*(other.storage.get() + i));
    }
  }

  constexpr bit_array(const std::initializer_list<value_type> init)
    requires(!std::is_same_v<value_type, word_type>)
      : m_size(init.size()),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    for (size_type i = 0; i < Words(m_size); ++i) {
      new (storage.get() + i) word_type();
    }
    std::copy(init.begin(), init.end(), this->begin());
  }

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

  constexpr bit_array(const std::initializer_list<word_type> init)
      : m_size(bitsof<word_type>() * init.size()),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    size_type i = 0;
    auto it = init.begin();
    for (; i < Words(m_size) && it != init.end(); ++i, ++it) {
      new (storage.get() + i) word_type(*it);
    }
    // Initialize remaining words if any
    for (; i < Words(m_size); ++i) {
      new (storage.get() + i) word_type();
    }
  }

  constexpr bit_array(const std::string_view s)
    requires(std::is_same_v<value_type, bit_value>)
      : m_size((std::count(s.begin(), s.end(), '0') + std::count(s.begin(), s.end(), '1'))),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    for (size_type i = 0; i < Words(m_size); ++i) {
      new (storage.get() + i) word_type();
    }
    size_type i = 0;
    for (char c : s) {
      if (c == '0') {
        begin()[i++] = bit0;
      } else if (c == '1') {
        begin()[i++] = bit1;
      }
    }
  }

  ~bit_array() = default;

  /*
   * Assignment
   */
  constexpr bit_array<T, std::dynamic_extent, V, W>& operator=(const bit_array<T, std::dynamic_extent, V, W>& other) {
    if (nullptr == storage.get() || m_size != other.m_size) {
      throw std::invalid_argument("Cannot reassign bit_array<std::dynamic_extent,V,W> size");
    }
    std::copy(other.begin(), other.end(), this->begin());
    return *this;
  }

  constexpr bit_array<T, std::dynamic_extent, V, W>& operator=(bit_array<T, std::dynamic_extent, V, W>&& other) {
    if (nullptr == storage.get() || m_size != other.m_size) {
      throw std::invalid_argument("Cannot reassign bit_array<std::dynamic_extent,V,W> size");
    }
    std::copy(other.begin(), other.end(), this->begin());
    return *this;
  }

  /*
   * Element Access
   */
  constexpr word_type* data() noexcept {
    return size() ? storage.get() : nullptr;
  }

  constexpr const word_type* data() const noexcept {
    return size() ? storage.get() : nullptr;
  }

  /*
   * Iterators
   */
  constexpr iterator begin() noexcept {
    return iterator(storage.get());
  }

  constexpr iterator end() noexcept {
    return begin() + size();
  }

  constexpr const_iterator begin() const noexcept {
    return const_iterator(storage.get());
  }

  constexpr const_iterator end() const noexcept {
    return const_iterator(storage.get()) + size();
  }

  constexpr const_iterator cbegin() const noexcept {
    return const_iterator(storage.get());
  }

  constexpr const_iterator cend() const noexcept {
    return const_iterator(storage.get()) + size();
  }

  /*
   * Capacity
   */
  constexpr size_type size() const noexcept {
    return m_size;
  }

  /*
   * Operations
   */
  constexpr void swap(bit_array<T, std::dynamic_extent, V, W>& other) noexcept {
    assert(this->m_size == other.m_size);
    W* it1 = this->storage.get();
    W* it2 = other.storage.get();
    for (size_type i = 0; i < Words(this->m_size); i++, it1++, it2++) {
      std::swap(*it1, *it2);
    }
  }

  template <std::integral U>
  explicit constexpr operator U() const noexcept {
    assert(size() <= bitsof<U>());
    return base::operator U();
  }
};

static_assert(bit_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_range concept!");
static_assert(bit_sized_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_sized_range concept!");
#ifdef CONTIGUOUS_RANGE
static_assert(bit_contiguous_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_range concept!");
static_assert(bit_contiguous_sized_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_sized_range concept!");
#endif

// ========================================================================== //
}  // namespace bit

#endif  // _BIT_ARRAY_DYNAMIC_EXTENT_HPP_INCLUDED

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
28	namespace bit {
29	namespace detail {
30	template <typename value_type, typename word_type>
31	using bit_array_it = typename std::conditional<std::is_same_v<value_type, bit_value>,
32	bit_iterator<word_type*>,
33	word_type*>::type;
34	template <typename value_type, typename word_type>
35	using bit_array_cit = typename std::conditional<std::is_same_v<value_type, bit_value>,
36	bit_iterator<const word_type*>,
37	const word_type*>::type;
38	} // namespace detail
39	template <typename T, std::align_val_t V, typename W>
40	class bit_array<T, std::dynamic_extent, V, W>
41	: public bit_array_base<bit_array<T, std::dynamic_extent, V, W>, T, W, detail::bit_array_it<T, W>, detail::bit_array_cit<T, W>> {
42	public:
43	using base = bit_array_base<bit_array<T, std::dynamic_extent, V, W>, T, W, detail::bit_array_it<T, W>, detail::bit_array_cit<T, W>>;
44	using typename base::const_iterator;
45	using typename base::const_pointer;
46	using typename base::const_reference;
47	using typename base::difference_type;
48	using typename base::iterator;
49	using typename base::pointer;
50	using typename base::reference;
51	using typename base::size_type;
52	using typename base::value_type;
53	using typename base::word_type;
54
55	private:
56	struct deleter {
57	size_type words;
58	void operator()(word_type* const p) const {	71✔
59	for (size_type i = 0; i < words; ++i) {	541,614,391✔
60	(p + i)->~word_type();	541,614,320✔
61	}
62	::operator delete(p, V);	71✔
63	}	71✔
64	};
65
66	const size_type m_size;
67	const std::unique_ptr<word_type[], deleter> storage;
68
69	protected:
70	static constexpr size_type Words(size_type N) {	541,614,536✔
71	return (N * bitsof<value_type>() + bitsof<word_type>() - 1) / bitsof<word_type>();	541,614,536✔
72	};
73
74	private:
75	static constexpr size_t AlignedBytes(size_t N) {	71✔
76	return (Words(N) * sizeof(word_type) + static_cast<size_t>(V) - 1) & ~(static_cast<size_t>(V) - 1);	71✔
77	};
78
79	public:
80	/*
81	* Constructors, copies and moves...
82	*/
83	bit_array() = delete;
84
85	constexpr bit_array(const size_type size)	10✔
86	: m_size(size),	10✔
87	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	10✔
88	//std::uninitialized_fill_n(this->begin(), Words(m_size), word_type());
89	for (size_type i = 0; i < Words(m_size); ++i) {	541,614,182✔
90	new (storage.get() + i) word_type();	541,614,172✔
91	}
92	}	10✔
93
94	template <std::integral U>
95	constexpr bit_array(const size_type size, const U& integral)
96	: m_size(size),
97	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
98	assert(bitsof<U>() <= size);
99	for (size_type i = 0; i < Words(m_size); ++i) {
100	new (storage.get() + i) word_type();
101	}
102	std::memcpy(storage.get(), &integral, sizeof(integral));
103	bool sign_extend = false;
104	if constexpr (std::is_signed_v<U>) {
105	sign_extend = (integral & (1 << (bitsof<U>() - 1))) ? true : false;
106	}
107	if (sign_extend) {
108	for (auto it = begin() + bitsof<U>(); it != end(); ++it) {
109	*it = bit1;
110	}
111	} else {
112	for (auto it = begin() + bitsof<U>(); it != end(); ++it) {
113	*it = bit0;
114	}
115	}
116	}
117
118	constexpr bit_array(const size_type size, const value_type bit_val)	22✔
119	: m_size(size),	22✔
120	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	22✔
121	if constexpr (std::is_same<value_type, word_type>::value) {
122	for (size_type i = 0; i < Words(m_size); ++i) {	34✔
123	new (storage.get() + i) word_type(bit_val);	32✔
124	}
125	} else {
126	for (size_type i = 0; i < Words(m_size); ++i) {	96✔
127	new (storage.get() + i) word_type();	76✔
128	}
129	this->fill(bit_val);	20✔
130	}
131	}	22✔
132
133	constexpr bit_array(const bit_array<T, std::dynamic_extent, V, W>& other)	33✔
134	: m_size(other.size()),	33✔
135	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	33✔
136	for (size_type i = 0; i < Words(m_size); ++i) {	66✔
137	new (storage.get() + i) word_type(*(other.storage.get() + i));	33✔
138	}
139	}	33✔
140
141	constexpr bit_array(const bit_array<T, std::dynamic_extent, V, W>&& other)	1✔
142	: m_size(other.size()),	1✔
143	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	1✔
144	for (size_type i = 0; i < Words(m_size); ++i) {	2✔
145	new (storage.get() + i) word_type(*(other.storage.get() + i));	1✔
146	}
147	}	1✔
148
149	constexpr bit_array(const std::initializer_list<value_type> init)	2✔
150	requires(!std::is_same_v<value_type, word_type>)
151	: m_size(init.size()),	2✔
152	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	2✔
153	for (size_type i = 0; i < Words(m_size); ++i) {	4✔
154	new (storage.get() + i) word_type();	2✔
155	}
156	std::copy(init.begin(), init.end(), this->begin());	2✔
157	}	2✔
158
159	#if 0
160	No known conversion from bool to bit_value
161	bit_value has explicit constructor from bool to bit_value so this doesnt work
162	constexpr bit_array<std::dynamic_extent,W>::bit_array(const std::initializer_list<bool> init)
163	: storage(std::make_unique<word_type[]>(Words(init.size()))),
164	m_size(init.size()) {
165	std::copy(init.begin(), init.end(), this->begin());
166	}
167	#endif
168
169	constexpr bit_array(const std::initializer_list<word_type> init)	1✔
170	: m_size(bitsof<word_type>() * init.size()),	1✔
171	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	1✔
172	size_type i = 0;	1✔
173	auto it = init.begin();	1✔
174	for (; i < Words(m_size) && it != init.end(); ++i, ++it) {	3✔
175	new (storage.get() + i) word_type(*it);	2✔
176	}
177	// Initialize remaining words if any
178	for (; i < Words(m_size); ++i) {	1✔
NEW 179	new (storage.get() + i) word_type();	×
180	}
181	}	1✔
182
183	constexpr bit_array(const std::string_view s)	2✔
184	requires(std::is_same_v<value_type, bit_value>)
185	: m_size((std::count(s.begin(), s.end(), '0') + std::count(s.begin(), s.end(), '1'))),	2✔
186	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	2✔
187	for (size_type i = 0; i < Words(m_size); ++i) {	4✔
188	new (storage.get() + i) word_type();	2✔
189	}
190	size_type i = 0;	2✔
191	for (char c : s) {	17✔
192	if (c == '0') {	15✔
193	begin()[i++] = bit0;	7✔
194	} else if (c == '1') {	8✔
195	begin()[i++] = bit1;	8✔
196	}
197	}
198	}	2✔
199
200	~bit_array() = default;	142✔
201
202	/*
203	* Assignment
204	*/
205	constexpr bit_array<T, std::dynamic_extent, V, W>& operator=(const bit_array<T, std::dynamic_extent, V, W>& other) {	1✔
206	if (nullptr == storage.get() \|\| m_size != other.m_size) {	1✔
NEW 207	throw std::invalid_argument("Cannot reassign bit_array<std::dynamic_extent,V,W> size");	×
208	}
209	std::copy(other.begin(), other.end(), this->begin());	1✔
210	return *this;	2✔
211	}
212
213	constexpr bit_array<T, std::dynamic_extent, V, W>& operator=(bit_array<T, std::dynamic_extent, V, W>&& other) {	1✔
214	if (nullptr == storage.get() \|\| m_size != other.m_size) {	1✔
NEW 215	throw std::invalid_argument("Cannot reassign bit_array<std::dynamic_extent,V,W> size");	×
216	}
217	std::copy(other.begin(), other.end(), this->begin());	1✔
218	return *this;	2✔
219	}
220
221	/*
222	* Element Access
223	*/
224	constexpr word_type* data() noexcept {	10✔
225	return size() ? storage.get() : nullptr;	10✔
226	}
227
228	constexpr const word_type* data() const noexcept {
229	return size() ? storage.get() : nullptr;
230	}
231
232	/*
233	* Iterators
234	*/
235	constexpr iterator begin() noexcept {	824✔
236	return iterator(storage.get());	824✔
237	}
238
239	constexpr iterator end() noexcept {	33✔
240	return begin() + size();	33✔
241	}
242
243	constexpr const_iterator begin() const noexcept {	5✔
244	return const_iterator(storage.get());	5✔
245	}
246
247	constexpr const_iterator end() const noexcept {	3✔
248	return const_iterator(storage.get()) + size();	3✔
249	}
250
251	constexpr const_iterator cbegin() const noexcept {
252	return const_iterator(storage.get());
253	}
254
255	constexpr const_iterator cend() const noexcept {
256	return const_iterator(storage.get()) + size();
257	}
258
259	/*
260	* Capacity
261	*/
262	constexpr size_type size() const noexcept {	235✔
263	return m_size;	235✔
264	}
265
266	/*
267	* Operations
268	*/
269	constexpr void swap(bit_array<T, std::dynamic_extent, V, W>& other) noexcept {	1✔
270	assert(this->m_size == other.m_size);	1✔
271	W* it1 = this->storage.get();	1✔
272	W* it2 = other.storage.get();	1✔
273	for (size_type i = 0; i < Words(this->m_size); i++, it1++, it2++) {	2✔
274	std::swap(it1, it2);	1✔
275	}
276	}	1✔
277
278	template <std::integral U>
279	explicit constexpr operator U() const noexcept {
280	assert(size() <= bitsof<U>());
281	return base::operator U();
282	}
283	};
284
285	static_assert(bit_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_range concept!");
286	static_assert(bit_sized_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_sized_range concept!");
287	#ifdef CONTIGUOUS_RANGE
288	static_assert(bit_contiguous_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_range concept!");
289	static_assert(bit_contiguous_sized_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_sized_range concept!");
290	#endif
291
292	// ========================================================================== //
293	} // namespace bit
294
295	#endif // _BIT_ARRAY_DYNAMIC_EXTENT_HPP_INCLUDED

PeterCDMcLean / BitLib / 14949319596

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

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