PostGIS  2.1.10dev-r@@SVN_REVISION@@
gserialized_gist_nd.c
Go to the documentation of this file.
1 /**********************************************************************
2  * $Id: gserialized_gist_nd.c 6519 2010-12-28 00:54:19Z pramsey $
3  *
4  * PostGIS - Spatial Types for PostgreSQL
5  * Copyright 2009 Paul Ramsey <pramsey@cleverelephant.ca>
6  *
7  * This is free software; you can redistribute and/or modify it under
8  * the terms of the GNU General Public Licence. See the COPYING file.
9  *
10  **********************************************************************/
11 
12 /*
13 ** R-Tree Bibliography
14 **
15 ** [1] A. Guttman. R-tree: a dynamic index structure for spatial searching.
16 ** Proceedings of the ACM SIGMOD Conference, pp 47-57, June 1984.
17 ** [2] C.-H. Ang and T. C. Tan. New linear node splitting algorithm for
18 ** R-Trees. Advances in Spatial Databases - 5th International Symposium,
19 ** 1997
20 ** [3] N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger. The R*tree: an
21 ** efficient and robust access method for points and rectangles.
22 ** Proceedings of the ACM SIGMOD Conference. June 1990.
23 */
24 
25 #include "postgres.h"
26 #include "access/gist.h" /* For GiST */
27 #include "access/itup.h"
28 #include "access/skey.h"
29 
30 #include "../postgis_config.h"
31 
32 /*#define POSTGIS_DEBUG_LEVEL 4*/
33 
34 #include "liblwgeom.h" /* For standard geometry types. */
35 #include "lwgeom_pg.h" /* For debugging macros. */
36 #include "gserialized_gist.h" /* For utility functions. */
37 #include "geography.h"
38 
39 /* Fall back to older finite() if necessary */
40 #ifndef HAVE_ISFINITE
41 # ifdef HAVE_GNU_ISFINITE
42 # define _GNU_SOURCE
43 # else
44 # define isfinite finite
45 # endif
46 #endif
47 
48 /*
49 ** When is a node split not so good? If more than 90% of the entries
50 ** end up in one of the children.
51 */
52 #define LIMIT_RATIO 0.1
53 
54 /*
55 ** For debugging
56 */
57 #if POSTGIS_DEBUG_LEVEL > 0
58 static int geog_counter_leaf = 0;
59 static int geog_counter_internal = 0;
60 #endif
61 
62 /*
63 ** ND Index key type stub prototypes
64 */
65 Datum gidx_out(PG_FUNCTION_ARGS);
66 Datum gidx_in(PG_FUNCTION_ARGS);
67 
68 /*
69 ** ND GiST prototypes
70 */
71 Datum gserialized_gist_consistent(PG_FUNCTION_ARGS);
72 Datum gserialized_gist_compress(PG_FUNCTION_ARGS);
73 Datum gserialized_gist_decompress(PG_FUNCTION_ARGS);
74 Datum gserialized_gist_penalty(PG_FUNCTION_ARGS);
75 Datum gserialized_gist_picksplit(PG_FUNCTION_ARGS);
76 Datum gserialized_gist_union(PG_FUNCTION_ARGS);
77 Datum gserialized_gist_same(PG_FUNCTION_ARGS);
78 
79 /*
80 ** ND Operator prototypes
81 */
82 Datum gserialized_overlaps(PG_FUNCTION_ARGS);
83 Datum gserialized_contains(PG_FUNCTION_ARGS);
84 Datum gserialized_within(PG_FUNCTION_ARGS);
85 
86 /*
87 ** GIDX true/false test function type
88 */
89 typedef bool (*gidx_predicate)(GIDX *a, GIDX *b);
90 
91 
92 /* Allocate a new copy of GIDX */
93 static GIDX* gidx_copy(GIDX *b)
94 {
95  GIDX *c = (GIDX*)palloc(VARSIZE(b));
96  POSTGIS_DEBUGF(5, "copied gidx (%p) to gidx (%p)", b, c);
97  memcpy((void*)c, (void*)b, VARSIZE(b));
98  return c;
99 }
100 
101 
102 /* Ensure all minimums are below maximums. */
103 static inline void gidx_validate(GIDX *b)
104 {
105  int i;
106  Assert(b);
107  POSTGIS_DEBUGF(5,"validating gidx (%s)", gidx_to_string(b));
108  for ( i = 0; i < GIDX_NDIMS(b); i++ )
109  {
110  if ( GIDX_GET_MIN(b,i) > GIDX_GET_MAX(b,i) )
111  {
112  float tmp;
113  tmp = GIDX_GET_MIN(b,i);
114  GIDX_SET_MIN(b,i,GIDX_GET_MAX(b,i));
115  GIDX_SET_MAX(b,i,tmp);
116  }
117  }
118  return;
119 }
120 
121 /* An "unknown" GIDX is used to represent the bounds of an EMPTY
122  geometry or other-wise unindexable geometry (like one with NaN
123  or Inf bounds) */
124 static inline bool gidx_is_unknown(const GIDX *a)
125 {
126  size_t size = VARSIZE(a) - VARHDRSZ;
127  /* "unknown" gidx objects have a too-small size of one float */
128  if ( size <= 0.0 )
129  return TRUE;
130  return FALSE;
131 }
132 
133 static inline void gidx_set_unknown(GIDX *a)
134 {
135  SET_VARSIZE(a, VARHDRSZ);
136 }
137 
138 /* Enlarge b_union to contain b_new. If b_new contains more
139  dimensions than b_union, expand b_union to contain those dimensions. */
140 static void gidx_merge(GIDX **b_union, GIDX *b_new)
141 {
142  int i, dims_union, dims_new;
143  Assert(b_union);
144  Assert(*b_union);
145  Assert(b_new);
146 
147  /* Can't merge an unknown into any thing */
148  if( gidx_is_unknown(b_new) )
149  return;
150 
151  /* Merge of unknown and known is known */
152  if( gidx_is_unknown(*b_union) )
153  {
154  *b_union = b_new;
155  return;
156  }
157 
158  dims_union = GIDX_NDIMS(*b_union);
159  dims_new = GIDX_NDIMS(b_new);
160 
161  POSTGIS_DEBUGF(4, "merging gidx (%s) into gidx (%s)", gidx_to_string(b_new), gidx_to_string(*b_union));
162 
163  if ( dims_new > dims_union )
164  {
165  POSTGIS_DEBUGF(5, "reallocating b_union from %d dims to %d dims", dims_union, dims_new);
166  *b_union = (GIDX*)repalloc(*b_union, GIDX_SIZE(dims_new));
167  SET_VARSIZE(*b_union, VARSIZE(b_new));
168  dims_union = dims_new;
169  }
170 
171  for ( i = 0; i < dims_new; i++ )
172  {
173  /* Adjust minimums */
174  GIDX_SET_MIN(*b_union, i, Min(GIDX_GET_MIN(*b_union,i),GIDX_GET_MIN(b_new,i)));
175  /* Adjust maximums */
176  GIDX_SET_MAX(*b_union, i, Max(GIDX_GET_MAX(*b_union,i),GIDX_GET_MAX(b_new,i)));
177  }
178 
179  POSTGIS_DEBUGF(5, "merge complete (%s)", gidx_to_string(*b_union));
180  return;
181 }
182 
183 /* Calculate the volume (in n-d units) of the GIDX */
184 static float gidx_volume(GIDX *a)
185 {
186  float result;
187  int i;
188  if ( a == NULL || gidx_is_unknown(a) )
189  {
190  /* elog(ERROR, "gidx_volume received a null argument"); */
191  return 0.0;
192  }
193  result = GIDX_GET_MAX(a,0) - GIDX_GET_MIN(a,0);
194  for ( i = 1; i < GIDX_NDIMS(a); i++ )
195  result *= (GIDX_GET_MAX(a,i) - GIDX_GET_MIN(a,i));
196  POSTGIS_DEBUGF(5, "calculated volume of %s as %.8g", gidx_to_string(a), result);
197  return result;
198 }
199 
200 /* Ensure the first argument has the higher dimensionality. */
201 static void gidx_dimensionality_check(GIDX **a, GIDX **b)
202 {
203  if ( GIDX_NDIMS(*a) < GIDX_NDIMS(*b) )
204  {
205  GIDX *tmp = *b;
206  *b = *a;
207  *a = tmp;
208  }
209 }
210 
211 /* Calculate the volume of the union of the boxes. Avoids creating an intermediate box. */
212 static float gidx_union_volume(GIDX *a, GIDX *b)
213 {
214  float result;
215  int i;
216  int ndims_a, ndims_b;
217 
218  POSTGIS_DEBUG(5,"entered function");
219 
220  if ( a == NULL && b == NULL )
221  {
222  elog(ERROR, "gidx_union_volume received two null arguments");
223  return 0.0;
224  }
225 
226  if ( a == NULL || gidx_is_unknown(a) )
227  return gidx_volume(b);
228 
229  if ( b == NULL || gidx_is_unknown(b) )
230  return gidx_volume(a);
231 
232  if ( gidx_is_unknown(a) && gidx_is_unknown(b) )
233  {
234  return 0.0;
235  }
236 
237  /* Ensure 'a' has the most dimensions. */
239 
240  ndims_a = GIDX_NDIMS(a);
241  ndims_b = GIDX_NDIMS(b);
242 
243  /* Initialize with maximal length of first dimension. */
244  result = Max(GIDX_GET_MAX(a,0),GIDX_GET_MAX(b,0)) - Min(GIDX_GET_MIN(a,0),GIDX_GET_MIN(b,0));
245 
246  /* Multiply by maximal length of remaining dimensions. */
247  for ( i = 1; i < ndims_b; i++ )
248  {
249  result *= (Max(GIDX_GET_MAX(a,i),GIDX_GET_MAX(b,i)) - Min(GIDX_GET_MIN(a,i),GIDX_GET_MIN(b,i)));
250  }
251 
252  /* Add in dimensions of higher dimensional box. */
253  for ( i = ndims_b; i < ndims_a; i++ )
254  {
255  result *= (GIDX_GET_MAX(a,i) - GIDX_GET_MIN(a,i));
256  }
257 
258  POSTGIS_DEBUGF(5, "volume( %s union %s ) = %.12g", gidx_to_string(a), gidx_to_string(b), result);
259 
260  return result;
261 }
262 
263 /* Calculate the volume of the intersection of the boxes. */
264 static float gidx_inter_volume(GIDX *a, GIDX *b)
265 {
266  int i;
267  float result;
268 
269  POSTGIS_DEBUG(5,"entered function");
270 
271  if ( a == NULL || b == NULL )
272  {
273  elog(ERROR, "gidx_inter_volume received a null argument");
274  return 0.0;
275  }
276 
277  if ( gidx_is_unknown(a) || gidx_is_unknown(b) )
278  {
279  return 0.0;
280  }
281 
282  /* Ensure 'a' has the most dimensions. */
284 
285  /* Initialize with minimal length of first dimension. */
286  result = Min(GIDX_GET_MAX(a,0),GIDX_GET_MAX(b,0)) - Max(GIDX_GET_MIN(a,0),GIDX_GET_MIN(b,0));
287 
288  /* If they are disjoint (max < min) then return zero. */
289  if ( result < 0.0 ) return 0.0;
290 
291  /* Continue for remaining dimensions. */
292  for ( i = 1; i < GIDX_NDIMS(b); i++ )
293  {
294  float width = Min(GIDX_GET_MAX(a,i),GIDX_GET_MAX(b,i)) - Max(GIDX_GET_MIN(a,i),GIDX_GET_MIN(b,i));
295  if ( width < 0.0 ) return 0.0;
296  /* Multiply by minimal length of remaining dimensions. */
297  result *= width;
298  }
299  POSTGIS_DEBUGF(5, "volume( %s intersection %s ) = %.12g", gidx_to_string(a), gidx_to_string(b), result);
300  return result;
301 }
302 
303 /*
304 ** Overlapping GIDX box test.
305 **
306 ** Box(A) Overlaps Box(B) IFF for every dimension d:
307 ** min(A,d) <= max(B,d) && max(A,d) => min(B,d)
308 **
309 ** Any missing dimension is assumed by convention to
310 ** overlap whatever finite range available on the
311 ** other operand. See
312 ** http://lists.osgeo.org/pipermail/postgis-devel/2015-February/024757.html
313 **
314 ** Empty boxes never overlap.
315 */
316 static bool gidx_overlaps(GIDX *a, GIDX *b)
317 {
318  int i;
319  int ndims_b;
320  POSTGIS_DEBUG(5, "entered function");
321 
322  if ( (a == NULL) || (b == NULL) ) return FALSE;
323 
324  if ( gidx_is_unknown(a) || gidx_is_unknown(b) )
325  return FALSE;
326 
327  /* Ensure 'a' has the most dimensions. */
329 
330  ndims_b = GIDX_NDIMS(b);
331 
332  /* compare only up to dimensions of (b), missing dimensions always overlap */
333  for ( i = 0; i < ndims_b; i++ )
334  {
335  if ( GIDX_GET_MIN(a,i) > GIDX_GET_MAX(b,i) )
336  return FALSE;
337  if ( GIDX_GET_MIN(b,i) > GIDX_GET_MAX(a,i) )
338  return FALSE;
339  }
340 
341  return TRUE;
342 }
343 
344 /*
345 ** Containment GIDX test.
346 **
347 ** Box(A) CONTAINS Box(B) IFF (pt(A)LL < pt(B)LL) && (pt(A)UR > pt(B)UR)
348 */
349 static bool gidx_contains(GIDX *a, GIDX *b)
350 {
351  int i, dims_a, dims_b;
352 
353  POSTGIS_DEBUG(5, "entered function");
354 
355  if ( (a == NULL) || (b == NULL) ) return FALSE;
356 
357  if ( gidx_is_unknown(a) || gidx_is_unknown(b) )
358  return FALSE;
359 
360  dims_a = GIDX_NDIMS(a);
361  dims_b = GIDX_NDIMS(b);
362 
363  if ( dims_a < dims_b )
364  {
365  /*
366  ** If (b) is of higher dimensionality than (a) it can only be contained
367  ** if those higher dimensions are zeroes.
368  */
369  for (i = dims_a; i < dims_b; i++)
370  {
371  if ( GIDX_GET_MIN(b,i) != 0 )
372  return FALSE;
373  if ( GIDX_GET_MAX(b,i) != 0 )
374  return FALSE;
375  }
376  }
377 
378  /* Excess dimensions of (a), don't matter, it just has to contain (b) in (b)'s dimensions */
379  for (i = 0; i < Min(dims_a, dims_b); i++)
380  {
381  if ( GIDX_GET_MIN(a,i) > GIDX_GET_MIN(b,i) )
382  return FALSE;
383  if ( GIDX_GET_MAX(a,i) < GIDX_GET_MAX(b,i) )
384  return FALSE;
385  }
386 
387  return TRUE;
388 }
389 
390 /*
391 ** Equality GIDX test.
392 **
393 ** Box(A) EQUALS Box(B) IFF (pt(A)LL == pt(B)LL) && (pt(A)UR == pt(B)UR)
394 */
395 static bool gidx_equals(GIDX *a, GIDX *b)
396 {
397  int i;
398 
399  POSTGIS_DEBUG(5, "entered function");
400 
401  if ( (a == NULL) && (b == NULL) ) return TRUE;
402  if ( (a == NULL) || (b == NULL) ) return FALSE;
403 
404  if ( gidx_is_unknown(a) && gidx_is_unknown(b) )
405  return TRUE;
406 
407  if ( gidx_is_unknown(a) || gidx_is_unknown(b) )
408  return FALSE;
409 
410  /* Ensure 'a' has the most dimensions. */
412 
413  /* For all shared dimensions min(a) == min(b), max(a) == max(b) */
414  for (i = 0; i < GIDX_NDIMS(b); i++)
415  {
416  if ( GIDX_GET_MIN(a,i) != GIDX_GET_MIN(b,i) )
417  return FALSE;
418  if ( GIDX_GET_MAX(a,i) != GIDX_GET_MAX(b,i) )
419  return FALSE;
420  }
421  /* For all unshared dimensions min(a) == 0.0, max(a) == 0.0 */
422  for (i = GIDX_NDIMS(b); i < GIDX_NDIMS(a); i++)
423  {
424  if ( GIDX_GET_MIN(a,i) != 0.0 )
425  return FALSE;
426  if ( GIDX_GET_MAX(a,i) != 0.0 )
427  return FALSE;
428  }
429  return TRUE;
430 }
431 
436 static int
437 gserialized_datum_predicate(Datum gs1, Datum gs2, gidx_predicate predicate)
438 {
439  /* Put aside some stack memory and use it for GIDX pointers. */
440  char boxmem1[GIDX_MAX_SIZE];
441  char boxmem2[GIDX_MAX_SIZE];
442  GIDX *gidx1 = (GIDX*)boxmem1;
443  GIDX *gidx2 = (GIDX*)boxmem2;
444 
445  POSTGIS_DEBUG(3, "entered function");
446 
447  /* Must be able to build box for each arguement (ie, not empty geometry)
448  and predicate function to return true. */
449  if ( (gserialized_datum_get_gidx_p(gs1, gidx1) == LW_SUCCESS) &&
450  (gserialized_datum_get_gidx_p(gs2, gidx2) == LW_SUCCESS) &&
451  predicate(gidx1, gidx2) )
452  {
453  POSTGIS_DEBUGF(3, "got boxes %s and %s", gidx_to_string(gidx1), gidx_to_string(gidx2));
454  return LW_TRUE;
455  }
456  return LW_FALSE;
457 }
458 
462 GSERIALIZED*
464 {
465  char boxmem[GIDX_MAX_SIZE];
466  GIDX *gidx = (GIDX*)boxmem;
467  float fdistance = (float)distance;
468 
469  /* Get our bounding box out of the geography, return right away if
470  input is an EMPTY geometry. */
471  if ( gserialized_get_gidx_p(g, gidx) == LW_FAILURE )
472  {
473  return g;
474  }
475 
476  gidx_expand(gidx, fdistance);
477 
478  return gserialized_set_gidx(g, gidx);
479 }
480 
481 /***********************************************************************
482 * GiST N-D Index Operator Functions
483 */
484 
485 /*
486 ** '~' and operator function. Based on two serialized return true if
487 ** the first is contained by the second.
488 */
490 Datum gserialized_within(PG_FUNCTION_ARGS)
491 {
492  if ( gserialized_datum_predicate(PG_GETARG_DATUM(1), PG_GETARG_DATUM(0), gidx_contains) == LW_TRUE )
493  {
494  PG_RETURN_BOOL(TRUE);
495  }
496 
497  PG_RETURN_BOOL(FALSE);
498 }
499 
500 /*
501 ** '@' and operator function. Based on two serialized return true if
502 ** the first contains the second.
503 */
505 Datum gserialized_contains(PG_FUNCTION_ARGS)
506 {
507  if ( gserialized_datum_predicate(PG_GETARG_DATUM(0),PG_GETARG_DATUM(1), gidx_contains) == LW_TRUE )
508  {
509  PG_RETURN_BOOL(TRUE);
510  }
511 
512  PG_RETURN_BOOL(FALSE);
513 }
514 
515 /*
516 ** '&&' operator function. Based on two serialized return true if
517 ** they overlap and false otherwise.
518 */
520 Datum gserialized_overlaps(PG_FUNCTION_ARGS)
521 {
522  if ( gserialized_datum_predicate(PG_GETARG_DATUM(0),PG_GETARG_DATUM(1), gidx_overlaps) == LW_TRUE )
523  {
524  PG_RETURN_BOOL(TRUE);
525  }
526 
527  PG_RETURN_BOOL(FALSE);
528 }
529 
530 /***********************************************************************
531 * GiST Index Support Functions
532 */
533 
534 /*
535 ** GiST support function. Given a geography, return a "compressed"
536 ** version. In this case, we convert the geography into a geocentric
537 ** bounding box. If the geography already has the box embedded in it
538 ** we pull that out and hand it back.
539 */
541 Datum gserialized_gist_compress(PG_FUNCTION_ARGS)
542 {
543  GISTENTRY *entry_in = (GISTENTRY*)PG_GETARG_POINTER(0);
544  GISTENTRY *entry_out = NULL;
545  char gidxmem[GIDX_MAX_SIZE];
546  GIDX *bbox_out = (GIDX*)gidxmem;
547  int result = LW_SUCCESS;
548  int i;
549 
550  POSTGIS_DEBUG(4, "[GIST] 'compress' function called");
551 
552  /*
553  ** Not a leaf key? There's nothing to do.
554  ** Return the input unchanged.
555  */
556  if ( ! entry_in->leafkey )
557  {
558  POSTGIS_DEBUG(4, "[GIST] non-leafkey entry, returning input unaltered");
559  PG_RETURN_POINTER(entry_in);
560  }
561 
562  POSTGIS_DEBUG(4, "[GIST] processing leafkey input");
563  entry_out = palloc(sizeof(GISTENTRY));
564 
565  /*
566  ** Null key? Make a copy of the input entry and
567  ** return.
568  */
569  if ( DatumGetPointer(entry_in->key) == NULL )
570  {
571  POSTGIS_DEBUG(4, "[GIST] leafkey is null");
572  gistentryinit(*entry_out, (Datum) 0, entry_in->rel,
573  entry_in->page, entry_in->offset, FALSE);
574  POSTGIS_DEBUG(4, "[GIST] returning copy of input");
575  PG_RETURN_POINTER(entry_out);
576  }
577 
578  /* Extract our index key from the GiST entry. */
579  result = gserialized_datum_get_gidx_p(entry_in->key, bbox_out);
580 
581  /* Is the bounding box valid (non-empty, non-infinite) ?
582  * If not, use the "unknown" GIDX. */
583  if ( result == LW_FAILURE )
584  {
585  POSTGIS_DEBUG(4, "[GIST] empty geometry!");
586  gidx_set_unknown(bbox_out);
587  gistentryinit(*entry_out, PointerGetDatum(gidx_copy(bbox_out)),
588  entry_in->rel, entry_in->page,
589  entry_in->offset, FALSE);
590  PG_RETURN_POINTER(entry_out);
591  }
592 
593  POSTGIS_DEBUGF(4, "[GIST] got entry_in->key: %s", gidx_to_string(bbox_out));
594 
595  /* Check all the dimensions for finite values.
596  * If not, use the "unknown" GIDX as a key */
597  for ( i = 0; i < GIDX_NDIMS(bbox_out); i++ )
598  {
599  if ( ! isfinite(GIDX_GET_MAX(bbox_out, i)) ||
600  ! isfinite(GIDX_GET_MIN(bbox_out, i)) )
601  {
602  gidx_set_unknown(bbox_out);
603  gistentryinit(*entry_out,
604  PointerGetDatum(gidx_copy(bbox_out)),
605  entry_in->rel, entry_in->page,
606  entry_in->offset, FALSE);
607  PG_RETURN_POINTER(entry_out);
608  }
609  }
610 
611  /* Enure bounding box has minimums below maximums. */
612  gidx_validate(bbox_out);
613 
614  /* Prepare GISTENTRY for return. */
615  gistentryinit(*entry_out, PointerGetDatum(gidx_copy(bbox_out)),
616  entry_in->rel, entry_in->page, entry_in->offset, FALSE);
617 
618  /* Return GISTENTRY. */
619  POSTGIS_DEBUG(4, "[GIST] 'compress' function complete");
620  PG_RETURN_POINTER(entry_out);
621 }
622 
623 /*
624 ** GiST support function.
625 ** Decompress an entry. Unused for geography, so we return.
626 */
628 Datum gserialized_gist_decompress(PG_FUNCTION_ARGS)
629 {
630  POSTGIS_DEBUG(5, "[GIST] 'decompress' function called");
631  /* We don't decompress. Just return the input. */
632  PG_RETURN_POINTER(PG_GETARG_POINTER(0));
633 }
634 
635 /*
636 ** GiST support function. Called from gserialized_gist_consistent below.
637 */
638 static inline bool gserialized_gist_consistent_leaf(GIDX *key, GIDX *query, StrategyNumber strategy)
639 {
640  bool retval;
641 
642  POSTGIS_DEBUGF(4, "[GIST] leaf consistent, strategy [%d], count[%i]",
643  strategy, geog_counter_leaf++);
644 
645  switch (strategy)
646  {
647  case RTOverlapStrategyNumber:
648  retval = (bool) gidx_overlaps(key, query);
649  break;
650  case RTSameStrategyNumber:
651  retval = (bool) gidx_equals(key, query);
652  break;
653  case RTContainsStrategyNumber:
654  case RTOldContainsStrategyNumber:
655  retval = (bool) gidx_contains(key, query);
656  break;
657  case RTContainedByStrategyNumber:
658  case RTOldContainedByStrategyNumber:
659  retval = (bool) gidx_contains(query, key);
660  break;
661  default:
662  retval = FALSE;
663  }
664 
665  return (retval);
666 }
667 
668 /*
669 ** GiST support function. Called from gserialized_gist_consistent below.
670 */
671 static inline bool gserialized_gist_consistent_internal(GIDX *key, GIDX *query, StrategyNumber strategy)
672 {
673  bool retval;
674 
675  POSTGIS_DEBUGF(4, "[GIST] internal consistent, strategy [%d], count[%i], query[%s], key[%s]",
676  strategy, geog_counter_internal++, gidx_to_string(query), gidx_to_string(key) );
677 
678  switch (strategy)
679  {
680  case RTOverlapStrategyNumber:
681  retval = (bool) gidx_overlaps(key, query);
682  break;
683  case RTSameStrategyNumber:
684  case RTContainsStrategyNumber:
685  case RTOldContainsStrategyNumber:
686  retval = (bool) gidx_contains(key, query);
687  break;
688  case RTContainedByStrategyNumber:
689  case RTOldContainedByStrategyNumber:
690  retval = (bool) gidx_overlaps(key, query);
691  break;
692  default:
693  retval = FALSE;
694  }
695 
696  return (retval);
697 }
698 
699 /*
700 ** GiST support function. Take in a query and an entry and see what the
701 ** relationship is, based on the query strategy.
702 */
704 Datum gserialized_gist_consistent(PG_FUNCTION_ARGS)
705 {
706  GISTENTRY *entry = (GISTENTRY*) PG_GETARG_POINTER(0);
707  StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
708  bool result;
709  char gidxmem[GIDX_MAX_SIZE];
710  GIDX *query_gbox_index = (GIDX*)gidxmem;
711 
712  /* PostgreSQL 8.4 and later require the RECHECK flag to be set here,
713  rather than being supplied as part of the operator class definition */
714  bool *recheck = (bool *) PG_GETARG_POINTER(4);
715 
716  /* We set recheck to false to avoid repeatedly pulling every "possibly matched" geometry
717  out during index scans. For cases when the geometries are large, rechecking
718  can make things twice as slow. */
719  *recheck = false;
720 
721  POSTGIS_DEBUG(4, "[GIST] 'consistent' function called");
722 
723  /* Quick sanity check on query argument. */
724  if ( DatumGetPointer(PG_GETARG_DATUM(1)) == NULL )
725  {
726  POSTGIS_DEBUG(4, "[GIST] null query pointer (!?!), returning false");
727  PG_RETURN_BOOL(FALSE); /* NULL query! This is screwy! */
728  }
729 
730  /* Quick sanity check on entry key. */
731  if ( DatumGetPointer(entry->key) == NULL )
732  {
733  POSTGIS_DEBUG(4, "[GIST] null index entry, returning false");
734  PG_RETURN_BOOL(FALSE); /* NULL entry! */
735  }
736 
737  /* Null box should never make this far. */
738  if ( gserialized_datum_get_gidx_p(PG_GETARG_DATUM(1), query_gbox_index) == LW_FAILURE )
739  {
740  POSTGIS_DEBUG(4, "[GIST] null query_gbox_index!");
741  PG_RETURN_BOOL(FALSE);
742  }
743 
744  /* Treat leaf node tests different from internal nodes */
745  if (GIST_LEAF(entry))
746  {
748  (GIDX*)DatumGetPointer(entry->key),
749  query_gbox_index, strategy);
750  }
751  else
752  {
754  (GIDX*)DatumGetPointer(entry->key),
755  query_gbox_index, strategy);
756  }
757 
758  PG_RETURN_BOOL(result);
759 }
760 
761 
762 /*
763 ** GiST support function. Calculate the "penalty" cost of adding this entry into an existing entry.
764 ** Calculate the change in volume of the old entry once the new entry is added.
765 ** TODO: Re-evaluate this in light of R*Tree penalty approaches.
766 */
768 Datum gserialized_gist_penalty(PG_FUNCTION_ARGS)
769 {
770  GISTENTRY *origentry = (GISTENTRY*) PG_GETARG_POINTER(0);
771  GISTENTRY *newentry = (GISTENTRY*) PG_GETARG_POINTER(1);
772  float *result = (float*) PG_GETARG_POINTER(2);
773  GIDX *gbox_index_orig, *gbox_index_new;
774  float size_union, size_orig;
775 
776  POSTGIS_DEBUG(4, "[GIST] 'penalty' function called");
777 
778  gbox_index_orig = (GIDX*)DatumGetPointer(origentry->key);
779  gbox_index_new = (GIDX*)DatumGetPointer(newentry->key);
780 
781  /* Drop out if we're dealing with null inputs. Shouldn't happen. */
782  if ( (gbox_index_orig == NULL) && (gbox_index_new == NULL) )
783  {
784  POSTGIS_DEBUG(4, "[GIST] both inputs NULL! returning penalty of zero");
785  *result = 0.0;
786  PG_RETURN_FLOAT8(*result);
787  }
788 
789  /* Calculate the size difference of the boxes (volume difference in this case). */
790  size_union = gidx_union_volume(gbox_index_orig, gbox_index_new);
791  size_orig = gidx_volume(gbox_index_orig);
792  *result = size_union - size_orig;
793 
794  /* All things being equal, we prefer to expand small boxes rather than large boxes.
795  NOTE: This code seemed to be causing badly balanced trees to be built
796  and therefore has been commented out. Not sure why it didn't work,
797  but it didn't.
798  if( FP_IS_ZERO(*result) )
799  if( FP_IS_ZERO(size_orig) )
800  *result = 0.0;
801  else
802  *result = 1.0 - (1.0/(1.0 + size_orig));
803  else
804  *result += 1.0;
805  */
806 
807  POSTGIS_DEBUGF(4, "[GIST] union size (%.12f), original size (%.12f), penalty (%.12f)", size_union, size_orig, *result);
808 
809  PG_RETURN_POINTER(result);
810 }
811 
812 /*
813 ** GiST support function. Merge all the boxes in a page into one master box.
814 */
816 Datum gserialized_gist_union(PG_FUNCTION_ARGS)
817 {
818  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
819  int *sizep = (int *) PG_GETARG_POINTER(1); /* Size of the return value */
820  int numranges, i;
821  GIDX *box_cur, *box_union;
822 
823  POSTGIS_DEBUG(4, "[GIST] 'union' function called");
824 
825  numranges = entryvec->n;
826 
827  box_cur = (GIDX*) DatumGetPointer(entryvec->vector[0].key);
828 
829  box_union = gidx_copy(box_cur);
830 
831  for ( i = 1; i < numranges; i++ )
832  {
833  box_cur = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
834  gidx_merge(&box_union, box_cur);
835  }
836 
837  *sizep = VARSIZE(box_union);
838 
839  POSTGIS_DEBUGF(4, "[GIST] union called, numranges(%i), pageunion %s", numranges, gidx_to_string(box_union));
840 
841  PG_RETURN_POINTER(box_union);
842 
843 }
844 
845 
846 
847 /*
848 ** GiST support function. Test equality of keys.
849 */
851 Datum gserialized_gist_same(PG_FUNCTION_ARGS)
852 {
853  GIDX *b1 = (GIDX*)PG_GETARG_POINTER(0);
854  GIDX *b2 = (GIDX*)PG_GETARG_POINTER(1);
855  bool *result = (bool*)PG_GETARG_POINTER(2);
856 
857  POSTGIS_DEBUG(4, "[GIST] 'same' function called");
858 
859  *result = gidx_equals(b1, b2);
860 
861  PG_RETURN_POINTER(result);
862 }
863 
864 
865 
866 /*
867 ** Utility function to add entries to the axis partition lists in the
868 ** picksplit function.
869 */
870 static void gserialized_gist_picksplit_addlist(OffsetNumber *list, GIDX **box_union, GIDX *box_current, int *pos, int num)
871 {
872  if ( *pos )
873  gidx_merge(box_union, box_current);
874  else
875  memcpy((void*)(*box_union), (void*)box_current, VARSIZE(box_current));
876  list[*pos] = num;
877  (*pos)++;
878 }
879 
880 /*
881 ** Utility function check whether the number of entries two halves of the
882 ** space constitute a "bad ratio" (poor balance).
883 */
885 {
886  POSTGIS_DEBUGF(4, "[GIST] checking split ratio (%d, %d)", x, y);
887  if ( (y == 0) || (((float)x / (float)y) < LIMIT_RATIO) ||
888  (x == 0) || (((float)y / (float)x) < LIMIT_RATIO) )
889  return TRUE;
890 
891  return FALSE;
892 }
893 
894 static bool gserialized_gist_picksplit_badratios(int *pos, int dims)
895 {
896  int i;
897  for ( i = 0; i < dims; i++ )
898  {
899  if ( gserialized_gist_picksplit_badratio(pos[2*i],pos[2*i+1]) == FALSE )
900  return FALSE;
901  }
902  return TRUE;
903 }
904 
905 
906 /*
907 ** Where the picksplit algorithm cannot find any basis for splitting one way
908 ** or another, we simply split the overflowing node in half.
909 */
910 static void gserialized_gist_picksplit_fallback(GistEntryVector *entryvec, GIST_SPLITVEC *v)
911 {
912  OffsetNumber i, maxoff;
913  GIDX *unionL = NULL;
914  GIDX *unionR = NULL;
915  int nbytes;
916 
917  POSTGIS_DEBUG(4, "[GIST] in fallback picksplit function");
918 
919  maxoff = entryvec->n - 1;
920 
921  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
922  v->spl_left = (OffsetNumber*) palloc(nbytes);
923  v->spl_right = (OffsetNumber*) palloc(nbytes);
924  v->spl_nleft = v->spl_nright = 0;
925 
926  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
927  {
928  GIDX *cur = (GIDX*)DatumGetPointer(entryvec->vector[i].key);
929 
930  if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
931  {
932  v->spl_left[v->spl_nleft] = i;
933  if (unionL == NULL)
934  {
935  unionL = gidx_copy(cur);
936  }
937  else
938  {
939  gidx_merge(&unionL, cur);
940  }
941  v->spl_nleft++;
942  }
943  else
944  {
945  v->spl_right[v->spl_nright] = i;
946  if (unionR == NULL)
947  {
948  unionR = gidx_copy(cur);
949  }
950  else
951  {
952  gidx_merge(&unionR, cur);
953  }
954  v->spl_nright++;
955  }
956  }
957 
958  if (v->spl_ldatum_exists)
959  gidx_merge(&unionL, (GIDX*)DatumGetPointer(v->spl_ldatum));
960 
961  v->spl_ldatum = PointerGetDatum(unionL);
962 
963  if (v->spl_rdatum_exists)
964  gidx_merge(&unionR, (GIDX*)DatumGetPointer(v->spl_rdatum));
965 
966  v->spl_rdatum = PointerGetDatum(unionR);
967  v->spl_ldatum_exists = v->spl_rdatum_exists = false;
968 }
969 
970 
971 
972 static void gserialized_gist_picksplit_constructsplit(GIST_SPLITVEC *v, OffsetNumber *list1, int nlist1, GIDX **union1, OffsetNumber *list2, int nlist2, GIDX **union2)
973 {
974  bool firstToLeft = true;
975 
976  POSTGIS_DEBUG(4, "[GIST] picksplit in constructsplit function");
977 
978  if (v->spl_ldatum_exists || v->spl_rdatum_exists)
979  {
980  if (v->spl_ldatum_exists && v->spl_rdatum_exists)
981  {
982  GIDX *LRl = gidx_copy(*union1);
983  GIDX *LRr = gidx_copy(*union2);
984  GIDX *RLl = gidx_copy(*union2);
985  GIDX *RLr = gidx_copy(*union1);
986  double sizeLR, sizeRL;
987 
988  gidx_merge(&LRl, (GIDX*)DatumGetPointer(v->spl_ldatum));
989  gidx_merge(&LRr, (GIDX*)DatumGetPointer(v->spl_rdatum));
990  gidx_merge(&RLl, (GIDX*)DatumGetPointer(v->spl_ldatum));
991  gidx_merge(&RLr, (GIDX*)DatumGetPointer(v->spl_rdatum));
992 
993  sizeLR = gidx_inter_volume(LRl,LRr);
994  sizeRL = gidx_inter_volume(RLl,RLr);
995 
996  POSTGIS_DEBUGF(4, "[GIST] sizeLR / sizeRL == %.12g / %.12g", sizeLR, sizeRL);
997 
998  if (sizeLR > sizeRL)
999  firstToLeft = false;
1000 
1001  }
1002  else
1003  {
1004  float p1, p2;
1005  GISTENTRY oldUnion, addon;
1006 
1007  gistentryinit(oldUnion, (v->spl_ldatum_exists) ? v->spl_ldatum : v->spl_rdatum,
1008  NULL, NULL, InvalidOffsetNumber, FALSE);
1009 
1010  gistentryinit(addon, PointerGetDatum(*union1), NULL, NULL, InvalidOffsetNumber, FALSE);
1011  DirectFunctionCall3(gserialized_gist_penalty, PointerGetDatum(&oldUnion), PointerGetDatum(&addon), PointerGetDatum(&p1));
1012  gistentryinit(addon, PointerGetDatum(*union2), NULL, NULL, InvalidOffsetNumber, FALSE);
1013  DirectFunctionCall3(gserialized_gist_penalty, PointerGetDatum(&oldUnion), PointerGetDatum(&addon), PointerGetDatum(&p2));
1014 
1015  POSTGIS_DEBUGF(4, "[GIST] p1 / p2 == %.12g / %.12g", p1, p2);
1016 
1017  if ((v->spl_ldatum_exists && p1 > p2) || (v->spl_rdatum_exists && p1 < p2))
1018  firstToLeft = false;
1019  }
1020  }
1021 
1022  POSTGIS_DEBUGF(4, "[GIST] firstToLeft == %d", firstToLeft);
1023 
1024  if (firstToLeft)
1025  {
1026  v->spl_left = list1;
1027  v->spl_right = list2;
1028  v->spl_nleft = nlist1;
1029  v->spl_nright = nlist2;
1030  if (v->spl_ldatum_exists)
1031  gidx_merge(union1, (GIDX*)DatumGetPointer(v->spl_ldatum));
1032  v->spl_ldatum = PointerGetDatum(*union1);
1033  if (v->spl_rdatum_exists)
1034  gidx_merge(union2, (GIDX*)DatumGetPointer(v->spl_rdatum));
1035  v->spl_rdatum = PointerGetDatum(*union2);
1036  }
1037  else
1038  {
1039  v->spl_left = list2;
1040  v->spl_right = list1;
1041  v->spl_nleft = nlist2;
1042  v->spl_nright = nlist1;
1043  if (v->spl_ldatum_exists)
1044  gidx_merge(union2, (GIDX*)DatumGetPointer(v->spl_ldatum));
1045  v->spl_ldatum = PointerGetDatum(*union2);
1046  if (v->spl_rdatum_exists)
1047  gidx_merge(union1, (GIDX*)DatumGetPointer(v->spl_rdatum));
1048  v->spl_rdatum = PointerGetDatum(*union1);
1049  }
1050 
1051  v->spl_ldatum_exists = v->spl_rdatum_exists = false;
1052 }
1053 
1054 
1055 #define BELOW(d) (2*(d))
1056 #define ABOVE(d) ((2*(d))+1)
1057 
1058 /*
1059 ** GiST support function. Split an overflowing node into two new nodes.
1060 ** Uses linear algorithm from Ang & Tan [2], dividing node extent into
1061 ** four quadrants, and splitting along the axis that most evenly distributes
1062 ** entries between the new nodes.
1063 ** TODO: Re-evaluate this in light of R*Tree picksplit approaches.
1064 */
1066 Datum gserialized_gist_picksplit(PG_FUNCTION_ARGS)
1067 {
1068 
1069  GistEntryVector *entryvec = (GistEntryVector*) PG_GETARG_POINTER(0);
1070 
1071  GIST_SPLITVEC *v = (GIST_SPLITVEC*) PG_GETARG_POINTER(1);
1072  OffsetNumber i;
1073  /* One union box for each half of the space. */
1074  GIDX **box_union;
1075  /* One offset number list for each half of the space. */
1076  OffsetNumber **list;
1077  /* One position index for each half of the space. */
1078  int *pos;
1079  GIDX *box_pageunion;
1080  GIDX *box_current;
1081  int direction = -1;
1082  bool all_entries_equal = true;
1083  OffsetNumber max_offset;
1084  int nbytes, ndims_pageunion, d;
1085  int posmin = entryvec->n;
1086 
1087  POSTGIS_DEBUG(4, "[GIST] 'picksplit' function called");
1088 
1089  /*
1090  ** First calculate the bounding box and maximum number of dimensions in this page.
1091  */
1092 
1093  max_offset = entryvec->n - 1;
1094  box_current = (GIDX*) DatumGetPointer(entryvec->vector[FirstOffsetNumber].key);
1095  box_pageunion = gidx_copy(box_current);
1096 
1097  /* Calculate the containing box (box_pageunion) for the whole page we are going to split. */
1098  for ( i = OffsetNumberNext(FirstOffsetNumber); i <= max_offset; i = OffsetNumberNext(i) )
1099  {
1100  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1101 
1102  if ( all_entries_equal == true && ! gidx_equals (box_pageunion, box_current) )
1103  all_entries_equal = false;
1104 
1105  gidx_merge( &box_pageunion, box_current );
1106  }
1107 
1108  POSTGIS_DEBUGF(3, "[GIST] box_pageunion: %s", gidx_to_string(box_pageunion));
1109 
1110  /* Every box in the page is the same! So, we split and just put half the boxes in each child. */
1111  if ( all_entries_equal )
1112  {
1113  POSTGIS_DEBUG(4, "[GIST] picksplit finds all entries equal!");
1115  PG_RETURN_POINTER(v);
1116  }
1117 
1118  /* Initialize memory structures. */
1119  nbytes = (max_offset + 2) * sizeof(OffsetNumber);
1120  ndims_pageunion = GIDX_NDIMS(box_pageunion);
1121  POSTGIS_DEBUGF(4, "[GIST] ndims_pageunion == %d", ndims_pageunion);
1122  pos = palloc(2*ndims_pageunion * sizeof(int));
1123  list = palloc(2*ndims_pageunion * sizeof(OffsetNumber*));
1124  box_union = palloc(2*ndims_pageunion * sizeof(GIDX*));
1125  for ( d = 0; d < ndims_pageunion; d++ )
1126  {
1127  list[BELOW(d)] = (OffsetNumber*) palloc(nbytes);
1128  list[ABOVE(d)] = (OffsetNumber*) palloc(nbytes);
1129  box_union[BELOW(d)] = gidx_new(ndims_pageunion);
1130  box_union[ABOVE(d)] = gidx_new(ndims_pageunion);
1131  pos[BELOW(d)] = 0;
1132  pos[ABOVE(d)] = 0;
1133  }
1134 
1135  /*
1136  ** Assign each entry in the node to the volume partitions it belongs to,
1137  ** such as "above the x/y plane, left of the y/z plane, below the x/z plane".
1138  ** Each entry thereby ends up in three of the six partitions.
1139  */
1140  POSTGIS_DEBUG(4, "[GIST] 'picksplit' calculating best split axis");
1141  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1142  {
1143  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1144 
1145  for ( d = 0; d < ndims_pageunion; d++ )
1146  {
1147  if ( GIDX_GET_MIN(box_current,d)-GIDX_GET_MIN(box_pageunion,d) < GIDX_GET_MAX(box_pageunion,d)-GIDX_GET_MAX(box_current,d) )
1148  {
1149  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1150  }
1151  else
1152  {
1153  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1154  }
1155 
1156  }
1157 
1158  }
1159 
1160  /*
1161  ** "Bad disposition", too many entries fell into one octant of the space, so no matter which
1162  ** plane we choose to split on, we're going to end up with a mostly full node. Where the
1163  ** data is pretty homogeneous (lots of duplicates) entries that are equidistant from the
1164  ** sides of the page union box can occasionally all end up in one place, leading
1165  ** to this condition.
1166  */
1167  if ( gserialized_gist_picksplit_badratios(pos,ndims_pageunion) == TRUE )
1168  {
1169  /*
1170  ** Instead we split on center points and see if we do better.
1171  ** First calculate the average center point for each axis.
1172  */
1173  double *avgCenter = palloc(ndims_pageunion * sizeof(double));
1174 
1175  for ( d = 0; d < ndims_pageunion; d++ )
1176  {
1177  avgCenter[d] = 0.0;
1178  }
1179 
1180  POSTGIS_DEBUG(4, "[GIST] picksplit can't find good split axis, trying center point method");
1181 
1182  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1183  {
1184  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1185  for ( d = 0; d < ndims_pageunion; d++ )
1186  {
1187  avgCenter[d] += (GIDX_GET_MAX(box_current,d) + GIDX_GET_MIN(box_current,d)) / 2.0;
1188  }
1189  }
1190  for ( d = 0; d < ndims_pageunion; d++ )
1191  {
1192  avgCenter[d] /= max_offset;
1193  pos[BELOW(d)] = pos[ABOVE(d)] = 0; /* Re-initialize our counters. */
1194  POSTGIS_DEBUGF(4, "[GIST] picksplit average center point[%d] = %.12g", d, avgCenter[d]);
1195  }
1196 
1197  /* For each of our entries... */
1198  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1199  {
1200  double center;
1201  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1202 
1203  for ( d = 0; d < ndims_pageunion; d++ )
1204  {
1205  center = (GIDX_GET_MIN(box_current,d)+GIDX_GET_MAX(box_current,d))/2.0;
1206  if ( center < avgCenter[d] )
1207  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1208  else if ( FPeq(center, avgCenter[d]) )
1209  if ( pos[BELOW(d)] > pos[ABOVE(d)] )
1210  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1211  else
1212  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1213  else
1214  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1215  }
1216 
1217  }
1218 
1219  /* Do we have a good disposition now? If not, screw it, just cut the node in half. */
1220  if ( gserialized_gist_picksplit_badratios(pos,ndims_pageunion) == TRUE )
1221  {
1222  POSTGIS_DEBUG(4, "[GIST] picksplit still cannot find a good split! just cutting the node in half");
1224  PG_RETURN_POINTER(v);
1225  }
1226 
1227  }
1228 
1229  /*
1230  ** Now, what splitting plane gives us the most even ratio of
1231  ** entries in our child pages? Since each split region has been apportioned entries
1232  ** against the same number of total entries, the axis that has the smallest maximum
1233  ** number of entries in its regions is the most evenly distributed.
1234  ** TODO: what if the distributions are equal in two or more axes?
1235  */
1236  for ( d = 0; d < ndims_pageunion; d++ )
1237  {
1238  int posd = Max(pos[ABOVE(d)],pos[BELOW(d)]);
1239  if ( posd < posmin )
1240  {
1241  direction = d;
1242  posmin = posd;
1243  }
1244  }
1245  if ( direction == -1 || posmin == entryvec->n )
1246  {
1247  /* ERROR OUT HERE */
1248  elog(ERROR, "Error in building split, unable to determine split direction.");
1249  }
1250 
1251  POSTGIS_DEBUGF(3, "[GIST] 'picksplit' splitting on axis %d", direction);
1252 
1254  pos[BELOW(direction)],
1255  &(box_union[BELOW(direction)]),
1256  list[ABOVE(direction)],
1257  pos[ABOVE(direction)],
1258  &(box_union[ABOVE(direction)]) );
1259 
1260  POSTGIS_DEBUGF(4, "[GIST] spl_ldatum: %s", gidx_to_string((GIDX*)v->spl_ldatum));
1261  POSTGIS_DEBUGF(4, "[GIST] spl_rdatum: %s", gidx_to_string((GIDX*)v->spl_rdatum));
1262 
1263  POSTGIS_DEBUGF(4, "[GIST] axis %d: parent range (%.12g, %.12g) left range (%.12g, %.12g), right range (%.12g, %.12g)",
1264  direction,
1265  GIDX_GET_MIN(box_pageunion, direction), GIDX_GET_MAX(box_pageunion, direction),
1266  GIDX_GET_MIN((GIDX*)v->spl_ldatum, direction), GIDX_GET_MAX((GIDX*)v->spl_ldatum, direction),
1267  GIDX_GET_MIN((GIDX*)v->spl_rdatum, direction), GIDX_GET_MAX((GIDX*)v->spl_rdatum, direction) );
1268 
1269  PG_RETURN_POINTER(v);
1270 
1271 }
1272 
1273 /*
1274 ** The GIDX key must be defined as a PostgreSQL type, even though it is only
1275 ** ever used internally. These no-op stubs are used to bind the type.
1276 */
1278 Datum gidx_in(PG_FUNCTION_ARGS)
1279 {
1280  ereport(ERROR,(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1281  errmsg("function gidx_in not implemented")));
1282  PG_RETURN_POINTER(NULL);
1283 }
1284 
1286 Datum gidx_out(PG_FUNCTION_ARGS)
1287 {
1288  ereport(ERROR,(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1289  errmsg("function gidx_out not implemented")));
1290  PG_RETURN_POINTER(NULL);
1291 }
static void gidx_merge(GIDX **b_union, GIDX *b_new)
static GIDX * gidx_copy(GIDX *b)
Datum gserialized_within(PG_FUNCTION_ARGS)
Datum gserialized_gist_decompress(PG_FUNCTION_ARGS)
static bool gidx_is_unknown(const GIDX *a)
static float gidx_volume(GIDX *a)
Datum gserialized_contains(PG_FUNCTION_ARGS)
static void gserialized_gist_picksplit_constructsplit(GIST_SPLITVEC *v, OffsetNumber *list1, int nlist1, GIDX **union1, OffsetNumber *list2, int nlist2, GIDX **union2)
Datum gserialized_gist_penalty(PG_FUNCTION_ARGS)
#define LW_SUCCESS
Definition: liblwgeom.h:55
static void gidx_set_unknown(GIDX *a)
static float gidx_union_volume(GIDX *a, GIDX *b)
static int gserialized_datum_predicate(Datum gs1, Datum gs2, gidx_predicate predicate)
Support function.
Datum gserialized_gist_union(PG_FUNCTION_ARGS)
char ** result
Definition: liblwgeom.h:218
static bool gserialized_gist_consistent_leaf(GIDX *key, GIDX *query, StrategyNumber strategy)
#define LW_FAILURE
Definition: liblwgeom.h:54
static void gidx_dimensionality_check(GIDX **a, GIDX **b)
static bool gidx_equals(GIDX *a, GIDX *b)
GSERIALIZED * gserialized_expand(GSERIALIZED *g, double distance)
Return a GSERIALIZED with an expanded bounding box.
#define LIMIT_RATIO
static void gidx_validate(GIDX *b)
Datum gserialized_gist_compress(PG_FUNCTION_ARGS)
#define LW_FALSE
Definition: liblwgeom.h:52
#define BELOW(d)
Datum gidx_in(PG_FUNCTION_ARGS)
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:51
static bool gserialized_gist_picksplit_badratios(int *pos, int dims)
Datum gserialized_gist_same(PG_FUNCTION_ARGS)
static int gserialized_gist_picksplit_badratio(int x, int y)
static void gserialized_gist_picksplit_fallback(GistEntryVector *entryvec, GIST_SPLITVEC *v)
#define isfinite
Definition: g_box.c:17
static float gidx_inter_volume(GIDX *a, GIDX *b)
tuple x
Definition: pixval.py:53
Datum distance(PG_FUNCTION_ARGS)
bool(* gidx_predicate)(GIDX *a, GIDX *b)
static void gserialized_gist_picksplit_addlist(OffsetNumber *list, GIDX **box_union, GIDX *box_current, int *pos, int num)
Datum gserialized_gist_picksplit(PG_FUNCTION_ARGS)
static bool gidx_overlaps(GIDX *a, GIDX *b)
#define FALSE
Definition: dbfopen.c:169
Datum gserialized_overlaps(PG_FUNCTION_ARGS)
static bool gidx_contains(GIDX *a, GIDX *b)
#define FPeq(A, B)
Definition: box2d.c:11
PG_FUNCTION_INFO_V1(gserialized_within)
Datum gserialized_gist_consistent(PG_FUNCTION_ARGS)
#define ABOVE(d)
#define TRUE
Definition: dbfopen.c:170
static bool gserialized_gist_consistent_internal(GIDX *key, GIDX *query, StrategyNumber strategy)
Datum gidx_out(PG_FUNCTION_ARGS)
tuple y
Definition: pixval.py:54
This library is the generic geometry handling section of PostGIS.