PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
spgkdtreeproc.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 spgkdtreeproc.c:

Go to the source code of this file.

Data Structures

struct  SortedPoint
 

Typedefs

typedef struct SortedPoint SortedPoint
 

Functions

Datum spg_kd_config (PG_FUNCTION_ARGS)
 
static int getSide (double coord, bool isX, Point *tst)
 
Datum spg_kd_choose (PG_FUNCTION_ARGS)
 
static int x_cmp (const void *a, const void *b)
 
static int y_cmp (const void *a, const void *b)
 
Datum spg_kd_picksplit (PG_FUNCTION_ARGS)
 
Datum spg_kd_inner_consistent (PG_FUNCTION_ARGS)
 

Typedef Documentation

◆ SortedPoint

typedef struct SortedPoint SortedPoint

Function Documentation

◆ getSide()

static int getSide ( double  coord,
bool  isX,
Point tst 
)
static

Definition at line 41 of file spgkdtreeproc.c.

42{
43 double tstcoord = (isX) ? tst->x : tst->y;
44
45 if (coord == tstcoord)
46 return 0;
47 else if (coord > tstcoord)
48 return 1;
49 else
50 return -1;
51}
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:76
float8 y
Definition: geo_decls.h:99
float8 x
Definition: geo_decls.h:98

References if(), Point::x, and Point::y.

Referenced by spg_kd_choose().

◆ spg_kd_choose()

Datum spg_kd_choose ( PG_FUNCTION_ARGS  )

Definition at line 54 of file spgkdtreeproc.c.

55{
58 Point *inPoint = DatumGetPointP(in->datum);
59 double coord;
60
61 if (in->allTheSame)
62 elog(ERROR, "allTheSame should not occur for k-d trees");
63
64 Assert(in->hasPrefix);
65 coord = DatumGetFloat8(in->prefixDatum);
66
67 Assert(in->nNodes == 2);
68
71 (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
72 out->result.matchNode.levelAdd = 1;
74
76}
#define Assert(condition)
Definition: c.h:812
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#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
static float8 DatumGetFloat8(Datum X)
Definition: postgres.h:494
@ spgMatchNode
Definition: spgist.h:69
static int getSide(double coord, bool isX, Point *tst)
Definition: spgkdtreeproc.c:41
bool hasPrefix
Definition: spgist.h:61
Datum prefixDatum
Definition: spgist.h:62
int nNodes
Definition: spgist.h:63
Datum datum
Definition: spgist.h:55
int level
Definition: spgist.h:57
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, DatumGetFloat8(), DatumGetPointP(), elog, ERROR, getSide(), spgChooseIn::hasPrefix, spgChooseIn::level, 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_kd_config()

Datum spg_kd_config ( PG_FUNCTION_ARGS  )

Definition at line 28 of file spgkdtreeproc.c.

29{
30 /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
32
33 cfg->prefixType = FLOAT8OID;
34 cfg->labelType = VOIDOID; /* we don't need node labels */
35 cfg->canReturnData = true;
36 cfg->longValuesOK = false;
38}
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_kd_inner_consistent()

Datum spg_kd_inner_consistent ( PG_FUNCTION_ARGS  )

Definition at line 160 of file spgkdtreeproc.c.

161{
164 double coord;
165 int which;
166 int i;
167 BOX bboxes[2];
168
169 Assert(in->hasPrefix);
170 coord = DatumGetFloat8(in->prefixDatum);
171
172 if (in->allTheSame)
173 elog(ERROR, "allTheSame should not occur for k-d trees");
174
175 Assert(in->nNodes == 2);
176
177 /* "which" is a bitmask of children that satisfy all constraints */
178 which = (1 << 1) | (1 << 2);
179
180 for (i = 0; i < in->nkeys; i++)
181 {
183 BOX *boxQuery;
184
185 switch (in->scankeys[i].sk_strategy)
186 {
188 if ((in->level % 2) != 0 && FPlt(query->x, coord))
189 which &= (1 << 1);
190 break;
192 if ((in->level % 2) != 0 && FPgt(query->x, coord))
193 which &= (1 << 2);
194 break;
196 if ((in->level % 2) != 0)
197 {
198 if (FPlt(query->x, coord))
199 which &= (1 << 1);
200 else if (FPgt(query->x, coord))
201 which &= (1 << 2);
202 }
203 else
204 {
205 if (FPlt(query->y, coord))
206 which &= (1 << 1);
207 else if (FPgt(query->y, coord))
208 which &= (1 << 2);
209 }
210 break;
213 if ((in->level % 2) == 0 && FPlt(query->y, coord))
214 which &= (1 << 1);
215 break;
218 if ((in->level % 2) == 0 && FPgt(query->y, coord))
219 which &= (1 << 2);
220 break;
222
223 /*
224 * For this operator, the query is a box not a point. We
225 * cheat to the extent of assuming that DatumGetPointP won't
226 * do anything that would be bad for a pointer-to-box.
227 */
228 boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
229
230 if ((in->level % 2) != 0)
231 {
232 if (FPlt(boxQuery->high.x, coord))
233 which &= (1 << 1);
234 else if (FPgt(boxQuery->low.x, coord))
235 which &= (1 << 2);
236 }
237 else
238 {
239 if (FPlt(boxQuery->high.y, coord))
240 which &= (1 << 1);
241 else if (FPgt(boxQuery->low.y, coord))
242 which &= (1 << 2);
243 }
244 break;
245 default:
246 elog(ERROR, "unrecognized strategy number: %d",
247 in->scankeys[i].sk_strategy);
248 break;
249 }
250
251 if (which == 0)
252 break; /* no need to consider remaining conditions */
253 }
254
255 /* We must descend into the children identified by which */
256 out->nNodes = 0;
257
258 /* Fast-path for no matching children */
259 if (!which)
261
262 out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
263
264 /*
265 * When ordering scan keys are specified, we've to calculate distance for
266 * them. In order to do that, we need calculate bounding boxes for both
267 * children nodes. Calculation of those bounding boxes on non-zero level
268 * require knowledge of bounding box of upper node. So, we save bounding
269 * boxes to traversalValues.
270 */
271 if (in->norderbys > 0)
272 {
273 BOX infArea;
274 BOX *area;
275
276 out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
277 out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
278
279 if (in->level == 0)
280 {
282
283 infArea.high.x = inf;
284 infArea.high.y = inf;
285 infArea.low.x = -inf;
286 infArea.low.y = -inf;
287 area = &infArea;
288 }
289 else
290 {
291 area = (BOX *) in->traversalValue;
292 Assert(area);
293 }
294
295 bboxes[0].low = area->low;
296 bboxes[1].high = area->high;
297
298 if (in->level % 2)
299 {
300 /* split box by x */
301 bboxes[0].high.x = bboxes[1].low.x = coord;
302 bboxes[0].high.y = area->high.y;
303 bboxes[1].low.y = area->low.y;
304 }
305 else
306 {
307 /* split box by y */
308 bboxes[0].high.y = bboxes[1].low.y = coord;
309 bboxes[0].high.x = area->high.x;
310 bboxes[1].low.x = area->low.x;
311 }
312 }
313
314 for (i = 1; i <= 2; i++)
315 {
316 if (which & (1 << i))
317 {
318 out->nodeNumbers[out->nNodes] = i - 1;
319
320 if (in->norderbys > 0)
321 {
323 BOX *box = box_copy(&bboxes[i - 1]);
324
325 MemoryContextSwitchTo(oldCtx);
326
327 out->traversalValues[out->nNodes] = box;
328
330 in->orderbys, in->norderbys);
331 }
332
333 out->nNodes++;
334 }
335 }
336
337 /* Set up level increments, too */
338 out->levelAdds = (int *) palloc(sizeof(int) * 2);
339 out->levelAdds[0] = 1;
340 out->levelAdds[1] = 1;
341
343}
double float8
Definition: c.h:584
static float8 get_float8_infinity(void)
Definition: float.h:94
static bool FPlt(double A, double B)
Definition: geo_decls.h:59
static BOX * DatumGetBoxP(Datum X)
Definition: geo_decls.h:234
static bool FPgt(double A, double B)
Definition: geo_decls.h:71
static Datum BoxPGetDatum(const BOX *X)
Definition: geo_decls.h:239
int i
Definition: isn.c:72
void * palloc(Size size)
Definition: mcxt.c:1317
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
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
#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
Definition: geo_decls.h:141
Point low
Definition: geo_decls.h:143
Point high
Definition: geo_decls.h:142
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_copy(), BoxPGetDatum(), DatumGetBoxP(), DatumGetFloat8(), DatumGetPointP(), spgInnerConsistentOut::distances, elog, ERROR, FPgt(), FPlt(), get_float8_infinity(), 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, spgInnerConsistentIn::prefixDatum, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTLeftStrategyNumber, RTOldAboveStrategyNumber, RTOldBelowStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, spgInnerConsistentIn::scankeys, ScanKeyData::sk_argument, ScanKeyData::sk_strategy, spg_key_orderbys_distances(), spgInnerConsistentIn::traversalMemoryContext, spgInnerConsistentIn::traversalValue, spgInnerConsistentOut::traversalValues, Point::x, and Point::y.

◆ spg_kd_picksplit()

Datum spg_kd_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 108 of file spgkdtreeproc.c.

109{
112 int i;
113 int middle;
114 SortedPoint *sorted;
115 double coord;
116
117 sorted = palloc(sizeof(*sorted) * in->nTuples);
118 for (i = 0; i < in->nTuples; i++)
119 {
120 sorted[i].p = DatumGetPointP(in->datums[i]);
121 sorted[i].i = i;
122 }
123
124 qsort(sorted, in->nTuples, sizeof(*sorted),
125 (in->level % 2) ? x_cmp : y_cmp);
126 middle = in->nTuples >> 1;
127 coord = (in->level % 2) ? sorted[middle].p->x : sorted[middle].p->y;
128
129 out->hasPrefix = true;
130 out->prefixDatum = Float8GetDatum(coord);
131
132 out->nNodes = 2;
133 out->nodeLabels = NULL; /* we don't need node labels */
134
135 out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
136 out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
137
138 /*
139 * Note: points that have coordinates exactly equal to coord may get
140 * classified into either node, depending on where they happen to fall in
141 * the sorted list. This is okay as long as the inner_consistent function
142 * descends into both sides for such cases. This is better than the
143 * alternative of trying to have an exact boundary, because it keeps the
144 * tree balanced even when we have many instances of the same point value.
145 * So we should never trigger the allTheSame logic.
146 */
147 for (i = 0; i < in->nTuples; i++)
148 {
149 Point *p = sorted[i].p;
150 int n = sorted[i].i;
151
152 out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
153 out->leafTupleDatums[n] = PointPGetDatum(p);
154 }
155
157}
Datum Float8GetDatum(float8 X)
Definition: fmgr.c:1816
#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, Float8GetDatum(), spgPickSplitOut::hasPrefix, i, SortedPoint::i, spgPickSplitOut::leafTupleDatums, spgPickSplitIn::level, spgPickSplitOut::mapTuplesToNodes, spgPickSplitOut::nNodes, spgPickSplitOut::nodeLabels, spgPickSplitIn::nTuples, SortedPoint::p, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, PointPGetDatum(), spgPickSplitOut::prefixDatum, qsort, x_cmp(), Point::y, and y_cmp().

◆ x_cmp()

static int x_cmp ( const void *  a,
const void *  b 
)
static

Definition at line 85 of file spgkdtreeproc.c.

86{
87 SortedPoint *pa = (SortedPoint *) a;
88 SortedPoint *pb = (SortedPoint *) b;
89
90 if (pa->p->x == pb->p->x)
91 return 0;
92 return (pa->p->x > pb->p->x) ? 1 : -1;
93}
int b
Definition: isn.c:69
int a
Definition: isn.c:68

References a, b, SortedPoint::p, and Point::x.

Referenced by spg_kd_picksplit(), and spg_quad_picksplit().

◆ y_cmp()

static int y_cmp ( const void *  a,
const void *  b 
)
static

Definition at line 96 of file spgkdtreeproc.c.

97{
98 SortedPoint *pa = (SortedPoint *) a;
99 SortedPoint *pb = (SortedPoint *) b;
100
101 if (pa->p->y == pb->p->y)
102 return 0;
103 return (pa->p->y > pb->p->y) ? 1 : -1;
104}

References a, b, SortedPoint::p, and Point::y.

Referenced by spg_kd_picksplit(), and spg_quad_picksplit().