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 2197 : static void CPL_IGNORE_RET_VAL_INT(CPL_UNUSED int v) {
119 : (void)v;
120 2197 : }
121 :
122 67064300 : static inline NUMTYPE min0(NUMTYPE x, NUMTYPE y) {
123 67064300 : return x < y ? x : y;
124 : }
125 :
126 67064300 : static inline NUMTYPE max0(NUMTYPE x, NUMTYPE y) {
127 67064300 : return x > y ? x : y;
128 : }
129 :
130 9744 : static struct node *node_new(struct sqlite_rtree_bl *tr, enum kind kind) {
131 9744 : struct node *node = STATIC_CAST(struct node *, tr->malloc(sizeof(struct node)));
132 9744 : if (!node) {
133 0 : return NULL;
134 : }
135 9744 : memset(node, 0, sizeof(struct node));
136 9744 : node->kind = kind;
137 9744 : tr->mem_usage += sizeof(struct node);
138 9744 : return node;
139 : }
140 :
141 9744 : static void node_free(struct sqlite_rtree_bl *tr, struct node *node) {
142 9744 : if (node->kind == BRANCH) {
143 9667 : for (int i = 0; i < node->count; i++) {
144 9307 : node_free(tr, node->nodes[i]);
145 : }
146 : }
147 9744 : tr->mem_usage -= sizeof(struct node);
148 9744 : tr->free(node);
149 9744 : }
150 :
151 18796400 : static void rect_expand(struct rect *rect, const struct rect *other) {
152 56389100 : for (int i = 0; i < DIMS; i++) {
153 37592800 : rect->min[i] = min0(rect->min[i], other->min[i]);
154 37592800 : rect->max[i] = max0(rect->max[i], other->max[i]);
155 : }
156 18796400 : }
157 :
158 15263700 : static double rect_area(const struct rect *rect) {
159 15263700 : double result = 1;
160 45791200 : for (int i = 0; i < DIMS; i++) {
161 30527500 : result *= STATIC_CAST(double, rect->max[i]) - rect->min[i];
162 : }
163 15263700 : return result;
164 : }
165 :
166 : // return the area of two rects expanded
167 14559100 : static double rect_unioned_area(const struct rect *rect,
168 : const struct rect *other) {
169 14559100 : double result = 1;
170 43677400 : for (int i = 0; i < DIMS; i++) {
171 29118300 : result *= STATIC_CAST(double, max0(rect->max[i], other->max[i])) -
172 29118300 : min0(rect->min[i], other->min[i]);
173 : }
174 14559100 : return result;
175 : }
176 :
177 14561200 : static bool rect_contains(const struct rect *rect, const struct rect *other) {
178 14562700 : for (int i = 0; i < DIMS; i++) {
179 14562300 : if (other->min[i] < rect->min[i])
180 61747 : return false;
181 14500500 : if (other->max[i] > rect->max[i])
182 14499000 : return false;
183 : }
184 460 : return true;
185 : }
186 :
187 704140 : static double rect_margin(const struct rect *rect) {
188 704140 : return (STATIC_CAST(double, rect->max[0]) - rect->min[0]) +
189 704140 : (STATIC_CAST(double, rect->max[1]) - rect->min[1]);
190 : }
191 :
192 352070 : static double rect_overlap(const struct rect *rect1, const struct rect *rect2) {
193 352070 : double overlap = 1;
194 354406 : for (int idim = 0; idim < DIMS; ++idim)
195 : {
196 353240 : double minv = max0(rect1->min[idim], rect2->min[idim]);
197 353240 : double maxv = min0(rect1->max[idim], rect2->max[idim]);
198 353240 : if( maxv < minv ) {
199 350904 : return 0;
200 : }
201 2336 : overlap *= (maxv - minv);
202 : }
203 1166 : 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 9265 : 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 9265 : nodeOri.kind = node->kind;
260 9265 : nodeOri.count = node->count;
261 9265 : memcpy(nodeOri.rects, node->rects, node->count * sizeof(struct rect));
262 9265 : nodeOri.rects[node->count] = *extraRect;
263 9265 : if (nodeOri.kind == LEAF) {
264 8947 : memcpy(nodeOri.datas, node->datas, node->count * sizeof(struct item));
265 8947 : 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 9265 : nodeOri.count ++;
271 9265 : assert(nodeOri.count == tr->node_capacity + 1);
272 :
273 : SortType aSorted[DIMS][MAXITEMS+1];
274 27795 : for (int idim = 0; idim < DIMS; ++idim) {
275 982090 : for (int i = 0; i < tr->node_capacity + 1; ++i) {
276 963560 : 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 9265 : std::sort(aSorted[0], aSorted[0] + nodeOri.count, [&nodeOri](const SortType& a, const SortType& b) {
288 3057300 : return nodeOri.rects[a.i].min[0] < nodeOri.rects[b.i].min[0] ||
289 715259 : (nodeOri.rects[a.i].min[0] == nodeOri.rects[b.i].min[0] &&
290 2343640 : nodeOri.rects[a.i].max[0] < nodeOri.rects[b.i].max[0]);
291 : });
292 9265 : std::sort(aSorted[1], aSorted[1] + nodeOri.count, [&nodeOri](const SortType& a, const SortType& b) {
293 3056840 : return nodeOri.rects[a.i].min[1] < nodeOri.rects[b.i].min[1] ||
294 716511 : (nodeOri.rects[a.i].min[1] == nodeOri.rects[b.i].min[1] &&
295 2343880 : nodeOri.rects[a.i].max[1] < nodeOri.rects[b.i].max[1]);
296 : });
297 : #endif
298 :
299 9265 : int iBestDim = 0;
300 9265 : int iBestSplit = tr->node_capacity / 2;
301 9265 : double fBestMargin = INFINITY;
302 27795 : for (int idim = 0; idim < DIMS; ++idim) {
303 18530 : double margin = 0;
304 18530 : double fBestOverlap = INFINITY;
305 18530 : double fBestArea = INFINITY;
306 18530 : int iBestLeft = 0;
307 18530 : const int minItems = tr->node_capacity / 3;
308 370600 : for (int nLeft = minItems; nLeft <= nodeOri.count - minItems; ++nLeft) {
309 352070 : struct rect rectLeft = nodeOri.rects[aSorted[idim][0].i];
310 352070 : struct rect rectRight = nodeOri.rects[aSorted[idim][nodeOri.count-1].i];
311 17955600 : for(int kk=1; kk<(nodeOri.count-1); kk++) {
312 17603500 : if( kk<nLeft ){
313 8801750 : rect_expand(&rectLeft, &nodeOri.rects[aSorted[idim][kk].i]);
314 : }else{
315 8801750 : rect_expand(&rectRight, &nodeOri.rects[aSorted[idim][kk].i]);
316 : }
317 : }
318 352070 : margin += rect_margin(&rectLeft);
319 352070 : margin += rect_margin(&rectRight);
320 352070 : double overlap = rect_overlap(&rectLeft, &rectRight);
321 352070 : double area = rect_area(&rectLeft) + rect_area(&rectRight);
322 352070 : if( overlap<fBestOverlap || (overlap==fBestOverlap && area<fBestArea)) {
323 184815 : iBestLeft = nLeft;
324 184815 : fBestOverlap = overlap;
325 184815 : fBestArea = area;
326 : }
327 : }
328 :
329 18530 : if (margin<fBestMargin) {
330 9273 : iBestDim = idim;
331 9273 : fBestMargin = margin;
332 9273 : iBestSplit = iBestLeft;
333 : }
334 : }
335 :
336 9265 : struct node *right = node_new(tr, node->kind);
337 9265 : if (!right) {
338 0 : return false;
339 : }
340 9265 : node->count = 0;
341 9265 : int i = 0;
342 250003 : for (; i < iBestSplit; ++i) {
343 240738 : struct node* target = node;
344 240738 : target->rects[target->count] = nodeOri.rects[aSorted[iBestDim][i].i];
345 240738 : if (nodeOri.kind == LEAF) {
346 232470 : 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 240738 : ++target->count;
351 : }
352 250307 : for (; i < nodeOri.count; ++i) {
353 241042 : struct node* target = right;
354 241042 : target->rects[target->count] = nodeOri.rects[aSorted[iBestDim][i].i];
355 241042 : if (nodeOri.kind == LEAF) {
356 232774 : 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 241042 : ++target->count;
361 : }
362 9265 : *right_out = right;
363 9265 : return true;
364 : }
365 :
366 503023 : static int node_choose_least_enlargement(const struct node *node,
367 : const struct rect *ir) {
368 503023 : int j = 0;
369 503023 : double jenlarge = INFINITY;
370 503023 : double minarea = 0;
371 15062200 : for (int i = 0; i < node->count; i++) {
372 : // calculate the enlarged area
373 14559100 : double uarea = rect_unioned_area(&node->rects[i], ir);
374 14559100 : double area = rect_area(&node->rects[i]);
375 14559100 : double enlarge = uarea - area;
376 14559100 : if (enlarge < jenlarge || (enlarge == jenlarge && area < minarea)) {
377 14501600 : j = i;
378 14501600 : jenlarge = enlarge;
379 14501600 : minarea = area;
380 : }
381 : }
382 503023 : return j;
383 : }
384 :
385 503461 : 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 503461 : int iBestIndex = -1;
406 503461 : double minArea = INFINITY;
407 15064600 : for (int i = 0; i < node->count; i++) {
408 14561200 : if (rect_contains(&node->rects[i], rect)) {
409 460 : double area = rect_area(&node->rects[i]);
410 460 : if( area < minArea )
411 : {
412 456 : iBestIndex = i;
413 456 : minArea = area;
414 : }
415 : }
416 : }
417 503461 : if (iBestIndex >= 0) {
418 : #ifdef USE_PATHHINT
419 : tr->path_hint[depth] = iBestIndex;
420 : #endif
421 438 : return iBestIndex;
422 : }
423 :
424 : // Fallback to using che "choose least enlargement" algorithm.
425 503023 : int i = node_choose_least_enlargement(node, rect);
426 : #ifdef USE_PATHHINT
427 : tr->path_hint[depth] = i;
428 : #endif
429 503023 : return i;
430 : }
431 :
432 18530 : static struct rect node_rect_calc(const struct node *node) {
433 18530 : struct rect rect = node->rects[0];
434 481780 : for (int i = 1; i < node->count; i++) {
435 463250 : rect_expand(&rect, &node->rects[i]);
436 : }
437 18530 : return rect;
438 : }
439 :
440 : // node_insert returns false if out of memory
441 738894 : 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 738894 : if (node->kind == LEAF) {
452 235433 : if (node->count == tr->node_capacity) {
453 8947 : *split = true;
454 8947 : *rectToInsert = *ir;
455 8947 : *itemToInsert = item;
456 8947 : *nodeToInsert = NULL;
457 8947 : return true;
458 : }
459 226486 : int index = node->count;
460 226486 : node->rects[index] = *ir;
461 226486 : node->datas[index] = item;
462 226486 : node->count++;
463 226486 : *split = false;
464 226486 : return true;
465 : }
466 : // Choose a subtree for inserting the rectangle.
467 503461 : const int i = node_choose(tr, node, ir, depth);
468 503461 : if (!node_insert(tr, node->nodes[i], ir, item, depth+1,
469 : split, rectToInsert, itemToInsert, nodeToInsert))
470 : {
471 0 : return false;
472 : }
473 503461 : if (!*split) {
474 494238 : rect_expand(&node->rects[i], ir);
475 494238 : *split = false;
476 494238 : return true;
477 : }
478 :
479 : struct node *right;
480 9223 : if (!node_split_rstartree(tr, node->nodes[i], rectToInsert,
481 : *itemToInsert, *nodeToInsert, &right)) {
482 0 : return false;
483 : }
484 9223 : node->rects[i] = node_rect_calc(node->nodes[i]);
485 :
486 : // split the child node
487 9223 : 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 8905 : *split = false;
496 8905 : node->rects[node->count] = node_rect_calc(right);
497 8905 : node->nodes[node->count] = right;
498 8905 : node->count++;
499 8905 : return true;
500 : }
501 :
502 : static
503 625 : struct sqlite_rtree_bl *sqlite_rtree_bl_new_with_allocator(int sqlite_page_size,
504 : void *(*pfnMalloc)(size_t),
505 : void (*pfnFree)(void*)) {
506 625 : if (!pfnMalloc)
507 625 : pfnMalloc = malloc;
508 625 : if (!pfnFree)
509 625 : pfnFree = free;
510 625 : struct sqlite_rtree_bl *tr = STATIC_CAST(struct sqlite_rtree_bl *, pfnMalloc(sizeof(struct sqlite_rtree_bl)));
511 625 : if (!tr) return NULL;
512 625 : memset(tr, 0, sizeof(struct sqlite_rtree_bl));
513 625 : tr->malloc = pfnMalloc;
514 625 : tr->free = pfnFree;
515 :
516 : // Cf https://github.com/sqlite/sqlite/blob/90e4a3b7fcdf63035d6f35eb44d11ff58ff4b068/ext/rtree/rtree.c#L3541
517 625 : tr->node_size = sqlite_page_size-64;
518 625 : if( tr->node_size > 4+BYTES_PER_CELL*MAXITEMS ){
519 625 : tr->node_size = 4+BYTES_PER_CELL*MAXITEMS;
520 : }
521 625 : tr->node_capacity = (tr->node_size-4)/BYTES_PER_CELL;
522 625 : tr->mem_usage = sizeof(struct sqlite_rtree_bl);
523 :
524 625 : return tr;
525 : }
526 :
527 625 : struct sqlite_rtree_bl *SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_new)(int sqlite_page_size) {
528 625 : 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 470866 : static float rtreeValueDown(double d){
543 470866 : float f = STATIC_CAST(float, d);
544 470866 : if( f>d ){
545 10065 : f = STATIC_CAST(float, d*(d<0 ? RNDAWAY : RNDTOWARDS));
546 : }
547 470866 : return f;
548 : }
549 470866 : static float rtreeValueUp(double d){
550 470866 : float f = STATIC_CAST(float, d);
551 470866 : if( f<d ){
552 10061 : f = STATIC_CAST(float, d*(d<0 ? RNDTOWARDS : RNDAWAY));
553 : }
554 470866 : return f;
555 : }
556 :
557 235433 : 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 235433 : if( !(minx <= maxx) || !(miny <= maxy) )
563 0 : return false;
564 :
565 : // copy input rect
566 : struct rect rect;
567 235433 : rect.min[0] = rtreeValueDown(minx);
568 235433 : rect.min[1] = rtreeValueDown(miny);
569 235433 : rect.max[0] = rtreeValueUp(maxx);
570 235433 : rect.max[1] = rtreeValueUp(maxy);
571 :
572 : // copy input data
573 : struct item item;
574 235433 : item.data = fid;
575 :
576 : struct rect rectToInsert;
577 : struct item itemToInsert;
578 : struct node* nodeToInsert;
579 :
580 235433 : if (!tr->root) {
581 437 : struct node *new_root = node_new(tr, LEAF);
582 437 : if (!new_root) {
583 0 : return false;
584 : }
585 437 : tr->root = new_root;
586 437 : tr->rect = rect;
587 437 : tr->height = 1;
588 : }
589 235433 : bool split = false;
590 235433 : if (!node_insert(tr, tr->root, &rect, item, 0,
591 : &split, &rectToInsert, &itemToInsert, &nodeToInsert)) {
592 0 : return false;
593 : }
594 235433 : if (!split) {
595 235391 : rect_expand(&tr->rect, &rect);
596 235391 : tr->count++;
597 235391 : return true;
598 : }
599 42 : struct node *new_root = node_new(tr, BRANCH);
600 42 : if (!new_root) {
601 0 : return false;
602 : }
603 : struct node *right;
604 42 : if (!node_split_rstartree(tr, tr->root, &rectToInsert, itemToInsert, nodeToInsert, &right)) {
605 0 : tr->free(new_root);
606 0 : return false;
607 : }
608 42 : new_root->rects[0] = node_rect_calc(tr->root);
609 42 : new_root->rects[1] = node_rect_calc(right);
610 42 : new_root->nodes[0] = tr->root;
611 42 : new_root->nodes[1] = right;
612 42 : tr->root = new_root;
613 42 : tr->root->count = 2;
614 42 : tr->height++;
615 :
616 42 : return true;
617 : }
618 :
619 235441 : size_t SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_ram_usage)(const sqlite_rtree_bl* tr) {
620 235441 : return tr->mem_usage;
621 : }
622 :
623 625 : void SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_free)(struct sqlite_rtree_bl *tr) {
624 625 : if (tr) {
625 625 : if (tr->root) {
626 437 : node_free(tr, tr->root);
627 : }
628 625 : tr->free(tr);
629 : }
630 625 : }
631 :
632 19416 : static void write_be_uint16(uint8_t* dest, uint16_t n) {
633 19416 : dest[0] = STATIC_CAST(uint8_t, n >> 8);
634 19416 : dest[1] = STATIC_CAST(uint8_t, n);
635 19416 : }
636 :
637 244380 : static void write_be_int64(uint8_t* dest, int64_t i) {
638 244380 : const uint64_t n = i;
639 244380 : dest[0] = STATIC_CAST(uint8_t, n >> 56);
640 244380 : dest[1] = STATIC_CAST(uint8_t, n >> 48);
641 244380 : dest[2] = STATIC_CAST(uint8_t, n >> 40);
642 244380 : dest[3] = STATIC_CAST(uint8_t, n >> 32);
643 244380 : dest[4] = STATIC_CAST(uint8_t, n >> 24);
644 244380 : dest[5] = STATIC_CAST(uint8_t, n >> 16);
645 244380 : dest[6] = STATIC_CAST(uint8_t, n >> 8);
646 244380 : dest[7] = STATIC_CAST(uint8_t, n);
647 244380 : }
648 :
649 977520 : static void write_be_float(uint8_t* dest, float f) {
650 : uint32_t n;
651 977520 : memcpy(&n, &f, sizeof(float));
652 977520 : dest[0] = STATIC_CAST(uint8_t, n >> 24);
653 977520 : dest[1] = STATIC_CAST(uint8_t, n >> 16);
654 977520 : dest[2] = STATIC_CAST(uint8_t, n >> 8);
655 977520 : dest[3] = STATIC_CAST(uint8_t, n);
656 977520 : }
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 29124 : 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 29124 : const int64_t this_cur_nodeno = (*p_cur_nodeno);
692 29124 : uint8_t blob[4 + MAXITEMS * BYTES_PER_CELL] = {0};
693 29124 : size_t offset = 4;
694 :
695 29124 : if (node->kind == BRANCH) {
696 29001 : for (int i = 0; i < node->count; ++i) {
697 27921 : ++(*p_cur_nodeno);
698 :
699 27921 : if (pass == PASS_ALL || pass == PASS_NODE) {
700 9307 : write_be_int64(blob + offset, (*p_cur_nodeno));
701 9307 : offset += sizeof(int64_t);
702 :
703 9307 : const float minx = node->rects[i].min[0];
704 9307 : write_be_float(blob + offset, minx);
705 9307 : offset += sizeof(float);
706 :
707 9307 : const float maxx = node->rects[i].max[0];
708 9307 : write_be_float(blob + offset, maxx);
709 9307 : offset += sizeof(float);
710 :
711 9307 : const float miny = node->rects[i].min[1];
712 9307 : write_be_float(blob + offset, miny);
713 9307 : offset += sizeof(float);
714 :
715 9307 : const float maxy = node->rects[i].max[1];
716 9307 : write_be_float(blob + offset, maxy);
717 9307 : offset += sizeof(float);
718 : }
719 :
720 27921 : if (!insert_into_db(ctxt, node->nodes[i], p_cur_nodeno,
721 : this_cur_nodeno, pass)) {
722 0 : return false;
723 : }
724 : }
725 : }
726 28044 : else if (pass == PASS_ALL || pass == PASS_NODE || pass == PASS_ROWID) {
727 488842 : for (int i = 0; i < node->count; ++i ) {
728 470146 : const int64_t fid = node->datas[i].data;
729 470146 : if( pass == PASS_ALL || pass == PASS_NODE )
730 : {
731 235073 : write_be_int64(blob + offset, fid);
732 235073 : offset += sizeof(int64_t);
733 :
734 235073 : const float minx = node->rects[i].min[0];
735 235073 : write_be_float(blob + offset, minx);
736 235073 : offset += sizeof(float);
737 :
738 235073 : const float maxx = node->rects[i].max[0];
739 235073 : write_be_float(blob + offset, maxx);
740 235073 : offset += sizeof(float);
741 :
742 235073 : const float miny = node->rects[i].min[1];
743 235073 : write_be_float(blob + offset, miny);
744 235073 : offset += sizeof(float);
745 :
746 235073 : const float maxy = node->rects[i].max[1];
747 235073 : write_be_float(blob + offset, maxy);
748 235073 : offset += sizeof(float);
749 : }
750 :
751 470146 : if (pass == PASS_ALL || pass == PASS_ROWID) {
752 235073 : sqlite3_reset(ctxt->hStmtRowid);
753 235073 : sqlite3_bind_int64(ctxt->hStmtRowid, 1, fid);
754 235073 : sqlite3_bind_int64(ctxt->hStmtRowid, 2, this_cur_nodeno);
755 235073 : int ret = sqlite3_step(ctxt->hStmtRowid);
756 235073 : 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 29124 : if (pass == PASS_ALL || pass == PASS_NODE) {
767 9708 : write_be_uint16(blob, STATIC_CAST(uint16_t, parent_nodeno == 0 ? ctxt->tree_height - 1 : 0));
768 9708 : write_be_uint16(blob + 2, STATIC_CAST(uint16_t, node->count));
769 :
770 9708 : sqlite3_reset(ctxt->hStmtNode);
771 9708 : sqlite3_bind_int64(ctxt->hStmtNode, 1, this_cur_nodeno);
772 9708 : sqlite3_bind_blob(ctxt->hStmtNode, 2, blob,
773 9708 : 4 + ctxt->node_capacity * BYTES_PER_CELL,
774 : SQLITE_STATIC);
775 9708 : int ret = sqlite3_step(ctxt->hStmtNode);
776 9708 : 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 29124 : if ((pass == PASS_ALL || pass == PASS_PARENT) && parent_nodeno > 0) {
785 9307 : sqlite3_reset(ctxt->hStmtParent);
786 9307 : sqlite3_bind_int64(ctxt->hStmtParent, 1, this_cur_nodeno);
787 9307 : sqlite3_bind_int64(ctxt->hStmtParent, 2, parent_nodeno);
788 9307 : int ret = sqlite3_step(ctxt->hStmtParent);
789 9307 : 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 29124 : return true;
798 : }
799 :
800 13547 : static bool IsLowercaseAlpha(const char* s)
801 : {
802 13547 : for (; *s != 0; ++s) {
803 10602 : if (!(*s >= 'a' && *s <= 'z')) {
804 0 : return false;
805 : }
806 : }
807 2945 : return true;
808 : }
809 :
810 589 : 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 589 : if (p_error_msg) {
821 589 : *p_error_msg = NULL;
822 : }
823 :
824 : char* sql;
825 1178 : if (IsLowercaseAlpha(rowid_colname) &&
826 1178 : IsLowercaseAlpha(minx_colname) &&
827 1178 : IsLowercaseAlpha(maxx_colname) &&
828 1767 : IsLowercaseAlpha(miny_colname) &&
829 589 : IsLowercaseAlpha(maxy_colname)) {
830 : /* To make OGC GeoPackage compliance test happy... */
831 589 : 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 589 : int ret = sqlite3_exec(hDB, sql, NULL, NULL, p_error_msg);
843 589 : sqlite3_free(sql);
844 589 : if (ret != SQLITE_OK) {
845 0 : return false;
846 : }
847 :
848 589 : if (tr->count == 0) {
849 188 : return true;
850 : }
851 :
852 : // Suppress default root node
853 401 : sql = sqlite3_mprintf("DELETE FROM \"%w_node\"", rtree_name);
854 401 : ret = sqlite3_exec(hDB, sql, NULL, NULL, p_error_msg);
855 401 : sqlite3_free(sql);
856 401 : if (ret != SQLITE_OK) {
857 0 : return false;
858 : }
859 :
860 401 : sqlite3_stmt *hStmtNode = NULL;
861 401 : sql = sqlite3_mprintf("INSERT INTO \"%w_node\" VALUES (?, ?)", rtree_name);
862 401 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, sql, -1, &hStmtNode, NULL));
863 401 : sqlite3_free(sql);
864 401 : if (!hStmtNode) {
865 0 : return false;
866 : }
867 :
868 401 : sqlite3_stmt *hStmtParent = NULL;
869 401 : sql = sqlite3_mprintf("INSERT INTO \"%w_parent\" VALUES (?, ?)", rtree_name);
870 401 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, sql, -1, &hStmtParent, NULL));
871 401 : sqlite3_free(sql);
872 401 : if (!hStmtParent) {
873 0 : sqlite3_finalize(hStmtNode);
874 0 : return false;
875 : }
876 :
877 401 : sqlite3_stmt *hStmtRowid = NULL;
878 401 : sql = sqlite3_mprintf("INSERT INTO \"%w_rowid\" VALUES (?, ?)", rtree_name);
879 401 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, sql, -1, &hStmtRowid, NULL));
880 401 : sqlite3_free(sql);
881 401 : if (!hStmtRowid) {
882 0 : sqlite3_finalize(hStmtNode);
883 0 : sqlite3_finalize(hStmtParent);
884 0 : return false;
885 : }
886 :
887 : rtree_insert_context ctxt;
888 401 : ctxt.hDB = hDB;
889 401 : ctxt.hStmtNode = hStmtNode;
890 401 : ctxt.hStmtParent = hStmtParent;
891 401 : ctxt.hStmtRowid = hStmtRowid;
892 401 : ctxt.node_capacity = tr->node_capacity;
893 401 : ctxt.tree_height = tr->height;
894 401 : ctxt.p_error_msg = p_error_msg;
895 :
896 401 : int64_t cur_nodeno = 1;
897 401 : bool ok = insert_into_db(&ctxt, tr->root, &cur_nodeno, 0, PASS_NODE);
898 401 : if (ok) {
899 401 : cur_nodeno = 1;
900 401 : ok = insert_into_db(&ctxt, tr->root, &cur_nodeno, 0, PASS_PARENT);
901 : }
902 401 : if (ok) {
903 401 : cur_nodeno = 1;
904 401 : ok = insert_into_db(&ctxt, tr->root, &cur_nodeno, 0, PASS_ROWID);
905 : }
906 :
907 401 : sqlite3_finalize(hStmtNode);
908 401 : sqlite3_finalize(hStmtParent);
909 401 : sqlite3_finalize(hStmtRowid);
910 401 : return ok;
911 : }
912 :
913 : #define NOTIFICATION_INTERVAL (500 * 1000)
914 :
915 577 : 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 577 : char** papszResult = NULL;
932 577 : sqlite3_get_table(hDB, "PRAGMA page_size", &papszResult, NULL, NULL, NULL);
933 577 : const int page_size = atoi(papszResult[1]);
934 577 : sqlite3_free_table(papszResult);
935 :
936 577 : struct sqlite_rtree_bl* t = SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_new)(page_size);
937 577 : 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 577 : sqlite3_stmt *hStmt = NULL;
944 : char *pszSQL =
945 577 : 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 577 : CPL_IGNORE_RET_VAL_INT(sqlite3_prepare_v2(hDB, pszSQL, -1, &hStmt, NULL));
957 577 : sqlite3_free(pszSQL);
958 577 : 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 577 : bool bMaxMemReached = false;
966 577 : uint64_t nRows = 0;
967 231634 : while (sqlite3_step(hStmt) == SQLITE_ROW) {
968 231069 : int64_t id = sqlite3_column_int64(hStmt, 0);
969 231069 : const double minx = sqlite3_column_double(hStmt, 1);
970 231069 : const double maxx = sqlite3_column_double(hStmt, 2);
971 231069 : const double miny = sqlite3_column_double(hStmt, 3);
972 231069 : const double maxy = sqlite3_column_double(hStmt, 4);
973 231069 : if (!SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_insert)(t, id, minx, miny, maxx, maxy)) {
974 0 : bMaxMemReached = true;
975 0 : break;
976 : }
977 462138 : if (max_ram_usage != 0 &&
978 231069 : SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_ram_usage)(t) > max_ram_usage) {
979 12 : bMaxMemReached = true;
980 12 : break;
981 : }
982 231057 : 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 577 : 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 577 : SQLITE_RTREE_BL_SYMBOL(sqlite_rtree_bl_free)(t);
1008 :
1009 577 : 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 577 : if (bOK && progress_cbk && (nRows % NOTIFICATION_INTERVAL) != 0)
1064 : {
1065 : char szMsg[256];
1066 393 : snprintf(szMsg, sizeof(szMsg), "%" PRIu64 " rows inserted in %s",
1067 : nRows, rtree_name);
1068 393 : CPL_IGNORE_RET_VAL_INT(progress_cbk(szMsg, progress_cbk_user_data));
1069 : }
1070 :
1071 577 : sqlite3_finalize(hStmt);
1072 577 : return bOK;
1073 : }
|
