Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * spgquadtreeproc.c
4 : * implementation of quad 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/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
26 9 : spg_quad_config(PG_FUNCTION_ARGS)
27 : {
28 : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
29 9 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
30 :
31 9 : cfg->prefixType = POINTOID;
32 9 : cfg->labelType = VOIDOID; /* we don't need node labels */
33 9 : cfg->canReturnData = true;
34 9 : cfg->longValuesOK = false;
35 9 : 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
54 1242137 : getQuadrant(Point *centroid, Point *tst)
55 : {
56 1270249 : if ((SPTEST(point_above, tst, centroid) ||
57 1242912 : SPTEST(point_horiz, tst, centroid)) &&
58 1242634 : (SPTEST(point_right, tst, centroid) ||
59 27834 : SPTEST(point_vert, tst, centroid)))
60 1187741 : return 1;
61 :
62 81733 : if (SPTEST(point_below, tst, centroid) &&
63 51911 : (SPTEST(point_right, tst, centroid) ||
64 24574 : SPTEST(point_vert, tst, centroid)))
65 2763 : return 2;
66 :
67 78692 : if ((SPTEST(point_below, tst, centroid) ||
68 51633 : SPTEST(point_horiz, tst, centroid)) &&
69 24574 : SPTEST(point_left, tst, centroid))
70 24574 : return 3;
71 :
72 54118 : if (SPTEST(point_above, tst, centroid) &&
73 27059 : SPTEST(point_left, tst, centroid))
74 27059 : return 4;
75 :
76 0 : elog(ERROR, "getQuadrant: impossible case");
77 : return 0;
78 : }
79 :
80 :
81 : Datum
82 1211164 : spg_quad_choose(PG_FUNCTION_ARGS)
83 : {
84 1211164 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
85 1211164 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
86 1211164 : Point *inPoint = DatumGetPointP(in->datum),
87 : *centroid;
88 :
89 1211164 : if (in->allTheSame)
90 : {
91 844 : out->resultType = spgMatchNode;
92 : /* nodeN will be set by core */
93 844 : out->result.matchNode.levelAdd = 0;
94 844 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
95 844 : PG_RETURN_VOID();
96 : }
97 :
98 1210320 : Assert(in->hasPrefix);
99 1210320 : centroid = DatumGetPointP(in->prefixDatum);
100 :
101 1210320 : Assert(in->nNodes == 4);
102 :
103 1210320 : out->resultType = spgMatchNode;
104 1210320 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
105 1210320 : out->result.matchNode.levelAdd = 0;
106 1210320 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
107 :
108 1210320 : PG_RETURN_VOID();
109 : }
110 :
111 : #ifdef USE_MEDIAN
112 : static int
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
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
136 188 : spg_quad_picksplit(PG_FUNCTION_ARGS)
137 : {
138 188 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
139 188 : 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 188 : centroid = palloc0(sizeof(*centroid));
160 :
161 31935 : for (i = 0; i < in->nTuples; i++)
162 : {
163 31747 : centroid->x += DatumGetPointP(in->datums[i])->x;
164 31747 : centroid->y += DatumGetPointP(in->datums[i])->y;
165 : }
166 :
167 188 : centroid->x /= in->nTuples;
168 188 : centroid->y /= in->nTuples;
169 : #endif
170 :
171 188 : out->hasPrefix = true;
172 188 : out->prefixDatum = PointPGetDatum(centroid);
173 :
174 188 : out->nNodes = 4;
175 188 : out->nodeLabels = NULL; /* we don't need node labels */
176 :
177 188 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
178 188 : out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
179 :
180 31935 : for (i = 0; i < in->nTuples; i++)
181 : {
182 31747 : Point *p = DatumGetPointP(in->datums[i]);
183 31747 : int quadrant = getQuadrant(centroid, p) - 1;
184 :
185 31747 : out->leafTupleDatums[i] = PointPGetDatum(p);
186 31747 : out->mapTuplesToNodes[i] = quadrant;
187 : }
188 :
189 188 : PG_RETURN_VOID();
190 : }
191 :
192 :
193 : Datum
194 756 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
195 : {
196 756 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
197 756 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
198 : Point *centroid;
199 : int which;
200 : int i;
201 :
202 756 : Assert(in->hasPrefix);
203 756 : centroid = DatumGetPointP(in->prefixDatum);
204 :
205 756 : if (in->allTheSame)
206 : {
207 : /* Report that all nodes should be visited */
208 60 : out->nNodes = in->nNodes;
209 60 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
210 540 : for (i = 0; i < in->nNodes; i++)
211 480 : out->nodeNumbers[i] = i;
212 60 : PG_RETURN_VOID();
213 : }
214 :
215 696 : Assert(in->nNodes == 4);
216 :
217 : /* "which" is a bitmask of quadrants that satisfy all constraints */
218 696 : which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
219 :
220 1128 : for (i = 0; i < in->nkeys; i++)
221 : {
222 432 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
223 : BOX *boxQuery;
224 :
225 432 : switch (in->scankeys[i].sk_strategy)
226 : {
227 : case RTLeftStrategyNumber:
228 68 : if (SPTEST(point_right, centroid, query))
229 2 : which &= (1 << 3) | (1 << 4);
230 68 : break;
231 : case RTRightStrategyNumber:
232 76 : if (SPTEST(point_left, centroid, query))
233 10 : which &= (1 << 1) | (1 << 2);
234 76 : break;
235 : case RTSameStrategyNumber:
236 6 : which &= (1 << getQuadrant(centroid, query));
237 6 : break;
238 : case RTBelowStrategyNumber:
239 130 : if (SPTEST(point_above, centroid, query))
240 64 : which &= (1 << 2) | (1 << 3);
241 130 : break;
242 : case RTAboveStrategyNumber:
243 128 : if (SPTEST(point_below, centroid, query))
244 62 : which &= (1 << 1) | (1 << 4);
245 128 : 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 24 : boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
254 :
255 24 : 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 16 : int r = 0;
266 :
267 16 : p = boxQuery->low;
268 16 : r |= 1 << getQuadrant(centroid, &p);
269 16 : p.y = boxQuery->high.y;
270 16 : r |= 1 << getQuadrant(centroid, &p);
271 16 : p = boxQuery->high;
272 16 : r |= 1 << getQuadrant(centroid, &p);
273 16 : p.x = boxQuery->low.x;
274 16 : r |= 1 << getQuadrant(centroid, &p);
275 :
276 16 : which &= r;
277 : }
278 24 : break;
279 : default:
280 0 : elog(ERROR, "unrecognized strategy number: %d",
281 : in->scankeys[i].sk_strategy);
282 : break;
283 : }
284 :
285 432 : if (which == 0)
286 0 : break; /* no need to consider remaining conditions */
287 : }
288 :
289 : /* We must descend into the quadrant(s) identified by which */
290 696 : out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
291 696 : out->nNodes = 0;
292 3480 : for (i = 1; i <= 4; i++)
293 : {
294 2784 : if (which & (1 << i))
295 2454 : out->nodeNumbers[out->nNodes++] = i - 1;
296 : }
297 :
298 696 : PG_RETURN_VOID();
299 : }
300 :
301 :
302 : Datum
303 158216 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
304 : {
305 158216 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
306 158216 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
307 158216 : Point *datum = DatumGetPointP(in->leafDatum);
308 : bool res;
309 : int i;
310 :
311 : /* all tests are exact */
312 158216 : out->recheck = false;
313 :
314 : /* leafDatum is what it is... */
315 158216 : out->leafValue = in->leafDatum;
316 :
317 : /* Perform the required comparison(s) */
318 158216 : res = true;
319 254668 : for (i = 0; i < in->nkeys; i++)
320 : {
321 114216 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
322 :
323 114216 : switch (in->scankeys[i].sk_strategy)
324 : {
325 : case RTLeftStrategyNumber:
326 25318 : res = SPTEST(point_left, datum, query);
327 25318 : break;
328 : case RTRightStrategyNumber:
329 20728 : res = SPTEST(point_right, datum, query);
330 20728 : break;
331 : case RTSameStrategyNumber:
332 194 : res = SPTEST(point_eq, datum, query);
333 194 : break;
334 : case RTBelowStrategyNumber:
335 29754 : res = SPTEST(point_below, datum, query);
336 29754 : break;
337 : case RTAboveStrategyNumber:
338 28602 : res = SPTEST(point_above, datum, query);
339 28602 : 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 9620 : res = SPTEST(box_contain_pt, query, datum);
348 9620 : break;
349 : default:
350 0 : elog(ERROR, "unrecognized strategy number: %d",
351 : in->scankeys[i].sk_strategy);
352 : break;
353 : }
354 :
355 114216 : if (!res)
356 17764 : break;
357 : }
358 :
359 158216 : PG_RETURN_BOOL(res);
360 : }
|
