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