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