14957957435

Committed 11 May 2025 05:09PM UTC coverage: 96.028% (-1.0%) from 97.036%

Build # 14957957435

Build Type

Pull #8

github

Committed by

web-flow

Commit Message

Merge e7b812994 into a837637fd

Pull Request Pull Request #8: Common bit array base

Coverage Stats

214 of 236 new or added lines in 6 files covered. (90.68%)

1354 of 1410 relevant lines covered (96.03%)

15522548.95 hits per line

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

97.92

/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"
#include "bitlib/bit_concepts.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 base::end;
  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;

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

  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_sized_range auto& other)
      : m_size(other.size()),
        storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
    ::bit::copy(other.begin(), other.end(), this->begin());
  }

  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=(const bit_sized_range auto& other) {
    if (other.size() != this->size()) [[unlikely]] {
      throw std::invalid_argument("other bit_range contains an invalid number of bits for bit_array.");
    }
    ::bit::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 const_iterator begin() const noexcept {
    return const_iterator(storage.get());
  }

  /*
   * 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);
    // Cannot just swap storage as it is const.
    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);
    }
  }
};

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	#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, std::align_val_t V, typename W>
41	class bit_array<T, std::dynamic_extent, V, W>
42	: 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>> {
43	public:
44	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>>;
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	struct deleter {
59	size_type words;
60	void operator()(word_type* const p) const {	75✔
61	for (size_type i = 0; i < words; ++i) {	541,614,399✔
62	(p + i)->~word_type();	541,614,324✔
63	}
64	::operator delete(p, V);	75✔
65	}	75✔
66	};
67
68	const size_type m_size;
69	const std::unique_ptr<word_type[], deleter> storage;
70
71	static constexpr size_type Words(size_type N) {	541,614,552✔
72	return (N * bitsof<value_type>() + bitsof<word_type>() - 1) / bitsof<word_type>();	541,614,552✔
73	};
74
75	static constexpr size_t AlignedBytes(size_t N) {	75✔
76	return (Words(N) * sizeof(word_type) + static_cast<size_t>(V) - 1) & ~(static_cast<size_t>(V) - 1);	75✔
77	};
78
79	public:
80	/*
81	* Constructors, copies and moves...
82	*/
83	bit_array() = delete;
84
85	constexpr bit_array(const size_type size)	12✔
86	: m_size(size),	12✔
87	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	12✔
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,186✔
90	new (storage.get() + i) word_type();	541,614,174✔
91	}
92	}	12✔
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_sized_range auto& other)
142	: m_size(other.size()),
143	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {
144	::bit::copy(other.begin(), other.end(), this->begin());
145	}
146
147	constexpr bit_array(const bit_array<T, std::dynamic_extent, V, W>&& other)	1✔
148	: m_size(other.size()),	1✔
149	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	1✔
150	for (size_type i = 0; i < Words(m_size); ++i) {	2✔
151	new (storage.get() + i) word_type(*(other.storage.get() + i));	1✔
152	}
153	}	1✔
154
155	constexpr bit_array(const std::initializer_list<value_type> init)	4✔
156	requires(!std::is_same_v<value_type, word_type>)
157	: m_size(init.size()),	4✔
158	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	4✔
159	for (size_type i = 0; i < Words(m_size); ++i) {	8✔
160	new (storage.get() + i) word_type();	4✔
161	}
162	std::copy(init.begin(), init.end(), this->begin());	4✔
163	}	4✔
164
165	#if 0
166	No known conversion from bool to bit_value
167	bit_value has explicit constructor from bool to bit_value so this doesnt work
168	constexpr bit_array<std::dynamic_extent,W>::bit_array(const std::initializer_list<bool> init)
169	: storage(std::make_unique<word_type[]>(Words(init.size()))),
170	m_size(init.size()) {
171	std::copy(init.begin(), init.end(), this->begin());
172	}
173	#endif
174
175	constexpr bit_array(const std::initializer_list<word_type> init)	1✔
176	: m_size(bitsof<word_type>() * init.size()),	1✔
177	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	1✔
178	size_type i = 0;	1✔
179	auto it = init.begin();	1✔
180	for (; i < Words(m_size) && it != init.end(); ++i, ++it) {	3✔
181	new (storage.get() + i) word_type(*it);	2✔
182	}
183	// Initialize remaining words if any
184	for (; i < Words(m_size); ++i) {	1✔
NEW 185	new (storage.get() + i) word_type();	×
186	}
187	}	1✔
188
189	constexpr bit_array(const std::string_view s)	2✔
190	requires(std::is_same_v<value_type, bit_value>)
191	: m_size((std::count(s.begin(), s.end(), '0') + std::count(s.begin(), s.end(), '1'))),	2✔
192	storage(static_cast<word_type*>(::operator new(AlignedBytes(m_size), V)), deleter{Words(m_size)}) {	2✔
193	for (size_type i = 0; i < Words(m_size); ++i) {	4✔
194	new (storage.get() + i) word_type();	2✔
195	}
196	size_type i = 0;	2✔
197	for (char c : s) {	17✔
198	if (c == '0') {	15✔
199	begin()[i++] = bit0;	7✔
200	} else if (c == '1') {	8✔
201	begin()[i++] = bit1;	8✔
202	}
203	}
204	}	2✔
205
206	~bit_array() = default;	150✔
207
208	/*
209	* Assignment
210	*/
211	constexpr bit_array<T, std::dynamic_extent, V, W>& operator=(const bit_array<T, std::dynamic_extent, V, W>& other) {	2✔
212	if (nullptr == storage.get() \|\| m_size != other.m_size) {	2✔
213	throw std::invalid_argument("Cannot reassign bit_array<std::dynamic_extent,V,W> size");	1✔
214	}
215	std::copy(other.begin(), other.end(), this->begin());	1✔
216	return *this;	2✔
217	}
218
219	constexpr bit_array<T, std::dynamic_extent, V, W>& operator=(const bit_sized_range auto& other) {	1✔
220	if (other.size() != this->size()) [[unlikely]] {	1✔
NEW 221	throw std::invalid_argument("other bit_range contains an invalid number of bits for bit_array.");	×
222	}
223	::bit::copy(other.begin(), other.end(), this->begin());	1✔
224	return *this;	2✔
225	};
226
227	constexpr bit_array<T, std::dynamic_extent, V, W>& operator=(bit_array<T, std::dynamic_extent, V, W>&& other) {	4✔
228	if (nullptr == storage.get() \|\| m_size != other.m_size) {	4✔
229	throw std::invalid_argument("Cannot reassign bit_array<std::dynamic_extent,V,W> size");	1✔
230	}
231	std::copy(other.begin(), other.end(), this->begin());	3✔
232	return *this;	6✔
233	}
234
235	/*
236	* Element Access
237	*/
238	constexpr word_type* data() noexcept {	10✔
239	return size() ? storage.get() : nullptr;	10✔
240	}
241
242	constexpr const word_type* data() const noexcept {
243	return size() ? storage.get() : nullptr;
244	}
245
246	/*
247	* Iterators
248	*/
249	constexpr iterator begin() noexcept {	834✔
250	return iterator(storage.get());	834✔
251	}
252
253	constexpr const_iterator begin() const noexcept {	8✔
254	return const_iterator(storage.get());	8✔
255	}
256
257	/*
258	* Capacity
259	*/
260	constexpr size_type size() const noexcept {	240✔
261	return m_size;	240✔
262	}
263
264	/*
265	* Operations
266	*/
267	constexpr void swap(bit_array<T, std::dynamic_extent, V, W>& other) noexcept {	1✔
268	assert(this->m_size == other.m_size);	1✔
269	// Cannot just swap storage as it is const.
270	W* it1 = this->storage.get();	1✔
271	W* it2 = other.storage.get();	1✔
272	for (size_type i = 0; i < Words(this->m_size); i++, it1++, it2++) {	2✔
273	std::swap(it1, it2);	1✔
274	}
275	}	1✔
276	};
277
278	static_assert(bit_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_range concept!");
279	static_assert(bit_sized_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_sized_range concept!");
280	#ifdef CONTIGUOUS_RANGE
281	static_assert(bit_contiguous_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_range concept!");
282	static_assert(bit_contiguous_sized_range<bit_array<>>, "bit_array<> does not satisfy bit_contiguous_sized_range concept!");
283	#endif
284
285	// ========================================================================== //
286	} // namespace bit
287
288	#endif // _BIT_ARRAY_DYNAMIC_EXTENT_HPP_INCLUDED

PeterCDMcLean / BitLib / 14957957435

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