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