Line data Source code
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
26 3 : spg_kd_config(PG_FUNCTION_ARGS)
27 : {
28 : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
29 3 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
30 :
31 3 : cfg->prefixType = FLOAT8OID;
32 3 : cfg->labelType = VOIDOID; /* we don't need node labels */
33 3 : cfg->canReturnData = true;
34 3 : cfg->longValuesOK = false;
35 3 : PG_RETURN_VOID();
36 : }
37 :
38 : static int
39 92865 : getSide(double coord, bool isX, Point *tst)
40 : {
41 92865 : double tstcoord = (isX) ? tst->x : tst->y;
42 :
43 92865 : if (coord == tstcoord)
44 4624 : return 0;
45 88241 : else if (coord > tstcoord)
46 23721 : return 1;
47 : else
48 64520 : return -1;
49 : }
50 :
51 : Datum
52 92865 : spg_kd_choose(PG_FUNCTION_ARGS)
53 : {
54 92865 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
55 92865 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
56 92865 : Point *inPoint = DatumGetPointP(in->datum);
57 : double coord;
58 :
59 92865 : if (in->allTheSame)
60 0 : elog(ERROR, "allTheSame should not occur for k-d trees");
61 :
62 92865 : Assert(in->hasPrefix);
63 92865 : coord = DatumGetFloat8(in->prefixDatum);
64 :
65 92865 : Assert(in->nNodes == 2);
66 :
67 92865 : out->resultType = spgMatchNode;
68 92865 : out->result.matchNode.nodeN =
69 92865 : (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
70 92865 : out->result.matchNode.levelAdd = 1;
71 92865 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
72 :
73 92865 : PG_RETURN_VOID();
74 : }
75 :
76 : typedef struct SortedPoint
77 : {
78 : Point *p;
79 : int i;
80 : } SortedPoint;
81 :
82 : static int
83 46158 : x_cmp(const void *a, const void *b)
84 : {
85 46158 : SortedPoint *pa = (SortedPoint *) a;
86 46158 : SortedPoint *pb = (SortedPoint *) b;
87 :
88 46158 : if (pa->p->x == pb->p->x)
89 1547 : return 0;
90 44611 : return (pa->p->x > pb->p->x) ? 1 : -1;
91 : }
92 :
93 : static int
94 50781 : y_cmp(const void *a, const void *b)
95 : {
96 50781 : SortedPoint *pa = (SortedPoint *) a;
97 50781 : SortedPoint *pb = (SortedPoint *) b;
98 :
99 50781 : if (pa->p->y == pb->p->y)
100 945 : return 0;
101 49836 : return (pa->p->y > pb->p->y) ? 1 : -1;
102 : }
103 :
104 :
105 : Datum
106 93 : spg_kd_picksplit(PG_FUNCTION_ARGS)
107 : {
108 93 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
109 93 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
110 : int i;
111 : int middle;
112 : SortedPoint *sorted;
113 : double coord;
114 :
115 93 : sorted = palloc(sizeof(*sorted) * in->nTuples);
116 15812 : for (i = 0; i < in->nTuples; i++)
117 : {
118 15719 : sorted[i].p = DatumGetPointP(in->datums[i]);
119 15719 : sorted[i].i = i;
120 : }
121 :
122 93 : qsort(sorted, in->nTuples, sizeof(*sorted),
123 : (in->level % 2) ? x_cmp : y_cmp);
124 93 : middle = in->nTuples >> 1;
125 93 : coord = (in->level % 2) ? sorted[middle].p->x : sorted[middle].p->y;
126 :
127 93 : out->hasPrefix = true;
128 93 : out->prefixDatum = Float8GetDatum(coord);
129 :
130 93 : out->nNodes = 2;
131 93 : out->nodeLabels = NULL; /* we don't need node labels */
132 :
133 93 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
134 93 : 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 15812 : for (i = 0; i < in->nTuples; i++)
146 : {
147 15719 : Point *p = sorted[i].p;
148 15719 : int n = sorted[i].i;
149 :
150 15719 : out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
151 15719 : out->leafTupleDatums[n] = PointPGetDatum(p);
152 : }
153 :
154 93 : PG_RETURN_VOID();
155 : }
156 :
157 : Datum
158 634 : spg_kd_inner_consistent(PG_FUNCTION_ARGS)
159 : {
160 634 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
161 634 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
162 : double coord;
163 : int which;
164 : int i;
165 :
166 634 : Assert(in->hasPrefix);
167 634 : coord = DatumGetFloat8(in->prefixDatum);
168 :
169 634 : if (in->allTheSame)
170 0 : elog(ERROR, "allTheSame should not occur for k-d trees");
171 :
172 634 : Assert(in->nNodes == 2);
173 :
174 : /* "which" is a bitmask of children that satisfy all constraints */
175 634 : which = (1 << 1) | (1 << 2);
176 :
177 1268 : for (i = 0; i < in->nkeys; i++)
178 : {
179 634 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
180 : BOX *boxQuery;
181 :
182 634 : switch (in->scankeys[i].sk_strategy)
183 : {
184 : case RTLeftStrategyNumber:
185 124 : if ((in->level % 2) != 0 && FPlt(query->x, coord))
186 10 : which &= (1 << 1);
187 124 : break;
188 : case RTRightStrategyNumber:
189 86 : if ((in->level % 2) != 0 && FPgt(query->x, coord))
190 2 : which &= (1 << 2);
191 86 : break;
192 : case RTSameStrategyNumber:
193 10 : if ((in->level % 2) != 0)
194 : {
195 4 : if (FPlt(query->x, coord))
196 2 : which &= (1 << 1);
197 2 : else if (FPgt(query->x, coord))
198 2 : which &= (1 << 2);
199 : }
200 : else
201 : {
202 6 : if (FPlt(query->y, coord))
203 2 : which &= (1 << 1);
204 4 : else if (FPgt(query->y, coord))
205 4 : which &= (1 << 2);
206 : }
207 10 : break;
208 : case RTBelowStrategyNumber:
209 178 : if ((in->level % 2) == 0 && FPlt(query->y, coord))
210 32 : which &= (1 << 1);
211 178 : break;
212 : case RTAboveStrategyNumber:
213 164 : if ((in->level % 2) == 0 && FPgt(query->y, coord))
214 62 : which &= (1 << 2);
215 164 : 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 72 : boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
224 :
225 72 : if ((in->level % 2) != 0)
226 : {
227 36 : if (FPlt(boxQuery->high.x, coord))
228 12 : which &= (1 << 1);
229 24 : else if (FPgt(boxQuery->low.x, coord))
230 0 : which &= (1 << 2);
231 : }
232 : else
233 : {
234 36 : if (FPlt(boxQuery->high.y, coord))
235 4 : which &= (1 << 1);
236 32 : else if (FPgt(boxQuery->low.y, coord))
237 4 : which &= (1 << 2);
238 : }
239 72 : break;
240 : default:
241 0 : elog(ERROR, "unrecognized strategy number: %d",
242 : in->scankeys[i].sk_strategy);
243 : break;
244 : }
245 :
246 634 : if (which == 0)
247 0 : break; /* no need to consider remaining conditions */
248 : }
249 :
250 : /* We must descend into the children identified by which */
251 634 : out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
252 634 : out->nNodes = 0;
253 1902 : for (i = 1; i <= 2; i++)
254 : {
255 1268 : if (which & (1 << i))
256 1132 : out->nodeNumbers[out->nNodes++] = i - 1;
257 : }
258 :
259 : /* Set up level increments, too */
260 634 : out->levelAdds = (int *) palloc(sizeof(int) * 2);
261 634 : out->levelAdds[0] = 1;
262 634 : out->levelAdds[1] = 1;
263 :
264 634 : 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 : */
|
