Line data Source code
1 : /******************************************************************************
2 : *
3 : * Purpose: Bulk loading of SQLite R*Tree tables
4 : * Author: Even Rouault <even dot rouault at spatialys dot com>
5 : *
6 : ******************************************************************************
7 : * Copyright (c) 2020- 2023 Joshua J Baker
8 : * Copyright (c) 2023, Even Rouault <even dot rouault at spatialys dot com>
9 : *
10 : * Permission is hereby granted, free of charge, to any person obtaining a
11 : * copy of this software and associated documentation files (the "Software"),
12 : * to deal in the Software without restriction, including without limitation
13 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 : * and/or sell copies of the Software, and to permit persons to whom the
15 : * Software is furnished to do so, subject to the following conditions:
16 : *
17 : * The above copyright notice and this permission notice shall be included
18 : * in all copies or substantial portions of the Software.
19 : *
20 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
21 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 : * DEALINGS IN THE SOFTWARE.
27 : ****************************************************************************/
28 :
29 : #ifndef __STDC_FORMAT_MACROS
30 : #define __STDC_FORMAT_MACROS
31 : #endif
32 :
33 : #include "sqlite_rtree_bulk_load.h"
34 :
35 : #include <assert.h>
36 : #include <inttypes.h>
37 : #include <math.h>
38 : #include <stdbool.h>
39 : #include <stdio.h>
40 : #include <string.h>
41 :
42 : #if defined(__cplusplus) && !defined(DISABLE_CPLUSPLUS)
43 : #define USE_CPLUSPLUS
44 : #endif
45 :
46 : #ifdef USE_CPLUSPLUS
47 : #include <algorithm>
48 : #else
49 : #include <stdlib.h>
50 : #endif
51 :
52 : #ifdef __cplusplus
53 : #define STATIC_CAST(type, value) static_cast<type>(value)
54 : #ifdef NULL
55 : #undef NULL
56 : #endif
57 : #define NULL nullptr
58 : #undef SQLITE_STATIC
59 : #define SQLITE_STATIC STATIC_CAST(sqlite3_destructor_type, nullptr)
60 : #else
61 : #define STATIC_CAST(type, value) (type)(value)
62 : #endif
63 :
64 : ////////////////////////////////
65 :
66 : #define DATATYPE int64_t
67 : #define DIMS 2
68 : #define NUMTYPE float
69 :
70 : // Cf https://github.com/sqlite/sqlite/blob/90e4a3b7fcdf63035d6f35eb44d11ff58ff4b068/ext/rtree/rtree.c#L262
71 : #define MAXITEMS 51
72 :
73 : #define BYTES_PER_CELL STATIC_CAST(int, sizeof(int64_t) + 4 * sizeof(float))
74 :
75 : //#ifndef RTREE_NOPATHHINT
76 : //#define USE_PATHHINT
77 : //#endif
78 :
79 : enum kind {
80 : LEAF = 1,
81 : BRANCH = 2,
82 : };
83 :
84 : struct rect {
85 : NUMTYPE min[DIMS];
86 : NUMTYPE max[DIMS];
87 : };
88 :
89 : struct item {
90 : DATATYPE data;
91 : };
92 :
93 : struct node {
94 : enum kind kind; // LEAF or BRANCH
95 : int count; // number of rects
96 : struct rect rects[MAXITEMS];
97 : union {
98 : struct node *nodes[MAXITEMS];
99 : struct item datas[MAXITEMS];
100 : };
101 : };
102 :
103 : struct node_MAXITEMS_plus_ONE {
104 : enum kind kind; // LEAF or BRANCH
105 : int count; // number of rects
106 : struct rect rects[MAXITEMS+1];
107 : union {
108 : struct node *nodes[MAXITEMS+1];
109 : struct item datas[MAXITEMS+1];
110 : };
111 : };
112 :
113 : struct sqlite_rtree_bl {
114 : struct rect rect;
115 : struct node *root;
116 : size_t count;
117 : size_t mem_usage;
118 : int height;
119 : int node_size;
120 : int node_capacity;
121 : #ifdef USE_PATHHINT
122 : int path_hint[16];
123 : #endif
124 : void *(*malloc)(size_t);
125 : void (*free)(void *);
126 : };
127 :
128 : #if defined(__GNUC__) && __GNUC__ >= 4
129 : #define CPL_UNUSED __attribute((__unused__))
130 : #else
131 : #define CPL_UNUSED
132 : #endif
133 :
134 2048 : static void CPL_IGNORE_RET_VAL_INT(CPL_UNUSED int v) {
135 : (void)v;
136 2048 : }
137 :
138 67018400 : static inline NUMTYPE min0(NUMTYPE x, NUMTYPE y) {
139 67018400 : return x < y ? x : y;
140 : }
141 :
142 67018400 : static inline NUMTYPE max0(NUMTYPE x, NUMTYPE y) {
143 67018400 : return x > y ? x : y;
144 : }
145 :
146 9702 : static struct node *node_new(struct sqlite_rtree_bl *tr, enum kind kind) {
147 9702 : struct node *node = STATIC_CAST(struct node *, tr->malloc(sizeof(struct node)));
148 9702 : if (!node) {
149 0 : return NULL;
150 : }
151 9702 : memset(node, 0, sizeof(struct node));
152 9702 : node->kind = kind;
153 9702 : tr->mem_usage += sizeof(struct node);
154 9702 : return node;
155 : }
156 :
157 9702 : static void node_free(struct sqlite_rtree_bl *tr, struct node *node) {
158 9702 : if (node->kind == BRANCH) {
159 9652 : for (int i = 0; i < node->count; i++) {
160 9294 : node_free(tr, node->nodes[i]);
161 : }
162 : }
163 9702 : tr->mem_usage -= sizeof(struct node);
164 9702 : tr->free(node);
165 9702 : }
166 :
167 18774400 : static void rect_expand(struct rect *rect, const struct rect *other) {
168 56323300 : for (int i = 0; i < DIMS; i++) {
169 37548900 : rect->min[i] = min0(rect->min[i], other->min[i]);
170 37548900 : rect->max[i] = max0(rect->max[i], other->max[i]);
171 : }
172 18774400 : }
173 :
174 15262300 : static double rect_area(const struct rect *rect) {
175 15262300 : double result = 1;
176 45787000 : for (int i = 0; i < DIMS; i++) {
177 30524700 : result *= STATIC_CAST(double, rect->max[i]) - rect->min[i];
178 : }
179 15262300 : return result;
180 : }
181 :
182 : // return the area of two rects expanded
183 14558600 : static double rect_unioned_area(const struct rect *rect,
184 : const struct rect *other) {
185 14558600 : double result = 1;
186 43675700 : for (int i = 0; i < DIMS; i++) {
187 29117100 : result *= STATIC_CAST(double, max0(rect->max[i], other->max[i])) -
188 29117100 : min0(rect->min[i], other->min[i]);
189 : }
190 14558600 : return result;
191 : }
192 :
193 14560600 : static bool rect_contains(const struct rect *rect, const struct rect *other) {
194 14562200 : for (int i = 0; i < DIMS; i++) {
195 14561700 : if (other->min[i] < rect->min[i])
196 61751 : return false;
197 14500000 : if (other->max[i] > rect->max[i])
198 14498400 : return false;
199 : }
200 460 : return true;
201 : }
202 :
203 703304 : static double rect_margin(const struct rect *rect) {
204 703304 : return (STATIC_CAST(double, rect->max[0]) - rect->min[0]) +
205 703304 : (STATIC_CAST(double, rect->max[1]) - rect->min[1]);
206 : }
207 :
208 351652 : static double rect_overlap(const struct rect *rect1, const struct rect *rect2) {
209 351652 : double overlap = 1;
210 353152 : for (int idim = 0; idim < DIMS; ++idim)
211 : {
212 352404 : double minv = max0(rect1->min[idim], rect2->min[idim]);
213 352404 : double maxv = min0(rect1->max[idim], rect2->max[idim]);
214 352404 : if( maxv < minv ) {
215 350904 : return 0;
216 : }
217 1500 : overlap *= (maxv - minv);
218 : }
219 748 : return overlap;
220 : }
221 :
222 : typedef struct SortType
223 : {
224 : int i;
225 : #ifndef USE_CPLUSPLUS
226 : struct rect* rects;
227 : #endif
228 : } SortType;
229 :
230 : #ifndef USE_CPLUSPLUS
231 : static int CompareAxis0(const void *a, const void *b)
232 : {
233 : const SortType* sa = STATIC_CAST(const SortType*, a);
234 : const SortType* sb = STATIC_CAST(const SortType*, b);
235 : if (sa->rects[sa->i].min[0] < sb->rects[sb->i].min[0])
236 : return -1;
237 : if (sa->rects[sa->i].min[0] == sb->rects[sb->i].min[0])
238 : {
239 : if (sa->rects[sa->i].max[0] < sb->rects[sb->i].max[0])
240 : return -1;
241 : if (sa->rects[sa->i].max[0] == sb->rects[sb->i].max[0])
242 : return 0;
243 : return 1;
244 : }
245 : return 1;
246 : }
247 :
248 : static int CompareAxis1(const void *a, const void *b)
249 : {
250 : const SortType* sa = STATIC_CAST(const SortType*, a);
251 : const SortType* sb = STATIC_CAST(const SortType*, b);
252 : if (sa->rects[sa->i].min[1] < sb->rects[sb->i].min[1])
253 : return -1;
254 : if (sa->rects[sa->i].min[1] == sb->rects[sb->i].min[1])
255 : {
256 : if (sa->rects[sa->i].max[1] < sb->rects[sb->i].max[1])
257 : return -1;
258 : if (sa->rects[sa->i].max[1] == sb->rects[sb->i].max[1])
259 : return 0;
260 : return 1;
261 : }
262 : return 1;
263 : }
264 : #endif
265 :
266 : // Implementation of the R*-tree variant of SplitNode from Beckman[1990].
267 : // Cf https://github.com/sqlite/sqlite/blob/5f53f85e22df1c5e1e36106b5e4d1db5089519aa/ext/rtree/rtree.c#L2418
268 9254 : static bool node_split_rstartree(struct sqlite_rtree_bl *tr,
269 : struct node *node,
270 : const struct rect *extraRect,
271 : struct item extraData,
272 : struct node *extraNode,
273 : struct node **right_out) {
274 : struct node_MAXITEMS_plus_ONE nodeOri;
275 9254 : nodeOri.kind = node->kind;
276 9254 : nodeOri.count = node->count;
277 9254 : memcpy(nodeOri.rects, node->rects, node->count * sizeof(struct rect));
278 9254 : nodeOri.rects[node->count] = *extraRect;
279 9254 : if (nodeOri.kind == LEAF) {
280 8936 : memcpy(nodeOri.datas, node->datas, node->count * sizeof(struct item));
281 8936 : nodeOri.datas[nodeOri.count] = extraData;
282 : } else {
283 318 : memcpy(nodeOri.nodes, node->nodes, node->count * sizeof(struct node*));
284 318 : nodeOri.nodes[nodeOri.count] = extraNode;
285 : }
286 9254 : nodeOri.count ++;
287 9254 : assert(nodeOri.count == tr->node_capacity + 1);
288 :
289 : SortType aSorted[DIMS][MAXITEMS+1];
290 27762 : for (int idim = 0; idim < DIMS; ++idim) {
291 980924 : for (int i = 0; i < tr->node_capacity + 1; ++i) {
292 962416 : aSorted[idim][i].i = i;
293 : #ifndef USE_CPLUSPLUS
294 : aSorted[idim][i].rects = nodeOri.rects;
295 : #endif
296 : }
297 : }
298 :
299 : #ifndef USE_CPLUSPLUS
300 : qsort(aSorted[0], nodeOri.count, sizeof(SortType), CompareAxis0);
301 : qsort(aSorted[1], nodeOri.count, sizeof(SortType), CompareAxis1);
302 : #else
303 9254 : std::sort(aSorted[0], aSorted[0] + nodeOri.count, [&nodeOri](const SortType& a, const SortType& b) {
304 3053540 : return nodeOri.rects[a.i].min[0] < nodeOri.rects[b.i].min[0] ||
305 714325 : (nodeOri.rects[a.i].min[0] == nodeOri.rects[b.i].min[0] &&
306 2340730 : nodeOri.rects[a.i].max[0] < nodeOri.rects[b.i].max[0]);
307 : });
308 9254 : std::sort(aSorted[1], aSorted[1] + nodeOri.count, [&nodeOri](const SortType& a, const SortType& b) {
309 3052780 : return nodeOri.rects[a.i].min[1] < nodeOri.rects[b.i].min[1] ||
310 714574 : (nodeOri.rects[a.i].min[1] == nodeOri.rects[b.i].min[1] &&
311 2339890 : nodeOri.rects[a.i].max[1] < nodeOri.rects[b.i].max[1]);
312 : });
313 : #endif
314 :
315 9254 : int iBestDim = 0;
316 9254 : int iBestSplit = tr->node_capacity / 2;
317 9254 : double fBestMargin = INFINITY;
318 27762 : for (int idim = 0; idim < DIMS; ++idim) {
319 18508 : double margin = 0;
320 18508 : double fBestOverlap = INFINITY;
321 18508 : double fBestArea = INFINITY;
322 18508 : int iBestLeft = 0;
323 18508 : const int minItems = tr->node_capacity / 3;
324 370160 : for (int nLeft = minItems; nLeft <= nodeOri.count - minItems; ++nLeft) {
325 351652 : struct rect rectLeft = nodeOri.rects[aSorted[idim][0].i];
326 351652 : struct rect rectRight = nodeOri.rects[aSorted[idim][nodeOri.count-1].i];
327 17934300 : for(int kk=1; kk<(nodeOri.count-1); kk++) {
328 17582600 : if( kk<nLeft ){
329 8791300 : rect_expand(&rectLeft, &nodeOri.rects[aSorted[idim][kk].i]);
330 : }else{
331 8791300 : rect_expand(&rectRight, &nodeOri.rects[aSorted[idim][kk].i]);
332 : }
333 : }
334 351652 : margin += rect_margin(&rectLeft);
335 351652 : margin += rect_margin(&rectRight);
336 351652 : double overlap = rect_overlap(&rectLeft, &rectRight);
337 351652 : double area = rect_area(&rectLeft) + rect_area(&rectRight);
338 351652 : if( overlap<fBestOverlap || (overlap==fBestOverlap && area<fBestArea)) {
339 184780 : iBestLeft = nLeft;
340 184780 : fBestOverlap = overlap;
341 184780 : fBestArea = area;
342 : }
343 : }
344 :
345 18508 : if (margin<fBestMargin) {
346 9262 : iBestDim = idim;
347 9262 : fBestMargin = margin;
348 9262 : iBestSplit = iBestLeft;
349 : }
350 : }
351 :
352 9254 : struct node *right = node_new(tr, node->kind);
353 9254 : if (!right) {
354 0 : return false;
355 : }
356 9254 : node->count = 0;
357 9254 : int i = 0;
358 249798 : for (; i < iBestSplit; ++i) {
359 240544 : struct node* target = node;
360 240544 : target->rects[target->count] = nodeOri.rects[aSorted[iBestDim][i].i];
361 240544 : if (nodeOri.kind == LEAF) {
362 232276 : target->datas[target->count] = nodeOri.datas[aSorted[iBestDim][i].i];
363 : } else {
364 8268 : target->nodes[target->count] = nodeOri.nodes[aSorted[iBestDim][i].i];
365 : }
366 240544 : ++target->count;
367 : }
368 249918 : for (; i < nodeOri.count; ++i) {
369 240664 : struct node* target = right;
370 240664 : target->rects[target->count] = nodeOri.rects[aSorted[iBestDim][i].i];
371 240664 : if (nodeOri.kind == LEAF) {
372 232396 : target->datas[target->count] = nodeOri.datas[aSorted[iBestDim][i].i];
373 : } else {
374 8268 : target->nodes[target->count] = nodeOri.nodes[aSorted[iBestDim][i].i];
375 : }
376 240664 : ++target->count;
377 : }
378 9254 : *right_out = right;
379 9254 : return true;
380 : }
381 :
382 502871 : static int node_choose_least_enlargement(const struct node *node,
383 : const struct rect *ir) {
384 502871 : int j = 0;
385 502871 : double jenlarge = INFINITY;
386 502871 : double minarea = 0;
387 15061400 : for (int i = 0; i < node->count; i++) {
388 : // calculate the enlarged area
389 14558600 : double uarea = rect_unioned_area(&node->rects[i], ir);
390 14558600 : double area = rect_area(&node->rects[i]);
391 14558600 : double enlarge = uarea - area;
392 14558600 : if (enlarge < jenlarge || (enlarge == jenlarge && area < minarea)) {
393 14501100 : j = i;
394 14501100 : jenlarge = enlarge;
395 14501100 : minarea = area;
396 : }
397 : }
398 502871 : return j;
399 : }
400 :
401 503309 : static int node_choose(struct sqlite_rtree_bl * tr,
402 : const struct node *node,
403 : const struct rect *rect,
404 : int depth)
405 : {
406 : #ifndef USE_PATHHINT
407 : (void)tr;
408 : (void)depth;
409 : #endif
410 :
411 : #ifdef USE_PATHHINT
412 : int h = tr->path_hint[depth];
413 : if (h < node->count) {
414 : if (rect_contains(&node->rects[h], rect)) {
415 : return h;
416 : }
417 : }
418 : #endif
419 :
420 : // Take a quick look for the first node that contain the rect.
421 503309 : int iBestIndex = -1;
422 503309 : double minArea = INFINITY;
423 15063900 : for (int i = 0; i < node->count; i++) {
424 14560600 : if (rect_contains(&node->rects[i], rect)) {
425 460 : double area = rect_area(&node->rects[i]);
426 460 : if( area < minArea )
427 : {
428 456 : iBestIndex = i;
429 456 : minArea = area;
430 : }
431 : }
432 : }
433 503309 : if (iBestIndex >= 0) {
434 : #ifdef USE_PATHHINT
435 : tr->path_hint[depth] = iBestIndex;
436 : #endif
437 438 : return iBestIndex;
438 : }
439 :
440 : // Fallback to using che "choose least enlargement" algorithm.
441 502871 : int i = node_choose_least_enlargement(node, rect);
442 : #ifdef USE_PATHHINT
443 : tr->path_hint[depth] = i;
444 : #endif
445 502871 : return i;
446 : }
447 :
448 18508 : static struct rect node_rect_calc(const struct node *node) {
449 18508 : struct rect rect = node->rects[0];
450 481208 : for (int i = 1; i < node->count; i++) {
451 462700 : rect_expand(&rect, &node->rects[i]);
452 : }
453 18508 : return rect;
454 : }
455 :
456 : // node_insert returns false if out of memory
457 738390 : static bool node_insert(struct sqlite_rtree_bl *tr,
458 : struct node *node,
459 : const struct rect *ir,
460 : struct item item,
461 : int depth,
462 : bool *split,
463 : struct rect *rectToInsert,
464 : struct item *itemToInsert,
465 : struct node** nodeToInsert)
466 : {
467 738390 : if (node->kind == LEAF) {
468 235081 : if (node->count == tr->node_capacity) {
469 8936 : *split = true;
470 8936 : *rectToInsert = *ir;
471 8936 : *itemToInsert = item;
472 8936 : *nodeToInsert = NULL;
473 8936 : return true;
474 : }
475 226145 : int index = node->count;
476 226145 : node->rects[index] = *ir;
477 226145 : node->datas[index] = item;
478 226145 : node->count++;
479 226145 : *split = false;
480 226145 : return true;
481 : }
482 : // Choose a subtree for inserting the rectangle.
483 503309 : const int i = node_choose(tr, node, ir, depth);
484 503309 : if (!node_insert(tr, node->nodes[i], ir, item, depth+1,
485 : split, rectToInsert, itemToInsert, nodeToInsert))
486 : {
487 0 : return false;
488 : }
489 503309 : if (!*split) {
490 494095 : rect_expand(&node->rects[i], ir);
491 494095 : *split = false;
492 494095 : return true;
493 : }
494 :
495 : struct node *right;
496 9214 : if (!node_split_rstartree(tr, node->nodes[i], rectToInsert,
497 : *itemToInsert, *nodeToInsert, &right)) {
498 0 : return false;
499 : }
500 9214 : node->rects[i] = node_rect_calc(node->nodes[i]);
501 :
502 : // split the child node
503 9214 : if (node->count == tr->node_capacity) {
504 318 : *split = true;
505 318 : *rectToInsert = node_rect_calc(right);
506 318 : *nodeToInsert = right;
507 318 : itemToInsert->data = -1;
508 318 : return true;
509 : }
510 :
511 8896 : *split = false;
512 8896 : node->rects[node->count] = node_rect_calc(right);
513 8896 : node->nodes[node->count] = right;
514 8896 : node->count++;
515 8896 : return true;
516 : }
517 :
518 : static
519 592 : struct sqlite_rtree_bl *sqlite_rtree_bl_new_with_allocator(int sqlite_page_size,
520 : void *(*pfnMalloc)(size_t),
521 : void (*pfnFree)(void*)) {
522 592 : if (!pfnMalloc)
523 592 : pfnMalloc = malloc;
524 592 : if (!pfnFree)
525 592 : pfnFree = free;
526 592 : struct sqlite_rtree_bl *tr = STATIC_CAST(struct sqlite_rtree_bl *, pfnMalloc(sizeof(struct sqlite_rtree_bl)));
527 592 : if (!tr) return NULL;
528 592 : memset(tr, 0, sizeof(struct sqlite_rtree_bl));
529 592 : tr->malloc = pfnMalloc;
530 592 : tr->free = pfnFree;
531 :
532 : // Cf https://github.com/sqlite/sqlite/blob/90e4a3b7fcdf63035d6f35eb44d11ff58ff4b068/ext/rtree/rtree.c#L3541
533 592 : tr->node_size = sqlite_page_size-64;
534 592 : if( tr->node_size > 4+BYTES_PER_CELL*MAXITEMS ){
535 592 : tr->node_size = 4+BYTES_PER_CELL*MAXITEMS;
536 : }
537 592 : tr->node_capacity = (tr->node_size-4)/BYTES_PER_CELL;
538 592 : tr->mem_usage = sizeof(struct sqlite_rtree_bl);
539 :
540 592 : return tr;
541 : }
542 :
543 592 : struct sqlite_rtree_bl *SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_new)(int sqlite_page_size) {
544 592 : return sqlite_rtree_bl_new_with_allocator(sqlite_page_size, NULL, NULL);
545 : }
546 :
547 : // Cf https://github.com/sqlite/sqlite/blob/90e4a3b7fcdf63035d6f35eb44d11ff58ff4b068/ext/rtree/rtree.c#L2993C1-L2995C3
548 : /*
549 : ** Rounding constants for float->double conversion.
550 : */
551 : #define RNDTOWARDS (1.0 - 1.0/8388608.0) /* Round towards zero */
552 : #define RNDAWAY (1.0 + 1.0/8388608.0) /* Round away from zero */
553 :
554 : /*
555 : ** Convert an sqlite3_value into an RtreeValue (presumably a float)
556 : ** while taking care to round toward negative or positive, respectively.
557 : */
558 470162 : static float rtreeValueDown(double d){
559 470162 : float f = STATIC_CAST(float, d);
560 470162 : if( f>d ){
561 10038 : f = STATIC_CAST(float, d*(d<0 ? RNDAWAY : RNDTOWARDS));
562 : }
563 470162 : return f;
564 : }
565 470162 : static float rtreeValueUp(double d){
566 470162 : float f = STATIC_CAST(float, d);
567 470162 : if( f<d ){
568 10031 : f = STATIC_CAST(float, d*(d<0 ? RNDTOWARDS : RNDAWAY));
569 : }
570 470162 : return f;
571 : }
572 :
573 235081 : bool SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_insert)(struct sqlite_rtree_bl *tr,
574 : int64_t fid,
575 : double minx, double miny,
576 : double maxx, double maxy)
577 : {
578 235081 : if( !(minx <= maxx) || !(miny <= maxy) )
579 0 : return false;
580 :
581 : // copy input rect
582 : struct rect rect;
583 235081 : rect.min[0] = rtreeValueDown(minx);
584 235081 : rect.min[1] = rtreeValueDown(miny);
585 235081 : rect.max[0] = rtreeValueUp(maxx);
586 235081 : rect.max[1] = rtreeValueUp(maxy);
587 :
588 : // copy input data
589 : struct item item;
590 235081 : item.data = fid;
591 :
592 : struct rect rectToInsert;
593 : struct item itemToInsert;
594 : struct node* nodeToInsert;
595 :
596 235081 : if (!tr->root) {
597 408 : struct node *new_root = node_new(tr, LEAF);
598 408 : if (!new_root) {
599 0 : return false;
600 : }
601 408 : tr->root = new_root;
602 408 : tr->rect = rect;
603 408 : tr->height = 1;
604 : }
605 235081 : bool split = false;
606 235081 : if (!node_insert(tr, tr->root, &rect, item, 0,
607 : &split, &rectToInsert, &itemToInsert, &nodeToInsert)) {
608 0 : return false;
609 : }
610 235081 : if (!split) {
611 235041 : rect_expand(&tr->rect, &rect);
612 235041 : tr->count++;
613 235041 : return true;
614 : }
615 40 : struct node *new_root = node_new(tr, BRANCH);
616 40 : if (!new_root) {
617 0 : return false;
618 : }
619 : struct node *right;
620 40 : if (!node_split_rstartree(tr, tr->root, &rectToInsert, itemToInsert, nodeToInsert, &right)) {
621 0 : tr->free(new_root);
622 0 : return false;
623 : }
624 40 : new_root->rects[0] = node_rect_calc(tr->root);
625 40 : new_root->rects[1] = node_rect_calc(right);
626 40 : new_root->nodes[0] = tr->root;
627 40 : new_root->nodes[1] = right;
628 40 : tr->root = new_root;
629 40 : tr->root->count = 2;
630 40 : tr->height++;
631 :
632 40 : return true;
633 : }
634 :
635 235089 : size_t SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_ram_usage)(const sqlite_rtree_bl* tr) {
636 235089 : return tr->mem_usage;
637 : }
638 :
639 592 : void SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_free)(struct sqlite_rtree_bl *tr) {
640 592 : if (tr) {
641 592 : if (tr->root) {
642 408 : node_free(tr, tr->root);
643 : }
644 592 : tr->free(tr);
645 : }
646 592 : }
647 :
648 19332 : static void write_be_uint16(uint8_t* dest, uint16_t n) {
649 19332 : dest[0] = STATIC_CAST(uint8_t, n >> 8);
650 19332 : dest[1] = STATIC_CAST(uint8_t, n);
651 19332 : }
652 :
653 244015 : static void write_be_int64(uint8_t* dest, int64_t i) {
654 244015 : const uint64_t n = i;
655 244015 : dest[0] = STATIC_CAST(uint8_t, n >> 56);
656 244015 : dest[1] = STATIC_CAST(uint8_t, n >> 48);
657 244015 : dest[2] = STATIC_CAST(uint8_t, n >> 40);
658 244015 : dest[3] = STATIC_CAST(uint8_t, n >> 32);
659 244015 : dest[4] = STATIC_CAST(uint8_t, n >> 24);
660 244015 : dest[5] = STATIC_CAST(uint8_t, n >> 16);
661 244015 : dest[6] = STATIC_CAST(uint8_t, n >> 8);
662 244015 : dest[7] = STATIC_CAST(uint8_t, n);
663 244015 : }
664 :
665 976060 : static void write_be_float(uint8_t* dest, float f) {
666 : uint32_t n;
667 976060 : memcpy(&n, &f, sizeof(float));
668 976060 : dest[0] = STATIC_CAST(uint8_t, n >> 24);
669 976060 : dest[1] = STATIC_CAST(uint8_t, n >> 16);
670 976060 : dest[2] = STATIC_CAST(uint8_t, n >> 8);
671 976060 : dest[3] = STATIC_CAST(uint8_t, n);
672 976060 : }
673 :
674 0 : static char* my_sqlite3_strdup(const char* s) {
675 0 : if( !s )
676 0 : return NULL;
677 0 : const int n = STATIC_CAST(int, strlen(s));
678 0 : char* new_s = STATIC_CAST(char*, sqlite3_malloc(n+1));
679 0 : memcpy(new_s, s, n+1);
680 0 : return new_s;
681 : }
682 :
683 : typedef struct rtree_insert_context
684 : {
685 : sqlite3* hDB;
686 : sqlite3_stmt* hStmtNode;
687 : sqlite3_stmt* hStmtParent;
688 : sqlite3_stmt* hStmtRowid;
689 : int node_capacity;
690 : int tree_height;
691 : char** p_error_msg;
692 : } rtree_insert_context;
693 :
694 : typedef enum
695 : {
696 : PASS_ALL,
697 : PASS_NODE,
698 : PASS_PARENT,
699 : PASS_ROWID,
700 : } PassType;
701 :
702 28998 : static bool insert_into_db(const struct rtree_insert_context* ctxt,
703 : const struct node* node,
704 : int64_t* p_cur_nodeno,
705 : int64_t parent_nodeno,
706 : PassType pass) {
707 28998 : const int64_t this_cur_nodeno = (*p_cur_nodeno);
708 28998 : uint8_t blob[4 + MAXITEMS * BYTES_PER_CELL] = {0};
709 28998 : size_t offset = 4;
710 :
711 28998 : if (node->kind == BRANCH) {
712 28956 : for (int i = 0; i < node->count; ++i) {
713 27882 : ++(*p_cur_nodeno);
714 :
715 27882 : if (pass == PASS_ALL || pass == PASS_NODE) {
716 9294 : write_be_int64(blob + offset, (*p_cur_nodeno));
717 9294 : offset += sizeof(int64_t);
718 :
719 9294 : const float minx = node->rects[i].min[0];
720 9294 : write_be_float(blob + offset, minx);
721 9294 : offset += sizeof(float);
722 :
723 9294 : const float maxx = node->rects[i].max[0];
724 9294 : write_be_float(blob + offset, maxx);
725 9294 : offset += sizeof(float);
726 :
727 9294 : const float miny = node->rects[i].min[1];
728 9294 : write_be_float(blob + offset, miny);
729 9294 : offset += sizeof(float);
730 :
731 9294 : const float maxy = node->rects[i].max[1];
732 9294 : write_be_float(blob + offset, maxy);
733 9294 : offset += sizeof(float);
734 : }
735 :
736 27882 : if (!insert_into_db(ctxt, node->nodes[i], p_cur_nodeno,
737 : this_cur_nodeno, pass)) {
738 0 : return false;
739 : }
740 : }
741 : }
742 27924 : else if (pass == PASS_ALL || pass == PASS_NODE || pass == PASS_ROWID) {
743 488058 : for (int i = 0; i < node->count; ++i ) {
744 469442 : const int64_t fid = node->datas[i].data;
745 469442 : if( pass == PASS_ALL || pass == PASS_NODE )
746 : {
747 234721 : write_be_int64(blob + offset, fid);
748 234721 : offset += sizeof(int64_t);
749 :
750 234721 : const float minx = node->rects[i].min[0];
751 234721 : write_be_float(blob + offset, minx);
752 234721 : offset += sizeof(float);
753 :
754 234721 : const float maxx = node->rects[i].max[0];
755 234721 : write_be_float(blob + offset, maxx);
756 234721 : offset += sizeof(float);
757 :
758 234721 : const float miny = node->rects[i].min[1];
759 234721 : write_be_float(blob + offset, miny);
760 234721 : offset += sizeof(float);
761 :
762 234721 : const float maxy = node->rects[i].max[1];
763 234721 : write_be_float(blob + offset, maxy);
764 234721 : offset += sizeof(float);
765 : }
766 :
767 469442 : if (pass == PASS_ALL || pass == PASS_ROWID) {
768 234721 : sqlite3_reset(ctxt->hStmtRowid);
769 234721 : sqlite3_bind_int64(ctxt->hStmtRowid, 1, fid);
770 234721 : sqlite3_bind_int64(ctxt->hStmtRowid, 2, this_cur_nodeno);
771 234721 : int ret = sqlite3_step(ctxt->hStmtRowid);
772 234721 : if (ret != SQLITE_OK && ret != SQLITE_DONE) {
773 0 : if (ctxt->p_error_msg) {
774 0 : *ctxt->p_error_msg = my_sqlite3_strdup(sqlite3_errmsg(ctxt->hDB));
775 : }
776 0 : return false;
777 : }
778 : }
779 : }
780 : }
781 :
782 28998 : if (pass == PASS_ALL || pass == PASS_NODE) {
783 9666 : write_be_uint16(blob, STATIC_CAST(uint16_t, parent_nodeno == 0 ? ctxt->tree_height - 1 : 0));
784 9666 : write_be_uint16(blob + 2, STATIC_CAST(uint16_t, node->count));
785 :
786 9666 : sqlite3_reset(ctxt->hStmtNode);
787 9666 : sqlite3_bind_int64(ctxt->hStmtNode, 1, this_cur_nodeno);
788 9666 : sqlite3_bind_blob(ctxt->hStmtNode, 2, blob,
789 9666 : 4 + ctxt->node_capacity * BYTES_PER_CELL,
790 : SQLITE_STATIC);
791 9666 : int ret = sqlite3_step(ctxt->hStmtNode);
792 9666 : if (ret != SQLITE_OK && ret != SQLITE_DONE) {
793 0 : if (ctxt->p_error_msg) {
794 0 : *ctxt->p_error_msg = my_sqlite3_strdup(sqlite3_errmsg(ctxt->hDB));
795 : }
796 0 : return false;
797 : }
798 : }
799 :
800 28998 : if ((pass == PASS_ALL || pass == PASS_PARENT) && parent_nodeno > 0) {
801 9294 : sqlite3_reset(ctxt->hStmtParent);
802 9294 : sqlite3_bind_int64(ctxt->hStmtParent, 1, this_cur_nodeno);
803 9294 : sqlite3_bind_int64(ctxt->hStmtParent, 2, parent_nodeno);
804 9294 : int ret = sqlite3_step(ctxt->hStmtParent);
805 9294 : if (ret != SQLITE_OK && ret != SQLITE_DONE) {
806 0 : if (ctxt->p_error_msg) {
807 0 : *ctxt->p_error_msg = my_sqlite3_strdup(sqlite3_errmsg(ctxt->hDB));
808 : }
809 0 : return false;
810 : }
811 : }
812 :
813 28998 : return true;
814 : }
815 :
816 12788 : static bool IsLowercaseAlpha(const char* s)
817 : {
818 12788 : for (; *s != 0; ++s) {
819 10008 : if (!(*s >= 'a' && *s <= 'z')) {
820 0 : return false;
821 : }
822 : }
823 2780 : return true;
824 : }
825 :
826 556 : bool SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_serialize)(
827 : const struct sqlite_rtree_bl *tr,
828 : sqlite3* hDB,
829 : const char* rtree_name,
830 : const char* rowid_colname,
831 : const char* minx_colname,
832 : const char* miny_colname,
833 : const char* maxx_colname,
834 : const char* maxy_colname,
835 : char** p_error_msg) {
836 556 : if (p_error_msg) {
837 556 : *p_error_msg = NULL;
838 : }
839 :
840 : char* sql;
841 1112 : if (IsLowercaseAlpha(rowid_colname) &&
842 1112 : IsLowercaseAlpha(minx_colname) &&
843 1112 : IsLowercaseAlpha(maxx_colname) &&
844 1668 : IsLowercaseAlpha(miny_colname) &&
845 556 : IsLowercaseAlpha(maxy_colname)) {
846 : /* To make OGC GeoPackage compliance test happy... */
847 556 : sql = sqlite3_mprintf(
848 : "CREATE VIRTUAL TABLE \"%w\" USING rtree(%s, %s, %s, %s, %s)",
849 : rtree_name, rowid_colname, minx_colname, maxx_colname, miny_colname,
850 : maxy_colname);
851 : }
852 : else {
853 0 : sql = sqlite3_mprintf(
854 : "CREATE VIRTUAL TABLE \"%w\" USING rtree(\"%w\", \"%w\", \"%w\", \"%w\", \"%w\")",
855 : rtree_name, rowid_colname, minx_colname, maxx_colname, miny_colname,
856 : maxy_colname);
857 : }
858 556 : int ret = sqlite3_exec(hDB, sql, NULL, NULL, p_error_msg);
859 556 : sqlite3_free(sql);
860 556 : if (ret != SQLITE_OK) {
861 0 : return false;
862 : }
863 :
864 556 : if (tr->count == 0) {
865 184 : return true;
866 : }
867 :
868 : // Suppress default root node
869 372 : sql = sqlite3_mprintf("DELETE FROM \"%w_node\"", rtree_name);
870 372 : ret = sqlite3_exec(hDB, sql, NULL, NULL, p_error_msg);
871 372 : sqlite3_free(sql);
872 372 : if (ret != SQLITE_OK) {
873 0 : return false;
874 : }
875 :
876 372 : sqlite3_stmt *hStmtNode = NULL;
877 372 : sql = sqlite3_mprintf("INSERT INTO \"%w_node\" VALUES (?, ?)", rtree_name);
878 372 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, sql, -1, &hStmtNode, NULL));
879 372 : sqlite3_free(sql);
880 372 : if (!hStmtNode) {
881 0 : return false;
882 : }
883 :
884 372 : sqlite3_stmt *hStmtParent = NULL;
885 372 : sql = sqlite3_mprintf("INSERT INTO \"%w_parent\" VALUES (?, ?)", rtree_name);
886 372 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, sql, -1, &hStmtParent, NULL));
887 372 : sqlite3_free(sql);
888 372 : if (!hStmtParent) {
889 0 : sqlite3_finalize(hStmtNode);
890 0 : return false;
891 : }
892 :
893 372 : sqlite3_stmt *hStmtRowid = NULL;
894 372 : sql = sqlite3_mprintf("INSERT INTO \"%w_rowid\" VALUES (?, ?)", rtree_name);
895 372 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, sql, -1, &hStmtRowid, NULL));
896 372 : sqlite3_free(sql);
897 372 : if (!hStmtRowid) {
898 0 : sqlite3_finalize(hStmtNode);
899 0 : sqlite3_finalize(hStmtParent);
900 0 : return false;
901 : }
902 :
903 : rtree_insert_context ctxt;
904 372 : ctxt.hDB = hDB;
905 372 : ctxt.hStmtNode = hStmtNode;
906 372 : ctxt.hStmtParent = hStmtParent;
907 372 : ctxt.hStmtRowid = hStmtRowid;
908 372 : ctxt.node_capacity = tr->node_capacity;
909 372 : ctxt.tree_height = tr->height;
910 372 : ctxt.p_error_msg = p_error_msg;
911 :
912 372 : int64_t cur_nodeno = 1;
913 372 : bool ok = insert_into_db(&ctxt, tr->root, &cur_nodeno, 0, PASS_NODE);
914 372 : if (ok) {
915 372 : cur_nodeno = 1;
916 372 : ok = insert_into_db(&ctxt, tr->root, &cur_nodeno, 0, PASS_PARENT);
917 : }
918 372 : if (ok) {
919 372 : cur_nodeno = 1;
920 372 : ok = insert_into_db(&ctxt, tr->root, &cur_nodeno, 0, PASS_ROWID);
921 : }
922 :
923 372 : sqlite3_finalize(hStmtNode);
924 372 : sqlite3_finalize(hStmtParent);
925 372 : sqlite3_finalize(hStmtRowid);
926 372 : return ok;
927 : }
928 :
929 : #define NOTIFICATION_INTERVAL (500 * 1000)
930 :
931 544 : bool SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_from_feature_table)(
932 : sqlite3* hDB,
933 : const char* feature_table_name,
934 : const char* feature_table_fid_colname,
935 : const char* feature_table_geom_colname,
936 : const char* rtree_name,
937 : const char* rowid_colname,
938 : const char* minx_colname,
939 : const char* miny_colname,
940 : const char* maxx_colname,
941 : const char* maxy_colname,
942 : size_t max_ram_usage,
943 : char** p_error_msg,
944 : sqlite_rtree_progress_callback progress_cbk,
945 : void* progress_cbk_user_data)
946 : {
947 544 : char** papszResult = NULL;
948 544 : sqlite3_get_table(hDB, "PRAGMA page_size", &papszResult, NULL, NULL, NULL);
949 544 : const int page_size = atoi(papszResult[1]);
950 544 : sqlite3_free_table(papszResult);
951 :
952 544 : struct sqlite_rtree_bl* t = SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_new)(page_size);
953 544 : if (!t) {
954 0 : if (p_error_msg)
955 0 : *p_error_msg = my_sqlite3_strdup("not enough memory");
956 0 : return false;
957 : }
958 :
959 544 : sqlite3_stmt *hStmt = NULL;
960 : char *pszSQL =
961 544 : sqlite3_mprintf("SELECT \"%w\", ST_MinX(\"%w\"), ST_MaxX(\"%w\"), "
962 : "ST_MinY(\"%w\"), ST_MaxY(\"%w\") FROM \"%w\" "
963 : "WHERE \"%w\" NOT NULL AND NOT ST_IsEmpty(\"%w\")",
964 : feature_table_fid_colname,
965 : feature_table_geom_colname,
966 : feature_table_geom_colname,
967 : feature_table_geom_colname,
968 : feature_table_geom_colname,
969 : feature_table_name,
970 : feature_table_geom_colname,
971 : feature_table_geom_colname);
972 544 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, pszSQL, -1, &hStmt, NULL));
973 544 : sqlite3_free(pszSQL);
974 544 : if (!hStmt) {
975 0 : if (p_error_msg)
976 0 : *p_error_msg = my_sqlite3_strdup(sqlite3_errmsg(hDB));
977 0 : SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_free)(t);
978 0 : return false;
979 : }
980 :
981 544 : bool bMaxMemReached = false;
982 544 : uint64_t nRows = 0;
983 231249 : while (sqlite3_step(hStmt) == SQLITE_ROW) {
984 230717 : int64_t id = sqlite3_column_int64(hStmt, 0);
985 230717 : const double minx = sqlite3_column_double(hStmt, 1);
986 230717 : const double maxx = sqlite3_column_double(hStmt, 2);
987 230717 : const double miny = sqlite3_column_double(hStmt, 3);
988 230717 : const double maxy = sqlite3_column_double(hStmt, 4);
989 230717 : if (!SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_insert)(t, id, minx, miny, maxx, maxy)) {
990 0 : bMaxMemReached = true;
991 0 : break;
992 : }
993 461434 : if (max_ram_usage != 0 &&
994 230717 : SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_ram_usage)(t) > max_ram_usage) {
995 12 : bMaxMemReached = true;
996 12 : break;
997 : }
998 230705 : if (progress_cbk && ((++nRows) % NOTIFICATION_INTERVAL) == 0) {
999 : char szMsg[256];
1000 0 : snprintf(szMsg, sizeof(szMsg),
1001 : "%" PRIu64 " rows inserted in %s (in RAM)",
1002 : nRows, rtree_name);
1003 0 : if (!progress_cbk(szMsg, progress_cbk_user_data)) {
1004 0 : SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_free)(t);
1005 0 : sqlite3_finalize(hStmt);
1006 0 : if (p_error_msg)
1007 0 : *p_error_msg = my_sqlite3_strdup("Processing interrupted");
1008 0 : return false;
1009 : }
1010 : }
1011 : }
1012 :
1013 544 : bool bOK = SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_serialize)(
1014 : t, hDB,
1015 : rtree_name,
1016 : rowid_colname,
1017 : minx_colname,
1018 : miny_colname,
1019 : maxx_colname,
1020 : maxy_colname,
1021 : p_error_msg);
1022 :
1023 544 : SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_free)(t);
1024 :
1025 544 : if (bOK && bMaxMemReached) {
1026 12 : if (progress_cbk) {
1027 12 : CPL_IGNORE_RET_VAL_INT(progress_cbk(
1028 : "Max RAM reached. Falling back to slower "
1029 : "insertion method", progress_cbk_user_data));
1030 : }
1031 :
1032 12 : sqlite3_stmt *hStmtInsert = NULL;
1033 : pszSQL =
1034 12 : sqlite3_mprintf("INSERT INTO \"%w\" VALUES (?,?,?,?,?)",
1035 : rtree_name);
1036 12 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, pszSQL, -1, &hStmtInsert, NULL));
1037 12 : sqlite3_free(pszSQL);
1038 12 : if (!hStmtInsert) {
1039 0 : if (p_error_msg)
1040 0 : *p_error_msg = my_sqlite3_strdup(sqlite3_errmsg(hDB));
1041 0 : sqlite3_finalize(hStmt);
1042 0 : return false;
1043 : }
1044 11200 : while (sqlite3_step(hStmt) == SQLITE_ROW) {
1045 11188 : int64_t id = sqlite3_column_int64(hStmt, 0);
1046 11188 : const double minx = sqlite3_column_double(hStmt, 1);
1047 11188 : const double maxx = sqlite3_column_double(hStmt, 2);
1048 11188 : const double miny = sqlite3_column_double(hStmt, 3);
1049 11188 : const double maxy = sqlite3_column_double(hStmt, 4);
1050 :
1051 11188 : sqlite3_reset(hStmtInsert);
1052 11188 : sqlite3_bind_int64(hStmtInsert, 1, id);
1053 11188 : sqlite3_bind_double(hStmtInsert, 2, minx);
1054 11188 : sqlite3_bind_double(hStmtInsert, 3, maxx);
1055 11188 : sqlite3_bind_double(hStmtInsert, 4, miny);
1056 11188 : sqlite3_bind_double(hStmtInsert, 5, maxy);
1057 11188 : int ret = sqlite3_step(hStmtInsert);
1058 11188 : if (ret != SQLITE_OK && ret != SQLITE_DONE) {
1059 0 : if (p_error_msg)
1060 0 : *p_error_msg = my_sqlite3_strdup(sqlite3_errmsg(hDB));
1061 0 : bOK = false;
1062 0 : break;
1063 : }
1064 11188 : if (progress_cbk && ((++nRows) % NOTIFICATION_INTERVAL) == 0) {
1065 : char szMsg[256];
1066 0 : snprintf(szMsg, sizeof(szMsg),
1067 : "%" PRIu64 " rows inserted in %s", nRows, rtree_name);
1068 0 : if (!progress_cbk(szMsg, progress_cbk_user_data)) {
1069 0 : bOK = false;
1070 0 : if (p_error_msg)
1071 0 : *p_error_msg = my_sqlite3_strdup("Processing interrupted");
1072 0 : break;
1073 : }
1074 : }
1075 : }
1076 12 : sqlite3_finalize(hStmtInsert);
1077 : }
1078 :
1079 544 : if (bOK && progress_cbk && (nRows % NOTIFICATION_INTERVAL) != 0)
1080 : {
1081 : char szMsg[256];
1082 364 : snprintf(szMsg, sizeof(szMsg), "%" PRIu64 " rows inserted in %s",
1083 : nRows, rtree_name);
1084 364 : CPL_IGNORE_RET_VAL_INT(progress_cbk(szMsg, progress_cbk_user_data));
1085 : }
1086 :
1087 544 : sqlite3_finalize(hStmt);
1088 544 : return bOK;
1089 : }
|
