PostgreSQL Source Code  git master
spgquadtreeproc.c File Reference
#include "postgres.h"
#include "access/spgist.h"
#include "access/spgist_private.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/float.h"
#include "utils/fmgrprotos.h"
#include "utils/geo_decls.h"
Include dependency graph for spgquadtreeproc.c:

Go to the source code of this file.

Macros

#define SPTEST(f, x, y)    DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))
 

Functions

Datum spg_quad_config (PG_FUNCTION_ARGS)
 
static int16 getQuadrant (Point *centroid, Point *tst)
 
static BOXgetQuadrantArea (BOX *bbox, Point *centroid, int quadrant)
 
Datum spg_quad_choose (PG_FUNCTION_ARGS)
 
Datum spg_quad_picksplit (PG_FUNCTION_ARGS)
 
Datum spg_quad_inner_consistent (PG_FUNCTION_ARGS)
 
Datum spg_quad_leaf_consistent (PG_FUNCTION_ARGS)
 

Macro Definition Documentation

◆ SPTEST

#define SPTEST (   f,
  x,
  y 
)     DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))

Definition at line 39 of file spgquadtreeproc.c.

Function Documentation

◆ getQuadrant()

static int16 getQuadrant ( Point centroid,
Point tst 
)
static

Definition at line 55 of file spgquadtreeproc.c.

56 {
57  if ((SPTEST(point_above, tst, centroid) ||
58  SPTEST(point_horiz, tst, centroid)) &&
59  (SPTEST(point_right, tst, centroid) ||
60  SPTEST(point_vert, tst, centroid)))
61  return 1;
62 
63  if (SPTEST(point_below, tst, centroid) &&
64  (SPTEST(point_right, tst, centroid) ||
65  SPTEST(point_vert, tst, centroid)))
66  return 2;
67 
68  if ((SPTEST(point_below, tst, centroid) ||
69  SPTEST(point_horiz, tst, centroid)) &&
70  SPTEST(point_left, tst, centroid))
71  return 3;
72 
73  if (SPTEST(point_above, tst, centroid) &&
74  SPTEST(point_left, tst, centroid))
75  return 4;
76 
77  elog(ERROR, "getQuadrant: impossible case");
78  return 0;
79 }
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
Datum point_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1919
Datum point_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1928
Datum point_horiz(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1946
Datum point_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1901
Datum point_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1910
Datum point_vert(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1937
#define SPTEST(f, x, y)

References elog, ERROR, point_above(), point_below(), point_horiz(), point_left(), point_right(), point_vert(), and SPTEST.

Referenced by spg_quad_choose(), spg_quad_inner_consistent(), and spg_quad_picksplit().

◆ getQuadrantArea()

static BOX* getQuadrantArea ( BOX bbox,
Point centroid,
int  quadrant 
)
static

Definition at line 83 of file spgquadtreeproc.c.

84 {
85  BOX *result = (BOX *) palloc(sizeof(BOX));
86 
87  switch (quadrant)
88  {
89  case 1:
90  result->high = bbox->high;
91  result->low = *centroid;
92  break;
93  case 2:
94  result->high.x = bbox->high.x;
95  result->high.y = centroid->y;
96  result->low.x = centroid->x;
97  result->low.y = bbox->low.y;
98  break;
99  case 3:
100  result->high = *centroid;
101  result->low = bbox->low;
102  break;
103  case 4:
104  result->high.x = centroid->x;
105  result->high.y = bbox->high.y;
106  result->low.x = bbox->low.x;
107  result->low.y = centroid->y;
108  break;
109  }
110 
111  return result;
112 }
void * palloc(Size size)
Definition: mcxt.c:1304
Definition: geo_decls.h:141
Point low
Definition: geo_decls.h:143
Point high
Definition: geo_decls.h:142
float8 y
Definition: geo_decls.h:99
float8 x
Definition: geo_decls.h:98

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

Referenced by spg_quad_inner_consistent().

◆ spg_quad_choose()

Datum spg_quad_choose ( PG_FUNCTION_ARGS  )

Definition at line 115 of file spgquadtreeproc.c.

116 {
119  Point *inPoint = DatumGetPointP(in->datum),
120  *centroid;
121 
122  if (in->allTheSame)
123  {
124  out->resultType = spgMatchNode;
125  /* nodeN will be set by core */
126  out->result.matchNode.levelAdd = 0;
127  out->result.matchNode.restDatum = PointPGetDatum(inPoint);
128  PG_RETURN_VOID();
129  }
130 
131  Assert(in->hasPrefix);
132  centroid = DatumGetPointP(in->prefixDatum);
133 
134  Assert(in->nNodes == 4);
135 
136  out->resultType = spgMatchNode;
137  out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
138  out->result.matchNode.levelAdd = 0;
139  out->result.matchNode.restDatum = PointPGetDatum(inPoint);
140 
141  PG_RETURN_VOID();
142 }
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
static Point * DatumGetPointP(Datum X)
Definition: geo_decls.h:176
static Datum PointPGetDatum(const Point *X)
Definition: geo_decls.h:181
Assert(fmt[strlen(fmt) - 1] !='\n')
@ spgMatchNode
Definition: spgist.h:69
static int16 getQuadrant(Point *centroid, Point *tst)
bool hasPrefix
Definition: spgist.h:61
Datum prefixDatum
Definition: spgist.h:62
int nNodes
Definition: spgist.h:63
Datum datum
Definition: spgist.h:55
bool allTheSame
Definition: spgist.h:60
spgChooseResultType resultType
Definition: spgist.h:76
struct spgChooseOut::@49::@50 matchNode
union spgChooseOut::@49 result

References spgChooseIn::allTheSame, Assert(), spgChooseIn::datum, DatumGetPointP(), getQuadrant(), spgChooseIn::hasPrefix, spgChooseOut::matchNode, spgChooseIn::nNodes, PG_GETARG_POINTER, PG_RETURN_VOID, PointPGetDatum(), spgChooseIn::prefixDatum, spgChooseOut::result, spgChooseOut::resultType, and spgMatchNode.

◆ spg_quad_config()

Datum spg_quad_config ( PG_FUNCTION_ARGS  )

Definition at line 27 of file spgquadtreeproc.c.

28 {
29  /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
31 
32  cfg->prefixType = POINTOID;
33  cfg->labelType = VOIDOID; /* we don't need node labels */
34  cfg->canReturnData = true;
35  cfg->longValuesOK = false;
37 }
bool longValuesOK
Definition: spgist.h:47
bool canReturnData
Definition: spgist.h:46
Oid labelType
Definition: spgist.h:44
Oid prefixType
Definition: spgist.h:43

References spgConfigOut::canReturnData, spgConfigOut::labelType, spgConfigOut::longValuesOK, PG_GETARG_POINTER, PG_RETURN_VOID, and spgConfigOut::prefixType.

◆ spg_quad_inner_consistent()

Datum spg_quad_inner_consistent ( PG_FUNCTION_ARGS  )

Definition at line 227 of file spgquadtreeproc.c.

228 {
231  Point *centroid;
232  BOX infbbox;
233  BOX *bbox = NULL;
234  int which;
235  int i;
236 
237  Assert(in->hasPrefix);
238  centroid = DatumGetPointP(in->prefixDatum);
239 
240  /*
241  * When ordering scan keys are specified, we've to calculate distance for
242  * them. In order to do that, we need calculate bounding boxes for all
243  * children nodes. Calculation of those bounding boxes on non-zero level
244  * require knowledge of bounding box of upper node. So, we save bounding
245  * boxes to traversalValues.
246  */
247  if (in->norderbys > 0)
248  {
249  out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
250  out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
251 
252  if (in->level == 0)
253  {
254  double inf = get_float8_infinity();
255 
256  infbbox.high.x = inf;
257  infbbox.high.y = inf;
258  infbbox.low.x = -inf;
259  infbbox.low.y = -inf;
260  bbox = &infbbox;
261  }
262  else
263  {
264  bbox = in->traversalValue;
265  Assert(bbox);
266  }
267  }
268 
269  if (in->allTheSame)
270  {
271  /* Report that all nodes should be visited */
272  out->nNodes = in->nNodes;
273  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
274  for (i = 0; i < in->nNodes; i++)
275  {
276  out->nodeNumbers[i] = i;
277 
278  if (in->norderbys > 0)
279  {
281 
282  /* Use parent quadrant box as traversalValue */
283  BOX *quadrant = box_copy(bbox);
284 
285  MemoryContextSwitchTo(oldCtx);
286 
287  out->traversalValues[i] = quadrant;
288  out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
289  in->orderbys, in->norderbys);
290  }
291  }
292  PG_RETURN_VOID();
293  }
294 
295  Assert(in->nNodes == 4);
296 
297  /* "which" is a bitmask of quadrants that satisfy all constraints */
298  which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
299 
300  for (i = 0; i < in->nkeys; i++)
301  {
302  Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
303  BOX *boxQuery;
304 
305  switch (in->scankeys[i].sk_strategy)
306  {
308  if (SPTEST(point_right, centroid, query))
309  which &= (1 << 3) | (1 << 4);
310  break;
312  if (SPTEST(point_left, centroid, query))
313  which &= (1 << 1) | (1 << 2);
314  break;
316  which &= (1 << getQuadrant(centroid, query));
317  break;
320  if (SPTEST(point_above, centroid, query))
321  which &= (1 << 2) | (1 << 3);
322  break;
325  if (SPTEST(point_below, centroid, query))
326  which &= (1 << 1) | (1 << 4);
327  break;
329 
330  /*
331  * For this operator, the query is a box not a point. We
332  * cheat to the extent of assuming that DatumGetPointP won't
333  * do anything that would be bad for a pointer-to-box.
334  */
335  boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
336 
338  PointerGetDatum(boxQuery),
339  PointerGetDatum(centroid))))
340  {
341  /* centroid is in box, so all quadrants are OK */
342  }
343  else
344  {
345  /* identify quadrant(s) containing all corners of box */
346  Point p;
347  int r = 0;
348 
349  p = boxQuery->low;
350  r |= 1 << getQuadrant(centroid, &p);
351  p.y = boxQuery->high.y;
352  r |= 1 << getQuadrant(centroid, &p);
353  p = boxQuery->high;
354  r |= 1 << getQuadrant(centroid, &p);
355  p.x = boxQuery->low.x;
356  r |= 1 << getQuadrant(centroid, &p);
357 
358  which &= r;
359  }
360  break;
361  default:
362  elog(ERROR, "unrecognized strategy number: %d",
363  in->scankeys[i].sk_strategy);
364  break;
365  }
366 
367  if (which == 0)
368  break; /* no need to consider remaining conditions */
369  }
370 
371  out->levelAdds = palloc(sizeof(int) * 4);
372  for (i = 0; i < 4; ++i)
373  out->levelAdds[i] = 1;
374 
375  /* We must descend into the quadrant(s) identified by which */
376  out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
377  out->nNodes = 0;
378 
379  for (i = 1; i <= 4; i++)
380  {
381  if (which & (1 << i))
382  {
383  out->nodeNumbers[out->nNodes] = i - 1;
384 
385  if (in->norderbys > 0)
386  {
388  BOX *quadrant = getQuadrantArea(bbox, centroid, i);
389 
390  MemoryContextSwitchTo(oldCtx);
391 
392  out->traversalValues[out->nNodes] = quadrant;
393 
394  out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
395  in->orderbys, in->norderbys);
396  }
397 
398  out->nNodes++;
399  }
400  }
401 
402  PG_RETURN_VOID();
403 }
static float8 get_float8_infinity(void)
Definition: float.h:94
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:644
static BOX * DatumGetBoxP(Datum X)
Definition: geo_decls.h:234
static Datum BoxPGetDatum(const BOX *X)
Definition: geo_decls.h:239
Datum box_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3146
int i
Definition: isn.c:73
static bool DatumGetBool(Datum X)
Definition: postgres.h:90
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
MemoryContextSwitchTo(old_ctx)
BOX * box_copy(BOX *orig)
Definition: spgproc.c:82
double * spg_key_orderbys_distances(Datum key, bool isLeaf, ScanKey orderbys, int norderbys)
Definition: spgproc.c:63
static BOX * getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
#define RTLeftStrategyNumber
Definition: stratnum.h:51
#define RTRightStrategyNumber
Definition: stratnum.h:55
#define RTSameStrategyNumber
Definition: stratnum.h:56
#define RTOldBelowStrategyNumber
Definition: stratnum.h:79
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define RTOldAboveStrategyNumber
Definition: stratnum.h:80
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
Datum sk_argument
Definition: skey.h:72
StrategyNumber sk_strategy
Definition: skey.h:68
void * traversalValue
Definition: spgist.h:141
ScanKey scankeys
Definition: spgist.h:134
ScanKey orderbys
Definition: spgist.h:135
MemoryContext traversalMemoryContext
Definition: spgist.h:142
void ** traversalValues
Definition: spgist.h:160
double ** distances
Definition: spgist.h:161

References spgInnerConsistentIn::allTheSame, Assert(), box_contain_pt(), box_copy(), BoxPGetDatum(), DatumGetBool(), DatumGetBoxP(), DatumGetPointP(), DirectFunctionCall2, spgInnerConsistentOut::distances, elog, ERROR, get_float8_infinity(), getQuadrant(), getQuadrantArea(), spgInnerConsistentIn::hasPrefix, BOX::high, i, spgInnerConsistentIn::level, spgInnerConsistentOut::levelAdds, BOX::low, MemoryContextSwitchTo(), spgInnerConsistentIn::nkeys, spgInnerConsistentIn::nNodes, spgInnerConsistentOut::nNodes, spgInnerConsistentOut::nodeNumbers, spgInnerConsistentIn::norderbys, spgInnerConsistentIn::orderbys, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, point_above(), point_below(), point_left(), point_right(), PointerGetDatum(), spgInnerConsistentIn::prefixDatum, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTLeftStrategyNumber, RTOldAboveStrategyNumber, RTOldBelowStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, spgInnerConsistentIn::scankeys, ScanKeyData::sk_argument, ScanKeyData::sk_strategy, spg_key_orderbys_distances(), SPTEST, spgInnerConsistentIn::traversalMemoryContext, spgInnerConsistentIn::traversalValue, spgInnerConsistentOut::traversalValues, Point::x, and Point::y.

◆ spg_quad_leaf_consistent()

Datum spg_quad_leaf_consistent ( PG_FUNCTION_ARGS  )

Definition at line 407 of file spgquadtreeproc.c.

408 {
411  Point *datum = DatumGetPointP(in->leafDatum);
412  bool res;
413  int i;
414 
415  /* all tests are exact */
416  out->recheck = false;
417 
418  /* leafDatum is what it is... */
419  out->leafValue = in->leafDatum;
420 
421  /* Perform the required comparison(s) */
422  res = true;
423  for (i = 0; i < in->nkeys; i++)
424  {
425  Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
426 
427  switch (in->scankeys[i].sk_strategy)
428  {
430  res = SPTEST(point_left, datum, query);
431  break;
433  res = SPTEST(point_right, datum, query);
434  break;
436  res = SPTEST(point_eq, datum, query);
437  break;
440  res = SPTEST(point_below, datum, query);
441  break;
444  res = SPTEST(point_above, datum, query);
445  break;
447 
448  /*
449  * For this operator, the query is a box not a point. We
450  * cheat to the extent of assuming that DatumGetPointP won't
451  * do anything that would be bad for a pointer-to-box.
452  */
453  res = SPTEST(box_contain_pt, query, datum);
454  break;
455  default:
456  elog(ERROR, "unrecognized strategy number: %d",
457  in->scankeys[i].sk_strategy);
458  break;
459  }
460 
461  if (!res)
462  break;
463  }
464 
465  if (res && in->norderbys > 0)
466  /* ok, it passes -> let's compute the distances */
468  in->orderbys, in->norderbys);
469 
471 }
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
Datum point_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1955
ScanKey scankeys
Definition: spgist.h:169
ScanKey orderbys
Definition: spgist.h:170
double * distances
Definition: spgist.h:188

References box_contain_pt(), DatumGetPointP(), spgLeafConsistentOut::distances, elog, ERROR, i, spgLeafConsistentIn::leafDatum, spgLeafConsistentOut::leafValue, spgLeafConsistentIn::nkeys, spgLeafConsistentIn::norderbys, spgLeafConsistentIn::orderbys, PG_GETARG_POINTER, PG_RETURN_BOOL, point_above(), point_below(), point_eq(), point_left(), point_right(), spgLeafConsistentOut::recheck, res, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTLeftStrategyNumber, RTOldAboveStrategyNumber, RTOldBelowStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, spgLeafConsistentIn::scankeys, ScanKeyData::sk_argument, ScanKeyData::sk_strategy, spg_key_orderbys_distances(), and SPTEST.

◆ spg_quad_picksplit()

Datum spg_quad_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 169 of file spgquadtreeproc.c.

170 {
173  int i;
174  Point *centroid;
175 
176 #ifdef USE_MEDIAN
177  /* Use the median values of x and y as the centroid point */
178  Point **sorted;
179 
180  sorted = palloc(sizeof(*sorted) * in->nTuples);
181  for (i = 0; i < in->nTuples; i++)
182  sorted[i] = DatumGetPointP(in->datums[i]);
183 
184  centroid = palloc(sizeof(*centroid));
185 
186  qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
187  centroid->x = sorted[in->nTuples >> 1]->x;
188  qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
189  centroid->y = sorted[in->nTuples >> 1]->y;
190 #else
191  /* Use the average values of x and y as the centroid point */
192  centroid = palloc0(sizeof(*centroid));
193 
194  for (i = 0; i < in->nTuples; i++)
195  {
196  centroid->x += DatumGetPointP(in->datums[i])->x;
197  centroid->y += DatumGetPointP(in->datums[i])->y;
198  }
199 
200  centroid->x /= in->nTuples;
201  centroid->y /= in->nTuples;
202 #endif
203 
204  out->hasPrefix = true;
205  out->prefixDatum = PointPGetDatum(centroid);
206 
207  out->nNodes = 4;
208  out->nodeLabels = NULL; /* we don't need node labels */
209 
210  out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
211  out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
212 
213  for (i = 0; i < in->nTuples; i++)
214  {
215  Point *p = DatumGetPointP(in->datums[i]);
216  int quadrant = getQuadrant(centroid, p) - 1;
217 
218  out->leafTupleDatums[i] = PointPGetDatum(p);
219  out->mapTuplesToNodes[i] = quadrant;
220  }
221 
222  PG_RETURN_VOID();
223 }
void * palloc0(Size size)
Definition: mcxt.c:1334
#define qsort(a, b, c, d)
Definition: port.h:449
uintptr_t Datum
Definition: postgres.h:64
static int x_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:85
static int y_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:96
Datum * datums
Definition: spgist.h:113
bool hasPrefix
Definition: spgist.h:119
int * mapTuplesToNodes
Definition: spgist.h:125
Datum * nodeLabels
Definition: spgist.h:123
Datum * leafTupleDatums
Definition: spgist.h:126
Datum prefixDatum
Definition: spgist.h:120

References DatumGetPointP(), spgPickSplitIn::datums, getQuadrant(), spgPickSplitOut::hasPrefix, i, spgPickSplitOut::leafTupleDatums, spgPickSplitOut::mapTuplesToNodes, spgPickSplitOut::nNodes, spgPickSplitOut::nodeLabels, spgPickSplitIn::nTuples, palloc(), palloc0(), PG_GETARG_POINTER, PG_RETURN_VOID, PointPGetDatum(), spgPickSplitOut::prefixDatum, qsort, Point::x, x_cmp(), Point::y, and y_cmp().