13069453084

Committed 31 Jan 2025 08:55AM UTC coverage: 82.728% (-0.007%) from 82.735%

Build # 13069453084

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #1604 from evoskuil/master

Set _CRTDBG_MAP_ALLOC for vc++ debug mode leak tracking.

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

15 existing lines in 11 files now uncovered.

10039 of 12135 relevant lines covered (82.73%)

3871639.49 hits per line

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

97.78

/include/bitcoin/system/impl/data/collection.ipp

/**
 * Copyright (c) 2011-2025 libbitcoin developers (see AUTHORS)
 *
 * This file is part of libbitcoin.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef LIBBITCOIN_SYSTEM_DATA_COLLECTION_IPP
#define LIBBITCOIN_SYSTEM_DATA_COLLECTION_IPP

#include <algorithm>
#include <array>
#include <iterator>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>
#include <bitcoin/system/define.hpp>
#include <bitcoin/system/math/math.hpp>

namespace libbitcoin {
namespace system {

// TODO: std::binary_search?
// TODO: provide optional comparison function?
// en.cppreference.com/w/cpp/utility/functional/less
// It is the responsibility of the caller to ensure that parameters implement
// sufficient comparison operator overloads (LT and GT). Either the 'list' 
// elements must implement (at least) member comparison operator overloads or
// the 'value' parameter must implement binary comparison operator overloads.
// Be aware that C-style arrays/strings are compared by pointers, not values.
// A 'list' of C-style arrays of char may be seached with std::string 'value'.
// std::string comparisons are not locale aware.
template <typename Collection, typename Element>
typename Collection::difference_type
constexpr binary_search(const Collection& list,
    const Element& element) NOEXCEPT
{
    if (std::empty(list))
        return negative_one;

    typename Collection::difference_type left = zero;
    typename Collection::difference_type right = sub1(std::size(list));

    while (left <= right)
    {
        auto middle = to_half(left + right);
        const auto& value = list[middle];

        if (value < element)
            left = add1(middle);
        else if (value > element)
            right = sub1(middle);
        else
            return middle;
    }

    return negative_one;
}

// C++17: Parallel policy for std::transform.
template <typename To, typename From>
inline To projection(const From& source) NOEXCEPT
{
    To out(std::size(source));

    std::transform(std::begin(source), std::end(source), std::begin(out),
        [](const typename From::value_type& element) NOEXCEPT
            -> typename To::value_type
        {
            return { element };
        });

    return out;
}

// C++17: Parallel policy for std::equal.
template <typename Left, typename Right>
constexpr bool deep_equal(const Left& left, const Right& right) NOEXCEPT
{
    return std::equal(std::begin(left), std::end(left),
        std::begin(right), std::end(right),
        [](const auto& first, const auto& second) NOEXCEPT
        {
            return 
                ((first != nullptr && second != nullptr) &&
                (*first == *second)) ||
                (first == nullptr && second == nullptr);
        });
}

// C++17: Parallel policy for std::any_of.
template <typename Collection, typename Element>
constexpr bool contains(const Collection& list,
    const Element& element) NOEXCEPT
{
    return std::find(std::begin(list), std::end(list), element) !=
        std::end(list);
}

// C++17: Parallel policy for std::find_if.
template <typename Collection>
typename Collection::difference_type
constexpr find_pair_position(const Collection& list,
    const typename Collection::value_type::first_type& key) NOEXCEPT
{
    const auto position = std::find_if(std::begin(list), std::end(list),
        [&key](const auto& pair) NOEXCEPT
        {
            return pair.first == key;
        });

    return position == std::end(list) ? negative_one :
        std::distance(std::begin(list), position);
}

// C++17: Parallel policy for std::find.
template <typename Collection>
typename Collection::difference_type
constexpr find_position(const Collection& list,
    const typename Collection::value_type& element) NOEXCEPT
{
    const auto position = std::find(std::begin(list), std::end(list), element);
    return position == std::end(list) ? negative_one :
        std::distance(std::begin(list), position);
}

// Collection requires insert method (vector).
template <typename Collection, typename Predicate>
typename Collection::iterator
inline insert_sorted(Collection& list,
    typename Collection::value_type& element, Predicate predicate) NOEXCEPT
{
    return list.insert(std::upper_bound(std::begin(list),
        std::end(list), element, predicate), element);
}

// Collection requires back and pop_back methods (vector).
template <typename Collection>
typename Collection::value_type
inline pop(Collection& stack) NOEXCEPT
{
    if (std::empty(stack))
        return {};

    typename Collection::value_type element{ std::move(stack.back()) };
    stack.pop_back();
    return element;
}

// Collection requires front and pop_front methods (list).
template <typename Collection>
typename Collection::value_type
inline pop_front(Collection& stack) NOEXCEPT
{
    if (std::empty(stack))
        return {};

    typename Collection::value_type element{ std::move(stack.front()) };
    stack.pop_front();
    return element;
}

// C++17: Parallel policy for std::sort, std::unique.
template <typename Collection>
constexpr bool is_distinct(Collection&& list) NOEXCEPT
{
    std::sort(std::begin(list), std::end(list));
    return std::unique(std::begin(list), std::end(list)) == std::end(list);
}

template <typename Collection>
constexpr bool is_distinct(const Collection& list) NOEXCEPT
{
    Collection copy{ list };
    return is_distinct(copy);
}

// C++17: Parallel policy for std::is_sorted.
template <typename Collection>
constexpr bool is_sorted(const Collection& list) NOEXCEPT
{
    return std::is_sorted(std::begin(list), std::end(list));
}

// C++17: Parallel policy for std::sort, std::erase.
template <typename Collection>
constexpr void distinct(Collection& list) NOEXCEPT
{
    std::sort(std::begin(list), std::end(list));
    list.erase(std::unique(std::begin(list), std::end(list)), std::end(list));
    list.shrink_to_fit();
}

template <typename Collection>
inline Collection distinct(Collection&& list) NOEXCEPT
{
    distinct(list);
    return std::forward<Collection>(list);
}

template <typename Collection>
inline Collection distinct_copy(const Collection& list) NOEXCEPT
{
    return distinct(Collection{ list });
}

template <typename Left, typename Right>
inline Left difference(const Left& left, const Right& right) NOEXCEPT
{
    return difference<Left>(std::begin(left), std::end(left), right);
}

template <typename Left, typename Right>
inline Left difference(const typename Left::const_iterator& begin,
    const typename Left::const_iterator& end, const Right& right) NOEXCEPT
{
    Left copy{};
    copy.reserve(std::distance(begin, end));
    
    // Linear copy since creating a copy, more efficient than multiple erases.
    for (auto min = begin; min != end; ++min)
        if (!contains(right, *min))
            copy.push_back(*min);
    
    copy.shrink_to_fit();
    return copy;
}

template <typename Left, typename Right>
constexpr bool is_intersecting(const Left& left, const Right& right) NOEXCEPT
{
    return is_intersecting<Left>(std::begin(left), std::end(left), right);
}

// C++17: Parallel policy for std::find_first_of.
template <typename Left, typename Right>
constexpr bool is_intersecting(const typename Left::const_iterator& begin,
    const typename Left::const_iterator& end, const Right& right) NOEXCEPT
{
    return std::find_first_of(begin, end, std::begin(right),
        std::end(right)) != end;
}

// C++17: Parallel policy for std::reverse.
template <typename Collection>
inline Collection reverse(Collection&& list) NOEXCEPT
{
    std::reverse(std::begin(list), std::end(list));
    return std::forward<Collection>(list);
}

template <typename Collection>
inline Collection reverse_copy(const Collection& list) NOEXCEPT
{
    return reverse(Collection{ list });
}

// C++17: Parallel policy for std::sort.
template <typename Collection>
constexpr void sort(Collection& list) NOEXCEPT
{
    std::sort(std::begin(list), std::end(list));
}

template <typename Collection>
inline Collection sort(Collection&& list) NOEXCEPT
{
    sort(list);
    return std::forward<Collection>(list);
}

template <typename Collection>
inline Collection sort_copy(const Collection& list) NOEXCEPT
{
    return sort(Collection{ list });
}

// C++17: Parallel policy for std::equal.
template <typename Collection>
constexpr bool starts_with(const typename Collection::const_iterator& begin,
    const typename Collection::const_iterator& end,
    const Collection& value) NOEXCEPT
{
    return !is_lesser(std::distance(begin, end), std::size(value)) &&
        std::equal(std::begin(value), std::end(value), begin);
}

} // namespace system
} // namespace libbitcoin

#endif

1	/**
2	* Copyright (c) 2011-2025 libbitcoin developers (see AUTHORS)
3	*
4	* This file is part of libbitcoin.
5	*
6	* This program is free software: you can redistribute it and/or modify
7	* it under the terms of the GNU Affero General Public License as published by
8	* the Free Software Foundation, either version 3 of the License, or
9	* (at your option) any later version.
10	*
11	* This program is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU Affero General Public License for more details.
15	*
16	* You should have received a copy of the GNU Affero General Public License
17	* along with this program. If not, see <http://www.gnu.org/licenses/>.
18	*/
19	#ifndef LIBBITCOIN_SYSTEM_DATA_COLLECTION_IPP
20	#define LIBBITCOIN_SYSTEM_DATA_COLLECTION_IPP
21
22	#include <algorithm>
23	#include <array>
24	#include <iterator>
25	#include <memory>
26	#include <type_traits>
27	#include <utility>
28	#include <vector>
29	#include <bitcoin/system/define.hpp>
30	#include <bitcoin/system/math/math.hpp>
31
32	namespace libbitcoin {
33	namespace system {
34
35	// TODO: std::binary_search?
36	// TODO: provide optional comparison function?
37	// en.cppreference.com/w/cpp/utility/functional/less
38	// It is the responsibility of the caller to ensure that parameters implement
39	// sufficient comparison operator overloads (LT and GT). Either the 'list'
40	// elements must implement (at least) member comparison operator overloads or
41	// the 'value' parameter must implement binary comparison operator overloads.
42	// Be aware that C-style arrays/strings are compared by pointers, not values.
43	// A 'list' of C-style arrays of char may be seached with std::string 'value'.
44	// std::string comparisons are not locale aware.
45	template <typename Collection, typename Element>
46	typename Collection::difference_type
47	constexpr binary_search(const Collection& list,	3,789✔
48	const Element& element) NOEXCEPT
49	{
50	if (std::empty(list))	14✔
51	return negative_one;
52
53	typename Collection::difference_type left = zero;
54	typename Collection::difference_type right = sub1(std::size(list));	13✔
55
56	while (left <= right)	38,656✔
57	{
58	auto middle = to_half(left + right);	38,316✔
59	const auto& value = list[middle];	38,316✔
60
61	if (value < element)	38,316✔
62	left = add1(middle);
63	else if (value > element)	22,035✔
64	right = sub1(middle);
65	else
66	return middle;	3,448✔
67	}
68
69	return negative_one;
70	}
71
72	// C++17: Parallel policy for std::transform.
73	template <typename To, typename From>
74	inline To projection(const From& source) NOEXCEPT	26✔
75	{
76	To out(std::size(source));	26✔
77
78	std::transform(std::begin(source), std::end(source), std::begin(out),	26✔
79	[](const typename From::value_type& element) NOEXCEPT	47✔
80	-> typename To::value_type
81	{
82	return { element };	47✔
83	});
84
85	return out;	26✔
86	}
87
88	// C++17: Parallel policy for std::equal.
89	template <typename Left, typename Right>
90	constexpr bool deep_equal(const Left& left, const Right& right) NOEXCEPT	90✔
91	{
92	return std::equal(std::begin(left), std::end(left),	90✔
93	std::begin(right), std::end(right),
94	[](const auto& first, const auto& second) NOEXCEPT	107✔
95	{
96	return
97	((first != nullptr && second != nullptr) &&	204✔
98	(first == second)) \|\|	214✔
99	(first == nullptr && second == nullptr);	×
100	});	90✔
101	}
102
103	// C++17: Parallel policy for std::any_of.
104	template <typename Collection, typename Element>
105	constexpr bool contains(const Collection& list,	57✔
106	const Element& element) NOEXCEPT
107	{
108	return std::find(std::begin(list), std::end(list), element) !=	57✔
109	std::end(list);	57✔
110	}
111
112	// C++17: Parallel policy for std::find_if.
113	template <typename Collection>
114	typename Collection::difference_type
115	constexpr find_pair_position(const Collection& list,	62✔
116	const typename Collection::value_type::first_type& key) NOEXCEPT
117	{
118	const auto position = std::find_if(std::begin(list), std::end(list),	62✔
119	[&key](const auto& pair) NOEXCEPT	157✔
120	{
121	return pair.first == key;	157✔
122	});
123
124	return position == std::end(list) ? negative_one :	62✔
125	std::distance(std::begin(list), position);	62✔
126	}
127
128	// C++17: Parallel policy for std::find.
129	template <typename Collection>
130	typename Collection::difference_type
131	constexpr find_position(const Collection& list,
132	const typename Collection::value_type& element) NOEXCEPT
133	{
134	const auto position = std::find(std::begin(list), std::end(list), element);
135	return position == std::end(list) ? negative_one :
136	std::distance(std::begin(list), position);
137	}
138
139	// Collection requires insert method (vector).
140	template <typename Collection, typename Predicate>
141	typename Collection::iterator
142	inline insert_sorted(Collection& list,	32✔
143	typename Collection::value_type& element, Predicate predicate) NOEXCEPT
144	{
145	return list.insert(std::upper_bound(std::begin(list),	32✔
146	std::end(list), element, predicate), element);	32✔
147	}
148
149	// Collection requires back and pop_back methods (vector).
150	template <typename Collection>
151	typename Collection::value_type
152	inline pop(Collection& stack) NOEXCEPT	21✔
153	{
154	if (std::empty(stack))	21✔
155	return {};
156
157	typename Collection::value_type element{ std::move(stack.back()) };	2✔
158	stack.pop_back();	18✔
159	return element;	2✔
160	}
161
162	// Collection requires front and pop_front methods (list).
163	template <typename Collection>
164	typename Collection::value_type
165	inline pop_front(Collection& stack) NOEXCEPT	3✔
166	{
167	if (std::empty(stack))	3✔
168	return {};
169
170	typename Collection::value_type element{ std::move(stack.front()) };	2✔
171	stack.pop_front();	2✔
172	return element;	2✔
173	}
174
175	// C++17: Parallel policy for std::sort, std::unique.
176	template <typename Collection>
177	constexpr bool is_distinct(Collection&& list) NOEXCEPT	20✔
178	{
179	std::sort(std::begin(list), std::end(list));	20✔
180	return std::unique(std::begin(list), std::end(list)) == std::end(list);	20✔
181	}
182
183	template <typename Collection>
184	constexpr bool is_distinct(const Collection& list) NOEXCEPT	1✔
185	{
186	Collection copy{ list };
187	return is_distinct(copy);	1✔
188	}
189
190	// C++17: Parallel policy for std::is_sorted.
191	template <typename Collection>
192	constexpr bool is_sorted(const Collection& list) NOEXCEPT	41✔
193	{
194	return std::is_sorted(std::begin(list), std::end(list));	41✔
195	}
196
197	// C++17: Parallel policy for std::sort, std::erase.
198	template <typename Collection>
199	constexpr void distinct(Collection& list) NOEXCEPT	29✔
200	{
201	std::sort(std::begin(list), std::end(list));	29✔
202	list.erase(std::unique(std::begin(list), std::end(list)), std::end(list));	29✔
203	list.shrink_to_fit();
204	}	29✔
205
206	template <typename Collection>
207	inline Collection distinct(Collection&& list) NOEXCEPT	5✔
208	{
209	distinct(list);	5✔
210	return std::forward<Collection>(list);	5✔
211	}
212
213	template <typename Collection>
214	inline Collection distinct_copy(const Collection& list) NOEXCEPT	1✔
215	{
216	return distinct(Collection{ list });	1✔
217	}
218
219	template <typename Left, typename Right>
220	inline Left difference(const Left& left, const Right& right) NOEXCEPT	8✔
221	{
222	return difference<Left>(std::begin(left), std::end(left), right);	8✔
223	}
224
225	template <typename Left, typename Right>
226	inline Left difference(const typename Left::const_iterator& begin,	12✔
227	const typename Left::const_iterator& end, const Right& right) NOEXCEPT
228	{
229	Left copy{};	12✔
230	copy.reserve(std::distance(begin, end));	12✔
231
232	// Linear copy since creating a copy, more efficient than multiple erases.
233	for (auto min = begin; min != end; ++min)	61✔
234	if (!contains(right, *min))	49✔
235	copy.push_back(*min);	29✔
236
237	copy.shrink_to_fit();
238	return copy;	12✔
UNCOV 239	}	×
240
241	template <typename Left, typename Right>
242	constexpr bool is_intersecting(const Left& left, const Right& right) NOEXCEPT	8✔
243	{
244	return is_intersecting<Left>(std::begin(left), std::end(left), right);	8✔
245	}
246
247	// C++17: Parallel policy for std::find_first_of.
248	template <typename Left, typename Right>
249	constexpr bool is_intersecting(const typename Left::const_iterator& begin,	1,966✔
250	const typename Left::const_iterator& end, const Right& right) NOEXCEPT
251	{
252	return std::find_first_of(begin, end, std::begin(right),	1,966✔
253	std::end(right)) != end;	1,966✔
254	}
255
256	// C++17: Parallel policy for std::reverse.
257	template <typename Collection>
258	inline Collection reverse(Collection&& list) NOEXCEPT	34✔
259	{
260	std::reverse(std::begin(list), std::end(list));	34✔
261	return std::forward<Collection>(list);	34✔
262	}
263
264	template <typename Collection>
265	inline Collection reverse_copy(const Collection& list) NOEXCEPT	19✔
266	{
267	return reverse(Collection{ list });	19✔
268	}
269
270	// C++17: Parallel policy for std::sort.
271	template <typename Collection>
272	constexpr void sort(Collection& list) NOEXCEPT	50✔
273	{
274	std::sort(std::begin(list), std::end(list));	50✔
275	}	50✔
276
277	template <typename Collection>
278	inline Collection sort(Collection&& list) NOEXCEPT	37✔
279	{
280	sort(list);	37✔
281	return std::forward<Collection>(list);	37✔
282	}
283
284	template <typename Collection>
285	inline Collection sort_copy(const Collection& list) NOEXCEPT	10✔
286	{
287	return sort(Collection{ list });	10✔
288	}
289
290	// C++17: Parallel policy for std::equal.
291	template <typename Collection>
292	constexpr bool starts_with(const typename Collection::const_iterator& begin,	4✔
293	const typename Collection::const_iterator& end,
294	const Collection& value) NOEXCEPT
295	{
296	return !is_lesser(std::distance(begin, end), std::size(value)) &&
297	std::equal(std::begin(value), std::end(value), begin);	4✔
298	}
299
300	} // namespace system
301	} // namespace libbitcoin
302
303	#endif

libbitcoin / libbitcoin-system / 13069453084

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