Branch data Line data Source code
1 : : /******************************************************************************
2 : : contrib/cube/cube.c
3 : :
4 : : This file contains routines that can be bound to a Postgres backend and
5 : : called by the backend in the process of processing queries. The calling
6 : : format for these routines is dictated by Postgres architecture.
7 : : ******************************************************************************/
8 : :
9 : : #include "postgres.h"
10 : :
11 : : #include <math.h>
12 : :
13 : : #include "access/gist.h"
14 : : #include "access/stratnum.h"
15 : : #include "cubedata.h"
16 : : #include "libpq/pqformat.h"
17 : : #include "utils/array.h"
18 : : #include "utils/float.h"
19 : :
20 : 3 : PG_MODULE_MAGIC_EXT(
21 : : .name = "cube",
22 : : .version = PG_VERSION
23 : : );
24 : :
25 : : /*
26 : : * Taken from the intarray contrib header
27 : : */
28 : : #define ARRPTR(x) ( (double *) ARR_DATA_PTR(x) )
29 : : #define ARRNELEMS(x) ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x))
30 : :
31 : : /*
32 : : * Input/Output routines
33 : : */
34 : 6 : PG_FUNCTION_INFO_V1(cube_in);
35 : 4 : PG_FUNCTION_INFO_V1(cube_a_f8_f8);
36 : 4 : PG_FUNCTION_INFO_V1(cube_a_f8);
37 : 5 : PG_FUNCTION_INFO_V1(cube_out);
38 : 3 : PG_FUNCTION_INFO_V1(cube_send);
39 : 3 : PG_FUNCTION_INFO_V1(cube_recv);
40 : 5 : PG_FUNCTION_INFO_V1(cube_f8);
41 : 4 : PG_FUNCTION_INFO_V1(cube_f8_f8);
42 : 5 : PG_FUNCTION_INFO_V1(cube_c_f8);
43 : 4 : PG_FUNCTION_INFO_V1(cube_c_f8_f8);
44 : 5 : PG_FUNCTION_INFO_V1(cube_dim);
45 : 5 : PG_FUNCTION_INFO_V1(cube_ll_coord);
46 : 5 : PG_FUNCTION_INFO_V1(cube_ur_coord);
47 : 4 : PG_FUNCTION_INFO_V1(cube_coord);
48 : 4 : PG_FUNCTION_INFO_V1(cube_coord_llur);
49 : 4 : PG_FUNCTION_INFO_V1(cube_subset);
50 : :
51 : : /*
52 : : * GiST support methods
53 : : */
54 : :
55 : 4 : PG_FUNCTION_INFO_V1(g_cube_consistent);
56 : 3 : PG_FUNCTION_INFO_V1(g_cube_compress);
57 : 3 : PG_FUNCTION_INFO_V1(g_cube_decompress);
58 : 4 : PG_FUNCTION_INFO_V1(g_cube_penalty);
59 : 4 : PG_FUNCTION_INFO_V1(g_cube_picksplit);
60 : 4 : PG_FUNCTION_INFO_V1(g_cube_union);
61 : 4 : PG_FUNCTION_INFO_V1(g_cube_same);
62 : 4 : PG_FUNCTION_INFO_V1(g_cube_distance);
63 : :
64 : : /*
65 : : * B-tree support functions
66 : : */
67 : 4 : PG_FUNCTION_INFO_V1(cube_eq);
68 : 4 : PG_FUNCTION_INFO_V1(cube_ne);
69 : 4 : PG_FUNCTION_INFO_V1(cube_lt);
70 : 4 : PG_FUNCTION_INFO_V1(cube_gt);
71 : 3 : PG_FUNCTION_INFO_V1(cube_le);
72 : 3 : PG_FUNCTION_INFO_V1(cube_ge);
73 : 4 : PG_FUNCTION_INFO_V1(cube_cmp);
74 : :
75 : : /*
76 : : * R-tree support functions
77 : : */
78 : :
79 : 5 : PG_FUNCTION_INFO_V1(cube_contains);
80 : 4 : PG_FUNCTION_INFO_V1(cube_contained);
81 : 4 : PG_FUNCTION_INFO_V1(cube_overlap);
82 : 4 : PG_FUNCTION_INFO_V1(cube_union);
83 : 4 : PG_FUNCTION_INFO_V1(cube_inter);
84 : 4 : PG_FUNCTION_INFO_V1(cube_size);
85 : :
86 : : /*
87 : : * miscellaneous
88 : : */
89 : 4 : PG_FUNCTION_INFO_V1(distance_taxicab);
90 : 5 : PG_FUNCTION_INFO_V1(cube_distance);
91 : 4 : PG_FUNCTION_INFO_V1(distance_chebyshev);
92 : 5 : PG_FUNCTION_INFO_V1(cube_is_point);
93 : 5 : PG_FUNCTION_INFO_V1(cube_enlarge);
94 : :
95 : : /*
96 : : * For internal use only
97 : : */
98 : : int32 cube_cmp_v0(NDBOX *a, NDBOX *b);
99 : : bool cube_contains_v0(NDBOX *a, NDBOX *b);
100 : : bool cube_overlap_v0(NDBOX *a, NDBOX *b);
101 : : NDBOX *cube_union_v0(NDBOX *a, NDBOX *b);
102 : : void rt_cube_size(NDBOX *a, double *size);
103 : : NDBOX *g_cube_binary_union(NDBOX *r1, NDBOX *r2, int *sizep);
104 : : bool g_cube_leaf_consistent(NDBOX *key, NDBOX *query, StrategyNumber strategy);
105 : : bool g_cube_internal_consistent(NDBOX *key, NDBOX *query, StrategyNumber strategy);
106 : :
107 : : /*
108 : : * Auxiliary functions
109 : : */
110 : : static double distance_1D(double a1, double a2, double b1, double b2);
111 : : static bool cube_is_point_internal(NDBOX *cube);
112 : :
113 : :
114 : : /*****************************************************************************
115 : : * Input/Output functions
116 : : *****************************************************************************/
117 : :
118 : : /* NdBox = [(lowerleft),(upperright)] */
119 : : /* [(xLL(1)...xLL(N)),(xUR(1)...xUR(n))] */
120 : : Datum
121 : 3435 : cube_in(PG_FUNCTION_ARGS)
122 : : {
123 : 3435 : char *str = PG_GETARG_CSTRING(0);
124 : : NDBOX *result;
125 : : Size scanbuflen;
126 : : yyscan_t scanner;
127 : :
128 : 3435 : cube_scanner_init(str, &scanbuflen, &scanner);
129 : :
130 : 3435 : cube_yyparse(&result, scanbuflen, fcinfo->context, scanner);
131 : :
132 : : /* We might as well run this even on failure. */
133 : 3405 : cube_scanner_finish(scanner);
134 : :
135 : 3405 : PG_RETURN_NDBOX_P(result);
136 : : }
137 : :
138 : :
139 : : /*
140 : : * Allows the construction of a cube from 2 float[]'s
141 : : */
142 : : Datum
143 : 22 : cube_a_f8_f8(PG_FUNCTION_ARGS)
144 : : {
145 : 22 : ArrayType *ur = PG_GETARG_ARRAYTYPE_P(0);
146 : 22 : ArrayType *ll = PG_GETARG_ARRAYTYPE_P(1);
147 : : NDBOX *result;
148 : : int i;
149 : : int dim;
150 : : int size;
151 : : bool point;
152 : : double *dur,
153 : : *dll;
154 : :
155 [ + - - + ]: 22 : if (array_contains_nulls(ur) || array_contains_nulls(ll))
156 [ # # ]: 0 : ereport(ERROR,
157 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
158 : : errmsg("cannot work with arrays containing NULLs")));
159 : :
160 : 22 : dim = ARRNELEMS(ur);
161 [ + + ]: 22 : if (dim > CUBE_MAX_DIM)
162 [ + - ]: 1 : ereport(ERROR,
163 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
164 : : errmsg("can't extend cube"),
165 : : errdetail("A cube cannot have more than %d dimensions.",
166 : : CUBE_MAX_DIM)));
167 : :
168 [ + + ]: 21 : if (ARRNELEMS(ll) != dim)
169 [ + - ]: 1 : ereport(ERROR,
170 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
171 : : errmsg("UR and LL arrays must be of same length")));
172 : :
173 [ - + ]: 20 : dur = ARRPTR(ur);
174 [ - + ]: 20 : dll = ARRPTR(ll);
175 : :
176 : : /* Check if it's a point */
177 : 20 : point = true;
178 [ + + ]: 223 : for (i = 0; i < dim; i++)
179 : : {
180 [ + + ]: 220 : if (dur[i] != dll[i])
181 : : {
182 : 17 : point = false;
183 : 17 : break;
184 : : }
185 : : }
186 : :
187 [ + + ]: 20 : size = point ? POINT_SIZE(dim) : CUBE_SIZE(dim);
188 : 20 : result = (NDBOX *) palloc0(size);
189 : 20 : SET_VARSIZE(result, size);
190 : 20 : SET_DIM(result, dim);
191 : :
192 [ + + ]: 274 : for (i = 0; i < dim; i++)
193 : 254 : result->x[i] = dur[i];
194 : :
195 [ + + ]: 20 : if (!point)
196 : : {
197 [ + + ]: 68 : for (i = 0; i < dim; i++)
198 : 51 : result->x[i + dim] = dll[i];
199 : : }
200 : : else
201 : 3 : SET_POINT_BIT(result);
202 : :
203 : 20 : PG_RETURN_NDBOX_P(result);
204 : : }
205 : :
206 : : /*
207 : : * Allows the construction of a zero-volume cube from a float[]
208 : : */
209 : : Datum
210 : 8 : cube_a_f8(PG_FUNCTION_ARGS)
211 : : {
212 : 8 : ArrayType *ur = PG_GETARG_ARRAYTYPE_P(0);
213 : : NDBOX *result;
214 : : int i;
215 : : int dim;
216 : : int size;
217 : : double *dur;
218 : :
219 [ - + ]: 8 : if (array_contains_nulls(ur))
220 [ # # ]: 0 : ereport(ERROR,
221 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
222 : : errmsg("cannot work with arrays containing NULLs")));
223 : :
224 : 8 : dim = ARRNELEMS(ur);
225 [ + + ]: 8 : if (dim > CUBE_MAX_DIM)
226 [ + - ]: 1 : ereport(ERROR,
227 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
228 : : errmsg("array is too long"),
229 : : errdetail("A cube cannot have more than %d dimensions.",
230 : : CUBE_MAX_DIM)));
231 : :
232 [ - + ]: 7 : dur = ARRPTR(ur);
233 : :
234 : 7 : size = POINT_SIZE(dim);
235 : 7 : result = (NDBOX *) palloc0(size);
236 : 7 : SET_VARSIZE(result, size);
237 : 7 : SET_DIM(result, dim);
238 : 7 : SET_POINT_BIT(result);
239 : :
240 [ + + ]: 223 : for (i = 0; i < dim; i++)
241 : 216 : result->x[i] = dur[i];
242 : :
243 : 7 : PG_RETURN_NDBOX_P(result);
244 : : }
245 : :
246 : : Datum
247 : 6 : cube_subset(PG_FUNCTION_ARGS)
248 : : {
249 : 6 : NDBOX *c = PG_GETARG_NDBOX_P(0);
250 : 6 : ArrayType *idx = PG_GETARG_ARRAYTYPE_P(1);
251 : : NDBOX *result;
252 : : int size,
253 : : dim,
254 : : i;
255 : : int *dx;
256 : :
257 [ - + ]: 6 : if (array_contains_nulls(idx))
258 [ # # ]: 0 : ereport(ERROR,
259 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
260 : : errmsg("cannot work with arrays containing NULLs")));
261 : :
262 [ - + ]: 6 : dx = (int32 *) ARR_DATA_PTR(idx);
263 : :
264 : 6 : dim = ARRNELEMS(idx);
265 [ + + ]: 6 : if (dim > CUBE_MAX_DIM)
266 [ + - ]: 1 : ereport(ERROR,
267 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
268 : : errmsg("array is too long"),
269 : : errdetail("A cube cannot have more than %d dimensions.",
270 : : CUBE_MAX_DIM)));
271 : :
272 [ + + ]: 5 : size = IS_POINT(c) ? POINT_SIZE(dim) : CUBE_SIZE(dim);
273 : 5 : result = (NDBOX *) palloc0(size);
274 : 5 : SET_VARSIZE(result, size);
275 : 5 : SET_DIM(result, dim);
276 : :
277 [ + + ]: 5 : if (IS_POINT(c))
278 : 3 : SET_POINT_BIT(result);
279 : :
280 [ + + ]: 113 : for (i = 0; i < dim; i++)
281 : : {
282 [ + - + + ]: 110 : if ((dx[i] <= 0) || (dx[i] > DIM(c)))
283 [ + - ]: 2 : ereport(ERROR,
284 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
285 : : errmsg("Index out of bounds")));
286 : 108 : result->x[i] = c->x[dx[i] - 1];
287 [ + + ]: 108 : if (!IS_POINT(c))
288 : 4 : result->x[i + dim] = c->x[dx[i] + DIM(c) - 1];
289 : : }
290 : :
291 [ - + ]: 3 : PG_FREE_IF_COPY(c, 0);
292 : 3 : PG_RETURN_NDBOX_P(result);
293 : : }
294 : :
295 : : Datum
296 : 389 : cube_out(PG_FUNCTION_ARGS)
297 : : {
298 : 389 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
299 : : StringInfoData buf;
300 : 389 : int dim = DIM(cube);
301 : : int i;
302 : :
303 : 389 : initStringInfo(&buf);
304 : :
305 : 389 : appendStringInfoChar(&buf, '(');
306 [ + + ]: 1435 : for (i = 0; i < dim; i++)
307 : : {
308 [ + + ]: 1046 : if (i > 0)
309 : 659 : appendStringInfoString(&buf, ", ");
310 : 1046 : appendStringInfoString(&buf, float8out_internal(LL_COORD(cube, i)));
311 : : }
312 : 389 : appendStringInfoChar(&buf, ')');
313 : :
314 [ + + ]: 389 : if (!cube_is_point_internal(cube))
315 : : {
316 : 290 : appendStringInfoString(&buf, ",(");
317 [ + + ]: 880 : for (i = 0; i < dim; i++)
318 : : {
319 [ + + ]: 590 : if (i > 0)
320 : 300 : appendStringInfoString(&buf, ", ");
321 [ - + ]: 590 : appendStringInfoString(&buf, float8out_internal(UR_COORD(cube, i)));
322 : : }
323 : 290 : appendStringInfoChar(&buf, ')');
324 : : }
325 : :
326 [ - + ]: 389 : PG_FREE_IF_COPY(cube, 0);
327 : 389 : PG_RETURN_CSTRING(buf.data);
328 : : }
329 : :
330 : : /*
331 : : * cube_send - a binary output handler for cube type
332 : : */
333 : : Datum
334 : 0 : cube_send(PG_FUNCTION_ARGS)
335 : : {
336 : 0 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
337 : : StringInfoData buf;
338 : : int32 i,
339 : 0 : nitems = DIM(cube);
340 : :
341 : 0 : pq_begintypsend(&buf);
342 : 0 : pq_sendint32(&buf, cube->header);
343 [ # # ]: 0 : if (!IS_POINT(cube))
344 : 0 : nitems += nitems;
345 : : /* for symmetry with cube_recv, we don't use LL_COORD/UR_COORD here */
346 [ # # ]: 0 : for (i = 0; i < nitems; i++)
347 : 0 : pq_sendfloat8(&buf, cube->x[i]);
348 : :
349 : 0 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
350 : : }
351 : :
352 : : /*
353 : : * cube_recv - a binary input handler for cube type
354 : : */
355 : : Datum
356 : 0 : cube_recv(PG_FUNCTION_ARGS)
357 : : {
358 : 0 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
359 : : int32 header;
360 : : int32 i,
361 : : nitems;
362 : : NDBOX *cube;
363 : :
364 : 0 : header = pq_getmsgint(buf, sizeof(int32));
365 : 0 : nitems = (header & DIM_MASK);
366 [ # # ]: 0 : if (nitems > CUBE_MAX_DIM)
367 [ # # ]: 0 : ereport(ERROR,
368 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
369 : : errmsg("cube dimension is too large"),
370 : : errdetail("A cube cannot have more than %d dimensions.",
371 : : CUBE_MAX_DIM)));
372 [ # # ]: 0 : if ((header & POINT_BIT) == 0)
373 : 0 : nitems += nitems;
374 : 0 : cube = palloc(offsetof(NDBOX, x) + sizeof(double) * nitems);
375 : 0 : SET_VARSIZE(cube, offsetof(NDBOX, x) + sizeof(double) * nitems);
376 : 0 : cube->header = header;
377 [ # # ]: 0 : for (i = 0; i < nitems; i++)
378 : 0 : cube->x[i] = pq_getmsgfloat8(buf);
379 : :
380 : 0 : PG_RETURN_NDBOX_P(cube);
381 : : }
382 : :
383 : :
384 : : /*****************************************************************************
385 : : * GiST functions
386 : : *****************************************************************************/
387 : :
388 : : /*
389 : : * The GiST Consistent method for boxes
390 : : * Should return false if for all data items x below entry,
391 : : * the predicate x op query == false, where op is the oper
392 : : * corresponding to strategy in the pg_amop table.
393 : : */
394 : : Datum
395 : 249 : g_cube_consistent(PG_FUNCTION_ARGS)
396 : : {
397 : 249 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
398 : 249 : NDBOX *query = PG_GETARG_NDBOX_P(1);
399 : 249 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
400 : : #ifdef NOT_USED
401 : : Oid subtype = PG_GETARG_OID(3);
402 : : #endif
403 : 249 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
404 : : bool res;
405 : :
406 : : /* All cases served by this function are exact */
407 : 249 : *recheck = false;
408 : :
409 : : /*
410 : : * if entry is not leaf, use g_cube_internal_consistent, else use
411 : : * g_cube_leaf_consistent
412 : : */
413 [ + + ]: 249 : if (GIST_LEAF(entry))
414 : 144 : res = g_cube_leaf_consistent(DatumGetNDBOXP(entry->key),
415 : : query, strategy);
416 : : else
417 : 105 : res = g_cube_internal_consistent(DatumGetNDBOXP(entry->key),
418 : : query, strategy);
419 : :
420 [ - + ]: 249 : PG_FREE_IF_COPY(query, 1);
421 : 249 : PG_RETURN_BOOL(res);
422 : : }
423 : :
424 : :
425 : : /*
426 : : * The GiST Union method for boxes
427 : : * returns the minimal bounding box that encloses all the entries in entryvec
428 : : */
429 : : Datum
430 : 2962 : g_cube_union(PG_FUNCTION_ARGS)
431 : : {
432 : 2962 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
433 : 2962 : int *sizep = (int *) PG_GETARG_POINTER(1);
434 : 2962 : NDBOX *out = (NDBOX *) NULL;
435 : : NDBOX *tmp;
436 : : int i;
437 : :
438 : 2962 : tmp = DatumGetNDBOXP(entryvec->vector[0].key);
439 : :
440 : : /*
441 : : * sizep = sizeof(NDBOX); -- NDBOX has variable size
442 : : */
443 : 2962 : *sizep = VARSIZE(tmp);
444 : :
445 [ + + ]: 5924 : for (i = 1; i < entryvec->n; i++)
446 : : {
447 : 2962 : out = g_cube_binary_union(tmp,
448 : 2962 : DatumGetNDBOXP(entryvec->vector[i].key),
449 : : sizep);
450 : 2962 : tmp = out;
451 : : }
452 : :
453 : 2962 : PG_RETURN_POINTER(out);
454 : : }
455 : :
456 : : /*
457 : : * GiST Compress and Decompress methods for boxes
458 : : * do not do anything.
459 : : */
460 : :
461 : : Datum
462 : 0 : g_cube_compress(PG_FUNCTION_ARGS)
463 : : {
464 : 0 : PG_RETURN_DATUM(PG_GETARG_DATUM(0));
465 : : }
466 : :
467 : : Datum
468 : 0 : g_cube_decompress(PG_FUNCTION_ARGS)
469 : : {
470 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
471 : 0 : NDBOX *key = DatumGetNDBOXP(entry->key);
472 : :
473 [ # # ]: 0 : if (key != DatumGetNDBOXP(entry->key))
474 : : {
475 : 0 : GISTENTRY *retval = palloc_object(GISTENTRY);
476 : :
477 : 0 : gistentryinit(*retval, PointerGetDatum(key),
478 : : entry->rel, entry->page,
479 : : entry->offset, false);
480 : 0 : PG_RETURN_POINTER(retval);
481 : : }
482 : 0 : PG_RETURN_POINTER(entry);
483 : : }
484 : :
485 : :
486 : : /*
487 : : * The GiST Penalty method for boxes
488 : : * As in the R-tree paper, we use change in area as our penalty metric
489 : : */
490 : : Datum
491 : 43445 : g_cube_penalty(PG_FUNCTION_ARGS)
492 : : {
493 : 43445 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
494 : 43445 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
495 : 43445 : float *result = (float *) PG_GETARG_POINTER(2);
496 : : NDBOX *ud;
497 : : double tmp1,
498 : : tmp2;
499 : :
500 : 43445 : ud = cube_union_v0(DatumGetNDBOXP(origentry->key),
501 : 43445 : DatumGetNDBOXP(newentry->key));
502 : 43445 : rt_cube_size(ud, &tmp1);
503 : 43445 : rt_cube_size(DatumGetNDBOXP(origentry->key), &tmp2);
504 : 43445 : *result = (float) (tmp1 - tmp2);
505 : :
506 : 43445 : PG_RETURN_FLOAT8(*result);
507 : : }
508 : :
509 : :
510 : :
511 : : /*
512 : : * The GiST PickSplit method for boxes
513 : : * We use Guttman's poly time split algorithm
514 : : */
515 : : Datum
516 : 34 : g_cube_picksplit(PG_FUNCTION_ARGS)
517 : : {
518 : 34 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
519 : 34 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
520 : : OffsetNumber i,
521 : : j;
522 : : NDBOX *datum_alpha,
523 : : *datum_beta;
524 : : NDBOX *datum_l,
525 : : *datum_r;
526 : : NDBOX *union_d,
527 : : *union_dl,
528 : : *union_dr;
529 : : NDBOX *inter_d;
530 : : bool firsttime;
531 : : double size_alpha,
532 : : size_beta,
533 : : size_union,
534 : : size_inter;
535 : : double size_waste,
536 : : waste;
537 : : double size_l,
538 : : size_r;
539 : : int nbytes;
540 : 34 : OffsetNumber seed_1 = 1,
541 : 34 : seed_2 = 2;
542 : : OffsetNumber *left,
543 : : *right;
544 : : OffsetNumber maxoff;
545 : :
546 : 34 : maxoff = entryvec->n - 2;
547 : 34 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
548 : 34 : v->spl_left = (OffsetNumber *) palloc(nbytes);
549 : 34 : v->spl_right = (OffsetNumber *) palloc(nbytes);
550 : :
551 : 34 : firsttime = true;
552 : 34 : waste = 0.0;
553 : :
554 [ + + ]: 4760 : for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
555 : : {
556 : 4726 : datum_alpha = DatumGetNDBOXP(entryvec->vector[i].key);
557 [ + + ]: 335546 : for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
558 : : {
559 : 330820 : datum_beta = DatumGetNDBOXP(entryvec->vector[j].key);
560 : :
561 : : /* compute the wasted space by unioning these guys */
562 : : /* size_waste = size_union - size_inter; */
563 : 330820 : union_d = cube_union_v0(datum_alpha, datum_beta);
564 : 330820 : rt_cube_size(union_d, &size_union);
565 : 330820 : inter_d = DatumGetNDBOXP(DirectFunctionCall2(cube_inter,
566 : : entryvec->vector[i].key,
567 : : entryvec->vector[j].key));
568 : 330820 : rt_cube_size(inter_d, &size_inter);
569 : 330820 : size_waste = size_union - size_inter;
570 : :
571 : : /*
572 : : * are these a more promising split than what we've already seen?
573 : : */
574 : :
575 [ + + - + ]: 330820 : if (size_waste > waste || firsttime)
576 : : {
577 : 449 : waste = size_waste;
578 : 449 : seed_1 = i;
579 : 449 : seed_2 = j;
580 : 449 : firsttime = false;
581 : : }
582 : : }
583 : : }
584 : :
585 : 34 : left = v->spl_left;
586 : 34 : v->spl_nleft = 0;
587 : 34 : right = v->spl_right;
588 : 34 : v->spl_nright = 0;
589 : :
590 : 34 : datum_alpha = DatumGetNDBOXP(entryvec->vector[seed_1].key);
591 : 34 : datum_l = cube_union_v0(datum_alpha, datum_alpha);
592 : 34 : rt_cube_size(datum_l, &size_l);
593 : 34 : datum_beta = DatumGetNDBOXP(entryvec->vector[seed_2].key);
594 : 34 : datum_r = cube_union_v0(datum_beta, datum_beta);
595 : 34 : rt_cube_size(datum_r, &size_r);
596 : :
597 : : /*
598 : : * Now split up the regions between the two seeds. An important property
599 : : * of this split algorithm is that the split vector v has the indices of
600 : : * items to be split in order in its left and right vectors. We exploit
601 : : * this property by doing a merge in the code that actually splits the
602 : : * page.
603 : : *
604 : : * For efficiency, we also place the new index tuple in this loop. This is
605 : : * handled at the very end, when we have placed all the existing tuples
606 : : * and i == maxoff + 1.
607 : : */
608 : :
609 : 34 : maxoff = OffsetNumberNext(maxoff);
610 [ + + ]: 4828 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
611 : : {
612 : : /*
613 : : * If we've already decided where to place this item, just put it on
614 : : * the right list. Otherwise, we need to figure out which page needs
615 : : * the least enlargement in order to store the item.
616 : : */
617 : :
618 [ + + ]: 4794 : if (i == seed_1)
619 : : {
620 : 34 : *left++ = i;
621 : 34 : v->spl_nleft++;
622 : 34 : continue;
623 : : }
624 [ + + ]: 4760 : else if (i == seed_2)
625 : : {
626 : 34 : *right++ = i;
627 : 34 : v->spl_nright++;
628 : 34 : continue;
629 : : }
630 : :
631 : : /* okay, which page needs least enlargement? */
632 : 4726 : datum_alpha = DatumGetNDBOXP(entryvec->vector[i].key);
633 : 4726 : union_dl = cube_union_v0(datum_l, datum_alpha);
634 : 4726 : union_dr = cube_union_v0(datum_r, datum_alpha);
635 : 4726 : rt_cube_size(union_dl, &size_alpha);
636 : 4726 : rt_cube_size(union_dr, &size_beta);
637 : :
638 : : /* pick which page to add it to */
639 [ + + ]: 4726 : if (size_alpha - size_l < size_beta - size_r)
640 : : {
641 : 2299 : datum_l = union_dl;
642 : 2299 : size_l = size_alpha;
643 : 2299 : *left++ = i;
644 : 2299 : v->spl_nleft++;
645 : : }
646 : : else
647 : : {
648 : 2427 : datum_r = union_dr;
649 : 2427 : size_r = size_beta;
650 : 2427 : *right++ = i;
651 : 2427 : v->spl_nright++;
652 : : }
653 : : }
654 : 34 : *left = *right = FirstOffsetNumber; /* sentinel value */
655 : :
656 : 34 : v->spl_ldatum = PointerGetDatum(datum_l);
657 : 34 : v->spl_rdatum = PointerGetDatum(datum_r);
658 : :
659 : 34 : PG_RETURN_POINTER(v);
660 : : }
661 : :
662 : : /*
663 : : * Equality method
664 : : */
665 : : Datum
666 : 2962 : g_cube_same(PG_FUNCTION_ARGS)
667 : : {
668 : 2962 : NDBOX *b1 = PG_GETARG_NDBOX_P(0);
669 : 2962 : NDBOX *b2 = PG_GETARG_NDBOX_P(1);
670 : 2962 : bool *result = (bool *) PG_GETARG_POINTER(2);
671 : :
672 [ + + ]: 2962 : if (cube_cmp_v0(b1, b2) == 0)
673 : 2810 : *result = true;
674 : : else
675 : 152 : *result = false;
676 : :
677 : 2962 : PG_RETURN_NDBOX_P(result);
678 : : }
679 : :
680 : : /*
681 : : * SUPPORT ROUTINES
682 : : */
683 : : bool
684 : 144 : g_cube_leaf_consistent(NDBOX *key,
685 : : NDBOX *query,
686 : : StrategyNumber strategy)
687 : : {
688 : : bool retval;
689 : :
690 [ + - - + : 144 : switch (strategy)
- ]
691 : : {
692 : 96 : case RTOverlapStrategyNumber:
693 : 96 : retval = cube_overlap_v0(key, query);
694 : 96 : break;
695 : 0 : case RTSameStrategyNumber:
696 : 0 : retval = (cube_cmp_v0(key, query) == 0);
697 : 0 : break;
698 : 0 : case RTContainsStrategyNumber:
699 : : case RTOldContainsStrategyNumber:
700 : 0 : retval = cube_contains_v0(key, query);
701 : 0 : break;
702 : 48 : case RTContainedByStrategyNumber:
703 : : case RTOldContainedByStrategyNumber:
704 : 48 : retval = cube_contains_v0(query, key);
705 : 48 : break;
706 : 0 : default:
707 : 0 : retval = false;
708 : : }
709 : 144 : return retval;
710 : : }
711 : :
712 : : bool
713 : 105 : g_cube_internal_consistent(NDBOX *key,
714 : : NDBOX *query,
715 : : StrategyNumber strategy)
716 : : {
717 : : bool retval;
718 : :
719 [ + - + - ]: 105 : switch (strategy)
720 : : {
721 : 70 : case RTOverlapStrategyNumber:
722 : 70 : retval = cube_overlap_v0(key, query);
723 : 70 : break;
724 : 0 : case RTSameStrategyNumber:
725 : : case RTContainsStrategyNumber:
726 : : case RTOldContainsStrategyNumber:
727 : 0 : retval = cube_contains_v0(key, query);
728 : 0 : break;
729 : 35 : case RTContainedByStrategyNumber:
730 : : case RTOldContainedByStrategyNumber:
731 : 35 : retval = cube_overlap_v0(key, query);
732 : 35 : break;
733 : 0 : default:
734 : 0 : retval = false;
735 : : }
736 : 105 : return retval;
737 : : }
738 : :
739 : : NDBOX *
740 : 2962 : g_cube_binary_union(NDBOX *r1, NDBOX *r2, int *sizep)
741 : : {
742 : : NDBOX *retval;
743 : :
744 : 2962 : retval = cube_union_v0(r1, r2);
745 : 2962 : *sizep = VARSIZE(retval);
746 : :
747 : 2962 : return retval;
748 : : }
749 : :
750 : :
751 : : /* cube_union_v0 */
752 : : NDBOX *
753 : 386752 : cube_union_v0(NDBOX *a, NDBOX *b)
754 : : {
755 : : int i;
756 : : NDBOX *result;
757 : : int dim;
758 : : int size;
759 : :
760 : : /* trivial case */
761 [ + + ]: 386752 : if (a == b)
762 : 68 : return a;
763 : :
764 : : /* swap the arguments if needed, so that 'a' is always larger than 'b' */
765 [ + + ]: 386684 : if (DIM(a) < DIM(b))
766 : : {
767 : 3 : NDBOX *tmp = b;
768 : :
769 : 3 : b = a;
770 : 3 : a = tmp;
771 : : }
772 : 386684 : dim = DIM(a);
773 : :
774 : 386684 : size = CUBE_SIZE(dim);
775 : 386684 : result = palloc0(size);
776 : 386684 : SET_VARSIZE(result, size);
777 : 386684 : SET_DIM(result, dim);
778 : :
779 : : /* First compute the union of the dimensions present in both args */
780 [ + + ]: 1160016 : for (i = 0; i < DIM(b); i++)
781 : : {
782 [ + + + + : 773332 : result->x[i] = Min(Min(LL_COORD(a, i), UR_COORD(a, i)),
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + ]
783 : : Min(LL_COORD(b, i), UR_COORD(b, i)));
784 [ + + + + : 773332 : result->x[i + DIM(a)] = Max(Max(LL_COORD(a, i), UR_COORD(a, i)),
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + ]
785 : : Max(LL_COORD(b, i), UR_COORD(b, i)));
786 : : }
787 : : /* continue on the higher dimensions only present in 'a' */
788 [ + + ]: 386724 : for (; i < DIM(a); i++)
789 : : {
790 [ + + + - : 40 : result->x[i] = Min(0,
+ - + + -
+ - - +
- ]
791 : : Min(LL_COORD(a, i), UR_COORD(a, i))
792 : : );
793 [ + + - + : 40 : result->x[i + dim] = Max(0,
+ + - + +
+ - + +
+ ]
794 : : Max(LL_COORD(a, i), UR_COORD(a, i))
795 : : );
796 : : }
797 : :
798 : : /*
799 : : * Check if the result was in fact a point, and set the flag in the datum
800 : : * accordingly. (we don't bother to repalloc it smaller)
801 : : */
802 [ + + ]: 386684 : if (cube_is_point_internal(result))
803 : : {
804 : 2 : size = POINT_SIZE(dim);
805 : 2 : SET_VARSIZE(result, size);
806 : 2 : SET_POINT_BIT(result);
807 : : }
808 : :
809 : 386684 : return result;
810 : : }
811 : :
812 : : Datum
813 : 5 : cube_union(PG_FUNCTION_ARGS)
814 : : {
815 : 5 : NDBOX *a = PG_GETARG_NDBOX_P(0);
816 : 5 : NDBOX *b = PG_GETARG_NDBOX_P(1);
817 : : NDBOX *res;
818 : :
819 : 5 : res = cube_union_v0(a, b);
820 : :
821 [ - + ]: 5 : PG_FREE_IF_COPY(a, 0);
822 [ - + ]: 5 : PG_FREE_IF_COPY(b, 1);
823 : 5 : PG_RETURN_NDBOX_P(res);
824 : : }
825 : :
826 : : /* cube_inter */
827 : : Datum
828 : 330827 : cube_inter(PG_FUNCTION_ARGS)
829 : : {
830 : 330827 : NDBOX *a = PG_GETARG_NDBOX_P(0);
831 : 330827 : NDBOX *b = PG_GETARG_NDBOX_P(1);
832 : : NDBOX *result;
833 : 330827 : bool swapped = false;
834 : : int i;
835 : : int dim;
836 : : int size;
837 : :
838 : : /* swap the arguments if needed, so that 'a' is always larger than 'b' */
839 [ - + ]: 330827 : if (DIM(a) < DIM(b))
840 : : {
841 : 0 : NDBOX *tmp = b;
842 : :
843 : 0 : b = a;
844 : 0 : a = tmp;
845 : 0 : swapped = true;
846 : : }
847 : 330827 : dim = DIM(a);
848 : :
849 : 330827 : size = CUBE_SIZE(dim);
850 : 330827 : result = (NDBOX *) palloc0(size);
851 : 330827 : SET_VARSIZE(result, size);
852 : 330827 : SET_DIM(result, dim);
853 : :
854 : : /* First compute intersection of the dimensions present in both args */
855 [ + + ]: 992483 : for (i = 0; i < DIM(b); i++)
856 : : {
857 [ + + + + : 661656 : result->x[i] = Max(Min(LL_COORD(a, i), UR_COORD(a, i)),
+ + + + +
+ + + + +
+ - - + -
+ + + + +
+ + ]
858 : : Min(LL_COORD(b, i), UR_COORD(b, i)));
859 [ + + + + : 661656 : result->x[i + DIM(a)] = Min(Max(LL_COORD(a, i), UR_COORD(a, i)),
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + ]
860 : : Max(LL_COORD(b, i), UR_COORD(b, i)));
861 : : }
862 : : /* continue on the higher dimensions only present in 'a' */
863 [ - + ]: 330827 : for (; i < DIM(a); i++)
864 : : {
865 [ # # # # : 0 : result->x[i] = Max(0,
# # # # #
# # # #
# ]
866 : : Min(LL_COORD(a, i), UR_COORD(a, i))
867 : : );
868 [ # # # # : 0 : result->x[i + DIM(a)] = Min(0,
# # # # #
# # # #
# ]
869 : : Max(LL_COORD(a, i), UR_COORD(a, i))
870 : : );
871 : : }
872 : :
873 : : /*
874 : : * Check if the result was in fact a point, and set the flag in the datum
875 : : * accordingly. (we don't bother to repalloc it smaller)
876 : : */
877 [ + + ]: 330827 : if (cube_is_point_internal(result))
878 : : {
879 : 2 : size = POINT_SIZE(dim);
880 : 2 : result = repalloc(result, size);
881 : 2 : SET_VARSIZE(result, size);
882 : 2 : SET_POINT_BIT(result);
883 : : }
884 : :
885 [ - + ]: 330827 : if (swapped)
886 : : {
887 [ # # ]: 0 : PG_FREE_IF_COPY(b, 0);
888 [ # # ]: 0 : PG_FREE_IF_COPY(a, 1);
889 : : }
890 : : else
891 : : {
892 [ - + ]: 330827 : PG_FREE_IF_COPY(a, 0);
893 [ - + ]: 330827 : PG_FREE_IF_COPY(b, 1);
894 : : }
895 : :
896 : : /*
897 : : * Is it OK to return a non-null intersection for non-overlapping boxes?
898 : : */
899 : 330827 : PG_RETURN_NDBOX_P(result);
900 : : }
901 : :
902 : : /* cube_size */
903 : : Datum
904 : 2 : cube_size(PG_FUNCTION_ARGS)
905 : : {
906 : 2 : NDBOX *a = PG_GETARG_NDBOX_P(0);
907 : : double result;
908 : :
909 : 2 : rt_cube_size(a, &result);
910 [ - + ]: 2 : PG_FREE_IF_COPY(a, 0);
911 : 2 : PG_RETURN_FLOAT8(result);
912 : : }
913 : :
914 : : void
915 : 758052 : rt_cube_size(NDBOX *a, double *size)
916 : : {
917 : : double result;
918 : : int i;
919 : :
920 [ - + ]: 758052 : if (a == (NDBOX *) NULL)
921 : : {
922 : : /* special case for GiST */
923 : 0 : result = 0.0;
924 : : }
925 [ + + - + ]: 758052 : else if (IS_POINT(a) || DIM(a) == 0)
926 : : {
927 : : /* necessarily has zero size */
928 : 1 : result = 0.0;
929 : : }
930 : : else
931 : : {
932 : 758051 : result = 1.0;
933 [ + + ]: 2274153 : for (i = 0; i < DIM(a); i++)
934 [ - + ]: 1516102 : result *= fabs(UR_COORD(a, i) - LL_COORD(a, i));
935 : : }
936 : 758052 : *size = result;
937 : 758052 : }
938 : :
939 : : /*
940 : : * make up a metric in which one box will be 'lower' than the other
941 : : * -- this can be useful for sorting and to determine uniqueness
942 : : */
943 : : int32
944 : 3010 : cube_cmp_v0(NDBOX *a, NDBOX *b)
945 : : {
946 : : int i;
947 : : int dim;
948 : :
949 : 3010 : dim = Min(DIM(a), DIM(b));
950 : :
951 : : /* compare the common dimensions */
952 [ + + ]: 8861 : for (i = 0; i < dim; i++)
953 : : {
954 [ + + + + : 11914 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) >
+ + + + ]
955 [ + + + + : 5957 : Min(LL_COORD(b, i), UR_COORD(b, i)))
+ + ]
956 : 91 : return 1;
957 [ + + + + : 11732 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) <
+ + + + ]
958 [ + + + + : 5866 : Min(LL_COORD(b, i), UR_COORD(b, i)))
+ + ]
959 : 15 : return -1;
960 : : }
961 [ + + ]: 8596 : for (i = 0; i < dim; i++)
962 : : {
963 [ + + - + : 11540 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) >
+ + - + ]
964 [ + + - + : 5770 : Max(LL_COORD(b, i), UR_COORD(b, i)))
+ + ]
965 : 0 : return 1;
966 [ + + - + : 11540 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) <
+ + + + ]
967 [ + + - + : 5770 : Max(LL_COORD(b, i), UR_COORD(b, i)))
+ + ]
968 : 78 : return -1;
969 : : }
970 : :
971 : : /* compare extra dimensions to zero */
972 [ + + ]: 2826 : if (DIM(a) > DIM(b))
973 : : {
974 [ + + ]: 24 : for (i = dim; i < DIM(a); i++)
975 : : {
976 [ + - + + : 18 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) > 0)
- + - + ]
977 : 0 : return 1;
978 [ + - + + : 18 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) < 0)
- + - + ]
979 : 0 : return -1;
980 : : }
981 [ + + ]: 20 : for (i = dim; i < DIM(a); i++)
982 : : {
983 [ + - + + : 18 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) > 0)
- + + + ]
984 : 4 : return 1;
985 [ + - - + : 14 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) < 0)
- + - + ]
986 : 0 : return -1;
987 : : }
988 : :
989 : : /*
990 : : * if all common dimensions are equal, the cube with more dimensions
991 : : * wins
992 : : */
993 : 2 : return 1;
994 : : }
995 [ + + ]: 2820 : if (DIM(a) < DIM(b))
996 : : {
997 [ + + ]: 32 : for (i = dim; i < DIM(b); i++)
998 : : {
999 [ + - + + : 24 : if (Min(LL_COORD(b, i), UR_COORD(b, i)) > 0)
- + - + ]
1000 : 0 : return -1;
1001 [ + - + + : 24 : if (Min(LL_COORD(b, i), UR_COORD(b, i)) < 0)
- + - + ]
1002 : 0 : return 1;
1003 : : }
1004 [ + + ]: 27 : for (i = dim; i < DIM(b); i++)
1005 : : {
1006 [ + - + + : 24 : if (Max(LL_COORD(b, i), UR_COORD(b, i)) > 0)
- + + + ]
1007 : 5 : return -1;
1008 [ + - - + : 19 : if (Max(LL_COORD(b, i), UR_COORD(b, i)) < 0)
- + - + ]
1009 : 0 : return 1;
1010 : : }
1011 : :
1012 : : /*
1013 : : * if all common dimensions are equal, the cube with more dimensions
1014 : : * wins
1015 : : */
1016 : 3 : return -1;
1017 : : }
1018 : :
1019 : : /* They're really equal */
1020 : 2812 : return 0;
1021 : : }
1022 : :
1023 : : Datum
1024 : 22 : cube_cmp(PG_FUNCTION_ARGS)
1025 : : {
1026 : 22 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1027 : 22 : *b = PG_GETARG_NDBOX_P(1);
1028 : : int32 res;
1029 : :
1030 : 22 : res = cube_cmp_v0(a, b);
1031 : :
1032 [ - + ]: 22 : PG_FREE_IF_COPY(a, 0);
1033 [ - + ]: 22 : PG_FREE_IF_COPY(b, 1);
1034 : 22 : PG_RETURN_INT32(res);
1035 : : }
1036 : :
1037 : :
1038 : : Datum
1039 : 8 : cube_eq(PG_FUNCTION_ARGS)
1040 : : {
1041 : 8 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1042 : 8 : *b = PG_GETARG_NDBOX_P(1);
1043 : : int32 res;
1044 : :
1045 : 8 : res = cube_cmp_v0(a, b);
1046 : :
1047 [ - + ]: 8 : PG_FREE_IF_COPY(a, 0);
1048 [ - + ]: 8 : PG_FREE_IF_COPY(b, 1);
1049 : 8 : PG_RETURN_BOOL(res == 0);
1050 : : }
1051 : :
1052 : :
1053 : : Datum
1054 : 2 : cube_ne(PG_FUNCTION_ARGS)
1055 : : {
1056 : 2 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1057 : 2 : *b = PG_GETARG_NDBOX_P(1);
1058 : : int32 res;
1059 : :
1060 : 2 : res = cube_cmp_v0(a, b);
1061 : :
1062 [ - + ]: 2 : PG_FREE_IF_COPY(a, 0);
1063 [ - + ]: 2 : PG_FREE_IF_COPY(b, 1);
1064 : 2 : PG_RETURN_BOOL(res != 0);
1065 : : }
1066 : :
1067 : :
1068 : : Datum
1069 : 8 : cube_lt(PG_FUNCTION_ARGS)
1070 : : {
1071 : 8 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1072 : 8 : *b = PG_GETARG_NDBOX_P(1);
1073 : : int32 res;
1074 : :
1075 : 8 : res = cube_cmp_v0(a, b);
1076 : :
1077 [ - + ]: 8 : PG_FREE_IF_COPY(a, 0);
1078 [ - + ]: 8 : PG_FREE_IF_COPY(b, 1);
1079 : 8 : PG_RETURN_BOOL(res < 0);
1080 : : }
1081 : :
1082 : :
1083 : : Datum
1084 : 8 : cube_gt(PG_FUNCTION_ARGS)
1085 : : {
1086 : 8 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1087 : 8 : *b = PG_GETARG_NDBOX_P(1);
1088 : : int32 res;
1089 : :
1090 : 8 : res = cube_cmp_v0(a, b);
1091 : :
1092 [ - + ]: 8 : PG_FREE_IF_COPY(a, 0);
1093 [ - + ]: 8 : PG_FREE_IF_COPY(b, 1);
1094 : 8 : PG_RETURN_BOOL(res > 0);
1095 : : }
1096 : :
1097 : :
1098 : : Datum
1099 : 0 : cube_le(PG_FUNCTION_ARGS)
1100 : : {
1101 : 0 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1102 : 0 : *b = PG_GETARG_NDBOX_P(1);
1103 : : int32 res;
1104 : :
1105 : 0 : res = cube_cmp_v0(a, b);
1106 : :
1107 [ # # ]: 0 : PG_FREE_IF_COPY(a, 0);
1108 [ # # ]: 0 : PG_FREE_IF_COPY(b, 1);
1109 : 0 : PG_RETURN_BOOL(res <= 0);
1110 : : }
1111 : :
1112 : :
1113 : : Datum
1114 : 0 : cube_ge(PG_FUNCTION_ARGS)
1115 : : {
1116 : 0 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1117 : 0 : *b = PG_GETARG_NDBOX_P(1);
1118 : : int32 res;
1119 : :
1120 : 0 : res = cube_cmp_v0(a, b);
1121 : :
1122 [ # # ]: 0 : PG_FREE_IF_COPY(a, 0);
1123 [ # # ]: 0 : PG_FREE_IF_COPY(b, 1);
1124 : 0 : PG_RETURN_BOOL(res >= 0);
1125 : : }
1126 : :
1127 : :
1128 : : /* Contains */
1129 : : /* Box(A) CONTAINS Box(B) IFF pt(A) < pt(B) */
1130 : : bool
1131 : 94 : cube_contains_v0(NDBOX *a, NDBOX *b)
1132 : : {
1133 : : int i;
1134 : :
1135 [ + - - + ]: 94 : if ((a == NULL) || (b == NULL))
1136 : 0 : return false;
1137 : :
1138 [ - + ]: 94 : if (DIM(a) < DIM(b))
1139 : : {
1140 : : /*
1141 : : * the further comparisons will make sense if the excess dimensions of
1142 : : * (b) were zeroes Since both UL and UR coordinates must be zero, we
1143 : : * can check them all without worrying about which is which.
1144 : : */
1145 [ # # ]: 0 : for (i = DIM(a); i < DIM(b); i++)
1146 : : {
1147 [ # # ]: 0 : if (LL_COORD(b, i) != 0)
1148 : 0 : return false;
1149 [ # # # # ]: 0 : if (UR_COORD(b, i) != 0)
1150 : 0 : return false;
1151 : : }
1152 : : }
1153 : :
1154 : : /* Can't care less about the excess dimensions of (a), if any */
1155 [ + + ]: 190 : for (i = 0; i < Min(DIM(a), DIM(b)); i++)
1156 : : {
1157 [ + + + + : 312 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) >
+ + + + ]
1158 [ + + + + : 156 : Min(LL_COORD(b, i), UR_COORD(b, i)))
+ + ]
1159 : 7 : return false;
1160 [ + + + + : 298 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) <
+ + + + ]
1161 [ + + + + : 149 : Max(LL_COORD(b, i), UR_COORD(b, i)))
+ + ]
1162 : 53 : return false;
1163 : : }
1164 : :
1165 : 34 : return true;
1166 : : }
1167 : :
1168 : : Datum
1169 : 31 : cube_contains(PG_FUNCTION_ARGS)
1170 : : {
1171 : 31 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1172 : 31 : *b = PG_GETARG_NDBOX_P(1);
1173 : : bool res;
1174 : :
1175 : 31 : res = cube_contains_v0(a, b);
1176 : :
1177 [ - + ]: 31 : PG_FREE_IF_COPY(a, 0);
1178 [ - + ]: 31 : PG_FREE_IF_COPY(b, 1);
1179 : 31 : PG_RETURN_BOOL(res);
1180 : : }
1181 : :
1182 : : /* Contained */
1183 : : /* Box(A) Contained by Box(B) IFF Box(B) Contains Box(A) */
1184 : : Datum
1185 : 15 : cube_contained(PG_FUNCTION_ARGS)
1186 : : {
1187 : 15 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1188 : 15 : *b = PG_GETARG_NDBOX_P(1);
1189 : : bool res;
1190 : :
1191 : 15 : res = cube_contains_v0(b, a);
1192 : :
1193 [ - + ]: 15 : PG_FREE_IF_COPY(a, 0);
1194 [ - + ]: 15 : PG_FREE_IF_COPY(b, 1);
1195 : 15 : PG_RETURN_BOOL(res);
1196 : : }
1197 : :
1198 : : /* Overlap */
1199 : : /* Box(A) Overlap Box(B) IFF (pt(a)LL < pt(B)UR) && (pt(b)LL < pt(a)UR) */
1200 : : bool
1201 : 209 : cube_overlap_v0(NDBOX *a, NDBOX *b)
1202 : : {
1203 : : int i;
1204 : :
1205 [ + - - + ]: 209 : if ((a == NULL) || (b == NULL))
1206 : 0 : return false;
1207 : :
1208 : : /* swap the box pointers if needed */
1209 [ - + ]: 209 : if (DIM(a) < DIM(b))
1210 : : {
1211 : 0 : NDBOX *tmp = b;
1212 : :
1213 : 0 : b = a;
1214 : 0 : a = tmp;
1215 : : }
1216 : :
1217 : : /* compare within the dimensions of (b) */
1218 [ + + ]: 287 : for (i = 0; i < DIM(b); i++)
1219 : : {
1220 [ + + + + : 268 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) > Max(LL_COORD(b, i), UR_COORD(b, i)))
+ + + + +
+ + + +
+ ]
1221 : 188 : return false;
1222 [ + + + + : 80 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) < Min(LL_COORD(b, i), UR_COORD(b, i)))
+ + + + +
+ + + +
+ ]
1223 : 2 : return false;
1224 : : }
1225 : :
1226 : : /* compare to zero those dimensions in (a) absent in (b) */
1227 [ + + ]: 24 : for (i = DIM(b); i < DIM(a); i++)
1228 : : {
1229 [ + - + - : 5 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) > 0)
- - - + ]
1230 : 0 : return false;
1231 [ + - - + : 5 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) < 0)
- + - + ]
1232 : 0 : return false;
1233 : : }
1234 : :
1235 : 19 : return true;
1236 : : }
1237 : :
1238 : :
1239 : : Datum
1240 : 8 : cube_overlap(PG_FUNCTION_ARGS)
1241 : : {
1242 : 8 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1243 : 8 : *b = PG_GETARG_NDBOX_P(1);
1244 : : bool res;
1245 : :
1246 : 8 : res = cube_overlap_v0(a, b);
1247 : :
1248 [ - + ]: 8 : PG_FREE_IF_COPY(a, 0);
1249 [ - + ]: 8 : PG_FREE_IF_COPY(b, 1);
1250 : 8 : PG_RETURN_BOOL(res);
1251 : : }
1252 : :
1253 : :
1254 : : /* Distance */
1255 : : /*
1256 : : * The distance is computed as a per axis sum of the squared distances
1257 : : * between 1D projections of the boxes onto Cartesian axes. Assuming zero
1258 : : * distance between overlapping projections, this metric coincides with the
1259 : : * "common sense" geometric distance
1260 : : */
1261 : : Datum
1262 : 3423 : cube_distance(PG_FUNCTION_ARGS)
1263 : : {
1264 : 3423 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1265 : 3423 : *b = PG_GETARG_NDBOX_P(1);
1266 : 3423 : bool swapped = false;
1267 : : double d,
1268 : : distance;
1269 : : int i;
1270 : :
1271 : : /* swap the box pointers if needed */
1272 [ + + ]: 3423 : if (DIM(a) < DIM(b))
1273 : : {
1274 : 3 : NDBOX *tmp = b;
1275 : :
1276 : 3 : b = a;
1277 : 3 : a = tmp;
1278 : 3 : swapped = true;
1279 : : }
1280 : :
1281 : 3423 : distance = 0.0;
1282 : : /* compute within the dimensions of (b) */
1283 [ + + ]: 10102 : for (i = 0; i < DIM(b); i++)
1284 : : {
1285 [ + + + + ]: 6679 : d = distance_1D(LL_COORD(a, i), UR_COORD(a, i), LL_COORD(b, i), UR_COORD(b, i));
1286 : 6679 : distance += d * d;
1287 : : }
1288 : :
1289 : : /* compute distance to zero for those dimensions in (a) absent in (b) */
1290 [ + + ]: 3819 : for (i = DIM(b); i < DIM(a); i++)
1291 : : {
1292 [ + + ]: 396 : d = distance_1D(LL_COORD(a, i), UR_COORD(a, i), 0.0, 0.0);
1293 : 396 : distance += d * d;
1294 : : }
1295 : :
1296 [ + + ]: 3423 : if (swapped)
1297 : : {
1298 [ - + ]: 3 : PG_FREE_IF_COPY(b, 0);
1299 [ - + ]: 3 : PG_FREE_IF_COPY(a, 1);
1300 : : }
1301 : : else
1302 : : {
1303 [ - + ]: 3420 : PG_FREE_IF_COPY(a, 0);
1304 [ - + ]: 3420 : PG_FREE_IF_COPY(b, 1);
1305 : : }
1306 : :
1307 : 3423 : PG_RETURN_FLOAT8(sqrt(distance));
1308 : : }
1309 : :
1310 : : Datum
1311 : 3195 : distance_taxicab(PG_FUNCTION_ARGS)
1312 : : {
1313 : 3195 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1314 : 3195 : *b = PG_GETARG_NDBOX_P(1);
1315 : 3195 : bool swapped = false;
1316 : : double distance;
1317 : : int i;
1318 : :
1319 : : /* swap the box pointers if needed */
1320 [ + + ]: 3195 : if (DIM(a) < DIM(b))
1321 : : {
1322 : 1 : NDBOX *tmp = b;
1323 : :
1324 : 1 : b = a;
1325 : 1 : a = tmp;
1326 : 1 : swapped = true;
1327 : : }
1328 : :
1329 : 3195 : distance = 0.0;
1330 : : /* compute within the dimensions of (b) */
1331 [ + + ]: 9584 : for (i = 0; i < DIM(b); i++)
1332 [ + + ]: 6389 : distance += fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1333 [ + + ]: 6389 : LL_COORD(b, i), UR_COORD(b, i)));
1334 : :
1335 : : /* compute distance to zero for those dimensions in (a) absent in (b) */
1336 [ + + ]: 3196 : for (i = DIM(b); i < DIM(a); i++)
1337 [ - + ]: 1 : distance += fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1338 : : 0.0, 0.0));
1339 : :
1340 [ + + ]: 3195 : if (swapped)
1341 : : {
1342 [ - + ]: 1 : PG_FREE_IF_COPY(b, 0);
1343 [ - + ]: 1 : PG_FREE_IF_COPY(a, 1);
1344 : : }
1345 : : else
1346 : : {
1347 [ - + ]: 3194 : PG_FREE_IF_COPY(a, 0);
1348 [ - + ]: 3194 : PG_FREE_IF_COPY(b, 1);
1349 : : }
1350 : :
1351 : 3195 : PG_RETURN_FLOAT8(distance);
1352 : : }
1353 : :
1354 : : Datum
1355 : 3195 : distance_chebyshev(PG_FUNCTION_ARGS)
1356 : : {
1357 : 3195 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1358 : 3195 : *b = PG_GETARG_NDBOX_P(1);
1359 : 3195 : bool swapped = false;
1360 : : double d,
1361 : : distance;
1362 : : int i;
1363 : :
1364 : : /* swap the box pointers if needed */
1365 [ + + ]: 3195 : if (DIM(a) < DIM(b))
1366 : : {
1367 : 1 : NDBOX *tmp = b;
1368 : :
1369 : 1 : b = a;
1370 : 1 : a = tmp;
1371 : 1 : swapped = true;
1372 : : }
1373 : :
1374 : 3195 : distance = 0.0;
1375 : : /* compute within the dimensions of (b) */
1376 [ + + ]: 9584 : for (i = 0; i < DIM(b); i++)
1377 : : {
1378 [ + + ]: 6389 : d = fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1379 [ + + ]: 6389 : LL_COORD(b, i), UR_COORD(b, i)));
1380 [ + + ]: 6389 : if (d > distance)
1381 : 4720 : distance = d;
1382 : : }
1383 : :
1384 : : /* compute distance to zero for those dimensions in (a) absent in (b) */
1385 [ + + ]: 3196 : for (i = DIM(b); i < DIM(a); i++)
1386 : : {
1387 [ - + ]: 1 : d = fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i), 0.0, 0.0));
1388 [ - + ]: 1 : if (d > distance)
1389 : 0 : distance = d;
1390 : : }
1391 : :
1392 [ + + ]: 3195 : if (swapped)
1393 : : {
1394 [ - + ]: 1 : PG_FREE_IF_COPY(b, 0);
1395 [ - + ]: 1 : PG_FREE_IF_COPY(a, 1);
1396 : : }
1397 : : else
1398 : : {
1399 [ - + ]: 3194 : PG_FREE_IF_COPY(a, 0);
1400 [ - + ]: 3194 : PG_FREE_IF_COPY(b, 1);
1401 : : }
1402 : :
1403 : 3195 : PG_RETURN_FLOAT8(distance);
1404 : : }
1405 : :
1406 : : Datum
1407 : 4127 : g_cube_distance(PG_FUNCTION_ARGS)
1408 : : {
1409 : 4127 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1410 : 4127 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1411 : 4127 : NDBOX *cube = DatumGetNDBOXP(entry->key);
1412 : : double retval;
1413 : :
1414 [ + + ]: 4127 : if (strategy == CubeKNNDistanceCoord)
1415 : : {
1416 : : /*
1417 : : * Handle ordering by ~> operator. See comments of cube_coord_llur()
1418 : : * for details
1419 : : */
1420 : 3875 : int coord = PG_GETARG_INT32(1);
1421 : 3875 : bool isLeaf = GistPageIsLeaf(entry->page);
1422 : 3875 : bool inverse = false;
1423 : :
1424 : : /* 0 is the only unsupported coordinate value */
1425 [ - + ]: 3875 : if (coord == 0)
1426 [ # # ]: 0 : ereport(ERROR,
1427 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1428 : : errmsg("zero cube index is not defined")));
1429 : :
1430 : : /* Return inversed value for negative coordinate */
1431 [ + + ]: 3875 : if (coord < 0)
1432 : : {
1433 : 2381 : coord = -coord;
1434 : 2381 : inverse = true;
1435 : : }
1436 : :
1437 [ + + ]: 3875 : if (coord <= 2 * DIM(cube))
1438 : : {
1439 : : /* dimension index */
1440 : 3873 : int index = (coord - 1) / 2;
1441 : :
1442 : : /* whether this is upper bound (lower bound otherwise) */
1443 : 3873 : bool upper = ((coord - 1) % 2 == 1);
1444 : :
1445 [ + + ]: 3873 : if (IS_POINT(cube))
1446 : : {
1447 : 10 : retval = cube->x[index];
1448 : : }
1449 : : else
1450 : : {
1451 [ + + ]: 3863 : if (isLeaf)
1452 : : {
1453 : : /* For leaf just return required upper/lower bound */
1454 [ + + ]: 3583 : if (upper)
1455 [ + + ]: 1725 : retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
1456 : : else
1457 [ - + ]: 1858 : retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1458 : : }
1459 : : else
1460 : : {
1461 : : /*
1462 : : * For non-leaf we should always return lower bound,
1463 : : * because even upper bound of a child in the subtree can
1464 : : * be as small as our lower bound. For inversed case we
1465 : : * return upper bound because it becomes lower bound for
1466 : : * inversed value.
1467 : : */
1468 [ + + ]: 280 : if (!inverse)
1469 [ + - ]: 140 : retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1470 : : else
1471 [ - + ]: 140 : retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
1472 : : }
1473 : : }
1474 : : }
1475 : : else
1476 : : {
1477 : 2 : retval = 0.0;
1478 : : }
1479 : :
1480 : : /* Inverse return value if needed */
1481 [ + + ]: 3875 : if (inverse)
1482 : 2381 : retval = -retval;
1483 : : }
1484 : : else
1485 : : {
1486 : 252 : NDBOX *query = PG_GETARG_NDBOX_P(1);
1487 : :
1488 [ + + + - ]: 252 : switch (strategy)
1489 : : {
1490 : 84 : case CubeKNNDistanceTaxicab:
1491 : 84 : retval = DatumGetFloat8(DirectFunctionCall2(distance_taxicab,
1492 : : PointerGetDatum(cube), PointerGetDatum(query)));
1493 : 84 : break;
1494 : 84 : case CubeKNNDistanceEuclid:
1495 : 84 : retval = DatumGetFloat8(DirectFunctionCall2(cube_distance,
1496 : : PointerGetDatum(cube), PointerGetDatum(query)));
1497 : 84 : break;
1498 : 84 : case CubeKNNDistanceChebyshev:
1499 : 84 : retval = DatumGetFloat8(DirectFunctionCall2(distance_chebyshev,
1500 : : PointerGetDatum(cube), PointerGetDatum(query)));
1501 : 84 : break;
1502 : 0 : default:
1503 [ # # ]: 0 : elog(ERROR, "unrecognized cube strategy number: %d", strategy);
1504 : : retval = 0; /* keep compiler quiet */
1505 : : break;
1506 : : }
1507 : : }
1508 : 4127 : PG_RETURN_FLOAT8(retval);
1509 : : }
1510 : :
1511 : : static double
1512 : 19855 : distance_1D(double a1, double a2, double b1, double b2)
1513 : : {
1514 : : /* interval (a) is entirely on the left of (b) */
1515 [ + + + + : 19855 : if ((a1 <= b1) && (a2 <= b1) && (a1 <= b2) && (a2 <= b2))
+ - + - ]
1516 [ + + + + ]: 376 : return (Min(b1, b2) - Max(a1, a2));
1517 : :
1518 : : /* interval (a) is entirely on the right of (b) */
1519 [ + + + + : 19479 : if ((a1 > b1) && (a2 > b1) && (a1 > b2) && (a2 > b2))
+ + + + ]
1520 [ + + - + ]: 19244 : return (Min(a1, a2) - Max(b1, b2));
1521 : :
1522 : : /* the rest are all sorts of intersections */
1523 : 235 : return 0.0;
1524 : : }
1525 : :
1526 : : /* Test if a box is also a point */
1527 : : Datum
1528 : 201 : cube_is_point(PG_FUNCTION_ARGS)
1529 : : {
1530 : 201 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1531 : : bool result;
1532 : :
1533 : 201 : result = cube_is_point_internal(cube);
1534 [ - + ]: 201 : PG_FREE_IF_COPY(cube, 0);
1535 : 201 : PG_RETURN_BOOL(result);
1536 : : }
1537 : :
1538 : : static bool
1539 : 718155 : cube_is_point_internal(NDBOX *cube)
1540 : : {
1541 : : int i;
1542 : :
1543 [ + + ]: 718155 : if (IS_POINT(cube))
1544 : 297 : return true;
1545 : :
1546 : : /*
1547 : : * Even if the point-flag is not set, all the lower-left coordinates might
1548 : : * match the upper-right coordinates, so that the value is in fact a
1549 : : * point. Such values don't arise with current code - the point flag is
1550 : : * always set if appropriate - but they might be present on-disk in
1551 : : * clusters upgraded from pre-9.4 versions.
1552 : : */
1553 [ + + ]: 717992 : for (i = 0; i < DIM(cube); i++)
1554 : : {
1555 [ - + + + ]: 717980 : if (LL_COORD(cube, i) != UR_COORD(cube, i))
1556 : 717846 : return false;
1557 : : }
1558 : 12 : return true;
1559 : : }
1560 : :
1561 : : /* Return dimensions in use in the data structure */
1562 : : Datum
1563 : 200 : cube_dim(PG_FUNCTION_ARGS)
1564 : : {
1565 : 200 : NDBOX *c = PG_GETARG_NDBOX_P(0);
1566 : 200 : int dim = DIM(c);
1567 : :
1568 [ - + ]: 200 : PG_FREE_IF_COPY(c, 0);
1569 : 200 : PG_RETURN_INT32(dim);
1570 : : }
1571 : :
1572 : : /* Return a specific normalized LL coordinate */
1573 : : Datum
1574 : 151 : cube_ll_coord(PG_FUNCTION_ARGS)
1575 : : {
1576 : 151 : NDBOX *c = PG_GETARG_NDBOX_P(0);
1577 : 151 : int n = PG_GETARG_INT32(1);
1578 : : double result;
1579 : :
1580 [ + + + - ]: 151 : if (DIM(c) >= n && n > 0)
1581 [ + + + + : 148 : result = Min(LL_COORD(c, n - 1), UR_COORD(c, n - 1));
+ + ]
1582 : : else
1583 : 3 : result = 0;
1584 : :
1585 [ - + ]: 151 : PG_FREE_IF_COPY(c, 0);
1586 : 151 : PG_RETURN_FLOAT8(result);
1587 : : }
1588 : :
1589 : : /* Return a specific normalized UR coordinate */
1590 : : Datum
1591 : 18 : cube_ur_coord(PG_FUNCTION_ARGS)
1592 : : {
1593 : 18 : NDBOX *c = PG_GETARG_NDBOX_P(0);
1594 : 18 : int n = PG_GETARG_INT32(1);
1595 : : double result;
1596 : :
1597 [ + + + - ]: 18 : if (DIM(c) >= n && n > 0)
1598 [ + + + + : 15 : result = Max(LL_COORD(c, n - 1), UR_COORD(c, n - 1));
+ + ]
1599 : : else
1600 : 3 : result = 0;
1601 : :
1602 [ - + ]: 18 : PG_FREE_IF_COPY(c, 0);
1603 : 18 : PG_RETURN_FLOAT8(result);
1604 : : }
1605 : :
1606 : : /*
1607 : : * Function returns cube coordinate.
1608 : : * Numbers from 1 to DIM denotes first corner coordinates.
1609 : : * Numbers from DIM+1 to 2*DIM denotes second corner coordinates.
1610 : : */
1611 : : Datum
1612 : 10 : cube_coord(PG_FUNCTION_ARGS)
1613 : : {
1614 : 10 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1615 : 10 : int coord = PG_GETARG_INT32(1);
1616 : :
1617 [ + + + + ]: 10 : if (coord <= 0 || coord > 2 * DIM(cube))
1618 [ + - ]: 5 : ereport(ERROR,
1619 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1620 : : errmsg("cube index %d is out of bounds", coord)));
1621 : :
1622 [ + + ]: 5 : if (IS_POINT(cube))
1623 : 2 : PG_RETURN_FLOAT8(cube->x[(coord - 1) % DIM(cube)]);
1624 : : else
1625 : 3 : PG_RETURN_FLOAT8(cube->x[coord - 1]);
1626 : : }
1627 : :
1628 : :
1629 : : /*----
1630 : : * This function works like cube_coord(), but rearranges coordinates in the
1631 : : * way suitable to support coordinate ordering using KNN-GiST. For historical
1632 : : * reasons this extension allows us to create cubes in form ((2,1),(1,2)) and
1633 : : * instead of normalizing such cube to ((1,1),(2,2)) it stores cube in original
1634 : : * way. But in order to get cubes ordered by one of dimensions from the index
1635 : : * without explicit sort step we need this representation-independent coordinate
1636 : : * getter. Moreover, indexed dataset may contain cubes of different dimensions
1637 : : * number. Accordingly, this coordinate getter should be able to return
1638 : : * lower/upper bound for particular dimension independently on number of cube
1639 : : * dimensions. Also, KNN-GiST supports only ascending sorting. In order to
1640 : : * support descending sorting, this function returns inverse of value when
1641 : : * negative coordinate is given.
1642 : : *
1643 : : * Long story short, this function uses following meaning of coordinates:
1644 : : * # (2 * N - 1) -- lower bound of Nth dimension,
1645 : : * # (2 * N) -- upper bound of Nth dimension,
1646 : : * # - (2 * N - 1) -- negative of lower bound of Nth dimension,
1647 : : * # - (2 * N) -- negative of upper bound of Nth dimension.
1648 : : *
1649 : : * When given coordinate exceeds number of cube dimensions, then 0 returned
1650 : : * (reproducing logic of GiST indexing of variable-length cubes).
1651 : : */
1652 : : Datum
1653 : 24953 : cube_coord_llur(PG_FUNCTION_ARGS)
1654 : : {
1655 : 24953 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1656 : 24953 : int coord = PG_GETARG_INT32(1);
1657 : 24953 : bool inverse = false;
1658 : : float8 result;
1659 : :
1660 : : /* 0 is the only unsupported coordinate value */
1661 [ + + ]: 24953 : if (coord == 0)
1662 [ + - ]: 1 : ereport(ERROR,
1663 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1664 : : errmsg("zero cube index is not defined")));
1665 : :
1666 : : /* Return inversed value for negative coordinate */
1667 [ + + ]: 24952 : if (coord < 0)
1668 : : {
1669 : 12473 : coord = -coord;
1670 : 12473 : inverse = true;
1671 : : }
1672 : :
1673 [ + + ]: 24952 : if (coord <= 2 * DIM(cube))
1674 : : {
1675 : : /* dimension index */
1676 : 24946 : int index = (coord - 1) / 2;
1677 : :
1678 : : /* whether this is upper bound (lower bound otherwise) */
1679 : 24946 : bool upper = ((coord - 1) % 2 == 1);
1680 : :
1681 [ + + ]: 24946 : if (IS_POINT(cube))
1682 : : {
1683 : 30 : result = cube->x[index];
1684 : : }
1685 : : else
1686 : : {
1687 [ + + ]: 24916 : if (upper)
1688 [ + + ]: 12457 : result = Max(cube->x[index], cube->x[index + DIM(cube)]);
1689 : : else
1690 [ + + ]: 12459 : result = Min(cube->x[index], cube->x[index + DIM(cube)]);
1691 : : }
1692 : : }
1693 : : else
1694 : : {
1695 : : /*
1696 : : * Return zero if coordinate is out of bound. That reproduces logic
1697 : : * of how cubes with low dimension number are expanded during GiST
1698 : : * indexing.
1699 : : */
1700 : 6 : result = 0.0;
1701 : : }
1702 : :
1703 : : /* Inverse value if needed */
1704 [ + + ]: 24952 : if (inverse)
1705 : 12473 : result = -result;
1706 : :
1707 : 24952 : PG_RETURN_FLOAT8(result);
1708 : : }
1709 : :
1710 : : /* Increase or decrease box size by a radius in at least n dimensions. */
1711 : : Datum
1712 : 54 : cube_enlarge(PG_FUNCTION_ARGS)
1713 : : {
1714 : 54 : NDBOX *a = PG_GETARG_NDBOX_P(0);
1715 : 54 : double r = PG_GETARG_FLOAT8(1);
1716 : 54 : int32 n = PG_GETARG_INT32(2);
1717 : : NDBOX *result;
1718 : 54 : int dim = 0;
1719 : : int size;
1720 : : int i,
1721 : : j;
1722 : :
1723 [ - + ]: 54 : if (n > CUBE_MAX_DIM)
1724 : 0 : n = CUBE_MAX_DIM;
1725 [ + + + + ]: 54 : if (r > 0 && n > 0)
1726 : 40 : dim = n;
1727 [ + + ]: 54 : if (DIM(a) > dim)
1728 : 15 : dim = DIM(a);
1729 : :
1730 : 54 : size = CUBE_SIZE(dim);
1731 : 54 : result = (NDBOX *) palloc0(size);
1732 : 54 : SET_VARSIZE(result, size);
1733 : 54 : SET_DIM(result, dim);
1734 : :
1735 [ + + ]: 188 : for (i = 0, j = dim; i < DIM(a); i++, j++)
1736 : : {
1737 [ + + + + ]: 134 : if (LL_COORD(a, i) >= UR_COORD(a, i))
1738 : : {
1739 [ + + ]: 126 : result->x[i] = UR_COORD(a, i) - r;
1740 : 126 : result->x[j] = LL_COORD(a, i) + r;
1741 : : }
1742 : : else
1743 : : {
1744 : 8 : result->x[i] = LL_COORD(a, i) - r;
1745 [ - + ]: 8 : result->x[j] = UR_COORD(a, i) + r;
1746 : : }
1747 [ + + ]: 134 : if (result->x[i] > result->x[j])
1748 : : {
1749 : 8 : result->x[i] = (result->x[i] + result->x[j]) / 2;
1750 : 8 : result->x[j] = result->x[i];
1751 : : }
1752 : : }
1753 : : /* dim > a->dim only if r > 0 */
1754 [ + + ]: 58 : for (; i < dim; i++, j++)
1755 : : {
1756 : 4 : result->x[i] = -r;
1757 : 4 : result->x[j] = r;
1758 : : }
1759 : :
1760 : : /*
1761 : : * Check if the result was in fact a point, and set the flag in the datum
1762 : : * accordingly. (we don't bother to repalloc it smaller)
1763 : : */
1764 [ + + ]: 54 : if (cube_is_point_internal(result))
1765 : : {
1766 : 8 : size = POINT_SIZE(dim);
1767 : 8 : SET_VARSIZE(result, size);
1768 : 8 : SET_POINT_BIT(result);
1769 : : }
1770 : :
1771 [ - + ]: 54 : PG_FREE_IF_COPY(a, 0);
1772 : 54 : PG_RETURN_NDBOX_P(result);
1773 : : }
1774 : :
1775 : : /* Create a one dimensional box with identical upper and lower coordinates */
1776 : : Datum
1777 : 194 : cube_f8(PG_FUNCTION_ARGS)
1778 : : {
1779 : 194 : double x = PG_GETARG_FLOAT8(0);
1780 : : NDBOX *result;
1781 : : int size;
1782 : :
1783 : 194 : size = POINT_SIZE(1);
1784 : 194 : result = (NDBOX *) palloc0(size);
1785 : 194 : SET_VARSIZE(result, size);
1786 : 194 : SET_DIM(result, 1);
1787 : 194 : SET_POINT_BIT(result);
1788 : 194 : result->x[0] = x;
1789 : :
1790 : 194 : PG_RETURN_NDBOX_P(result);
1791 : : }
1792 : :
1793 : : /* Create a one dimensional box */
1794 : : Datum
1795 : 12 : cube_f8_f8(PG_FUNCTION_ARGS)
1796 : : {
1797 : 12 : double x0 = PG_GETARG_FLOAT8(0);
1798 : 12 : double x1 = PG_GETARG_FLOAT8(1);
1799 : : NDBOX *result;
1800 : : int size;
1801 : :
1802 [ + + ]: 12 : if (x0 == x1)
1803 : : {
1804 : 4 : size = POINT_SIZE(1);
1805 : 4 : result = (NDBOX *) palloc0(size);
1806 : 4 : SET_VARSIZE(result, size);
1807 : 4 : SET_DIM(result, 1);
1808 : 4 : SET_POINT_BIT(result);
1809 : 4 : result->x[0] = x0;
1810 : : }
1811 : : else
1812 : : {
1813 : 8 : size = CUBE_SIZE(1);
1814 : 8 : result = (NDBOX *) palloc0(size);
1815 : 8 : SET_VARSIZE(result, size);
1816 : 8 : SET_DIM(result, 1);
1817 : 8 : result->x[0] = x0;
1818 : 8 : result->x[1] = x1;
1819 : : }
1820 : :
1821 : 12 : PG_RETURN_NDBOX_P(result);
1822 : : }
1823 : :
1824 : : /*
1825 : : * Add a dimension to an existing cube with the same values for the new
1826 : : * coordinate
1827 : : */
1828 : : Datum
1829 : 387 : cube_c_f8(PG_FUNCTION_ARGS)
1830 : : {
1831 : 387 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1832 : 387 : double x = PG_GETARG_FLOAT8(1);
1833 : : NDBOX *result;
1834 : : int size;
1835 : : int i;
1836 : :
1837 [ + + ]: 387 : if (DIM(cube) + 1 > CUBE_MAX_DIM)
1838 [ + - ]: 1 : ereport(ERROR,
1839 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1840 : : errmsg("can't extend cube"),
1841 : : errdetail("A cube cannot have more than %d dimensions.",
1842 : : CUBE_MAX_DIM)));
1843 : :
1844 [ + + ]: 386 : if (IS_POINT(cube))
1845 : : {
1846 : 383 : size = POINT_SIZE((DIM(cube) + 1));
1847 : 383 : result = (NDBOX *) palloc0(size);
1848 : 383 : SET_VARSIZE(result, size);
1849 : 383 : SET_DIM(result, DIM(cube) + 1);
1850 : 383 : SET_POINT_BIT(result);
1851 [ + + ]: 957 : for (i = 0; i < DIM(cube); i++)
1852 : 574 : result->x[i] = cube->x[i];
1853 : 383 : result->x[DIM(result) - 1] = x;
1854 : : }
1855 : : else
1856 : : {
1857 : 3 : size = CUBE_SIZE((DIM(cube) + 1));
1858 : 3 : result = (NDBOX *) palloc0(size);
1859 : 3 : SET_VARSIZE(result, size);
1860 : 3 : SET_DIM(result, DIM(cube) + 1);
1861 [ + + ]: 7 : for (i = 0; i < DIM(cube); i++)
1862 : : {
1863 : 4 : result->x[i] = cube->x[i];
1864 : 4 : result->x[DIM(result) + i] = cube->x[DIM(cube) + i];
1865 : : }
1866 : 3 : result->x[DIM(result) - 1] = x;
1867 : 3 : result->x[2 * DIM(result) - 1] = x;
1868 : : }
1869 : :
1870 [ - + ]: 386 : PG_FREE_IF_COPY(cube, 0);
1871 : 386 : PG_RETURN_NDBOX_P(result);
1872 : : }
1873 : :
1874 : : /* Add a dimension to an existing cube */
1875 : : Datum
1876 : 9 : cube_c_f8_f8(PG_FUNCTION_ARGS)
1877 : : {
1878 : 9 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1879 : 9 : double x1 = PG_GETARG_FLOAT8(1);
1880 : 9 : double x2 = PG_GETARG_FLOAT8(2);
1881 : : NDBOX *result;
1882 : : int size;
1883 : : int i;
1884 : :
1885 [ + + ]: 9 : if (DIM(cube) + 1 > CUBE_MAX_DIM)
1886 [ + - ]: 1 : ereport(ERROR,
1887 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1888 : : errmsg("can't extend cube"),
1889 : : errdetail("A cube cannot have more than %d dimensions.",
1890 : : CUBE_MAX_DIM)));
1891 : :
1892 [ + + + + ]: 8 : if (IS_POINT(cube) && (x1 == x2))
1893 : : {
1894 : 1 : size = POINT_SIZE((DIM(cube) + 1));
1895 : 1 : result = (NDBOX *) palloc0(size);
1896 : 1 : SET_VARSIZE(result, size);
1897 : 1 : SET_DIM(result, DIM(cube) + 1);
1898 : 1 : SET_POINT_BIT(result);
1899 [ + + ]: 2 : for (i = 0; i < DIM(cube); i++)
1900 : 1 : result->x[i] = cube->x[i];
1901 : 1 : result->x[DIM(result) - 1] = x1;
1902 : : }
1903 : : else
1904 : : {
1905 : 7 : size = CUBE_SIZE((DIM(cube) + 1));
1906 : 7 : result = (NDBOX *) palloc0(size);
1907 : 7 : SET_VARSIZE(result, size);
1908 : 7 : SET_DIM(result, DIM(cube) + 1);
1909 [ + + ]: 15 : for (i = 0; i < DIM(cube); i++)
1910 : : {
1911 : 8 : result->x[i] = LL_COORD(cube, i);
1912 [ + + ]: 8 : result->x[DIM(result) + i] = UR_COORD(cube, i);
1913 : : }
1914 : 7 : result->x[DIM(result) - 1] = x1;
1915 : 7 : result->x[2 * DIM(result) - 1] = x2;
1916 : : }
1917 : :
1918 [ - + ]: 8 : PG_FREE_IF_COPY(cube, 0);
1919 : 8 : PG_RETURN_NDBOX_P(result);
1920 : : }
|
