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