14955974867

Committed 11 May 2025 12:51PM UTC coverage: 95.522% (-1.5%) from 97.036%

Build # 14955974867

Build Type

Pull #8

github

Committed by

web-flow

Commit Message

Merge e5791b246 into a837637fd

Pull Request Pull Request #8: Common bit array base

Run Details

203 of 232 new or added lines in 6 files covered. (87.5%)

1 existing line in 1 file now uncovered.

1344 of 1407 relevant lines covered (95.52%)

15555644.28 hits per line

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

96.7

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

PeterCDMcLean / BitLib / 14955974867

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