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