1794

Committed 31 Oct 2023 10:48PM UTC coverage: 91.584% (+0.02%) from 91.565%

Build # 1794

Build Type

push

Evergreen

Committed by

web-flow

Commit Message

remove unnecessary callback use for ArrayWithFind::find_action() (#7095)

* remove unnecessary callback use for ArrayWithFind::find_action()

* remove find_action_pattern which hasn't been used in years

* add changeloge note

* lint and address comments

Run Details

92898 of 170898 branches covered (0.0%)

107 of 126 new or added lines in 10 files covered. (84.92%)

47 existing lines in 13 files now uncovered.

230666 of 251863 relevant lines covered (91.58%)

6855264.67 hits per line

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

91.85

/src/realm/array_integer.cpp

/*************************************************************************
 *
 * Copyright 2016 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 <vector>

#include <realm/array_integer_tpl.hpp>
#include <realm/impl/destroy_guard.hpp>
#include <realm/column_integer.hpp>

using namespace realm;

Mixed ArrayInteger::get_any(size_t ndx) const
{
    return Mixed(get(ndx));
}

Mixed ArrayIntNull::get_any(size_t ndx) const
{
    return Mixed(get(ndx));
}

MemRef ArrayIntNull::create_array(Type type, bool context_flag, size_t size, Allocator& alloc)
{
    // Create an array with null value as the first element
    return Array::create(type, context_flag, wtype_Bits, size + 1, 0, alloc); // Throws
}


void ArrayIntNull::init_from_ref(ref_type ref) noexcept
{
    REALM_ASSERT_DEBUG(ref);
    char* header = m_alloc.translate(ref);
    init_from_mem(MemRef{header, ref, m_alloc});
}

void ArrayIntNull::init_from_mem(MemRef mem) noexcept
{
    Array::init_from_mem(mem);

    // We always have the null value stored at position 0
    REALM_ASSERT(m_size > 0);
}

void ArrayIntNull::init_from_parent() noexcept
{
    init_from_ref(get_ref_from_parent());
}

namespace {
int64_t next_null_candidate(int64_t previous_candidate)
{
    uint64_t x = static_cast<uint64_t>(previous_candidate);
    // Increment by a prime number. This guarantees that we will
    // eventually hit every possible integer in the 2^64 range.
    x += 0xfffffffbULL;
    return int64_t(x);
}
}

int_fast64_t ArrayIntNull::choose_random_null(int64_t incoming) const
{
    // We just need any number -- it could have been `rand()`, but
    // random numbers are hard, and we don't want to risk locking mutices
    // or saving state. The top of the stack should be "random enough".
    int64_t candidate = reinterpret_cast<int64_t>(&candidate);

    while (true) {
        candidate = next_null_candidate(candidate);
        if (candidate == incoming) {
            continue;
        }
        if (can_use_as_null(candidate)) {
            return candidate;
        }
    }
}

bool ArrayIntNull::can_use_as_null(int64_t candidate) const
{
    return find_first(candidate) == npos;
}

void ArrayIntNull::replace_nulls_with(int64_t new_null)
{
    int64_t old_null = null_value();
    Array::set(0, new_null);
    size_t i = 1;
    while (true) {
        size_t found = Array::find_first(old_null, i);
        if (found < Array::size()) {
            Array::set(found, new_null);
            i = found + 1;
        }
        else {
            break;
        }
    }
}


void ArrayIntNull::avoid_null_collision(int64_t value)
{
    if (m_width == 64) {
        if (value == null_value()) {
            int_fast64_t new_null = choose_random_null(value);
            replace_nulls_with(new_null);
        }
    }
    else {
        if (value < m_lbound || value >= m_ubound) {
            size_t new_width = bit_width(value);
            int64_t new_upper_bound = Array::ubound_for_width(new_width);

            // We're using upper bound as magic NULL value, so we have to check
            // explicitly that the incoming value doesn't happen to be the new
            // NULL value. If it is, we upgrade one step further.
            if (new_width < 64 && value == new_upper_bound) {
                new_width = (new_width == 0 ? 1 : new_width * 2);
                new_upper_bound = Array::ubound_for_width(new_width);
            }

            int64_t new_null;
            if (new_width == 64) {
                // Width will be upgraded to 64, so we need to pick a random NULL.
                new_null = choose_random_null(value);
            }
            else {
                new_null = new_upper_bound;
            }

            replace_nulls_with(new_null); // Expands array
        }
    }
}

void ArrayIntNull::find_all(IntegerColumn* result, value_type value, size_t col_offset, size_t begin,
                            size_t end) const
{
    // FIXME: We can't use the fast Array::find_all here, because it would put the wrong indices
    // in the result column. Since find_all may be invoked many times for different leaves in the
    // B+tree with the same result column, we also can't simply adjust indices after finding them
    // (because then the first indices would be adjusted multiple times for each subsequent leaf)

    if (end == npos) {
        end = size();
    }

    for (size_t i = begin; i < end; ++i) {
        if (get(i) == value) {
            result->add(col_offset + i);
        }
    }
}

bool ArrayIntNull::find(int cond, value_type value, size_t start, size_t end, QueryStateBase* state) const
{
    return find_impl(cond, value, start, end, state);
}

size_t ArrayIntNull::find_first(value_type value, size_t begin, size_t end) const
{
    return find_first<Equal>(value, begin, end);
}

void ArrayIntNull::get_chunk(size_t ndx, value_type res[8]) const noexcept
{
    // FIXME: Optimize this
    int64_t tmp[8];
    Array::get_chunk(ndx + 1, tmp);
    int64_t null = null_value();
    for (size_t i = 0; i < 8; ++i) {
        res[i] = tmp[i] == null ? util::Optional<int64_t>() : tmp[i];
    }
}

void ArrayIntNull::move(ArrayIntNull& dst, size_t ndx)
{
    size_t sz = size();
    for (size_t i = ndx; i < sz; i++) {
        dst.add(get(i));
    }
    truncate(ndx + 1);
}

1	/*************************************************************************
2	*
3	* Copyright 2016 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	#include <vector>
20
21	#include <realm/array_integer_tpl.hpp>
22	#include <realm/impl/destroy_guard.hpp>
23	#include <realm/column_integer.hpp>
24
25	using namespace realm;
26
27	Mixed ArrayInteger::get_any(size_t ndx) const
28	{	18,773,835✔
29	return Mixed(get(ndx));	18,773,835✔
30	}	18,773,835✔
31
32	Mixed ArrayIntNull::get_any(size_t ndx) const
33	{	12,297,711✔
34	return Mixed(get(ndx));	12,297,711✔
35	}	12,297,711✔
36
37	MemRef ArrayIntNull::create_array(Type type, bool context_flag, size_t size, Allocator& alloc)
38	{	82,554✔
39	// Create an array with null value as the first element	40,494✔
40	return Array::create(type, context_flag, wtype_Bits, size + 1, 0, alloc); // Throws	82,554✔
41	}	82,554✔
42
43
44	void ArrayIntNull::init_from_ref(ref_type ref) noexcept
45	{	80,043,234✔
46	REALM_ASSERT_DEBUG(ref);	80,043,234✔
47	char* header = m_alloc.translate(ref);	80,043,234✔
48	init_from_mem(MemRef{header, ref, m_alloc});	80,043,234✔
49	}	80,043,234✔
50
51	void ArrayIntNull::init_from_mem(MemRef mem) noexcept
52	{	80,098,668✔
53	Array::init_from_mem(mem);	80,098,668✔
54		40,079,193✔
55	// We always have the null value stored at position 0	40,079,193✔
56	REALM_ASSERT(m_size > 0);	80,098,668✔
57	}	80,098,668✔
58
59	void ArrayIntNull::init_from_parent() noexcept
60	{	8,116,206✔
61	init_from_ref(get_ref_from_parent());	8,116,206✔
62	}	8,116,206✔
63
64	namespace {
65	int64_t next_null_candidate(int64_t previous_candidate)
66	{	23,928✔
67	uint64_t x = static_cast<uint64_t>(previous_candidate);	23,928✔
68	// Increment by a prime number. This guarantees that we will	11,964✔
69	// eventually hit every possible integer in the 2^64 range.	11,964✔
70	x += 0xfffffffbULL;	23,928✔
71	return int64_t(x);	23,928✔
72	}	23,928✔
73	}
74
75	int_fast64_t ArrayIntNull::choose_random_null(int64_t incoming) const
76	{	23,922✔
77	// We just need any number -- it could have been `rand()`, but	11,961✔
78	// random numbers are hard, and we don't want to risk locking mutices	11,961✔
79	// or saving state. The top of the stack should be "random enough".	11,961✔
80	int64_t candidate = reinterpret_cast<int64_t>(&candidate);	23,922✔
81		11,961✔
82	while (true) {	23,928✔
83	candidate = next_null_candidate(candidate);	23,928✔
84	if (candidate == incoming) {	23,928✔
85	continue;	6✔
86	}	6✔
87	if (can_use_as_null(candidate)) {	23,922✔
88	return candidate;	23,922✔
89	}	23,922✔
90	}	23,922✔
91	}	23,922✔
92
93	bool ArrayIntNull::can_use_as_null(int64_t candidate) const
94	{	23,922✔
95	return find_first(candidate) == npos;	23,922✔
96	}	23,922✔
97
98	void ArrayIntNull::replace_nulls_with(int64_t new_null)
99	{	97,026✔
100	int64_t old_null = null_value();	97,026✔
101	Array::set(0, new_null);	97,026✔
102	size_t i = 1;	97,026✔
103	while (true) {	147,153✔
104	size_t found = Array::find_first(old_null, i);	147,153✔
105	if (found < Array::size()) {	147,153✔
106	Array::set(found, new_null);	50,127✔
107	i = found + 1;	50,127✔
108	}	50,127✔
109	else {	97,026✔
110	break;	97,026✔
111	}	97,026✔
112	}	147,153✔
113	}	97,026✔
114
115
116	void ArrayIntNull::avoid_null_collision(int64_t value)
117	{	4,192,104✔
118	if (m_width == 64) {	4,192,104✔
119	if (value == null_value()) {	184,752✔
120	int_fast64_t new_null = choose_random_null(value);	6✔
121	replace_nulls_with(new_null);	6✔
122	}	6✔
123	}	184,752✔
124	else {	4,007,352✔
125	if (value < m_lbound \|\| value >= m_ubound) {	4,007,352✔
126	size_t new_width = bit_width(value);	97,020✔
127	int64_t new_upper_bound = Array::ubound_for_width(new_width);	97,020✔
128		47,712✔
129	// We're using upper bound as magic NULL value, so we have to check	47,712✔
130	// explicitly that the incoming value doesn't happen to be the new	47,712✔
131	// NULL value. If it is, we upgrade one step further.	47,712✔
132	if (new_width < 64 && value == new_upper_bound) {	97,020✔
133	new_width = (new_width == 0 ? 1 : new_width * 2);	28,686✔
134	new_upper_bound = Array::ubound_for_width(new_width);	38,199✔
135	}	38,199✔
136		47,712✔
137	int64_t new_null;	97,020✔
138	if (new_width == 64) {	97,020✔
139	// Width will be upgraded to 64, so we need to pick a random NULL.	11,958✔
140	new_null = choose_random_null(value);	23,916✔
141	}	23,916✔
142	else {	73,104✔
143	new_null = new_upper_bound;	73,104✔
144	}	73,104✔
145		47,712✔
146	replace_nulls_with(new_null); // Expands array	97,020✔
147	}	97,020✔
148	}	4,007,352✔
149	}	4,192,104✔
150
151	void ArrayIntNull::find_all(IntegerColumn* result, value_type value, size_t col_offset, size_t begin,
152	size_t end) const
153	{	6✔
154	// FIXME: We can't use the fast Array::find_all here, because it would put the wrong indices	3✔
155	// in the result column. Since find_all may be invoked many times for different leaves in the	3✔
156	// B+tree with the same result column, we also can't simply adjust indices after finding them	3✔
157	// (because then the first indices would be adjusted multiple times for each subsequent leaf)	3✔
158		3✔
159	if (end == npos) {	6✔
160	end = size();	6✔
161	}	6✔
162		3✔
163	for (size_t i = begin; i < end; ++i) {	612✔
164	if (get(i) == value) {	606✔
165	result->add(col_offset + i);	12✔
166	}	12✔
167	}	606✔
168	}	6✔
169
170	bool ArrayIntNull::find(int cond, value_type value, size_t start, size_t end, QueryStateBase* state) const
171	{	×
NEW 172	return find_impl(cond, value, start, end, state);	×
173	}	×
174
175	size_t ArrayIntNull::find_first(value_type value, size_t begin, size_t end) const
176	{	25,824✔
177	return find_first<Equal>(value, begin, end);	25,824✔
178	}	25,824✔
179
180	void ArrayIntNull::get_chunk(size_t ndx, value_type res[8]) const noexcept
181	{	×
182	// FIXME: Optimize this
183	int64_t tmp[8];	×
184	Array::get_chunk(ndx + 1, tmp);	×
185	int64_t null = null_value();	×
186	for (size_t i = 0; i < 8; ++i) {	×
187	res[i] = tmp[i] == null ? util::Optional<int64_t>() : tmp[i];	×
188	}	×
189	}	×
190
191	void ArrayIntNull::move(ArrayIntNull& dst, size_t ndx)
192	{	9,528✔
193	size_t sz = size();	9,528✔
194	for (size_t i = ndx; i < sz; i++) {	1,071,990✔
195	dst.add(get(i));	1,062,462✔
196	}	1,062,462✔
197	truncate(ndx + 1);	9,528✔
198	}	9,528✔

realm / realm-core / 1794

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