14995399828

Committed 13 May 2025 11:26AM UTC coverage: 49.868% (-46.5%) from 96.333%

Build # 14995399828

Build Type

push

github

Committed by

web-flow

Commit Message

Add github workflow targets for warnings (#7)

* WError cmake option

* Add a build-only workflow for warnings

* Add clang warnings build target

* Try enabling coverage w/ clang

* Refactor presets

* composite actions are apparently syntax strict

* Try to symlink llvm/clang tools

* Use absolute path for coverage.profraw

* ctest interferes with llvm coverage, likely due to parallel. try a cleaner approach

* Codecov only supports lcov/gcov

* Prevent artifact conflicts

* missing github token

* Different artifact names

Run Details

5155 of 10638 branches covered (48.46%)

Branch coverage included in aggregate %.

39 of 70 new or added lines in 1 file covered. (55.71%)

128 existing lines in 10 files now uncovered.

5402 of 10532 relevant lines covered (51.29%)

5332091.8 hits per line

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

87.45

/include/bitlib/bit-algorithms/rotate.hpp

// ================================= ROTATE ================================= //
// Project:         The Experimental Bit Algorithms Library
// Name:            rotate.hpp
// Description:     bit_iterator overloads for std::rotate
// Contributor(s):  Bryce Kille [2019]
// License:         BSD 3-Clause License
// ========================================================================== //
#ifndef _ROTATE_HPP_INCLUDED
#define _ROTATE_HPP_INCLUDED
// ========================================================================== //



// ============================== PREAMBLE ================================== //
// C++ standard library
#include <iostream>
// Project sources
#include "bit_algorithm.hpp"
// Third-party libraries
// Miscellaneous
namespace bit {
// ========================================================================== //

// Rotates a range by copying [first...n_first) to the stack, then shifting
// the range to the left and appending the copied section to the end.
//
// Note: distance(first, n_first) <= 3*digits
template <class ForwardIt, int BufferSize>
bit_iterator<ForwardIt> _rotate_via_copy_begin(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    constexpr size_type digits = binary_digits<word_type>::value;

    size_type k = distance(first, n_first);
    assert(k <= BufferSize*digits);
    word_type copy_arr[BufferSize];
    copy_arr[0] = *first.base();
    ForwardIt it = ++first.base();
    short unsigned int pos = 1;
    short int bits_left_to_copy = k - (digits - first.position());
    while (bits_left_to_copy > 0) {
        copy_arr[pos++] = *it++;
        bits_left_to_copy -= digits;
    }
    bit_iterator<ForwardIt> ret = shift_left(first, last, k);
    copy(
        bit_iterator<word_type*>(copy_arr, first.position()),
        bit_iterator<word_type*>(
                copy_arr,
                first.position()
        ) + k,
        ret
    );
    return ret;
}

// Rotates a range by copying [n_first, last) to the stack, then shifting
// the range to the right and prepending the copied section to the beginning.
//
// Note: distance(n_first, last) <= 3*digits
template <class ForwardIt, int BufferSize>
bit_iterator<ForwardIt> _rotate_via_copy_end(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    constexpr size_type digits = binary_digits<word_type>::value;

    size_type k = distance(n_first, last);
    assert(k <= BufferSize*digits);
    word_type copy_arr[BufferSize];
    copy_arr[0] = *n_first.base();
    ForwardIt it = ++n_first.base();
    short unsigned int pos = 1;
    short int bits_left_to_copy = k - (digits - n_first.position());
    while (bits_left_to_copy > 0) {
        copy_arr[pos++] = *it++;
        bits_left_to_copy -= digits;
    }
    bit_iterator<ForwardIt> ret = shift_right(first, last, k);
    copy(
        bit_iterator<word_type*>(copy_arr, n_first.position()),
        bit_iterator<word_type*>(
                copy_arr,
                n_first.position()
        ) + k,
        first
    );
    return ret;
}

// Rotates a range using random-access iterators. Algorithm logic from the GCC
// implementation
template <class RandomAccessIt>
bit_iterator<RandomAccessIt> _rotate_via_raw(
   bit_iterator<RandomAccessIt> first,
   bit_iterator<RandomAccessIt> n_first,
   bit_iterator<RandomAccessIt> last,
   std::random_access_iterator_tag
) {
    // Types and constants
    using word_type = typename bit_iterator<RandomAccessIt>::word_type;
    using size_type = typename bit_iterator<RandomAccessIt>::size_type;
    using difference_type =
        typename bit_iterator<RandomAccessIt>::difference_type;
    constexpr difference_type digits = binary_digits<word_type>::value;

    difference_type k = n_first - first;
    difference_type n = last - first;

    if (k == n - k) {
        swap_ranges(first, n_first, n_first);
        return n_first;
    }

    bit_iterator<RandomAccessIt> p = first;
    bit_iterator<RandomAccessIt> ret = first + (last - n_first);

    for (;;) {
        if (k < n - k) {
            if (k <= digits) {
                // BENCHMARK NOTE: may be better to do k <= 3*digits and use
                // the _rotate_via_copy method.
                word_type temp_word = get_word<word_type>(p, k);
                bit_iterator<RandomAccessIt> temp_it = shift_left(p, p + n, k);
                write_word<word_type>(temp_word, temp_it, k);
                return ret;
            }
            bit_iterator<RandomAccessIt> q = p + k;
            unsigned int full_swaps = (n - k) / k;
            size_type remainder = (n - k) - full_swaps*k;
            while (full_swaps > 0) {
                swap_ranges(p, q, q);
                p += k;
                q += k;
                --full_swaps;
            }
            swap_ranges(p, p + remainder, q);
            p += remainder;
            q += remainder;
            n %= k;
            if (n == 0)
                return ret;
            std::swap(n, k);
            k = n - k;
        } else {
            k = n - k;
            if (k <= digits) {
                word_type temp_word = get_word<word_type>(p + n - k, k);
                shift_right(p, p + n, k);
                write_word<word_type>(temp_word, p, k);
                return ret;
            }
            bit_iterator<RandomAccessIt> q = p + n;
            p = q - k;
            unsigned int full_swaps = (n - k) / k;
            size_type remainder = (n - k) - full_swaps*k;
            while (full_swaps > 0) {
                p -= k;
                q -= k;
                swap_ranges(p, q, q);
                --full_swaps;
            }
            p -= remainder;
            q -= remainder;
            swap_ranges(p, p + remainder, q);
            n %= k;
            if (n == 0)
                return ret;
            std::swap(n, k);
        }
    }
}

// Main function for implementing the bit overload of std::rotate.
template <class ForwardIt>
bit_iterator<ForwardIt> rotate(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Assertions
    _assert_range_viability(first, n_first);
    _assert_range_viability(n_first, last);
    _assert_range_viability(first, last);
    //if (first == n_first) return n_first;
    if (first == n_first) return last;

    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    using difference_type =
        typename bit_iterator<ForwardIt>::difference_type;
    constexpr difference_type digits = binary_digits<word_type>::value;

    // Initialization
    const bool is_first_aligned = first.position() == 0;
    const bool is_last_aligned = last.position() == 0;

    // Within the same word
    if (std::next(first.base(), is_last_aligned) == last.base()) {
        if (is_first_aligned && is_last_aligned) {
            *first.base() =
                (*first.base() >> n_first.position())
                |
                static_cast<word_type>(
                        *first.base() << (digits - n_first.position())
            );
            return std::next(first, digits - n_first.position());
        } else {
            size_type last_pos = is_last_aligned ? digits : last.position();
            size_type k = n_first.position() - first.position();
            size_type p = last_pos - n_first.position();
            size_type d = last_pos - first.position();

            word_type mask = ((1ULL << d) - 1) << first.position();
            word_type rotated = *first.base() & mask;
            rotated = static_cast<word_type>(rotated >> k)
                | static_cast<word_type>(rotated << p);
            *first.base() = _bitblend<word_type>(
                *first.base(),
                rotated,
                first.position(),
                d
            );
            return std::next(first, p);
        }
    }

    // Single word subcases
    if (is_within<digits>(first, n_first)) {
        size_type k = distance(first, n_first);
        word_type temp = get_word<word_type>(first, k);
        bit_iterator<ForwardIt> new_last = shift_left(first, last, k);
        write_word<word_type>(temp, new_last, static_cast<word_type>(k));
        return new_last;
    } else if (is_within<digits>(n_first, last)) {
        size_type p = distance(n_first, last);
        word_type temp = get_word<word_type>(n_first, p);
        auto new_last = shift_right(first, last, p);
        write_word(temp, first, static_cast<word_type>(p));
        return new_last;
    }
    return _rotate_via_raw(
            first,
            n_first,
            last,
            typename std::iterator_traits<ForwardIt>::iterator_category()
    );
}


// ========================================================================== //
} // namespace bit
#endif // _ROTATE_HPP_INCLUDED
// ========================================================================== //

1	// ================================= ROTATE ================================= //
2	// Project: The Experimental Bit Algorithms Library
3	// Name: rotate.hpp
4	// Description: bit_iterator overloads for std::rotate
5	// Contributor(s): Bryce Kille [2019]
6	// License: BSD 3-Clause License
7	// ========================================================================== //
8	#ifndef _ROTATE_HPP_INCLUDED
9	#define _ROTATE_HPP_INCLUDED
10	// ========================================================================== //
11
12
13
14	// ============================== PREAMBLE ================================== //
15	// C++ standard library
16	#include <iostream>
17	// Project sources
18	#include "bit_algorithm.hpp"
19	// Third-party libraries
20	// Miscellaneous
21	namespace bit {
22	// ========================================================================== //
23
24	// Rotates a range by copying [first...n_first) to the stack, then shifting
25	// the range to the left and appending the copied section to the end.
26	//
27	// Note: distance(first, n_first) <= 3*digits
28	template <class ForwardIt, int BufferSize>
29	bit_iterator<ForwardIt> _rotate_via_copy_begin(
30	bit_iterator<ForwardIt> first,
31	bit_iterator<ForwardIt> n_first,
32	bit_iterator<ForwardIt> last
33	) {
34	// Types and constants
35	using word_type = typename bit_iterator<ForwardIt>::word_type;
36	using size_type = typename bit_iterator<ForwardIt>::size_type;
37	constexpr size_type digits = binary_digits<word_type>::value;
38
39	size_type k = distance(first, n_first);
40	assert(k <= BufferSize*digits);
41	word_type copy_arr[BufferSize];
42	copy_arr[0] = *first.base();
43	ForwardIt it = ++first.base();
44	short unsigned int pos = 1;
45	short int bits_left_to_copy = k - (digits - first.position());
46	while (bits_left_to_copy > 0) {
47	copy_arr[pos++] = *it++;
48	bits_left_to_copy -= digits;
49	}
50	bit_iterator<ForwardIt> ret = shift_left(first, last, k);
51	copy(
52	bit_iterator<word_type*>(copy_arr, first.position()),
53	bit_iterator<word_type*>(
54	copy_arr,
55	first.position()
56	) + k,
57	ret
58	);
59	return ret;
60	}
61
62	// Rotates a range by copying [n_first, last) to the stack, then shifting
63	// the range to the right and prepending the copied section to the beginning.
64	//
65	// Note: distance(n_first, last) <= 3*digits
66	template <class ForwardIt, int BufferSize>
67	bit_iterator<ForwardIt> _rotate_via_copy_end(
68	bit_iterator<ForwardIt> first,
69	bit_iterator<ForwardIt> n_first,
70	bit_iterator<ForwardIt> last
71	) {
72	// Types and constants
73	using word_type = typename bit_iterator<ForwardIt>::word_type;
74	using size_type = typename bit_iterator<ForwardIt>::size_type;
75	constexpr size_type digits = binary_digits<word_type>::value;
76
77	size_type k = distance(n_first, last);
78	assert(k <= BufferSize*digits);
79	word_type copy_arr[BufferSize];
80	copy_arr[0] = *n_first.base();
81	ForwardIt it = ++n_first.base();
82	short unsigned int pos = 1;
83	short int bits_left_to_copy = k - (digits - n_first.position());
84	while (bits_left_to_copy > 0) {
85	copy_arr[pos++] = *it++;
86	bits_left_to_copy -= digits;
87	}
88	bit_iterator<ForwardIt> ret = shift_right(first, last, k);
89	copy(
90	bit_iterator<word_type*>(copy_arr, n_first.position()),
91	bit_iterator<word_type*>(
92	copy_arr,
93	n_first.position()
94	) + k,
95	first
96	);
97	return ret;
98	}
99
100	// Rotates a range using random-access iterators. Algorithm logic from the GCC
101	// implementation
102	template <class RandomAccessIt>
103	bit_iterator<RandomAccessIt> _rotate_via_raw(	3,056✔
104	bit_iterator<RandomAccessIt> first,
105	bit_iterator<RandomAccessIt> n_first,
106	bit_iterator<RandomAccessIt> last,
107	std::random_access_iterator_tag
108	) {	1,808✔
109	// Types and constants
110	using word_type = typename bit_iterator<RandomAccessIt>::word_type;	1,808✔
111	using size_type = typename bit_iterator<RandomAccessIt>::size_type;	1,808✔
112	using difference_type =	1,808✔
113	typename bit_iterator<RandomAccessIt>::difference_type;	1,808✔
114	constexpr difference_type digits = binary_digits<word_type>::value;	4,864✔
115
116	difference_type k = n_first - first;	4,864✔
117	difference_type n = last - first;	4,864✔
118
119	if (k == n - k) {	4,864!
120	swap_ranges(first, n_first, n_first);	16✔
121	return n_first;	16✔
122	}	16✔
123
124	bit_iterator<RandomAccessIt> p = first;	4,848✔
125	bit_iterator<RandomAccessIt> ret = first + (last - n_first);	4,848✔
126
127	for (;;) {	12,256✔
128	if (k < n - k) {	15,312✔
129	if (k <= digits) {	8,352✔
130	// BENCHMARK NOTE: may be better to do k <= 3*digits and use
131	// the _rotate_via_copy method.
132	word_type temp_word = get_word<word_type>(p, k);	3,632✔
133	bit_iterator<RandomAccessIt> temp_it = shift_left(p, p + n, k);	3,632✔
134	write_word<word_type>(temp_word, temp_it, k);	3,632✔
135	return ret;	3,632✔
136	}	992✔
137	bit_iterator<RandomAccessIt> q = p + k;	4,720✔
138	unsigned int full_swaps = (n - k) / k;	4,720✔
139	size_type remainder = (n - k) - full_swaps*k;	4,720✔
140	while (full_swaps > 0) {	22,192✔
141	swap_ranges(p, q, q);	17,472✔
142	p += k;	17,472✔
143	q += k;	17,472✔
144	--full_swaps;	17,472✔
145	}	10,208✔
146	swap_ranges(p, p + remainder, q);	4,720✔
147	p += remainder;	4,720✔
148	q += remainder;	4,720✔
149	n %= k;	4,720✔
150	if (n == 0)	4,720!
151	return ret;	×
152	std::swap(n, k);	4,720✔
153	k = n - k;	4,720✔
154	} else {	3,280✔
155	k = n - k;	6,960✔
156	if (k <= digits) {	6,960✔
157	word_type temp_word = get_word<word_type>(p + n - k, k);	1,184✔
158	shift_right(p, p + n, k);	1,184✔
159	write_word<word_type>(temp_word, p, k);	1,184✔
160	return ret;	1,184✔
161	}	784✔
162	bit_iterator<RandomAccessIt> q = p + n;	5,776✔
163	p = q - k;	5,776✔
164	unsigned int full_swaps = (n - k) / k;	5,776✔
165	size_type remainder = (n - k) - full_swaps*k;	5,776✔
166	while (full_swaps > 0) {	24,336✔
167	p -= k;	18,560✔
168	q -= k;	18,560✔
169	swap_ranges(p, q, q);	18,560✔
170	--full_swaps;	18,560✔
171	}	7,888✔
172	p -= remainder;	5,776✔
173	q -= remainder;	5,776✔
174	swap_ranges(p, p + remainder, q);	5,776✔
175	n %= k;	5,776✔
176	if (n == 0)	5,776!
177	return ret;	32✔
178	std::swap(n, k);	5,744✔
179	}	2,480✔
180	}	5,872✔
181	}	1,792✔
182
183	// Main function for implementing the bit overload of std::rotate.
184	template <class ForwardIt>
185	bit_iterator<ForwardIt> rotate(	8,256✔
186	bit_iterator<ForwardIt> first,
187	bit_iterator<ForwardIt> n_first,
188	bit_iterator<ForwardIt> last
189	) {	8,256✔
190	// Assertions
191	_assert_range_viability(first, n_first);	16,512✔
192	_assert_range_viability(n_first, last);	16,512✔
193	_assert_range_viability(first, last);	16,512✔
194	//if (first == n_first) return n_first;
195	if (first == n_first) return last;	16,512✔
196
197	// Types and constants
198	using word_type = typename bit_iterator<ForwardIt>::word_type;	7,584✔
199	using size_type = typename bit_iterator<ForwardIt>::size_type;	7,584✔
200	using difference_type =	7,584✔
201	typename bit_iterator<ForwardIt>::difference_type;	7,584✔
202	constexpr difference_type digits = binary_digits<word_type>::value;	15,616✔
203
204	// Initialization
205	const bool is_first_aligned = first.position() == 0;	15,616✔
206	const bool is_last_aligned = last.position() == 0;	15,616✔
207
208	// Within the same word
209	if (std::next(first.base(), is_last_aligned) == last.base()) {	23,648✔
210	if (is_first_aligned && is_last_aligned) {	3,184!
211	*first.base() =	×
212	(*first.base() >> n_first.position())	×
213	\|	×
214	static_cast<word_type>(	×
215	*first.base() << (digits - n_first.position())	×
UNCOV 216	);
217	return std::next(first, digits - n_first.position());	×
218	} else {	1,488✔
219	size_type last_pos = is_last_aligned ? digits : last.position();	3,184!
220	size_type k = n_first.position() - first.position();	3,184✔
221	size_type p = last_pos - n_first.position();	3,184✔
222	size_type d = last_pos - first.position();	3,184✔
223
224	word_type mask = ((1ULL << d) - 1) << first.position();	3,184✔
225	word_type rotated = *first.base() & mask;	3,184✔
226	rotated = static_cast<word_type>(rotated >> k)	3,184✔
227	\| static_cast<word_type>(rotated << p);	3,184✔
228	*first.base() = _bitblend<word_type>(	4,176✔
229	*first.base(),	4,880✔
230	rotated,	1,488✔
231	first.position(),	2,192✔
232	d	1,488✔
233	);	1,488✔
234	return std::next(first, p);	4,880✔
235	}	1,488✔
236	}	1,488✔
237
238	// Single word subcases
239	if (is_within<digits>(first, n_first)) {	12,432!
240	size_type k = distance(first, n_first);	5,168✔
241	word_type temp = get_word<word_type>(first, k);	5,168✔
242	bit_iterator<ForwardIt> new_last = shift_left(first, last, k);	5,168✔
243	write_word<word_type>(temp, new_last, static_cast<word_type>(k));	5,168✔
244	return new_last;	5,168✔
245	} else if (is_within<digits>(n_first, last)) {	7,264✔
246	size_type p = distance(n_first, last);	2,400✔
247	word_type temp = get_word<word_type>(n_first, p);	2,400✔
248	auto new_last = shift_right(first, last, p);	2,400✔
249	write_word(temp, first, static_cast<word_type>(p));	2,400✔
250	return new_last;	2,400✔
251	}	2,096✔
252	return _rotate_via_raw(	4,864✔
253	first,	1,808✔
254	n_first,	1,808✔
255	last,	1,808✔
256	typename std::iterator_traits<ForwardIt>::iterator_category()	1,808✔
257	);	4,864✔
258	}	6,096✔
259
260
261	// ========================================================================== //
262	} // namespace bit
263	#endif // _ROTATE_HPP_INCLUDED
264	// ========================================================================== //

PeterCDMcLean / BitLib / 14995399828

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