jorgen.edelbo_402

Committed 21 Aug 2024 11:10AM CUT coverage: 91.054% (-0.03%) from 91.085%

Build # jorgen.edelbo_402

Build Type

Pull #7803

Evergreen

Committed by

jedelbo

Commit Message

Small fix to Table::typed_write

When writing the realm to a new file from a write transaction,
the Table may be COW so that the top ref is changed. So don't
use the ref that is present in the group when the operation starts.

Pull Request Pull Request #7803: Feature/string compression

Run Details

103494 of 181580 branches covered (57.0%)

1929 of 1999 new or added lines in 46 files covered. (96.5%)

695 existing lines in 51 files now uncovered.

220142 of 241772 relevant lines covered (91.05%)

7344461.76 hits per line

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

86.27

/src/realm/array_string_short.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 <cstdlib>
#include <algorithm>
#include <cstring>

#ifdef REALM_DEBUG
#include <cstdio>
#include <iostream>
#include <iomanip>
#endif

#include <realm/utilities.hpp>
#include <realm/array_string_short.hpp>
#include <realm/impl/destroy_guard.hpp>
#include <realm/column_integer.hpp>

using namespace realm;


namespace {

// Round up to nearest possible block length: 0, 1, 2, 4, 8, 16, 32, 64, 128, 256. We include 1 to store empty
// strings in as little space as possible, because 0 can only store nulls.
size_t round_up(size_t size)
{
    REALM_ASSERT(size <= 256);

    if (size <= 2)
        return size;

    size--;
    size |= size >> 1;
    size |= size >> 2;
    size |= size >> 4;
    ++size;
    return size;
}

} // anonymous namespace

bool ArrayStringShort::is_null(size_t ndx) const
{
    REALM_ASSERT_3(ndx, <, m_size);
    StringData sd = get(ndx);
    return sd.is_null();
}

void ArrayStringShort::set_null(size_t ndx)
{
    REALM_ASSERT_3(ndx, <, m_size);
    StringData sd = realm::null();
    set(ndx, sd);
}

void ArrayStringShort::set(size_t ndx, StringData value)
{
    REALM_ASSERT_3(ndx, <, m_size);
    REALM_ASSERT_3(value.size(), <, max_width); // otherwise we have to use another column type

    // if m_width == 0 and m_nullable == true, then entire array contains only null entries
    // if m_width == 0 and m_nullable == false, then entire array contains only "" entries
    if ((m_nullable ? value.is_null() : value.size() == 0) && m_width == 0) {
        return; // existing element in array already equals the value we want to set it to
    }

    // Make room for the new value plus a zero-termination
    if (m_width <= value.size()) {
        // Calc min column width
        size_t new_width = ::round_up(value.size() + 1);
        const size_t old_width = m_width;
        alloc(m_size, new_width); // Throws

        char* base = m_data;
        char* new_end = base + m_size * new_width;

        // Expand the old values in reverse order
        if (old_width > 0) {
            const char* old_end = base + m_size * old_width;
            while (new_end != base) {
                *--new_end = char(*--old_end + (new_width - old_width));
                {
                    // extend 0-padding
                    char* new_begin = new_end - (new_width - old_width);
                    std::fill(new_begin, new_end, 0);
                    new_end = new_begin;
                }
                {
                    // copy string payload
                    const char* old_begin = old_end - (old_width - 1);
                    if (static_cast<size_t>(old_end - old_begin) < old_width) // non-null string
                        new_end = std::copy_backward(old_begin, old_end, new_end);
                    old_end = old_begin;
                }
            }
        }
        else {
            // old_width == 0. Expand to new width.
            while (new_end != base) {
                REALM_ASSERT_3(new_width, <=, max_width);
                *--new_end = static_cast<char>(new_width);
                {
                    char* new_begin = new_end - (new_width - 1);
                    std::fill(new_begin, new_end, 0); // Fill with zero bytes
                    new_end = new_begin;
                }
            }
        }
    }
    else if (is_read_only()) {
        if (get(ndx) == value)
            return;
        copy_on_write();
    }

    REALM_ASSERT_3(0, <, m_width);

    // Set the value
    char* begin = m_data + (ndx * m_width);
    char* end = begin + (m_width - 1);
    begin = realm::safe_copy_n(value.data(), value.size(), begin);
    std::fill(begin, end, 0); // Pad with zero bytes
    static_assert(max_width <= max_width, "Padding size must fit in 7-bits");

    if (value.is_null()) {
        REALM_ASSERT_3(m_width, <=, 128);
        *end = static_cast<char>(m_width);
    }
    else {
        int pad_size = int(end - begin);
        *end = char(pad_size);
    }
}


void ArrayStringShort::insert(size_t ndx, StringData value)
{
    REALM_ASSERT_3(ndx, <=, m_size);
    REALM_ASSERT(value.size() < max_width); // otherwise we have to use another column type

    // FIXME: this performs up to 2 memcpy() operations. This could be improved
    // by making the allocator make a gap for the new value for us, but it's a
    // bit complex.

    // Allocate room for the new value
    const auto old_size = m_size;
    alloc(m_size + 1, m_width); // Throws

    // Make gap for new value
    memmove(m_data + m_width * (ndx + 1), m_data + m_width * ndx, m_width * (old_size - ndx));

    // Set new value
    set(ndx, value);
    return;
}

void ArrayStringShort::erase(size_t ndx)
{
    REALM_ASSERT_3(ndx, <, m_size);

    // Check if we need to copy before modifying
    copy_on_write(); // Throws

    // move data backwards after deletion
    if (ndx < m_size - 1) {
        char* new_begin = m_data + ndx * m_width;
        char* old_begin = new_begin + m_width;
        char* old_end = m_data + m_size * m_width;
        realm::safe_copy_n(old_begin, old_end - old_begin, new_begin);
    }

    --m_size;

    // Update size in header
    set_header_size(m_size);
}

size_t ArrayStringShort::calc_byte_len(size_t num_items, size_t width) const
{
    return header_size + (num_items * width);
}

size_t ArrayStringShort::calc_item_count(size_t bytes, size_t width) const noexcept
{
    if (width == 0)
        return size_t(-1); // zero-width gives infinite space

    size_t bytes_without_header = bytes - header_size;
    return bytes_without_header / width;
}

size_t ArrayStringShort::count(StringData value, size_t begin, size_t end) const noexcept
{
    size_t num_matches = 0;

    size_t begin_2 = begin;
    for (;;) {
        size_t ndx = find_first(value, begin_2, end);
        if (ndx == not_found)
            break;
        ++num_matches;
        begin_2 = ndx + 1;
    }

    return num_matches;
}

size_t ArrayStringShort::find_first(StringData value, size_t begin, size_t end) const noexcept
{
    if (end == size_t(-1))
        end = m_size;
    REALM_ASSERT(begin <= m_size && end <= m_size && begin <= end);

    if (m_width == 0) {
        if (m_nullable)
            // m_width == 0 implies that all elements in the array are NULL
            return value.is_null() && begin < m_size ? begin : npos;
        else
            return value.size() == 0 && begin < m_size ? begin : npos;
    }

    const size_t value_size = value.size();
    // A string can never be wider than the column width
    if (m_width <= value_size)
        return size_t(-1);

    if (m_nullable ? value.is_null() : value_size == 0) {
        for (size_t i = begin; i != end; ++i) {
            if (m_nullable ? is_null(i) : get(i).size() == 0)
                return i;
        }
    }
    else if (value_size == 0) {
        const char* data = m_data + (m_width - 1);
        for (size_t i = begin; i != end; ++i) {
            size_t data_i_size = (m_width - 1) - data[i * m_width];
            // left-hand-side tests if array element is NULL
            if (REALM_UNLIKELY(data_i_size == 0))
                return i;
        }
    }
    else {
        for (size_t i = begin; i != end; ++i) {
            const char* data = m_data + (i * m_width);
            if (memcmp(data, value.data(), value_size) == 0) {
                size_t data_size = (m_width - 1) - data[m_width - 1];
                if (data_size == value_size) {
                    return i;
                }
            }
        }
    }

    return not_found;
}

void ArrayStringShort::find_all(IntegerColumn& result, StringData value, size_t add_offset, size_t begin, size_t end)
{
    size_t begin_2 = begin;
    for (;;) {
        size_t ndx = find_first(value, begin_2, end);
        if (ndx == not_found)
            break;
        result.add(add_offset + ndx); // Throws
        begin_2 = ndx + 1;
    }
}

bool ArrayStringShort::compare_string(const ArrayStringShort& c) const noexcept
{
    if (c.size() != size())
        return false;

    for (size_t i = 0; i < size(); ++i) {
        if (get(i) != c.get(i))
            return false;
    }

    return true;
}

#ifdef REALM_DEBUG // LCOV_EXCL_START ignore debug functions

void ArrayStringShort::string_stats() const
{
    size_t total = 0;
    size_t longest = 0;

    for (size_t i = 0; i < m_size; ++i) {
        StringData str = get(i);
        size_t str_size = str.size() + 1;
        total += str_size;
        if (str_size > longest)
            longest = str_size;
    }

    size_t array_size = m_size * m_width;
    size_t zeroes = array_size - total;
    size_t zavg = zeroes / (m_size ? m_size : 1); // avoid possible div by zero

    std::cout << "Size: " << m_size << "\n";
    std::cout << "Width: " << m_width << "\n";
    std::cout << "Total: " << array_size << "\n";
    // std::cout << "Capacity: " << m_capacity << "\n\n";
    std::cout << "Bytes string: " << total << "\n";
    std::cout << "     longest: " << longest << "\n";
    std::cout << "Bytes zeroes: " << zeroes << "\n";
    std::cout << "         avg: " << zavg << "\n";
}

#endif // LCOV_EXCL_STOP ignore debug functions

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 <cstdlib>
20	#include <algorithm>
21	#include <cstring>
22
23	#ifdef REALM_DEBUG
24	#include <cstdio>
25	#include <iostream>
26	#include <iomanip>
27	#endif
28
29	#include <realm/utilities.hpp>
30	#include <realm/array_string_short.hpp>
31	#include <realm/impl/destroy_guard.hpp>
32	#include <realm/column_integer.hpp>
33
34	using namespace realm;
35
36
37	namespace {
38
39	// Round up to nearest possible block length: 0, 1, 2, 4, 8, 16, 32, 64, 128, 256. We include 1 to store empty
40	// strings in as little space as possible, because 0 can only store nulls.
41	size_t round_up(size_t size)
42	{	903,801✔
43	REALM_ASSERT(size <= 256);	903,801✔
44
45	if (size <= 2)	903,801✔
46	return size;	19,239✔
47
48	size--;	884,562✔
49	size \|= size >> 1;	884,562✔
50	size \|= size >> 2;	884,562✔
51	size \|= size >> 4;	884,562✔
52	++size;	884,562✔
53	return size;	884,562✔
54	}	903,801✔
55
56	} // anonymous namespace
57
58	bool ArrayStringShort::is_null(size_t ndx) const
59	{	610,230✔
60	REALM_ASSERT_3(ndx, <, m_size);	610,230✔
61	StringData sd = get(ndx);	610,230✔
62	return sd.is_null();	610,230✔
63	}	610,230✔
64
65	void ArrayStringShort::set_null(size_t ndx)
66	{	18✔
67	REALM_ASSERT_3(ndx, <, m_size);	18✔
68	StringData sd = realm::null();	18✔
69	set(ndx, sd);	18✔
70	}	18✔
71
72	void ArrayStringShort::set(size_t ndx, StringData value)
73	{	3,566,661✔
74	REALM_ASSERT_3(ndx, <, m_size);	3,566,661✔
75	REALM_ASSERT_3(value.size(), <, max_width); // otherwise we have to use another column type	3,566,661✔
76
77	// if m_width == 0 and m_nullable == true, then entire array contains only null entries
78	// if m_width == 0 and m_nullable == false, then entire array contains only "" entries
79	if ((m_nullable ? value.is_null() : value.size() == 0) && m_width == 0) {	3,566,661✔
80	return; // existing element in array already equals the value we want to set it to	52,155✔
81	}	52,155✔
82
83	// Make room for the new value plus a zero-termination
84	if (m_width <= value.size()) {	3,514,506✔
85	// Calc min column width
86	size_t new_width = ::round_up(value.size() + 1);	903,807✔
87	const size_t old_width = m_width;	903,807✔
88	alloc(m_size, new_width); // Throws	903,807✔
89
90	char* base = m_data;	903,807✔
91	char* new_end = base + m_size * new_width;	903,807✔
92
93	// Expand the old values in reverse order
94	if (old_width > 0) {	903,807✔
95	const char* old_end = base + m_size * old_width;	172,728✔
96	while (new_end != base) {	697,446✔
97	--new_end = char(--old_end + (new_width - old_width));	524,718✔
98	{	524,718✔
99	// extend 0-padding
100	char* new_begin = new_end - (new_width - old_width);	524,718✔
101	std::fill(new_begin, new_end, 0);	524,718✔
102	new_end = new_begin;	524,718✔
103	}	524,718✔
104	{	524,718✔
105	// copy string payload
106	const char* old_begin = old_end - (old_width - 1);	524,718✔
107	if (static_cast<size_t>(old_end - old_begin) < old_width) // non-null string	524,718✔
108	new_end = std::copy_backward(old_begin, old_end, new_end);	524,718✔
109	old_end = old_begin;	524,718✔
110	}	524,718✔
111	}	524,718✔
112	}	172,728✔
113	else {	731,079✔
114	// old_width == 0. Expand to new width.
115	while (new_end != base) {	1,492,632✔
116	REALM_ASSERT_3(new_width, <=, max_width);	761,553✔
117	*--new_end = static_cast<char>(new_width);	761,553✔
118	{	761,553✔
119	char* new_begin = new_end - (new_width - 1);	761,553✔
120	std::fill(new_begin, new_end, 0); // Fill with zero bytes	761,553✔
121	new_end = new_begin;	761,553✔
122	}	761,553✔
123	}	761,553✔
124	}	731,079✔
125	}	903,807✔
126	else if (is_read_only()) {	2,610,699✔
127	if (get(ndx) == value)	1,305✔
UNCOV 128	return;	×
129	copy_on_write();	1,305✔
130	}	1,305✔
131
132	REALM_ASSERT_3(0, <, m_width);	3,514,506✔
133
134	// Set the value
135	char* begin = m_data + (ndx * m_width);	3,514,506✔
136	char* end = begin + (m_width - 1);	3,514,506✔
137	begin = realm::safe_copy_n(value.data(), value.size(), begin);	3,514,506✔
138	std::fill(begin, end, 0); // Pad with zero bytes	3,514,506✔
139	static_assert(max_width <= max_width, "Padding size must fit in 7-bits");	3,514,506✔
140
141	if (value.is_null()) {	3,514,506✔
142	REALM_ASSERT_3(m_width, <=, 128);	47,763✔
143	*end = static_cast<char>(m_width);	47,763✔
144	}	47,763✔
145	else {	3,466,743✔
146	int pad_size = int(end - begin);	3,466,743✔
147	*end = char(pad_size);	3,466,743✔
148	}	3,466,743✔
149	}	3,514,506✔
150
151
152	void ArrayStringShort::insert(size_t ndx, StringData value)
153	{	3,114,639✔
154	REALM_ASSERT_3(ndx, <=, m_size);	3,114,639✔
155	REALM_ASSERT(value.size() < max_width); // otherwise we have to use another column type	3,114,639✔
156
157	// FIXME: this performs up to 2 memcpy() operations. This could be improved
158	// by making the allocator make a gap for the new value for us, but it's a
159	// bit complex.
160
161	// Allocate room for the new value
162	const auto old_size = m_size;	3,114,639✔
163	alloc(m_size + 1, m_width); // Throws	3,114,639✔
164
165	// Make gap for new value
166	memmove(m_data + m_width * (ndx + 1), m_data + m_width * ndx, m_width * (old_size - ndx));	3,114,639✔
167
168	// Set new value
169	set(ndx, value);	3,114,639✔
170	return;	3,114,639✔
171	}	3,114,639✔
172
173	void ArrayStringShort::erase(size_t ndx)
174	{	368,796✔
175	REALM_ASSERT_3(ndx, <, m_size);	368,796✔
176
177	// Check if we need to copy before modifying
178	copy_on_write(); // Throws	368,796✔
179
180	// move data backwards after deletion
181	if (ndx < m_size - 1) {	368,796✔
182	char* new_begin = m_data + ndx * m_width;	296,928✔
183	char* old_begin = new_begin + m_width;	296,928✔
184	char* old_end = m_data + m_size * m_width;	296,928✔
185	realm::safe_copy_n(old_begin, old_end - old_begin, new_begin);	296,928✔
186	}	296,928✔
187
188	--m_size;	368,796✔
189
190	// Update size in header
191	set_header_size(m_size);	368,796✔
192	}	368,796✔
193
194	size_t ArrayStringShort::calc_byte_len(size_t num_items, size_t width) const
195	{	4,012,806✔
196	return header_size + (num_items * width);	4,012,806✔
197	}	4,012,806✔
198
199	size_t ArrayStringShort::calc_item_count(size_t bytes, size_t width) const noexcept
200	{	×
201	if (width == 0)	×
202	return size_t(-1); // zero-width gives infinite space	×
203
204	size_t bytes_without_header = bytes - header_size;	×
205	return bytes_without_header / width;	×
206	}	×
207
208	size_t ArrayStringShort::count(StringData value, size_t begin, size_t end) const noexcept
209	{	6✔
210	size_t num_matches = 0;	6✔
211
212	size_t begin_2 = begin;	6✔
213	for (;;) {	24✔
214	size_t ndx = find_first(value, begin_2, end);	24✔
215	if (ndx == not_found)	24✔
216	break;	6✔
217	++num_matches;	18✔
218	begin_2 = ndx + 1;	18✔
219	}	18✔
220
221	return num_matches;	6✔
222	}	6✔
223
224	size_t ArrayStringShort::find_first(StringData value, size_t begin, size_t end) const noexcept
225	{	21,024,045✔
226	if (end == size_t(-1))	21,024,045✔
227	end = m_size;	20,924,466✔
228	REALM_ASSERT(begin <= m_size && end <= m_size && begin <= end);	21,024,045✔
229
230	if (m_width == 0) {	21,024,045✔
231	if (m_nullable)	3,905,445✔
232	// m_width == 0 implies that all elements in the array are NULL
233	return value.is_null() && begin < m_size ? begin : npos;	12!
234	else	3,905,433✔
235	return value.size() == 0 && begin < m_size ? begin : npos;	3,905,433✔
236	}	3,905,445✔
237
238	const size_t value_size = value.size();	17,118,600✔
239	// A string can never be wider than the column width
240	if (m_width <= value_size)	17,118,600✔
241	return size_t(-1);	276,630✔
242
243	if (m_nullable ? value.is_null() : value_size == 0) {	16,841,970✔
244	for (size_t i = begin; i != end; ++i) {	199,887✔
245	if (m_nullable ? is_null(i) : get(i).size() == 0)	145,131✔
246	return i;	1,398✔
247	}	145,131✔
248	}	56,154✔
249	else if (value_size == 0) {	16,785,816✔
250	const char* data = m_data + (m_width - 1);	168✔
251	for (size_t i = begin; i != end; ++i) {	462✔
252	size_t data_i_size = (m_width - 1) - data[i * m_width];	426✔
253	// left-hand-side tests if array element is NULL
254	if (REALM_UNLIKELY(data_i_size == 0))	426✔
255	return i;	132✔
256	}	426✔
257	}	168✔
258	else {	16,785,648✔
259	for (size_t i = begin; i != end; ++i) {	214,292,409✔
260	const char* data = m_data + (i * m_width);	213,483,672✔
261	if (memcmp(data, value.data(), value_size) == 0) {	213,483,672✔
262	size_t data_size = (m_width - 1) - data[m_width - 1];	15,680,871✔
263	if (data_size == value_size) {	16,032,849✔
264	return i;	15,976,911✔
265	}	15,976,911✔
266	}	15,680,871✔
267	}	213,483,672✔
268	}	16,785,648✔
269
270	return not_found;	863,529✔
271	}	16,841,970✔
272
273	void ArrayStringShort::find_all(IntegerColumn& result, StringData value, size_t add_offset, size_t begin, size_t end)
274	{	6✔
275	size_t begin_2 = begin;	6✔
276	for (;;) {	24✔
277	size_t ndx = find_first(value, begin_2, end);	24✔
278	if (ndx == not_found)	24✔
279	break;	6✔
280	result.add(add_offset + ndx); // Throws	18✔
281	begin_2 = ndx + 1;	18✔
282	}	18✔
283	}	6✔
284
285	bool ArrayStringShort::compare_string(const ArrayStringShort& c) const noexcept
286	{	24✔
287	if (c.size() != size())	24✔
288	return false;	6✔
289
290	for (size_t i = 0; i < size(); ++i) {	24✔
291	if (get(i) != c.get(i))	12✔
292	return false;	6✔
293	}	12✔
294
295	return true;	12✔
296	}	18✔
297
298	#ifdef REALM_DEBUG // LCOV_EXCL_START ignore debug functions
299
300	void ArrayStringShort::string_stats() const
301	{	×
302	size_t total = 0;	×
303	size_t longest = 0;	×
304
305	for (size_t i = 0; i < m_size; ++i) {	×
306	StringData str = get(i);	×
307	size_t str_size = str.size() + 1;	×
308	total += str_size;	×
309	if (str_size > longest)	×
310	longest = str_size;	×
311	}	×
312
313	size_t array_size = m_size * m_width;	×
314	size_t zeroes = array_size - total;	×
315	size_t zavg = zeroes / (m_size ? m_size : 1); // avoid possible div by zero	×
316
317	std::cout << "Size: " << m_size << "\n";	×
318	std::cout << "Width: " << m_width << "\n";	×
319	std::cout << "Total: " << array_size << "\n";	×
320	// std::cout << "Capacity: " << m_capacity << "\n\n";
321	std::cout << "Bytes string: " << total << "\n";	×
322	std::cout << " longest: " << longest << "\n";	×
323	std::cout << "Bytes zeroes: " << zeroes << "\n";	×
324	std::cout << " avg: " << zavg << "\n";	×
325	}	×
326
327	#endif // LCOV_EXCL_STOP ignore debug functions

realm / realm-core / jorgen.edelbo_402

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