PostgreSQL Source Code  git master
gistproc.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * gistproc.c
4  * Support procedures for GiSTs over 2-D objects (boxes, polygons, circles,
5  * points).
6  *
7  * This gives R-tree behavior, with Guttman's poly-time split algorithm.
8  *
9  *
10  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
11  * Portions Copyright (c) 1994, Regents of the University of California
12  *
13  * IDENTIFICATION
14  * src/backend/access/gist/gistproc.c
15  *
16  *-------------------------------------------------------------------------
17  */
18 #include "postgres.h"
19 
20 #include <math.h>
21 
22 #include "access/gist.h"
23 #include "access/stratnum.h"
24 #include "utils/builtins.h"
25 #include "utils/float.h"
26 #include "utils/geo_decls.h"
27 #include "utils/sortsupport.h"
28 
29 
30 static bool gist_box_leaf_consistent(BOX *key, BOX *query,
31  StrategyNumber strategy);
32 static bool rtree_internal_consistent(BOX *key, BOX *query,
33  StrategyNumber strategy);
34 
35 static uint64 point_zorder_internal(float4 x, float4 y);
36 static uint64 part_bits32_by2(uint32 x);
37 static uint32 ieee_float32_to_uint32(float f);
38 static int gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup);
40 static int gist_bbox_zorder_cmp_abbrev(Datum z1, Datum z2, SortSupport ssup);
41 static bool gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup);
42 
43 
44 /* Minimum accepted ratio of split */
45 #define LIMIT_RATIO 0.3
46 
47 
48 /**************************************************
49  * Box ops
50  **************************************************/
51 
52 /*
53  * Calculates union of two boxes, a and b. The result is stored in *n.
54  */
55 static void
56 rt_box_union(BOX *n, const BOX *a, const BOX *b)
57 {
58  n->high.x = float8_max(a->high.x, b->high.x);
59  n->high.y = float8_max(a->high.y, b->high.y);
60  n->low.x = float8_min(a->low.x, b->low.x);
61  n->low.y = float8_min(a->low.y, b->low.y);
62 }
63 
64 /*
65  * Size of a BOX for penalty-calculation purposes.
66  * The result can be +Infinity, but not NaN.
67  */
68 static float8
69 size_box(const BOX *box)
70 {
71  /*
72  * Check for zero-width cases. Note that we define the size of a zero-
73  * by-infinity box as zero. It's important to special-case this somehow,
74  * as naively multiplying infinity by zero will produce NaN.
75  *
76  * The less-than cases should not happen, but if they do, say "zero".
77  */
78  if (float8_le(box->high.x, box->low.x) ||
79  float8_le(box->high.y, box->low.y))
80  return 0.0;
81 
82  /*
83  * We treat NaN as larger than +Infinity, so any distance involving a NaN
84  * and a non-NaN is infinite. Note the previous check eliminated the
85  * possibility that the low fields are NaNs.
86  */
87  if (isnan(box->high.x) || isnan(box->high.y))
88  return get_float8_infinity();
89  return float8_mul(float8_mi(box->high.x, box->low.x),
90  float8_mi(box->high.y, box->low.y));
91 }
92 
93 /*
94  * Return amount by which the union of the two boxes is larger than
95  * the original BOX's area. The result can be +Infinity, but not NaN.
96  */
97 static float8
98 box_penalty(const BOX *original, const BOX *new)
99 {
100  BOX unionbox;
101 
102  rt_box_union(&unionbox, original, new);
103  return float8_mi(size_box(&unionbox), size_box(original));
104 }
105 
106 /*
107  * The GiST Consistent method for boxes
108  *
109  * Should return false if for all data items x below entry,
110  * the predicate x op query must be false, where op is the oper
111  * corresponding to strategy in the pg_amop table.
112  */
113 Datum
115 {
116  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
117  BOX *query = PG_GETARG_BOX_P(1);
119 
120  /* Oid subtype = PG_GETARG_OID(3); */
121  bool *recheck = (bool *) PG_GETARG_POINTER(4);
122 
123  /* All cases served by this function are exact */
124  *recheck = false;
125 
126  if (DatumGetBoxP(entry->key) == NULL || query == NULL)
127  PG_RETURN_BOOL(false);
128 
129  /*
130  * if entry is not leaf, use rtree_internal_consistent, else use
131  * gist_box_leaf_consistent
132  */
133  if (GIST_LEAF(entry))
135  query,
136  strategy));
137  else
139  query,
140  strategy));
141 }
142 
143 /*
144  * Increase BOX b to include addon.
145  */
146 static void
147 adjustBox(BOX *b, const BOX *addon)
148 {
149  if (float8_lt(b->high.x, addon->high.x))
150  b->high.x = addon->high.x;
151  if (float8_gt(b->low.x, addon->low.x))
152  b->low.x = addon->low.x;
153  if (float8_lt(b->high.y, addon->high.y))
154  b->high.y = addon->high.y;
155  if (float8_gt(b->low.y, addon->low.y))
156  b->low.y = addon->low.y;
157 }
158 
159 /*
160  * The GiST Union method for boxes
161  *
162  * returns the minimal bounding box that encloses all the entries in entryvec
163  */
164 Datum
166 {
168  int *sizep = (int *) PG_GETARG_POINTER(1);
169  int numranges,
170  i;
171  BOX *cur,
172  *pageunion;
173 
174  numranges = entryvec->n;
175  pageunion = (BOX *) palloc(sizeof(BOX));
176  cur = DatumGetBoxP(entryvec->vector[0].key);
177  memcpy((void *) pageunion, (void *) cur, sizeof(BOX));
178 
179  for (i = 1; i < numranges; i++)
180  {
181  cur = DatumGetBoxP(entryvec->vector[i].key);
182  adjustBox(pageunion, cur);
183  }
184  *sizep = sizeof(BOX);
185 
186  PG_RETURN_POINTER(pageunion);
187 }
188 
189 /*
190  * We store boxes as boxes in GiST indexes, so we do not need
191  * compress, decompress, or fetch functions.
192  */
193 
194 /*
195  * The GiST Penalty method for boxes (also used for points)
196  *
197  * As in the R-tree paper, we use change in area as our penalty metric
198  */
199 Datum
201 {
202  GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
203  GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
204  float *result = (float *) PG_GETARG_POINTER(2);
205  BOX *origbox = DatumGetBoxP(origentry->key);
206  BOX *newbox = DatumGetBoxP(newentry->key);
207 
208  *result = (float) box_penalty(origbox, newbox);
209  PG_RETURN_POINTER(result);
210 }
211 
212 /*
213  * Trivial split: half of entries will be placed on one page
214  * and another half - to another
215  */
216 static void
218 {
219  OffsetNumber i,
220  maxoff;
221  BOX *unionL = NULL,
222  *unionR = NULL;
223  int nbytes;
224 
225  maxoff = entryvec->n - 1;
226 
227  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
228  v->spl_left = (OffsetNumber *) palloc(nbytes);
229  v->spl_right = (OffsetNumber *) palloc(nbytes);
230  v->spl_nleft = v->spl_nright = 0;
231 
232  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
233  {
234  BOX *cur = DatumGetBoxP(entryvec->vector[i].key);
235 
236  if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
237  {
238  v->spl_left[v->spl_nleft] = i;
239  if (unionL == NULL)
240  {
241  unionL = (BOX *) palloc(sizeof(BOX));
242  *unionL = *cur;
243  }
244  else
245  adjustBox(unionL, cur);
246 
247  v->spl_nleft++;
248  }
249  else
250  {
251  v->spl_right[v->spl_nright] = i;
252  if (unionR == NULL)
253  {
254  unionR = (BOX *) palloc(sizeof(BOX));
255  *unionR = *cur;
256  }
257  else
258  adjustBox(unionR, cur);
259 
260  v->spl_nright++;
261  }
262  }
263 
264  v->spl_ldatum = BoxPGetDatum(unionL);
265  v->spl_rdatum = BoxPGetDatum(unionR);
266 }
267 
268 /*
269  * Represents information about an entry that can be placed to either group
270  * without affecting overlap over selected axis ("common entry").
271  */
272 typedef struct
273 {
274  /* Index of entry in the initial array */
275  int index;
276  /* Delta between penalties of entry insertion into different groups */
278 } CommonEntry;
279 
280 /*
281  * Context for g_box_consider_split. Contains information about currently
282  * selected split and some general information.
283  */
284 typedef struct
285 {
286  int entriesCount; /* total number of entries being split */
287  BOX boundingBox; /* minimum bounding box across all entries */
288 
289  /* Information about currently selected split follows */
290 
291  bool first; /* true if no split was selected yet */
292 
293  float8 leftUpper; /* upper bound of left interval */
294  float8 rightLower; /* lower bound of right interval */
295 
298  int dim; /* axis of this split */
299  float8 range; /* width of general MBR projection to the
300  * selected axis */
302 
303 /*
304  * Interval represents projection of box to axis.
305  */
306 typedef struct
307 {
309  upper;
310 } SplitInterval;
311 
312 /*
313  * Interval comparison function by lower bound of the interval;
314  */
315 static int
316 interval_cmp_lower(const void *i1, const void *i2)
317 {
318  float8 lower1 = ((const SplitInterval *) i1)->lower,
319  lower2 = ((const SplitInterval *) i2)->lower;
320 
321  return float8_cmp_internal(lower1, lower2);
322 }
323 
324 /*
325  * Interval comparison function by upper bound of the interval;
326  */
327 static int
328 interval_cmp_upper(const void *i1, const void *i2)
329 {
330  float8 upper1 = ((const SplitInterval *) i1)->upper,
331  upper2 = ((const SplitInterval *) i2)->upper;
332 
333  return float8_cmp_internal(upper1, upper2);
334 }
335 
336 /*
337  * Replace negative (or NaN) value with zero.
338  */
339 static inline float
341 {
342  if (val >= 0.0f)
343  return val;
344  else
345  return 0.0f;
346 }
347 
348 /*
349  * Consider replacement of currently selected split with the better one.
350  */
351 static inline void
353  float8 rightLower, int minLeftCount,
354  float8 leftUpper, int maxLeftCount)
355 {
356  int leftCount,
357  rightCount;
358  float4 ratio,
359  overlap;
360  float8 range;
361 
362  /*
363  * Calculate entries distribution ratio assuming most uniform distribution
364  * of common entries.
365  */
366  if (minLeftCount >= (context->entriesCount + 1) / 2)
367  {
368  leftCount = minLeftCount;
369  }
370  else
371  {
372  if (maxLeftCount <= context->entriesCount / 2)
373  leftCount = maxLeftCount;
374  else
375  leftCount = context->entriesCount / 2;
376  }
377  rightCount = context->entriesCount - leftCount;
378 
379  /*
380  * Ratio of split - quotient between size of lesser group and total
381  * entries count.
382  */
383  ratio = float4_div(Min(leftCount, rightCount), context->entriesCount);
384 
385  if (ratio > LIMIT_RATIO)
386  {
387  bool selectthis = false;
388 
389  /*
390  * The ratio is acceptable, so compare current split with previously
391  * selected one. Between splits of one dimension we search for minimal
392  * overlap (allowing negative values) and minimal ration (between same
393  * overlaps. We switch dimension if find less overlap (non-negative)
394  * or less range with same overlap.
395  */
396  if (dimNum == 0)
397  range = float8_mi(context->boundingBox.high.x,
398  context->boundingBox.low.x);
399  else
400  range = float8_mi(context->boundingBox.high.y,
401  context->boundingBox.low.y);
402 
403  overlap = float8_div(float8_mi(leftUpper, rightLower), range);
404 
405  /* If there is no previous selection, select this */
406  if (context->first)
407  selectthis = true;
408  else if (context->dim == dimNum)
409  {
410  /*
411  * Within the same dimension, choose the new split if it has a
412  * smaller overlap, or same overlap but better ratio.
413  */
414  if (overlap < context->overlap ||
415  (overlap == context->overlap && ratio > context->ratio))
416  selectthis = true;
417  }
418  else
419  {
420  /*
421  * Across dimensions, choose the new split if it has a smaller
422  * *non-negative* overlap, or same *non-negative* overlap but
423  * bigger range. This condition differs from the one described in
424  * the article. On the datasets where leaf MBRs don't overlap
425  * themselves, non-overlapping splits (i.e. splits which have zero
426  * *non-negative* overlap) are frequently possible. In this case
427  * splits tends to be along one dimension, because most distant
428  * non-overlapping splits (i.e. having lowest negative overlap)
429  * appears to be in the same dimension as in the previous split.
430  * Therefore MBRs appear to be very prolonged along another
431  * dimension, which leads to bad search performance. Using range
432  * as the second split criteria makes MBRs more quadratic. Using
433  * *non-negative* overlap instead of overlap as the first split
434  * criteria gives to range criteria a chance to matter, because
435  * non-overlapping splits are equivalent in this criteria.
436  */
437  if (non_negative(overlap) < non_negative(context->overlap) ||
438  (range > context->range &&
439  non_negative(overlap) <= non_negative(context->overlap)))
440  selectthis = true;
441  }
442 
443  if (selectthis)
444  {
445  /* save information about selected split */
446  context->first = false;
447  context->ratio = ratio;
448  context->range = range;
449  context->overlap = overlap;
450  context->rightLower = rightLower;
451  context->leftUpper = leftUpper;
452  context->dim = dimNum;
453  }
454  }
455 }
456 
457 /*
458  * Compare common entries by their deltas.
459  */
460 static int
461 common_entry_cmp(const void *i1, const void *i2)
462 {
463  float8 delta1 = ((const CommonEntry *) i1)->delta,
464  delta2 = ((const CommonEntry *) i2)->delta;
465 
466  return float8_cmp_internal(delta1, delta2);
467 }
468 
469 /*
470  * --------------------------------------------------------------------------
471  * Double sorting split algorithm. This is used for both boxes and points.
472  *
473  * The algorithm finds split of boxes by considering splits along each axis.
474  * Each entry is first projected as an interval on the X-axis, and different
475  * ways to split the intervals into two groups are considered, trying to
476  * minimize the overlap of the groups. Then the same is repeated for the
477  * Y-axis, and the overall best split is chosen. The quality of a split is
478  * determined by overlap along that axis and some other criteria (see
479  * g_box_consider_split).
480  *
481  * After that, all the entries are divided into three groups:
482  *
483  * 1) Entries which should be placed to the left group
484  * 2) Entries which should be placed to the right group
485  * 3) "Common entries" which can be placed to any of groups without affecting
486  * of overlap along selected axis.
487  *
488  * The common entries are distributed by minimizing penalty.
489  *
490  * For details see:
491  * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
492  * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
493  * --------------------------------------------------------------------------
494  */
495 Datum
497 {
500  OffsetNumber i,
501  maxoff;
502  ConsiderSplitContext context;
503  BOX *box,
504  *leftBox,
505  *rightBox;
506  int dim,
507  commonEntriesCount;
508  SplitInterval *intervalsLower,
509  *intervalsUpper;
510  CommonEntry *commonEntries;
511  int nentries;
512 
513  memset(&context, 0, sizeof(ConsiderSplitContext));
514 
515  maxoff = entryvec->n - 1;
516  nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
517 
518  /* Allocate arrays for intervals along axes */
519  intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
520  intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
521 
522  /*
523  * Calculate the overall minimum bounding box over all the entries.
524  */
525  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
526  {
527  box = DatumGetBoxP(entryvec->vector[i].key);
528  if (i == FirstOffsetNumber)
529  context.boundingBox = *box;
530  else
531  adjustBox(&context.boundingBox, box);
532  }
533 
534  /*
535  * Iterate over axes for optimal split searching.
536  */
537  context.first = true; /* nothing selected yet */
538  for (dim = 0; dim < 2; dim++)
539  {
540  float8 leftUpper,
541  rightLower;
542  int i1,
543  i2;
544 
545  /* Project each entry as an interval on the selected axis. */
546  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
547  {
548  box = DatumGetBoxP(entryvec->vector[i].key);
549  if (dim == 0)
550  {
551  intervalsLower[i - FirstOffsetNumber].lower = box->low.x;
552  intervalsLower[i - FirstOffsetNumber].upper = box->high.x;
553  }
554  else
555  {
556  intervalsLower[i - FirstOffsetNumber].lower = box->low.y;
557  intervalsLower[i - FirstOffsetNumber].upper = box->high.y;
558  }
559  }
560 
561  /*
562  * Make two arrays of intervals: one sorted by lower bound and another
563  * sorted by upper bound.
564  */
565  memcpy(intervalsUpper, intervalsLower,
566  sizeof(SplitInterval) * nentries);
567  qsort(intervalsLower, nentries, sizeof(SplitInterval),
569  qsort(intervalsUpper, nentries, sizeof(SplitInterval),
571 
572  /*----
573  * The goal is to form a left and right interval, so that every entry
574  * interval is contained by either left or right interval (or both).
575  *
576  * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
577  *
578  * 0 1 2 3 4
579  * +-+
580  * +---+
581  * +-+
582  * +---+
583  *
584  * The left and right intervals are of the form (0,a) and (b,4).
585  * We first consider splits where b is the lower bound of an entry.
586  * We iterate through all entries, and for each b, calculate the
587  * smallest possible a. Then we consider splits where a is the
588  * upper bound of an entry, and for each a, calculate the greatest
589  * possible b.
590  *
591  * In the above example, the first loop would consider splits:
592  * b=0: (0,1)-(0,4)
593  * b=1: (0,1)-(1,4)
594  * b=2: (0,3)-(2,4)
595  *
596  * And the second loop:
597  * a=1: (0,1)-(1,4)
598  * a=3: (0,3)-(2,4)
599  * a=4: (0,4)-(2,4)
600  */
601 
602  /*
603  * Iterate over lower bound of right group, finding smallest possible
604  * upper bound of left group.
605  */
606  i1 = 0;
607  i2 = 0;
608  rightLower = intervalsLower[i1].lower;
609  leftUpper = intervalsUpper[i2].lower;
610  while (true)
611  {
612  /*
613  * Find next lower bound of right group.
614  */
615  while (i1 < nentries &&
616  float8_eq(rightLower, intervalsLower[i1].lower))
617  {
618  if (float8_lt(leftUpper, intervalsLower[i1].upper))
619  leftUpper = intervalsLower[i1].upper;
620  i1++;
621  }
622  if (i1 >= nentries)
623  break;
624  rightLower = intervalsLower[i1].lower;
625 
626  /*
627  * Find count of intervals which anyway should be placed to the
628  * left group.
629  */
630  while (i2 < nentries &&
631  float8_le(intervalsUpper[i2].upper, leftUpper))
632  i2++;
633 
634  /*
635  * Consider found split.
636  */
637  g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
638  }
639 
640  /*
641  * Iterate over upper bound of left group finding greatest possible
642  * lower bound of right group.
643  */
644  i1 = nentries - 1;
645  i2 = nentries - 1;
646  rightLower = intervalsLower[i1].upper;
647  leftUpper = intervalsUpper[i2].upper;
648  while (true)
649  {
650  /*
651  * Find next upper bound of left group.
652  */
653  while (i2 >= 0 && float8_eq(leftUpper, intervalsUpper[i2].upper))
654  {
655  if (float8_gt(rightLower, intervalsUpper[i2].lower))
656  rightLower = intervalsUpper[i2].lower;
657  i2--;
658  }
659  if (i2 < 0)
660  break;
661  leftUpper = intervalsUpper[i2].upper;
662 
663  /*
664  * Find count of intervals which anyway should be placed to the
665  * right group.
666  */
667  while (i1 >= 0 && float8_ge(intervalsLower[i1].lower, rightLower))
668  i1--;
669 
670  /*
671  * Consider found split.
672  */
673  g_box_consider_split(&context, dim,
674  rightLower, i1 + 1, leftUpper, i2 + 1);
675  }
676  }
677 
678  /*
679  * If we failed to find any acceptable splits, use trivial split.
680  */
681  if (context.first)
682  {
683  fallbackSplit(entryvec, v);
685  }
686 
687  /*
688  * Ok, we have now selected the split across one axis.
689  *
690  * While considering the splits, we already determined that there will be
691  * enough entries in both groups to reach the desired ratio, but we did
692  * not memorize which entries go to which group. So determine that now.
693  */
694 
695  /* Allocate vectors for results */
696  v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
697  v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
698  v->spl_nleft = 0;
699  v->spl_nright = 0;
700 
701  /* Allocate bounding boxes of left and right groups */
702  leftBox = palloc0(sizeof(BOX));
703  rightBox = palloc0(sizeof(BOX));
704 
705  /*
706  * Allocate an array for "common entries" - entries which can be placed to
707  * either group without affecting overlap along selected axis.
708  */
709  commonEntriesCount = 0;
710  commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
711 
712  /* Helper macros to place an entry in the left or right group */
713 #define PLACE_LEFT(box, off) \
714  do { \
715  if (v->spl_nleft > 0) \
716  adjustBox(leftBox, box); \
717  else \
718  *leftBox = *(box); \
719  v->spl_left[v->spl_nleft++] = off; \
720  } while(0)
721 
722 #define PLACE_RIGHT(box, off) \
723  do { \
724  if (v->spl_nright > 0) \
725  adjustBox(rightBox, box); \
726  else \
727  *rightBox = *(box); \
728  v->spl_right[v->spl_nright++] = off; \
729  } while(0)
730 
731  /*
732  * Distribute entries which can be distributed unambiguously, and collect
733  * common entries.
734  */
735  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
736  {
737  float8 lower,
738  upper;
739 
740  /*
741  * Get upper and lower bounds along selected axis.
742  */
743  box = DatumGetBoxP(entryvec->vector[i].key);
744  if (context.dim == 0)
745  {
746  lower = box->low.x;
747  upper = box->high.x;
748  }
749  else
750  {
751  lower = box->low.y;
752  upper = box->high.y;
753  }
754 
755  if (float8_le(upper, context.leftUpper))
756  {
757  /* Fits to the left group */
758  if (float8_ge(lower, context.rightLower))
759  {
760  /* Fits also to the right group, so "common entry" */
761  commonEntries[commonEntriesCount++].index = i;
762  }
763  else
764  {
765  /* Doesn't fit to the right group, so join to the left group */
766  PLACE_LEFT(box, i);
767  }
768  }
769  else
770  {
771  /*
772  * Each entry should fit on either left or right group. Since this
773  * entry didn't fit on the left group, it better fit in the right
774  * group.
775  */
776  Assert(float8_ge(lower, context.rightLower));
777 
778  /* Doesn't fit to the left group, so join to the right group */
779  PLACE_RIGHT(box, i);
780  }
781  }
782 
783  /*
784  * Distribute "common entries", if any.
785  */
786  if (commonEntriesCount > 0)
787  {
788  /*
789  * Calculate minimum number of entries that must be placed in both
790  * groups, to reach LIMIT_RATIO.
791  */
792  int m = ceil(LIMIT_RATIO * nentries);
793 
794  /*
795  * Calculate delta between penalties of join "common entries" to
796  * different groups.
797  */
798  for (i = 0; i < commonEntriesCount; i++)
799  {
800  box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
801  commonEntries[i].delta = Abs(float8_mi(box_penalty(leftBox, box),
802  box_penalty(rightBox, box)));
803  }
804 
805  /*
806  * Sort "common entries" by calculated deltas in order to distribute
807  * the most ambiguous entries first.
808  */
809  qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
810 
811  /*
812  * Distribute "common entries" between groups.
813  */
814  for (i = 0; i < commonEntriesCount; i++)
815  {
816  box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
817 
818  /*
819  * Check if we have to place this entry in either group to achieve
820  * LIMIT_RATIO.
821  */
822  if (v->spl_nleft + (commonEntriesCount - i) <= m)
823  PLACE_LEFT(box, commonEntries[i].index);
824  else if (v->spl_nright + (commonEntriesCount - i) <= m)
825  PLACE_RIGHT(box, commonEntries[i].index);
826  else
827  {
828  /* Otherwise select the group by minimal penalty */
829  if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
830  PLACE_LEFT(box, commonEntries[i].index);
831  else
832  PLACE_RIGHT(box, commonEntries[i].index);
833  }
834  }
835  }
836 
837  v->spl_ldatum = PointerGetDatum(leftBox);
838  v->spl_rdatum = PointerGetDatum(rightBox);
840 }
841 
842 /*
843  * Equality method
844  *
845  * This is used for boxes, points, circles, and polygons, all of which store
846  * boxes as GiST index entries.
847  *
848  * Returns true only when boxes are exactly the same. We can't use fuzzy
849  * comparisons here without breaking index consistency; therefore, this isn't
850  * equivalent to box_same().
851  */
852 Datum
854 {
855  BOX *b1 = PG_GETARG_BOX_P(0);
856  BOX *b2 = PG_GETARG_BOX_P(1);
857  bool *result = (bool *) PG_GETARG_POINTER(2);
858 
859  if (b1 && b2)
860  *result = (float8_eq(b1->low.x, b2->low.x) &&
861  float8_eq(b1->low.y, b2->low.y) &&
862  float8_eq(b1->high.x, b2->high.x) &&
863  float8_eq(b1->high.y, b2->high.y));
864  else
865  *result = (b1 == NULL && b2 == NULL);
866  PG_RETURN_POINTER(result);
867 }
868 
869 /*
870  * Leaf-level consistency for boxes: just apply the query operator
871  */
872 static bool
874 {
875  bool retval;
876 
877  switch (strategy)
878  {
881  PointerGetDatum(key),
882  PointerGetDatum(query)));
883  break;
886  PointerGetDatum(key),
887  PointerGetDatum(query)));
888  break;
891  PointerGetDatum(key),
892  PointerGetDatum(query)));
893  break;
896  PointerGetDatum(key),
897  PointerGetDatum(query)));
898  break;
901  PointerGetDatum(key),
902  PointerGetDatum(query)));
903  break;
906  PointerGetDatum(key),
907  PointerGetDatum(query)));
908  break;
912  PointerGetDatum(key),
913  PointerGetDatum(query)));
914  break;
918  PointerGetDatum(key),
919  PointerGetDatum(query)));
920  break;
923  PointerGetDatum(key),
924  PointerGetDatum(query)));
925  break;
928  PointerGetDatum(key),
929  PointerGetDatum(query)));
930  break;
933  PointerGetDatum(key),
934  PointerGetDatum(query)));
935  break;
938  PointerGetDatum(key),
939  PointerGetDatum(query)));
940  break;
941  default:
942  elog(ERROR, "unrecognized strategy number: %d", strategy);
943  retval = false; /* keep compiler quiet */
944  break;
945  }
946  return retval;
947 }
948 
949 /*****************************************
950  * Common rtree functions (for boxes, polygons, and circles)
951  *****************************************/
952 
953 /*
954  * Internal-page consistency for all these types
955  *
956  * We can use the same function since all types use bounding boxes as the
957  * internal-page representation.
958  */
959 static bool
961 {
962  bool retval;
963 
964  switch (strategy)
965  {
968  PointerGetDatum(key),
969  PointerGetDatum(query)));
970  break;
973  PointerGetDatum(key),
974  PointerGetDatum(query)));
975  break;
978  PointerGetDatum(key),
979  PointerGetDatum(query)));
980  break;
983  PointerGetDatum(key),
984  PointerGetDatum(query)));
985  break;
988  PointerGetDatum(key),
989  PointerGetDatum(query)));
990  break;
995  PointerGetDatum(key),
996  PointerGetDatum(query)));
997  break;
1001  PointerGetDatum(key),
1002  PointerGetDatum(query)));
1003  break;
1006  PointerGetDatum(key),
1007  PointerGetDatum(query)));
1008  break;
1009  case RTBelowStrategyNumber:
1011  PointerGetDatum(key),
1012  PointerGetDatum(query)));
1013  break;
1014  case RTAboveStrategyNumber:
1016  PointerGetDatum(key),
1017  PointerGetDatum(query)));
1018  break;
1021  PointerGetDatum(key),
1022  PointerGetDatum(query)));
1023  break;
1024  default:
1025  elog(ERROR, "unrecognized strategy number: %d", strategy);
1026  retval = false; /* keep compiler quiet */
1027  break;
1028  }
1029  return retval;
1030 }
1031 
1032 /**************************************************
1033  * Polygon ops
1034  **************************************************/
1035 
1036 /*
1037  * GiST compress for polygons: represent a polygon by its bounding box
1038  */
1039 Datum
1041 {
1042  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1043  GISTENTRY *retval;
1044 
1045  if (entry->leafkey)
1046  {
1047  POLYGON *in = DatumGetPolygonP(entry->key);
1048  BOX *r;
1049 
1050  r = (BOX *) palloc(sizeof(BOX));
1051  memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX));
1052 
1053  retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1054  gistentryinit(*retval, PointerGetDatum(r),
1055  entry->rel, entry->page,
1056  entry->offset, false);
1057  }
1058  else
1059  retval = entry;
1060  PG_RETURN_POINTER(retval);
1061 }
1062 
1063 /*
1064  * The GiST Consistent method for polygons
1065  */
1066 Datum
1068 {
1069  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1070  POLYGON *query = PG_GETARG_POLYGON_P(1);
1072 
1073  /* Oid subtype = PG_GETARG_OID(3); */
1074  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1075  bool result;
1076 
1077  /* All cases served by this function are inexact */
1078  *recheck = true;
1079 
1080  if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1081  PG_RETURN_BOOL(false);
1082 
1083  /*
1084  * Since the operators require recheck anyway, we can just use
1085  * rtree_internal_consistent even at leaf nodes. (This works in part
1086  * because the index entries are bounding boxes not polygons.)
1087  */
1088  result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1089  &(query->boundbox), strategy);
1090 
1091  /* Avoid memory leak if supplied poly is toasted */
1092  PG_FREE_IF_COPY(query, 1);
1093 
1094  PG_RETURN_BOOL(result);
1095 }
1096 
1097 /**************************************************
1098  * Circle ops
1099  **************************************************/
1100 
1101 /*
1102  * GiST compress for circles: represent a circle by its bounding box
1103  */
1104 Datum
1106 {
1107  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1108  GISTENTRY *retval;
1109 
1110  if (entry->leafkey)
1111  {
1112  CIRCLE *in = DatumGetCircleP(entry->key);
1113  BOX *r;
1114 
1115  r = (BOX *) palloc(sizeof(BOX));
1116  r->high.x = float8_pl(in->center.x, in->radius);
1117  r->low.x = float8_mi(in->center.x, in->radius);
1118  r->high.y = float8_pl(in->center.y, in->radius);
1119  r->low.y = float8_mi(in->center.y, in->radius);
1120 
1121  retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1122  gistentryinit(*retval, PointerGetDatum(r),
1123  entry->rel, entry->page,
1124  entry->offset, false);
1125  }
1126  else
1127  retval = entry;
1128  PG_RETURN_POINTER(retval);
1129 }
1130 
1131 /*
1132  * The GiST Consistent method for circles
1133  */
1134 Datum
1136 {
1137  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1138  CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1140 
1141  /* Oid subtype = PG_GETARG_OID(3); */
1142  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1143  BOX bbox;
1144  bool result;
1145 
1146  /* All cases served by this function are inexact */
1147  *recheck = true;
1148 
1149  if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1150  PG_RETURN_BOOL(false);
1151 
1152  /*
1153  * Since the operators require recheck anyway, we can just use
1154  * rtree_internal_consistent even at leaf nodes. (This works in part
1155  * because the index entries are bounding boxes not circles.)
1156  */
1157  bbox.high.x = float8_pl(query->center.x, query->radius);
1158  bbox.low.x = float8_mi(query->center.x, query->radius);
1159  bbox.high.y = float8_pl(query->center.y, query->radius);
1160  bbox.low.y = float8_mi(query->center.y, query->radius);
1161 
1162  result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1163  &bbox, strategy);
1164 
1165  PG_RETURN_BOOL(result);
1166 }
1167 
1168 /**************************************************
1169  * Point ops
1170  **************************************************/
1171 
1172 Datum
1174 {
1175  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1176 
1177  if (entry->leafkey) /* Point, actually */
1178  {
1179  BOX *box = palloc(sizeof(BOX));
1180  Point *point = DatumGetPointP(entry->key);
1181  GISTENTRY *retval = palloc(sizeof(GISTENTRY));
1182 
1183  box->high = box->low = *point;
1184 
1185  gistentryinit(*retval, BoxPGetDatum(box),
1186  entry->rel, entry->page, entry->offset, false);
1187 
1188  PG_RETURN_POINTER(retval);
1189  }
1190 
1191  PG_RETURN_POINTER(entry);
1192 }
1193 
1194 /*
1195  * GiST Fetch method for point
1196  *
1197  * Get point coordinates from its bounding box coordinates and form new
1198  * gistentry.
1199  */
1200 Datum
1202 {
1203  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1204  BOX *in = DatumGetBoxP(entry->key);
1205  Point *r;
1206  GISTENTRY *retval;
1207 
1208  retval = palloc(sizeof(GISTENTRY));
1209 
1210  r = (Point *) palloc(sizeof(Point));
1211  r->x = in->high.x;
1212  r->y = in->high.y;
1213  gistentryinit(*retval, PointerGetDatum(r),
1214  entry->rel, entry->page,
1215  entry->offset, false);
1216 
1217  PG_RETURN_POINTER(retval);
1218 }
1219 
1220 
1221 #define point_point_distance(p1,p2) \
1222  DatumGetFloat8(DirectFunctionCall2(point_distance, \
1223  PointPGetDatum(p1), PointPGetDatum(p2)))
1224 
1225 static float8
1226 computeDistance(bool isLeaf, BOX *box, Point *point)
1227 {
1228  float8 result = 0.0;
1229 
1230  if (isLeaf)
1231  {
1232  /* simple point to point distance */
1233  result = point_point_distance(point, &box->low);
1234  }
1235  else if (point->x <= box->high.x && point->x >= box->low.x &&
1236  point->y <= box->high.y && point->y >= box->low.y)
1237  {
1238  /* point inside the box */
1239  result = 0.0;
1240  }
1241  else if (point->x <= box->high.x && point->x >= box->low.x)
1242  {
1243  /* point is over or below box */
1244  Assert(box->low.y <= box->high.y);
1245  if (point->y > box->high.y)
1246  result = float8_mi(point->y, box->high.y);
1247  else if (point->y < box->low.y)
1248  result = float8_mi(box->low.y, point->y);
1249  else
1250  elog(ERROR, "inconsistent point values");
1251  }
1252  else if (point->y <= box->high.y && point->y >= box->low.y)
1253  {
1254  /* point is to left or right of box */
1255  Assert(box->low.x <= box->high.x);
1256  if (point->x > box->high.x)
1257  result = float8_mi(point->x, box->high.x);
1258  else if (point->x < box->low.x)
1259  result = float8_mi(box->low.x, point->x);
1260  else
1261  elog(ERROR, "inconsistent point values");
1262  }
1263  else
1264  {
1265  /* closest point will be a vertex */
1266  Point p;
1267  float8 subresult;
1268 
1269  result = point_point_distance(point, &box->low);
1270 
1271  subresult = point_point_distance(point, &box->high);
1272  if (result > subresult)
1273  result = subresult;
1274 
1275  p.x = box->low.x;
1276  p.y = box->high.y;
1277  subresult = point_point_distance(point, &p);
1278  if (result > subresult)
1279  result = subresult;
1280 
1281  p.x = box->high.x;
1282  p.y = box->low.y;
1283  subresult = point_point_distance(point, &p);
1284  if (result > subresult)
1285  result = subresult;
1286  }
1287 
1288  return result;
1289 }
1290 
1291 static bool
1293  bool isLeaf, BOX *key, Point *query)
1294 {
1295  bool result = false;
1296 
1297  switch (strategy)
1298  {
1299  case RTLeftStrategyNumber:
1300  result = FPlt(key->low.x, query->x);
1301  break;
1302  case RTRightStrategyNumber:
1303  result = FPgt(key->high.x, query->x);
1304  break;
1305  case RTAboveStrategyNumber:
1306  result = FPgt(key->high.y, query->y);
1307  break;
1308  case RTBelowStrategyNumber:
1309  result = FPlt(key->low.y, query->y);
1310  break;
1311  case RTSameStrategyNumber:
1312  if (isLeaf)
1313  {
1314  /* key.high must equal key.low, so we can disregard it */
1315  result = (FPeq(key->low.x, query->x) &&
1316  FPeq(key->low.y, query->y));
1317  }
1318  else
1319  {
1320  result = (FPle(query->x, key->high.x) &&
1321  FPge(query->x, key->low.x) &&
1322  FPle(query->y, key->high.y) &&
1323  FPge(query->y, key->low.y));
1324  }
1325  break;
1326  default:
1327  elog(ERROR, "unrecognized strategy number: %d", strategy);
1328  result = false; /* keep compiler quiet */
1329  break;
1330  }
1331 
1332  return result;
1333 }
1334 
1335 #define GeoStrategyNumberOffset 20
1336 #define PointStrategyNumberGroup 0
1337 #define BoxStrategyNumberGroup 1
1338 #define PolygonStrategyNumberGroup 2
1339 #define CircleStrategyNumberGroup 3
1340 
1341 Datum
1343 {
1344  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1346  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1347  bool result;
1348  StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1349 
1350  switch (strategyGroup)
1351  {
1354  GIST_LEAF(entry),
1355  DatumGetBoxP(entry->key),
1356  PG_GETARG_POINT_P(1));
1357  *recheck = false;
1358  break;
1360  {
1361  /*
1362  * The only operator in this group is point <@ box (on_pb), so
1363  * we needn't examine strategy again.
1364  *
1365  * For historical reasons, on_pb uses exact rather than fuzzy
1366  * comparisons. We could use box_overlap when at an internal
1367  * page, but that would lead to possibly visiting child pages
1368  * uselessly, because box_overlap uses fuzzy comparisons.
1369  * Instead we write a non-fuzzy overlap test. The same code
1370  * will also serve for leaf-page tests, since leaf keys have
1371  * high == low.
1372  */
1373  BOX *query,
1374  *key;
1375 
1376  query = PG_GETARG_BOX_P(1);
1377  key = DatumGetBoxP(entry->key);
1378 
1379  result = (key->high.x >= query->low.x &&
1380  key->low.x <= query->high.x &&
1381  key->high.y >= query->low.y &&
1382  key->low.y <= query->high.y);
1383  *recheck = false;
1384  }
1385  break;
1387  {
1388  POLYGON *query = PG_GETARG_POLYGON_P(1);
1389 
1391  PointerGetDatum(entry),
1392  PolygonPGetDatum(query),
1394  0, PointerGetDatum(recheck)));
1395 
1396  if (GIST_LEAF(entry) && result)
1397  {
1398  /*
1399  * We are on leaf page and quick check shows overlapping
1400  * of polygon's bounding box and point
1401  */
1402  BOX *box = DatumGetBoxP(entry->key);
1403 
1404  Assert(box->high.x == box->low.x
1405  && box->high.y == box->low.y);
1407  PolygonPGetDatum(query),
1408  PointPGetDatum(&box->high)));
1409  *recheck = false;
1410  }
1411  }
1412  break;
1414  {
1415  CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1416 
1418  PointerGetDatum(entry),
1419  CirclePGetDatum(query),
1421  0, PointerGetDatum(recheck)));
1422 
1423  if (GIST_LEAF(entry) && result)
1424  {
1425  /*
1426  * We are on leaf page and quick check shows overlapping
1427  * of polygon's bounding box and point
1428  */
1429  BOX *box = DatumGetBoxP(entry->key);
1430 
1431  Assert(box->high.x == box->low.x
1432  && box->high.y == box->low.y);
1434  CirclePGetDatum(query),
1435  PointPGetDatum(&box->high)));
1436  *recheck = false;
1437  }
1438  }
1439  break;
1440  default:
1441  elog(ERROR, "unrecognized strategy number: %d", strategy);
1442  result = false; /* keep compiler quiet */
1443  break;
1444  }
1445 
1446  PG_RETURN_BOOL(result);
1447 }
1448 
1449 Datum
1451 {
1452  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1454  float8 distance;
1455  StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1456 
1457  switch (strategyGroup)
1458  {
1460  distance = computeDistance(GIST_LEAF(entry),
1461  DatumGetBoxP(entry->key),
1462  PG_GETARG_POINT_P(1));
1463  break;
1464  default:
1465  elog(ERROR, "unrecognized strategy number: %d", strategy);
1466  distance = 0.0; /* keep compiler quiet */
1467  break;
1468  }
1469 
1470  PG_RETURN_FLOAT8(distance);
1471 }
1472 
1473 static float8
1475 {
1476  float8 distance;
1477  StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1478 
1479  switch (strategyGroup)
1480  {
1482  distance = computeDistance(false,
1483  DatumGetBoxP(entry->key),
1484  DatumGetPointP(query));
1485  break;
1486  default:
1487  elog(ERROR, "unrecognized strategy number: %d", strategy);
1488  distance = 0.0; /* keep compiler quiet */
1489  }
1490 
1491  return distance;
1492 }
1493 
1494 Datum
1496 {
1497  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1498  Datum query = PG_GETARG_DATUM(1);
1500 
1501  /* Oid subtype = PG_GETARG_OID(3); */
1502  /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */
1503  float8 distance;
1504 
1505  distance = gist_bbox_distance(entry, query, strategy);
1506 
1507  PG_RETURN_FLOAT8(distance);
1508 }
1509 
1510 /*
1511  * The inexact GiST distance methods for geometric types that store bounding
1512  * boxes.
1513  *
1514  * Compute lossy distance from point to index entries. The result is inexact
1515  * because index entries are bounding boxes, not the exact shapes of the
1516  * indexed geometric types. We use distance from point to MBR of index entry.
1517  * This is a lower bound estimate of distance from point to indexed geometric
1518  * type.
1519  */
1520 Datum
1522 {
1523  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1524  Datum query = PG_GETARG_DATUM(1);
1526 
1527  /* Oid subtype = PG_GETARG_OID(3); */
1528  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1529  float8 distance;
1530 
1531  distance = gist_bbox_distance(entry, query, strategy);
1532  *recheck = true;
1533 
1534  PG_RETURN_FLOAT8(distance);
1535 }
1536 
1537 Datum
1539 {
1540  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1541  Datum query = PG_GETARG_DATUM(1);
1543 
1544  /* Oid subtype = PG_GETARG_OID(3); */
1545  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1546  float8 distance;
1547 
1548  distance = gist_bbox_distance(entry, query, strategy);
1549  *recheck = true;
1550 
1551  PG_RETURN_FLOAT8(distance);
1552 }
1553 
1554 /*
1555  * Z-order routines for fast index build
1556  */
1557 
1558 /*
1559  * Compute Z-value of a point
1560  *
1561  * Z-order (also known as Morton Code) maps a two-dimensional point to a
1562  * single integer, in a way that preserves locality. Points that are close in
1563  * the two-dimensional space are mapped to integer that are not far from each
1564  * other. We do that by interleaving the bits in the X and Y components.
1565  *
1566  * Morton Code is normally defined only for integers, but the X and Y values
1567  * of a point are floating point. We expect floats to be in IEEE format.
1568  */
1569 static uint64
1571 {
1574 
1575  /* Interleave the bits */
1576  return part_bits32_by2(ix) | (part_bits32_by2(iy) << 1);
1577 }
1578 
1579 /* Interleave 32 bits with zeroes */
1580 static uint64
1582 {
1583  uint64 n = x;
1584 
1585  n = (n | (n << 16)) & UINT64CONST(0x0000FFFF0000FFFF);
1586  n = (n | (n << 8)) & UINT64CONST(0x00FF00FF00FF00FF);
1587  n = (n | (n << 4)) & UINT64CONST(0x0F0F0F0F0F0F0F0F);
1588  n = (n | (n << 2)) & UINT64CONST(0x3333333333333333);
1589  n = (n | (n << 1)) & UINT64CONST(0x5555555555555555);
1590 
1591  return n;
1592 }
1593 
1594 /*
1595  * Convert a 32-bit IEEE float to uint32 in a way that preserves the ordering
1596  */
1597 static uint32
1599 {
1600  /*----
1601  *
1602  * IEEE 754 floating point format
1603  * ------------------------------
1604  *
1605  * IEEE 754 floating point numbers have this format:
1606  *
1607  * exponent (8 bits)
1608  * |
1609  * s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm
1610  * | |
1611  * sign mantissa (23 bits)
1612  *
1613  * Infinity has all bits in the exponent set and the mantissa is all
1614  * zeros. Negative infinity is the same but with the sign bit set.
1615  *
1616  * NaNs are represented with all bits in the exponent set, and the least
1617  * significant bit in the mantissa also set. The rest of the mantissa bits
1618  * can be used to distinguish different kinds of NaNs.
1619  *
1620  * The IEEE format has the nice property that when you take the bit
1621  * representation and interpret it as an integer, the order is preserved,
1622  * except for the sign. That holds for the +-Infinity values too.
1623  *
1624  * Mapping to uint32
1625  * -----------------
1626  *
1627  * In order to have a smooth transition from negative to positive numbers,
1628  * we map floats to unsigned integers like this:
1629  *
1630  * x < 0 to range 0-7FFFFFFF
1631  * x = 0 to value 8000000 (both positive and negative zero)
1632  * x > 0 to range 8000001-FFFFFFFF
1633  *
1634  * We don't care to distinguish different kind of NaNs, so they are all
1635  * mapped to the same arbitrary value, FFFFFFFF. Because of the IEEE bit
1636  * representation of NaNs, there aren't any non-NaN values that would be
1637  * mapped to FFFFFFFF. In fact, there is a range of unused values on both
1638  * ends of the uint32 space.
1639  */
1640  if (isnan(f))
1641  return 0xFFFFFFFF;
1642  else
1643  {
1644  union
1645  {
1646  float f;
1647  uint32 i;
1648  } u;
1649 
1650  u.f = f;
1651 
1652  /* Check the sign bit */
1653  if ((u.i & 0x80000000) != 0)
1654  {
1655  /*
1656  * Map the negative value to range 0-7FFFFFFF. This flips the sign
1657  * bit to 0 in the same instruction.
1658  */
1659  Assert(f <= 0); /* can be -0 */
1660  u.i ^= 0xFFFFFFFF;
1661  }
1662  else
1663  {
1664  /* Map the positive value (or 0) to range 80000000-FFFFFFFF */
1665  u.i |= 0x80000000;
1666  }
1667 
1668  return u.i;
1669  }
1670 }
1671 
1672 /*
1673  * Compare the Z-order of points
1674  */
1675 static int
1677 {
1678  Point *p1 = &(DatumGetBoxP(a)->low);
1679  Point *p2 = &(DatumGetBoxP(b)->low);
1680  uint64 z1;
1681  uint64 z2;
1682 
1683  /*
1684  * Do a quick check for equality first. It's not clear if this is worth it
1685  * in general, but certainly is when used as tie-breaker with abbreviated
1686  * keys,
1687  */
1688  if (p1->x == p2->x && p1->y == p2->y)
1689  return 0;
1690 
1691  z1 = point_zorder_internal(p1->x, p1->y);
1692  z2 = point_zorder_internal(p2->x, p2->y);
1693  if (z1 > z2)
1694  return 1;
1695  else if (z1 < z2)
1696  return -1;
1697  else
1698  return 0;
1699 }
1700 
1701 /*
1702  * Abbreviated version of Z-order comparison
1703  *
1704  * The abbreviated format is a Z-order value computed from the two 32-bit
1705  * floats. If SIZEOF_DATUM == 8, the 64-bit Z-order value fits fully in the
1706  * abbreviated Datum, otherwise use its most significant bits.
1707  */
1708 static Datum
1710 {
1711  Point *p = &(DatumGetBoxP(original)->low);
1712  uint64 z;
1713 
1714  z = point_zorder_internal(p->x, p->y);
1715 
1716 #if SIZEOF_DATUM == 8
1717  return (Datum) z;
1718 #else
1719  return (Datum) (z >> 32);
1720 #endif
1721 }
1722 
1723 static int
1725 {
1726  /*
1727  * Compare the pre-computed Z-orders as unsigned integers. Datum is a
1728  * typedef for 'uintptr_t', so no casting is required.
1729  */
1730  if (z1 > z2)
1731  return 1;
1732  else if (z1 < z2)
1733  return -1;
1734  else
1735  return 0;
1736 }
1737 
1738 /*
1739  * We never consider aborting the abbreviation.
1740  *
1741  * On 64-bit systems, the abbreviation is not lossy so it is always
1742  * worthwhile. (Perhaps it's not on 32-bit systems, but we don't bother
1743  * with logic to decide.)
1744  */
1745 static bool
1747 {
1748  return false;
1749 }
1750 
1751 /*
1752  * Sort support routine for fast GiST index build by sorting.
1753  */
1754 Datum
1756 {
1758 
1759  if (ssup->abbreviate)
1760  {
1765  }
1766  else
1767  {
1769  }
1770  PG_RETURN_VOID();
1771 }
#define GIST_LEAF(entry)
Definition: gist.h:162
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
Datum box_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:597
Relation rel
Definition: gist.h:153
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:360
Datum box_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:669
float8 lower
Definition: gistproc.c:308
static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:960
static float8 size_box(const BOX *box)
Definition: gistproc.c:69
#define GeoStrategyNumberOffset
Definition: gistproc.c:1335
Datum box_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:539
Definition: geo_decls.h:99
#define PLACE_LEFT(box, off)
#define BoxStrategyNumberGroup
Definition: gistproc.c:1337
static bool gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:873
static float4 float4_div(const float4 val1, const float4 val2)
Definition: float.h:221
#define PG_GETARG_BOX_P(n)
Definition: geo_decls.h:158
Datum box_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:571
static float8 get_float8_infinity(void)
Definition: float.h:93
#define RTOldContainsStrategyNumber
Definition: stratnum.h:63
#define RTOldContainedByStrategyNumber
Definition: stratnum.h:64
float8 x
Definition: geo_decls.h:57
#define RTLeftStrategyNumber
Definition: stratnum.h:51
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:44
static float8 float8_min(const float8 val1, const float8 val2)
Definition: float.h:339
float8 radius
Definition: geo_decls.h:124
static int interval_cmp_lower(const void *i1, const void *i2)
Definition: gistproc.c:316
Datum box_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:612
#define CircleStrategyNumberGroup
Definition: gistproc.c:1339
#define PointerGetDatum(X)
Definition: postgres.h:556
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
float8 delta
Definition: gistproc.c:277
static int interval_cmp_upper(const void *i1, const void *i2)
Definition: gistproc.c:328
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:365
#define Min(x, y)
Definition: c.h:927
static uint64 part_bits32_by2(uint32 x)
Definition: gistproc.c:1581
#define PolygonPGetDatum(X)
Definition: geo_decls.h:163
Datum gist_point_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1342
Datum box_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:551
OffsetNumber * spl_left
Definition: gist.h:134
Datum spl_rdatum
Definition: gist.h:141
#define Int16GetDatum(X)
Definition: postgres.h:451
#define RTOverBelowStrategyNumber
Definition: stratnum.h:59
static int common_entry_cmp(const void *i1, const void *i2)
Definition: gistproc.c:461
static bool float8_le(const float8 val1, const float8 val2)
Definition: float.h:303
int32 n
Definition: gist.h:227
Datum gist_box_same(PG_FUNCTION_ARGS)
Definition: gistproc.c:853
Datum gist_box_picksplit(PG_FUNCTION_ARGS)
Definition: gistproc.c:496
struct cursor * cur
Definition: ecpg.c:28
uint16 StrategyNumber
Definition: stratnum.h:22
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Datum poly_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4041
Datum gist_point_fetch(PG_FUNCTION_ARGS)
Definition: gistproc.c:1201
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:75
static float8 float8_mul(const float8 val1, const float8 val2)
Definition: float.h:207
int spl_nleft
Definition: gist.h:135
#define PLACE_RIGHT(box, off)
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define PG_GETARG_POLYGON_P(n)
Definition: geo_decls.h:164
Datum gist_box_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:114
int float8_cmp_internal(float8 a, float8 b)
Definition: float.c:914
#define PointStrategyNumberGroup
Definition: gistproc.c:1336
Datum gist_poly_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1040
uint16 OffsetNumber
Definition: off.h:24
Page page
Definition: gist.h:154
#define Abs(x)
Definition: c.h:933
Definition: type.h:89
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:228
#define RTOverAboveStrategyNumber
Definition: stratnum.h:62
#define CirclePGetDatum(X)
Definition: geo_decls.h:169
#define FPgt(A, B)
Definition: geo_decls.h:38
Datum gist_point_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1450
#define point_point_distance(p1, p2)
Definition: gistproc.c:1221
static uint64 point_zorder_internal(float4 x, float4 y)
Definition: gistproc.c:1570
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, float8 rightLower, int minLeftCount, float8 leftUpper, int maxLeftCount)
Definition: gistproc.c:352
#define ERROR
Definition: elog.h:43
double float8
Definition: c.h:498
int spl_nright
Definition: gist.h:140
#define PG_GETARG_POINT_P(n)
Definition: geo_decls.h:136
Datum box_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:680
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
Datum key
Definition: gist.h:152
Datum box_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:646
static Datum gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup)
Definition: gistproc.c:1709
#define DatumGetCircleP(X)
Definition: geo_decls.h:168
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
static float8 computeDistance(bool isLeaf, BOX *box, Point *point)
Definition: gistproc.c:1226
#define FirstOffsetNumber
Definition: off.h:27
static void rt_box_union(BOX *n, const BOX *a, const BOX *b)
Definition: gistproc.c:56
#define DatumGetBool(X)
Definition: postgres.h:393
#define RTSameStrategyNumber
Definition: stratnum.h:56
static int gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup)
Definition: gistproc.c:1676
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
static bool float8_ge(const float8 val1, const float8 val2)
Definition: float.h:327
unsigned int uint32
Definition: c.h:374
static float8 float8_pl(const float8 val1, const float8 val2)
Definition: float.h:157
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
Definition: gistproc.c:217
static float8 float8_mi(const float8 val1, const float8 val2)
Definition: float.h:181
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
#define RTOverRightStrategyNumber
Definition: stratnum.h:54
static bool gist_point_consistent_internal(StrategyNumber strategy, bool isLeaf, BOX *key, Point *query)
Definition: gistproc.c:1292
bool leafkey
Definition: gist.h:156
static bool float8_lt(const float8 val1, const float8 val2)
Definition: float.h:291
#define DirectFunctionCall5(func, arg1, arg2, arg3, arg4, arg5)
Definition: fmgr.h:632
#define FPeq(A, B)
Definition: geo_decls.h:34
static uint32 ieee_float32_to_uint32(float f)
Definition: gistproc.c:1598
static void adjustBox(BOX *b, const BOX *addon)
Definition: gistproc.c:147
Point low
Definition: geo_decls.h:101
float float4
Definition: c.h:497
#define RTOverLeftStrategyNumber
Definition: stratnum.h:52
void * palloc0(Size size)
Definition: mcxt.c:981
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:358
uintptr_t Datum
Definition: postgres.h:367
Datum circle_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5077
Datum gist_circle_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1135
Datum gist_point_sortsupport(PG_FUNCTION_ARGS)
Definition: gistproc.c:1755
Datum box_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:635
#define PolygonStrategyNumberGroup
Definition: gistproc.c:1338
#define LIMIT_RATIO
Definition: gistproc.c:45
#define PG_GETARG_CIRCLE_P(n)
Definition: geo_decls.h:170
#define BoxPGetDatum(X)
Definition: geo_decls.h:157
static bool float8_gt(const float8 val1, const float8 val2)
Definition: float.h:315
Datum gist_box_penalty(PG_FUNCTION_ARGS)
Definition: gistproc.c:200
BOX boundbox
Definition: geo_decls.h:114
Datum gist_circle_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1105
#define PG_RETURN_VOID()
Definition: fmgr.h:348
static bool gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup)
Definition: gistproc.c:1746
Datum box_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:623
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define FPlt(A, B)
Definition: geo_decls.h:36
Datum spl_ldatum
Definition: gist.h:136
#define Assert(condition)
Definition: c.h:745
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:236
float8 y
Definition: geo_decls.h:57
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182
#define RTRightStrategyNumber
Definition: stratnum.h:55
#define DatumGetPointP(X)
Definition: geo_decls.h:134
static float non_negative(float val)
Definition: gistproc.c:340
static float8 float8_div(const float8 val1, const float8 val2)
Definition: float.h:237
Datum box_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:586
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
Datum gist_box_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1495
OffsetNumber * spl_right
Definition: gist.h:139
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define RTContainsStrategyNumber
Definition: stratnum.h:57
Datum gist_poly_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1067
static float8 gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy)
Definition: gistproc.c:1474
#define DatumGetBoxP(X)
Definition: geo_decls.h:156
Datum gist_point_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1173
Point high
Definition: geo_decls.h:101
static bool float8_eq(const float8 val1, const float8 val2)
Definition: float.h:267
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272
#define DatumGetPolygonP(X)
Definition: geo_decls.h:161
Point center
Definition: geo_decls.h:123
Datum gist_circle_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1521
void * palloc(Size size)
Definition: mcxt.c:950
static int gist_bbox_zorder_cmp_abbrev(Datum z1, Datum z2, SortSupport ssup)
Definition: gistproc.c:1724
Datum gist_box_union(PG_FUNCTION_ARGS)
Definition: gistproc.c:165
#define FPge(A, B)
Definition: geo_decls.h:39
#define elog(elevel,...)
Definition: elog.h:214
int i
#define RTOverlapStrategyNumber
Definition: stratnum.h:53
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
static float8 box_penalty(const BOX *original, const BOX *new)
Definition: gistproc.c:98
Datum box_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:658
#define FPle(A, B)
Definition: geo_decls.h:37
#define qsort(a, b, c, d)
Definition: port.h:475
static float8 float8_max(const float8 val1, const float8 val2)
Definition: float.h:351
OffsetNumber offset
Definition: gist.h:155
Datum gist_poly_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1538
long val
Definition: informix.c:664
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:626
#define PointPGetDatum(X)
Definition: geo_decls.h:135
float8 upper
Definition: gistproc.c:308