15624655410

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

Build # 15624655410

Build Type

push

github

Committed by

web-flow

Commit Message

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

Run Details

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

66.67

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

// ================================= EQUAL =================================== //
// Project:     The Experimental Bit Algorithms Library
// Name:        equal.hpp
// Contributor: Bryce Kille [2019]
//              Peter McLean [2025]
// License:     BSD 3-Clause License
// ========================================================================== //
#ifndef _EQUAL_HPP_INCLUDED
#define _EQUAL_HPP_INCLUDED
// ========================================================================== //

// ================================ PREAMBLE ================================ //
// C++ standard library
#include <type_traits>
#include <math.h>
// Project sources
#include "bitlib/bit-iterator/bit.hpp"
// Third-party libraries
// Miscellaneous
namespace bit {
// ========================================================================== //
struct equal_impl;

// Status: Does not work for Input/Output iterators due to distance call
template <typename RandomAccessIt1, typename RandomAccessIt2>
constexpr bool equal(
    const bit_iterator<RandomAccessIt1>& first,
    const bit_iterator<RandomAccessIt1>& last,
    const bit_iterator<RandomAccessIt2>& d_first) {
  return with_bit_iterator_adapter<equal_impl>(first, last, d_first);
}

// ---------------------------- Equal Algorithms ----------------------------- //

// Status: Does not work for Input/Output iterators due to distance call
struct equal_impl {
  template <typename RandomAccessIt1, typename RandomAccessIt2>
  constexpr bool operator()(
      bit_iterator<RandomAccessIt1> first,
      bit_iterator<RandomAccessIt1> last,
      bit_iterator<RandomAccessIt2> d_first) {
    // Types and constants
    using dst_word_type = typename bit_iterator<RandomAccessIt2>::word_type;
    using src_word_type = typename bit_iterator<RandomAccessIt1>::word_type;
    static_assert(::std::is_same<dst_word_type, src_word_type>::value, "Underlying word types must be equal");
    using word_type = dst_word_type;
    using size_type = typename bit_iterator<RandomAccessIt2>::size_type;
    constexpr size_type digits = binary_digits<word_type>::value;

    // Assertions
    _assert_range_viability(first, last);
    if (first == last) {
      return true;
    }

    // Initialization
    const bool is_d_first_aligned = d_first.position() == 0;
    size_type total_bits_to_check = distance(first, last);
    size_type remaining_bits_to_check = total_bits_to_check;
    auto it = d_first.base();

    // d_first is not aligned.
    if (!is_d_first_aligned) {
      const size_type partial_bits_to_check = ::std::min(
          remaining_bits_to_check,
          digits - d_first.position());
      const word_type mask = _mask<word_type>(partial_bits_to_check) << d_first.position();
      const word_type comp = static_cast<word_type>(
          get_word<word_type>(first, partial_bits_to_check)
          << d_first.position());
      if ((mask & *it) != (mask & comp)) {
        return false;
      }
      remaining_bits_to_check -= partial_bits_to_check;
      advance(first, partial_bits_to_check);
      it++;
    }

    if (remaining_bits_to_check > 0) {
      const bool is_first_aligned = first.position() == 0;
      // d_first will be aligned at this point
      if (is_first_aligned && remaining_bits_to_check >= digits) {
        auto N = ::std::distance(first.base(), last.base());
        bool found_mismatch = !::std::equal(first.base(), last.base(), it);
        if (found_mismatch) {
          return false;
        }
        it += N;
        first += digits * N;
        remaining_bits_to_check -= digits * N;
      } else {
        // TODO benchmark if its faster to ::std::check the entire range then shift
        while (remaining_bits_to_check >= digits) {
          if (*it != get_word<word_type>(first, digits)) {
            return false;
          }
          remaining_bits_to_check -= digits;
          it++;
          advance(first, digits);
        }
      }
      if (remaining_bits_to_check > 0) {
        const word_type mask = _mask<word_type>(remaining_bits_to_check);
        const word_type comp = get_word<word_type>(first, remaining_bits_to_check);
        if ((mask & *it) != (mask & comp)) {
          return false;
        }
      }
    }
    return true;
  }
};
// -------------------------------------------------------------------------- //



// ========================================================================== //
} // namespace bit
#endif // _EQUAL_HPP_INCLUDED
// ========================================================================== //

1	// ================================= EQUAL =================================== //
2	// Project: The Experimental Bit Algorithms Library
3	// Name: equal.hpp
4	// Contributor: Bryce Kille [2019]
5	// Peter McLean [2025]
6	// License: BSD 3-Clause License
7	// ========================================================================== //
8	#ifndef _EQUAL_HPP_INCLUDED
9	#define _EQUAL_HPP_INCLUDED
10	// ========================================================================== //
11
12	// ================================ PREAMBLE ================================ //
13	// C++ standard library
14	#include <type_traits>
15	#include <math.h>
16	// Project sources
17	#include "bitlib/bit-iterator/bit.hpp"
18	// Third-party libraries
19	// Miscellaneous
20	namespace bit {
21	// ========================================================================== //
22	struct equal_impl;
23
24	// Status: Does not work for Input/Output iterators due to distance call
25	template <typename RandomAccessIt1, typename RandomAccessIt2>
26	constexpr bool equal(	7,594✔
27	const bit_iterator<RandomAccessIt1>& first,
28	const bit_iterator<RandomAccessIt1>& last,
29	const bit_iterator<RandomAccessIt2>& d_first) {	7,594✔
30	return with_bit_iterator_adapter<equal_impl>(first, last, d_first);	22,782✔
31	}	7,594✔
32
33	// ---------------------------- Equal Algorithms ----------------------------- //
34
35	// Status: Does not work for Input/Output iterators due to distance call
36	struct equal_impl {
37	template <typename RandomAccessIt1, typename RandomAccessIt2>
38	constexpr bool operator()(	7,594✔
39	bit_iterator<RandomAccessIt1> first,
40	bit_iterator<RandomAccessIt1> last,
41	bit_iterator<RandomAccessIt2> d_first) {	7,594✔
42	// Types and constants
43	using dst_word_type = typename bit_iterator<RandomAccessIt2>::word_type;	7,594✔
44	using src_word_type = typename bit_iterator<RandomAccessIt1>::word_type;	7,594✔
45	static_assert(::std::is_same<dst_word_type, src_word_type>::value, "Underlying word types must be equal");	7,594✔
46	using word_type = dst_word_type;	7,594✔
47	using size_type = typename bit_iterator<RandomAccessIt2>::size_type;	7,594✔
48	constexpr size_type digits = binary_digits<word_type>::value;	15,188✔
49
50	// Assertions
51	_assert_range_viability(first, last);	15,188✔
52	if (first == last) {	15,188!
53	return true;	580✔
54	}	300✔
55
56	// Initialization
57	const bool is_d_first_aligned = d_first.position() == 0;	14,608✔
58	size_type total_bits_to_check = distance(first, last);	14,608✔
59	size_type remaining_bits_to_check = total_bits_to_check;	14,608✔
60	auto it = d_first.base();	14,608✔
61
62	// d_first is not aligned.
63	if (!is_d_first_aligned) {	14,608!
64	const size_type partial_bits_to_check = ::std::min(	12,476✔
65	remaining_bits_to_check,	6,035✔
66	digits - d_first.position());	18,917✔
67	const word_type mask = _mask<word_type>(partial_bits_to_check) << d_first.position();	12,476✔
68	const word_type comp = static_cast<word_type>(	12,476✔
69	get_word<word_type>(first, partial_bits_to_check)	12,476✔
70	<< d_first.position());	12,476✔
71	if ((mask & *it) != (mask & comp)) {	12,476!
72	return false;	2,979✔
73	}	1,073✔
74	remaining_bits_to_check -= partial_bits_to_check;	9,497✔
75	advance(first, partial_bits_to_check);	9,497✔
76	it++;	9,497✔
77	}	4,962✔
78
79	if (remaining_bits_to_check > 0) {	11,629!
80	const bool is_first_aligned = first.position() == 0;	9,472✔
81	// d_first will be aligned at this point
82	if (is_first_aligned && remaining_bits_to_check >= digits) {	9,472!
83	auto N = ::std::distance(first.base(), last.base());	7,432✔
84	bool found_mismatch = !::std::equal(first.base(), last.base(), it);	7,432✔
85	if (found_mismatch) {	7,432!
86	return false;	1,188✔
87	}	959✔
88	it += N;	6,244✔
89	first += digits * N;	6,244✔
90	remaining_bits_to_check -= digits * N;	6,244✔
91	} else {	6,244✔
92	// TODO benchmark if its faster to ::std::check the entire range then shift
93	while (remaining_bits_to_check >= digits) {	2,040!
NEW 94	if (*it != get_word<word_type>(first, digits)) {	×
UNCOV 95	return false;	×
96	}
NEW 97	remaining_bits_to_check -= digits;	×
NEW 98	it++;	×
NEW 99	advance(first, digits);	×
100	}
101	}	1,039✔
102	if (remaining_bits_to_check > 0) {	8,284!
103	const word_type mask = _mask<word_type>(remaining_bits_to_check);	7,826✔
104	const word_type comp = get_word<word_type>(first, remaining_bits_to_check);	7,826✔
105	if ((mask & *it) != (mask & comp)) {	7,826!
106	return false;	124✔
107	}	85✔
108	}	3,930✔
109	}	4,155✔
110	return true;	10,317✔
111	}	6,221✔
112	};
113	// -------------------------------------------------------------------------- //
114
115
116
117	// ========================================================================== //
118	} // namespace bit
119	#endif // _EQUAL_HPP_INCLUDED
120	// ========================================================================== //

PeterCDMcLean / BitLib / 15624655410

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