PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
spgquadtreeproc.c File Reference
#include "postgres.h"
#include "access/spgist.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/builtins.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)
 
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

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

Function Documentation

static int16 getQuadrant ( Point centroid,
Point tst 
)
static

Definition at line 54 of file spgquadtreeproc.c.

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().

55 {
56  if ((SPTEST(point_above, tst, centroid) ||
57  SPTEST(point_horiz, tst, centroid)) &&
58  (SPTEST(point_right, tst, centroid) ||
59  SPTEST(point_vert, tst, centroid)))
60  return 1;
61 
62  if (SPTEST(point_below, tst, centroid) &&
63  (SPTEST(point_right, tst, centroid) ||
64  SPTEST(point_vert, tst, centroid)))
65  return 2;
66 
67  if ((SPTEST(point_below, tst, centroid) ||
68  SPTEST(point_horiz, tst, centroid)) &&
69  SPTEST(point_left, tst, centroid))
70  return 3;
71 
72  if (SPTEST(point_above, tst, centroid) &&
73  SPTEST(point_left, tst, centroid))
74  return 4;
75 
76  elog(ERROR, "getQuadrant: impossible case");
77  return 0;
78 }
Datum point_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1848
Datum point_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1830
#define ERROR
Definition: elog.h:43
Datum point_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1821
#define SPTEST(f, x, y)
Datum point_vert(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1857
Datum point_horiz(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1866
Datum point_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1839
#define elog
Definition: elog.h:219
Datum spg_quad_choose ( PG_FUNCTION_ARGS  )

Definition at line 82 of file spgquadtreeproc.c.

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.

83 {
86  Point *inPoint = DatumGetPointP(in->datum),
87  *centroid;
88 
89  if (in->allTheSame)
90  {
91  out->resultType = spgMatchNode;
92  /* nodeN will be set by core */
93  out->result.matchNode.levelAdd = 0;
94  out->result.matchNode.restDatum = PointPGetDatum(inPoint);
96  }
97 
98  Assert(in->hasPrefix);
99  centroid = DatumGetPointP(in->prefixDatum);
100 
101  Assert(in->nNodes == 4);
102 
103  out->resultType = spgMatchNode;
104  out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
105  out->result.matchNode.levelAdd = 0;
106  out->result.matchNode.restDatum = PointPGetDatum(inPoint);
107 
108  PG_RETURN_VOID();
109 }
Datum datum
Definition: spgist.h:56
bool hasPrefix
Definition: spgist.h:62
struct spgChooseOut::@48::@49 matchNode
Datum prefixDatum
Definition: spgist.h:63
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
static int16 getQuadrant(Point *centroid, Point *tst)
int nNodes
Definition: spgist.h:64
spgChooseResultType resultType
Definition: spgist.h:77
#define PG_RETURN_VOID()
Definition: fmgr.h:309
#define Assert(condition)
Definition: c.h:675
#define DatumGetPointP(X)
Definition: geo_decls.h:137
union spgChooseOut::@48 result
bool allTheSame
Definition: spgist.h:61
#define PointPGetDatum(X)
Definition: geo_decls.h:138
Datum spg_quad_config ( PG_FUNCTION_ARGS  )

Definition at line 26 of file spgquadtreeproc.c.

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

27 {
28  /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
30 
31  cfg->prefixType = POINTOID;
32  cfg->labelType = VOIDOID; /* we don't need node labels */
33  cfg->canReturnData = true;
34  cfg->longValuesOK = false;
36 }
bool canReturnData
Definition: spgist.h:47
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
#define VOIDOID
Definition: pg_type.h:690
#define POINTOID
Definition: pg_type.h:393
bool longValuesOK
Definition: spgist.h:48
Oid prefixType
Definition: spgist.h:45
#define PG_RETURN_VOID()
Definition: fmgr.h:309
Oid labelType
Definition: spgist.h:46
Datum spg_quad_inner_consistent ( PG_FUNCTION_ARGS  )

Definition at line 194 of file spgquadtreeproc.c.

References spgInnerConsistentIn::allTheSame, Assert, box_contain_pt(), DatumGetBool, DatumGetBoxP, DatumGetPointP, DirectFunctionCall2, elog, ERROR, getQuadrant(), spgInnerConsistentIn::hasPrefix, BOX::high, i, BOX::low, spgInnerConsistentIn::nkeys, spgInnerConsistentIn::nNodes, spgInnerConsistentOut::nNodes, spgInnerConsistentOut::nodeNumbers, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, point_above(), point_below(), point_left(), point_right(), PointerGetDatum, spgInnerConsistentIn::prefixDatum, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTLeftStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, spgInnerConsistentIn::scankeys, ScanKeyData::sk_argument, ScanKeyData::sk_strategy, SPTEST, Point::x, and Point::y.

195 {
198  Point *centroid;
199  int which;
200  int i;
201 
202  Assert(in->hasPrefix);
203  centroid = DatumGetPointP(in->prefixDatum);
204 
205  if (in->allTheSame)
206  {
207  /* Report that all nodes should be visited */
208  out->nNodes = in->nNodes;
209  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
210  for (i = 0; i < in->nNodes; i++)
211  out->nodeNumbers[i] = i;
212  PG_RETURN_VOID();
213  }
214 
215  Assert(in->nNodes == 4);
216 
217  /* "which" is a bitmask of quadrants that satisfy all constraints */
218  which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
219 
220  for (i = 0; i < in->nkeys; i++)
221  {
222  Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
223  BOX *boxQuery;
224 
225  switch (in->scankeys[i].sk_strategy)
226  {
228  if (SPTEST(point_right, centroid, query))
229  which &= (1 << 3) | (1 << 4);
230  break;
232  if (SPTEST(point_left, centroid, query))
233  which &= (1 << 1) | (1 << 2);
234  break;
236  which &= (1 << getQuadrant(centroid, query));
237  break;
239  if (SPTEST(point_above, centroid, query))
240  which &= (1 << 2) | (1 << 3);
241  break;
243  if (SPTEST(point_below, centroid, query))
244  which &= (1 << 1) | (1 << 4);
245  break;
247 
248  /*
249  * For this operator, the query is a box not a point. We
250  * cheat to the extent of assuming that DatumGetPointP won't
251  * do anything that would be bad for a pointer-to-box.
252  */
253  boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
254 
256  PointerGetDatum(boxQuery),
257  PointerGetDatum(centroid))))
258  {
259  /* centroid is in box, so all quadrants are OK */
260  }
261  else
262  {
263  /* identify quadrant(s) containing all corners of box */
264  Point p;
265  int r = 0;
266 
267  p = boxQuery->low;
268  r |= 1 << getQuadrant(centroid, &p);
269  p.y = boxQuery->high.y;
270  r |= 1 << getQuadrant(centroid, &p);
271  p = boxQuery->high;
272  r |= 1 << getQuadrant(centroid, &p);
273  p.x = boxQuery->low.x;
274  r |= 1 << getQuadrant(centroid, &p);
275 
276  which &= r;
277  }
278  break;
279  default:
280  elog(ERROR, "unrecognized strategy number: %d",
281  in->scankeys[i].sk_strategy);
282  break;
283  }
284 
285  if (which == 0)
286  break; /* no need to consider remaining conditions */
287  }
288 
289  /* We must descend into the quadrant(s) identified by which */
290  out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
291  out->nNodes = 0;
292  for (i = 1; i <= 4; i++)
293  {
294  if (which & (1 << i))
295  out->nodeNumbers[out->nNodes++] = i - 1;
296  }
297 
298  PG_RETURN_VOID();
299 }
Definition: geo_decls.h:102
#define RTLeftStrategyNumber
Definition: stratnum.h:44
#define PointerGetDatum(X)
Definition: postgres.h:562
Datum box_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3171
double y
Definition: geo_decls.h:60
#define RTContainedByStrategyNumber
Definition: stratnum.h:51
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
#define RTBelowStrategyNumber
Definition: stratnum.h:53
double x
Definition: geo_decls.h:60
Datum point_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1848
Datum point_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1830
#define ERROR
Definition: elog.h:43
StrategyNumber sk_strategy
Definition: skey.h:68
Datum point_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1821
#define SPTEST(f, x, y)
#define DatumGetBool(X)
Definition: postgres.h:399
#define RTSameStrategyNumber
Definition: stratnum.h:49
static int16 getQuadrant(Point *centroid, Point *tst)
Point low
Definition: geo_decls.h:104
#define PG_RETURN_VOID()
Definition: fmgr.h:309
#define RTAboveStrategyNumber
Definition: stratnum.h:54
#define Assert(condition)
Definition: c.h:675
#define RTRightStrategyNumber
Definition: stratnum.h:48
#define DatumGetPointP(X)
Definition: geo_decls.h:137
ScanKey scankeys
Definition: spgist.h:135
#define DatumGetBoxP(X)
Definition: geo_decls.h:159
Point high
Definition: geo_decls.h:104
void * palloc(Size size)
Definition: mcxt.c:849
int i
Datum point_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1839
#define elog
Definition: elog.h:219
Datum sk_argument
Definition: skey.h:72
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:586
Datum spg_quad_leaf_consistent ( PG_FUNCTION_ARGS  )

Definition at line 303 of file spgquadtreeproc.c.

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

304 {
307  Point *datum = DatumGetPointP(in->leafDatum);
308  bool res;
309  int i;
310 
311  /* all tests are exact */
312  out->recheck = false;
313 
314  /* leafDatum is what it is... */
315  out->leafValue = in->leafDatum;
316 
317  /* Perform the required comparison(s) */
318  res = true;
319  for (i = 0; i < in->nkeys; i++)
320  {
321  Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
322 
323  switch (in->scankeys[i].sk_strategy)
324  {
326  res = SPTEST(point_left, datum, query);
327  break;
329  res = SPTEST(point_right, datum, query);
330  break;
332  res = SPTEST(point_eq, datum, query);
333  break;
335  res = SPTEST(point_below, datum, query);
336  break;
338  res = SPTEST(point_above, datum, query);
339  break;
341 
342  /*
343  * For this operator, the query is a box not a point. We
344  * cheat to the extent of assuming that DatumGetPointP won't
345  * do anything that would be bad for a pointer-to-box.
346  */
347  res = SPTEST(box_contain_pt, query, datum);
348  break;
349  default:
350  elog(ERROR, "unrecognized strategy number: %d",
351  in->scankeys[i].sk_strategy);
352  break;
353  }
354 
355  if (!res)
356  break;
357  }
358 
359  PG_RETURN_BOOL(res);
360 }
#define RTLeftStrategyNumber
Definition: stratnum.h:44
Datum box_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3171
#define RTContainedByStrategyNumber
Definition: stratnum.h:51
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
#define RTBelowStrategyNumber
Definition: stratnum.h:53
Datum point_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1848
Datum point_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1830
#define ERROR
Definition: elog.h:43
StrategyNumber sk_strategy
Definition: skey.h:68
ScanKey scankeys
Definition: spgist.h:167
Datum point_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1821
#define SPTEST(f, x, y)
#define RTSameStrategyNumber
Definition: stratnum.h:49
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:319
#define RTAboveStrategyNumber
Definition: stratnum.h:54
#define RTRightStrategyNumber
Definition: stratnum.h:48
#define DatumGetPointP(X)
Definition: geo_decls.h:137
Datum point_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1875
int i
Datum point_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1839
#define elog
Definition: elog.h:219
Datum sk_argument
Definition: skey.h:72
Datum spg_quad_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 136 of file spgquadtreeproc.c.

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

137 {
140  int i;
141  Point *centroid;
142 
143 #ifdef USE_MEDIAN
144  /* Use the median values of x and y as the centroid point */
145  Point **sorted;
146 
147  sorted = palloc(sizeof(*sorted) * in->nTuples);
148  for (i = 0; i < in->nTuples; i++)
149  sorted[i] = DatumGetPointP(in->datums[i]);
150 
151  centroid = palloc(sizeof(*centroid));
152 
153  qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
154  centroid->x = sorted[in->nTuples >> 1]->x;
155  qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
156  centroid->y = sorted[in->nTuples >> 1]->y;
157 #else
158  /* Use the average values of x and y as the centroid point */
159  centroid = palloc0(sizeof(*centroid));
160 
161  for (i = 0; i < in->nTuples; i++)
162  {
163  centroid->x += DatumGetPointP(in->datums[i])->x;
164  centroid->y += DatumGetPointP(in->datums[i])->y;
165  }
166 
167  centroid->x /= in->nTuples;
168  centroid->y /= in->nTuples;
169 #endif
170 
171  out->hasPrefix = true;
172  out->prefixDatum = PointPGetDatum(centroid);
173 
174  out->nNodes = 4;
175  out->nodeLabels = NULL; /* we don't need node labels */
176 
177  out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
178  out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
179 
180  for (i = 0; i < in->nTuples; i++)
181  {
182  Point *p = DatumGetPointP(in->datums[i]);
183  int quadrant = getQuadrant(centroid, p) - 1;
184 
185  out->leafTupleDatums[i] = PointPGetDatum(p);
186  out->mapTuplesToNodes[i] = quadrant;
187  }
188 
189  PG_RETURN_VOID();
190 }
Datum * leafTupleDatums
Definition: spgist.h:127
Datum * datums
Definition: spgist.h:114
double y
Definition: geo_decls.h:60
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
double x
Definition: geo_decls.h:60
Datum * nodeLabels
Definition: spgist.h:124
static int16 getQuadrant(Point *centroid, Point *tst)
static int x_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:83
void * palloc0(Size size)
Definition: mcxt.c:878
uintptr_t Datum
Definition: postgres.h:372
#define PG_RETURN_VOID()
Definition: fmgr.h:309
#define NULL
Definition: c.h:229
#define DatumGetPointP(X)
Definition: geo_decls.h:137
bool hasPrefix
Definition: spgist.h:120
void * palloc(Size size)
Definition: mcxt.c:849
int i
int * mapTuplesToNodes
Definition: spgist.h:126
Datum prefixDatum
Definition: spgist.h:121
#define qsort(a, b, c, d)
Definition: port.h:440
#define PointPGetDatum(X)
Definition: geo_decls.h:138
static int y_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:94