PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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:225
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:1317
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 {
125 /* nodeN will be set by core */
126 out->result.matchNode.levelAdd = 0;
129 }
130
131 Assert(in->hasPrefix);
132 centroid = DatumGetPointP(in->prefixDatum);
133
134 Assert(in->nNodes == 4);
135
137 out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
138 out->result.matchNode.levelAdd = 0;
140
142}
#define Assert(condition)
Definition: c.h:812
#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
@ 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
int levelAdd
Definition: spgist.h:82
Datum restDatum
Definition: spgist.h:83
int nodeN
Definition: spgist.h:81
struct spgChooseOut::@51::@52 matchNode
union spgChooseOut::@51 result

References spgChooseIn::allTheSame, Assert, spgChooseIn::datum, DatumGetPointP(), getQuadrant(), spgChooseIn::hasPrefix, spgChooseOut::levelAdd, spgChooseOut::matchNode, spgChooseIn::nNodes, spgChooseOut::nodeN, PG_GETARG_POINTER, PG_RETURN_VOID, PointPGetDatum(), spgChooseIn::prefixDatum, spgChooseOut::restDatum, 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 }
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 {
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
403}
static float8 get_float8_infinity(void)
Definition: float.h:94
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:643
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:72
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
static bool DatumGetBool(Datum X)
Definition: postgres.h:90
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
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 {
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
219 out->mapTuplesToNodes[i] = quadrant;
220 }
221
223}
void * palloc0(Size size)
Definition: mcxt.c:1347
#define qsort(a, b, c, d)
Definition: port.h:447
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().