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

Function Documentation

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

Definition at line 39 of file spgkdtreeproc.c.

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

Referenced by spg_kd_choose().

40 {
41  double tstcoord = (isX) ? tst->x : tst->y;
42 
43  if (coord == tstcoord)
44  return 0;
45  else if (coord > tstcoord)
46  return 1;
47  else
48  return -1;
49 }
double y
Definition: geo_decls.h:60
double x
Definition: geo_decls.h:60
Datum spg_kd_choose ( PG_FUNCTION_ARGS  )

Definition at line 52 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.

53 {
56  Point *inPoint = DatumGetPointP(in->datum);
57  double coord;
58 
59  if (in->allTheSame)
60  elog(ERROR, "allTheSame should not occur for k-d trees");
61 
62  Assert(in->hasPrefix);
63  coord = DatumGetFloat8(in->prefixDatum);
64 
65  Assert(in->nNodes == 2);
66 
67  out->resultType = spgMatchNode;
68  out->result.matchNode.nodeN =
69  (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
70  out->result.matchNode.levelAdd = 1;
71  out->result.matchNode.restDatum = PointPGetDatum(inPoint);
72 
74 }
Datum datum
Definition: spgist.h:56
bool hasPrefix
Definition: spgist.h:62
int level
Definition: spgist.h:58
struct spgChooseOut::@48::@49 matchNode
Datum prefixDatum
Definition: spgist.h:63
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
#define ERROR
Definition: elog.h:43
int nNodes
Definition: spgist.h:64
#define DatumGetFloat8(X)
Definition: postgres.h:734
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
static int getSide(double coord, bool isX, Point *tst)
Definition: spgkdtreeproc.c:39
bool allTheSame
Definition: spgist.h:61
#define elog
Definition: elog.h:219
#define PointPGetDatum(X)
Definition: geo_decls.h:138
Datum spg_kd_config ( PG_FUNCTION_ARGS  )

Definition at line 26 of file spgkdtreeproc.c.

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

27 {
28  /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
30 
31  cfg->prefixType = FLOAT8OID;
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
bool longValuesOK
Definition: spgist.h:48
Oid prefixType
Definition: spgist.h:45
#define PG_RETURN_VOID()
Definition: fmgr.h:309
#define FLOAT8OID
Definition: pg_type.h:419
Oid labelType
Definition: spgist.h:46
Datum spg_kd_inner_consistent ( PG_FUNCTION_ARGS  )

Definition at line 158 of file spgkdtreeproc.c.

References spgInnerConsistentIn::allTheSame, Assert, DatumGetBoxP, DatumGetFloat8, DatumGetPointP, elog, ERROR, FPgt, FPlt, spgInnerConsistentIn::hasPrefix, BOX::high, i, spgInnerConsistentIn::level, spgInnerConsistentOut::levelAdds, BOX::low, spgInnerConsistentIn::nkeys, spgInnerConsistentIn::nNodes, spgInnerConsistentOut::nNodes, spgInnerConsistentOut::nodeNumbers, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, spgInnerConsistentIn::prefixDatum, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTLeftStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, spgInnerConsistentIn::scankeys, ScanKeyData::sk_argument, ScanKeyData::sk_strategy, Point::x, and Point::y.

159 {
162  double coord;
163  int which;
164  int i;
165 
166  Assert(in->hasPrefix);
167  coord = DatumGetFloat8(in->prefixDatum);
168 
169  if (in->allTheSame)
170  elog(ERROR, "allTheSame should not occur for k-d trees");
171 
172  Assert(in->nNodes == 2);
173 
174  /* "which" is a bitmask of children that satisfy all constraints */
175  which = (1 << 1) | (1 << 2);
176 
177  for (i = 0; i < in->nkeys; i++)
178  {
179  Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
180  BOX *boxQuery;
181 
182  switch (in->scankeys[i].sk_strategy)
183  {
185  if ((in->level % 2) != 0 && FPlt(query->x, coord))
186  which &= (1 << 1);
187  break;
189  if ((in->level % 2) != 0 && FPgt(query->x, coord))
190  which &= (1 << 2);
191  break;
193  if ((in->level % 2) != 0)
194  {
195  if (FPlt(query->x, coord))
196  which &= (1 << 1);
197  else if (FPgt(query->x, coord))
198  which &= (1 << 2);
199  }
200  else
201  {
202  if (FPlt(query->y, coord))
203  which &= (1 << 1);
204  else if (FPgt(query->y, coord))
205  which &= (1 << 2);
206  }
207  break;
209  if ((in->level % 2) == 0 && FPlt(query->y, coord))
210  which &= (1 << 1);
211  break;
213  if ((in->level % 2) == 0 && FPgt(query->y, coord))
214  which &= (1 << 2);
215  break;
217 
218  /*
219  * For this operator, the query is a box not a point. We
220  * cheat to the extent of assuming that DatumGetPointP won't
221  * do anything that would be bad for a pointer-to-box.
222  */
223  boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
224 
225  if ((in->level % 2) != 0)
226  {
227  if (FPlt(boxQuery->high.x, coord))
228  which &= (1 << 1);
229  else if (FPgt(boxQuery->low.x, coord))
230  which &= (1 << 2);
231  }
232  else
233  {
234  if (FPlt(boxQuery->high.y, coord))
235  which &= (1 << 1);
236  else if (FPgt(boxQuery->low.y, coord))
237  which &= (1 << 2);
238  }
239  break;
240  default:
241  elog(ERROR, "unrecognized strategy number: %d",
242  in->scankeys[i].sk_strategy);
243  break;
244  }
245 
246  if (which == 0)
247  break; /* no need to consider remaining conditions */
248  }
249 
250  /* We must descend into the children identified by which */
251  out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
252  out->nNodes = 0;
253  for (i = 1; i <= 2; i++)
254  {
255  if (which & (1 << i))
256  out->nodeNumbers[out->nNodes++] = i - 1;
257  }
258 
259  /* Set up level increments, too */
260  out->levelAdds = (int *) palloc(sizeof(int) * 2);
261  out->levelAdds[0] = 1;
262  out->levelAdds[1] = 1;
263 
264  PG_RETURN_VOID();
265 }
Definition: geo_decls.h:102
#define RTLeftStrategyNumber
Definition: stratnum.h:44
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
#define FPgt(A, B)
Definition: geo_decls.h:41
#define ERROR
Definition: elog.h:43
StrategyNumber sk_strategy
Definition: skey.h:68
#define RTSameStrategyNumber
Definition: stratnum.h:49
Point low
Definition: geo_decls.h:104
#define DatumGetFloat8(X)
Definition: postgres.h:734
#define PG_RETURN_VOID()
Definition: fmgr.h:309
#define RTAboveStrategyNumber
Definition: stratnum.h:54
#define FPlt(A, B)
Definition: geo_decls.h:39
#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
#define elog
Definition: elog.h:219
Datum sk_argument
Definition: skey.h:72
Datum spg_kd_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 106 of file spgkdtreeproc.c.

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

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

Definition at line 83 of file spgkdtreeproc.c.

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

Referenced by spg_kd_picksplit(), and spg_quad_picksplit().

84 {
85  SortedPoint *pa = (SortedPoint *) a;
86  SortedPoint *pb = (SortedPoint *) b;
87 
88  if (pa->p->x == pb->p->x)
89  return 0;
90  return (pa->p->x > pb->p->x) ? 1 : -1;
91 }
double x
Definition: geo_decls.h:60
static int y_cmp ( const void *  a,
const void *  b 
)
static

Definition at line 94 of file spgkdtreeproc.c.

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

Referenced by spg_kd_picksplit(), and spg_quad_picksplit().

95 {
96  SortedPoint *pa = (SortedPoint *) a;
97  SortedPoint *pb = (SortedPoint *) b;
98 
99  if (pa->p->y == pb->p->y)
100  return 0;
101  return (pa->p->y > pb->p->y) ? 1 : -1;
102 }
double y
Definition: geo_decls.h:60