PostGIS  3.1.6dev-r@@SVN_REVISION@@
gserialized_gist_2d.c
Go to the documentation of this file.
1 /**********************************************************************
2  *
3  * PostGIS - Spatial Types for PostgreSQL
4  * http://postgis.net
5  *
6  * PostGIS is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * PostGIS is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with PostGIS. If not, see <http://www.gnu.org/licenses/>.
18  *
19  **********************************************************************
20  *
21  * Copyright 2009 Paul Ramsey <pramsey@cleverelephant.ca>
22  * Copyright 2017-2019 Darafei Praliaskouski <me@komzpa.net>
23  *
24  **********************************************************************/
25 
26 /*
27 ** R-Tree Bibliography
28 **
29 ** [1] A. Guttman. R-tree: a dynamic index structure for spatial searching.
30 ** Proceedings of the ACM SIGMOD Conference, pp 47-57, June 1984.
31 ** [2] C.-H. Ang and T. C. Tan. New linear node splitting algorithm for
32 ** R-Trees. Advances in Spatial Databases - 5th International Symposium,
33 ** 1997
34 ** [3] N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger. The R*tree: an
35 ** efficient and robust access method for points and rectangles.
36 ** Proceedings of the ACM SIGMOD Conference. June 1990.
37 ** [4] A. Korotkov, "A new double sorting-based node splitting algorithm for R-tree",
38 ** http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
39 */
40 
41 #include "postgres.h"
42 #include "access/gist.h" /* For GiST */
43 #include "access/itup.h"
44 #include "access/skey.h"
45 
46 #include "../postgis_config.h"
47 
48 #include "liblwgeom.h" /* For standard geometry types. */
49 #include "liblwgeom_internal.h"
50 #include "lwgeom_pg.h" /* For debugging macros. */
51 #include "gserialized_gist.h" /* For utility functions. */
52 
53 #include <float.h> /* For FLT_MAX */
54 #include <math.h>
55 
56 /*
57 ** When is a node split not so good? If more than 90% of the entries
58 ** end up in one of the children.
59 */
60 #define LIMIT_RATIO 0.1
61 
62 /*
63 ** For debugging
64 */
65 #if POSTGIS_DEBUG_LEVEL > 0
66 static int g2d_counter_leaf = 0;
67 static int g2d_counter_internal = 0;
68 #endif
69 
70 /*
71 ** GiST 2D key stubs
72 */
73 Datum box2df_out(PG_FUNCTION_ARGS);
74 Datum box2df_in(PG_FUNCTION_ARGS);
75 
76 /*
77 ** GiST 2D index function prototypes
78 */
79 Datum gserialized_gist_consistent_2d(PG_FUNCTION_ARGS);
80 Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS);
81 Datum gserialized_gist_decompress_2d(PG_FUNCTION_ARGS);
82 Datum gserialized_gist_penalty_2d(PG_FUNCTION_ARGS);
83 Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS);
84 Datum gserialized_gist_union_2d(PG_FUNCTION_ARGS);
85 Datum gserialized_gist_same_2d(PG_FUNCTION_ARGS);
86 Datum gserialized_gist_distance_2d(PG_FUNCTION_ARGS);
87 
88 /*
89 ** GiST 2D operator prototypes
90 */
91 Datum gserialized_same_2d(PG_FUNCTION_ARGS);
92 Datum gserialized_within_2d(PG_FUNCTION_ARGS);
93 Datum gserialized_contains_2d(PG_FUNCTION_ARGS);
94 Datum gserialized_overlaps_2d(PG_FUNCTION_ARGS);
95 Datum gserialized_left_2d(PG_FUNCTION_ARGS);
96 Datum gserialized_right_2d(PG_FUNCTION_ARGS);
97 Datum gserialized_above_2d(PG_FUNCTION_ARGS);
98 Datum gserialized_below_2d(PG_FUNCTION_ARGS);
99 Datum gserialized_overleft_2d(PG_FUNCTION_ARGS);
100 Datum gserialized_overright_2d(PG_FUNCTION_ARGS);
101 Datum gserialized_overabove_2d(PG_FUNCTION_ARGS);
102 Datum gserialized_overbelow_2d(PG_FUNCTION_ARGS);
103 Datum gserialized_distance_box_2d(PG_FUNCTION_ARGS);
104 Datum gserialized_distance_centroid_2d(PG_FUNCTION_ARGS);
105 Datum gserialized_contains_box2df_geom_2d(PG_FUNCTION_ARGS);
106 Datum gserialized_contains_box2df_box2df_2d(PG_FUNCTION_ARGS);
107 Datum gserialized_within_box2df_geom_2d(PG_FUNCTION_ARGS);
108 Datum gserialized_within_box2df_box2df_2d(PG_FUNCTION_ARGS);
109 Datum gserialized_overlaps_box2df_geom_2d(PG_FUNCTION_ARGS);
110 Datum gserialized_overlaps_box2df_box2df_2d(PG_FUNCTION_ARGS);
111 
112 /*
113 ** true/false test function type
114 */
115 typedef bool (*box2df_predicate)(const BOX2DF *a, const BOX2DF *b);
116 
117 
118 static char* box2df_to_string(const BOX2DF *a)
119 {
120  static const int precision = 12;
121  char tmp[13 + 4 * OUT_MAX_BYTES_DOUBLE] = {'B', 'O', 'X', '2', 'D', 'F', '(', 0};
122  int len = 7;
123 
124  if (a == NULL)
125  return pstrdup("<NULLPTR>");
126 
127  len += lwprint_double(a->xmin, precision, &tmp[len]);
128  tmp[len++] = ' ';
129  len += lwprint_double(a->ymin, precision, &tmp[len]);
130  tmp[len++] = ',';
131  tmp[len++] = ' ';
132  len += lwprint_double(a->xmax, precision, &tmp[len]);
133  tmp[len++] = ' ';
134  len += lwprint_double(a->ymax, precision, &tmp[len]);
135  tmp[len++] = ')';
136 
137  return pstrdup(tmp);
138 }
139 
140 /* Allocate a new copy of BOX2DF */
141 BOX2DF* box2df_copy(BOX2DF *b)
142 {
143  BOX2DF *c = (BOX2DF*)palloc(sizeof(BOX2DF));
144  memcpy((void*)c, (void*)b, sizeof(BOX2DF));
145  POSTGIS_DEBUGF(5, "copied box2df (%p) to box2df (%p)", b, c);
146  return c;
147 }
148 
149 inline bool box2df_is_empty(const BOX2DF *a)
150 {
151  if (isnan(a->xmin))
152  return true;
153  else
154  return false;
155 }
156 
157 inline void box2df_set_empty(BOX2DF *a)
158 {
159  a->xmin = a->xmax = a->ymin = a->ymax = NAN;
160  return;
161 }
162 
163 inline void box2df_set_finite(BOX2DF *a)
164 {
165  if ( ! isfinite(a->xmax) )
166  a->xmax = FLT_MAX;
167  if ( ! isfinite(a->ymax) )
168  a->ymax = FLT_MAX;
169  if ( ! isfinite(a->ymin) )
170  a->ymin = -1*FLT_MAX;
171  if ( ! isfinite(a->xmin) )
172  a->xmin = -1*FLT_MAX;
173  return;
174 }
175 
176 /* Enlarge b_union to contain b_new. */
177 void box2df_merge(BOX2DF *b_union, BOX2DF *b_new)
178 {
179 
180  POSTGIS_DEBUGF(5, "merging %s with %s", box2df_to_string(b_union), box2df_to_string(b_new));
181  /* Adjust minimums */
182  if (b_union->xmin > b_new->xmin || isnan(b_union->xmin))
183  b_union->xmin = b_new->xmin;
184  if (b_union->ymin > b_new->ymin || isnan(b_union->ymin))
185  b_union->ymin = b_new->ymin;
186  /* Adjust maximums */
187  if (b_union->xmax < b_new->xmax || isnan(b_union->xmax))
188  b_union->xmax = b_new->xmax;
189  if (b_union->ymax < b_new->ymax || isnan(b_union->ymax))
190  b_union->ymax = b_new->ymax;
191 
192  POSTGIS_DEBUGF(5, "merge complete %s", box2df_to_string(b_union));
193  return;
194 }
195 
196 
197 /* Convert a double-based GBOX into a float-based BOX2DF,
198  ensuring the float box is larger than the double box */
199 static inline int box2df_from_gbox_p(GBOX *box, BOX2DF *a)
200 {
201  a->xmin = next_float_down(box->xmin);
202  a->xmax = next_float_up(box->xmax);
203  a->ymin = next_float_down(box->ymin);
204  a->ymax = next_float_up(box->ymax);
205  return LW_SUCCESS;
206 }
207 
208 int box2df_to_gbox_p(BOX2DF *a, GBOX *box)
209 {
210  memset(box, 0, sizeof(GBOX));
211  box->xmin = a->xmin;
212  box->xmax = a->xmax;
213  box->ymin = a->ymin;
214  box->ymax = a->ymax;
215  return LW_SUCCESS;
216 }
217 
218 /***********************************************************************
219 ** BOX2DF tests for 2D index operators.
220 */
221 
222 /* Ensure all minimums are below maximums. */
223 inline void box2df_validate(BOX2DF *b)
224 {
225  float tmp;
226 
227  if ( box2df_is_empty(b) )
228  return;
229 
230  if ( b->xmax < b->xmin )
231  {
232  tmp = b->xmin;
233  b->xmin = b->xmax;
234  b->xmax = tmp;
235  }
236  if ( b->ymax < b->ymin )
237  {
238  tmp = b->ymin;
239  b->ymin = b->ymax;
240  b->ymax = tmp;
241  }
242  return;
243 }
244 
245 bool box2df_overlaps(const BOX2DF *a, const BOX2DF *b)
246 {
247  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
248  return false;
249 
250  if ( (a->xmin > b->xmax) || (b->xmin > a->xmax) ||
251  (a->ymin > b->ymax) || (b->ymin > a->ymax) )
252  {
253  return false;
254  }
255 
256  return true;
257 }
258 
259 bool box2df_contains(const BOX2DF *a, const BOX2DF *b)
260 {
261  if ( !a || !b )
262  return false;
263 
264  /* All things can contain EMPTY (except EMPTY) */
265  if ( box2df_is_empty(b) && ! box2df_is_empty(a) )
266  return true;
267 
268  if ( (a->xmin > b->xmin) || (a->xmax < b->xmax) ||
269  (a->ymin > b->ymin) || (a->ymax < b->ymax) )
270  {
271  return false;
272  }
273 
274  return true;
275 }
276 
277 static bool box2df_within(const BOX2DF *a, const BOX2DF *b)
278 {
279  if ( !a || !b )
280  return false;
281 
282  /* EMPTY is within all other things (except EMPTY) */
283  if ( box2df_is_empty(a) && ! box2df_is_empty(b) )
284  return true;
285 
286  if ( (a->xmin < b->xmin) || (a->xmax > b->xmax) ||
287  (a->ymin < b->ymin) || (a->ymax > b->ymax) )
288  {
289  return false;
290  }
291 
292  return true;
293 }
294 
295 bool box2df_equals(const BOX2DF *a, const BOX2DF *b)
296 {
297  if ( !a && !b )
298  return true;
299  else if ( !a || !b )
300  return false;
301  else if ( box2df_is_empty(a) && box2df_is_empty(b) )
302  return true;
303  else if ( box2df_is_empty(a) || box2df_is_empty(b) )
304  return false;
305  else if ((a->xmin == b->xmin) && (a->xmax == b->xmax) && (a->ymin == b->ymin) && (a->ymax == b->ymax))
306  return true;
307  else
308  return false;
309 }
310 
311 bool box2df_overleft(const BOX2DF *a, const BOX2DF *b)
312 {
313  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
314  return false;
315 
316  /* a.xmax <= b.xmax */
317  return a->xmax <= b->xmax;
318 }
319 
320 bool box2df_left(const BOX2DF *a, const BOX2DF *b)
321 {
322  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
323  return false;
324 
325  /* a.xmax < b.xmin */
326  return a->xmax < b->xmin;
327 }
328 
329 bool box2df_right(const BOX2DF *a, const BOX2DF *b)
330 {
331  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
332  return false;
333 
334  /* a.xmin > b.xmax */
335  return a->xmin > b->xmax;
336 }
337 
338 bool box2df_overright(const BOX2DF *a, const BOX2DF *b)
339 {
340  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
341  return false;
342 
343  /* a.xmin >= b.xmin */
344  return a->xmin >= b->xmin;
345 }
346 
347 bool box2df_overbelow(const BOX2DF *a, const BOX2DF *b)
348 {
349  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
350  return false;
351 
352  /* a.ymax <= b.ymax */
353  return a->ymax <= b->ymax;
354 }
355 
356 bool box2df_below(const BOX2DF *a, const BOX2DF *b)
357 {
358  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
359  return false;
360 
361  /* a.ymax < b.ymin */
362  return a->ymax < b->ymin;
363 }
364 
365 bool box2df_above(const BOX2DF *a, const BOX2DF *b)
366 {
367  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
368  return false;
369 
370  /* a.ymin > b.ymax */
371  return a->ymin > b->ymax;
372 }
373 
374 bool box2df_overabove(const BOX2DF *a, const BOX2DF *b)
375 {
376  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
377  return false;
378 
379  /* a.ymin >= b.ymin */
380  return a->ymin >= b->ymin;
381 }
382 
386 static double box2df_distance_leaf_centroid(const BOX2DF *a, const BOX2DF *b)
387 {
388  /* The centroid->centroid distance between the boxes */
389  double a_x = (a->xmax + a->xmin) / 2.0;
390  double a_y = (a->ymax + a->ymin) / 2.0;
391  double b_x = (b->xmax + b->xmin) / 2.0;
392  double b_y = (b->ymax + b->ymin) / 2.0;
393 
394  /* This "distance" is only used for comparisons, */
395  return sqrt((a_x - b_x) * (a_x - b_x) + (a_y - b_y) * (a_y - b_y));
396 }
397 
398 /* Quick distance function */
399 static inline double pt_distance(double ax, double ay, double bx, double by)
400 {
401  return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
402 }
403 
407 static double box2df_distance(const BOX2DF *a, const BOX2DF *b)
408 {
409  /* Check for overlap */
410  if ( box2df_overlaps(a, b) )
411  return 0.0;
412 
413  if ( box2df_left(a, b) )
414  {
415  if ( box2df_above(a, b) )
416  return pt_distance(a->xmax, a->ymin, b->xmin, b->ymax);
417  if ( box2df_below(a, b) )
418  return pt_distance(a->xmax, a->ymax, b->xmin, b->ymin);
419  else
420  return (double)b->xmin - (double)a->xmax;
421  }
422  if ( box2df_right(a, b) )
423  {
424  if ( box2df_above(a, b) )
425  return pt_distance(a->xmin, a->ymin, b->xmax, b->ymax);
426  if ( box2df_below(a, b) )
427  return pt_distance(a->xmin, a->ymax, b->xmax, b->ymin);
428  else
429  return (double)a->xmin - (double)b->xmax;
430  }
431  if ( box2df_above(a, b) )
432  {
433  if ( box2df_left(a, b) )
434  return pt_distance(a->xmax, a->ymin, b->xmin, b->ymax);
435  if ( box2df_right(a, b) )
436  return pt_distance(a->xmin, a->ymin, b->xmax, b->ymax);
437  else
438  return (double)a->ymin - (double)b->ymax;
439  }
440  if ( box2df_below(a, b) )
441  {
442  if ( box2df_left(a, b) )
443  return pt_distance(a->xmax, a->ymax, b->xmin, b->ymin);
444  if ( box2df_right(a, b) )
445  return pt_distance(a->xmin, a->ymax, b->xmax, b->ymin);
446  else
447  return (double)b->ymin - (double)a->ymax;
448  }
449 
450  return FLT_MAX;
451 }
452 
458 int
459 gserialized_datum_get_internals_p(Datum gsdatum, GBOX *gbox, lwflags_t *flags, uint8_t *type, int32_t *srid)
460 {
461  int result = LW_SUCCESS;
462  GSERIALIZED *gpart = NULL;
463  int need_detoast = PG_GSERIALIZED_DATUM_NEEDS_DETOAST((struct varlena *)gsdatum);
464  if (need_detoast)
465  {
466  gpart = (GSERIALIZED *)PG_DETOAST_DATUM_SLICE(gsdatum, 0, gserialized_max_header_size());
467  }
468  else
469  {
470  gpart = (GSERIALIZED *)gsdatum;
471  }
472 
473  if (!gserialized_has_bbox(gpart) && need_detoast && LWSIZE_GET(gpart->size) >= gserialized_max_header_size())
474  {
475  /* The headers don't contain a bbox and the object is larger than what we retrieved, so
476  * we now detoast it completely */
477  POSTGIS_FREE_IF_COPY_P(gpart, gsdatum);
478  gpart = (GSERIALIZED *)PG_DETOAST_DATUM(gsdatum);
479  }
480 
481  result = gserialized_get_gbox_p(gpart, gbox);
482  *flags = gserialized_get_lwflags(gpart);
483  *srid = gserialized_get_srid(gpart);
484  *type = gserialized_get_type(gpart);
485 
486  POSTGIS_FREE_IF_COPY_P(gpart, gsdatum);
487  return result;
488 }
489 
497 int
498 gserialized_datum_get_gbox_p(Datum gsdatum, GBOX *gbox)
499 {
500  uint8_t type;
501  int32_t srid;
502  lwflags_t flags;
503 
504  return gserialized_datum_get_internals_p(gsdatum, gbox, &flags, &type, &srid);
505 }
506 
507 /* Note that this duplicates code from gserialized_datum_get_internals_p. It does so because
508  * accessing only the BOX2DF (as floats) is faster and this is a hot path function in indexes
509  */
510 int
511 gserialized_datum_get_box2df_p(Datum gsdatum, BOX2DF *box2df)
512 {
513  int result = LW_SUCCESS;
514  GSERIALIZED *gpart = NULL;
515  int need_detoast = PG_GSERIALIZED_DATUM_NEEDS_DETOAST((struct varlena *)gsdatum);
516  if (need_detoast)
517  {
518  gpart = (GSERIALIZED *)PG_DETOAST_DATUM_SLICE(gsdatum, 0, gserialized_max_header_size());
519  }
520  else
521  {
522  gpart = (GSERIALIZED *)gsdatum;
523  }
524 
525  if (gserialized_has_bbox(gpart))
526  {
527  size_t box_ndims;
528  const float *f = gserialized_get_float_box_p(gpart, &box_ndims);
529  memcpy(box2df, f, sizeof(BOX2DF));
530  result = LW_SUCCESS;
531  }
532  else
533  {
534  GBOX gbox = {0};
535  if (need_detoast && LWSIZE_GET(gpart->size) >= gserialized_max_header_size())
536  {
537  /* The headers don't contain a bbox and the object is larger than what we retrieved, so
538  * we now detoast it completely and recheck */
539  POSTGIS_FREE_IF_COPY_P(gpart, gsdatum);
540  gpart = (GSERIALIZED *)PG_DETOAST_DATUM(gsdatum);
541  }
542  result = gserialized_get_gbox_p(gpart, &gbox);
543  if (result == LW_SUCCESS)
544  {
545  result = box2df_from_gbox_p(&gbox, box2df);
546  }
547  }
548 
549  POSTGIS_FREE_IF_COPY_P(gpart, gsdatum);
550  return result;
551 }
552 
557 static int
558 gserialized_datum_predicate_2d(Datum gs1, Datum gs2, box2df_predicate predicate)
559 {
560  BOX2DF b1, b2, *br1=NULL, *br2=NULL;
561  POSTGIS_DEBUG(3, "entered function");
562 
563  if (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) br1 = &b1;
564  if (gserialized_datum_get_box2df_p(gs2, &b2) == LW_SUCCESS) br2 = &b2;
565 
566  if ( predicate(br1, br2) )
567  {
568  POSTGIS_DEBUGF(3, "got boxes %s and %s", br1 ? box2df_to_string(&b1) : "(null)", br2 ? box2df_to_string(&b2) : "(null)");
569  return LW_TRUE;
570  }
571  return LW_FALSE;
572 }
573 
574 static int
575 gserialized_datum_predicate_box2df_geom_2d(const BOX2DF *br1, Datum gs2, box2df_predicate predicate)
576 {
577  BOX2DF b2, *br2=NULL;
578  POSTGIS_DEBUG(3, "entered function");
579 
580  if (gserialized_datum_get_box2df_p(gs2, &b2) == LW_SUCCESS) br2 = &b2;
581 
582  if ( predicate(br1, br2) )
583  {
584  POSTGIS_DEBUGF(3, "got boxes %s", br2 ? box2df_to_string(&b2) : "(null)");
585  return LW_TRUE;
586  }
587  return LW_FALSE;
588 }
589 
590 /***********************************************************************
591 * BRIN 2-D Index Operator Functions
592 */
593 
595 Datum gserialized_contains_box2df_geom_2d(PG_FUNCTION_ARGS)
596 {
597  POSTGIS_DEBUG(3, "entered function");
598  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_contains) == LW_TRUE )
599  PG_RETURN_BOOL(true);
600 
601  PG_RETURN_BOOL(false);
602 }
603 
606 {
607  if ( box2df_contains((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
608  PG_RETURN_BOOL(true);
609 
610  PG_RETURN_BOOL(false);
611 }
612 
614 Datum gserialized_within_box2df_geom_2d(PG_FUNCTION_ARGS)
615 {
616  POSTGIS_DEBUG(3, "entered function");
617  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_within) == LW_TRUE )
618  PG_RETURN_BOOL(true);
619 
620  PG_RETURN_BOOL(false);
621 }
622 
624 Datum gserialized_within_box2df_box2df_2d(PG_FUNCTION_ARGS)
625 {
626  if ( box2df_within((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
627  PG_RETURN_BOOL(true);
628 
629  PG_RETURN_BOOL(false);
630 }
631 
633 Datum gserialized_overlaps_box2df_geom_2d(PG_FUNCTION_ARGS)
634 {
635  POSTGIS_DEBUG(3, "entered function");
636  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_overlaps) == LW_TRUE )
637  PG_RETURN_BOOL(true);
638 
639  PG_RETURN_BOOL(false);
640 }
641 
644 {
645  if ( box2df_overlaps((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
646  PG_RETURN_BOOL(true);
647 
648  PG_RETURN_BOOL(false);
649 }
650 
651 /***********************************************************************
652 * GiST 2-D Index Operator Functions
653 */
654 
656 Datum gserialized_distance_centroid_2d(PG_FUNCTION_ARGS)
657 {
658  BOX2DF b1, b2;
659  Datum gs1 = PG_GETARG_DATUM(0);
660  Datum gs2 = PG_GETARG_DATUM(1);
661 
662  POSTGIS_DEBUG(3, "entered function");
663 
664  /* Must be able to build box for each argument (ie, not empty geometry). */
665  if ( (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) &&
667  {
668  double distance = box2df_distance_leaf_centroid(&b1, &b2);
669  POSTGIS_DEBUGF(3, "got boxes %s and %s", box2df_to_string(&b1), box2df_to_string(&b2));
670  PG_RETURN_FLOAT8(distance);
671  }
672  PG_RETURN_FLOAT8(FLT_MAX);
673 }
674 
676 Datum gserialized_distance_box_2d(PG_FUNCTION_ARGS)
677 {
678  BOX2DF b1, b2;
679  Datum gs1 = PG_GETARG_DATUM(0);
680  Datum gs2 = PG_GETARG_DATUM(1);
681 
682  POSTGIS_DEBUG(3, "entered function");
683 
684  /* Must be able to build box for each argument (ie, not empty geometry). */
685  if ( (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) &&
687  {
688  double distance = box2df_distance(&b1, &b2);
689  POSTGIS_DEBUGF(3, "got boxes %s and %s", box2df_to_string(&b1), box2df_to_string(&b2));
690  PG_RETURN_FLOAT8(distance);
691  }
692  PG_RETURN_FLOAT8(FLT_MAX);
693 }
694 
696 Datum gserialized_same_2d(PG_FUNCTION_ARGS)
697 {
698  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_equals) == LW_TRUE )
699  PG_RETURN_BOOL(true);
700 
701  PG_RETURN_BOOL(false);
702 }
703 
705 Datum gserialized_within_2d(PG_FUNCTION_ARGS)
706 {
707  POSTGIS_DEBUG(3, "entered function");
708  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_within) == LW_TRUE )
709  PG_RETURN_BOOL(true);
710 
711  PG_RETURN_BOOL(false);
712 }
713 
715 Datum gserialized_contains_2d(PG_FUNCTION_ARGS)
716 {
717  POSTGIS_DEBUG(3, "entered function");
718  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_contains) == LW_TRUE )
719  PG_RETURN_BOOL(true);
720 
721  PG_RETURN_BOOL(false);
722 }
723 
725 Datum gserialized_overlaps_2d(PG_FUNCTION_ARGS)
726 {
727  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overlaps) == LW_TRUE )
728  PG_RETURN_BOOL(true);
729 
730  PG_RETURN_BOOL(false);
731 }
732 
734 Datum gserialized_left_2d(PG_FUNCTION_ARGS)
735 {
736  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_left) == LW_TRUE )
737  PG_RETURN_BOOL(true);
738 
739  PG_RETURN_BOOL(false);
740 }
741 
743 Datum gserialized_right_2d(PG_FUNCTION_ARGS)
744 {
745  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_right) == LW_TRUE )
746  PG_RETURN_BOOL(true);
747 
748  PG_RETURN_BOOL(false);
749 }
750 
752 Datum gserialized_above_2d(PG_FUNCTION_ARGS)
753 {
754  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_above) == LW_TRUE )
755  PG_RETURN_BOOL(true);
756 
757  PG_RETURN_BOOL(false);
758 }
759 
761 Datum gserialized_below_2d(PG_FUNCTION_ARGS)
762 {
763  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_below) == LW_TRUE )
764  PG_RETURN_BOOL(true);
765 
766  PG_RETURN_BOOL(false);
767 }
768 
770 Datum gserialized_overleft_2d(PG_FUNCTION_ARGS)
771 {
772  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overleft) == LW_TRUE )
773  PG_RETURN_BOOL(true);
774 
775  PG_RETURN_BOOL(false);
776 }
777 
779 Datum gserialized_overright_2d(PG_FUNCTION_ARGS)
780 {
781  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overright) == LW_TRUE )
782  PG_RETURN_BOOL(true);
783 
784  PG_RETURN_BOOL(false);
785 }
786 
788 Datum gserialized_overabove_2d(PG_FUNCTION_ARGS)
789 {
790  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overabove) == LW_TRUE )
791  PG_RETURN_BOOL(true);
792 
793  PG_RETURN_BOOL(false);
794 }
795 
797 Datum gserialized_overbelow_2d(PG_FUNCTION_ARGS)
798 {
799  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overbelow) == LW_TRUE )
800  PG_RETURN_BOOL(true);
801 
802  PG_RETURN_BOOL(false);
803 }
804 
805 
806 /***********************************************************************
807 * GiST Index Support Functions
808 */
809 
810 /*
811 ** GiST support function. Given a geography, return a "compressed"
812 ** version. In this case, we convert the geography into a geocentric
813 ** bounding box. If the geography already has the box embedded in it
814 ** we pull that out and hand it back.
815 */
817 Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS)
818 {
819  GISTENTRY *entry_in = (GISTENTRY*)PG_GETARG_POINTER(0);
820  GISTENTRY *entry_out = NULL;
821  BOX2DF bbox_out;
822  int result = LW_SUCCESS;
823 
824  POSTGIS_DEBUG(4, "[GIST] 'compress' function called");
825 
826  /*
827  ** Not a leaf key? There's nothing to do.
828  ** Return the input unchanged.
829  */
830  if ( ! entry_in->leafkey )
831  {
832  POSTGIS_DEBUG(4, "[GIST] non-leafkey entry, returning input unaltered");
833  PG_RETURN_POINTER(entry_in);
834  }
835 
836  POSTGIS_DEBUG(4, "[GIST] processing leafkey input");
837  entry_out = palloc(sizeof(GISTENTRY));
838 
839  /*
840  ** Null key? Make a copy of the input entry and
841  ** return.
842  */
843  if ( DatumGetPointer(entry_in->key) == NULL )
844  {
845  POSTGIS_DEBUG(4, "[GIST] leafkey is null");
846  gistentryinit(*entry_out, (Datum) 0, entry_in->rel,
847  entry_in->page, entry_in->offset, false);
848  POSTGIS_DEBUG(4, "[GIST] returning copy of input");
849  PG_RETURN_POINTER(entry_out);
850  }
851 
852  /* Extract our index key from the GiST entry. */
853  result = gserialized_datum_get_box2df_p(entry_in->key, &bbox_out);
854 
855  /* Is the bounding box valid (non-empty, non-infinite)? If not, return input uncompressed. */
856  if ( result == LW_FAILURE )
857  {
858  box2df_set_empty(&bbox_out);
859  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
860  entry_in->rel, entry_in->page, entry_in->offset, false);
861 
862  POSTGIS_DEBUG(4, "[GIST] empty geometry!");
863  PG_RETURN_POINTER(entry_out);
864  }
865 
866  POSTGIS_DEBUGF(4, "[GIST] got entry_in->key: %s", box2df_to_string(&bbox_out));
867 
868  /* Check all the dimensions for finite values */
869  if ( ! isfinite(bbox_out.xmax) || ! isfinite(bbox_out.xmin) ||
870  ! isfinite(bbox_out.ymax) || ! isfinite(bbox_out.ymin) )
871  {
872  box2df_set_finite(&bbox_out);
873  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
874  entry_in->rel, entry_in->page, entry_in->offset, false);
875 
876  POSTGIS_DEBUG(4, "[GIST] infinite geometry!");
877  PG_RETURN_POINTER(entry_out);
878  }
879 
880  /* Enure bounding box has minimums below maximums. */
881  box2df_validate(&bbox_out);
882 
883  /* Prepare GISTENTRY for return. */
884  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
885  entry_in->rel, entry_in->page, entry_in->offset, false);
886 
887  /* Return GISTENTRY. */
888  POSTGIS_DEBUG(4, "[GIST] 'compress' function complete");
889  PG_RETURN_POINTER(entry_out);
890 }
891 
892 
893 /*
894 ** GiST support function.
895 ** Decompress an entry. Unused for geography, so we return.
896 */
898 Datum gserialized_gist_decompress_2d(PG_FUNCTION_ARGS)
899 {
900  POSTGIS_DEBUG(5, "[GIST] 'decompress' function called");
901  /* We don't decompress. Just return the input. */
902  PG_RETURN_POINTER(PG_GETARG_POINTER(0));
903 }
904 
905 
906 
907 /*
908 ** GiST support function. Called from gserialized_gist_consistent below.
909 */
910 static inline bool gserialized_gist_consistent_leaf_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
911 {
912  bool retval;
913 
914  POSTGIS_DEBUGF(4, "[GIST] leaf consistent, strategy [%d], count[%i]",
915  strategy, g2d_counter_leaf++);
916 
917  switch (strategy)
918  {
919 
920  /* Basic overlaps */
921  case RTOverlapStrategyNumber:
922  retval = (bool) box2df_overlaps(key, query);
923  break;
924  case RTSameStrategyNumber:
925  retval = (bool) box2df_equals(key, query);
926  break;
927  case RTContainsStrategyNumber:
928  case RTOldContainsStrategyNumber:
929  retval = (bool) box2df_contains(key, query);
930  break;
931  case RTContainedByStrategyNumber:
932  case RTOldContainedByStrategyNumber:
933  retval = (bool) box2df_within(key, query);
934  break;
935 
936  /* To one side */
937  case RTAboveStrategyNumber:
938  retval = (bool) box2df_above(key, query);
939  break;
940  case RTBelowStrategyNumber:
941  retval = (bool) box2df_below(key, query);
942  break;
943  case RTRightStrategyNumber:
944  retval = (bool) box2df_right(key, query);
945  break;
946  case RTLeftStrategyNumber:
947  retval = (bool) box2df_left(key, query);
948  break;
949 
950  /* Overlapping to one side */
951  case RTOverAboveStrategyNumber:
952  retval = (bool) box2df_overabove(key, query);
953  break;
954  case RTOverBelowStrategyNumber:
955  retval = (bool) box2df_overbelow(key, query);
956  break;
957  case RTOverRightStrategyNumber:
958  retval = (bool) box2df_overright(key, query);
959  break;
960  case RTOverLeftStrategyNumber:
961  retval = (bool) box2df_overleft(key, query);
962  break;
963 
964  default:
965  retval = false;
966  }
967 
968  return (retval);
969 }
970 
971 /*
972 ** GiST support function. Called from gserialized_gist_consistent below.
973 */
974 static inline bool gserialized_gist_consistent_internal_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
975 {
976  bool retval;
977 
978  POSTGIS_DEBUGF(4, "[GIST] internal consistent, strategy [%d], count[%i], query[%s], key[%s]",
979  strategy, g2d_counter_internal++, box2df_to_string(query), box2df_to_string(key) );
980 
981  switch (strategy)
982  {
983 
984  /* Basic overlaps */
985  case RTOverlapStrategyNumber:
986  retval = (bool) box2df_overlaps(key, query);
987  break;
988  case RTSameStrategyNumber:
989  case RTContainsStrategyNumber:
990  case RTOldContainsStrategyNumber:
991  retval = (bool) box2df_contains(key, query);
992  break;
993  case RTContainedByStrategyNumber:
994  case RTOldContainedByStrategyNumber:
995  retval = (bool) box2df_overlaps(key, query);
996  break;
997 
998  /* To one side */
999  case RTAboveStrategyNumber:
1000  retval = (bool)(!box2df_overbelow(key, query));
1001  break;
1002  case RTBelowStrategyNumber:
1003  retval = (bool)(!box2df_overabove(key, query));
1004  break;
1005  case RTRightStrategyNumber:
1006  retval = (bool)(!box2df_overleft(key, query));
1007  break;
1008  case RTLeftStrategyNumber:
1009  retval = (bool)(!box2df_overright(key, query));
1010  break;
1011 
1012  /* Overlapping to one side */
1013  case RTOverAboveStrategyNumber:
1014  retval = (bool)(!box2df_below(key, query));
1015  break;
1016  case RTOverBelowStrategyNumber:
1017  retval = (bool)(!box2df_above(key, query));
1018  break;
1019  case RTOverRightStrategyNumber:
1020  retval = (bool)(!box2df_left(key, query));
1021  break;
1022  case RTOverLeftStrategyNumber:
1023  retval = (bool)(!box2df_right(key, query));
1024  break;
1025 
1026  default:
1027  retval = false;
1028  }
1029 
1030  return (retval);
1031 }
1032 
1033 /*
1034 ** GiST support function. Take in a query and an entry and see what the
1035 ** relationship is, based on the query strategy.
1036 */
1038 Datum gserialized_gist_consistent_2d(PG_FUNCTION_ARGS)
1039 {
1040  GISTENTRY *entry = (GISTENTRY*) PG_GETARG_POINTER(0);
1041  StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1042  bool result;
1043  BOX2DF query_gbox_index;
1044 
1045  /* PostgreSQL 8.4 and later require the RECHECK flag to be set here,
1046  rather than being supplied as part of the operator class definition */
1047  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1048 
1049  /* We set recheck to false to avoid repeatedly pulling every "possibly matched" geometry
1050  out during index scans. For cases when the geometries are large, rechecking
1051  can make things twice as slow. */
1052  *recheck = false;
1053 
1054  POSTGIS_DEBUG(4, "[GIST] 'consistent' function called");
1055 
1056  /* Quick sanity check on query argument. */
1057  if ( DatumGetPointer(PG_GETARG_DATUM(1)) == NULL )
1058  {
1059  POSTGIS_DEBUG(4, "[GIST] null query pointer (!?!), returning false");
1060  PG_RETURN_BOOL(false); /* NULL query! This is screwy! */
1061  }
1062 
1063  /* Quick sanity check on entry key. */
1064  if ( DatumGetPointer(entry->key) == NULL )
1065  {
1066  POSTGIS_DEBUG(4, "[GIST] null index entry, returning false");
1067  PG_RETURN_BOOL(false); /* NULL entry! */
1068  }
1069 
1070  /* Null box should never make this far. */
1071  if ( gserialized_datum_get_box2df_p(PG_GETARG_DATUM(1), &query_gbox_index) == LW_FAILURE )
1072  {
1073  POSTGIS_DEBUG(4, "[GIST] null query_gbox_index!");
1074  PG_RETURN_BOOL(false);
1075  }
1076 
1077  /* Treat leaf node tests different from internal nodes */
1078  if (GIST_LEAF(entry))
1079  {
1081  (BOX2DF*)DatumGetPointer(entry->key),
1082  &query_gbox_index, strategy);
1083  }
1084  else
1085  {
1087  (BOX2DF*)DatumGetPointer(entry->key),
1088  &query_gbox_index, strategy);
1089  }
1090 
1091  PG_RETURN_BOOL(result);
1092 }
1093 
1094 
1095 /*
1096 ** GiST support function. Take in a query and an entry and return the "distance"
1097 ** between them.
1098 **
1099 ** Given an index entry p and a query value q, this function determines the
1100 ** index entry's "distance" from the query value. This function must be
1101 ** supplied if the operator class contains any ordering operators. A query
1102 ** using the ordering operator will be implemented by returning index entries
1103 ** with the smallest "distance" values first, so the results must be consistent
1104 ** with the operator's semantics. For a leaf index entry the result just
1105 ** represents the distance to the index entry; for an internal tree node, the
1106 ** result must be the smallest distance that any child entry could have.
1107 **
1108 ** Strategy 13 = true distance tests <->
1109 ** Strategy 14 = box-based distance tests <#>
1110 */
1112 Datum gserialized_gist_distance_2d(PG_FUNCTION_ARGS)
1113 {
1114  GISTENTRY *entry = (GISTENTRY*) PG_GETARG_POINTER(0);
1115  BOX2DF query_box;
1116  BOX2DF *entry_box;
1117  StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1118  double distance;
1119  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1120 
1121  POSTGIS_DEBUG(4, "[GIST] 'distance' function called");
1122 
1123  /* We are using '13' as the gist true-distance <-> strategy number
1124  * and '14' as the gist distance-between-boxes <#> strategy number */
1125  if ( strategy != 13 && strategy != 14 ) {
1126  elog(ERROR, "unrecognized strategy number: %d", strategy);
1127  PG_RETURN_FLOAT8(FLT_MAX);
1128  }
1129 
1130  /* Null box should never make this far. */
1131  if ( gserialized_datum_get_box2df_p(PG_GETARG_DATUM(1), &query_box) == LW_FAILURE )
1132  {
1133  POSTGIS_DEBUG(4, "[GIST] null query_gbox_index!");
1134  PG_RETURN_FLOAT8(FLT_MAX);
1135  }
1136 
1137  /* Get the entry box */
1138  entry_box = (BOX2DF*)DatumGetPointer(entry->key);
1139 
1140  /* Box-style distance test */
1141  if ( strategy == 14 ) /* operator <#> */
1142  {
1143  distance = box2df_distance(entry_box, &query_box);
1144  }
1145  /* True distance test (formerly centroid distance) */
1146  else if ( strategy == 13 ) /* operator <-> */
1147  {
1148  /* In all cases, since we only have keys (boxes) we'll return */
1149  /* the minimum possible distance, which is the box2df_distance */
1150  /* and let the recheck sort things out in the case of leaves */
1151  distance = box2df_distance(entry_box, &query_box);
1152 
1153  if (GIST_LEAF(entry))
1154  *recheck = true;
1155  }
1156  else
1157  {
1158  elog(ERROR, "%s: reached unreachable code", __func__);
1159  PG_RETURN_NULL();
1160  }
1161 
1162  PG_RETURN_FLOAT8(distance);
1163 }
1164 
1165 /*
1166 ** Function to pack floats of different realms.
1167 ** This function serves to pack bit flags inside float type.
1168 ** Result value represent can be from two different "realms".
1169 ** Every value from realm 1 is greater than any value from realm 0.
1170 ** Values from the same realm loose one bit of precision.
1171 **
1172 ** This technique is possible due to floating point numbers specification
1173 ** according to IEEE 754: exponent bits are highest
1174 ** (excluding sign bits, but here penalty is always positive). If float a is
1175 ** greater than float b, integer A with same bit representation as a is greater
1176 ** than integer B with same bits as b.
1177 */
1178 static inline float
1179 pack_float(const float value, const uint8_t realm)
1180 {
1181  union {
1182  float f;
1183  struct {
1184  unsigned value : 31, sign : 1;
1185  } vbits;
1186  struct {
1187  unsigned value : 30, realm : 1, sign : 1;
1188  } rbits;
1189  } a;
1190 
1191  a.f = value;
1192  a.rbits.value = a.vbits.value >> 1;
1193  a.rbits.realm = realm;
1194 
1195  return a.f;
1196 }
1197 
1198 static inline float
1199 box2df_penalty(const BOX2DF *b1, const BOX2DF *b2)
1200 {
1201  float b1xmin = b1->xmin, b1xmax = b1->xmax;
1202  float b1ymin = b1->ymin, b1ymax = b1->ymax;
1203  float b2xmin = b2->xmin, b2xmax = b2->xmax;
1204  float b2ymin = b2->ymin, b2ymax = b2->ymax;
1205 
1206  float box_union_xmin = Min(b1xmin, b2xmin), box_union_xmax = Max(b1xmax, b2xmax);
1207  float box_union_ymin = Min(b1ymin, b2ymin), box_union_ymax = Max(b1ymax, b2ymax);
1208 
1209  float b1dx = b1xmax - b1xmin, b1dy = b1ymax - b1ymin;
1210  float box_union_dx = box_union_xmax - box_union_xmin, box_union_dy = box_union_ymax - box_union_ymin;
1211 
1212  float box_union_area = box_union_dx * box_union_dy, box1area = b1dx * b1dy;
1213  float box_union_edge = box_union_dx + box_union_dy, box1edge = b1dx + b1dy;
1214 
1215  float area_extension = box_union_area - box1area;
1216  float edge_extension = box_union_edge - box1edge;
1217 
1218  /* REALM 1: Area extension is nonzero, return it */
1219  if (area_extension > FLT_EPSILON)
1220  return pack_float(area_extension, 1);
1221  /* REALM 0: Area extension is zero, return nonzero edge extension */
1222  else if (edge_extension > FLT_EPSILON)
1223  return pack_float(edge_extension, 0);
1224 
1225  return 0;
1226 }
1227 
1228 /*
1229 ** GiST support function. Calculate the "penalty" cost of adding this entry into an existing entry.
1230 ** Calculate the change in volume of the old entry once the new entry is added.
1231 */
1233 Datum gserialized_gist_penalty_2d(PG_FUNCTION_ARGS)
1234 {
1235  GISTENTRY *origentry = (GISTENTRY*) PG_GETARG_POINTER(0);
1236  GISTENTRY *newentry = (GISTENTRY*) PG_GETARG_POINTER(1);
1237  float *result = (float*) PG_GETARG_POINTER(2);
1238  BOX2DF *b1, *b2;
1239 
1240  b1 = (BOX2DF *)DatumGetPointer(origentry->key);
1241  b2 = (BOX2DF *)DatumGetPointer(newentry->key);
1242 
1243  /* Penalty value of 0 has special code path in Postgres's gistchoose.
1244  * It is used as an early exit condition in subtree loop, allowing faster tree descend.
1245  * For multi-column index, it lets next column break the tie, possibly more confidently.
1246  */
1247  *result = 0;
1248 
1249  if (b1 && b2 && !box2df_is_empty(b1) && !box2df_is_empty(b2))
1250  *result = box2df_penalty(b1, b2);
1251 
1252  PG_RETURN_POINTER(result);
1253 }
1254 
1255 /*
1256 ** GiST support function. Merge all the boxes in a page into one master box.
1257 */
1259 Datum gserialized_gist_union_2d(PG_FUNCTION_ARGS)
1260 {
1261  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1262  int *sizep = (int *) PG_GETARG_POINTER(1); /* Size of the return value */
1263  int numranges, i;
1264  BOX2DF *box_cur, *box_union;
1265 
1266  POSTGIS_DEBUG(4, "[GIST] 'union' function called");
1267 
1268  numranges = entryvec->n;
1269 
1270  box_cur = (BOX2DF*) DatumGetPointer(entryvec->vector[0].key);
1271 
1272  box_union = box2df_copy(box_cur);
1273 
1274  for ( i = 1; i < numranges; i++ )
1275  {
1276  box_cur = (BOX2DF*) DatumGetPointer(entryvec->vector[i].key);
1277  box2df_merge(box_union, box_cur);
1278  }
1279 
1280  *sizep = sizeof(BOX2DF);
1281 
1282  POSTGIS_DEBUGF(4, "[GIST] 'union', numranges(%i), pageunion %s", numranges, box2df_to_string(box_union));
1283 
1284  PG_RETURN_POINTER(box_union);
1285 
1286 }
1287 
1288 /*
1289 ** GiST support function. Test equality of keys.
1290 */
1292 Datum gserialized_gist_same_2d(PG_FUNCTION_ARGS)
1293 {
1294  BOX2DF *b1 = (BOX2DF*)PG_GETARG_POINTER(0);
1295  BOX2DF *b2 = (BOX2DF*)PG_GETARG_POINTER(1);
1296  bool *result = (bool*)PG_GETARG_POINTER(2);
1297 
1298  POSTGIS_DEBUG(4, "[GIST] 'same' function called");
1299 
1300  *result = box2df_equals(b1, b2);
1301 
1302  PG_RETURN_POINTER(result);
1303 }
1304 
1305 /*
1306  * Adjust BOX2DF b boundaries with insertion of addon.
1307  */
1308 static void
1309 adjustBox(BOX2DF *b, BOX2DF *addon)
1310 {
1311  if (b->xmax < addon->xmax || isnan(b->xmax))
1312  b->xmax = addon->xmax;
1313  if (b->xmin > addon->xmin || isnan(b->xmin))
1314  b->xmin = addon->xmin;
1315  if (b->ymax < addon->ymax || isnan(b->ymax))
1316  b->ymax = addon->ymax;
1317  if (b->ymin > addon->ymin || isnan(b->ymin))
1318  b->ymin = addon->ymin;
1319 }
1320 
1321 /*
1322  * Trivial split: half of entries will be placed on one page
1323  * and another half - to another
1324  */
1325 static void
1326 fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
1327 {
1328  OffsetNumber i,
1329  maxoff;
1330  BOX2DF *unionL = NULL,
1331  *unionR = NULL;
1332  int nbytes;
1333 
1334  maxoff = entryvec->n - 1;
1335 
1336  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
1337  v->spl_left = (OffsetNumber *) palloc(nbytes);
1338  v->spl_right = (OffsetNumber *) palloc(nbytes);
1339  v->spl_nleft = v->spl_nright = 0;
1340 
1341  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1342  {
1343  BOX2DF *cur = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1344 
1345  if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
1346  {
1347  v->spl_left[v->spl_nleft] = i;
1348  if (unionL == NULL)
1349  {
1350  unionL = (BOX2DF *) palloc(sizeof(BOX2DF));
1351  *unionL = *cur;
1352  }
1353  else
1354  adjustBox(unionL, cur);
1355 
1356  v->spl_nleft++;
1357  }
1358  else
1359  {
1360  v->spl_right[v->spl_nright] = i;
1361  if (unionR == NULL)
1362  {
1363  unionR = (BOX2DF *) palloc(sizeof(BOX2DF));
1364  *unionR = *cur;
1365  }
1366  else
1367  adjustBox(unionR, cur);
1368 
1369  v->spl_nright++;
1370  }
1371  }
1372 
1373  if (v->spl_ldatum_exists)
1374  adjustBox(unionL, (BOX2DF *) DatumGetPointer(v->spl_ldatum));
1375  v->spl_ldatum = BoxPGetDatum(unionL);
1376 
1377  if (v->spl_rdatum_exists)
1378  adjustBox(unionR, (BOX2DF *) DatumGetPointer(v->spl_rdatum));
1379  v->spl_rdatum = BoxPGetDatum(unionR);
1380 
1381  v->spl_ldatum_exists = v->spl_rdatum_exists = false;
1382 }
1383 
1384 /*
1385  * Represents information about an entry that can be placed to either group
1386  * without affecting overlap over selected axis ("common entry").
1387  */
1388 typedef struct
1389 {
1390  /* Index of entry in the initial array */
1391  int index;
1392  /* Delta between penalties of entry insertion into different groups */
1393  float delta;
1394 } CommonEntry;
1395 
1396 /*
1397  * Context for g_box_consider_split. Contains information about currently
1398  * selected split and some general information.
1399  */
1400 typedef struct
1401 {
1402  int entriesCount; /* total number of entries being split */
1403  BOX2DF boundingBox; /* minimum bounding box across all entries */
1404 
1405  /* Information about currently selected split follows */
1406 
1407  bool first; /* true if no split was selected yet */
1408 
1409  float leftUpper; /* upper bound of left interval */
1410  float rightLower; /* lower bound of right interval */
1411 
1412  float4 ratio;
1413  float4 overlap;
1414  int dim; /* axis of this split */
1415  float range; /* width of general MBR projection to the
1416  * selected axis */
1418 
1419 /*
1420  * Interval represents projection of box to axis.
1421  */
1422 typedef struct
1423 {
1424  float lower,
1426 } SplitInterval;
1427 
1428 /*
1429  * Interval comparison function by lower bound of the interval;
1430  */
1431 static int
1432 interval_cmp_lower(const void *i1, const void *i2)
1433 {
1434  float lower1 = ((const SplitInterval *) i1)->lower,
1435  lower2 = ((const SplitInterval *) i2)->lower;
1436 
1437  if (isnan(lower1))
1438  {
1439  if (isnan(lower2))
1440  return 0;
1441  else
1442  return 1;
1443  }
1444  else if (isnan(lower2))
1445  {
1446  return -1;
1447  }
1448  else
1449  {
1450  if (lower1 < lower2)
1451  return -1;
1452  else if (lower1 > lower2)
1453  return 1;
1454  else
1455  return 0;
1456  }
1457 }
1458 
1459 
1460 /*
1461  * Interval comparison function by upper bound of the interval;
1462  */
1463 static int
1464 interval_cmp_upper(const void *i1, const void *i2)
1465 {
1466  float upper1 = ((const SplitInterval *) i1)->upper,
1467  upper2 = ((const SplitInterval *) i2)->upper;
1468 
1469  if (isnan(upper1))
1470  {
1471  if (isnan(upper2))
1472  return 0;
1473  else
1474  return -1;
1475  }
1476  else if (isnan(upper2))
1477  {
1478  return 1;
1479  }
1480  else
1481  {
1482  if (upper1 < upper2)
1483  return -1;
1484  else if (upper1 > upper2)
1485  return 1;
1486  else
1487  return 0;
1488  }
1489 }
1490 
1491 /*
1492  * Replace negative value with zero.
1493  */
1494 static inline float
1495 non_negative(float val)
1496 {
1497  if (val >= 0.0f)
1498  return val;
1499  else
1500  return 0.0f;
1501 }
1502 
1503 /*
1504  * Consider replacement of currently selected split with the better one.
1505  */
1506 static inline void
1508  float rightLower, int minLeftCount,
1509  float leftUpper, int maxLeftCount)
1510 {
1511  int leftCount,
1512  rightCount;
1513  float4 ratio,
1514  overlap;
1515  float range;
1516 
1517  POSTGIS_DEBUGF(5, "consider split: dimNum = %d, rightLower = %f, "
1518  "minLeftCount = %d, leftUpper = %f, maxLeftCount = %d ",
1519  dimNum, rightLower, minLeftCount, leftUpper, maxLeftCount);
1520 
1521  /*
1522  * Calculate entries distribution ratio assuming most uniform distribution
1523  * of common entries.
1524  */
1525  if (minLeftCount >= (context->entriesCount + 1) / 2)
1526  {
1527  leftCount = minLeftCount;
1528  }
1529  else
1530  {
1531  if (maxLeftCount <= context->entriesCount / 2)
1532  leftCount = maxLeftCount;
1533  else
1534  leftCount = context->entriesCount / 2;
1535  }
1536  rightCount = context->entriesCount - leftCount;
1537 
1538  /*
1539  * Ratio of split - quotient between size of lesser group and total
1540  * entries count.
1541  */
1542  ratio = ((float4) Min(leftCount, rightCount)) /
1543  ((float4) context->entriesCount);
1544 
1545  if (ratio > LIMIT_RATIO)
1546  {
1547  bool selectthis = false;
1548 
1549  /*
1550  * The ratio is acceptable, so compare current split with previously
1551  * selected one. Between splits of one dimension we search for minimal
1552  * overlap (allowing negative values) and minimal ration (between same
1553  * overlaps. We switch dimension if find less overlap (non-negative)
1554  * or less range with same overlap.
1555  */
1556  if (dimNum == 0)
1557  range = context->boundingBox.xmax - context->boundingBox.xmin;
1558  else
1559  range = context->boundingBox.ymax - context->boundingBox.ymin;
1560 
1561  overlap = (leftUpper - rightLower) / range;
1562 
1563  /* If there is no previous selection, select this */
1564  if (context->first)
1565  selectthis = true;
1566  else if (context->dim == dimNum)
1567  {
1568  /*
1569  * Within the same dimension, choose the new split if it has a
1570  * smaller overlap, or same overlap but better ratio.
1571  */
1572  if (overlap < context->overlap ||
1573  (overlap == context->overlap && ratio > context->ratio))
1574  selectthis = true;
1575  }
1576  else
1577  {
1578  /*
1579  * Across dimensions, choose the new split if it has a smaller
1580  * *non-negative* overlap, or same *non-negative* overlap but
1581  * bigger range. This condition differs from the one described in
1582  * the article. On the datasets where leaf MBRs don't overlap
1583  * themselves, non-overlapping splits (i.e. splits which have zero
1584  * *non-negative* overlap) are frequently possible. In this case
1585  * splits tends to be along one dimension, because most distant
1586  * non-overlapping splits (i.e. having lowest negative overlap)
1587  * appears to be in the same dimension as in the previous split.
1588  * Therefore MBRs appear to be very prolonged along another
1589  * dimension, which leads to bad search performance. Using range
1590  * as the second split criteria makes MBRs more quadratic. Using
1591  * *non-negative* overlap instead of overlap as the first split
1592  * criteria gives to range criteria a chance to matter, because
1593  * non-overlapping splits are equivalent in this criteria.
1594  */
1595  if (non_negative(overlap) < non_negative(context->overlap) ||
1596  (range > context->range &&
1597  non_negative(overlap) <= non_negative(context->overlap)))
1598  selectthis = true;
1599  }
1600 
1601  if (selectthis)
1602  {
1603  /* save information about selected split */
1604  context->first = false;
1605  context->ratio = ratio;
1606  context->range = range;
1607  context->overlap = overlap;
1608  context->rightLower = rightLower;
1609  context->leftUpper = leftUpper;
1610  context->dim = dimNum;
1611  POSTGIS_DEBUG(5, "split selected");
1612  }
1613  }
1614 }
1615 
1616 /*
1617  * Compare common entries by their deltas.
1618  */
1619 static int
1620 common_entry_cmp(const void *i1, const void *i2)
1621 {
1622  float delta1 = ((const CommonEntry *) i1)->delta,
1623  delta2 = ((const CommonEntry *) i2)->delta;
1624 
1625  if (delta1 < delta2)
1626  return -1;
1627  else if (delta1 > delta2)
1628  return 1;
1629  else
1630  return 0;
1631 }
1632 
1633 /*
1634  * --------------------------------------------------------------------------
1635  * Double sorting split algorithm. This is used for both boxes and points.
1636  *
1637  * The algorithm finds split of boxes by considering splits along each axis.
1638  * Each entry is first projected as an interval on the X-axis, and different
1639  * ways to split the intervals into two groups are considered, trying to
1640  * minimize the overlap of the groups. Then the same is repeated for the
1641  * Y-axis, and the overall best split is chosen. The quality of a split is
1642  * determined by overlap along that axis and some other criteria (see
1643  * g_box_consider_split).
1644  *
1645  * After that, all the entries are divided into three groups:
1646  *
1647  * 1) Entries which should be placed to the left group
1648  * 2) Entries which should be placed to the right group
1649  * 3) "Common entries" which can be placed to any of groups without affecting
1650  * of overlap along selected axis.
1651  *
1652  * The common entries are distributed by minimizing penalty.
1653  *
1654  * For details see:
1655  * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
1656  * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
1657  * --------------------------------------------------------------------------
1658  */
1660 Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS)
1661 {
1662  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1663  GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
1664  OffsetNumber i,
1665  maxoff;
1666  ConsiderSplitContext context;
1667  BOX2DF *box,
1668  *leftBox,
1669  *rightBox;
1670  int dim,
1671  commonEntriesCount;
1672  SplitInterval *intervalsLower,
1673  *intervalsUpper;
1674  CommonEntry *commonEntries;
1675  int nentries;
1676 
1677  POSTGIS_DEBUG(3, "[GIST] 'picksplit' entered");
1678 
1679  memset(&context, 0, sizeof(ConsiderSplitContext));
1680 
1681  maxoff = entryvec->n - 1;
1682  nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
1683 
1684  /* Allocate arrays for intervals along axes */
1685  intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1686  intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1687 
1688  /*
1689  * Calculate the overall minimum bounding box over all the entries.
1690  */
1691  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1692  {
1693  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1694  if (i == FirstOffsetNumber)
1695  context.boundingBox = *box;
1696  else
1697  adjustBox(&context.boundingBox, box);
1698  }
1699 
1700  POSTGIS_DEBUGF(4, "boundingBox is %s", box2df_to_string(
1701  &context.boundingBox));
1702 
1703  /*
1704  * Iterate over axes for optimal split searching.
1705  */
1706  context.first = true; /* nothing selected yet */
1707  for (dim = 0; dim < 2; dim++)
1708  {
1709  float leftUpper,
1710  rightLower;
1711  int i1,
1712  i2;
1713 
1714  /* Project each entry as an interval on the selected axis. */
1715  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1716  {
1717  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1718  if (dim == 0)
1719  {
1720  intervalsLower[i - FirstOffsetNumber].lower = box->xmin;
1721  intervalsLower[i - FirstOffsetNumber].upper = box->xmax;
1722  }
1723  else
1724  {
1725  intervalsLower[i - FirstOffsetNumber].lower = box->ymin;
1726  intervalsLower[i - FirstOffsetNumber].upper = box->ymax;
1727  }
1728  }
1729 
1730  /*
1731  * Make two arrays of intervals: one sorted by lower bound and another
1732  * sorted by upper bound.
1733  */
1734  memcpy(intervalsUpper, intervalsLower,
1735  sizeof(SplitInterval) * nentries);
1736  qsort(intervalsLower, nentries, sizeof(SplitInterval),
1738  qsort(intervalsUpper, nentries, sizeof(SplitInterval),
1740 
1741  /*----
1742  * The goal is to form a left and right interval, so that every entry
1743  * interval is contained by either left or right interval (or both).
1744  *
1745  * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
1746  *
1747  * 0 1 2 3 4
1748  * +-+
1749  * +---+
1750  * +-+
1751  * +---+
1752  *
1753  * The left and right intervals are of the form (0,a) and (b,4).
1754  * We first consider splits where b is the lower bound of an entry.
1755  * We iterate through all entries, and for each b, calculate the
1756  * smallest possible a. Then we consider splits where a is the
1757  * upper bound of an entry, and for each a, calculate the greatest
1758  * possible b.
1759  *
1760  * In the above example, the first loop would consider splits:
1761  * b=0: (0,1)-(0,4)
1762  * b=1: (0,1)-(1,4)
1763  * b=2: (0,3)-(2,4)
1764  *
1765  * And the second loop:
1766  * a=1: (0,1)-(1,4)
1767  * a=3: (0,3)-(2,4)
1768  * a=4: (0,4)-(2,4)
1769  */
1770 
1771  /*
1772  * Iterate over lower bound of right group, finding smallest possible
1773  * upper bound of left group.
1774  */
1775  i1 = 0;
1776  i2 = 0;
1777  rightLower = intervalsLower[i1].lower;
1778  leftUpper = intervalsUpper[i2].lower;
1779  while (true)
1780  {
1781  /*
1782  * Find next lower bound of right group.
1783  */
1784  while (i1 < nentries && (rightLower == intervalsLower[i1].lower ||
1785  isnan(intervalsLower[i1].lower)))
1786  {
1787  leftUpper = Max(leftUpper, intervalsLower[i1].upper);
1788  i1++;
1789  }
1790  if (i1 >= nentries)
1791  break;
1792  rightLower = intervalsLower[i1].lower;
1793 
1794  /*
1795  * Find count of intervals which anyway should be placed to the
1796  * left group.
1797  */
1798  while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
1799  i2++;
1800 
1801  /*
1802  * Consider found split.
1803  */
1804  g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
1805  }
1806 
1807  /*
1808  * Iterate over upper bound of left group finding greatest possible
1809  * lower bound of right group.
1810  */
1811  i1 = nentries - 1;
1812  i2 = nentries - 1;
1813  rightLower = intervalsLower[i1].upper;
1814  leftUpper = intervalsUpper[i2].upper;
1815  while (true)
1816  {
1817  /*
1818  * Find next upper bound of left group.
1819  */
1820  while (i2 >= 0 && (leftUpper == intervalsUpper[i2].upper ||
1821  isnan(intervalsUpper[i2].upper)))
1822  {
1823  rightLower = Min(rightLower, intervalsUpper[i2].lower);
1824  i2--;
1825  }
1826  if (i2 < 0)
1827  break;
1828  leftUpper = intervalsUpper[i2].upper;
1829 
1830  /*
1831  * Find count of intervals which anyway should be placed to the
1832  * right group.
1833  */
1834  while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
1835  i1--;
1836 
1837  /*
1838  * Consider found split.
1839  */
1840  g_box_consider_split(&context, dim,
1841  rightLower, i1 + 1, leftUpper, i2 + 1);
1842  }
1843  }
1844 
1845  /*
1846  * If we failed to find any acceptable splits, use trivial split.
1847  */
1848  if (context.first)
1849  {
1850  POSTGIS_DEBUG(4, "no acceptable splits, trivial split");
1851  fallbackSplit(entryvec, v);
1852  PG_RETURN_POINTER(v);
1853  }
1854 
1855  /*
1856  * Ok, we have now selected the split across one axis.
1857  *
1858  * While considering the splits, we already determined that there will be
1859  * enough entries in both groups to reach the desired ratio, but we did
1860  * not memorize which entries go to which group. So determine that now.
1861  */
1862 
1863  POSTGIS_DEBUGF(4, "split direction: %d", context.dim);
1864 
1865  /* Allocate vectors for results */
1866  v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
1867  v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
1868  v->spl_nleft = 0;
1869  v->spl_nright = 0;
1870 
1871  /* Allocate bounding boxes of left and right groups */
1872  leftBox = palloc0(sizeof(BOX2DF));
1873  rightBox = palloc0(sizeof(BOX2DF));
1874 
1875  /*
1876  * Allocate an array for "common entries" - entries which can be placed to
1877  * either group without affecting overlap along selected axis.
1878  */
1879  commonEntriesCount = 0;
1880  commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
1881 
1882  /* Helper macros to place an entry in the left or right group */
1883 #define PLACE_LEFT(box, off) \
1884  do { \
1885  if (v->spl_nleft > 0) \
1886  adjustBox(leftBox, box); \
1887  else \
1888  *leftBox = *(box); \
1889  v->spl_left[v->spl_nleft++] = off; \
1890  } while(0)
1891 
1892 #define PLACE_RIGHT(box, off) \
1893  do { \
1894  if (v->spl_nright > 0) \
1895  adjustBox(rightBox, box); \
1896  else \
1897  *rightBox = *(box); \
1898  v->spl_right[v->spl_nright++] = off; \
1899  } while(0)
1900 
1901  /*
1902  * Distribute entries which can be distributed unambiguously, and collect
1903  * common entries.
1904  */
1905  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1906  {
1907  float lower,
1908  upper;
1909 
1910  /*
1911  * Get upper and lower bounds along selected axis.
1912  */
1913  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1914  if (context.dim == 0)
1915  {
1916  lower = box->xmin;
1917  upper = box->xmax;
1918  }
1919  else
1920  {
1921  lower = box->ymin;
1922  upper = box->ymax;
1923  }
1924 
1925  if (upper <= context.leftUpper || isnan(upper))
1926  {
1927  /* Fits to the left group */
1928  if (lower >= context.rightLower || isnan(lower))
1929  {
1930  /* Fits also to the right group, so "common entry" */
1931  commonEntries[commonEntriesCount++].index = i;
1932  }
1933  else
1934  {
1935  /* Doesn't fit to the right group, so join to the left group */
1936  PLACE_LEFT(box, i);
1937  }
1938  }
1939  else
1940  {
1941  /*
1942  * Each entry should fit on either left or right group. Since this
1943  * entry didn't fit on the left group, it better fit in the right
1944  * group.
1945  */
1946  Assert(lower >= context.rightLower);
1947 
1948  /* Doesn't fit to the left group, so join to the right group */
1949  PLACE_RIGHT(box, i);
1950  }
1951  }
1952 
1953  POSTGIS_DEBUGF(4, "leftBox is %s", box2df_to_string(leftBox));
1954  POSTGIS_DEBUGF(4, "rightBox is %s", box2df_to_string(rightBox));
1955 
1956  /*
1957  * Distribute "common entries", if any.
1958  */
1959  if (commonEntriesCount > 0)
1960  {
1961  /*
1962  * Calculate minimum number of entries that must be placed in both
1963  * groups, to reach LIMIT_RATIO.
1964  */
1965  int m = ceil(LIMIT_RATIO * (double) nentries);
1966 
1967  /*
1968  * Calculate delta between penalties of join "common entries" to
1969  * different groups.
1970  */
1971  for (i = 0; i < commonEntriesCount; i++)
1972  {
1973  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
1974  commonEntries[i].index].key);
1975  commonEntries[i].delta = Abs(box2df_penalty(leftBox, box) - box2df_penalty(rightBox, box));
1976  }
1977 
1978  /*
1979  * Sort "common entries" by calculated deltas in order to distribute
1980  * the most ambiguous entries first.
1981  */
1982  qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
1983 
1984  /*
1985  * Distribute "common entries" between groups.
1986  */
1987  for (i = 0; i < commonEntriesCount; i++)
1988  {
1989  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
1990  commonEntries[i].index].key);
1991 
1992  /*
1993  * Check if we have to place this entry in either group to achieve
1994  * LIMIT_RATIO.
1995  */
1996  if (v->spl_nleft + (commonEntriesCount - i) <= m)
1997  PLACE_LEFT(box, commonEntries[i].index);
1998  else if (v->spl_nright + (commonEntriesCount - i) <= m)
1999  PLACE_RIGHT(box, commonEntries[i].index);
2000  else
2001  {
2002  /* Otherwise select the group by minimal penalty */
2003  if (box2df_penalty(leftBox, box) < box2df_penalty(rightBox, box))
2004  PLACE_LEFT(box, commonEntries[i].index);
2005  else
2006  PLACE_RIGHT(box, commonEntries[i].index);
2007  }
2008  }
2009  }
2010  v->spl_ldatum = PointerGetDatum(leftBox);
2011  v->spl_rdatum = PointerGetDatum(rightBox);
2012 
2013  POSTGIS_DEBUG(4, "[GIST] 'picksplit' completed");
2014 
2015  PG_RETURN_POINTER(v);
2016 }
2017 
2018 /*
2019 ** The BOX2DF key must be defined as a PostgreSQL type, even though it is only
2020 ** ever used internally. These no-op stubs are used to bind the type.
2021 */
2023 Datum box2df_in(PG_FUNCTION_ARGS)
2024 {
2025  ereport(ERROR,(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2026  errmsg("function box2df_in not implemented")));
2027  PG_RETURN_POINTER(NULL);
2028 }
2029 
2031 Datum box2df_out(PG_FUNCTION_ARGS)
2032 {
2033  BOX2DF *box = (BOX2DF *) PG_GETARG_POINTER(0);
2034  char *result = box2df_to_string(box);
2035  PG_RETURN_CSTRING(result);
2036 }
static uint8_t precision
Definition: cu_in_twkb.c:25
char result[OUT_DOUBLE_BUFFER_SIZE]
Definition: cu_print.c:267
int gserialized_has_bbox(const GSERIALIZED *g)
Check if a GSERIALIZED has a bounding box without deserializing first.
Definition: gserialized.c:163
int32_t gserialized_get_srid(const GSERIALIZED *g)
Extract the SRID from the serialized form (it is packed into three bytes so this is a handy function)...
Definition: gserialized.c:126
int gserialized_get_gbox_p(const GSERIALIZED *g, GBOX *gbox)
Read the box from the GSERIALIZED or calculate it if necessary.
Definition: gserialized.c:65
const float * gserialized_get_float_box_p(const GSERIALIZED *g, size_t *ndims)
Access to the float bounding box, if there is one.
Definition: gserialized.c:248
uint32_t gserialized_get_type(const GSERIALIZED *g)
Extract the geometry type from the serialized form (it hides in the anonymous data area,...
Definition: gserialized.c:89
uint32_t gserialized_max_header_size(void)
Returns the size in bytes to read from toast to get the basic information from a geometry: GSERIALIZE...
Definition: gserialized.c:101
lwflags_t gserialized_get_lwflags(const GSERIALIZED *g)
Read the flags from a GSERIALIZED and return a standard lwflag integer.
Definition: gserialized.c:18
bool box2df_left(const BOX2DF *a, const BOX2DF *b)
static char * box2df_to_string(const BOX2DF *a)
void box2df_merge(BOX2DF *b_union, BOX2DF *b_new)
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
Datum gserialized_overbelow_2d(PG_FUNCTION_ARGS)
void box2df_set_empty(BOX2DF *a)
Datum gserialized_gist_same_2d(PG_FUNCTION_ARGS)
Datum gserialized_contains_box2df_geom_2d(PG_FUNCTION_ARGS)
bool box2df_is_empty(const BOX2DF *a)
static int gserialized_datum_predicate_2d(Datum gs1, Datum gs2, box2df_predicate predicate)
Support function.
Datum gserialized_within_2d(PG_FUNCTION_ARGS)
PG_FUNCTION_INFO_V1(gserialized_contains_box2df_geom_2d)
Datum box2df_out(PG_FUNCTION_ARGS)
Datum gserialized_within_box2df_geom_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_penalty_2d(PG_FUNCTION_ARGS)
Datum gserialized_left_2d(PG_FUNCTION_ARGS)
Datum gserialized_contains_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_consistent_2d(PG_FUNCTION_ARGS)
static int interval_cmp_upper(const void *i1, const void *i2)
Datum gserialized_distance_box_2d(PG_FUNCTION_ARGS)
bool box2df_equals(const BOX2DF *a, const BOX2DF *b)
#define LIMIT_RATIO
bool box2df_contains(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_gist_union_2d(PG_FUNCTION_ARGS)
#define PLACE_RIGHT(box, off)
Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS)
Datum gserialized_distance_centroid_2d(PG_FUNCTION_ARGS)
Datum gserialized_contains_box2df_box2df_2d(PG_FUNCTION_ARGS)
Datum gserialized_overlaps_2d(PG_FUNCTION_ARGS)
Datum gserialized_overlaps_box2df_geom_2d(PG_FUNCTION_ARGS)
Datum gserialized_within_box2df_box2df_2d(PG_FUNCTION_ARGS)
bool box2df_right(const BOX2DF *a, const BOX2DF *b)
bool box2df_overlaps(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_overleft_2d(PG_FUNCTION_ARGS)
void box2df_set_finite(BOX2DF *a)
static bool gserialized_gist_consistent_internal_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
Datum gserialized_overlaps_box2df_box2df_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_distance_2d(PG_FUNCTION_ARGS)
Datum gserialized_overright_2d(PG_FUNCTION_ARGS)
static bool box2df_within(const BOX2DF *a, const BOX2DF *b)
bool box2df_above(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_right_2d(PG_FUNCTION_ARGS)
bool box2df_overbelow(const BOX2DF *a, const BOX2DF *b)
bool(* box2df_predicate)(const BOX2DF *a, const BOX2DF *b)
static double box2df_distance(const BOX2DF *a, const BOX2DF *b)
Calculate the box->box distance.
static double box2df_distance_leaf_centroid(const BOX2DF *a, const BOX2DF *b)
Calculate the centroid->centroid distance between the boxes.
Datum gserialized_below_2d(PG_FUNCTION_ARGS)
Datum gserialized_overabove_2d(PG_FUNCTION_ARGS)
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, float rightLower, int minLeftCount, float leftUpper, int maxLeftCount)
int box2df_to_gbox_p(BOX2DF *a, GBOX *box)
static int interval_cmp_lower(const void *i1, const void *i2)
bool box2df_overright(const BOX2DF *a, const BOX2DF *b)
static double pt_distance(double ax, double ay, double bx, double by)
static float pack_float(const float value, const uint8_t realm)
static int common_entry_cmp(const void *i1, const void *i2)
Datum gserialized_gist_decompress_2d(PG_FUNCTION_ARGS)
int gserialized_datum_get_box2df_p(Datum gsdatum, BOX2DF *box2df)
int gserialized_datum_get_internals_p(Datum gsdatum, GBOX *gbox, lwflags_t *flags, uint8_t *type, int32_t *srid)
Peak into a GSERIALIZED datum to find its bounding box and some other metadata.
int gserialized_datum_get_gbox_p(Datum gsdatum, GBOX *gbox)
Given a GSERIALIZED datum, as quickly as possible (peaking into the top of the memory) return the gbo...
static int box2df_from_gbox_p(GBOX *box, BOX2DF *a)
bool box2df_overabove(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS)
#define PLACE_LEFT(box, off)
void box2df_validate(BOX2DF *b)
static float box2df_penalty(const BOX2DF *b1, const BOX2DF *b2)
bool box2df_below(const BOX2DF *a, const BOX2DF *b)
static bool gserialized_gist_consistent_leaf_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
bool box2df_overleft(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_above_2d(PG_FUNCTION_ARGS)
static int gserialized_datum_predicate_box2df_geom_2d(const BOX2DF *br1, Datum gs2, box2df_predicate predicate)
BOX2DF * box2df_copy(BOX2DF *b)
Datum gserialized_same_2d(PG_FUNCTION_ARGS)
Datum box2df_in(PG_FUNCTION_ARGS)
static void adjustBox(BOX2DF *b, BOX2DF *addon)
static float non_negative(float val)
#define LW_FALSE
Definition: liblwgeom.h:108
#define LW_FAILURE
Definition: liblwgeom.h:110
#define LWSIZE_GET(varsize)
Macro for reading the size from the GSERIALIZED size attribute.
Definition: liblwgeom.h:338
#define LW_SUCCESS
Definition: liblwgeom.h:111
uint16_t lwflags_t
Definition: liblwgeom.h:313
float next_float_up(double d)
Definition: lwgeom_api.c:75
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:107
float next_float_down(double d)
Definition: lwgeom_api.c:54
This library is the generic geometry handling section of PostGIS.
#define OUT_MAX_BYTES_DOUBLE
int lwprint_double(double d, int maxdd, char *buf)
Definition: lwprint.c:463
#define NAN
Definition: lwgeodetic.h:37
#define POSTGIS_FREE_IF_COPY_P(ptrsrc, ptrori)
Definition: lwinline.h:245
static double distance(double x1, double y1, double x2, double y2)
Definition: lwtree.c:1032
int value
Definition: genraster.py:62
type
Definition: ovdump.py:42
double ymax
Definition: liblwgeom.h:371
double xmax
Definition: liblwgeom.h:369
double ymin
Definition: liblwgeom.h:370
double xmin
Definition: liblwgeom.h:368
uint32_t size
Definition: liblwgeom.h:458