PostgreSQL Source Code  git master
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/builtins.h"
#include "utils/float.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.

References Point::x, and Point::y.

Referenced by spg_kd_choose().

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 }
float8 x
Definition: geo_decls.h:57
float8 y
Definition: geo_decls.h:57

◆ spg_kd_choose()

Datum spg_kd_choose ( PG_FUNCTION_ARGS  )

Definition at line 54 of file spgkdtreeproc.c.

References spgChooseIn::allTheSame, Assert, spgChooseIn::datum, DatumGetFloat8, DatumGetPointP, elog, ERROR, getSide(), spgChooseIn::hasPrefix, spgChooseIn::level, spgChooseOut::matchNode, spgChooseIn::nNodes, PG_GETARG_POINTER, PG_RETURN_VOID, PointPGetDatum, spgChooseIn::prefixDatum, spgChooseOut::result, spgChooseOut::resultType, and spgMatchNode.

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 
69  out->resultType = spgMatchNode;
70  out->result.matchNode.nodeN =
71  (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
72  out->result.matchNode.levelAdd = 1;
73  out->result.matchNode.restDatum = PointPGetDatum(inPoint);
74 
76 }
Datum datum
Definition: spgist.h:58
bool hasPrefix
Definition: spgist.h:64
int level
Definition: spgist.h:60
struct spgChooseOut::@48::@49 matchNode
Datum prefixDatum
Definition: spgist.h:65
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
#define ERROR
Definition: elog.h:43
int nNodes
Definition: spgist.h:66
#define DatumGetFloat8(X)
Definition: postgres.h:728
spgChooseResultType resultType
Definition: spgist.h:79
#define PG_RETURN_VOID()
Definition: fmgr.h:339
#define Assert(condition)
Definition: c.h:732
#define DatumGetPointP(X)
Definition: geo_decls.h:134
union spgChooseOut::@48 result
static int getSide(double coord, bool isX, Point *tst)
Definition: spgkdtreeproc.c:41
#define elog(elevel,...)
Definition: elog.h:226
bool allTheSame
Definition: spgist.h:63
#define PointPGetDatum(X)
Definition: geo_decls.h:135

◆ spg_kd_config()

Datum spg_kd_config ( PG_FUNCTION_ARGS  )

Definition at line 28 of file spgkdtreeproc.c.

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

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 canReturnData
Definition: spgist.h:49
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
bool longValuesOK
Definition: spgist.h:50
Oid prefixType
Definition: spgist.h:46
#define PG_RETURN_VOID()
Definition: fmgr.h:339
Oid labelType
Definition: spgist.h:47

◆ spg_kd_inner_consistent()

Datum spg_kd_inner_consistent ( PG_FUNCTION_ARGS  )

Definition at line 160 of file spgkdtreeproc.c.

References spgInnerConsistentIn::allTheSame, Assert, box_copy(), BoxPGetDatum, DatumGetBoxP, DatumGetFloat8, DatumGetPointP, spgInnerConsistentOut::distances, elog, ERROR, FPgt, FPlt, get_float8_infinity(), spgInnerConsistentIn::hasPrefix, BOX::high, SortedPoint::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, 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.

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  {
182  Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
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;
212  if ((in->level % 2) == 0 && FPlt(query->y, coord))
213  which &= (1 << 1);
214  break;
216  if ((in->level % 2) == 0 && FPgt(query->y, coord))
217  which &= (1 << 2);
218  break;
220 
221  /*
222  * For this operator, the query is a box not a point. We
223  * cheat to the extent of assuming that DatumGetPointP won't
224  * do anything that would be bad for a pointer-to-box.
225  */
226  boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
227 
228  if ((in->level % 2) != 0)
229  {
230  if (FPlt(boxQuery->high.x, coord))
231  which &= (1 << 1);
232  else if (FPgt(boxQuery->low.x, coord))
233  which &= (1 << 2);
234  }
235  else
236  {
237  if (FPlt(boxQuery->high.y, coord))
238  which &= (1 << 1);
239  else if (FPgt(boxQuery->low.y, coord))
240  which &= (1 << 2);
241  }
242  break;
243  default:
244  elog(ERROR, "unrecognized strategy number: %d",
245  in->scankeys[i].sk_strategy);
246  break;
247  }
248 
249  if (which == 0)
250  break; /* no need to consider remaining conditions */
251  }
252 
253  /* We must descend into the children identified by which */
254  out->nNodes = 0;
255 
256  /* Fast-path for no matching children */
257  if (!which)
258  PG_RETURN_VOID();
259 
260  out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
261 
262  /*
263  * When ordering scan keys are specified, we've to calculate distance for
264  * them. In order to do that, we need calculate bounding boxes for both
265  * children nodes. Calculation of those bounding boxes on non-zero level
266  * require knowledge of bounding box of upper node. So, we save bounding
267  * boxes to traversalValues.
268  */
269  if (in->norderbys > 0)
270  {
271  BOX infArea;
272  BOX *area;
273 
274  out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
275  out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
276 
277  if (in->level == 0)
278  {
279  float8 inf = get_float8_infinity();
280 
281  infArea.high.x = inf;
282  infArea.high.y = inf;
283  infArea.low.x = -inf;
284  infArea.low.y = -inf;
285  area = &infArea;
286  }
287  else
288  {
289  area = (BOX *) in->traversalValue;
290  Assert(area);
291  }
292 
293  bboxes[0].low = area->low;
294  bboxes[1].high = area->high;
295 
296  if (in->level % 2)
297  {
298  /* split box by x */
299  bboxes[0].high.x = bboxes[1].low.x = coord;
300  bboxes[0].high.y = area->high.y;
301  bboxes[1].low.y = area->low.y;
302  }
303  else
304  {
305  /* split box by y */
306  bboxes[0].high.y = bboxes[1].low.y = coord;
307  bboxes[0].high.x = area->high.x;
308  bboxes[1].low.x = area->low.x;
309  }
310  }
311 
312  for (i = 1; i <= 2; i++)
313  {
314  if (which & (1 << i))
315  {
316  out->nodeNumbers[out->nNodes] = i - 1;
317 
318  if (in->norderbys > 0)
319  {
321  BOX *box = box_copy(&bboxes[i - 1]);
322 
323  MemoryContextSwitchTo(oldCtx);
324 
325  out->traversalValues[out->nNodes] = box;
326 
327  out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(box), false,
328  in->orderbys, in->norderbys);
329  }
330 
331  out->nNodes++;
332  }
333  }
334 
335  /* Set up level increments, too */
336  out->levelAdds = (int *) palloc(sizeof(int) * 2);
337  out->levelAdds[0] = 1;
338  out->levelAdds[1] = 1;
339 
340  PG_RETURN_VOID();
341 }
Definition: geo_decls.h:99
static float8 get_float8_infinity(void)
Definition: float.h:90
float8 x
Definition: geo_decls.h:57
#define RTLeftStrategyNumber
Definition: stratnum.h:51
ScanKey orderbys
Definition: spgist.h:138
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * traversalValue
Definition: spgist.h:144
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define FPgt(A, B)
Definition: geo_decls.h:38
MemoryContext traversalMemoryContext
Definition: spgist.h:145
#define ERROR
Definition: elog.h:43
double float8
Definition: c.h:491
StrategyNumber sk_strategy
Definition: skey.h:68
#define RTSameStrategyNumber
Definition: stratnum.h:56
void ** traversalValues
Definition: spgist.h:163
Point low
Definition: geo_decls.h:101
#define DatumGetFloat8(X)
Definition: postgres.h:728
double ** distances
Definition: spgist.h:164
BOX * box_copy(BOX *orig)
Definition: spgproc.c:82
#define BoxPGetDatum(X)
Definition: geo_decls.h:157
#define PG_RETURN_VOID()
Definition: fmgr.h:339
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define FPlt(A, B)
Definition: geo_decls.h:36
#define Assert(condition)
Definition: c.h:732
float8 y
Definition: geo_decls.h:57
#define RTRightStrategyNumber
Definition: stratnum.h:55
#define DatumGetPointP(X)
Definition: geo_decls.h:134
ScanKey scankeys
Definition: spgist.h:137
#define DatumGetBoxP(X)
Definition: geo_decls.h:156
Point high
Definition: geo_decls.h:101
void * palloc(Size size)
Definition: mcxt.c:949
double * spg_key_orderbys_distances(Datum key, bool isLeaf, ScanKey orderbys, int norderbys)
Definition: spgproc.c:63
#define elog(elevel,...)
Definition: elog.h:226
int i
Datum sk_argument
Definition: skey.h:72

◆ spg_kd_picksplit()

Datum spg_kd_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 108 of file spgkdtreeproc.c.

References DatumGetPointP, spgPickSplitIn::datums, Float8GetDatum(), spgPickSplitOut::hasPrefix, 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, Point::x, x_cmp(), Point::y, and y_cmp().

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 
156  PG_RETURN_VOID();
157 }
Datum * leafTupleDatums
Definition: spgist.h:129
Datum * datums
Definition: spgist.h:116
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
Datum Float8GetDatum(float8 X)
Definition: fmgr.c:1723
Datum * nodeLabels
Definition: spgist.h:126
static int x_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:85
uintptr_t Datum
Definition: postgres.h:367
#define PG_RETURN_VOID()
Definition: fmgr.h:339
float8 y
Definition: geo_decls.h:57
#define DatumGetPointP(X)
Definition: geo_decls.h:134
bool hasPrefix
Definition: spgist.h:122
void * palloc(Size size)
Definition: mcxt.c:949
int i
int * mapTuplesToNodes
Definition: spgist.h:128
Datum prefixDatum
Definition: spgist.h:123
#define qsort(a, b, c, d)
Definition: port.h:492
#define PointPGetDatum(X)
Definition: geo_decls.h:135
static int y_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:96

◆ x_cmp()

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

Definition at line 85 of file spgkdtreeproc.c.

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

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

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 }
float8 x
Definition: geo_decls.h:57

◆ y_cmp()

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

Definition at line 96 of file spgkdtreeproc.c.

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

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

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 }
float8 y
Definition: geo_decls.h:57