james.stone_381

Committed 25 Sep 2023 06:35PM UTC coverage: 90.919% (+0.03%) from 90.892%

Build # james.stone_381

Build Type

Pull #6670

Evergreen

Committed by

ironage

Commit Message

optimize: only compare strings once

Pull Request Pull Request #6670: Sorting stage 3

Run Details

97114 of 177952 branches covered (0.0%)

879 of 887 new or added lines in 12 files covered. (99.1%)

105 existing lines in 17 files now uncovered.

236103 of 259684 relevant lines covered (90.92%)

7062315.99 hits per line

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

86.17

/src/realm/set.cpp

/*************************************************************************
 *
 * Copyright 2020 Realm Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 **************************************************************************/


#include "realm/set.hpp"
#include "realm/array_basic.hpp"
#include "realm/array_integer.hpp"
#include "realm/array_bool.hpp"
#include "realm/array_string.hpp"
#include "realm/array_binary.hpp"
#include "realm/array_timestamp.hpp"
#include "realm/array_decimal128.hpp"
#include "realm/array_fixed_bytes.hpp"
#include "realm/array_typed_link.hpp"
#include "realm/array_mixed.hpp"
#include "realm/replication.hpp"

namespace realm {

/********************************** SetBase *********************************/

void SetBase::insert_repl(Replication* repl, size_t index, Mixed value) const
{
    repl->set_insert(*this, index, value);
}

void SetBase::erase_repl(Replication* repl, size_t index, Mixed value) const
{
    repl->set_erase(*this, index, value);
}

void SetBase::clear_repl(Replication* repl) const
{
    repl->set_clear(*this);
}

std::vector<Mixed> SetBase::convert_to_mixed_set(const CollectionBase& rhs)
{
    std::vector<Mixed> mixed;
    mixed.reserve(rhs.size());
    for (size_t i = 0; i < rhs.size(); i++) {
        mixed.push_back(rhs.get_any(i));
    }
    std::sort(mixed.begin(), mixed.end(), SetElementLessThan<Mixed>());
    mixed.erase(std::unique(mixed.begin(), mixed.end()), mixed.end());
    return mixed;
}

template <>
void CollectionBaseImpl<SetBase>::to_json(std::ostream& out, size_t, JSONOutputMode output_mode,
                                          util::FunctionRef<void(const Mixed&)> fn) const
{
    int closing = 0;
    if (output_mode == output_mode_xjson_plus) {
        out << "{ \"$set\": ";
        closing++;
    }

    out << "[";
    auto sz = size();
    for (size_t i = 0; i < sz; i++) {
        if (i > 0)
            out << ",";
        Mixed val = get_any(i);
        if (val.is_type(type_TypedLink)) {
            fn(val);
        }
        else {
            val.to_json(out, output_mode);
        }
    }
    out << "]";
    while (closing--)
        out << "}";
}

/********************************* Set<Key> *********************************/

template <>
void Set<ObjKey>::do_insert(size_t ndx, ObjKey target_key)
{
    auto origin_table = get_table_unchecked();
    auto target_table_key = origin_table->get_opposite_table_key(m_col_key);
    set_backlink(m_col_key, {target_table_key, target_key});
    m_tree->insert(ndx, target_key);
    if (target_key.is_unresolved()) {
        m_tree->set_context_flag(true);
    }
}

template <>
void Set<ObjKey>::do_erase(size_t ndx)
{
    auto origin_table = get_table_unchecked();
    auto target_table_key = origin_table->get_opposite_table_key(m_col_key);
    ObjKey old_key = get(ndx);
    CascadeState state(old_key.is_unresolved() ? CascadeState::Mode::All : CascadeState::Mode::Strong);

    bool recurse = remove_backlink(m_col_key, {target_table_key, old_key}, state);

    m_tree->erase(ndx);

    if (recurse) {
        _impl::TableFriend::remove_recursive(*origin_table, state); // Throws
    }
    if (old_key.is_unresolved()) {
        // We might have removed the last unresolved link - check it

        // FIXME: Exploit the fact that the values are sorted and unresolved
        // keys have a negative value.
        _impl::check_for_last_unresolved(m_tree.get());
    }
}

template <>
void Set<ObjKey>::do_clear()
{
    size_t ndx = size();
    while (ndx--) {
        do_erase(ndx);
    }

    m_tree->set_context_flag(false);
}

template <>
void Set<ObjLink>::do_insert(size_t ndx, ObjLink target_link)
{
    set_backlink(m_col_key, target_link);
    m_tree->insert(ndx, target_link);
}

template <>
void Set<ObjLink>::do_erase(size_t ndx)
{
    ObjLink old_link = get(ndx);
    CascadeState state(old_link.get_obj_key().is_unresolved() ? CascadeState::Mode::All : CascadeState::Mode::Strong);

    bool recurse = remove_backlink(m_col_key, old_link, state);

    m_tree->erase(ndx);

    if (recurse) {
        auto table = get_table_unchecked();
        _impl::TableFriend::remove_recursive(*table, state); // Throws
    }
}

template <>
void Set<Mixed>::do_insert(size_t ndx, Mixed value)
{
    REALM_ASSERT(!value.is_type(type_Link));
    if (value.is_type(type_TypedLink)) {
        auto target_link = value.get<ObjLink>();
        get_table_unchecked()->get_parent_group()->validate(target_link);
        set_backlink(m_col_key, target_link);
    }
    m_tree->insert(ndx, value);
}

template <>
void Set<Mixed>::do_erase(size_t ndx)
{
    if (Mixed old_value = get(ndx); old_value.is_type(type_TypedLink)) {
        auto old_link = old_value.get<ObjLink>();

        CascadeState state(old_link.get_obj_key().is_unresolved() ? CascadeState::Mode::All
                                                                  : CascadeState::Mode::Strong);
        bool recurse = remove_backlink(m_col_key, old_link, state);

        m_tree->erase(ndx);

        if (recurse) {
            auto table = get_table_unchecked();
            _impl::TableFriend::remove_recursive(*table, state); // Throws
        }
    }
    else {
        m_tree->erase(ndx);
    }
}

template <>
void Set<Mixed>::do_clear()
{
    size_t ndx = size();
    while (ndx--) {
        do_erase(ndx);
    }
}

template <>
void Set<Mixed>::migrate()
{
    // We should just move all string values to be before the binary values
    size_t first_binary = size();
    for (size_t n = 0; n < size(); n++) {
        if (m_tree->get(n).is_type(type_Binary)) {
            first_binary = n;
            break;
        }
    }

    for (size_t n = first_binary; n < size(); n++) {
        if (m_tree->get(n).is_type(type_String)) {
            m_tree->insert(first_binary, Mixed());
            m_tree->swap(n + 1, first_binary);
            m_tree->erase(n + 1);
            first_binary++;
        }
    }
}

template <class T>
void Set<T>::do_resort(size_t start, size_t end)
{
    if (end > size()) {
        end = size();
    }
    if (start >= end) {
        return;
    }
    std::vector<size_t> indices;
    indices.resize(end - start);
    std::iota(indices.begin(), indices.end(), 0);
    std::sort(indices.begin(), indices.end(), [&](auto a, auto b) {
        return get(a + start) < get(b + start);
    });
    for (size_t i = 0; i < indices.size(); ++i) {
        if (indices[i] != i) {
            m_tree->swap(i + start, start + indices[i]);
            auto it = std::find(indices.begin() + i, indices.end(), i);
            REALM_ASSERT(it != indices.end());
            *it = indices[i];
            indices[i] = i;
        }
    }
}

template <>
void Set<Mixed>::migrate_strings()
{
    // sort order of strings changed
    const size_t set_size = size();
    size_t first_binary = set_size;
    size_t first_string = set_size;
    for (size_t n = 0; n < set_size; n++) {
        auto val = m_tree->get(n);
        if (val.is_type(type_String) && first_string == set_size) {
            first_string = n;
            continue;
        }
        if (val.is_type(type_Binary)) {
            first_binary = n;
            break;
        }
    }
    do_resort(first_string, first_binary);
}

template <>
void Set<StringData>::migrate_strings()
{
    // sort order of strings changed
    do_resort(0, size());
}

void LnkSet::remove_target_row(size_t link_ndx)
{
    // Deleting the object will automatically remove all links
    // to it. So we do not have to manually remove the deleted link
    ObjKey k = get(link_ndx);
    get_target_table()->remove_object(k);
}

void LnkSet::remove_all_target_rows()
{
    if (m_set.update()) {
        _impl::TableFriend::batch_erase_rows(*get_target_table(), *m_set.m_tree);
    }
}

bool LnkSet::is_subset_of(const CollectionBase& rhs) const
{
    return this->m_set.is_subset_of(rhs);
}

bool LnkSet::is_strict_subset_of(const CollectionBase& rhs) const
{
    return this->m_set.is_strict_subset_of(rhs);
}

bool LnkSet::is_superset_of(const CollectionBase& rhs) const
{
    return this->m_set.is_superset_of(rhs);
}

bool LnkSet::is_strict_superset_of(const CollectionBase& rhs) const
{
    return this->m_set.is_strict_superset_of(rhs);
}

bool LnkSet::intersects(const CollectionBase& rhs) const
{
    return this->m_set.intersects(rhs);
}

bool LnkSet::set_equals(const CollectionBase& rhs) const
{
    return this->m_set.set_equals(rhs);
}

void LnkSet::to_json(std::ostream& out, size_t link_depth, JSONOutputMode output_mode,
                     util::FunctionRef<void(const Mixed&)> fn) const
{
    auto [open_str, close_str] = get_open_close_strings(link_depth, output_mode);

    out << open_str;
    out << "[";

    auto sz = m_set.size();
    for (size_t i = 0; i < sz; i++) {
        if (i > 0)
            out << ",";
        Mixed val(m_set.get(i));
        fn(val);
    }

    out << "]";
    out << close_str;
}


void set_sorted_indices(size_t sz, std::vector<size_t>& indices, bool ascending)
{
    indices.resize(sz);
    if (ascending) {
        std::iota(indices.begin(), indices.end(), 0);
    }
    else {
        std::iota(indices.rbegin(), indices.rend(), 0);
    }
}

template <typename Iterator>
static bool partition_points(const Set<Mixed>& set, std::vector<size_t>& indices, Iterator& first_string,
                             Iterator& first_binary, Iterator& end)
{
    first_string = std::partition_point(indices.begin(), indices.end(), [&](size_t i) {
        return set.get(i).is_type(type_Bool, type_Int, type_Float, type_Double, type_Decimal);
    });
    if (first_string == indices.end() || !set.get(*first_string).is_type(type_String))
        return false;
    first_binary = std::partition_point(first_string + 1, indices.end(), [&](size_t i) {
        return set.get(i).is_type(type_String);
    });
    if (first_binary == indices.end() || !set.get(*first_binary).is_type(type_Binary))
        return false;
    end = std::partition_point(first_binary + 1, indices.end(), [&](size_t i) {
        return set.get(i).is_type(type_Binary);
    });
    return true;
}

template <>
void Set<Mixed>::sort(std::vector<size_t>& indices, bool ascending) const
{
    set_sorted_indices(size(), indices, true);

    // The on-disk order is bool -> numbers -> string -> binary -> others
    // We want to merge the string and binary sections to match the sort order
    // of other collections. To do this we find the three partition points
    // where the first string occurs, the first binary occurs, and the first
    // non-binary after binaries occurs. If there's no strings or binaries we
    // don't have to do anything. If they're both non-empty, we perform an
    // in-place merge on the strings and binaries.
    std::vector<size_t>::iterator first_string, first_binary, end;
    if (partition_points(*this, indices, first_string, first_binary, end)) {
        std::inplace_merge(first_string, first_binary, end, [&](auto a, auto b) {
            return get(a) < get(b);
        });
    }
    if (!ascending) {
        std::reverse(indices.begin(), indices.end());
    }
}

} // namespace realm

1	/*************************************************************************
2	*
3	* Copyright 2020 Realm Inc.
4	*
5	* Licensed under the Apache License, Version 2.0 (the "License");
6	* you may not use this file except in compliance with the License.
7	* You may obtain a copy of the License at
8	*
9	* http://www.apache.org/licenses/LICENSE-2.0
10	*
11	* Unless required by applicable law or agreed to in writing, software
12	* distributed under the License is distributed on an "AS IS" BASIS,
13	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14	* See the License for the specific language governing permissions and
15	* limitations under the License.
16	*
17	**************************************************************************/
18
19
20	#include "realm/set.hpp"
21	#include "realm/array_basic.hpp"
22	#include "realm/array_integer.hpp"
23	#include "realm/array_bool.hpp"
24	#include "realm/array_string.hpp"
25	#include "realm/array_binary.hpp"
26	#include "realm/array_timestamp.hpp"
27	#include "realm/array_decimal128.hpp"
28	#include "realm/array_fixed_bytes.hpp"
29	#include "realm/array_typed_link.hpp"
30	#include "realm/array_mixed.hpp"
31	#include "realm/replication.hpp"
32
33	namespace realm {
34
35	/******************************** SetBase *******************************/
36
37	void SetBase::insert_repl(Replication* repl, size_t index, Mixed value) const
38	{	60,708✔
39	repl->set_insert(*this, index, value);	60,708✔
40	}	60,708✔
41
42	void SetBase::erase_repl(Replication* repl, size_t index, Mixed value) const
43	{	9,462✔
44	repl->set_erase(*this, index, value);	9,462✔
45	}	9,462✔
46
47	void SetBase::clear_repl(Replication* repl) const
48	{	2,412✔
49	repl->set_clear(*this);	2,412✔
50	}	2,412✔
51
52	std::vector<Mixed> SetBase::convert_to_mixed_set(const CollectionBase& rhs)
53	{	522✔
54	std::vector<Mixed> mixed;	522✔
55	mixed.reserve(rhs.size());	522✔
56	for (size_t i = 0; i < rhs.size(); i++) {	2,754✔
57	mixed.push_back(rhs.get_any(i));	2,232✔
58	}	2,232✔
59	std::sort(mixed.begin(), mixed.end(), SetElementLessThan<Mixed>());	522✔
60	mixed.erase(std::unique(mixed.begin(), mixed.end()), mixed.end());	522✔
61	return mixed;	522✔
62	}	522✔
63
64	template <>
65	void CollectionBaseImpl<SetBase>::to_json(std::ostream& out, size_t, JSONOutputMode output_mode,
66	util::FunctionRef<void(const Mixed&)> fn) const
67	{	300✔
68	int closing = 0;	300✔
69	if (output_mode == output_mode_xjson_plus) {	300✔
70	out << "{ \"$set\": ";	90✔
71	closing++;	90✔
72	}	90✔
73		150✔
74	out << "[";	300✔
75	auto sz = size();	300✔
76	for (size_t i = 0; i < sz; i++) {	606✔
77	if (i > 0)	306✔
78	out << ",";	6✔
79	Mixed val = get_any(i);	306✔
80	if (val.is_type(type_TypedLink)) {	306✔
81	fn(val);	6✔
82	}	6✔
83	else {	300✔
84	val.to_json(out, output_mode);	300✔
85	}	300✔
86	}	306✔
87	out << "]";	300✔
88	while (closing--)	390✔
89	out << "}";	90✔
90	}	300✔
91
92	/******************************* Set<Key> *******************************/
93
94	template <>
95	void Set<ObjKey>::do_insert(size_t ndx, ObjKey target_key)
96	{	16,926✔
97	auto origin_table = get_table_unchecked();	16,926✔
98	auto target_table_key = origin_table->get_opposite_table_key(m_col_key);	16,926✔
99	set_backlink(m_col_key, {target_table_key, target_key});	16,926✔
100	m_tree->insert(ndx, target_key);	16,926✔
101	if (target_key.is_unresolved()) {	16,926✔
102	m_tree->set_context_flag(true);	54✔
103	}	54✔
104	}	16,926✔
105
106	template <>
107	void Set<ObjKey>::do_erase(size_t ndx)
108	{	5,592✔
109	auto origin_table = get_table_unchecked();	5,592✔
110	auto target_table_key = origin_table->get_opposite_table_key(m_col_key);	5,592✔
111	ObjKey old_key = get(ndx);	5,592✔
112	CascadeState state(old_key.is_unresolved() ? CascadeState::Mode::All : CascadeState::Mode::Strong);	5,586✔
113		2,796✔
114	bool recurse = remove_backlink(m_col_key, {target_table_key, old_key}, state);	5,592✔
115		2,796✔
116	m_tree->erase(ndx);	5,592✔
117		2,796✔
118	if (recurse) {	5,592✔
119	_impl::TableFriend::remove_recursive(*origin_table, state); // Throws	×
120	}	×
121	if (old_key.is_unresolved()) {	5,592✔
122	// We might have removed the last unresolved link - check it	6✔
123		6✔
124	// FIXME: Exploit the fact that the values are sorted and unresolved	6✔
125	// keys have a negative value.	6✔
126	_impl::check_for_last_unresolved(m_tree.get());	12✔
127	}	12✔
128	}	5,592✔
129
130	template <>
131	void Set<ObjKey>::do_clear()
132	{	924✔
133	size_t ndx = size();	924✔
134	while (ndx--) {	4,752✔
135	do_erase(ndx);	3,828✔
136	}	3,828✔
137		462✔
138	m_tree->set_context_flag(false);	924✔
139	}	924✔
140
141	template <>
142	void Set<ObjLink>::do_insert(size_t ndx, ObjLink target_link)
143	{	×
144	set_backlink(m_col_key, target_link);	×
145	m_tree->insert(ndx, target_link);	×
146	}	×
147
148	template <>
149	void Set<ObjLink>::do_erase(size_t ndx)
150	{	×
151	ObjLink old_link = get(ndx);	×
152	CascadeState state(old_link.get_obj_key().is_unresolved() ? CascadeState::Mode::All : CascadeState::Mode::Strong);	×
153
154	bool recurse = remove_backlink(m_col_key, old_link, state);	×
155
156	m_tree->erase(ndx);	×
157
158	if (recurse) {	×
159	auto table = get_table_unchecked();	×
160	_impl::TableFriend::remove_recursive(*table, state); // Throws	×
161	}	×
162	}	×
163
164	template <>
165	void Set<Mixed>::do_insert(size_t ndx, Mixed value)
166	{	8,652✔
167	REALM_ASSERT(!value.is_type(type_Link));	8,652✔
168	if (value.is_type(type_TypedLink)) {	8,652✔
169	auto target_link = value.get<ObjLink>();	4,398✔
170	get_table_unchecked()->get_parent_group()->validate(target_link);	4,398✔
171	set_backlink(m_col_key, target_link);	4,398✔
172	}	4,398✔
173	m_tree->insert(ndx, value);	8,652✔
174	}	8,652✔
175
176	template <>
177	void Set<Mixed>::do_erase(size_t ndx)
178	{	3,618✔
179	if (Mixed old_value = get(ndx); old_value.is_type(type_TypedLink)) {	3,618✔
180	auto old_link = old_value.get<ObjLink>();	1,032✔
181		516✔
182	CascadeState state(old_link.get_obj_key().is_unresolved() ? CascadeState::Mode::All	516✔
183	: CascadeState::Mode::Strong);	1,032✔
184	bool recurse = remove_backlink(m_col_key, old_link, state);	1,032✔
185		516✔
186	m_tree->erase(ndx);	1,032✔
187		516✔
188	if (recurse) {	1,032✔
189	auto table = get_table_unchecked();	×
190	_impl::TableFriend::remove_recursive(*table, state); // Throws	×
191	}	×
192	}	1,032✔
193	else {	2,586✔
194	m_tree->erase(ndx);	2,586✔
195	}	2,586✔
196	}	3,618✔
197
198	template <>
199	void Set<Mixed>::do_clear()
200	{	252✔
201	size_t ndx = size();	252✔
202	while (ndx--) {	2,292✔
203	do_erase(ndx);	2,040✔
204	}	2,040✔
205	}	252✔
206
207	template <>
208	void Set<Mixed>::migrate()
209	{	6✔
210	// We should just move all string values to be before the binary values	3✔
211	size_t first_binary = size();	6✔
212	for (size_t n = 0; n < size(); n++) {	24✔
213	if (m_tree->get(n).is_type(type_Binary)) {	24✔
214	first_binary = n;	6✔
215	break;	6✔
216	}	6✔
217	}	24✔
218		3✔
219	for (size_t n = first_binary; n < size(); n++) {	36✔
220	if (m_tree->get(n).is_type(type_String)) {	30✔
221	m_tree->insert(first_binary, Mixed());	12✔
222	m_tree->swap(n + 1, first_binary);	12✔
223	m_tree->erase(n + 1);	12✔
224	first_binary++;	12✔
225	}	12✔
226	}	30✔
227	}	6✔
228
229	template <class T>
230	void Set<T>::do_resort(size_t start, size_t end)
231	{	18✔
232	if (end > size()) {	18✔
NEW 233	end = size();	×
NEW 234	}	×
235	if (start >= end) {	18✔
NEW 236	return;	×
NEW 237	}	×
238	std::vector<size_t> indices;	18✔
239	indices.resize(end - start);	18✔
240	std::iota(indices.begin(), indices.end(), 0);	18✔
241	std::sort(indices.begin(), indices.end(), [&](auto a, auto b) {	570✔
242	return get(a + start) < get(b + start);	570✔
243	});	570✔
244	for (size_t i = 0; i < indices.size(); ++i) {	198✔
245	if (indices[i] != i) {	180✔
246	m_tree->swap(i + start, start + indices[i]);	126✔
247	auto it = std::find(indices.begin() + i, indices.end(), i);	126✔
248	REALM_ASSERT(it != indices.end());	126✔
249	*it = indices[i];	126✔
250	indices[i] = i;	126✔
251	}	126✔
252	}	180✔
253	}	18✔
254
255	template <>
256	void Set<Mixed>::migrate_strings()
257	{	12✔
258	// sort order of strings changed	6✔
259	const size_t set_size = size();	12✔
260	size_t first_binary = set_size;	12✔
261	size_t first_string = set_size;	12✔
262	for (size_t n = 0; n < set_size; n++) {	138✔
263	auto val = m_tree->get(n);	138✔
264	if (val.is_type(type_String) && first_string == set_size) {	138✔
265	first_string = n;	12✔
266	continue;	12✔
267	}	12✔
268	if (val.is_type(type_Binary)) {	126✔
269	first_binary = n;	12✔
270	break;	12✔
271	}	12✔
272	}	126✔
273	do_resort(first_string, first_binary);	12✔
274	}	12✔
275
276	template <>
277	void Set<StringData>::migrate_strings()
278	{	6✔
279	// sort order of strings changed	3✔
280	do_resort(0, size());	6✔
281	}	6✔
282
283	void LnkSet::remove_target_row(size_t link_ndx)
284	{	×
285	// Deleting the object will automatically remove all links
286	// to it. So we do not have to manually remove the deleted link
287	ObjKey k = get(link_ndx);	×
288	get_target_table()->remove_object(k);	×
289	}	×
290
291	void LnkSet::remove_all_target_rows()
292	{	510✔
293	if (m_set.update()) {	510✔
294	_impl::TableFriend::batch_erase_rows(get_target_table(), m_set.m_tree);	510✔
295	}	510✔
296	}	510✔
297
298	bool LnkSet::is_subset_of(const CollectionBase& rhs) const
299	{	24✔
300	return this->m_set.is_subset_of(rhs);	24✔
301	}	24✔
302
303	bool LnkSet::is_strict_subset_of(const CollectionBase& rhs) const
304	{	×
305	return this->m_set.is_strict_subset_of(rhs);	×
306	}	×
307
308	bool LnkSet::is_superset_of(const CollectionBase& rhs) const
309	{	×
310	return this->m_set.is_superset_of(rhs);	×
311	}	×
312
313	bool LnkSet::is_strict_superset_of(const CollectionBase& rhs) const
314	{	×
315	return this->m_set.is_strict_superset_of(rhs);	×
316	}	×
317
318	bool LnkSet::intersects(const CollectionBase& rhs) const
319	{	36✔
320	return this->m_set.intersects(rhs);	36✔
321	}	36✔
322
323	bool LnkSet::set_equals(const CollectionBase& rhs) const
324	{	×
325	return this->m_set.set_equals(rhs);	×
326	}	×
327
328	void LnkSet::to_json(std::ostream& out, size_t link_depth, JSONOutputMode output_mode,
329	util::FunctionRef<void(const Mixed&)> fn) const
330	{	72✔
331	auto [open_str, close_str] = get_open_close_strings(link_depth, output_mode);	72✔
332		36✔
333	out << open_str;	72✔
334	out << "[";	72✔
335		36✔
336	auto sz = m_set.size();	72✔
337	for (size_t i = 0; i < sz; i++) {	144✔
338	if (i > 0)	72✔
339	out << ",";	24✔
340	Mixed val(m_set.get(i));	72✔
341	fn(val);	72✔
342	}	72✔
343		36✔
344	out << "]";	72✔
345	out << close_str;	72✔
346	}	72✔
347
348
349	void set_sorted_indices(size_t sz, std::vector<size_t>& indices, bool ascending)
350	{	31,878✔
351	indices.resize(sz);	31,878✔
352	if (ascending) {	31,878✔
353	std::iota(indices.begin(), indices.end(), 0);	31,626✔
354	}	31,626✔
355	else {	252✔
356	std::iota(indices.rbegin(), indices.rend(), 0);	252✔
357	}	252✔
358	}	31,878✔
359
360	template <typename Iterator>
361	static bool partition_points(const Set<Mixed>& set, std::vector<size_t>& indices, Iterator& first_string,
362	Iterator& first_binary, Iterator& end)
363	{	1,782✔
364	first_string = std::partition_point(indices.begin(), indices.end(), [&](size_t i) {	1,734✔
365	return set.get(i).is_type(type_Bool, type_Int, type_Float, type_Double, type_Decimal);	1,686✔
366	});	1,686✔
367	if (first_string == indices.end() \|\| !set.get(*first_string).is_type(type_String))	1,782✔
368	return false;	1,716✔
369	first_binary = std::partition_point(first_string + 1, indices.end(), [&](size_t i) {	150✔
370	return set.get(i).is_type(type_String);	150✔
371	});	150✔
372	if (first_binary == indices.end() \|\| !set.get(*first_binary).is_type(type_Binary))	66✔
373	return false;	30✔
374	end = std::partition_point(first_binary + 1, indices.end(), [&](size_t i) {	72✔
375	return set.get(i).is_type(type_Binary);	72✔
376	});	72✔
377	return true;	36✔
378	}	36✔
379
380	template <>
381	void Set<Mixed>::sort(std::vector<size_t>& indices, bool ascending) const
382	{	1,782✔
383	set_sorted_indices(size(), indices, true);	1,782✔
384		891✔
385	// The on-disk order is bool -> numbers -> string -> binary -> others	891✔
386	// We want to merge the string and binary sections to match the sort order	891✔
387	// of other collections. To do this we find the three partition points	891✔
388	// where the first string occurs, the first binary occurs, and the first	891✔
389	// non-binary after binaries occurs. If there's no strings or binaries we	891✔
390	// don't have to do anything. If they're both non-empty, we perform an	891✔
391	// in-place merge on the strings and binaries.	891✔
392	std::vector<size_t>::iterator first_string, first_binary, end;	1,782✔
393	if (partition_points(*this, indices, first_string, first_binary, end)) {	1,782✔
394	std::inplace_merge(first_string, first_binary, end, [&](auto a, auto b) {	72✔
395	return get(a) < get(b);	72✔
396	});	72✔
397	}	36✔
398	if (!ascending) {	1,782✔
399	std::reverse(indices.begin(), indices.end());	36✔
400	}	36✔
401	}	1,782✔
402
403	} // namespace realm

realm / realm-core / james.stone_381

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