1 /*-------------------------------------------------------------------------
2 *
3 * spgquadtreeproc.c
4 * implementation of quad 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/spgquadtreeproc.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_quad_config(PG_FUNCTION_ARGS)26 spg_quad_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 = POINTOID;
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 #define SPTEST(f, x, y) \
39 DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))
40
41 /*
42 * Determine which quadrant a point falls into, relative to the centroid.
43 *
44 * Quadrants are identified like this:
45 *
46 * 4 | 1
47 * ----+-----
48 * 3 | 2
49 *
50 * Points on one of the axes are taken to lie in the lowest-numbered
51 * adjacent quadrant.
52 */
53 static int16
getQuadrant(Point * centroid,Point * tst)54 getQuadrant(Point *centroid, Point *tst)
55 {
56 if ((SPTEST(point_above, tst, centroid) ||
57 SPTEST(point_horiz, tst, centroid)) &&
58 (SPTEST(point_right, tst, centroid) ||
59 SPTEST(point_vert, tst, centroid)))
60 return 1;
61
62 if (SPTEST(point_below, tst, centroid) &&
63 (SPTEST(point_right, tst, centroid) ||
64 SPTEST(point_vert, tst, centroid)))
65 return 2;
66
67 if ((SPTEST(point_below, tst, centroid) ||
68 SPTEST(point_horiz, tst, centroid)) &&
69 SPTEST(point_left, tst, centroid))
70 return 3;
71
72 if (SPTEST(point_above, tst, centroid) &&
73 SPTEST(point_left, tst, centroid))
74 return 4;
75
76 elog(ERROR, "getQuadrant: impossible case");
77 return 0;
78 }
79
80
81 Datum
spg_quad_choose(PG_FUNCTION_ARGS)82 spg_quad_choose(PG_FUNCTION_ARGS)
83 {
84 spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
85 spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
86 Point *inPoint = DatumGetPointP(in->datum),
87 *centroid;
88
89 if (in->allTheSame)
90 {
91 out->resultType = spgMatchNode;
92 /* nodeN will be set by core */
93 out->result.matchNode.levelAdd = 0;
94 out->result.matchNode.restDatum = PointPGetDatum(inPoint);
95 PG_RETURN_VOID();
96 }
97
98 Assert(in->hasPrefix);
99 centroid = DatumGetPointP(in->prefixDatum);
100
101 Assert(in->nNodes == 4);
102
103 out->resultType = spgMatchNode;
104 out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
105 out->result.matchNode.levelAdd = 0;
106 out->result.matchNode.restDatum = PointPGetDatum(inPoint);
107
108 PG_RETURN_VOID();
109 }
110
111 #ifdef USE_MEDIAN
112 static int
x_cmp(const void * a,const void * b,void * arg)113 x_cmp(const void *a, const void *b, void *arg)
114 {
115 Point *pa = *(Point **) a;
116 Point *pb = *(Point **) b;
117
118 if (pa->x == pb->x)
119 return 0;
120 return (pa->x > pb->x) ? 1 : -1;
121 }
122
123 static int
y_cmp(const void * a,const void * b,void * arg)124 y_cmp(const void *a, const void *b, void *arg)
125 {
126 Point *pa = *(Point **) a;
127 Point *pb = *(Point **) b;
128
129 if (pa->y == pb->y)
130 return 0;
131 return (pa->y > pb->y) ? 1 : -1;
132 }
133 #endif
134
135 Datum
spg_quad_picksplit(PG_FUNCTION_ARGS)136 spg_quad_picksplit(PG_FUNCTION_ARGS)
137 {
138 spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
139 spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
140 int i;
141 Point *centroid;
142
143 #ifdef USE_MEDIAN
144 /* Use the median values of x and y as the centroid point */
145 Point **sorted;
146
147 sorted = palloc(sizeof(*sorted) * in->nTuples);
148 for (i = 0; i < in->nTuples; i++)
149 sorted[i] = DatumGetPointP(in->datums[i]);
150
151 centroid = palloc(sizeof(*centroid));
152
153 qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
154 centroid->x = sorted[in->nTuples >> 1]->x;
155 qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
156 centroid->y = sorted[in->nTuples >> 1]->y;
157 #else
158 /* Use the average values of x and y as the centroid point */
159 centroid = palloc0(sizeof(*centroid));
160
161 for (i = 0; i < in->nTuples; i++)
162 {
163 centroid->x += DatumGetPointP(in->datums[i])->x;
164 centroid->y += DatumGetPointP(in->datums[i])->y;
165 }
166
167 centroid->x /= in->nTuples;
168 centroid->y /= in->nTuples;
169 #endif
170
171 out->hasPrefix = true;
172 out->prefixDatum = PointPGetDatum(centroid);
173
174 out->nNodes = 4;
175 out->nodeLabels = NULL; /* we don't need node labels */
176
177 out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
178 out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
179
180 for (i = 0; i < in->nTuples; i++)
181 {
182 Point *p = DatumGetPointP(in->datums[i]);
183 int quadrant = getQuadrant(centroid, p) - 1;
184
185 out->leafTupleDatums[i] = PointPGetDatum(p);
186 out->mapTuplesToNodes[i] = quadrant;
187 }
188
189 PG_RETURN_VOID();
190 }
191
192
193 Datum
spg_quad_inner_consistent(PG_FUNCTION_ARGS)194 spg_quad_inner_consistent(PG_FUNCTION_ARGS)
195 {
196 spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
197 spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
198 Point *centroid;
199 int which;
200 int i;
201
202 Assert(in->hasPrefix);
203 centroid = DatumGetPointP(in->prefixDatum);
204
205 if (in->allTheSame)
206 {
207 /* Report that all nodes should be visited */
208 out->nNodes = in->nNodes;
209 out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
210 for (i = 0; i < in->nNodes; i++)
211 out->nodeNumbers[i] = i;
212 PG_RETURN_VOID();
213 }
214
215 Assert(in->nNodes == 4);
216
217 /* "which" is a bitmask of quadrants that satisfy all constraints */
218 which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
219
220 for (i = 0; i < in->nkeys; i++)
221 {
222 Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
223 BOX *boxQuery;
224
225 switch (in->scankeys[i].sk_strategy)
226 {
227 case RTLeftStrategyNumber:
228 if (SPTEST(point_right, centroid, query))
229 which &= (1 << 3) | (1 << 4);
230 break;
231 case RTRightStrategyNumber:
232 if (SPTEST(point_left, centroid, query))
233 which &= (1 << 1) | (1 << 2);
234 break;
235 case RTSameStrategyNumber:
236 which &= (1 << getQuadrant(centroid, query));
237 break;
238 case RTBelowStrategyNumber:
239 if (SPTEST(point_above, centroid, query))
240 which &= (1 << 2) | (1 << 3);
241 break;
242 case RTAboveStrategyNumber:
243 if (SPTEST(point_below, centroid, query))
244 which &= (1 << 1) | (1 << 4);
245 break;
246 case RTContainedByStrategyNumber:
247
248 /*
249 * For this operator, the query is a box not a point. We
250 * cheat to the extent of assuming that DatumGetPointP won't
251 * do anything that would be bad for a pointer-to-box.
252 */
253 boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
254
255 if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
256 PointerGetDatum(boxQuery),
257 PointerGetDatum(centroid))))
258 {
259 /* centroid is in box, so all quadrants are OK */
260 }
261 else
262 {
263 /* identify quadrant(s) containing all corners of box */
264 Point p;
265 int r = 0;
266
267 p = boxQuery->low;
268 r |= 1 << getQuadrant(centroid, &p);
269 p.y = boxQuery->high.y;
270 r |= 1 << getQuadrant(centroid, &p);
271 p = boxQuery->high;
272 r |= 1 << getQuadrant(centroid, &p);
273 p.x = boxQuery->low.x;
274 r |= 1 << getQuadrant(centroid, &p);
275
276 which &= r;
277 }
278 break;
279 default:
280 elog(ERROR, "unrecognized strategy number: %d",
281 in->scankeys[i].sk_strategy);
282 break;
283 }
284
285 if (which == 0)
286 break; /* no need to consider remaining conditions */
287 }
288
289 /* We must descend into the quadrant(s) identified by which */
290 out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
291 out->nNodes = 0;
292 for (i = 1; i <= 4; i++)
293 {
294 if (which & (1 << i))
295 out->nodeNumbers[out->nNodes++] = i - 1;
296 }
297
298 PG_RETURN_VOID();
299 }
300
301
302 Datum
spg_quad_leaf_consistent(PG_FUNCTION_ARGS)303 spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
304 {
305 spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
306 spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
307 Point *datum = DatumGetPointP(in->leafDatum);
308 bool res;
309 int i;
310
311 /* all tests are exact */
312 out->recheck = false;
313
314 /* leafDatum is what it is... */
315 out->leafValue = in->leafDatum;
316
317 /* Perform the required comparison(s) */
318 res = true;
319 for (i = 0; i < in->nkeys; i++)
320 {
321 Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
322
323 switch (in->scankeys[i].sk_strategy)
324 {
325 case RTLeftStrategyNumber:
326 res = SPTEST(point_left, datum, query);
327 break;
328 case RTRightStrategyNumber:
329 res = SPTEST(point_right, datum, query);
330 break;
331 case RTSameStrategyNumber:
332 res = SPTEST(point_eq, datum, query);
333 break;
334 case RTBelowStrategyNumber:
335 res = SPTEST(point_below, datum, query);
336 break;
337 case RTAboveStrategyNumber:
338 res = SPTEST(point_above, datum, query);
339 break;
340 case RTContainedByStrategyNumber:
341
342 /*
343 * For this operator, the query is a box not a point. We
344 * cheat to the extent of assuming that DatumGetPointP won't
345 * do anything that would be bad for a pointer-to-box.
346 */
347 res = SPTEST(box_contain_pt, query, datum);
348 break;
349 default:
350 elog(ERROR, "unrecognized strategy number: %d",
351 in->scankeys[i].sk_strategy);
352 break;
353 }
354
355 if (!res)
356 break;
357 }
358
359 PG_RETURN_BOOL(res);
360 }
361