rtree.c

filter: Statementstmt 79.8% 516 / 646 Branchbran 46.2% 260 / 562 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 64.2% 776 / 1208 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« matras.c ↑ Summary R.xs »
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 #include "rtree.h"
32 #include <string.h>
33 #include <assert.h>
34 #include <limits.h>
35 #include <stddef.h>
36 #include <sys/types.h>
37  
38 /*------------------------------------------------------------------------- */
39 /* R-tree internal structures definition */
40 /*------------------------------------------------------------------------- */
41 enum {
42 /* rtree will try to determine optimal page size */
43 RTREE_OPTIMAL_BRANCHES_IN_PAGE = 18,
44 /* actual number of branches could be up to double of the previous
45 * constant */
46 RTREE_MAXIMUM_BRANCHES_IN_PAGE = RTREE_OPTIMAL_BRANCHES_IN_PAGE * 2
47 };
48  
49 struct rtree_page_branch {
50 union {
51 struct rtree_page *page;
52 record_t record;
53 } data;
54 struct rtree_rect rect;
55 };
56  
57 enum {
58 RTREE_BRANCH_DATA_SIZE = offsetof(struct rtree_page_branch, rect)
59 };
60  
61 struct rtree_page {
62 /* number of branches at page */
63 unsigned n;
64 /* branches */
65 struct rtree_page_branch data[];
66 };
67  
68 struct rtree_neighbor_page {
69 struct rtree_neighbor_page* next;
70 struct rtree_neighbor buf[];
71 };
72  
73 struct rtree_reinsert_list {
74 struct rtree_page *chain;
75 int level;
76 };
77  
78 static int
79 2277 neighbor_cmp(struct rtree_neighbor *a, struct rtree_neighbor *b)
80 {
81 3004 ▶ return a->distance < b->distance ? -1 :
Branch: 1 branch
BranchTrueFalseTotal
return a->distance < b->distance ? -1 : 1550 727 2277
82 940 ▶ a->distance > b->distance ? 1 :
Branch: 1 branch
BranchTrueFalseTotal
a->distance > b->distance ? 1 : 514 213 727
83 426 ▶ a->level < b->level ? -1 :
Branch: 1 branch
BranchTrueFalseTotal
a->level < b->level ? -1 : 213 0 213
84 426 ▶ a->level > b->level ? 1 :
Branch: 1 branch
BranchTrueFalseTotal
a->level > b->level ? 1 : 213 0 213
85 213 ▶ a < b ? -1 : a > b ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
a < b ? -1 : a > b ? 1 : 0; 213 0 213
86 return 0;
87 }
88  
89 0 ▶rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp);
Branch: 148 branches
BranchTrueFalseTotal
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 213 1 214
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 990 213 1203
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 1 213 214
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 1074 1074
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 560 514 1074
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 1074 213 1287
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 332 311 643
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 257 75 332
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 100 157 257
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 194 117 311
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 48 146 194
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 643 21 664
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 990 213 1203
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 213 0 213
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 213 213
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 1203 0 1203
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 213 213
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 213 213
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 213 213
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 2 211 213
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 90 121 211
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 90 90
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 198 198
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 198 0 198
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 198 198
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 82 116 198
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 19 63 82
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 82 82
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 82 0 82
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 31 85 116
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 6 25 31
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 25 0 25
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 198 8 206
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 8 8
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 19 0 19
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 19 19
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 19 0 19
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
rb_gen(, rtnt_, rtnt_t, struct rtree_neighbor, link, neighbor_cmp); 0 0 0
90  
91 /*------------------------------------------------------------------------- */
92 /* R-tree rectangle methods */
93 /*------------------------------------------------------------------------- */
94  
95 void
96 108 rtree_rect_normalize(struct rtree_rect *rect, unsigned dimension)
97 {
98 324 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 216 108 324
99 216 coord_t *coords = &rect->coords[2 * i];
100 216 ▶ if (coords[0] <= coords[1])
Branch: 1 branch
BranchTrueFalseTotal
if (coords[0] <= coords[1]) 216 0 216
101 216 continue;
102 0 coord_t tmp = coords[0];
103 0 coords[0] = coords[1];
104 0 coords[1] = tmp;
105 }
106 108 }
107  
108 static void
109 469704 rtree_rect_copy(struct rtree_rect *to, const struct rtree_rect *from,
110 unsigned dimension)
111 {
112 2348536 ▶ for (int i = dimension * 2; --i >= 0; )
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension * 2; --i >= 0; ) 1878832 469704 2348536
113 1878832 to->coords[i] = from->coords[i];
114 469704 }
115  
116 void
117 0 rtree_set2d(struct rtree_rect *rect,
118 coord_t left, coord_t bottom, coord_t right, coord_t top)
119 {
120 0 rect->coords[0] = left;
121 0 rect->coords[1] = right;
122 0 rect->coords[2] = bottom;
123 0 rect->coords[3] = top;
124 0 }
125  
126 void
127 0 rtree_set2dp(struct rtree_rect *rect, coord_t x, coord_t y)
128 {
129 0 rect->coords[0] = x;
130 0 rect->coords[1] = x;
131 0 rect->coords[2] = y;
132 0 rect->coords[3] = y;
133 0 }
134  
135 /* Manhattan distance */
136 static sq_coord_t
137 0 rtree_rect_neigh_distance(const struct rtree_rect *rect,
138 const struct rtree_rect *neigh_rect,
139 unsigned dimension)
140 {
141 0 sq_coord_t result = 0;
142 0 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 0 0 0
143 0 const coord_t *coords = &rect->coords[2 * i];
144 0 coord_t neigh_coord = neigh_rect->coords[2 * i];
145 0 ▶ if (neigh_coord < coords[0]) {
Branch: 1 branch
BranchTrueFalseTotal
if (neigh_coord < coords[0]) { 0 0 0
146 0 sq_coord_t diff = (sq_coord_t)(neigh_coord - coords[0]);
147 0 result += -diff;
148 0 ▶ } else if (neigh_coord > coords[1]) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (neigh_coord > coords[1]) { 0 0 0
149 0 sq_coord_t diff = (sq_coord_t)(neigh_coord - coords[1]);
150 0 result += diff;
151 }
152 }
153 0 return result;
154 }
155  
156 /* Euclid distance, squared */
157 static sq_coord_t
158 213 rtree_rect_neigh_distance2(const struct rtree_rect *rect,
159 const struct rtree_rect *neigh_rect,
160 unsigned dimension)
161 {
162 213 sq_coord_t result = 0;
163 639 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 426 213 639
164 426 const coord_t *coords = &rect->coords[2 * i];
165 426 coord_t neigh_coord = neigh_rect->coords[2 * i];
166 426 ▶ if (neigh_coord < coords[0]) {
Branch: 1 branch
BranchTrueFalseTotal
if (neigh_coord < coords[0]) { 319 107 426
167 319 sq_coord_t diff = (sq_coord_t)(neigh_coord - coords[0]);
168 319 result += diff * diff;
169 107 ▶ } else if (neigh_coord > coords[1]) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (neigh_coord > coords[1]) { 102 5 107
170 102 sq_coord_t diff = (sq_coord_t)(neigh_coord - coords[1]);
171 102 result += diff * diff;
172 }
173 }
174 213 return result;
175 }
176  
177 static area_t
178 9148050 rtree_rect_area(const struct rtree_rect *rect, unsigned dimension)
179 {
180 9148050 area_t area = 1;
181 27444150 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 18296100 9148050 27444150
182 18296100 const coord_t *coords = &rect->coords[2 * i];
183 18296100 area *= coords[1] - coords[0];
184 }
185 9148050 return area;
186 }
187  
188 static coord_t
189 391680 rtree_rect_half_margin(const struct rtree_rect *rect, unsigned dimension)
190 {
191 391680 coord_t hm = 0;
192 1175040 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 783360 391680 1175040
193 783360 const coord_t *coords = &rect->coords[2 * i];
194 783360 hm += coords[1] - coords[0];
195 }
196 391680 return hm;
197 }
198  
199 static void
200 1680652 rtree_rect_add(struct rtree_rect *to, const struct rtree_rect *item,
201 unsigned dimension)
202 {
203 5041956 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 3361304 1680652 5041956
204 3361304 coord_t *to_coords = &to->coords[2 * i];
205 3361304 const coord_t *item_coords = &item->coords[2 * i];
206 3361304 ▶ if (to_coords[0] > item_coords[0])
Branch: 1 branch
BranchTrueFalseTotal
if (to_coords[0] > item_coords[0]) 448890 2912414 3361304
207 448890 to_coords[0] = item_coords[0];
208 3361304 ▶ if (to_coords[1] < item_coords[1])
Branch: 1 branch
BranchTrueFalseTotal
if (to_coords[1] < item_coords[1]) 1395237 1966067 3361304
209 1395237 to_coords[1] = item_coords[1];
210 }
211 1680652 }
212  
213 static coord_t
214 9076682 rtree_min(coord_t a, coord_t b)
215 {
216 9076682 ▶ return a < b ? a : b;
Branch: 1 branch
BranchTrueFalseTotal
return a < b ? a : b; 5763851 3312831 9076682
217 }
218  
219 static coord_t
220 9076682 rtree_max(coord_t a, coord_t b)
221 {
222 9076682 ▶ return a > b ? a : b;
Branch: 1 branch
BranchTrueFalseTotal
return a > b ? a : b; 5637299 3439383 9076682
223 }
224  
225 static void
226 4518945 rtree_rect_cover(const struct rtree_rect *item1,
227 const struct rtree_rect *item2,
228 struct rtree_rect *result,
229 unsigned dimension)
230 {
231 13556835 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 9037890 4518945 13556835
232 9037890 const coord_t *i1_coords = &item1->coords[2 * i];
233 9037890 const coord_t *i2_coords = &item2->coords[2 * i];
234 9037890 coord_t *r_coords = &result->coords[2 * i];
235 9037890 r_coords[0] = rtree_min(i1_coords[0], i2_coords[0]);
236 9037890 r_coords[1] = rtree_max(i1_coords[1], i2_coords[1]);
237 }
238 4518945 }
239  
240 static void
241 36720 rtree_rect_intersection(const struct rtree_rect *item1,
242 const struct rtree_rect *item2,
243 struct rtree_rect *result,
244 unsigned dimension)
245 {
246 110160 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 73440 36720 110160
247 73440 const coord_t *i1_coords = &item1->coords[2 * i];
248 73440 const coord_t *i2_coords = &item2->coords[2 * i];
249 73440 coord_t *r_coords = &result->coords[2 * i];
250 73440 ▶ if (i1_coords[0] > i2_coords[1] || i1_coords[1] < i2_coords[0])
Branch: 2 branches
BranchTrueFalseTotal
if (i1_coords[0] > i2_coords[1] || i1_coords[1] < i2_coords[0]) 73440 0 73440
if (i1_coords[0] > i2_coords[1] || i1_coords[1] < i2_coords[0]) 34648 38792 73440
251 34648 r_coords[0] = r_coords[1] = 0;
252 else {
253 38792 r_coords[0] = rtree_max(i1_coords[0], i2_coords[0]);
254 38792 r_coords[1] = rtree_min(i1_coords[1], i2_coords[1]);
255 }
256 }
257 36720 }
258  
259 static bool
260 97 rtree_rect_intersects_rect(const struct rtree_rect *rt1,
261 const struct rtree_rect *rt2,
262 unsigned dimension)
263 {
264 185 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 143 42 185
265 143 const coord_t *coords1 = &rt1->coords[2 * i];
266 143 const coord_t *coords2 = &rt2->coords[2 * i];
267 143 ▶ if (coords1[0] > coords2[1] || coords1[1] < coords2[0])
Branch: 2 branches
BranchTrueFalseTotal
if (coords1[0] > coords2[1] || coords1[1] < coords2[0]) 143 0 143
if (coords1[0] > coords2[1] || coords1[1] < coords2[0]) 55 88 143
268 55 return false;
269 }
270 42 return true;
271 }
272  
273 static bool
274 101 rtree_rect_in_rect(const struct rtree_rect *rt1,
275 const struct rtree_rect *rt2,
276 unsigned dimension)
277 {
278 303 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 202 101 303
279 202 const coord_t *coords1 = &rt1->coords[2 * i];
280 202 const coord_t *coords2 = &rt2->coords[2 * i];
281 202 ▶ if (coords1[0] < coords2[0] || coords1[1] > coords2[1])
Branch: 2 branches
BranchTrueFalseTotal
if (coords1[0] < coords2[0] || coords1[1] > coords2[1]) 202 0 202
if (coords1[0] < coords2[0] || coords1[1] > coords2[1]) 0 202 202
282 0 return false;
283 }
284 101 return true;
285 }
286  
287 static bool
288 101 rtree_rect_strict_in_rect(const struct rtree_rect *rt1,
289 const struct rtree_rect *rt2,
290 unsigned dimension)
291 {
292 303 ▶ for (int i = dimension; --i >= 0; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension; --i >= 0; ) { 202 101 303
293 202 const coord_t *coords1 = &rt1->coords[2 * i];
294 202 const coord_t *coords2 = &rt2->coords[2 * i];
295 202 ▶ if (coords1[0] <= coords2[0] || coords1[1] >= coords2[1])
Branch: 2 branches
BranchTrueFalseTotal
if (coords1[0] <= coords2[0] || coords1[1] >= coords2[1]) 202 0 202
if (coords1[0] <= coords2[0] || coords1[1] >= coords2[1]) 0 202 202
296 0 return false;
297 }
298 101 return true;
299 }
300  
301 static bool
302 101 rtree_rect_holds_rect(const struct rtree_rect *rt1,
303 const struct rtree_rect *rt2,
304 unsigned dimension)
305 {
306 101 return rtree_rect_in_rect(rt2, rt1, dimension);
307 }
308  
309 static bool
310 101 rtree_rect_strict_holds_rect(const struct rtree_rect *rt1,
311 const struct rtree_rect *rt2,
312 unsigned dimension)
313 {
314 101 return rtree_rect_strict_in_rect(rt2, rt1, dimension);
315 }
316  
317 static bool
318 0 rtree_rect_equal_to_rect(const struct rtree_rect *rt1,
319 const struct rtree_rect *rt2,
320 unsigned dimension)
321 {
322 0 ▶ for (int i = dimension * 2; --i >= 0; )
Branch: 1 branch
BranchTrueFalseTotal
for (int i = dimension * 2; --i >= 0; ) 0 0 0
323 0 ▶ if (rt1->coords[i] != rt2->coords[i])
Branch: 1 branch
BranchTrueFalseTotal
if (rt1->coords[i] != rt2->coords[i]) 0 0 0
324 0 return false;
325 0 return true;
326 }
327  
328 static bool
329 106334 rtree_always_true(const struct rtree_rect *rt1,
330 const struct rtree_rect *rt2,
331 unsigned dimension)
332 {
333 (void) rt1;
334 (void) rt2;
335 (void) dimension;
336 106334 return true;
337 }
338  
339 /*------------------------------------------------------------------------- */
340 /* R-tree page methods */
341 /*------------------------------------------------------------------------- */
342  
343 static struct rtree_page *
344 6135 rtree_page_alloc(struct rtree *tree)
345 {
346 6135 ▶ if (tree->free_pages) {
Branch: 1 branch
BranchTrueFalseTotal
if (tree->free_pages) { 0 6135 6135
347 0 struct rtree_page *result =
348 (struct rtree_page *)tree->free_pages;
349 0 tree->free_pages = *(void **)tree->free_pages;
350 0 return result;
351 } else {
352 uint32_t unused_id;
353 6135 return (struct rtree_page *)
354 6135 matras_alloc(&tree->mtab, &unused_id);
355 }
356 }
357  
358 static void
359 6135 rtree_page_free(struct rtree *tree, struct rtree_page *page)
360 {
361 6135 *(void **)page = tree->free_pages;
362 6135 tree->free_pages = (void *)page;
363 6135 }
364  
365 static struct rtree_page_branch *
366 5748207 rtree_branch_get(const struct rtree *tree, const struct rtree_page *page,
367 unsigned ind)
368 {
369 11496414 return (struct rtree_page_branch *)
370 5748207 ((char *)page->data + ind * tree->page_branch_size);
371 }
372  
373 static void
374 259318 rtree_branch_copy(struct rtree_page_branch *to,
375 const struct rtree_page_branch *from, unsigned dimension)
376 {
377 259318 to->data = from->data;
378 259318 rtree_rect_copy(&to->rect, &from->rect, dimension);
379 259318 }
380  
381  
382 static void
383 0 set_next_reinsert_page(const struct rtree *tree, struct rtree_page *page,
384 struct rtree_page *next_page)
385 {
386 /* The page must be MIN_FILLed, so last branch is unused */
387 0 struct rtree_page_branch *b = rtree_branch_get(tree, page,
388 0 tree->page_max_fill - 1);
389 0 b->data.page = next_page;
390 0 }
391  
392 struct rtree_page *
393 0 get_next_reinsert_page(const struct rtree *tree, const struct rtree_page *page)
394 {
395 0 struct rtree_page_branch *b = rtree_branch_get(tree, page,
396 0 tree->page_max_fill - 1);
397 0 return b->data.page;
398 }
399  
400 /* Calculate cover of all rectangles at page */
401 static void
402 12241 rtree_page_cover(const struct rtree *tree, const struct rtree_page *page,
403 struct rtree_rect *res)
404 {
405 12241 rtree_rect_copy(res, &rtree_branch_get(tree, page, 0)->rect,
406 12241 tree->dimension);
407 159132 ▶ for (unsigned i = 1; i < page->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 1; i < page->n; i++) { 146891 12241 159132
408 146891 rtree_rect_add(res, &rtree_branch_get(tree, page, i)->rect,
409 146891 tree->dimension);
410 }
411 12241 }
412  
413 /* Create root page by first inserting record */
414 static void
415 6 rtree_page_init_with_record(const struct rtree *tree, struct rtree_page *page,
416 struct rtree_rect *rect, record_t obj)
417 {
418 6 struct rtree_page_branch *b = rtree_branch_get(tree, page, 0);
419 6 page->n = 1;
420 6 rtree_rect_copy(&b->rect, rect, tree->dimension);
421 6 b->data.record = obj;
422 6 }
423  
424 /* Create new root page (root splitting) */
425 static void
426 4 rtree_page_init_with_pages(const struct rtree *tree, struct rtree_page *page,
427 struct rtree_page *page1, struct rtree_page *page2)
428 {
429 4 page->n = 2;
430 4 struct rtree_page_branch *b = rtree_branch_get(tree, page, 0);
431 4 rtree_page_cover(tree, page1, &b->rect);
432 4 b->data.page = page1;
433 4 b = rtree_branch_get(tree, page, 1);
434 4 rtree_page_cover(tree, page2, &b->rect);
435 4 b->data.page = page2;
436 4 }
437  
438 static struct rtree_page *
439 6120 rtree_split_page(struct rtree *tree, struct rtree_page *page,
440 const struct rtree_page_branch *br)
441 {
442 6120 ▶ assert(page->n == tree->page_max_fill);
Branch: 1 branch
BranchTrueFalseTotal
assert(page->n == tree->page_max_fill); 0 6120 6120
443 const struct rtree_rect *rects[RTREE_MAXIMUM_BRANCHES_IN_PAGE + 1];
444 unsigned ids[RTREE_MAXIMUM_BRANCHES_IN_PAGE + 1];
445 6120 rects[0] = &br->rect;
446 6120 ids[0] = 0;
447 159120 ▶ for (unsigned i = 0; i < page->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0; i < page->n; i++) { 153000 6120 159120
448 153000 struct rtree_page_branch *b = rtree_branch_get(tree, page, i);
449 153000 rects[i + 1] = &b->rect;
450 153000 ids[i + 1] = i + 1;
451 }
452 6120 const unsigned n = page->n + 1;
453 6120 const unsigned k_max = n - 2 * tree->page_min_fill;
454 6120 unsigned d = tree->dimension;
455 6120 unsigned best_axis = 0;
456 6120 coord_t best_s = 0;
457 18360 ▶ for (unsigned a = 0; a < d; a++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned a = 0; a < d; a++) { 12240 6120 18360
458 318240 ▶ for (unsigned i = 0; i < n - 1; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0; i < n - 1; i++) { 306000 12240 318240
459 306000 unsigned min_i = i;
460 306000 coord_t min_l = rects[ids[i]]->coords[2 * a];
461 306000 coord_t min_r = rects[ids[i]]->coords[2 * a + 1];
462 4284000 ▶ for (unsigned j = i + 1; j < n; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned j = i + 1; j < n; j++) { 3978000 306000 4284000
463 3978000 coord_t l = rects[ids[j]]->coords[2 * a];
464 3978000 coord_t r = rects[ids[j]]->coords[2 * a + 1];
465 3978000 ▶ if (l < min_l || (l == min_l && r < min_r)) {
Branch: 3 branches
BranchTrueFalseTotal
if (l < min_l || (l == min_l && r < min_r)) { 3351577 626423 3978000
if (l < min_l || (l == min_l && r < min_r)) { 0 3351577 3351577
if (l < min_l || (l == min_l && r < min_r)) { 0 0 0
466 626423 min_i = j;
467 626423 min_l = l;
468 626423 min_r = r;
469 }
470 }
471 306000 unsigned tmp = ids[i];
472 306000 ids[i] = ids[min_i];
473 306000 ids[min_i] = tmp;
474 }
475 struct rtree_rect test_rect;
476 coord_t dir_hm[RTREE_MAXIMUM_BRANCHES_IN_PAGE + 1];
477 coord_t rev_hm[RTREE_MAXIMUM_BRANCHES_IN_PAGE + 1];
478 12240 dir_hm[0] = 0;
479 12240 rtree_rect_copy(&test_rect, rects[ids[0]], d);
480 12240 dir_hm[1] = rtree_rect_half_margin(&test_rect, d);
481 195840 ▶ for (unsigned i = 1; i < n - tree->page_min_fill; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 1; i < n - tree->page_min_fill; i++) { 183600 12240 195840
482 183600 rtree_rect_add(&test_rect, rects[ids[i]], d);
483 183600 dir_hm[i + 1] = rtree_rect_half_margin(&test_rect, d);
484 }
485 12240 rev_hm[0] = 0;
486 12240 rtree_rect_copy(&test_rect, rects[ids[n - 1]], d);
487 12240 rev_hm[1] = rtree_rect_half_margin(&test_rect, d);
488 195840 ▶ for (unsigned i = 1; i < n - tree->page_min_fill; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 1; i < n - tree->page_min_fill; i++) { 183600 12240 195840
489 183600 rtree_rect_add(&test_rect, rects[ids[n - i - 1]], d);
490 183600 rev_hm[i + 1] = rtree_rect_half_margin(&test_rect, d);
491 }
492 12240 coord_t s = 0;
493 85680 ▶ for (unsigned k = 0; k < k_max; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned k = 0; k < k_max; k++) { 73440 12240 85680
494 73440 unsigned k1 = tree->page_min_fill + k;
495 73440 unsigned k2 = n - k1;
496 73440 s += dir_hm[k1] + rev_hm[k2];
497 }
498 12240 ▶ if (a == 0 || s < best_s) {
Branch: 2 branches
BranchTrueFalseTotal
if (a == 0 || s < best_s) { 6120 6120 12240
if (a == 0 || s < best_s) { 3018 3102 6120
499 9138 best_axis = a;
500 9138 best_s = s;
501 }
502 }
503 6120 unsigned a = best_axis;
504 159120 ▶ for (unsigned i = 0; i < n - 1; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0; i < n - 1; i++) { 153000 6120 159120
505 153000 unsigned min_i = i;
506 153000 coord_t min_l = rects[ids[i]]->coords[2 * a];
507 153000 coord_t min_r = rects[ids[i]]->coords[2 * a + 1];
508 2142000 ▶ for (unsigned j = i + 1; j < n; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned j = i + 1; j < n; j++) { 1989000 153000 2142000
509 1989000 coord_t l = rects[ids[j]]->coords[2 * a];
510 1989000 coord_t r = rects[ids[j]]->coords[2 * a + 1];
511 1989000 ▶ if (l < min_l || (l == min_l && r < min_r)) {
Branch: 3 branches
BranchTrueFalseTotal
if (l < min_l || (l == min_l && r < min_r)) { 1827919 161081 1989000
if (l < min_l || (l == min_l && r < min_r)) { 0 1827919 1827919
if (l < min_l || (l == min_l && r < min_r)) { 0 0 0
512 161081 min_i = j;
513 161081 min_l = l;
514 161081 min_r = r;
515 }
516 }
517 153000 unsigned tmp = ids[i];
518 153000 ids[i] = ids[min_i];
519 153000 ids[min_i] = tmp;
520 }
521 6120 area_t min_overlap = 0;
522 6120 area_t min_area = 0;
523 6120 unsigned min_k = 0;
524 42840 ▶ for (unsigned k = 0; k < k_max; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned k = 0; k < k_max; k++) { 36720 6120 42840
525 36720 unsigned k1 = tree->page_min_fill + k;
526 /* unsigned k2 = n - k1; */
527 struct rtree_rect rt1, rt2, over_rt;
528 36720 rtree_rect_copy(&rt1, rects[ids[0]], d);
529 459000 ▶ for (unsigned i = 1; i < k1; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 1; i < k1; i++) { 422280 36720 459000
530 422280 rtree_rect_add(&rt1, rects[ids[i]], d);
531 }
532 36720 rtree_rect_copy(&rt2, rects[ids[k1]], d);
533 495720 ▶ for (unsigned i = k1 + 1; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = k1 + 1; i < n; i++) { 459000 36720 495720
534 459000 rtree_rect_add(&rt2, rects[ids[i]], d);
535 }
536 36720 rtree_rect_intersection(&rt1, &rt2, &over_rt, d);
537 36720 area_t overlap = rtree_rect_area(&over_rt, d);
538 36720 area_t area = rtree_rect_area(&rt1, d) +
539 36720 rtree_rect_area(&rt2, d);
540 36720 ▶ if (k == 0 || overlap < min_overlap ||
Branch: 3 branches
BranchTrueFalseTotal
if (k == 0 || overlap < min_overlap || 30600 6120 36720
if (k == 0 || overlap < min_overlap || 29997 603 30600
if (k == 0 || overlap < min_overlap || 28850 1147 29997
541 28850 ▶ (overlap == min_overlap && area < min_area)) {
Branch: 1 branch
BranchTrueFalseTotal
(overlap == min_overlap && area < min_area)) { 8751 20099 28850
542 15474 min_k = k;
543 15474 min_overlap = overlap;
544 15474 min_area = area;
545 }
546 }
547 6120 unsigned k = min_k;
548 6120 unsigned k1 = tree->page_min_fill + k;
549 6120 unsigned k2 = n - k1;
550 6120 struct rtree_page *new_page = rtree_page_alloc(tree);
551 6120 tree->n_pages++;
552 char taken[RTREE_MAXIMUM_BRANCHES_IN_PAGE];
553 6120 memset(taken, 0, sizeof(taken));
554 82605 ▶ for (unsigned i = 0; i < k1; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0; i < k1; i++) { 76485 6120 82605
555 struct rtree_page_branch *new_b =
556 76485 rtree_branch_get(tree, new_page, i);
557 76485 const struct rtree_page_branch *from_b = br;
558 76485 ▶ if (ids[i]) {
Branch: 1 branch
BranchTrueFalseTotal
if (ids[i]) { 73622 2863 76485
559 73622 from_b = rtree_branch_get(tree, page, ids[i] - 1);
560 73622 taken[ids[i] - 1] = 1;
561 }
562 76485 rtree_branch_copy(new_b, from_b, d);
563 }
564 6120 unsigned moved = 0;
565 159120 ▶ for (unsigned i = 0, j = 0; j < page->n; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0, j = 0; j < page->n; j++) { 153000 6120 159120
566 153000 ▶ if (taken[j] == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (taken[j] == 0) { 79378 73622 153000
567 struct rtree_page_branch *to, *from;
568 79378 to = rtree_branch_get(tree, page, i++);
569 79378 from = rtree_branch_get(tree, page, j);
570 79378 rtree_branch_copy(to, from, tree->dimension);
571 79378 moved++;
572 }
573 }
574 6120 ▶ assert(moved == k2 || moved + 1 == k2);
Branch: 2 branches
BranchTrueFalseTotal
assert(moved == k2 || moved + 1 == k2); 3257 2863 6120
assert(moved == k2 || moved + 1 == k2); 0 3257 3257
575 6120 ▶ if (moved + 1 == k2) {
Branch: 1 branch
BranchTrueFalseTotal
if (moved + 1 == k2) { 3257 2863 6120
576 struct rtree_page_branch *to;
577 3257 to = rtree_branch_get(tree, page, moved);
578 3257 rtree_branch_copy(to, br, tree->dimension);
579 }
580 6120 new_page->n = k1;
581 6120 page->n = k2;
582 6120 return new_page;
583 }
584  
585 static struct rtree_page*
586 106316 rtree_page_add_branch(struct rtree *tree, struct rtree_page *page,
587 const struct rtree_page_branch *br)
588 {
589 106316 ▶ if (page->n < tree->page_max_fill) {
Branch: 1 branch
BranchTrueFalseTotal
if (page->n < tree->page_max_fill) { 100196 6120 106316
590 struct rtree_page_branch *b;
591 100196 b = rtree_branch_get(tree, page, page->n++);
592 100196 rtree_branch_copy(b, br, tree->dimension);
593 100196 return NULL;
594 } else {
595 6120 return rtree_split_page(tree, page, br);
596 }
597 }
598  
599 static void
600 2 rtree_page_remove_branch(struct rtree *tree, struct rtree_page *page, int i)
601 {
602 2 page->n--;
603 4 ▶ for (unsigned j = i; j < page->n; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned j = i; j < page->n; j++) { 2 2 4
604 struct rtree_page_branch *to, *from;
605 2 to = rtree_branch_get(tree, page, j);
606 2 from = rtree_branch_get(tree, page, j + 1);
607 2 rtree_branch_copy(to, from, tree->dimension);
608 }
609 2 }
610  
611 static struct rtree_page *
612 391597 rtree_page_insert(struct rtree *tree, struct rtree_page *page,
613 const struct rtree_rect *rect, record_t obj, int level)
614 {
615 struct rtree_page_branch br;
616 391597 ▶ if (--level != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (--level != 0) { 291397 100200 391597
617 /* not a leaf page, minize area increase */
618 291397 unsigned mini = 0;
619 291397 char found = 0;
620 291397 area_t min_incr = 0, best_area = 0;
621 4810342 ▶ for (unsigned i = 0; i < page->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0; i < page->n; i++) { 4518945 291397 4810342
622 struct rtree_page_branch *b;
623 4518945 b = rtree_branch_get(tree, page, i);
624 4518945 area_t r_area = rtree_rect_area(&b->rect,
625 tree->dimension);
626 struct rtree_rect cover;
627 4518945 rtree_rect_cover(&b->rect, rect,
628 &cover, tree->dimension);
629 4518945 area_t incr = rtree_rect_area(&cover,
630 tree->dimension);
631 4518945 incr -= r_area;
632 4518945 ▶ assert(incr >= 0);
Branch: 1 branch
BranchTrueFalseTotal
assert(incr >= 0); 0 4518945 4518945
633 4518945 ▶ if (i == 0 || incr < min_incr || (incr == min_incr && r_area < best_area)) {
Branch: 4 branches
BranchTrueFalseTotal
if (i == 0 || incr < min_incr || (incr == min_incr && r_area < best_area)) { 4227548 291397 4518945
if (i == 0 || incr < min_incr || (incr == min_incr && r_area < best_area)) { 3563183 664365 4227548
if (i == 0 || incr < min_incr || (incr == min_incr && r_area < best_area)) { 34055 3529128 3563183
if (i == 0 || incr < min_incr || (incr == min_incr && r_area < best_area)) { 21960 12095 34055
634 977722 best_area = r_area;
635 977722 min_incr = incr;
636 977722 mini = i;
637 977722 found = 1;
638 }
639 }
640 291397 ▶ assert(found);
Branch: 1 branch
BranchTrueFalseTotal
assert(found); 0 291397 291397
641 (void) found;
642 struct rtree_page_branch *b;
643 291397 b = rtree_branch_get(tree, page, mini);
644 291397 struct rtree_page *p = b->data.page;
645 291397 struct rtree_page *q = rtree_page_insert(tree, p,
646 rect, obj, level);
647 291397 ▶ if (q == NULL) {
Branch: 1 branch
BranchTrueFalseTotal
if (q == NULL) { 285281 6116 291397
648 /* child was not split */
649 285281 rtree_rect_add(&b->rect, rect, tree->dimension);
650 285281 return NULL;
651 } else {
652 /* child was split */
653 6116 rtree_page_cover(tree, p, &b->rect);
654 6116 br.data.page = q;
655 6116 rtree_page_cover(tree, q, &br.rect);
656 6116 return rtree_page_add_branch(tree, page, &br);
657 }
658 } else {
659 100200 br.data.record = obj;
660 100200 rtree_rect_copy(&br.rect, rect, tree->dimension);
661 100200 return rtree_page_add_branch(tree, page, &br);
662 }
663 }
664  
665 static bool
666 3 rtree_page_remove(struct rtree *tree, struct rtree_page *page,
667 const struct rtree_rect *rect, record_t obj,
668 int level, struct rtree_reinsert_list *rlist)
669 {
670 3 unsigned d = tree->dimension;
671 3 ▶ if (--level != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (--level != 0) { 0 3 3
672 0 ▶ for (unsigned i = 0; i < page->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0; i < page->n; i++) { 0 0 0
673 struct rtree_page_branch *b;
674 0 b = rtree_branch_get(tree, page, i);
675 0 ▶ if (!rtree_rect_intersects_rect(&b->rect, rect, d))
Branch: 1 branch
BranchTrueFalseTotal
if (!rtree_rect_intersects_rect(&b->rect, rect, d)) 0 0 0
676 0 continue;
677 0 struct rtree_page *next_page = b->data.page;
678 0 ▶ if (!rtree_page_remove(tree, next_page, rect,
Branch: 1 branch
BranchTrueFalseTotal
if (!rtree_page_remove(tree, next_page, rect, 0 0 0
679 obj, level, rlist))
680 0 continue;
681 0 ▶ if (next_page->n >= tree->page_min_fill) {
Branch: 1 branch
BranchTrueFalseTotal
if (next_page->n >= tree->page_min_fill) { 0 0 0
682 0 rtree_page_cover(tree, next_page, &b->rect);
683 } else {
684 /* not enough entries in child */
685 0 set_next_reinsert_page(tree, next_page,
686 rlist->chain);
687 0 rlist->chain = next_page;
688 0 rlist->level = level - 1;
689 0 rtree_page_remove_branch(tree, page, i);
690 }
691 0 return true;
692 }
693 } else {
694 6 ▶ for (unsigned i = 0; i < page->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0; i < page->n; i++) { 5 1 6
695 struct rtree_page_branch *b;
696 5 b = rtree_branch_get(tree, page, i);
697 5 ▶ if (b->data.page == obj) {
Branch: 1 branch
BranchTrueFalseTotal
if (b->data.page == obj) { 2 3 5
698 2 rtree_page_remove_branch(tree, page, i);
699 2 return true;
700 }
701 }
702 }
703 1 return false;
704 }
705  
706 static void
707 6130 rtree_page_purge(struct rtree *tree, struct rtree_page *page, int level)
708 {
709 6130 ▶ if (--level != 0) { /* this is an internal node in the tree */
Branch: 1 branch
BranchTrueFalseTotal
if (--level != 0) { /* this is an internal node in the tree */ 354 5776 6130
710 6478 ▶ for (unsigned i = 0; i < page->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0; i < page->n; i++) { 6124 354 6478
711 struct rtree_page_branch *b;
712 6124 b = rtree_branch_get(tree, page, i);
713 6124 rtree_page_purge(tree, b->data.page, level);
714 }
715 }
716 6130 rtree_page_free(tree, page);
717 6130 }
718  
719 /*------------------------------------------------------------------------- */
720 /* R-tree iterator methods */
721 /*------------------------------------------------------------------------- */
722  
723 static bool
724 6153 rtree_iterator_goto_first(struct rtree_iterator *itr, unsigned sp,
725 struct rtree_page* pg)
726 {
727 6153 unsigned d = itr->tree->dimension;
728 6153 ▶ if (sp + 1 == itr->tree->height) {
Branch: 1 branch
BranchTrueFalseTotal
if (sp + 1 == itr->tree->height) { 5791 362 6153
729 5792 ▶ for (unsigned i = 0, n = pg->n; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0, n = pg->n; i < n; i++) { 5792 0 5792
730 struct rtree_page_branch *b;
731 5792 b = rtree_branch_get(itr->tree, pg, i);
732 5792 ▶ if (itr->leaf_cmp(&itr->rect, &b->rect, d)) {
Branch: 1 branch
BranchTrueFalseTotal
if (itr->leaf_cmp(&itr->rect, &b->rect, d)) { 5791 1 5792
733 5791 itr->stack[sp].page = pg;
734 5791 itr->stack[sp].pos = i;
735 5791 return true;
736 }
737 }
738 } else {
739 382 ▶ for (unsigned i = 0, n = pg->n; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = 0, n = pg->n; i < n; i++) { 382 0 382
740 struct rtree_page_branch *b;
741 382 b = rtree_branch_get(itr->tree, pg, i);
742 382 ▶ if (itr->intr_cmp(&itr->rect, &b->rect, d)
Branch: 1 branch
BranchTrueFalseTotal
if (itr->intr_cmp(&itr->rect, &b->rect, d) 362 20 382
743 362 ▶ && rtree_iterator_goto_first(itr, sp + 1,
Branch: 1 branch
BranchTrueFalseTotal
&& rtree_iterator_goto_first(itr, sp + 1, 362 0 362
744 b->data.page))
745 {
746 362 itr->stack[sp].page = pg;
747 362 itr->stack[sp].pos = i;
748 362 return true;
749 }
750 }
751 }
752 0 return false;
753 }
754  
755  
756 static bool
757 106570 rtree_iterator_goto_next(struct rtree_iterator *itr, unsigned sp)
758 {
759 106570 unsigned d = itr->tree->dimension;
760 106570 struct rtree_page *pg = itr->stack[sp].page;
761 106570 ▶ if (sp + 1 == itr->tree->height) {
Branch: 1 branch
BranchTrueFalseTotal
if (sp + 1 == itr->tree->height) { 100433 6137 106570
762 100456 ▶ for (unsigned i = itr->stack[sp].pos, n = pg->n; ++i < n;) {
Branch: 1 branch
BranchTrueFalseTotal
for (unsigned i = itr->stack[sp].pos, n = pg->n; ++i < n;) { 94667 5789 100456
763 struct rtree_page_branch *b;
764 94667 b = rtree_branch_get(itr->tree, pg, i);
765 94667 ▶ if (itr->leaf_cmp(&itr->rect, &b->rect, d)) {
Branch: 1 branch
BranchTrueFalseTotal
if (itr->leaf_cmp(&itr->rect, &b->rect, d)) { 94644 23 94667
766 94644 itr->stack[sp].pos = i;
767 94644 return true;
768 }
769 }
770 } else {
771 6148 ▶ for (int i = itr->stack[sp].pos, n = pg->n; ++i < n;) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = itr->stack[sp].pos, n = pg->n; ++i < n;) { 5792 356 6148
772 struct rtree_page_branch *b;
773 5792 b = rtree_branch_get(itr->tree, pg, i);
774 5792 ▶ if (itr->intr_cmp(&itr->rect, &b->rect, d)
Branch: 1 branch
BranchTrueFalseTotal
if (itr->intr_cmp(&itr->rect, &b->rect, d) 5781 11 5792
775 5781 ▶ && rtree_iterator_goto_first(itr, sp + 1,
Branch: 1 branch
BranchTrueFalseTotal
&& rtree_iterator_goto_first(itr, sp + 1, 5781 0 5781
776 b->data.page))
777 {
778 5781 itr->stack[sp].page = pg;
779 5781 itr->stack[sp].pos = i;
780 5781 return true;
781 }
782 }
783 }
784 6145 ▶ return sp > 0 ? rtree_iterator_goto_next(itr, sp - 1) : false;
Branch: 2 branches
BranchTrueFalseTotal
return sp > 0 ? rtree_iterator_goto_next(itr, sp - 1) : false; 6137 8 6145
return sp > 0 ? rtree_iterator_goto_next(itr, sp - 1) : false; 6131 6 6137
785 }
786  
787 void
788 19 rtree_iterator_destroy(struct rtree_iterator *itr)
789 {
790 struct rtree_neighbor_page *curr, *next;
791 24 ▶ for (curr = itr->page_list; curr != NULL; curr = next) {
Branch: 1 branch
BranchTrueFalseTotal
for (curr = itr->page_list; curr != NULL; curr = next) { 5 19 24
792 5 next = curr->next;
793 5 rtree_page_free((struct rtree *) itr->tree,
794 (struct rtree_page *) curr);
795 }
796 19 itr->page_list = NULL;
797 19 itr->page_pos = INT_MAX;
798 19 }
799  
800 struct rtree_neighbor *
801 0 rtree_iterator_reset_cb(rtnt_t *t, struct rtree_neighbor *n, void *d)
802 {
803 (void) t;
804 0 struct rtree_iterator *itr = (struct rtree_iterator *)d;
805 0 n->next = itr->neigh_free_list;
806 0 itr->neigh_free_list = n;
807 0 return 0;
808 }
809  
810 static void
811 19 rtree_iterator_reset(struct rtree_iterator *itr)
812 {
813 19 rtnt_iter(&itr->neigh_tree, 0, rtree_iterator_reset_cb, (void *)itr);
814 19 rtnt_new(&itr->neigh_tree);
815 19 }
816  
817 static struct rtree_neighbor *
818 89 rtree_iterator_allocate_neighbour(struct rtree_iterator *itr)
819 {
820 89 ▶ if (itr->page_pos >= itr->tree->neighbours_in_page) {
Branch: 1 branch
BranchTrueFalseTotal
if (itr->page_pos >= itr->tree->neighbours_in_page) { 5 84 89
821 struct rtree_neighbor_page *new_page =
822 (struct rtree_neighbor_page *)
823 5 rtree_page_alloc((struct rtree*)itr->tree);
824 5 new_page->next = itr->page_list;
825 5 itr->page_list = new_page;
826 5 itr->page_pos = 0;
827 }
828 89 return itr->page_list->buf + itr->page_pos++;
829 }
830  
831 static struct rtree_neighbor *
832 213 rtree_iterator_new_neighbor(struct rtree_iterator *itr,
833 void *child, sq_coord_t distance, int level)
834 {
835 213 struct rtree_neighbor *n = itr->neigh_free_list;
836 213 ▶ if (n == NULL)
Branch: 1 branch
BranchTrueFalseTotal
if (n == NULL) 89 124 213
837 89 n = rtree_iterator_allocate_neighbour(itr);
838 else
839 124 itr->neigh_free_list = n->next;
840 213 n->child = child;
841 213 n->distance = distance;
842 213 n->level = level;
843 213 return n;
844 }
845  
846 static void
847 213 rtree_iterator_free_neighbor(struct rtree_iterator *itr,
848 struct rtree_neighbor *n)
849 {
850 213 n->next = itr->neigh_free_list;
851 213 itr->neigh_free_list = n;
852 213 }
853  
854 void
855 19 rtree_iterator_init(struct rtree_iterator *itr)
856 {
857 19 itr->tree = 0;
858 19 rtnt_new(&itr->neigh_tree);
859 19 itr->neigh_free_list = NULL;
860 19 itr->page_list = NULL;
861 19 itr->page_pos = INT_MAX;
862 19 }
863  
864 static void
865 13 rtree_iterator_process_neigh(struct rtree_iterator *itr,
866 struct rtree_neighbor *neighbor)
867 {
868 13 unsigned d = itr->tree->dimension;
869 13 void *child = neighbor->child;
870 13 struct rtree_page *pg = (struct rtree_page *)child;
871 13 int level = neighbor->level;
872 13 rtree_iterator_free_neighbor(itr, neighbor);
873 225 ▶ for (int i = 0, n = pg->n; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0, n = pg->n; i < n; i++) { 212 13 225
874 struct rtree_page_branch *b;
875 212 b = rtree_branch_get(itr->tree, pg, i);
876 coord_t distance;
877 212 ▶ if (itr->tree->distance_type == RTREE_EUCLID)
Branch: 1 branch
BranchTrueFalseTotal
if (itr->tree->distance_type == RTREE_EUCLID) 212 0 212
878 212 distance = rtree_rect_neigh_distance2(&b->rect,
879 212 &itr->rect, d);
880 else
881 0 distance = rtree_rect_neigh_distance(&b->rect,
882 0 &itr->rect, d);
883 struct rtree_neighbor *neigh =
884 212 rtree_iterator_new_neighbor(itr, b->data.page,
885 distance, level - 1);
886 212 rtnt_insert(&itr->neigh_tree, neigh);
887 }
888 13 }
889  
890  
891 record_t
892 100634 rtree_iterator_next(struct rtree_iterator *itr)
893 {
894 100634 ▶ if (itr->version != itr->tree->version) {
Branch: 1 branch
BranchTrueFalseTotal
if (itr->version != itr->tree->version) { 0 100634 100634
895 /* Index was updated since cursor initialziation */
896 0 return NULL;
897 }
898 100634 ▶ if (itr->op == SOP_NEIGHBOR) {
Branch: 1 branch
BranchTrueFalseTotal
if (itr->op == SOP_NEIGHBOR) { 201 100433 100634
899 /* To return element in order of increasing distance from
900 * specified point, we build sorted list of R-Tree items
901 * (ordered by distance from specified point) starting from
902 * root page.
903 * Algorithm is the following:
904 *
905 * insert root R-Tree page in the sorted list
906 * while sorted list is not empty:
907 * get top element from the sorted list
908 * if it is tree leaf (record) then return it as
909 * current element
910 * otherwise (R-Tree page) get siblings of this R-Tree
911 * page and insert them in sorted list
912 */
913 13 while (true) {
914 struct rtree_neighbor *neighbor =
915 214 rtnt_first(&itr->neigh_tree);
916 214 ▶ if (neighbor == NULL)
Branch: 1 branch
BranchTrueFalseTotal
if (neighbor == NULL) 1 213 214
917 1 return NULL;
918 213 rtnt_remove(&itr->neigh_tree, neighbor);
919 213 ▶ if (neighbor->level == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (neighbor->level == 0) { 200 13 213
920 200 void *child = neighbor->child;
921 200 rtree_iterator_free_neighbor(itr, neighbor);
922 200 return (record_t)child;
923 } else {
924 13 rtree_iterator_process_neigh(itr, neighbor);
925 }
926 }
927 }
928 100433 int sp = itr->tree->height - 1;
929 100433 ▶ if (!itr->eof && rtree_iterator_goto_next(itr, sp)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!itr->eof && rtree_iterator_goto_next(itr, sp)) { 100433 0 100433
if (!itr->eof && rtree_iterator_goto_next(itr, sp)) { 100425 8 100433
930 struct rtree_page_branch *b;
931 100425 b = rtree_branch_get(itr->tree,
932 100425 itr->stack[sp].page, itr->stack[sp].pos);
933 100425 return b->data.record;
934 }
935 8 itr->eof = true;
936 8 return NULL;
937 }
938  
939 /*------------------------------------------------------------------------- */
940 /* R-tree methods */
941 /*------------------------------------------------------------------------- */
942  
943 int
944 14 rtree_init(struct rtree *tree, unsigned dimension, uint32_t extent_size,
945 rtree_extent_alloc_t extent_alloc, rtree_extent_free_t extent_free,
946 void *alloc_ctx, enum rtree_distance_type distance_type)
947 {
948 14 tree->n_records = 0;
949 14 tree->height = 0;
950 14 tree->root = NULL;
951 14 tree->version = 0;
952 14 tree->n_pages = 0;
953 14 tree->free_pages = 0;
954  
955 14 tree->dimension = dimension;
956 14 tree->distance_type = distance_type;
957 14 tree->page_branch_size =
958 (RTREE_BRANCH_DATA_SIZE + dimension * 2 * sizeof(coord_t));
959 14 tree->page_size = RTREE_OPTIMAL_BRANCHES_IN_PAGE *
960 14 tree->page_branch_size + sizeof(int);
961 /* round up to closest power of 2 */
962 14 int lz = __builtin_clz(tree->page_size - 1);
963 14 tree->page_size = 1u << (sizeof(int) * CHAR_BIT - lz);
964 14 ▶ assert(tree->page_size - sizeof(int) >=
Branch: 1 branch
BranchTrueFalseTotal
assert(tree->page_size - sizeof(int) >= 0 14 14
965 tree->page_branch_size * RTREE_OPTIMAL_BRANCHES_IN_PAGE);
966 14 tree->page_max_fill = (tree->page_size - sizeof(int)) /
967 14 tree->page_branch_size;
968 14 tree->page_min_fill = tree->page_max_fill * 2 / 5;
969 14 tree->neighbours_in_page = (tree->page_size - sizeof(void *))
970 14 / sizeof(struct rtree_neighbor);
971  
972 14 matras_create(&tree->mtab, extent_size, tree->page_size,
973 extent_alloc, extent_free, alloc_ctx);
974 14 return 0;
975 }
976  
977 void
978 14 rtree_destroy(struct rtree *tree)
979 {
980 14 rtree_purge(tree);
981 14 matras_destroy(&tree->mtab);
982 14 }
983  
984 void
985 100206 rtree_insert(struct rtree *tree, struct rtree_rect *rect, record_t obj)
986 {
987 100206 ▶ if (tree->root == NULL) {
Branch: 1 branch
BranchTrueFalseTotal
if (tree->root == NULL) { 6 100200 100206
988 6 tree->root = rtree_page_alloc(tree);
989 6 rtree_page_init_with_record(tree, tree->root, rect, obj);
990 6 tree->height = 1;
991 6 tree->n_pages++;
992 } else {
993 struct rtree_page *p =
994 100200 rtree_page_insert(tree, tree->root, rect, obj, tree->height);
995 100200 ▶ if (p != NULL) {
Branch: 1 branch
BranchTrueFalseTotal
if (p != NULL) { 4 100196 100200
996 /* root splitted */
997 4 struct rtree_page *new_root = rtree_page_alloc(tree);
998 4 rtree_page_init_with_pages(tree, new_root,
999 tree->root, p);
1000 4 tree->root = new_root;
1001 4 tree->height++;
1002 4 tree->n_pages++;
1003 }
1004 }
1005 100206 tree->version++;
1006 100206 tree->n_records++;
1007 100206 }
1008  
1009 bool
1010 3 rtree_remove(struct rtree *tree, const struct rtree_rect *rect, record_t obj)
1011 {
1012 struct rtree_reinsert_list rlist;
1013 3 rlist.chain = NULL;
1014 3 ▶ if (tree->height == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (tree->height == 0) 0 3 3
1015 0 return false;
1016 3 ▶ if (!rtree_page_remove(tree, tree->root, rect, obj, tree->height, &rlist))
Branch: 1 branch
BranchTrueFalseTotal
if (!rtree_page_remove(tree, tree->root, rect, obj, tree->height, &rlist)) 1 2 3
1017 1 return false;
1018 2 struct rtree_page *pg = rlist.chain;
1019 2 int level = rlist.level;
1020 2 ▶ while (pg != NULL) {
Branch: 1 branch
BranchTrueFalseTotal
while (pg != NULL) { 0 2 2
1021 0 ▶ for (int i = 0, n = pg->n; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0, n = pg->n; i < n; i++) { 0 0 0
1022 struct rtree_page_branch *b;
1023 0 b = rtree_branch_get(tree, pg, i);
1024 struct rtree_page *p =
1025 0 rtree_page_insert(tree, tree->root,
1026 0 &b->rect, b->data.record,
1027 0 tree->height - level);
1028 0 ▶ if (p != NULL) {
Branch: 1 branch
BranchTrueFalseTotal
if (p != NULL) { 0 0 0
1029 /* root splitted */
1030 struct rtree_page *new_root
1031 0 = rtree_page_alloc(tree);
1032 0 rtree_page_init_with_pages(tree, new_root,
1033 tree->root, p);
1034 0 tree->root = new_root;
1035 0 tree->height++;
1036 0 tree->n_pages++;
1037 }
1038 }
1039 0 level--;
1040 0 struct rtree_page *next = get_next_reinsert_page(tree, pg);
1041 0 rtree_page_free(tree, pg);
1042 0 tree->n_pages--;
1043 0 pg = next;
1044 }
1045 2 ▶ if (tree->root->n == 1 && tree->height > 1) {
Branch: 2 branches
BranchTrueFalseTotal
if (tree->root->n == 1 && tree->height > 1) { 1 1 2
if (tree->root->n == 1 && tree->height > 1) { 0 1 1
1046 struct rtree_page_branch *b;
1047 0 b = rtree_branch_get(tree, tree->root, 0);
1048 0 struct rtree_page *new_root = b->data.page;
1049 0 rtree_page_free(tree, tree->root);
1050 0 tree->root = new_root;
1051 0 tree->height--;
1052 0 tree->n_pages--;
1053 }
1054 2 tree->n_records--;
1055 2 tree->version++;
1056 2 return true;
1057 }
1058  
1059 bool
1060 19 rtree_search(const struct rtree *tree, const struct rtree_rect *rect,
1061 enum spatial_search_op op, struct rtree_iterator *itr)
1062 {
1063 19 rtree_iterator_reset(itr);
1064 19 ▶ assert(itr->tree == 0 || itr->tree == tree);
Branch: 2 branches
BranchTrueFalseTotal
assert(itr->tree == 0 || itr->tree == tree); 0 19 19
assert(itr->tree == 0 || itr->tree == tree); 0 0 0
1065 19 itr->tree = tree;
1066 19 itr->version = tree->version;
1067 19 rtree_rect_copy(&itr->rect, rect, tree->dimension);
1068 19 itr->op = op;
1069 19 ▶ assert(tree->height <= RTREE_MAX_HEIGHT);
Branch: 1 branch
BranchTrueFalseTotal
assert(tree->height <= RTREE_MAX_HEIGHT); 0 19 19
1070 19 switch (op) {
1071 14 case SOP_ALL:
1072 14 itr->intr_cmp = itr->leaf_cmp = rtree_always_true;
1073 14 break;
1074 0 case SOP_EQUALS:
1075 0 itr->intr_cmp = rtree_rect_in_rect;
1076 0 itr->leaf_cmp = rtree_rect_equal_to_rect;
1077 0 break;
1078 0 case SOP_CONTAINS:
1079 0 itr->intr_cmp = itr->leaf_cmp = rtree_rect_in_rect;
1080 0 break;
1081 0 case SOP_STRICT_CONTAINS:
1082 0 itr->intr_cmp = itr->leaf_cmp = rtree_rect_strict_in_rect;
1083 0 break;
1084 2 case SOP_OVERLAPS:
1085 2 itr->intr_cmp = itr->leaf_cmp = rtree_rect_intersects_rect;
1086 2 break;
1087 1 case SOP_BELONGS:
1088 1 itr->intr_cmp = rtree_rect_intersects_rect;
1089 1 itr->leaf_cmp = rtree_rect_holds_rect;
1090 1 break;
1091 1 case SOP_STRICT_BELONGS:
1092 1 itr->intr_cmp = rtree_rect_intersects_rect;
1093 1 itr->leaf_cmp = rtree_rect_strict_holds_rect;
1094 1 break;
1095 1 case SOP_NEIGHBOR:
1096 1 ▶ if (tree->root) {
Branch: 1 branch
BranchTrueFalseTotal
if (tree->root) { 1 0 1
1097 struct rtree_rect cover;
1098 1 rtree_page_cover(tree, tree->root, &cover);
1099 sq_coord_t distance;
1100 1 ▶ if (tree->distance_type == RTREE_EUCLID)
Branch: 1 branch
BranchTrueFalseTotal
if (tree->distance_type == RTREE_EUCLID) 1 0 1
1101 distance =
1102 1 rtree_rect_neigh_distance2(&cover, rect,
1103 1 tree->dimension);
1104 else
1105 distance =
1106 0 rtree_rect_neigh_distance(&cover, rect,
1107 0 tree->dimension);
1108 struct rtree_neighbor *n =
1109 1 rtree_iterator_new_neighbor(itr, tree->root,
1110 distance,
1111 1 tree->height);
1112 1 rtnt_insert(&itr->neigh_tree, n);
1113 1 return true;
1114 } else {
1115 0 return false;
1116 }
1117 }
1118 18 ▶ if (tree->root && rtree_iterator_goto_first(itr, 0, tree->root)) {
Branch: 2 branches
BranchTrueFalseTotal
if (tree->root && rtree_iterator_goto_first(itr, 0, tree->root)) { 10 8 18
if (tree->root && rtree_iterator_goto_first(itr, 0, tree->root)) { 10 0 10
1119 10 itr->stack[tree->height-1].pos -= 1;
1120 /* will be incremented by goto_next */
1121 10 itr->eof = false;
1122 10 return true;
1123 } else {
1124 8 itr->eof = true;
1125 8 return false;
1126 }
1127 }
1128  
1129 void
1130 14 rtree_purge(struct rtree *tree)
1131 {
1132 14 ▶ if (tree->root != NULL) {
Branch: 1 branch
BranchTrueFalseTotal
if (tree->root != NULL) { 6 8 14
1133 6 rtree_page_purge(tree, tree->root, tree->height);
1134 6 tree->root = NULL;
1135 6 tree->n_records = 0;
1136 6 tree->n_pages = 0;
1137 6 tree->height = 0;
1138 }
1139 14 }
1140  
1141 size_t
1142 0 rtree_used_size(const struct rtree *tree)
1143 {
1144 0 return tree->n_pages * tree->page_size;
1145 }
1146  
1147 unsigned
1148 0 rtree_number_of_records(const struct rtree *tree) {
1149 0 return tree->n_records;
1150 }
1151  
1152 #if 0
1153 #include <stdio.h>
1154 void
1155 rtree_debug_print_page(const struct rtree *tree, const struct rtree_page *page,
1156 unsigned level, unsigned path)
1157 {
1158 printf("%d:\n", path);
1159 unsigned d = tree->dimension;
1160 for (int i = 0; i < page->n; i++) {
1161 struct rtree_page_branch *b;
1162 b = rtree_branch_get(tree, page, i);
1163 double v = 1;
1164 for (unsigned j = 0; j < d; j++) {
1165 double d1 = b->rect.coords[j * 2];
1166 double d2 = b->rect.coords[j * 2 + 1];
1167 v *= (d2 - d1) / 100;
1168 printf("[%04.1lf-%04.1lf:%04.1lf]", d2, d1, d2 - d1);
1169 }
1170 printf("%d\n", (int)(v * 100));
1171 }
1172 if (--level > 1) {
1173 for (int i = 0; i < page->n; i++) {
1174 struct rtree_page_branch *b;
1175 b = rtree_branch_get(tree, page, i);
1176 rtree_debug_print_page(tree, b->data.page, level,
1177 path * 100 + i + 1);
1178 }
1179 }
1180 }
1181  
1182 void
1183 rtree_debug_print(const struct rtree *tree)
1184 {
1185 if (tree->root)
1186 rtree_debug_print_page(tree, tree->root, tree->height, 1);
1187 }
1188 #endif
1189  
« matras.c ↑ Summary R.xs »