1 /*-------------------------------------------------------------------------
2 *
3 * spgkdtreeproc.c
4 * implementation of k-d tree over points for SP-GiST
5 *
6 *
7 * Portions Copyright (c) 1996-2016, 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
spg_kd_config(PG_FUNCTION_ARGS)26 spg_kd_config(PG_FUNCTION_ARGS)
27 {
28 /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
29 spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
30
31 cfg->prefixType = FLOAT8OID;
32 cfg->labelType = VOIDOID; /* we don't need node labels */
33 cfg->canReturnData = true;
34 cfg->longValuesOK = false;
35 PG_RETURN_VOID();
36 }
37
38 static int
getSide(double coord,bool isX,Point * tst)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
spg_kd_choose(PG_FUNCTION_ARGS)52 spg_kd_choose(PG_FUNCTION_ARGS)
53 {
54 spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
55 spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
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
73 PG_RETURN_VOID();
74 }
75
76 typedef struct SortedPoint
77 {
78 Point *p;
79 int i;
80 } SortedPoint;
81
82 static int
x_cmp(const void * a,const void * b)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
y_cmp(const void * a,const void * b)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
spg_kd_picksplit(PG_FUNCTION_ARGS)106 spg_kd_picksplit(PG_FUNCTION_ARGS)
107 {
108 spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
109 spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
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
spg_kd_inner_consistent(PG_FUNCTION_ARGS)158 spg_kd_inner_consistent(PG_FUNCTION_ARGS)
159 {
160 spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
161 spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
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 {
184 case RTLeftStrategyNumber:
185 if ((in->level % 2) != 0 && FPlt(query->x, coord))
186 which &= (1 << 1);
187 break;
188 case RTRightStrategyNumber:
189 if ((in->level % 2) != 0 && FPgt(query->x, coord))
190 which &= (1 << 2);
191 break;
192 case RTSameStrategyNumber:
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;
208 case RTBelowStrategyNumber:
209 if ((in->level % 2) == 0 && FPlt(query->y, coord))
210 which &= (1 << 1);
211 break;
212 case RTAboveStrategyNumber:
213 if ((in->level % 2) == 0 && FPgt(query->y, coord))
214 which &= (1 << 2);
215 break;
216 case RTContainedByStrategyNumber:
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 */
272