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