PostgreSQL Source Code  git master
gistproc.c File Reference
#include "postgres.h"
#include <math.h>
#include "access/gist.h"
#include "access/stratnum.h"
#include "utils/builtins.h"
#include "utils/float.h"
#include "utils/geo_decls.h"
#include "utils/sortsupport.h"
Include dependency graph for gistproc.c:

Go to the source code of this file.

Data Structures

struct  CommonEntry
 
struct  ConsiderSplitContext
 
struct  SplitInterval
 

Macros

#define LIMIT_RATIO   0.3
 
#define PLACE_LEFT(box, off)
 
#define PLACE_RIGHT(box, off)
 
#define point_point_distance(p1, p2)
 
#define GeoStrategyNumberOffset   20
 
#define PointStrategyNumberGroup   0
 
#define BoxStrategyNumberGroup   1
 
#define PolygonStrategyNumberGroup   2
 
#define CircleStrategyNumberGroup   3
 

Functions

static bool gist_box_leaf_consistent (BOX *key, BOX *query, StrategyNumber strategy)
 
static bool rtree_internal_consistent (BOX *key, BOX *query, StrategyNumber strategy)
 
static uint64 point_zorder_internal (float4 x, float4 y)
 
static uint64 part_bits32_by2 (uint32 x)
 
static uint32 ieee_float32_to_uint32 (float f)
 
static int gist_bbox_zorder_cmp (Datum a, Datum b, SortSupport ssup)
 
static Datum gist_bbox_zorder_abbrev_convert (Datum original, SortSupport ssup)
 
static int gist_bbox_zorder_cmp_abbrev (Datum z1, Datum z2, SortSupport ssup)
 
static bool gist_bbox_zorder_abbrev_abort (int memtupcount, SortSupport ssup)
 
static void rt_box_union (BOX *n, const BOX *a, const BOX *b)
 
static float8 size_box (const BOX *box)
 
static float8 box_penalty (const BOX *original, const BOX *new)
 
Datum gist_box_consistent (PG_FUNCTION_ARGS)
 
static void adjustBox (BOX *b, const BOX *addon)
 
Datum gist_box_union (PG_FUNCTION_ARGS)
 
Datum gist_box_penalty (PG_FUNCTION_ARGS)
 
static void fallbackSplit (GistEntryVector *entryvec, GIST_SPLITVEC *v)
 
static int interval_cmp_lower (const void *i1, const void *i2)
 
static int interval_cmp_upper (const void *i1, const void *i2)
 
static float non_negative (float val)
 
static void g_box_consider_split (ConsiderSplitContext *context, int dimNum, float8 rightLower, int minLeftCount, float8 leftUpper, int maxLeftCount)
 
static int common_entry_cmp (const void *i1, const void *i2)
 
Datum gist_box_picksplit (PG_FUNCTION_ARGS)
 
Datum gist_box_same (PG_FUNCTION_ARGS)
 
Datum gist_poly_compress (PG_FUNCTION_ARGS)
 
Datum gist_poly_consistent (PG_FUNCTION_ARGS)
 
Datum gist_circle_compress (PG_FUNCTION_ARGS)
 
Datum gist_circle_consistent (PG_FUNCTION_ARGS)
 
Datum gist_point_compress (PG_FUNCTION_ARGS)
 
Datum gist_point_fetch (PG_FUNCTION_ARGS)
 
static float8 computeDistance (bool isLeaf, BOX *box, Point *point)
 
static bool gist_point_consistent_internal (StrategyNumber strategy, bool isLeaf, BOX *key, Point *query)
 
Datum gist_point_consistent (PG_FUNCTION_ARGS)
 
Datum gist_point_distance (PG_FUNCTION_ARGS)
 
static float8 gist_bbox_distance (GISTENTRY *entry, Datum query, StrategyNumber strategy)
 
Datum gist_box_distance (PG_FUNCTION_ARGS)
 
Datum gist_circle_distance (PG_FUNCTION_ARGS)
 
Datum gist_poly_distance (PG_FUNCTION_ARGS)
 
Datum gist_point_sortsupport (PG_FUNCTION_ARGS)
 

Macro Definition Documentation

◆ BoxStrategyNumberGroup

#define BoxStrategyNumberGroup   1

Definition at line 1333 of file gistproc.c.

Referenced by gist_point_consistent().

◆ CircleStrategyNumberGroup

#define CircleStrategyNumberGroup   3

Definition at line 1335 of file gistproc.c.

Referenced by gist_point_consistent().

◆ GeoStrategyNumberOffset

#define GeoStrategyNumberOffset   20

Definition at line 1331 of file gistproc.c.

Referenced by gist_bbox_distance(), gist_point_consistent(), and gist_point_distance().

◆ LIMIT_RATIO

#define LIMIT_RATIO   0.3

Definition at line 45 of file gistproc.c.

Referenced by g_box_consider_split(), and gist_box_picksplit().

◆ PLACE_LEFT

#define PLACE_LEFT (   box,
  off 
)
Value:
do { \
if (v->spl_nleft > 0) \
adjustBox(leftBox, box); \
else \
*leftBox = *(box); \
v->spl_left[v->spl_nleft++] = off; \
} while(0)

Referenced by gist_box_picksplit().

◆ PLACE_RIGHT

#define PLACE_RIGHT (   box,
  off 
)
Value:
do { \
if (v->spl_nright > 0) \
adjustBox(rightBox, box); \
else \
*rightBox = *(box); \
v->spl_right[v->spl_nright++] = off; \
} while(0)

Referenced by gist_box_picksplit().

◆ point_point_distance

#define point_point_distance (   p1,
  p2 
)
Value:
Datum point_distance(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1962
#define DatumGetFloat8(X)
Definition: postgres.h:714
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:628
#define PointPGetDatum(X)
Definition: geo_decls.h:176

Definition at line 1217 of file gistproc.c.

Referenced by computeDistance().

◆ PointStrategyNumberGroup

#define PointStrategyNumberGroup   0

Definition at line 1332 of file gistproc.c.

Referenced by gist_bbox_distance(), gist_point_consistent(), and gist_point_distance().

◆ PolygonStrategyNumberGroup

#define PolygonStrategyNumberGroup   2

Definition at line 1334 of file gistproc.c.

Referenced by gist_point_consistent().

Function Documentation

◆ adjustBox()

static void adjustBox ( BOX b,
const BOX addon 
)
static

Definition at line 147 of file gistproc.c.

References float8_gt(), float8_lt(), BOX::high, BOX::low, Point::x, and Point::y.

Referenced by fallbackSplit(), gist_box_picksplit(), and gist_box_union().

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 }
float8 x
Definition: geo_decls.h:98
static bool float8_lt(const float8 val1, const float8 val2)
Definition: float.h:291
Point low
Definition: geo_decls.h:142
static bool float8_gt(const float8 val1, const float8 val2)
Definition: float.h:315
float8 y
Definition: geo_decls.h:98
Point high
Definition: geo_decls.h:142

◆ box_penalty()

static float8 box_penalty ( const BOX original,
const BOX new 
)
static

Definition at line 98 of file gistproc.c.

References float8_mi(), rt_box_union(), and size_box().

Referenced by gist_box_penalty(), and gist_box_picksplit().

99 {
100  BOX unionbox;
101 
102  rt_box_union(&unionbox, original, new);
103  return float8_mi(size_box(&unionbox), size_box(original));
104 }
static float8 size_box(const BOX *box)
Definition: gistproc.c:69
Definition: geo_decls.h:140
static void rt_box_union(BOX *n, const BOX *a, const BOX *b)
Definition: gistproc.c:56
static float8 float8_mi(const float8 val1, const float8 val2)
Definition: float.h:181

◆ common_entry_cmp()

static int common_entry_cmp ( const void *  i1,
const void *  i2 
)
static

Definition at line 461 of file gistproc.c.

References float8_cmp_internal().

Referenced by gist_box_picksplit().

462 {
463  float8 delta1 = ((const CommonEntry *) i1)->delta,
464  delta2 = ((const CommonEntry *) i2)->delta;
465 
466  return float8_cmp_internal(delta1, delta2);
467 }
int float8_cmp_internal(float8 a, float8 b)
Definition: float.c:914
double float8
Definition: c.h:553

◆ computeDistance()

static float8 computeDistance ( bool  isLeaf,
BOX box,
Point point 
)
static

Definition at line 1222 of file gistproc.c.

References Assert, elog, ERROR, float8_mi(), BOX::high, BOX::low, point_point_distance, Point::x, and Point::y.

Referenced by gist_bbox_distance(), and gist_point_distance().

1223 {
1224  float8 result = 0.0;
1225 
1226  if (isLeaf)
1227  {
1228  /* simple point to point distance */
1229  result = point_point_distance(point, &box->low);
1230  }
1231  else if (point->x <= box->high.x && point->x >= box->low.x &&
1232  point->y <= box->high.y && point->y >= box->low.y)
1233  {
1234  /* point inside the box */
1235  result = 0.0;
1236  }
1237  else if (point->x <= box->high.x && point->x >= box->low.x)
1238  {
1239  /* point is over or below box */
1240  Assert(box->low.y <= box->high.y);
1241  if (point->y > box->high.y)
1242  result = float8_mi(point->y, box->high.y);
1243  else if (point->y < box->low.y)
1244  result = float8_mi(box->low.y, point->y);
1245  else
1246  elog(ERROR, "inconsistent point values");
1247  }
1248  else if (point->y <= box->high.y && point->y >= box->low.y)
1249  {
1250  /* point is to left or right of box */
1251  Assert(box->low.x <= box->high.x);
1252  if (point->x > box->high.x)
1253  result = float8_mi(point->x, box->high.x);
1254  else if (point->x < box->low.x)
1255  result = float8_mi(box->low.x, point->x);
1256  else
1257  elog(ERROR, "inconsistent point values");
1258  }
1259  else
1260  {
1261  /* closest point will be a vertex */
1262  Point p;
1263  float8 subresult;
1264 
1265  result = point_point_distance(point, &box->low);
1266 
1267  subresult = point_point_distance(point, &box->high);
1268  if (result > subresult)
1269  result = subresult;
1270 
1271  p.x = box->low.x;
1272  p.y = box->high.y;
1273  subresult = point_point_distance(point, &p);
1274  if (result > subresult)
1275  result = subresult;
1276 
1277  p.x = box->high.x;
1278  p.y = box->low.y;
1279  subresult = point_point_distance(point, &p);
1280  if (result > subresult)
1281  result = subresult;
1282  }
1283 
1284  return result;
1285 }
float8 x
Definition: geo_decls.h:98
#define point_point_distance(p1, p2)
Definition: gistproc.c:1217
#define ERROR
Definition: elog.h:43
double float8
Definition: c.h:553
static float8 float8_mi(const float8 val1, const float8 val2)
Definition: float.h:181
Point low
Definition: geo_decls.h:142
#define Assert(condition)
Definition: c.h:800
float8 y
Definition: geo_decls.h:98
Point high
Definition: geo_decls.h:142
#define elog(elevel,...)
Definition: elog.h:228

◆ fallbackSplit()

static void fallbackSplit ( GistEntryVector entryvec,
GIST_SPLITVEC v 
)
static

Definition at line 217 of file gistproc.c.

References adjustBox(), BoxPGetDatum, cur, DatumGetBoxP, FirstOffsetNumber, i, GISTENTRY::key, GistEntryVector::n, OffsetNumberNext, palloc(), GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, GIST_SPLITVEC::spl_right, and GistEntryVector::vector.

Referenced by gist_box_picksplit().

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 }
Definition: geo_decls.h:140
OffsetNumber * spl_left
Definition: gist.h:134
Datum spl_rdatum
Definition: gist.h:141
int32 n
Definition: gist.h:227
struct cursor * cur
Definition: ecpg.c:28
int spl_nleft
Definition: gist.h:135
uint16 OffsetNumber
Definition: off.h:24
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:228
int spl_nright
Definition: gist.h:140
Datum key
Definition: gist.h:152
#define FirstOffsetNumber
Definition: off.h:27
static void adjustBox(BOX *b, const BOX *addon)
Definition: gistproc.c:147
#define BoxPGetDatum(X)
Definition: geo_decls.h:198
Datum spl_ldatum
Definition: gist.h:136
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
OffsetNumber * spl_right
Definition: gist.h:139
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
void * palloc(Size size)
Definition: mcxt.c:950
int i

◆ g_box_consider_split()

static void g_box_consider_split ( ConsiderSplitContext context,
int  dimNum,
float8  rightLower,
int  minLeftCount,
float8  leftUpper,
int  maxLeftCount 
)
inlinestatic

Definition at line 352 of file gistproc.c.

References ConsiderSplitContext::boundingBox, ConsiderSplitContext::dim, ConsiderSplitContext::entriesCount, ConsiderSplitContext::first, float4_div(), float8_div(), float8_mi(), BOX::high, ConsiderSplitContext::leftUpper, LIMIT_RATIO, BOX::low, Min, non_negative(), ConsiderSplitContext::overlap, ConsiderSplitContext::range, range(), ConsiderSplitContext::ratio, ConsiderSplitContext::rightLower, Point::x, and Point::y.

Referenced by gist_box_picksplit().

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 }
static float4 float4_div(const float4 val1, const float4 val2)
Definition: float.h:221
float8 x
Definition: geo_decls.h:98
#define Min(x, y)
Definition: c.h:982
double float8
Definition: c.h:553
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
Point low
Definition: geo_decls.h:142
float float4
Definition: c.h:552
#define LIMIT_RATIO
Definition: gistproc.c:45
float8 y
Definition: geo_decls.h:98
static float non_negative(float val)
Definition: gistproc.c:340
static float8 float8_div(const float8 val1, const float8 val2)
Definition: float.h:237
Point high
Definition: geo_decls.h:142

◆ gist_bbox_distance()

static float8 gist_bbox_distance ( GISTENTRY entry,
Datum  query,
StrategyNumber  strategy 
)
static

Definition at line 1480 of file gistproc.c.

References computeDistance(), DatumGetBoxP, DatumGetPointP, elog, ERROR, GeoStrategyNumberOffset, GISTENTRY::key, and PointStrategyNumberGroup.

Referenced by gist_box_distance(), gist_circle_distance(), and gist_poly_distance().

1481 {
1482  float8 distance;
1483  StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1484 
1485  switch (strategyGroup)
1486  {
1488  distance = computeDistance(false,
1489  DatumGetBoxP(entry->key),
1490  DatumGetPointP(query));
1491  break;
1492  default:
1493  elog(ERROR, "unrecognized strategy number: %d", strategy);
1494  distance = 0.0; /* keep compiler quiet */
1495  }
1496 
1497  return distance;
1498 }
#define GeoStrategyNumberOffset
Definition: gistproc.c:1331
uint16 StrategyNumber
Definition: stratnum.h:22
#define PointStrategyNumberGroup
Definition: gistproc.c:1332
#define ERROR
Definition: elog.h:43
double float8
Definition: c.h:553
Datum key
Definition: gist.h:152
static float8 computeDistance(bool isLeaf, BOX *box, Point *point)
Definition: gistproc.c:1222
#define DatumGetPointP(X)
Definition: geo_decls.h:175
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
#define elog(elevel,...)
Definition: elog.h:228

◆ gist_bbox_zorder_abbrev_abort()

static bool gist_bbox_zorder_abbrev_abort ( int  memtupcount,
SortSupport  ssup 
)
static

Definition at line 1752 of file gistproc.c.

Referenced by gist_point_sortsupport().

1753 {
1754  return false;
1755 }

◆ gist_bbox_zorder_abbrev_convert()

static Datum gist_bbox_zorder_abbrev_convert ( Datum  original,
SortSupport  ssup 
)
static

Definition at line 1715 of file gistproc.c.

References DatumGetBoxP, point_zorder_internal(), Point::x, and Point::y.

Referenced by gist_point_sortsupport().

1716 {
1717  Point *p = &(DatumGetBoxP(original)->low);
1718  uint64 z;
1719 
1720  z = point_zorder_internal(p->x, p->y);
1721 
1722 #if SIZEOF_DATUM == 8
1723  return (Datum) z;
1724 #else
1725  return (Datum) (z >> 32);
1726 #endif
1727 }
float8 x
Definition: geo_decls.h:98
static uint64 point_zorder_internal(float4 x, float4 y)
Definition: gistproc.c:1576
uintptr_t Datum
Definition: postgres.h:367
float8 y
Definition: geo_decls.h:98
#define DatumGetBoxP(X)
Definition: geo_decls.h:197

◆ gist_bbox_zorder_cmp()

static int gist_bbox_zorder_cmp ( Datum  a,
Datum  b,
SortSupport  ssup 
)
static

Definition at line 1682 of file gistproc.c.

References DatumGetBoxP, point_zorder_internal(), Point::x, and Point::y.

Referenced by gist_point_sortsupport().

1683 {
1684  Point *p1 = &(DatumGetBoxP(a)->low);
1685  Point *p2 = &(DatumGetBoxP(b)->low);
1686  uint64 z1;
1687  uint64 z2;
1688 
1689  /*
1690  * Do a quick check for equality first. It's not clear if this is worth it
1691  * in general, but certainly is when used as tie-breaker with abbreviated
1692  * keys,
1693  */
1694  if (p1->x == p2->x && p1->y == p2->y)
1695  return 0;
1696 
1697  z1 = point_zorder_internal(p1->x, p1->y);
1698  z2 = point_zorder_internal(p2->x, p2->y);
1699  if (z1 > z2)
1700  return 1;
1701  else if (z1 < z2)
1702  return -1;
1703  else
1704  return 0;
1705 }
float8 x
Definition: geo_decls.h:98
static uint64 point_zorder_internal(float4 x, float4 y)
Definition: gistproc.c:1576
float8 y
Definition: geo_decls.h:98
#define DatumGetBoxP(X)
Definition: geo_decls.h:197

◆ gist_bbox_zorder_cmp_abbrev()

static int gist_bbox_zorder_cmp_abbrev ( Datum  z1,
Datum  z2,
SortSupport  ssup 
)
static

Definition at line 1730 of file gistproc.c.

Referenced by gist_point_sortsupport().

1731 {
1732  /*
1733  * Compare the pre-computed Z-orders as unsigned integers. Datum is a
1734  * typedef for 'uintptr_t', so no casting is required.
1735  */
1736  if (z1 > z2)
1737  return 1;
1738  else if (z1 < z2)
1739  return -1;
1740  else
1741  return 0;
1742 }

◆ gist_box_consistent()

Datum gist_box_consistent ( PG_FUNCTION_ARGS  )

Definition at line 114 of file gistproc.c.

References DatumGetBoxP, gist_box_leaf_consistent(), GIST_LEAF, GISTENTRY::key, PG_GETARG_BOX_P, PG_GETARG_POINTER, PG_GETARG_UINT16, PG_RETURN_BOOL, and rtree_internal_consistent().

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 }
#define GIST_LEAF(entry)
Definition: gist.h:162
static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:958
Definition: geo_decls.h:140
static bool gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:873
#define PG_GETARG_BOX_P(n)
Definition: geo_decls.h:199
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Datum key
Definition: gist.h:152
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272

◆ gist_box_distance()

Datum gist_box_distance ( PG_FUNCTION_ARGS  )

Definition at line 1501 of file gistproc.c.

References gist_bbox_distance(), PG_GETARG_DATUM, PG_GETARG_POINTER, PG_GETARG_UINT16, and PG_RETURN_FLOAT8.

1502 {
1503  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1504  Datum query = PG_GETARG_DATUM(1);
1506 
1507  /* Oid subtype = PG_GETARG_OID(3); */
1508  /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */
1509  float8 distance;
1510 
1511  distance = gist_bbox_distance(entry, query, strategy);
1512 
1513  PG_RETURN_FLOAT8(distance);
1514 }
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
double float8
Definition: c.h:553
uintptr_t Datum
Definition: postgres.h:367
static float8 gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy)
Definition: gistproc.c:1480
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272

◆ gist_box_leaf_consistent()

static bool gist_box_leaf_consistent ( BOX key,
BOX query,
StrategyNumber  strategy 
)
static

Definition at line 873 of file gistproc.c.

References box_above(), box_below(), box_contain(), box_contained(), box_left(), box_overabove(), box_overbelow(), box_overlap(), box_overleft(), box_overright(), box_right(), box_same(), DatumGetBool, DirectFunctionCall2, elog, ERROR, PointerGetDatum, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTContainsStrategyNumber, RTLeftStrategyNumber, RTOverAboveStrategyNumber, RTOverBelowStrategyNumber, RTOverlapStrategyNumber, RTOverLeftStrategyNumber, RTOverRightStrategyNumber, RTRightStrategyNumber, and RTSameStrategyNumber.

Referenced by gist_box_consistent().

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;
911  PointerGetDatum(key),
912  PointerGetDatum(query)));
913  break;
916  PointerGetDatum(key),
917  PointerGetDatum(query)));
918  break;
921  PointerGetDatum(key),
922  PointerGetDatum(query)));
923  break;
926  PointerGetDatum(key),
927  PointerGetDatum(query)));
928  break;
931  PointerGetDatum(key),
932  PointerGetDatum(query)));
933  break;
936  PointerGetDatum(key),
937  PointerGetDatum(query)));
938  break;
939  default:
940  elog(ERROR, "unrecognized strategy number: %d", strategy);
941  retval = false; /* keep compiler quiet */
942  break;
943  }
944  return retval;
945 }
Datum box_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:597
Datum box_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:669
Datum box_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:539
Datum box_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:571
#define RTLeftStrategyNumber
Definition: stratnum.h:51
Datum box_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:612
#define PointerGetDatum(X)
Definition: postgres.h:556
Datum box_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:551
#define RTOverBelowStrategyNumber
Definition: stratnum.h:59
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define RTOverAboveStrategyNumber
Definition: stratnum.h:62
#define ERROR
Definition: elog.h:43
Datum box_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:680
Datum box_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:646
#define DatumGetBool(X)
Definition: postgres.h:393
#define RTSameStrategyNumber
Definition: stratnum.h:56
#define RTOverRightStrategyNumber
Definition: stratnum.h:54
#define RTOverLeftStrategyNumber
Definition: stratnum.h:52
Datum box_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:635
Datum box_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:623
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define RTRightStrategyNumber
Definition: stratnum.h:55
Datum box_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:586
#define RTContainsStrategyNumber
Definition: stratnum.h:57
#define elog(elevel,...)
Definition: elog.h:228
#define RTOverlapStrategyNumber
Definition: stratnum.h:53
Datum box_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:658
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:628

◆ gist_box_penalty()

Datum gist_box_penalty ( PG_FUNCTION_ARGS  )

Definition at line 200 of file gistproc.c.

References box_penalty(), DatumGetBoxP, GISTENTRY::key, PG_GETARG_POINTER, and PG_RETURN_POINTER.

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 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
Definition: geo_decls.h:140
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Datum key
Definition: gist.h:152
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
static float8 box_penalty(const BOX *original, const BOX *new)
Definition: gistproc.c:98

◆ gist_box_picksplit()

Datum gist_box_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 496 of file gistproc.c.

References Abs, adjustBox(), Assert, ConsiderSplitContext::boundingBox, box_penalty(), common_entry_cmp(), DatumGetBoxP, CommonEntry::delta, ConsiderSplitContext::dim, ConsiderSplitContext::entriesCount, fallbackSplit(), ConsiderSplitContext::first, FirstOffsetNumber, float8_eq(), float8_ge(), float8_gt(), float8_le(), float8_lt(), float8_mi(), g_box_consider_split(), BOX::high, i, CommonEntry::index, interval_cmp_lower(), interval_cmp_upper(), GISTENTRY::key, ConsiderSplitContext::leftUpper, LIMIT_RATIO, BOX::low, lower(), SplitInterval::lower, GistEntryVector::n, OffsetNumberNext, palloc(), palloc0(), PG_GETARG_POINTER, PG_RETURN_POINTER, PLACE_LEFT, PLACE_RIGHT, PointerGetDatum, qsort, ConsiderSplitContext::rightLower, GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, GIST_SPLITVEC::spl_right, upper(), SplitInterval::upper, GistEntryVector::vector, Point::x, and Point::y.

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 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
float8 lower
Definition: gistproc.c:308
Definition: geo_decls.h:140
#define PLACE_LEFT(box, off)
float8 x
Definition: geo_decls.h:98
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:44
static int interval_cmp_lower(const void *i1, const void *i2)
Definition: gistproc.c:316
#define PointerGetDatum(X)
Definition: postgres.h:556
float8 delta
Definition: gistproc.c:277
static int interval_cmp_upper(const void *i1, const void *i2)
Definition: gistproc.c:328
OffsetNumber * spl_left
Definition: gist.h:134
Datum spl_rdatum
Definition: gist.h:141
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
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:75
int spl_nleft
Definition: gist.h:135
#define PLACE_RIGHT(box, off)
uint16 OffsetNumber
Definition: off.h:24
#define Abs(x)
Definition: c.h:988
Definition: type.h:89
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:228
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, float8 rightLower, int minLeftCount, float8 leftUpper, int maxLeftCount)
Definition: gistproc.c:352
double float8
Definition: c.h:553
int spl_nright
Definition: gist.h:140
Datum key
Definition: gist.h:152
#define FirstOffsetNumber
Definition: off.h:27
static bool float8_ge(const float8 val1, const float8 val2)
Definition: float.h:327
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 bool float8_lt(const float8 val1, const float8 val2)
Definition: float.h:291
static void adjustBox(BOX *b, const BOX *addon)
Definition: gistproc.c:147
Point low
Definition: geo_decls.h:142
void * palloc0(Size size)
Definition: mcxt.c:981
#define LIMIT_RATIO
Definition: gistproc.c:45
static bool float8_gt(const float8 val1, const float8 val2)
Definition: float.h:315
Datum spl_ldatum
Definition: gist.h:136
#define Assert(condition)
Definition: c.h:800
float8 y
Definition: geo_decls.h:98
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
OffsetNumber * spl_right
Definition: gist.h:139
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
Point high
Definition: geo_decls.h:142
static bool float8_eq(const float8 val1, const float8 val2)
Definition: float.h:267
void * palloc(Size size)
Definition: mcxt.c:950
int i
static float8 box_penalty(const BOX *original, const BOX *new)
Definition: gistproc.c:98
#define qsort(a, b, c, d)
Definition: port.h:497
float8 upper
Definition: gistproc.c:308

◆ gist_box_same()

Datum gist_box_same ( PG_FUNCTION_ARGS  )

Definition at line 853 of file gistproc.c.

References float8_eq(), BOX::high, BOX::low, PG_GETARG_BOX_P, PG_GETARG_POINTER, PG_RETURN_POINTER, Point::x, and Point::y.

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 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
Definition: geo_decls.h:140
#define PG_GETARG_BOX_P(n)
Definition: geo_decls.h:199
float8 x
Definition: geo_decls.h:98
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Point low
Definition: geo_decls.h:142
float8 y
Definition: geo_decls.h:98
Point high
Definition: geo_decls.h:142
static bool float8_eq(const float8 val1, const float8 val2)
Definition: float.h:267

◆ gist_box_union()

Datum gist_box_union ( PG_FUNCTION_ARGS  )

Definition at line 165 of file gistproc.c.

References adjustBox(), cur, DatumGetBoxP, i, GISTENTRY::key, GistEntryVector::n, palloc(), PG_GETARG_POINTER, PG_RETURN_POINTER, and GistEntryVector::vector.

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 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
Definition: geo_decls.h:140
int32 n
Definition: gist.h:227
struct cursor * cur
Definition: ecpg.c:28
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:228
Datum key
Definition: gist.h:152
static void adjustBox(BOX *b, const BOX *addon)
Definition: gistproc.c:147
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
void * palloc(Size size)
Definition: mcxt.c:950
int i

◆ gist_circle_compress()

Datum gist_circle_compress ( PG_FUNCTION_ARGS  )

Definition at line 1101 of file gistproc.c.

References CIRCLE::center, DatumGetCircleP, float8_mi(), float8_pl(), gistentryinit, BOX::high, GISTENTRY::key, GISTENTRY::leafkey, BOX::low, GISTENTRY::offset, GISTENTRY::page, palloc(), PG_GETARG_POINTER, PG_RETURN_POINTER, PointerGetDatum, CIRCLE::radius, GISTENTRY::rel, Point::x, and Point::y.

1102 {
1103  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1104  GISTENTRY *retval;
1105 
1106  if (entry->leafkey)
1107  {
1108  CIRCLE *in = DatumGetCircleP(entry->key);
1109  BOX *r;
1110 
1111  r = (BOX *) palloc(sizeof(BOX));
1112  r->high.x = float8_pl(in->center.x, in->radius);
1113  r->low.x = float8_mi(in->center.x, in->radius);
1114  r->high.y = float8_pl(in->center.y, in->radius);
1115  r->low.y = float8_mi(in->center.y, in->radius);
1116 
1117  retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1118  gistentryinit(*retval, PointerGetDatum(r),
1119  entry->rel, entry->page,
1120  entry->offset, false);
1121  }
1122  else
1123  retval = entry;
1124  PG_RETURN_POINTER(retval);
1125 }
Relation rel
Definition: gist.h:153
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
Definition: geo_decls.h:140
float8 x
Definition: geo_decls.h:98
float8 radius
Definition: geo_decls.h:165
#define PointerGetDatum(X)
Definition: postgres.h:556
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Page page
Definition: gist.h:154
Datum key
Definition: gist.h:152
#define DatumGetCircleP(X)
Definition: geo_decls.h:209
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
bool leafkey
Definition: gist.h:156
Point low
Definition: geo_decls.h:142
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:236
float8 y
Definition: geo_decls.h:98
Point high
Definition: geo_decls.h:142
Point center
Definition: geo_decls.h:164
void * palloc(Size size)
Definition: mcxt.c:950
OffsetNumber offset
Definition: gist.h:155

◆ gist_circle_consistent()

Datum gist_circle_consistent ( PG_FUNCTION_ARGS  )

Definition at line 1131 of file gistproc.c.

References CIRCLE::center, DatumGetBoxP, float8_mi(), float8_pl(), BOX::high, GISTENTRY::key, BOX::low, PG_GETARG_CIRCLE_P, PG_GETARG_POINTER, PG_GETARG_UINT16, PG_RETURN_BOOL, CIRCLE::radius, rtree_internal_consistent(), Point::x, and Point::y.

Referenced by gist_point_consistent().

1132 {
1133  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1134  CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1136 
1137  /* Oid subtype = PG_GETARG_OID(3); */
1138  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1139  BOX bbox;
1140  bool result;
1141 
1142  /* All cases served by this function are inexact */
1143  *recheck = true;
1144 
1145  if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1146  PG_RETURN_BOOL(false);
1147 
1148  /*
1149  * Since the operators require recheck anyway, we can just use
1150  * rtree_internal_consistent even at leaf nodes. (This works in part
1151  * because the index entries are bounding boxes not circles.)
1152  */
1153  bbox.high.x = float8_pl(query->center.x, query->radius);
1154  bbox.low.x = float8_mi(query->center.x, query->radius);
1155  bbox.high.y = float8_pl(query->center.y, query->radius);
1156  bbox.low.y = float8_mi(query->center.y, query->radius);
1157 
1158  result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1159  &bbox, strategy);
1160 
1161  PG_RETURN_BOOL(result);
1162 }
static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:958
Definition: geo_decls.h:140
float8 x
Definition: geo_decls.h:98
float8 radius
Definition: geo_decls.h:165
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Datum key
Definition: gist.h:152
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
Point low
Definition: geo_decls.h:142
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
#define PG_GETARG_CIRCLE_P(n)
Definition: geo_decls.h:211
float8 y
Definition: geo_decls.h:98
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
Point high
Definition: geo_decls.h:142
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272
Point center
Definition: geo_decls.h:164

◆ gist_circle_distance()

Datum gist_circle_distance ( PG_FUNCTION_ARGS  )

Definition at line 1527 of file gistproc.c.

References gist_bbox_distance(), PG_GETARG_DATUM, PG_GETARG_POINTER, PG_GETARG_UINT16, and PG_RETURN_FLOAT8.

1528 {
1529  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1530  Datum query = PG_GETARG_DATUM(1);
1532 
1533  /* Oid subtype = PG_GETARG_OID(3); */
1534  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1535  float8 distance;
1536 
1537  distance = gist_bbox_distance(entry, query, strategy);
1538  *recheck = true;
1539 
1540  PG_RETURN_FLOAT8(distance);
1541 }
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
double float8
Definition: c.h:553
uintptr_t Datum
Definition: postgres.h:367
static float8 gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy)
Definition: gistproc.c:1480
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272

◆ gist_point_compress()

Datum gist_point_compress ( PG_FUNCTION_ARGS  )

Definition at line 1169 of file gistproc.c.

References BoxPGetDatum, DatumGetPointP, gistentryinit, BOX::high, GISTENTRY::key, GISTENTRY::leafkey, BOX::low, GISTENTRY::offset, GISTENTRY::page, palloc(), PG_GETARG_POINTER, PG_RETURN_POINTER, and GISTENTRY::rel.

1170 {
1171  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1172 
1173  if (entry->leafkey) /* Point, actually */
1174  {
1175  BOX *box = palloc(sizeof(BOX));
1176  Point *point = DatumGetPointP(entry->key);
1177  GISTENTRY *retval = palloc(sizeof(GISTENTRY));
1178 
1179  box->high = box->low = *point;
1180 
1181  gistentryinit(*retval, BoxPGetDatum(box),
1182  entry->rel, entry->page, entry->offset, false);
1183 
1184  PG_RETURN_POINTER(retval);
1185  }
1186 
1187  PG_RETURN_POINTER(entry);
1188 }
Relation rel
Definition: gist.h:153
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
Definition: geo_decls.h:140
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Page page
Definition: gist.h:154
Datum key
Definition: gist.h:152
bool leafkey
Definition: gist.h:156
Point low
Definition: geo_decls.h:142
#define BoxPGetDatum(X)
Definition: geo_decls.h:198
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:236
#define DatumGetPointP(X)
Definition: geo_decls.h:175
Point high
Definition: geo_decls.h:142
void * palloc(Size size)
Definition: mcxt.c:950
OffsetNumber offset
Definition: gist.h:155

◆ gist_point_consistent()

Datum gist_point_consistent ( PG_FUNCTION_ARGS  )

Definition at line 1338 of file gistproc.c.

References Assert, BoxStrategyNumberGroup, circle_contain_pt(), CirclePGetDatum, CircleStrategyNumberGroup, DatumGetBool, DatumGetBoxP, DirectFunctionCall2, DirectFunctionCall5, elog, ERROR, GeoStrategyNumberOffset, gist_circle_consistent(), GIST_LEAF, gist_point_consistent_internal(), gist_poly_consistent(), BOX::high, Int16GetDatum, sort-test::key, GISTENTRY::key, BOX::low, PG_GETARG_BOX_P, PG_GETARG_CIRCLE_P, PG_GETARG_POINT_P, PG_GETARG_POINTER, PG_GETARG_POLYGON_P, PG_GETARG_UINT16, PG_RETURN_BOOL, PointerGetDatum, PointPGetDatum, PointStrategyNumberGroup, poly_contain_pt(), PolygonPGetDatum, PolygonStrategyNumberGroup, RTAboveStrategyNumber, RTBelowStrategyNumber, RTOldAboveStrategyNumber, RTOldBelowStrategyNumber, RTOverlapStrategyNumber, Point::x, and Point::y.

1339 {
1340  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1342  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1343  bool result;
1344  StrategyNumber strategyGroup;
1345 
1346  /*
1347  * We have to remap these strategy numbers to get this klugy
1348  * classification logic to work.
1349  */
1350  if (strategy == RTOldBelowStrategyNumber)
1351  strategy = RTBelowStrategyNumber;
1352  else if (strategy == RTOldAboveStrategyNumber)
1353  strategy = RTAboveStrategyNumber;
1354 
1355  strategyGroup = strategy / GeoStrategyNumberOffset;
1356  switch (strategyGroup)
1357  {
1360  GIST_LEAF(entry),
1361  DatumGetBoxP(entry->key),
1362  PG_GETARG_POINT_P(1));
1363  *recheck = false;
1364  break;
1366  {
1367  /*
1368  * The only operator in this group is point <@ box (on_pb), so
1369  * we needn't examine strategy again.
1370  *
1371  * For historical reasons, on_pb uses exact rather than fuzzy
1372  * comparisons. We could use box_overlap when at an internal
1373  * page, but that would lead to possibly visiting child pages
1374  * uselessly, because box_overlap uses fuzzy comparisons.
1375  * Instead we write a non-fuzzy overlap test. The same code
1376  * will also serve for leaf-page tests, since leaf keys have
1377  * high == low.
1378  */
1379  BOX *query,
1380  *key;
1381 
1382  query = PG_GETARG_BOX_P(1);
1383  key = DatumGetBoxP(entry->key);
1384 
1385  result = (key->high.x >= query->low.x &&
1386  key->low.x <= query->high.x &&
1387  key->high.y >= query->low.y &&
1388  key->low.y <= query->high.y);
1389  *recheck = false;
1390  }
1391  break;
1393  {
1394  POLYGON *query = PG_GETARG_POLYGON_P(1);
1395 
1397  PointerGetDatum(entry),
1398  PolygonPGetDatum(query),
1400  0, PointerGetDatum(recheck)));
1401 
1402  if (GIST_LEAF(entry) && result)
1403  {
1404  /*
1405  * We are on leaf page and quick check shows overlapping
1406  * of polygon's bounding box and point
1407  */
1408  BOX *box = DatumGetBoxP(entry->key);
1409 
1410  Assert(box->high.x == box->low.x
1411  && box->high.y == box->low.y);
1413  PolygonPGetDatum(query),
1414  PointPGetDatum(&box->high)));
1415  *recheck = false;
1416  }
1417  }
1418  break;
1420  {
1421  CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1422 
1424  PointerGetDatum(entry),
1425  CirclePGetDatum(query),
1427  0, PointerGetDatum(recheck)));
1428 
1429  if (GIST_LEAF(entry) && result)
1430  {
1431  /*
1432  * We are on leaf page and quick check shows overlapping
1433  * of polygon's bounding box and point
1434  */
1435  BOX *box = DatumGetBoxP(entry->key);
1436 
1437  Assert(box->high.x == box->low.x
1438  && box->high.y == box->low.y);
1440  CirclePGetDatum(query),
1441  PointPGetDatum(&box->high)));
1442  *recheck = false;
1443  }
1444  }
1445  break;
1446  default:
1447  elog(ERROR, "unrecognized strategy number: %d", strategy);
1448  result = false; /* keep compiler quiet */
1449  break;
1450  }
1451 
1452  PG_RETURN_BOOL(result);
1453 }
#define GIST_LEAF(entry)
Definition: gist.h:162
#define RTOldAboveStrategyNumber
Definition: stratnum.h:80
#define GeoStrategyNumberOffset
Definition: gistproc.c:1331
Definition: geo_decls.h:140
#define BoxStrategyNumberGroup
Definition: gistproc.c:1333
#define PG_GETARG_BOX_P(n)
Definition: geo_decls.h:199
float8 x
Definition: geo_decls.h:98
#define CircleStrategyNumberGroup
Definition: gistproc.c:1335
#define PointerGetDatum(X)
Definition: postgres.h:556
#define PolygonPGetDatum(X)
Definition: geo_decls.h:204
#define Int16GetDatum(X)
Definition: postgres.h:451
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Datum poly_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4053
#define RTOldBelowStrategyNumber
Definition: stratnum.h:79
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define PG_GETARG_POLYGON_P(n)
Definition: geo_decls.h:205
#define PointStrategyNumberGroup
Definition: gistproc.c:1332
#define CirclePGetDatum(X)
Definition: geo_decls.h:210
#define ERROR
Definition: elog.h:43
#define PG_GETARG_POINT_P(n)
Definition: geo_decls.h:177
Datum key
Definition: gist.h:152
#define DatumGetBool(X)
Definition: postgres.h:393
static bool gist_point_consistent_internal(StrategyNumber strategy, bool isLeaf, BOX *key, Point *query)
Definition: gistproc.c:1288
#define DirectFunctionCall5(func, arg1, arg2, arg3, arg4, arg5)
Definition: fmgr.h:634
Point low
Definition: geo_decls.h:142
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
Datum circle_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5089
Datum gist_circle_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1131
#define PolygonStrategyNumberGroup
Definition: gistproc.c:1334
#define PG_GETARG_CIRCLE_P(n)
Definition: geo_decls.h:211
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define Assert(condition)
Definition: c.h:800
float8 y
Definition: geo_decls.h:98
Datum gist_poly_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1063
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
Point high
Definition: geo_decls.h:142
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272
#define elog(elevel,...)
Definition: elog.h:228
#define RTOverlapStrategyNumber
Definition: stratnum.h:53
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:628
#define PointPGetDatum(X)
Definition: geo_decls.h:176

◆ gist_point_consistent_internal()

static bool gist_point_consistent_internal ( StrategyNumber  strategy,
bool  isLeaf,
BOX key,
Point query 
)
static

Definition at line 1288 of file gistproc.c.

References elog, ERROR, FPeq(), FPge(), FPgt(), FPle(), FPlt(), BOX::high, BOX::low, RTAboveStrategyNumber, RTBelowStrategyNumber, RTLeftStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, Point::x, and Point::y.

Referenced by gist_point_consistent().

1290 {
1291  bool result = false;
1292 
1293  switch (strategy)
1294  {
1295  case RTLeftStrategyNumber:
1296  result = FPlt(key->low.x, query->x);
1297  break;
1298  case RTRightStrategyNumber:
1299  result = FPgt(key->high.x, query->x);
1300  break;
1301  case RTAboveStrategyNumber:
1302  result = FPgt(key->high.y, query->y);
1303  break;
1304  case RTBelowStrategyNumber:
1305  result = FPlt(key->low.y, query->y);
1306  break;
1307  case RTSameStrategyNumber:
1308  if (isLeaf)
1309  {
1310  /* key.high must equal key.low, so we can disregard it */
1311  result = (FPeq(key->low.x, query->x) &&
1312  FPeq(key->low.y, query->y));
1313  }
1314  else
1315  {
1316  result = (FPle(query->x, key->high.x) &&
1317  FPge(query->x, key->low.x) &&
1318  FPle(query->y, key->high.y) &&
1319  FPge(query->y, key->low.y));
1320  }
1321  break;
1322  default:
1323  elog(ERROR, "unrecognized strategy number: %d", strategy);
1324  result = false; /* keep compiler quiet */
1325  break;
1326  }
1327 
1328  return result;
1329 }
static bool FPle(double A, double B)
Definition: geo_decls.h:65
float8 x
Definition: geo_decls.h:98
#define RTLeftStrategyNumber
Definition: stratnum.h:51
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define ERROR
Definition: elog.h:43
#define RTSameStrategyNumber
Definition: stratnum.h:56
Point low
Definition: geo_decls.h:142
#define RTAboveStrategyNumber
Definition: stratnum.h:61
float8 y
Definition: geo_decls.h:98
static bool FPgt(double A, double B)
Definition: geo_decls.h:71
#define RTRightStrategyNumber
Definition: stratnum.h:55
Point high
Definition: geo_decls.h:142
#define elog(elevel,...)
Definition: elog.h:228
static bool FPeq(double A, double B)
Definition: geo_decls.h:47
static bool FPge(double A, double B)
Definition: geo_decls.h:77
static bool FPlt(double A, double B)
Definition: geo_decls.h:59

◆ gist_point_distance()

Datum gist_point_distance ( PG_FUNCTION_ARGS  )

Definition at line 1456 of file gistproc.c.

References computeDistance(), DatumGetBoxP, elog, ERROR, GeoStrategyNumberOffset, GIST_LEAF, GISTENTRY::key, PG_GETARG_POINT_P, PG_GETARG_POINTER, PG_GETARG_UINT16, PG_RETURN_FLOAT8, and PointStrategyNumberGroup.

1457 {
1458  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1460  float8 distance;
1461  StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1462 
1463  switch (strategyGroup)
1464  {
1466  distance = computeDistance(GIST_LEAF(entry),
1467  DatumGetBoxP(entry->key),
1468  PG_GETARG_POINT_P(1));
1469  break;
1470  default:
1471  elog(ERROR, "unrecognized strategy number: %d", strategy);
1472  distance = 0.0; /* keep compiler quiet */
1473  break;
1474  }
1475 
1476  PG_RETURN_FLOAT8(distance);
1477 }
#define GIST_LEAF(entry)
Definition: gist.h:162
#define GeoStrategyNumberOffset
Definition: gistproc.c:1331
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PointStrategyNumberGroup
Definition: gistproc.c:1332
#define ERROR
Definition: elog.h:43
double float8
Definition: c.h:553
#define PG_GETARG_POINT_P(n)
Definition: geo_decls.h:177
Datum key
Definition: gist.h:152
static float8 computeDistance(bool isLeaf, BOX *box, Point *point)
Definition: gistproc.c:1222
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272
#define elog(elevel,...)
Definition: elog.h:228

◆ gist_point_fetch()

Datum gist_point_fetch ( PG_FUNCTION_ARGS  )

Definition at line 1197 of file gistproc.c.

References DatumGetBoxP, gistentryinit, BOX::high, GISTENTRY::key, GISTENTRY::offset, GISTENTRY::page, palloc(), PG_GETARG_POINTER, PG_RETURN_POINTER, PointerGetDatum, GISTENTRY::rel, Point::x, and Point::y.

1198 {
1199  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1200  BOX *in = DatumGetBoxP(entry->key);
1201  Point *r;
1202  GISTENTRY *retval;
1203 
1204  retval = palloc(sizeof(GISTENTRY));
1205 
1206  r = (Point *) palloc(sizeof(Point));
1207  r->x = in->high.x;
1208  r->y = in->high.y;
1209  gistentryinit(*retval, PointerGetDatum(r),
1210  entry->rel, entry->page,
1211  entry->offset, false);
1212 
1213  PG_RETURN_POINTER(retval);
1214 }
Relation rel
Definition: gist.h:153
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
Definition: geo_decls.h:140
float8 x
Definition: geo_decls.h:98
#define PointerGetDatum(X)
Definition: postgres.h:556
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Page page
Definition: gist.h:154
Datum key
Definition: gist.h:152
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:236
float8 y
Definition: geo_decls.h:98
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
Point high
Definition: geo_decls.h:142
void * palloc(Size size)
Definition: mcxt.c:950
OffsetNumber offset
Definition: gist.h:155

◆ gist_point_sortsupport()

Datum gist_point_sortsupport ( PG_FUNCTION_ARGS  )

Definition at line 1761 of file gistproc.c.

References SortSupportData::abbrev_abort, SortSupportData::abbrev_converter, SortSupportData::abbrev_full_comparator, SortSupportData::abbreviate, SortSupportData::comparator, gist_bbox_zorder_abbrev_abort(), gist_bbox_zorder_abbrev_convert(), gist_bbox_zorder_cmp(), gist_bbox_zorder_cmp_abbrev(), PG_GETARG_POINTER, and PG_RETURN_VOID.

1762 {
1764 
1765  if (ssup->abbreviate)
1766  {
1771  }
1772  else
1773  {
1775  }
1776  PG_RETURN_VOID();
1777 }
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
static Datum gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup)
Definition: gistproc.c:1715
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
static int gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup)
Definition: gistproc.c:1682
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
#define PG_RETURN_VOID()
Definition: fmgr.h:349
static bool gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup)
Definition: gistproc.c:1752
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182
static int gist_bbox_zorder_cmp_abbrev(Datum z1, Datum z2, SortSupport ssup)
Definition: gistproc.c:1730

◆ gist_poly_compress()

Datum gist_poly_compress ( PG_FUNCTION_ARGS  )

Definition at line 1036 of file gistproc.c.

References POLYGON::boundbox, DatumGetPolygonP, gistentryinit, GISTENTRY::key, GISTENTRY::leafkey, GISTENTRY::offset, GISTENTRY::page, palloc(), PG_GETARG_POINTER, PG_RETURN_POINTER, PointerGetDatum, and GISTENTRY::rel.

1037 {
1038  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1039  GISTENTRY *retval;
1040 
1041  if (entry->leafkey)
1042  {
1043  POLYGON *in = DatumGetPolygonP(entry->key);
1044  BOX *r;
1045 
1046  r = (BOX *) palloc(sizeof(BOX));
1047  memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX));
1048 
1049  retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1050  gistentryinit(*retval, PointerGetDatum(r),
1051  entry->rel, entry->page,
1052  entry->offset, false);
1053  }
1054  else
1055  retval = entry;
1056  PG_RETURN_POINTER(retval);
1057 }
Relation rel
Definition: gist.h:153
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
Definition: geo_decls.h:140
#define PointerGetDatum(X)
Definition: postgres.h:556
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
Page page
Definition: gist.h:154
Datum key
Definition: gist.h:152
bool leafkey
Definition: gist.h:156
BOX boundbox
Definition: geo_decls.h:155
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:236
#define DatumGetPolygonP(X)
Definition: geo_decls.h:202
void * palloc(Size size)
Definition: mcxt.c:950
OffsetNumber offset
Definition: gist.h:155

◆ gist_poly_consistent()

Datum gist_poly_consistent ( PG_FUNCTION_ARGS  )

Definition at line 1063 of file gistproc.c.

References POLYGON::boundbox, DatumGetBoxP, GISTENTRY::key, PG_FREE_IF_COPY, PG_GETARG_POINTER, PG_GETARG_POLYGON_P, PG_GETARG_UINT16, PG_RETURN_BOOL, and rtree_internal_consistent().

Referenced by gist_point_consistent().

1064 {
1065  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1066  POLYGON *query = PG_GETARG_POLYGON_P(1);
1068 
1069  /* Oid subtype = PG_GETARG_OID(3); */
1070  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1071  bool result;
1072 
1073  /* All cases served by this function are inexact */
1074  *recheck = true;
1075 
1076  if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1077  PG_RETURN_BOOL(false);
1078 
1079  /*
1080  * Since the operators require recheck anyway, we can just use
1081  * rtree_internal_consistent even at leaf nodes. (This works in part
1082  * because the index entries are bounding boxes not polygons.)
1083  */
1084  result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1085  &(query->boundbox), strategy);
1086 
1087  /* Avoid memory leak if supplied poly is toasted */
1088  PG_FREE_IF_COPY(query, 1);
1089 
1090  PG_RETURN_BOOL(result);
1091 }
static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:958
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_GETARG_POLYGON_P(n)
Definition: geo_decls.h:205
Datum key
Definition: gist.h:152
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
BOX boundbox
Definition: geo_decls.h:155
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define DatumGetBoxP(X)
Definition: geo_decls.h:197
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272

◆ gist_poly_distance()

Datum gist_poly_distance ( PG_FUNCTION_ARGS  )

Definition at line 1544 of file gistproc.c.

References gist_bbox_distance(), PG_GETARG_DATUM, PG_GETARG_POINTER, PG_GETARG_UINT16, and PG_RETURN_FLOAT8.

1545 {
1546  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1547  Datum query = PG_GETARG_DATUM(1);
1549 
1550  /* Oid subtype = PG_GETARG_OID(3); */
1551  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1552  float8 distance;
1553 
1554  distance = gist_bbox_distance(entry, query, strategy);
1555  *recheck = true;
1556 
1557  PG_RETURN_FLOAT8(distance);
1558 }
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
double float8
Definition: c.h:553
uintptr_t Datum
Definition: postgres.h:367
static float8 gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy)
Definition: gistproc.c:1480
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272

◆ ieee_float32_to_uint32()

static uint32 ieee_float32_to_uint32 ( float  f)
static

Definition at line 1604 of file gistproc.c.

References Assert, and i.

Referenced by point_zorder_internal().

1605 {
1606  /*----
1607  *
1608  * IEEE 754 floating point format
1609  * ------------------------------
1610  *
1611  * IEEE 754 floating point numbers have this format:
1612  *
1613  * exponent (8 bits)
1614  * |
1615  * s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm
1616  * | |
1617  * sign mantissa (23 bits)
1618  *
1619  * Infinity has all bits in the exponent set and the mantissa is all
1620  * zeros. Negative infinity is the same but with the sign bit set.
1621  *
1622  * NaNs are represented with all bits in the exponent set, and the least
1623  * significant bit in the mantissa also set. The rest of the mantissa bits
1624  * can be used to distinguish different kinds of NaNs.
1625  *
1626  * The IEEE format has the nice property that when you take the bit
1627  * representation and interpret it as an integer, the order is preserved,
1628  * except for the sign. That holds for the +-Infinity values too.
1629  *
1630  * Mapping to uint32
1631  * -----------------
1632  *
1633  * In order to have a smooth transition from negative to positive numbers,
1634  * we map floats to unsigned integers like this:
1635  *
1636  * x < 0 to range 0-7FFFFFFF
1637  * x = 0 to value 8000000 (both positive and negative zero)
1638  * x > 0 to range 8000001-FFFFFFFF
1639  *
1640  * We don't care to distinguish different kind of NaNs, so they are all
1641  * mapped to the same arbitrary value, FFFFFFFF. Because of the IEEE bit
1642  * representation of NaNs, there aren't any non-NaN values that would be
1643  * mapped to FFFFFFFF. In fact, there is a range of unused values on both
1644  * ends of the uint32 space.
1645  */
1646  if (isnan(f))
1647  return 0xFFFFFFFF;
1648  else
1649  {
1650  union
1651  {
1652  float f;
1653  uint32 i;
1654  } u;
1655 
1656  u.f = f;
1657 
1658  /* Check the sign bit */
1659  if ((u.i & 0x80000000) != 0)
1660  {
1661  /*
1662  * Map the negative value to range 0-7FFFFFFF. This flips the sign
1663  * bit to 0 in the same instruction.
1664  */
1665  Assert(f <= 0); /* can be -0 */
1666  u.i ^= 0xFFFFFFFF;
1667  }
1668  else
1669  {
1670  /* Map the positive value (or 0) to range 80000000-FFFFFFFF */
1671  u.i |= 0x80000000;
1672  }
1673 
1674  return u.i;
1675  }
1676 }
unsigned int uint32
Definition: c.h:429
#define Assert(condition)
Definition: c.h:800
int i

◆ interval_cmp_lower()

static int interval_cmp_lower ( const void *  i1,
const void *  i2 
)
static

Definition at line 316 of file gistproc.c.

References float8_cmp_internal().

Referenced by gist_box_picksplit().

317 {
318  float8 lower1 = ((const SplitInterval *) i1)->lower,
319  lower2 = ((const SplitInterval *) i2)->lower;
320 
321  return float8_cmp_internal(lower1, lower2);
322 }
int float8_cmp_internal(float8 a, float8 b)
Definition: float.c:914
double float8
Definition: c.h:553

◆ interval_cmp_upper()

static int interval_cmp_upper ( const void *  i1,
const void *  i2 
)
static

Definition at line 328 of file gistproc.c.

References float8_cmp_internal().

Referenced by gist_box_picksplit().

329 {
330  float8 upper1 = ((const SplitInterval *) i1)->upper,
331  upper2 = ((const SplitInterval *) i2)->upper;
332 
333  return float8_cmp_internal(upper1, upper2);
334 }
int float8_cmp_internal(float8 a, float8 b)
Definition: float.c:914
double float8
Definition: c.h:553

◆ non_negative()

static float non_negative ( float  val)
inlinestatic

Definition at line 340 of file gistproc.c.

References val.

Referenced by g_box_consider_split().

341 {
342  if (val >= 0.0f)
343  return val;
344  else
345  return 0.0f;
346 }
long val
Definition: informix.c:664

◆ part_bits32_by2()

static uint64 part_bits32_by2 ( uint32  x)
static

Definition at line 1587 of file gistproc.c.

Referenced by point_zorder_internal().

1588 {
1589  uint64 n = x;
1590 
1591  n = (n | (n << 16)) & UINT64CONST(0x0000FFFF0000FFFF);
1592  n = (n | (n << 8)) & UINT64CONST(0x00FF00FF00FF00FF);
1593  n = (n | (n << 4)) & UINT64CONST(0x0F0F0F0F0F0F0F0F);
1594  n = (n | (n << 2)) & UINT64CONST(0x3333333333333333);
1595  n = (n | (n << 1)) & UINT64CONST(0x5555555555555555);
1596 
1597  return n;
1598 }

◆ point_zorder_internal()

static uint64 point_zorder_internal ( float4  x,
float4  y 
)
static

Definition at line 1576 of file gistproc.c.

References ieee_float32_to_uint32(), and part_bits32_by2().

Referenced by gist_bbox_zorder_abbrev_convert(), and gist_bbox_zorder_cmp().

1577 {
1580 
1581  /* Interleave the bits */
1582  return part_bits32_by2(ix) | (part_bits32_by2(iy) << 1);
1583 }
static uint64 part_bits32_by2(uint32 x)
Definition: gistproc.c:1587
unsigned int uint32
Definition: c.h:429
static uint32 ieee_float32_to_uint32(float f)
Definition: gistproc.c:1604

◆ rt_box_union()

static void rt_box_union ( BOX n,
const BOX a,
const BOX b 
)
static

Definition at line 56 of file gistproc.c.

References float8_max(), float8_min(), BOX::high, BOX::low, Point::x, and Point::y.

Referenced by box_penalty().

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 }
float8 x
Definition: geo_decls.h:98
static float8 float8_min(const float8 val1, const float8 val2)
Definition: float.h:339
Point low
Definition: geo_decls.h:142
float8 y
Definition: geo_decls.h:98
Point high
Definition: geo_decls.h:142
static float8 float8_max(const float8 val1, const float8 val2)
Definition: float.h:351

◆ rtree_internal_consistent()

static bool rtree_internal_consistent ( BOX key,
BOX query,
StrategyNumber  strategy 
)
static

Definition at line 958 of file gistproc.c.

References box_above(), box_below(), box_contain(), box_left(), box_overabove(), box_overbelow(), box_overlap(), box_overleft(), box_overright(), box_right(), DatumGetBool, DirectFunctionCall2, elog, ERROR, PointerGetDatum, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTContainsStrategyNumber, RTLeftStrategyNumber, RTOverAboveStrategyNumber, RTOverBelowStrategyNumber, RTOverlapStrategyNumber, RTOverLeftStrategyNumber, RTOverRightStrategyNumber, RTRightStrategyNumber, and RTSameStrategyNumber.

Referenced by gist_box_consistent(), gist_circle_consistent(), and gist_poly_consistent().

959 {
960  bool retval;
961 
962  switch (strategy)
963  {
966  PointerGetDatum(key),
967  PointerGetDatum(query)));
968  break;
971  PointerGetDatum(key),
972  PointerGetDatum(query)));
973  break;
976  PointerGetDatum(key),
977  PointerGetDatum(query)));
978  break;
981  PointerGetDatum(key),
982  PointerGetDatum(query)));
983  break;
986  PointerGetDatum(key),
987  PointerGetDatum(query)));
988  break;
992  PointerGetDatum(key),
993  PointerGetDatum(query)));
994  break;
997  PointerGetDatum(key),
998  PointerGetDatum(query)));
999  break;
1002  PointerGetDatum(key),
1003  PointerGetDatum(query)));
1004  break;
1005  case RTBelowStrategyNumber:
1007  PointerGetDatum(key),
1008  PointerGetDatum(query)));
1009  break;
1010  case RTAboveStrategyNumber:
1012  PointerGetDatum(key),
1013  PointerGetDatum(query)));
1014  break;
1017  PointerGetDatum(key),
1018  PointerGetDatum(query)));
1019  break;
1020  default:
1021  elog(ERROR, "unrecognized strategy number: %d", strategy);
1022  retval = false; /* keep compiler quiet */
1023  break;
1024  }
1025  return retval;
1026 }
Datum box_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:597
Datum box_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:571
#define RTLeftStrategyNumber
Definition: stratnum.h:51
Datum box_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:612
#define PointerGetDatum(X)
Definition: postgres.h:556
Datum box_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:551
#define RTOverBelowStrategyNumber
Definition: stratnum.h:59
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define RTOverAboveStrategyNumber
Definition: stratnum.h:62
#define ERROR
Definition: elog.h:43
Datum box_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:680
Datum box_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:646
#define DatumGetBool(X)
Definition: postgres.h:393
#define RTSameStrategyNumber
Definition: stratnum.h:56
#define RTOverRightStrategyNumber
Definition: stratnum.h:54
#define RTOverLeftStrategyNumber
Definition: stratnum.h:52
Datum box_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:635
Datum box_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:623
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define RTRightStrategyNumber
Definition: stratnum.h:55
Datum box_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:586
#define RTContainsStrategyNumber
Definition: stratnum.h:57
#define elog(elevel,...)
Definition: elog.h:228
#define RTOverlapStrategyNumber
Definition: stratnum.h:53
Datum box_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:658
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:628

◆ size_box()

static float8 size_box ( const BOX box)
static

Definition at line 69 of file gistproc.c.

References float8_le(), float8_mi(), float8_mul(), get_float8_infinity(), BOX::high, BOX::low, Point::x, and Point::y.

Referenced by box_penalty().

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 }
static float8 get_float8_infinity(void)
Definition: float.h:93
float8 x
Definition: geo_decls.h:98
static bool float8_le(const float8 val1, const float8 val2)
Definition: float.h:303
static float8 float8_mul(const float8 val1, const float8 val2)
Definition: float.h:207
static float8 float8_mi(const float8 val1, const float8 val2)
Definition: float.h:181
Point low
Definition: geo_decls.h:142
float8 y
Definition: geo_decls.h:98
Point high
Definition: geo_decls.h:142