PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
spgkdtreeproc.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * spgkdtreeproc.c
4  * implementation of k-d tree over points for SP-GiST
5  *
6  *
7  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * IDENTIFICATION
11  * src/backend/access/spgist/spgkdtreeproc.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 
16 #include "postgres.h"
17 
18 #include "access/spgist.h"
19 #include "access/stratnum.h"
20 #include "catalog/pg_type.h"
21 #include "utils/builtins.h"
22 #include "utils/geo_decls.h"
23 
24 
25 Datum
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 }
37 
38 static int
39 getSide(double coord, bool isX, Point *tst)
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 }
50 
51 Datum
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 }
75 
76 typedef struct SortedPoint
77 {
78  Point *p;
79  int i;
80 } SortedPoint;
81 
82 static int
83 x_cmp(const void *a, const void *b)
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 }
92 
93 static int
94 y_cmp(const void *a, const void *b)
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 }
103 
104 
105 Datum
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 }
156 
157 Datum
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 }
266 
267 /*
268  * spg_kd_leaf_consistent() is the same as spg_quad_leaf_consistent(),
269  * since we support the same operators and the same leaf data type.
270  * So we just borrow that function.
271  */
Definition: geo_decls.h:102
Datum datum
Definition: spgist.h:56
bool hasPrefix
Definition: spgist.h:62
int level
Definition: spgist.h:58
bool canReturnData
Definition: spgist.h:47
Datum * leafTupleDatums
Definition: spgist.h:127
#define RTLeftStrategyNumber
Definition: stratnum.h:44
Datum * datums
Definition: spgist.h:114
struct spgChooseOut::@48::@49 matchNode
Datum spg_kd_inner_consistent(PG_FUNCTION_ARGS)
double y
Definition: geo_decls.h:60
Datum prefixDatum
Definition: spgist.h:63
Datum spg_kd_choose(PG_FUNCTION_ARGS)
Definition: spgkdtreeproc.c:52
#define RTContainedByStrategyNumber
Definition: stratnum.h:51
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
Datum spg_kd_config(PG_FUNCTION_ARGS)
Definition: spgkdtreeproc.c:26
#define RTBelowStrategyNumber
Definition: stratnum.h:53
Datum Float8GetDatum(float8 X)
Definition: fmgr.c:1810
double x
Definition: geo_decls.h:60
#define FPgt(A, B)
Definition: geo_decls.h:41
#define VOIDOID
Definition: pg_type.h:690
#define ERROR
Definition: elog.h:43
Datum * nodeLabels
Definition: spgist.h:124
StrategyNumber sk_strategy
Definition: skey.h:68
#define RTSameStrategyNumber
Definition: stratnum.h:49
static int x_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:83
int nNodes
Definition: spgist.h:64
Point low
Definition: geo_decls.h:104
#define DatumGetFloat8(X)
Definition: postgres.h:734
bool longValuesOK
Definition: spgist.h:48
uintptr_t Datum
Definition: postgres.h:372
Oid prefixType
Definition: spgist.h:45
spgChooseResultType resultType
Definition: spgist.h:77
#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:681
#define RTRightStrategyNumber
Definition: stratnum.h:48
#define DatumGetPointP(X)
Definition: geo_decls.h:137
bool hasPrefix
Definition: spgist.h:120
#define FLOAT8OID
Definition: pg_type.h:419
union spgChooseOut::@48 result
ScanKey scankeys
Definition: spgist.h:135
#define DatumGetBoxP(X)
Definition: geo_decls.h:159
Datum spg_kd_picksplit(PG_FUNCTION_ARGS)
struct SortedPoint SortedPoint
Point high
Definition: geo_decls.h:104
static int getSide(double coord, bool isX, Point *tst)
Definition: spgkdtreeproc.c:39
void * palloc(Size size)
Definition: mcxt.c:848
Oid labelType
Definition: spgist.h:46
int i
int * mapTuplesToNodes
Definition: spgist.h:126
bool allTheSame
Definition: spgist.h:61
Datum prefixDatum
Definition: spgist.h:121
#define PG_FUNCTION_ARGS
Definition: fmgr.h:158
#define elog
Definition: elog.h:219
#define qsort(a, b, c, d)
Definition: port.h:447
Datum sk_argument
Definition: skey.h:72
#define PointPGetDatum(X)
Definition: geo_decls.h:138
static int y_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:94