5653

pending completion

Build # 5653

Build Type

push

travis-ci

Committed by

rtsisyk

Commit Message

vinyl: vinyl/large.test.lua is too large

2Mb tuple is overkill for 1k page.

Fixes #1868

Run Details

21209 of 25630 relevant lines covered (82.75%)

881605.61 hits per line

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

97.26

/src/lib/bitset/iterator.c

/*
 * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *
 * 1. Redistributions of source code must retain the above
 *    copyright notice, this list of conditions and the
 *    following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above
 *    copyright notice, this list of conditions and the following
 *    disclaimer in the documentation and/or other materials
 *    provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
 * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include "bitset/iterator.h"
#include "bitset/expr.h"
#include "page.h"

#include <assert.h>

const size_t ITERATOR_DEFAULT_CAPACITY = 2;
const size_t ITERATOR_CONJ_DEFAULT_CAPACITY = 32;

struct bitset_iterator_conj {
        size_t page_first_pos;
        size_t size;
        size_t capacity;
        struct bitset **bitsets;
        bool *pre_nots;
        struct bitset_page **pages;
};

/**
 * @brief Construct iterator
 * @param it iterator
 * @param realloc memory allocator to use
 */
void
bitset_iterator_create(struct bitset_iterator *it,
                       void *(*realloc)(void *ptr, size_t size))
{
        memset(it, 0, sizeof(*it));
        it->realloc = realloc;
}

/**
 * @brief Destroys the @a it object
 * @param it object
 * @see bitset_iterator_new
 */
void
bitset_iterator_destroy(struct bitset_iterator *it)
{
        for (size_t c = 0; c < it->size; c++) {
                if (it->conjs[c].capacity == 0)
                        continue;

                it->realloc(it->conjs[c].bitsets, 0);
                it->realloc(it->conjs[c].pre_nots, 0);
                it->realloc(it->conjs[c].pages, 0);
        }

        if (it->capacity > 0) {
                it->realloc(it->conjs, 0);
        }

        if (it->page != NULL) {
                bitset_page_destroy(it->page);
                it->realloc(it->page, 0);
        }

        if (it->page != NULL) {
                bitset_page_destroy(it->page_tmp);
                it->realloc(it->page_tmp, 0);
        }

        memset(it, 0, sizeof(*it));
}


static int
bitset_iterator_reserve(struct bitset_iterator *it, size_t size)
{
        if (size <= it->capacity)
                return 0;

        size_t capacity = (it->capacity > 0)
                                ? it->capacity
                                : ITERATOR_DEFAULT_CAPACITY;

        while (capacity <= size) {
                capacity *= 2;
        }

        struct bitset_iterator_conj *conjs =
                        it->realloc(it->conjs, capacity * sizeof(*it->conjs));
        if (conjs == NULL)
                return -1;

        memset(conjs + it->capacity, 0,
               (capacity - it->capacity) * sizeof(*it->conjs));

        it->conjs = conjs;
        it->capacity = capacity;

        return 0;
}

static int
bitset_iterator_conj_reserve(struct bitset_iterator *it,
                             struct bitset_iterator_conj *conj, size_t size)
{
        if (size <= conj->capacity)
                return 0;

        size_t capacity = (conj->capacity > 0)
                                ? conj->capacity
                                : ITERATOR_CONJ_DEFAULT_CAPACITY;

        while (capacity <= size) {
                capacity *= 2;
        }

        struct bitset **bitsets = it->realloc(conj->bitsets,
                                        capacity * sizeof(*conj->bitsets));
        if (bitsets == NULL)
                goto error_1;
        bool *pre_nots = it->realloc(conj->pre_nots,
                                        capacity * sizeof(*conj->pre_nots));
        if (pre_nots == NULL)
                goto error_2;
        struct bitset_page **pages = it->realloc(conj->pages,
                                        capacity * sizeof(*conj->pages));
        if (pre_nots == NULL)
                goto error_3;

        memset(bitsets + conj->capacity, 0,
               (capacity - conj->capacity) * sizeof(*conj->bitsets));
        memset(pre_nots + conj->capacity, 0,
               (capacity - conj->capacity) * sizeof(*conj->pre_nots));
        memset(pages + conj->capacity, 0,
               (capacity - conj->capacity) * sizeof(*conj->pages));

        conj->bitsets = bitsets;
        conj->pre_nots = pre_nots;
        conj->pages = pages;
        conj->capacity = capacity;

        return 0;

error_3:
        it->realloc(pre_nots, 0);
error_2:
        it->realloc(bitsets, 0);
error_1:
        return -1;
}

int
bitset_iterator_init(struct bitset_iterator *it, struct bitset_expr *expr,
                     struct bitset **p_bitsets, size_t bitsets_size)
{
        assert(it != NULL);
        assert(expr != NULL);
        if (bitsets_size > 0) {
                assert(p_bitsets != NULL);
        }

        size_t page_alloc_size = bitset_page_alloc_size(it->realloc);
        if (it->page != NULL) {
                bitset_page_destroy(it->page);
        } else {
                it->page = it->realloc(NULL, page_alloc_size);
        }

        bitset_page_create(it->page);

        if (it->page_tmp != NULL) {
                bitset_page_destroy(it->page_tmp);
        } else {
                it->page_tmp = it->realloc(NULL, page_alloc_size);
                if (it->page_tmp == NULL)
                        return -1;
        }

        bitset_page_create(it->page_tmp);

        if (bitset_iterator_reserve(it, expr->size) != 0)
                return -1;

        for (size_t c = 0; c < expr->size; c++) {
                struct bitset_expr_conj *exconj = &expr->conjs[c];
                struct bitset_iterator_conj *itconj = &it->conjs[c];

                if (bitset_iterator_conj_reserve(it, itconj, exconj->size) != 0)
                        return -1;

                for (size_t b = 0; b < exconj->size; b++) {
                        assert(exconj->bitset_ids[b] < bitsets_size);
                        itconj->page_first_pos = 0;
                        assert(p_bitsets[exconj->bitset_ids[b]] != NULL);
                        itconj->bitsets[b] = p_bitsets[exconj->bitset_ids[b]];
                        itconj->pre_nots[b] = exconj->pre_nots[b];
                        itconj->pages[b] = NULL;
                }

                itconj->size = exconj->size;
        }

        it->size = expr->size;

        bitset_iterator_rewind(it);

        return 0;
}

static void
bitset_iterator_conj_rewind(struct bitset_iterator_conj *conj, size_t pos)
{
        assert(conj != NULL);
        assert(pos % (BITSET_PAGE_DATA_SIZE * CHAR_BIT) == 0);
        assert(conj->page_first_pos <= pos);

        if (conj->size == 0) {
                conj->page_first_pos = SIZE_MAX;
                return;
        }

        struct bitset_page key;
        key.first_pos = pos;

        restart:
        for (size_t b = 0; b < conj->size; b++) {
                conj->pages[b] = bitset_pages_nsearch(&conj->bitsets[b]->pages,
                                                      &key);
#if 0
                if (conj->pages[b] != NULL) {
                        fprintf(stderr, "rewind [%zu] => %zu (%p)\n", b,
                                conj->pages[b]->first_pos, conj->pages[b]);
                } else {
                        fprintf(stderr, "rewind [%zu] => NULL\n", b);
                }
#endif
                if (conj->pre_nots[b])
                        continue;

                /* bitset b does not have more pages */
                if (conj->pages[b] == NULL) {
                        conj->page_first_pos = SIZE_MAX;
                        return;
                }

                assert(conj->pages[b]->first_pos >= key.first_pos);

                /* bitset b have a next page, but it is beyond pos scope */
                if (conj->pages[b]->first_pos > key.first_pos) {
                        key.first_pos = conj->pages[b]->first_pos;
                        goto restart;
                }
        }

        conj->page_first_pos = key.first_pos;
}

static int
bitset_iterator_conj_cmp(const void *p1, const void *p2)
{
        assert(p1 != NULL && p2 != NULL);

        struct bitset_iterator_conj *conj1 = (struct bitset_iterator_conj *) p1;
        struct bitset_iterator_conj *conj2 = (struct bitset_iterator_conj *) p2;

        if (conj1->page_first_pos < conj2->page_first_pos) {
                return -1;
        } else if (conj1->page_first_pos > conj2->page_first_pos) {
                return 1;
        } else {
                return 0;
        }
}

static void
bitset_iterator_conj_prepare_page(struct bitset_iterator_conj *conj,
                                  struct bitset_page *dst)
{
        assert(conj != NULL);
        assert(dst != NULL);
        assert(conj->size > 0);
        assert(conj->page_first_pos != SIZE_MAX);

        bitset_page_set_ones(dst);
        for (size_t b = 0; b < conj->size; b++) {
                if (!conj->pre_nots[b]) {
                        /* conj->pages[b] is rewinded to conj->page_first_pos */
                        assert(conj->pages[b]->first_pos == conj->page_first_pos);
                        bitset_page_and(dst, conj->pages[b]);
                } else {
                        /*
                         * If page is NULL or its position is not equal
                         * to conj->page_first_pos then conj->bitset[b]
                         * does not have page with the required position and
                         * all bits in this page are considered to be zeros.
                         * Since NAND(a, zeros) => a, we can simple skip this
                         * bitset here.
                         */
                        if (conj->pages[b] == NULL ||
                            conj->pages[b]->first_pos != conj->page_first_pos)
                                continue;

                        bitset_page_nand(dst, conj->pages[b]);
                }
        }
}

static void
bitset_iterator_prepare_page(struct bitset_iterator *it)
{
        qsort(it->conjs, it->size, sizeof(*it->conjs),
              bitset_iterator_conj_cmp);

        bitset_page_set_zeros(it->page);
        if (it->size > 0) {
                it->page->first_pos = it->conjs[0].page_first_pos;
        } else {
                it->page->first_pos = SIZE_MAX;
        }

        /* There is no more conjunctions that can be ORed */
        if (it->page->first_pos == SIZE_MAX)
                return;

        /* For each conj where conj->page_first_pos == pos */
        for (size_t c = 0; c < it->size; c++) {
                if (it->conjs[c].page_first_pos > it->page->first_pos)
                        break;

                /* Get result from conj */
                bitset_iterator_conj_prepare_page(&it->conjs[c], it->page_tmp);
                /* OR page from conjunction with it->page */
                bitset_page_or(it->page, it->page_tmp);
        }

        /* Init the bit iterator on it->page */
        bit_iterator_init(&it->page_it, bitset_page_data(it->page),
                      BITSET_PAGE_DATA_SIZE, true);
}

static void
bitset_iterator_first_page(struct bitset_iterator *it)
{
        assert(it != NULL);

        /* Rewind all conjunctions to first positions */
        for (size_t c = 0; c < it->size; c++) {
                bitset_iterator_conj_rewind(&it->conjs[c], 0);
        }

        /* Prepare the result page */
        bitset_iterator_prepare_page(it);
}

static void
bitset_iterator_next_page(struct bitset_iterator *it)
{
        assert(it != NULL);

        size_t PAGE_BIT = BITSET_PAGE_DATA_SIZE * CHAR_BIT;
        size_t pos = it->page->first_pos;

        /* Rewind all conjunctions that at the current position to the
         * next position */
        for (size_t c = 0; c < it->size; c++) {
                if (it->conjs[c].page_first_pos > pos)
                        break;

                bitset_iterator_conj_rewind(&it->conjs[c], pos + PAGE_BIT);
                assert(pos + PAGE_BIT <= it->conjs[c].page_first_pos);
        }

        /* Prepare the result page */
        bitset_iterator_prepare_page(it);
}


void
bitset_iterator_rewind(struct bitset_iterator *it)
{
        assert(it != NULL);

        /* Prepare first page */
        bitset_iterator_first_page(it);
}

size_t
bitset_iterator_next(struct bitset_iterator *it)
{
        assert(it != NULL);

        while (true) {
                if (it->page->first_pos == SIZE_MAX)
                        return SIZE_MAX;

                size_t pos = bit_iterator_next(&it->page_it);
                if (pos != SIZE_MAX) {
                        return it->page->first_pos + pos;
                }

                bitset_iterator_next_page(it);
        }
}

1	/*
2	* Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
3	*
4	* Redistribution and use in source and binary forms, with or
5	* without modification, are permitted provided that the following
6	* conditions are met:
7	*
8	* 1. Redistributions of source code must retain the above
9	* copyright notice, this list of conditions and the
10	* following disclaimer.
11	*
12	* 2. Redistributions in binary form must reproduce the above
13	* copyright notice, this list of conditions and the following
14	* disclaimer in the documentation and/or other materials
15	* provided with the distribution.
16	*
17	* THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
18	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
19	* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
21	* <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
22	* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
25	* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
26	* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
28	* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29	* SUCH DAMAGE.
30	*/
31
32	#include "bitset/iterator.h"
33	#include "bitset/expr.h"
34	#include "page.h"
35
36	#include <assert.h>
37
38	const size_t ITERATOR_DEFAULT_CAPACITY = 2;
39	const size_t ITERATOR_CONJ_DEFAULT_CAPACITY = 32;
40
41	struct bitset_iterator_conj {
42	size_t page_first_pos;
43	size_t size;
44	size_t capacity;
45	struct bitset **bitsets;
46	bool *pre_nots;
47	struct bitset_page **pages;
48	};
49
50	/**
51	* @brief Construct iterator
52	* @param it iterator
53	* @param realloc memory allocator to use
54	*/
55	void
56	bitset_iterator_create(struct bitset_iterator *it,	56✔
57	void (realloc)(void *ptr, size_t size))
58	{
59	memset(it, 0, sizeof(*it));
60	it->realloc = realloc;	56✔
61	}	56✔
62
63	/**
64	* @brief Destroys the @a it object
65	* @param it object
66	* @see bitset_iterator_new
67	*/
68	void
69	bitset_iterator_destroy(struct bitset_iterator *it)	56✔
70	{
71	for (size_t c = 0; c < it->size; c++) {	155✔
72	if (it->conjs[c].capacity == 0)	99✔
73	continue;	7✔
74
75	it->realloc(it->conjs[c].bitsets, 0);	92✔
76	it->realloc(it->conjs[c].pre_nots, 0);	92✔
77	it->realloc(it->conjs[c].pages, 0);	92✔
78	}
79
80	if (it->capacity > 0) {	56✔
81	it->realloc(it->conjs, 0);	53✔
82	}
83
84	if (it->page != NULL) {	56✔
85	bitset_page_destroy(it->page);	55✔
86	it->realloc(it->page, 0);	55✔
87	}
88
89	if (it->page != NULL) {	56✔
90	bitset_page_destroy(it->page_tmp);	55✔
91	it->realloc(it->page_tmp, 0);	55✔
92	}
93
94	memset(it, 0, sizeof(*it));
95	}	56✔
96
97
98	static int
99	bitset_iterator_reserve(struct bitset_iterator *it, size_t size)	3,753✔
100	{
101	if (size <= it->capacity)	3,753✔
102	return 0;
103
104	size_t capacity = (it->capacity > 0)	53✔
105	? it->capacity
106	: ITERATOR_DEFAULT_CAPACITY;	53✔
107
108	while (capacity <= size) {	120✔
109	capacity *= 2;	14✔
110	}
111
112	struct bitset_iterator_conj *conjs =	53✔
113	it->realloc(it->conjs, capacity * sizeof(*it->conjs));	53✔
114	if (conjs == NULL)	53✔
115	return -1;
116
117	memset(conjs + it->capacity, 0,	53✔
118	(capacity - it->capacity) * sizeof(*it->conjs));	53✔
119
120	it->conjs = conjs;	53✔
121	it->capacity = capacity;	53✔
122
123	return 0;	53✔
124	}
125
126	static int
127	bitset_iterator_conj_reserve(struct bitset_iterator *it,	3,797✔
128	struct bitset_iterator_conj *conj, size_t size)
129	{
130	if (size <= conj->capacity)	3,797✔
131	return 0;
132
133	size_t capacity = (conj->capacity > 0)	93✔
134	? conj->capacity
135	: ITERATOR_CONJ_DEFAULT_CAPACITY;	93✔
136
137	while (capacity <= size) {	106✔
138	capacity *= 2;	13✔
139	}
140
141	struct bitset **bitsets = it->realloc(conj->bitsets,	93✔
142	capacity * sizeof(*conj->bitsets));
143	if (bitsets == NULL)	93✔
144	goto error_1;
145	bool *pre_nots = it->realloc(conj->pre_nots,	93✔
146	capacity * sizeof(*conj->pre_nots));
147	if (pre_nots == NULL)	93✔
148	goto error_2;
149	struct bitset_page **pages = it->realloc(conj->pages,	93✔
150	capacity * sizeof(*conj->pages));
151	if (pre_nots == NULL)	93✔
152	goto error_3;
153
154	memset(bitsets + conj->capacity, 0,	93✔
155	(capacity - conj->capacity) * sizeof(*conj->bitsets));	93✔
156	memset(pre_nots + conj->capacity, 0,	93✔
157	(capacity - conj->capacity) * sizeof(*conj->pre_nots));	93✔
158	memset(pages + conj->capacity, 0,	93✔
159	(capacity - conj->capacity) * sizeof(*conj->pages));	93✔
160
161	conj->bitsets = bitsets;	93✔
162	conj->pre_nots = pre_nots;	93✔
163	conj->pages = pages;	93✔
164	conj->capacity = capacity;	93✔
165
166	return 0;
167
168	error_3:
169	it->realloc(pre_nots, 0);	×
170	error_2:
171	it->realloc(bitsets, 0);	×
172	error_1:
173	return -1;
174	}
175
176	int
177	bitset_iterator_init(struct bitset_iterator it, struct bitset_expr expr,	3,753✔
178	struct bitset **p_bitsets, size_t bitsets_size)
179	{
180	assert(it != NULL);
181	assert(expr != NULL);
182	if (bitsets_size > 0) {
183	assert(p_bitsets != NULL);
184	}
185
186	size_t page_alloc_size = bitset_page_alloc_size(it->realloc);	3,753✔
187	if (it->page != NULL) {	3,753✔
188	bitset_page_destroy(it->page);
189	} else {
190	it->page = it->realloc(NULL, page_alloc_size);	55✔
191	}
192
193	bitset_page_create(it->page);	3,753✔
194
195	if (it->page_tmp != NULL) {	3,753✔
196	bitset_page_destroy(it->page_tmp);
197	} else {
198	it->page_tmp = it->realloc(NULL, page_alloc_size);	55✔
199	if (it->page_tmp == NULL)	55✔
200	return -1;
201	}
202
203	bitset_page_create(it->page_tmp);	3,753✔
204
205	if (bitset_iterator_reserve(it, expr->size) != 0)	3,753✔
206	return -1;
207
208	for (size_t c = 0; c < expr->size; c++) {	3,797✔
209	struct bitset_expr_conj *exconj = &expr->conjs[c];	3,797✔
210	struct bitset_iterator_conj *itconj = &it->conjs[c];	3,797✔
211
212	if (bitset_iterator_conj_reserve(it, itconj, exconj->size) != 0)	3,797✔
213	return -1;
214
215	for (size_t b = 0; b < exconj->size; b++) {	240,612✔
216	assert(exconj->bitset_ids[b] < bitsets_size);
217	itconj->page_first_pos = 0;	240,612✔
218	assert(p_bitsets[exconj->bitset_ids[b]] != NULL);
219	itconj->bitsets[b] = p_bitsets[exconj->bitset_ids[b]];	240,612✔
220	itconj->pre_nots[b] = exconj->pre_nots[b];	240,612✔
221	itconj->pages[b] = NULL;	240,612✔
222	}
223
224	itconj->size = exconj->size;	3,797✔
225	}
226
227	it->size = expr->size;	3,753✔
228
229	bitset_iterator_rewind(it);
230
231	return 0;	3,753✔
232	}
233
234	static void
235	bitset_iterator_conj_rewind(struct bitset_iterator_conj *conj, size_t pos)	11,581✔
236	{
237	assert(conj != NULL);
238	assert(pos % (BITSET_PAGE_DATA_SIZE * CHAR_BIT) == 0);
239	assert(conj->page_first_pos <= pos);
240
241	if (conj->size == 0) {	11,581✔
242	conj->page_first_pos = SIZE_MAX;	7✔
243	return;	105✔
244	}
245
246	struct bitset_page key;
247	key.first_pos = pos;	11,574✔
248
249	restart:
250	for (size_t b = 0; b < conj->size; b++) {	7,135,983✔
251	conj->pages[b] = bitset_pages_nsearch(&conj->bitsets[b]->pages,	8,856,104✔
252	&key);
253	#if 0
254	if (conj->pages[b] != NULL) {
255	fprintf(stderr, "rewind [%zu] => %zu (%p)\n", b,
256	conj->pages[b]->first_pos, conj->pages[b]);
257	} else {
258	fprintf(stderr, "rewind [%zu] => NULL\n", b);
259	}
260	#endif
261	if (conj->pre_nots[b])	8,856,104✔
262	continue;	4,472,580✔
263
264	/* bitset b does not have more pages */
265	if (conj->pages[b] == NULL) {	4,383,524✔
266	conj->page_first_pos = SIZE_MAX;	91✔
267	return;	91✔
268	}
269
270	assert(conj->pages[b]->first_pos >= key.first_pos);
271
272	/* bitset b have a next page, but it is beyond pos scope */
273	if (conj->pages[b]->first_pos > key.first_pos) {	4,383,433✔
274	key.first_pos = conj->pages[b]->first_pos;	1,720,030✔
275	goto restart;	1,720,030✔
276	}
277	}
278
279	conj->page_first_pos = key.first_pos;	11,483✔
280	}
281
282	static int
283	bitset_iterator_conj_cmp(const void p1, const void p2)	16,730✔
284	{
285	assert(p1 != NULL && p2 != NULL);
286
287	struct bitset_iterator_conj conj1 = (struct bitset_iterator_conj ) p1;	16,730✔
288	struct bitset_iterator_conj conj2 = (struct bitset_iterator_conj ) p2;	16,730✔
289
290	if (conj1->page_first_pos < conj2->page_first_pos) {	16,730✔
291	return -1;
292	} else if (conj1->page_first_pos > conj2->page_first_pos) {	16,719✔
293	return 1;
294	} else {
295	return 0;	16,678✔
296	}
297	}
298
299	static void
300	bitset_iterator_conj_prepare_page(struct bitset_iterator_conj *conj,	11,483✔
301	struct bitset_page *dst)
302	{
303	assert(conj != NULL);
304	assert(dst != NULL);
305	assert(conj->size > 0);
306	assert(conj->page_first_pos != SIZE_MAX);
307
308	bitset_page_set_ones(dst);
309	for (size_t b = 0; b < conj->size; b++) {	304,131✔
310	if (!conj->pre_nots[b]) {	292,648✔
311	/* conj->pages[b] is rewinded to conj->page_first_pos */
312	assert(conj->pages[b]->first_pos == conj->page_first_pos);
313	bitset_page_and(dst, conj->pages[b]);	86,437✔
314	} else {
315	/*
316	* If page is NULL or its position is not equal
317	* to conj->page_first_pos then conj->bitset[b]
318	* does not have page with the required position and
319	* all bits in this page are considered to be zeros.
320	* Since NAND(a, zeros) => a, we can simple skip this
321	* bitset here.
322	*/
323	if (conj->pages[b] == NULL \|\|	273,740✔
324	conj->pages[b]->first_pos != conj->page_first_pos)	67,529✔
325	continue;	201,026✔
326
327	bitset_page_nand(dst, conj->pages[b]);	5,185✔
328	}
329	}
330	}	11,483✔
331
332	static void
333	bitset_iterator_prepare_page(struct bitset_iterator *it)	5,076✔
334	{
335	qsort(it->conjs, it->size, sizeof(*it->conjs),	5,076✔
336	bitset_iterator_conj_cmp);
337
338	bitset_page_set_zeros(it->page);	5,076✔
339	if (it->size > 0) {	5,076✔
340	it->page->first_pos = it->conjs[0].page_first_pos;	5,074✔
341	} else {
342	it->page->first_pos = SIZE_MAX;	2✔
343	}
344
345	/* There is no more conjunctions that can be ORed */
346	if (it->page->first_pos == SIZE_MAX)	5,076✔
347	return;	5,076✔
348
349	/* For each conj where conj->page_first_pos == pos */
350	for (size_t c = 0; c < it->size; c++) {	11,483✔
351	if (it->conjs[c].page_first_pos > it->page->first_pos)	11,487✔
352	break;
353
354	/* Get result from conj */
355	bitset_iterator_conj_prepare_page(&it->conjs[c], it->page_tmp);	11,483✔
356	/* OR page from conjunction with it->page */
357	bitset_page_or(it->page, it->page_tmp);	11,483✔
358	}
359
360	/* Init the bit iterator on it->page */
361	bit_iterator_init(&it->page_it, bitset_page_data(it->page),	10,038✔
362	BITSET_PAGE_DATA_SIZE, true);
363	}
364
365	static void
366	bitset_iterator_first_page(struct bitset_iterator *it)	3,753✔
367	{
368	assert(it != NULL);
369
370	/* Rewind all conjunctions to first positions */
371	for (size_t c = 0; c < it->size; c++) {	7,550✔
372	bitset_iterator_conj_rewind(&it->conjs[c], 0);	3,797✔
373	}
374
375	/* Prepare the result page */
376	bitset_iterator_prepare_page(it);	3,753✔
377	}	3,753✔
378
379	static void
380	bitset_iterator_next_page(struct bitset_iterator *it)	1,323✔
381	{
382	assert(it != NULL);
383
384	size_t PAGE_BIT = BITSET_PAGE_DATA_SIZE * CHAR_BIT;	1,323✔
385	size_t pos = it->page->first_pos;	1,323✔
386
387	/* Rewind all conjunctions that at the current position to the
388	* next position */
389	for (size_t c = 0; c < it->size; c++) {	9,107✔
390	if (it->conjs[c].page_first_pos > pos)	7,788✔
391	break;
392
393	bitset_iterator_conj_rewind(&it->conjs[c], pos + PAGE_BIT);	7,784✔
394	assert(pos + PAGE_BIT <= it->conjs[c].page_first_pos);
395	}
396
397	/* Prepare the result page */
398	bitset_iterator_prepare_page(it);	1,323✔
399	}	1,323✔
400
401
402	void
403	bitset_iterator_rewind(struct bitset_iterator *it)	×
404	{
405	assert(it != NULL);
406
407	/* Prepare first page */
408	bitset_iterator_first_page(it);	3,753✔
409	}	×
410
411	size_t
412	bitset_iterator_next(struct bitset_iterator *it)	458,744✔
413	{
414	assert(it != NULL);
415
416	while (true) {
417	if (it->page->first_pos == SIZE_MAX)	460,067✔
418	return SIZE_MAX;
419
420	size_t pos = bit_iterator_next(&it->page_it);	328,938✔
421	if (pos != SIZE_MAX) {	328,938✔
422	return it->page->first_pos + pos;	327,615✔
423	}
424
425	bitset_iterator_next_page(it);	1,323✔
426	}	1,323✔
427	}

tarantool / tarantool / 5653

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