| 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
| Branch | True | False | Total |
| return a->distance < b->distance ? -1 : |
1550 |
727 |
2277 |
|
| 82 |
940 |
▶ | a->distance > b->distance ? 1 : |
Branch: 1 branch
| Branch | True | False | Total |
| a->distance > b->distance ? 1 : |
514 |
213 |
727 |
|
| 83 |
426 |
▶ | a->level < b->level ? -1 : |
Branch: 1 branch
| Branch | True | False | Total |
| a->level < b->level ? -1 : |
213 |
0 |
213 |
|
| 84 |
426 |
▶ | a->level > b->level ? 1 : |
Branch: 1 branch
| Branch | True | False | Total |
| a->level > b->level ? 1 : |
213 |
0 |
213 |
|
| 85 |
213 |
▶ | a < b ? -1 : a > b ? 1 : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| } 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| } 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (int i = dimension * 2; --i >= 0; ) |
0 |
0 |
0 |
|
| 323 |
0 |
▶ | if (rt1->coords[i] != rt2->coords[i]) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (unsigned a = 0; a < d; a++) { |
12240 |
6120 |
18360 |
|
| 458 |
318240 |
▶ | for (unsigned i = 0; i < n - 1; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| (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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (unsigned i = 0, j = 0; j < page->n; j++) { |
153000 |
6120 |
159120 |
|
| 566 |
153000 |
▶ | if (taken[j] == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| assert(incr >= 0); |
0 |
4518945 |
4518945 |
|
| 633 |
4518945 |
▶ | if (i == 0 || incr < min_incr || (incr == min_incr && r_area < best_area)) { |
Branch: 4 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (--level != 0) { |
0 |
3 |
3 |
|
| 672 |
0 |
▶ | for (unsigned i = 0; i < page->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (sp + 1 == itr->tree->height) { |
5791 |
362 |
6153 |
|
| 729 |
5792 |
▶ | for (unsigned i = 0, n = pg->n; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (itr->intr_cmp(&itr->rect, &b->rect, d) |
362 |
20 |
382 |
|
| 743 |
362 |
▶ | && rtree_iterator_goto_first(itr, sp + 1, |
Branch: 1 branch
| Branch | True | False | Total |
| && 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (itr->intr_cmp(&itr->rect, &b->rect, d) |
5781 |
11 |
5792 |
|
| 775 |
5781 |
▶ | && rtree_iterator_goto_first(itr, sp + 1, |
Branch: 1 branch
| Branch | True | False | Total |
| && 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| while (pg != NULL) { |
0 |
2 |
2 |
|
| 1021 |
0 |
▶ | for (int i = 0, n = pg->n; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |
|
| |