PostgreSQL Source Code git master
Loading...
Searching...
No Matches
Macros | Functions
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 BOX * getQuadrantArea (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 41 of file spgquadtreeproc.c.

57{
58 if ((SPTEST(point_above, tst, centroid) ||
59 SPTEST(point_horiz, tst, centroid)) &&
60 (SPTEST(point_right, tst, centroid) ||
61 SPTEST(point_vert, tst, centroid)))
62 return 1;
63
64 if (SPTEST(point_below, tst, centroid) &&
65 (SPTEST(point_right, tst, centroid) ||
66 SPTEST(point_vert, tst, centroid)))
67 return 2;
68
69 if ((SPTEST(point_below, tst, centroid) ||
70 SPTEST(point_horiz, tst, centroid)) &&
71 SPTEST(point_left, tst, centroid))
72 return 3;
73
74 if (SPTEST(point_above, tst, centroid) &&
75 SPTEST(point_left, tst, centroid))
76 return 4;
77
78 elog(ERROR, "getQuadrant: impossible case");
79 return 0;
80}
81
82/* Returns bounding box of a given quadrant inside given bounding box */
83static BOX *
84getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
85{
86 BOX *result = palloc_object(BOX);
87
88 switch (quadrant)
89 {
90 case 1:
91 result->high = bbox->high;
92 result->low = *centroid;
93 break;
94 case 2:
95 result->high.x = bbox->high.x;
96 result->high.y = centroid->y;
97 result->low.x = centroid->x;
98 result->low.y = bbox->low.y;
99 break;
100 case 3:
101 result->high = *centroid;
102 result->low = bbox->low;
103 break;
104 case 4:
105 result->high.x = centroid->x;
106 result->high.y = bbox->high.y;
107 result->low.x = bbox->low.x;
108 result->low.y = centroid->y;
109 break;
110 }
111
112 return result;
113}
114
115Datum
116spg_quad_choose(PG_FUNCTION_ARGS)
117{
118 spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
119 spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
120 Point *inPoint = DatumGetPointP(in->datum),
121 *centroid;
122
123 if (in->allTheSame)
124 {
125 out->resultType = spgMatchNode;
126 /* nodeN will be set by core */
127 out->result.matchNode.levelAdd = 0;
128 out->result.matchNode.restDatum = PointPGetDatum(inPoint);
129 PG_RETURN_VOID();
130 }
131
132 Assert(in->hasPrefix);
133 centroid = DatumGetPointP(in->prefixDatum);
134
135 Assert(in->nNodes == 4);
136
137 out->resultType = spgMatchNode;
138 out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
139 out->result.matchNode.levelAdd = 0;
140 out->result.matchNode.restDatum = PointPGetDatum(inPoint);
141
142 PG_RETURN_VOID();
143}
144
145#ifdef USE_MEDIAN
146static int
147x_cmp(const void *a, const void *b, void *arg)
148{
149 Point *pa = *(Point *const *) a;
150 Point *pb = *(Point *const *) b;
151
152 if (pa->x == pb->x)
153 return 0;
154 return (pa->x > pb->x) ? 1 : -1;
155}
156
157static int
158y_cmp(const void *a, const void *b, void *arg)
159{
160 Point *pa = *(Point *const *) a;
161 Point *pb = *(Point *const *) b;
162
163 if (pa->y == pb->y)
164 return 0;
165 return (pa->y > pb->y) ? 1 : -1;
166}
167#endif
168
169Datum
170spg_quad_picksplit(PG_FUNCTION_ARGS)
171{
172 spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
173 spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
174 int i;
175 Point *centroid;
176
177#ifdef USE_MEDIAN
178 /* Use the median values of x and y as the centroid point */
179 Point **sorted;
180
181 sorted = palloc_array(Point *, in->nTuples);
182 for (i = 0; i < in->nTuples; i++)
183 sorted[i] = DatumGetPointP(in->datums[i]);
184
185 centroid = palloc_object(Point);
186
187 qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
188 centroid->x = sorted[in->nTuples >> 1]->x;
189 qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
190 centroid->y = sorted[in->nTuples >> 1]->y;
191#else
192 /* Use the average values of x and y as the centroid point */
193 centroid = palloc0_object(Point);
194
195 for (i = 0; i < in->nTuples; i++)
196 {
197 centroid->x += DatumGetPointP(in->datums[i])->x;
198 centroid->y += DatumGetPointP(in->datums[i])->y;
199 }
200
201 centroid->x /= in->nTuples;
202 centroid->y /= in->nTuples;
203#endif
204
205 out->hasPrefix = true;
206 out->prefixDatum = PointPGetDatum(centroid);
207
208 out->nNodes = 4;
209 out->nodeLabels = NULL; /* we don't need node labels */
210
211 out->mapTuplesToNodes = palloc_array(int, in->nTuples);
212 out->leafTupleDatums = palloc_array(Datum, in->nTuples);
213
214 for (i = 0; i < in->nTuples; i++)
215 {
216 Point *p = DatumGetPointP(in->datums[i]);
217 int quadrant = getQuadrant(centroid, p) - 1;
218
219 out->leafTupleDatums[i] = PointPGetDatum(p);
220 out->mapTuplesToNodes[i] = quadrant;
221 }
222
223 PG_RETURN_VOID();
224}
225
226
227Datum
228spg_quad_inner_consistent(PG_FUNCTION_ARGS)
229{
230 spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
231 spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
232 Point *centroid;
233 BOX infbbox;
234 BOX *bbox = NULL;
235 int which;
236 int i;
237
238 Assert(in->hasPrefix);
239 centroid = DatumGetPointP(in->prefixDatum);
240
241 /*
242 * When ordering scan keys are specified, we've to calculate distance for
243 * them. In order to do that, we need calculate bounding boxes for all
244 * children nodes. Calculation of those bounding boxes on non-zero level
245 * require knowledge of bounding box of upper node. So, we save bounding
246 * boxes to traversalValues.
247 */
248 if (in->norderbys > 0)
249 {
250 out->distances = palloc_array(double *, in->nNodes);
251 out->traversalValues = palloc_array(void *, in->nNodes);
252
253 if (in->level == 0)
254 {
255 double inf = get_float8_infinity();
256
257 infbbox.high.x = inf;
258 infbbox.high.y = inf;
259 infbbox.low.x = -inf;
260 infbbox.low.y = -inf;
261 bbox = &infbbox;
262 }
263 else
264 {
265 bbox = in->traversalValue;
266 Assert(bbox);
267 }
268 }
269
270 if (in->allTheSame)
271 {
272 /* Report that all nodes should be visited */
273 out->nNodes = in->nNodes;
274 out->nodeNumbers = palloc_array(int, in->nNodes);
275 for (i = 0; i < in->nNodes; i++)
276 {
277 out->nodeNumbers[i] = i;
278
279 if (in->norderbys > 0)
280 {
281 MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
282
283 /* Use parent quadrant box as traversalValue */
284 BOX *quadrant = box_copy(bbox);
285
286 MemoryContextSwitchTo(oldCtx);
287
288 out->traversalValues[i] = quadrant;
289 out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
290 in->orderbys, in->norderbys);
291 }
292 }
293 PG_RETURN_VOID();
294 }
295
296 Assert(in->nNodes == 4);
297
298 /* "which" is a bitmask of quadrants that satisfy all constraints */
299 which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
300
301 for (i = 0; i < in->nkeys; i++)
302 {
303 Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
304 BOX *boxQuery;
305
306 switch (in->scankeys[i].sk_strategy)
307 {
308 case RTLeftStrategyNumber:
309 if (SPTEST(point_right, centroid, query))
310 which &= (1 << 3) | (1 << 4);
311 break;
312 case RTRightStrategyNumber:
313 if (SPTEST(point_left, centroid, query))
314 which &= (1 << 1) | (1 << 2);
315 break;
316 case RTSameStrategyNumber:
317 which &= (1 << getQuadrant(centroid, query));
318 break;
319 case RTBelowStrategyNumber:
320 case RTOldBelowStrategyNumber:
321 if (SPTEST(point_above, centroid, query))
322 which &= (1 << 2) | (1 << 3);
323 break;
324 case RTAboveStrategyNumber:
325 case RTOldAboveStrategyNumber:
326 if (SPTEST(point_below, centroid, query))
327 which &= (1 << 1) | (1 << 4);
328 break;
329 case RTContainedByStrategyNumber:
330
331 /*
332 * For this operator, the query is a box not a point. We
333 * cheat to the extent of assuming that DatumGetPointP won't
334 * do anything that would be bad for a pointer-to-box.
335 */
336 boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
337
338 if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
339 PointerGetDatum(boxQuery),
340 PointerGetDatum(centroid))))
341 {
342 /* centroid is in box, so all quadrants are OK */
343 }
344 else
345 {
346 /* identify quadrant(s) containing all corners of box */
347 Point p;
348 int r = 0;
349
350 p = boxQuery->low;
351 r |= 1 << getQuadrant(centroid, &p);
352 p.y = boxQuery->high.y;
353 r |= 1 << getQuadrant(centroid, &p);
354 p = boxQuery->high;
355 r |= 1 << getQuadrant(centroid, &p);
356 p.x = boxQuery->low.x;
357 r |= 1 << getQuadrant(centroid, &p);
358
359 which &= r;
360 }
361 break;
362 default:
363 elog(ERROR, "unrecognized strategy number: %d",
364 in->scankeys[i].sk_strategy);
365 break;
366 }
367
368 if (which == 0)
369 break; /* no need to consider remaining conditions */
370 }
371
372 out->levelAdds = palloc_array(int, 4);
373 for (i = 0; i < 4; ++i)
374 out->levelAdds[i] = 1;
375
376 /* We must descend into the quadrant(s) identified by which */
377 out->nodeNumbers = palloc_array(int, 4);
378 out->nNodes = 0;
379
380 for (i = 1; i <= 4; i++)
381 {
382 if (which & (1 << i))
383 {
384 out->nodeNumbers[out->nNodes] = i - 1;
385
386 if (in->norderbys > 0)
387 {
388 MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
389 BOX *quadrant = getQuadrantArea(bbox, centroid, i);
390
391 MemoryContextSwitchTo(oldCtx);
392
393 out->traversalValues[out->nNodes] = quadrant;
394
395 out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
396 in->orderbys, in->norderbys);
397 }
398
399 out->nNodes++;
400 }
401 }
402
403 PG_RETURN_VOID();
404}
405
406
407Datum
408spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
409{
410 spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
411 spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
412 Point *datum = DatumGetPointP(in->leafDatum);
413 bool res;
414 int i;
415
416 /* all tests are exact */
417 out->recheck = false;
418
419 /* leafDatum is what it is... */
420 out->leafValue = in->leafDatum;
421
422 /* Perform the required comparison(s) */
423 res = true;
424 for (i = 0; i < in->nkeys; i++)
425 {
426 Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
427
428 switch (in->scankeys[i].sk_strategy)
429 {
430 case RTLeftStrategyNumber:
431 res = SPTEST(point_left, datum, query);
432 break;
433 case RTRightStrategyNumber:
434 res = SPTEST(point_right, datum, query);
435 break;
436 case RTSameStrategyNumber:
437 res = SPTEST(point_eq, datum, query);
438 break;
439 case RTBelowStrategyNumber:
440 case RTOldBelowStrategyNumber:
441 res = SPTEST(point_below, datum, query);
442 break;
443 case RTAboveStrategyNumber:
444 case RTOldAboveStrategyNumber:
445 res = SPTEST(point_above, datum, query);
446 break;
447 case RTContainedByStrategyNumber:
448
449 /*
450 * For this operator, the query is a box not a point. We
451 * cheat to the extent of assuming that DatumGetPointP won't
452 * do anything that would be bad for a pointer-to-box.
453 */
454 res = SPTEST(box_contain_pt, query, datum);
455 break;
456 default:
457 elog(ERROR, "unrecognized strategy number: %d",
458 in->scankeys[i].sk_strategy);
459 break;
460 }
461
462 if (!res)
463 break;
464 }
465
466 if (res && in->norderbys > 0)
467 /* ok, it passes -> let's compute the distances */
468 out->distances = spg_key_orderbys_distances(in->leafDatum, true,
469 in->orderbys, in->norderbys);
470
471 PG_RETURN_BOOL(res);
472}
Assert
#define Assert(condition)
Definition c.h:873
ERROR
#define ERROR
Definition elog.h:39
elog
#define elog(elevel,...)
Definition elog.h:226
palloc_object
#define palloc_object(type)
Definition fe_memutils.h:74
palloc_array
#define palloc_array(type, count)
Definition fe_memutils.h:76
palloc0_object
#define palloc0_object(type)
Definition fe_memutils.h:75
get_float8_infinity
static float8 get_float8_infinity(void)
Definition float.h:65
PG_RETURN_VOID
#define PG_RETURN_VOID()
Definition fmgr.h:350
DirectFunctionCall2
#define DirectFunctionCall2(func, arg1, arg2)
Definition fmgr.h:686
PG_GETARG_POINTER
#define PG_GETARG_POINTER(n)
Definition fmgr.h:277
PG_FUNCTION_ARGS
#define PG_FUNCTION_ARGS
Definition fmgr.h:193
PG_RETURN_BOOL
#define PG_RETURN_BOOL(x)
Definition fmgr.h:360
DatumGetPointP
static Point * DatumGetPointP(Datum X)
Definition geo_decls.h:175
PointPGetDatum
static Datum PointPGetDatum(const Point *X)
Definition geo_decls.h:180
DatumGetBoxP
static BOX * DatumGetBoxP(Datum X)
Definition geo_decls.h:233
BoxPGetDatum
static Datum BoxPGetDatum(const BOX *X)
Definition geo_decls.h:238
point_eq
Datum point_eq(PG_FUNCTION_ARGS)
Definition geo_ops.c:1955
point_above
Datum point_above(PG_FUNCTION_ARGS)
Definition geo_ops.c:1919
box_contain_pt
Datum box_contain_pt(PG_FUNCTION_ARGS)
Definition geo_ops.c:3146
point_below
Datum point_below(PG_FUNCTION_ARGS)
Definition geo_ops.c:1928
point_horiz
Datum point_horiz(PG_FUNCTION_ARGS)
Definition geo_ops.c:1946
point_left
Datum point_left(PG_FUNCTION_ARGS)
Definition geo_ops.c:1901
point_right
Datum point_right(PG_FUNCTION_ARGS)
Definition geo_ops.c:1910
point_vert
Datum point_vert(PG_FUNCTION_ARGS)
Definition geo_ops.c:1937
b
int b
Definition isn.c:74
a
int a
Definition isn.c:73
i
int i
Definition isn.c:77
MemoryContextSwitchTo
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition palloc.h:124
arg
void * arg
Definition pg_backup_utils.c:29
qsort
#define qsort(a, b, c, d)
Definition port.h:495
DatumGetBool
static bool DatumGetBool(Datum X)
Definition postgres.h:100
PointerGetDatum
static Datum PointerGetDatum(const void *X)
Definition postgres.h:352
Datum
uint64_t Datum
Definition postgres.h:70
fb
static int fb(int x)
Definition preproc-init.c:92
spgMatchNode
@ spgMatchNode
Definition spgist.h:69
x_cmp
static int x_cmp(const void *a, const void *b)
Definition spgkdtreeproc.c:87
y_cmp
static int y_cmp(const void *a, const void *b)
Definition spgkdtreeproc.c:98
box_copy
BOX * box_copy(BOX *orig)
Definition spgproc.c:82
spg_key_orderbys_distances
double * spg_key_orderbys_distances(Datum key, bool isLeaf, ScanKey orderbys, int norderbys)
Definition spgproc.c:63
spg_quad_picksplit
Datum spg_quad_picksplit(PG_FUNCTION_ARGS)
Definition spgquadtreeproc.c:171
spg_quad_choose
Datum spg_quad_choose(PG_FUNCTION_ARGS)
Definition spgquadtreeproc.c:117
getQuadrant
static int16 getQuadrant(Point *centroid, Point *tst)
Definition spgquadtreeproc.c:57
spg_quad_leaf_consistent
Datum spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
Definition spgquadtreeproc.c:409
spg_quad_inner_consistent
Datum spg_quad_inner_consistent(PG_FUNCTION_ARGS)
Definition spgquadtreeproc.c:229
getQuadrantArea
static BOX * getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
Definition spgquadtreeproc.c:85
SPTEST
#define SPTEST(f, x, y)
Definition spgquadtreeproc.c:41
RTLeftStrategyNumber
#define RTLeftStrategyNumber
Definition stratnum.h:51
RTRightStrategyNumber
#define RTRightStrategyNumber
Definition stratnum.h:55
RTSameStrategyNumber
#define RTSameStrategyNumber
Definition stratnum.h:56
RTOldBelowStrategyNumber
#define RTOldBelowStrategyNumber
Definition stratnum.h:79
RTBelowStrategyNumber
#define RTBelowStrategyNumber
Definition stratnum.h:60
RTOldAboveStrategyNumber
#define RTOldAboveStrategyNumber
Definition stratnum.h:80
RTAboveStrategyNumber
#define RTAboveStrategyNumber
Definition stratnum.h:61
RTContainedByStrategyNumber
#define RTContainedByStrategyNumber
Definition stratnum.h:58
BOX::low
Point low
Definition geo_decls.h:142
BOX::high
Point high
Definition geo_decls.h:141
Point::y
float8 y
Definition geo_decls.h:98
Point::x
float8 x
Definition geo_decls.h:97
ScanKeyData::sk_argument
Datum sk_argument
Definition skey.h:72
ScanKeyData::sk_strategy
StrategyNumber sk_strategy
Definition skey.h:68
spgChooseIn::hasPrefix
bool hasPrefix
Definition spgist.h:61
spgChooseIn::prefixDatum
Datum prefixDatum
Definition spgist.h:62
spgChooseIn::nNodes
int nNodes
Definition spgist.h:63
spgChooseIn::datum
Datum datum
Definition spgist.h:55
spgChooseIn::allTheSame
bool allTheSame
Definition spgist.h:60
spgChooseOut::resultType
spgChooseResultType resultType
Definition spgist.h:76
spgChooseOut::levelAdd
int levelAdd
Definition spgist.h:82
spgChooseOut::restDatum
Datum restDatum
Definition spgist.h:83
spgChooseOut::nodeN
int nodeN
Definition spgist.h:81
spgChooseOut::result
union spgChooseOut::@54 result
spgChooseOut::matchNode
struct spgChooseOut::@54::@55 matchNode
spgInnerConsistentIn::traversalValue
void * traversalValue
Definition spgist.h:141
spgInnerConsistentIn::traversalMemoryContext
MemoryContext traversalMemoryContext
Definition spgist.h:142
spgInnerConsistentOut::traversalValues
void ** traversalValues
Definition spgist.h:160
spgInnerConsistentOut::distances
double ** distances
Definition spgist.h:161
spgLeafConsistentOut::distances
double * distances
Definition spgist.h:188
spgPickSplitIn::datums
Datum * datums
Definition spgist.h:113
spgPickSplitOut::mapTuplesToNodes
int * mapTuplesToNodes
Definition spgist.h:125
spgPickSplitOut::nodeLabels
Datum * nodeLabels
Definition spgist.h:123
spgPickSplitOut::leafTupleDatums
Datum * leafTupleDatums
Definition spgist.h:126
spgPickSplitOut::prefixDatum
Datum prefixDatum
Definition spgist.h:120

Function Documentation

◆ getQuadrant()

static int16 getQuadrant ( Point *  centroid,
Point *  tst 
)
static

Definition at line 57 of file spgquadtreeproc.c.

58{
59 if ((SPTEST(point_above, tst, centroid) ||
60 SPTEST(point_horiz, tst, centroid)) &&
61 (SPTEST(point_right, tst, centroid) ||
62 SPTEST(point_vert, tst, centroid)))
63 return 1;
64
65 if (SPTEST(point_below, tst, centroid) &&
66 (SPTEST(point_right, tst, centroid) ||
67 SPTEST(point_vert, tst, centroid)))
68 return 2;
69
70 if ((SPTEST(point_below, tst, centroid) ||
71 SPTEST(point_horiz, tst, centroid)) &&
72 SPTEST(point_left, tst, centroid))
73 return 3;
74
75 if (SPTEST(point_above, tst, centroid) &&
76 SPTEST(point_left, tst, centroid))
77 return 4;
78
79 elog(ERROR, "getQuadrant: impossible case");
80 return 0;
81}

References elog, ERROR, fb(), 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 85 of file spgquadtreeproc.c.

86{
87 BOX *result = palloc_object(BOX);
88
89 switch (quadrant)
90 {
91 case 1:
92 result->high = bbox->high;
93 result->low = *centroid;
94 break;
95 case 2:
96 result->high.x = bbox->high.x;
97 result->high.y = centroid->y;
98 result->low.x = centroid->x;
99 result->low.y = bbox->low.y;
100 break;
101 case 3:
102 result->high = *centroid;
103 result->low = bbox->low;
104 break;
105 case 4:
106 result->high.x = centroid->x;
107 result->high.y = bbox->high.y;
108 result->low.x = bbox->low.x;
109 result->low.y = centroid->y;
110 break;
111 }
112
113 return result;
114}

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

Referenced by spg_quad_inner_consistent().

◆ spg_quad_choose()

Datum spg_quad_choose ( PG_FUNCTION_ARGS  )

Definition at line 117 of file spgquadtreeproc.c.

118{
119 spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
120 spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
121 Point *inPoint = DatumGetPointP(in->datum),
122 *centroid;
123
124 if (in->allTheSame)
125 {
126 out->resultType = spgMatchNode;
127 /* nodeN will be set by core */
128 out->result.matchNode.levelAdd = 0;
129 out->result.matchNode.restDatum = PointPGetDatum(inPoint);
130 PG_RETURN_VOID();
131 }
132
133 Assert(in->hasPrefix);
134 centroid = DatumGetPointP(in->prefixDatum);
135
136 Assert(in->nNodes == 4);
137
138 out->resultType = spgMatchNode;
139 out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
140 out->result.matchNode.levelAdd = 0;
141 out->result.matchNode.restDatum = PointPGetDatum(inPoint);
142
143 PG_RETURN_VOID();
144}

References spgChooseIn::allTheSame, Assert, spgChooseIn::datum, DatumGetPointP(), fb(), 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#ifdef NOT_USED
30 spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0);
31#endif
32 spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
33
34 cfg->prefixType = POINTOID;
35 cfg->labelType = VOIDOID; /* we don't need node labels */
36 cfg->canReturnData = true;
37 cfg->longValuesOK = false;
38 PG_RETURN_VOID();
39}
spgConfigOut::longValuesOK
bool longValuesOK
Definition spgist.h:47
spgConfigOut::canReturnData
bool canReturnData
Definition spgist.h:46
spgConfigOut::labelType
Oid labelType
Definition spgist.h:44
spgConfigOut::prefixType
Oid prefixType
Definition spgist.h:43

References spgConfigOut::canReturnData, fb(), 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 229 of file spgquadtreeproc.c.

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

References spgInnerConsistentIn::allTheSame, Assert, box_contain_pt(), box_copy(), BoxPGetDatum(), DatumGetBool(), DatumGetBoxP(), DatumGetPointP(), DirectFunctionCall2, spgInnerConsistentOut::distances, elog, ERROR, fb(), get_float8_infinity(), getQuadrant(), getQuadrantArea(), spgInnerConsistentIn::hasPrefix, i, spgInnerConsistentIn::level, spgInnerConsistentOut::levelAdds, MemoryContextSwitchTo(), spgInnerConsistentIn::nkeys, spgInnerConsistentIn::nNodes, spgInnerConsistentOut::nNodes, spgInnerConsistentOut::nodeNumbers, spgInnerConsistentIn::norderbys, spgInnerConsistentIn::orderbys, palloc_array, 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 409 of file spgquadtreeproc.c.

410{
411 spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
412 spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
413 Point *datum = DatumGetPointP(in->leafDatum);
414 bool res;
415 int i;
416
417 /* all tests are exact */
418 out->recheck = false;
419
420 /* leafDatum is what it is... */
421 out->leafValue = in->leafDatum;
422
423 /* Perform the required comparison(s) */
424 res = true;
425 for (i = 0; i < in->nkeys; i++)
426 {
427 Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
428
429 switch (in->scankeys[i].sk_strategy)
430 {
431 case RTLeftStrategyNumber:
432 res = SPTEST(point_left, datum, query);
433 break;
434 case RTRightStrategyNumber:
435 res = SPTEST(point_right, datum, query);
436 break;
437 case RTSameStrategyNumber:
438 res = SPTEST(point_eq, datum, query);
439 break;
440 case RTBelowStrategyNumber:
441 case RTOldBelowStrategyNumber:
442 res = SPTEST(point_below, datum, query);
443 break;
444 case RTAboveStrategyNumber:
445 case RTOldAboveStrategyNumber:
446 res = SPTEST(point_above, datum, query);
447 break;
448 case RTContainedByStrategyNumber:
449
450 /*
451 * For this operator, the query is a box not a point. We
452 * cheat to the extent of assuming that DatumGetPointP won't
453 * do anything that would be bad for a pointer-to-box.
454 */
455 res = SPTEST(box_contain_pt, query, datum);
456 break;
457 default:
458 elog(ERROR, "unrecognized strategy number: %d",
459 in->scankeys[i].sk_strategy);
460 break;
461 }
462
463 if (!res)
464 break;
465 }
466
467 if (res && in->norderbys > 0)
468 /* ok, it passes -> let's compute the distances */
469 out->distances = spg_key_orderbys_distances(in->leafDatum, true,
470 in->orderbys, in->norderbys);
471
472 PG_RETURN_BOOL(res);
473}

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, 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 171 of file spgquadtreeproc.c.

172{
173 spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
174 spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
175 int i;
176 Point *centroid;
177
178#ifdef USE_MEDIAN
179 /* Use the median values of x and y as the centroid point */
180 Point **sorted;
181
182 sorted = palloc_array(Point *, in->nTuples);
183 for (i = 0; i < in->nTuples; i++)
184 sorted[i] = DatumGetPointP(in->datums[i]);
185
186 centroid = palloc_object(Point);
187
188 qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
189 centroid->x = sorted[in->nTuples >> 1]->x;
190 qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
191 centroid->y = sorted[in->nTuples >> 1]->y;
192#else
193 /* Use the average values of x and y as the centroid point */
194 centroid = palloc0_object(Point);
195
196 for (i = 0; i < in->nTuples; i++)
197 {
198 centroid->x += DatumGetPointP(in->datums[i])->x;
199 centroid->y += DatumGetPointP(in->datums[i])->y;
200 }
201
202 centroid->x /= in->nTuples;
203 centroid->y /= in->nTuples;
204#endif
205
206 out->hasPrefix = true;
207 out->prefixDatum = PointPGetDatum(centroid);
208
209 out->nNodes = 4;
210 out->nodeLabels = NULL; /* we don't need node labels */
211
212 out->mapTuplesToNodes = palloc_array(int, in->nTuples);
213 out->leafTupleDatums = palloc_array(Datum, in->nTuples);
214
215 for (i = 0; i < in->nTuples; i++)
216 {
217 Point *p = DatumGetPointP(in->datums[i]);
218 int quadrant = getQuadrant(centroid, p) - 1;
219
220 out->leafTupleDatums[i] = PointPGetDatum(p);
221 out->mapTuplesToNodes[i] = quadrant;
222 }
223
224 PG_RETURN_VOID();
225}

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