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;
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 12 : PG_FUNCTION_INFO_V1(cube_in);
32 8 : PG_FUNCTION_INFO_V1(cube_a_f8_f8);
33 8 : PG_FUNCTION_INFO_V1(cube_a_f8);
34 10 : PG_FUNCTION_INFO_V1(cube_out);
35 6 : PG_FUNCTION_INFO_V1(cube_send);
36 6 : PG_FUNCTION_INFO_V1(cube_recv);
37 10 : PG_FUNCTION_INFO_V1(cube_f8);
38 8 : PG_FUNCTION_INFO_V1(cube_f8_f8);
39 10 : PG_FUNCTION_INFO_V1(cube_c_f8);
40 8 : PG_FUNCTION_INFO_V1(cube_c_f8_f8);
41 10 : PG_FUNCTION_INFO_V1(cube_dim);
42 10 : PG_FUNCTION_INFO_V1(cube_ll_coord);
43 10 : PG_FUNCTION_INFO_V1(cube_ur_coord);
44 8 : PG_FUNCTION_INFO_V1(cube_coord);
45 8 : PG_FUNCTION_INFO_V1(cube_coord_llur);
46 8 : PG_FUNCTION_INFO_V1(cube_subset);
47 :
48 : /*
49 : ** GiST support methods
50 : */
51 :
52 8 : PG_FUNCTION_INFO_V1(g_cube_consistent);
53 6 : PG_FUNCTION_INFO_V1(g_cube_compress);
54 6 : PG_FUNCTION_INFO_V1(g_cube_decompress);
55 8 : PG_FUNCTION_INFO_V1(g_cube_penalty);
56 8 : PG_FUNCTION_INFO_V1(g_cube_picksplit);
57 8 : PG_FUNCTION_INFO_V1(g_cube_union);
58 8 : PG_FUNCTION_INFO_V1(g_cube_same);
59 8 : PG_FUNCTION_INFO_V1(g_cube_distance);
60 :
61 : /*
62 : ** B-tree support functions
63 : */
64 8 : PG_FUNCTION_INFO_V1(cube_eq);
65 8 : PG_FUNCTION_INFO_V1(cube_ne);
66 8 : PG_FUNCTION_INFO_V1(cube_lt);
67 8 : PG_FUNCTION_INFO_V1(cube_gt);
68 6 : PG_FUNCTION_INFO_V1(cube_le);
69 6 : PG_FUNCTION_INFO_V1(cube_ge);
70 8 : PG_FUNCTION_INFO_V1(cube_cmp);
71 :
72 : /*
73 : ** R-tree support functions
74 : */
75 :
76 10 : PG_FUNCTION_INFO_V1(cube_contains);
77 8 : PG_FUNCTION_INFO_V1(cube_contained);
78 8 : PG_FUNCTION_INFO_V1(cube_overlap);
79 8 : PG_FUNCTION_INFO_V1(cube_union);
80 8 : PG_FUNCTION_INFO_V1(cube_inter);
81 8 : PG_FUNCTION_INFO_V1(cube_size);
82 :
83 : /*
84 : ** miscellaneous
85 : */
86 8 : PG_FUNCTION_INFO_V1(distance_taxicab);
87 10 : PG_FUNCTION_INFO_V1(cube_distance);
88 8 : PG_FUNCTION_INFO_V1(distance_chebyshev);
89 10 : PG_FUNCTION_INFO_V1(cube_is_point);
90 10 : 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 6870 : cube_in(PG_FUNCTION_ARGS)
119 : {
120 6870 : char *str = PG_GETARG_CSTRING(0);
121 : NDBOX *result;
122 : Size scanbuflen;
123 :
124 6870 : cube_scanner_init(str, &scanbuflen);
125 :
126 6870 : cube_yyparse(&result, scanbuflen, fcinfo->context);
127 :
128 : /* We might as well run this even on failure. */
129 6810 : cube_scanner_finish();
130 :
131 6810 : PG_RETURN_NDBOX_P(result);
132 : }
133 :
134 :
135 : /*
136 : ** Allows the construction of a cube from 2 float[]'s
137 : */
138 : Datum
139 44 : cube_a_f8_f8(PG_FUNCTION_ARGS)
140 : {
141 44 : ArrayType *ur = PG_GETARG_ARRAYTYPE_P(0);
142 44 : ArrayType *ll = PG_GETARG_ARRAYTYPE_P(1);
143 : NDBOX *result;
144 : int i;
145 : int dim;
146 : int size;
147 : bool point;
148 : double *dur,
149 : *dll;
150 :
151 44 : if (array_contains_nulls(ur) || array_contains_nulls(ll))
152 0 : ereport(ERROR,
153 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
154 : errmsg("cannot work with arrays containing NULLs")));
155 :
156 44 : dim = ARRNELEMS(ur);
157 44 : if (dim > CUBE_MAX_DIM)
158 2 : ereport(ERROR,
159 : (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 42 : if (ARRNELEMS(ll) != dim)
165 2 : ereport(ERROR,
166 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
167 : errmsg("UR and LL arrays must be of same length")));
168 :
169 40 : dur = ARRPTR(ur);
170 40 : dll = ARRPTR(ll);
171 :
172 : /* Check if it's a point */
173 40 : point = true;
174 446 : for (i = 0; i < dim; i++)
175 : {
176 440 : if (dur[i] != dll[i])
177 : {
178 34 : point = false;
179 34 : break;
180 : }
181 : }
182 :
183 40 : size = point ? POINT_SIZE(dim) : CUBE_SIZE(dim);
184 40 : result = (NDBOX *) palloc0(size);
185 40 : SET_VARSIZE(result, size);
186 40 : SET_DIM(result, dim);
187 :
188 548 : for (i = 0; i < dim; i++)
189 508 : result->x[i] = dur[i];
190 :
191 40 : if (!point)
192 : {
193 136 : for (i = 0; i < dim; i++)
194 102 : result->x[i + dim] = dll[i];
195 : }
196 : else
197 6 : SET_POINT_BIT(result);
198 :
199 40 : PG_RETURN_NDBOX_P(result);
200 : }
201 :
202 : /*
203 : ** Allows the construction of a zero-volume cube from a float[]
204 : */
205 : Datum
206 16 : cube_a_f8(PG_FUNCTION_ARGS)
207 : {
208 16 : ArrayType *ur = PG_GETARG_ARRAYTYPE_P(0);
209 : NDBOX *result;
210 : int i;
211 : int dim;
212 : int size;
213 : double *dur;
214 :
215 16 : if (array_contains_nulls(ur))
216 0 : ereport(ERROR,
217 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
218 : errmsg("cannot work with arrays containing NULLs")));
219 :
220 16 : dim = ARRNELEMS(ur);
221 16 : if (dim > CUBE_MAX_DIM)
222 2 : ereport(ERROR,
223 : (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 14 : dur = ARRPTR(ur);
229 :
230 14 : size = POINT_SIZE(dim);
231 14 : result = (NDBOX *) palloc0(size);
232 14 : SET_VARSIZE(result, size);
233 14 : SET_DIM(result, dim);
234 14 : SET_POINT_BIT(result);
235 :
236 446 : for (i = 0; i < dim; i++)
237 432 : result->x[i] = dur[i];
238 :
239 14 : PG_RETURN_NDBOX_P(result);
240 : }
241 :
242 : Datum
243 12 : cube_subset(PG_FUNCTION_ARGS)
244 : {
245 12 : NDBOX *c = PG_GETARG_NDBOX_P(0);
246 12 : ArrayType *idx = PG_GETARG_ARRAYTYPE_P(1);
247 : NDBOX *result;
248 : int size,
249 : dim,
250 : i;
251 : int *dx;
252 :
253 12 : if (array_contains_nulls(idx))
254 0 : ereport(ERROR,
255 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
256 : errmsg("cannot work with arrays containing NULLs")));
257 :
258 12 : dx = (int32 *) ARR_DATA_PTR(idx);
259 :
260 12 : dim = ARRNELEMS(idx);
261 12 : if (dim > CUBE_MAX_DIM)
262 2 : ereport(ERROR,
263 : (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 10 : size = IS_POINT(c) ? POINT_SIZE(dim) : CUBE_SIZE(dim);
269 10 : result = (NDBOX *) palloc0(size);
270 10 : SET_VARSIZE(result, size);
271 10 : SET_DIM(result, dim);
272 :
273 10 : if (IS_POINT(c))
274 6 : SET_POINT_BIT(result);
275 :
276 226 : for (i = 0; i < dim; i++)
277 : {
278 220 : if ((dx[i] <= 0) || (dx[i] > DIM(c)))
279 4 : ereport(ERROR,
280 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
281 : errmsg("Index out of bounds")));
282 216 : result->x[i] = c->x[dx[i] - 1];
283 216 : if (!IS_POINT(c))
284 8 : result->x[i + dim] = c->x[dx[i] + DIM(c) - 1];
285 : }
286 :
287 6 : PG_FREE_IF_COPY(c, 0);
288 6 : PG_RETURN_NDBOX_P(result);
289 : }
290 :
291 : Datum
292 778 : cube_out(PG_FUNCTION_ARGS)
293 : {
294 778 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
295 : StringInfoData buf;
296 778 : int dim = DIM(cube);
297 : int i;
298 :
299 778 : initStringInfo(&buf);
300 :
301 778 : appendStringInfoChar(&buf, '(');
302 2870 : for (i = 0; i < dim; i++)
303 : {
304 2092 : if (i > 0)
305 1318 : appendStringInfoString(&buf, ", ");
306 2092 : appendStringInfoString(&buf, float8out_internal(LL_COORD(cube, i)));
307 : }
308 778 : appendStringInfoChar(&buf, ')');
309 :
310 778 : if (!cube_is_point_internal(cube))
311 : {
312 580 : appendStringInfoString(&buf, ",(");
313 1760 : for (i = 0; i < dim; i++)
314 : {
315 1180 : if (i > 0)
316 600 : appendStringInfoString(&buf, ", ");
317 1180 : appendStringInfoString(&buf, float8out_internal(UR_COORD(cube, i)));
318 : }
319 580 : appendStringInfoChar(&buf, ')');
320 : }
321 :
322 778 : PG_FREE_IF_COPY(cube, 0);
323 778 : PG_RETURN_CSTRING(buf.data);
324 : }
325 :
326 : /*
327 : * cube_send - a binary output handler for cube type
328 : */
329 : Datum
330 0 : cube_send(PG_FUNCTION_ARGS)
331 : {
332 0 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
333 : StringInfoData buf;
334 : int32 i,
335 0 : nitems = DIM(cube);
336 :
337 0 : pq_begintypsend(&buf);
338 0 : pq_sendint32(&buf, cube->header);
339 0 : if (!IS_POINT(cube))
340 0 : nitems += nitems;
341 : /* for symmetry with cube_recv, we don't use LL_COORD/UR_COORD here */
342 0 : for (i = 0; i < nitems; i++)
343 0 : pq_sendfloat8(&buf, cube->x[i]);
344 :
345 0 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
346 : }
347 :
348 : /*
349 : * cube_recv - a binary input handler for cube type
350 : */
351 : Datum
352 0 : cube_recv(PG_FUNCTION_ARGS)
353 : {
354 0 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
355 : int32 header;
356 : int32 i,
357 : nitems;
358 : NDBOX *cube;
359 :
360 0 : header = pq_getmsgint(buf, sizeof(int32));
361 0 : nitems = (header & DIM_MASK);
362 0 : if (nitems > CUBE_MAX_DIM)
363 0 : ereport(ERROR,
364 : (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 0 : if ((header & POINT_BIT) == 0)
369 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 :
376 0 : PG_RETURN_NDBOX_P(cube);
377 : }
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 498 : g_cube_consistent(PG_FUNCTION_ARGS)
392 : {
393 498 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
394 498 : NDBOX *query = PG_GETARG_NDBOX_P(1);
395 498 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
396 :
397 : /* Oid subtype = PG_GETARG_OID(3); */
398 498 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
399 : bool res;
400 :
401 : /* All cases served by this function are exact */
402 498 : *recheck = false;
403 :
404 : /*
405 : * if entry is not leaf, use g_cube_internal_consistent, else use
406 : * g_cube_leaf_consistent
407 : */
408 498 : if (GIST_LEAF(entry))
409 288 : res = g_cube_leaf_consistent(DatumGetNDBOXP(entry->key),
410 : query, strategy);
411 : else
412 210 : res = g_cube_internal_consistent(DatumGetNDBOXP(entry->key),
413 : query, strategy);
414 :
415 498 : PG_FREE_IF_COPY(query, 1);
416 498 : PG_RETURN_BOOL(res);
417 : }
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 5924 : g_cube_union(PG_FUNCTION_ARGS)
426 : {
427 5924 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
428 5924 : int *sizep = (int *) PG_GETARG_POINTER(1);
429 5924 : NDBOX *out = (NDBOX *) NULL;
430 : NDBOX *tmp;
431 : int i;
432 :
433 5924 : tmp = DatumGetNDBOXP(entryvec->vector[0].key);
434 :
435 : /*
436 : * sizep = sizeof(NDBOX); -- NDBOX has variable size
437 : */
438 5924 : *sizep = VARSIZE(tmp);
439 :
440 11848 : for (i = 1; i < entryvec->n; i++)
441 : {
442 5924 : out = g_cube_binary_union(tmp,
443 5924 : DatumGetNDBOXP(entryvec->vector[i].key),
444 : sizep);
445 5924 : tmp = out;
446 : }
447 :
448 5924 : PG_RETURN_POINTER(out);
449 : }
450 :
451 : /*
452 : ** GiST Compress and Decompress methods for boxes
453 : ** do not do anything.
454 : */
455 :
456 : Datum
457 0 : g_cube_compress(PG_FUNCTION_ARGS)
458 : {
459 0 : PG_RETURN_DATUM(PG_GETARG_DATUM(0));
460 : }
461 :
462 : Datum
463 0 : g_cube_decompress(PG_FUNCTION_ARGS)
464 : {
465 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
466 0 : NDBOX *key = DatumGetNDBOXP(entry->key);
467 :
468 0 : if (key != DatumGetNDBOXP(entry->key))
469 : {
470 0 : GISTENTRY *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
471 :
472 0 : gistentryinit(*retval, PointerGetDatum(key),
473 : entry->rel, entry->page,
474 : entry->offset, false);
475 0 : PG_RETURN_POINTER(retval);
476 : }
477 0 : PG_RETURN_POINTER(entry);
478 : }
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 86928 : g_cube_penalty(PG_FUNCTION_ARGS)
487 : {
488 86928 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
489 86928 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
490 86928 : float *result = (float *) PG_GETARG_POINTER(2);
491 : NDBOX *ud;
492 : double tmp1,
493 : tmp2;
494 :
495 86928 : ud = cube_union_v0(DatumGetNDBOXP(origentry->key),
496 86928 : DatumGetNDBOXP(newentry->key));
497 86928 : rt_cube_size(ud, &tmp1);
498 86928 : rt_cube_size(DatumGetNDBOXP(origentry->key), &tmp2);
499 86928 : *result = (float) (tmp1 - tmp2);
500 :
501 86928 : PG_RETURN_FLOAT8(*result);
502 : }
503 :
504 :
505 :
506 : /*
507 : ** The GiST PickSplit method for boxes
508 : ** We use Guttman's poly time split algorithm
509 : */
510 : Datum
511 68 : g_cube_picksplit(PG_FUNCTION_ARGS)
512 : {
513 68 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
514 68 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
515 : 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 68 : OffsetNumber seed_1 = 1,
536 68 : seed_2 = 2;
537 : OffsetNumber *left,
538 : *right;
539 : OffsetNumber maxoff;
540 :
541 68 : maxoff = entryvec->n - 2;
542 68 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
543 68 : v->spl_left = (OffsetNumber *) palloc(nbytes);
544 68 : v->spl_right = (OffsetNumber *) palloc(nbytes);
545 :
546 68 : firsttime = true;
547 68 : waste = 0.0;
548 :
549 9520 : for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
550 : {
551 9452 : datum_alpha = DatumGetNDBOXP(entryvec->vector[i].key);
552 671092 : for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
553 : {
554 661640 : datum_beta = DatumGetNDBOXP(entryvec->vector[j].key);
555 :
556 : /* compute the wasted space by unioning these guys */
557 : /* size_waste = size_union - size_inter; */
558 661640 : union_d = cube_union_v0(datum_alpha, datum_beta);
559 661640 : rt_cube_size(union_d, &size_union);
560 661640 : inter_d = DatumGetNDBOXP(DirectFunctionCall2(cube_inter,
561 : entryvec->vector[i].key,
562 : entryvec->vector[j].key));
563 661640 : rt_cube_size(inter_d, &size_inter);
564 661640 : size_waste = size_union - size_inter;
565 :
566 : /*
567 : * are these a more promising split than what we've already seen?
568 : */
569 :
570 661640 : if (size_waste > waste || firsttime)
571 : {
572 912 : waste = size_waste;
573 912 : seed_1 = i;
574 912 : seed_2 = j;
575 912 : firsttime = false;
576 : }
577 : }
578 : }
579 :
580 68 : left = v->spl_left;
581 68 : v->spl_nleft = 0;
582 68 : right = v->spl_right;
583 68 : v->spl_nright = 0;
584 :
585 68 : datum_alpha = DatumGetNDBOXP(entryvec->vector[seed_1].key);
586 68 : datum_l = cube_union_v0(datum_alpha, datum_alpha);
587 68 : rt_cube_size(datum_l, &size_l);
588 68 : datum_beta = DatumGetNDBOXP(entryvec->vector[seed_2].key);
589 68 : datum_r = cube_union_v0(datum_beta, datum_beta);
590 68 : rt_cube_size(datum_r, &size_r);
591 :
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 68 : maxoff = OffsetNumberNext(maxoff);
605 9656 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
606 : {
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 9588 : if (i == seed_1)
614 : {
615 68 : *left++ = i;
616 68 : v->spl_nleft++;
617 68 : continue;
618 : }
619 9520 : else if (i == seed_2)
620 : {
621 68 : *right++ = i;
622 68 : v->spl_nright++;
623 68 : continue;
624 : }
625 :
626 : /* okay, which page needs least enlargement? */
627 9452 : datum_alpha = DatumGetNDBOXP(entryvec->vector[i].key);
628 9452 : union_dl = cube_union_v0(datum_l, datum_alpha);
629 9452 : union_dr = cube_union_v0(datum_r, datum_alpha);
630 9452 : rt_cube_size(union_dl, &size_alpha);
631 9452 : rt_cube_size(union_dr, &size_beta);
632 :
633 : /* pick which page to add it to */
634 9452 : if (size_alpha - size_l < size_beta - size_r)
635 : {
636 4556 : datum_l = union_dl;
637 4556 : size_l = size_alpha;
638 4556 : *left++ = i;
639 4556 : v->spl_nleft++;
640 : }
641 : else
642 : {
643 4896 : datum_r = union_dr;
644 4896 : size_r = size_beta;
645 4896 : *right++ = i;
646 4896 : v->spl_nright++;
647 : }
648 : }
649 68 : *left = *right = FirstOffsetNumber; /* sentinel value */
650 :
651 68 : v->spl_ldatum = PointerGetDatum(datum_l);
652 68 : v->spl_rdatum = PointerGetDatum(datum_r);
653 :
654 68 : PG_RETURN_POINTER(v);
655 : }
656 :
657 : /*
658 : ** Equality method
659 : */
660 : Datum
661 5924 : g_cube_same(PG_FUNCTION_ARGS)
662 : {
663 5924 : NDBOX *b1 = PG_GETARG_NDBOX_P(0);
664 5924 : NDBOX *b2 = PG_GETARG_NDBOX_P(1);
665 5924 : bool *result = (bool *) PG_GETARG_POINTER(2);
666 :
667 5924 : if (cube_cmp_v0(b1, b2) == 0)
668 5614 : *result = true;
669 : else
670 310 : *result = false;
671 :
672 5924 : PG_RETURN_NDBOX_P(result);
673 : }
674 :
675 : /*
676 : ** SUPPORT ROUTINES
677 : */
678 : bool
679 288 : g_cube_leaf_consistent(NDBOX *key,
680 : NDBOX *query,
681 : StrategyNumber strategy)
682 : {
683 : bool retval;
684 :
685 288 : switch (strategy)
686 : {
687 192 : case RTOverlapStrategyNumber:
688 192 : retval = cube_overlap_v0(key, query);
689 192 : break;
690 0 : case RTSameStrategyNumber:
691 0 : retval = (cube_cmp_v0(key, query) == 0);
692 0 : break;
693 0 : case RTContainsStrategyNumber:
694 : case RTOldContainsStrategyNumber:
695 0 : retval = cube_contains_v0(key, query);
696 0 : break;
697 96 : case RTContainedByStrategyNumber:
698 : case RTOldContainedByStrategyNumber:
699 96 : retval = cube_contains_v0(query, key);
700 96 : break;
701 0 : default:
702 0 : retval = false;
703 : }
704 288 : return retval;
705 : }
706 :
707 : bool
708 210 : g_cube_internal_consistent(NDBOX *key,
709 : NDBOX *query,
710 : StrategyNumber strategy)
711 : {
712 : bool retval;
713 :
714 210 : switch (strategy)
715 : {
716 140 : case RTOverlapStrategyNumber:
717 140 : retval = (bool) cube_overlap_v0(key, query);
718 140 : break;
719 0 : case RTSameStrategyNumber:
720 : case RTContainsStrategyNumber:
721 : case RTOldContainsStrategyNumber:
722 0 : retval = (bool) cube_contains_v0(key, query);
723 0 : break;
724 70 : case RTContainedByStrategyNumber:
725 : case RTOldContainedByStrategyNumber:
726 70 : retval = (bool) cube_overlap_v0(key, query);
727 70 : break;
728 0 : default:
729 0 : retval = false;
730 : }
731 210 : return retval;
732 : }
733 :
734 : NDBOX *
735 5924 : g_cube_binary_union(NDBOX *r1, NDBOX *r2, int *sizep)
736 : {
737 : NDBOX *retval;
738 :
739 5924 : retval = cube_union_v0(r1, r2);
740 5924 : *sizep = VARSIZE(retval);
741 :
742 5924 : return retval;
743 : }
744 :
745 :
746 : /* cube_union_v0 */
747 : NDBOX *
748 773542 : cube_union_v0(NDBOX *a, NDBOX *b)
749 : {
750 : int i;
751 : NDBOX *result;
752 : int dim;
753 : int size;
754 :
755 : /* trivial case */
756 773542 : if (a == b)
757 136 : return a;
758 :
759 : /* swap the arguments if needed, so that 'a' is always larger than 'b' */
760 773406 : if (DIM(a) < DIM(b))
761 : {
762 6 : NDBOX *tmp = b;
763 :
764 6 : b = a;
765 6 : a = tmp;
766 : }
767 773406 : dim = DIM(a);
768 :
769 773406 : size = CUBE_SIZE(dim);
770 773406 : result = palloc0(size);
771 773406 : SET_VARSIZE(result, size);
772 773406 : SET_DIM(result, dim);
773 :
774 : /* First compute the union of the dimensions present in both args */
775 2320146 : for (i = 0; i < DIM(b); i++)
776 : {
777 1546740 : result->x[i] = Min(Min(LL_COORD(a, i), UR_COORD(a, i)),
778 : Min(LL_COORD(b, i), UR_COORD(b, i)));
779 1546740 : result->x[i + DIM(a)] = Max(Max(LL_COORD(a, i), UR_COORD(a, i)),
780 : Max(LL_COORD(b, i), UR_COORD(b, i)));
781 : }
782 : /* continue on the higher dimensions only present in 'a' */
783 773486 : for (; i < DIM(a); i++)
784 : {
785 80 : result->x[i] = Min(0,
786 : Min(LL_COORD(a, i), UR_COORD(a, i))
787 : );
788 80 : result->x[i + dim] = Max(0,
789 : 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 773406 : if (cube_is_point_internal(result))
798 : {
799 4 : size = POINT_SIZE(dim);
800 4 : SET_VARSIZE(result, size);
801 4 : SET_POINT_BIT(result);
802 : }
803 :
804 773406 : return result;
805 : }
806 :
807 : Datum
808 10 : cube_union(PG_FUNCTION_ARGS)
809 : {
810 10 : NDBOX *a = PG_GETARG_NDBOX_P(0);
811 10 : NDBOX *b = PG_GETARG_NDBOX_P(1);
812 : NDBOX *res;
813 :
814 10 : res = cube_union_v0(a, b);
815 :
816 10 : PG_FREE_IF_COPY(a, 0);
817 10 : PG_FREE_IF_COPY(b, 1);
818 10 : PG_RETURN_NDBOX_P(res);
819 : }
820 :
821 : /* cube_inter */
822 : Datum
823 661654 : cube_inter(PG_FUNCTION_ARGS)
824 : {
825 661654 : NDBOX *a = PG_GETARG_NDBOX_P(0);
826 661654 : NDBOX *b = PG_GETARG_NDBOX_P(1);
827 : NDBOX *result;
828 661654 : bool swapped = false;
829 : int i;
830 : int dim;
831 : int size;
832 :
833 : /* swap the arguments if needed, so that 'a' is always larger than 'b' */
834 661654 : if (DIM(a) < DIM(b))
835 : {
836 0 : NDBOX *tmp = b;
837 :
838 0 : b = a;
839 0 : a = tmp;
840 0 : swapped = true;
841 : }
842 661654 : dim = DIM(a);
843 :
844 661654 : size = CUBE_SIZE(dim);
845 661654 : result = (NDBOX *) palloc0(size);
846 661654 : SET_VARSIZE(result, size);
847 661654 : SET_DIM(result, dim);
848 :
849 : /* First compute intersection of the dimensions present in both args */
850 1984966 : for (i = 0; i < DIM(b); i++)
851 : {
852 1323312 : result->x[i] = Max(Min(LL_COORD(a, i), UR_COORD(a, i)),
853 : Min(LL_COORD(b, i), UR_COORD(b, i)));
854 1323312 : result->x[i + DIM(a)] = Min(Max(LL_COORD(a, i), UR_COORD(a, i)),
855 : Max(LL_COORD(b, i), UR_COORD(b, i)));
856 : }
857 : /* continue on the higher dimensions only present in 'a' */
858 661654 : for (; i < DIM(a); i++)
859 : {
860 0 : result->x[i] = Max(0,
861 : Min(LL_COORD(a, i), UR_COORD(a, i))
862 : );
863 0 : result->x[i + DIM(a)] = Min(0,
864 : 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 661654 : if (cube_is_point_internal(result))
873 : {
874 4 : size = POINT_SIZE(dim);
875 4 : result = repalloc(result, size);
876 4 : SET_VARSIZE(result, size);
877 4 : SET_POINT_BIT(result);
878 : }
879 :
880 661654 : if (swapped)
881 : {
882 0 : PG_FREE_IF_COPY(b, 0);
883 0 : PG_FREE_IF_COPY(a, 1);
884 : }
885 : else
886 : {
887 661654 : PG_FREE_IF_COPY(a, 0);
888 661654 : PG_FREE_IF_COPY(b, 1);
889 : }
890 :
891 : /*
892 : * Is it OK to return a non-null intersection for non-overlapping boxes?
893 : */
894 661654 : PG_RETURN_NDBOX_P(result);
895 : }
896 :
897 : /* cube_size */
898 : Datum
899 4 : cube_size(PG_FUNCTION_ARGS)
900 : {
901 4 : NDBOX *a = PG_GETARG_NDBOX_P(0);
902 : double result;
903 :
904 4 : rt_cube_size(a, &result);
905 4 : PG_FREE_IF_COPY(a, 0);
906 4 : PG_RETURN_FLOAT8(result);
907 : }
908 :
909 : void
910 1516180 : rt_cube_size(NDBOX *a, double *size)
911 : {
912 : double result;
913 : int i;
914 :
915 1516180 : if (a == (NDBOX *) NULL)
916 : {
917 : /* special case for GiST */
918 0 : result = 0.0;
919 : }
920 1516180 : else if (IS_POINT(a) || DIM(a) == 0)
921 : {
922 : /* necessarily has zero size */
923 2 : result = 0.0;
924 : }
925 : else
926 : {
927 1516178 : result = 1.0;
928 4548534 : for (i = 0; i < DIM(a); i++)
929 3032356 : result *= fabs(UR_COORD(a, i) - LL_COORD(a, i));
930 : }
931 1516180 : *size = result;
932 1516180 : }
933 :
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 6020 : cube_cmp_v0(NDBOX *a, NDBOX *b)
938 : {
939 : int i;
940 : int dim;
941 :
942 6020 : dim = Min(DIM(a), DIM(b));
943 :
944 : /* compare the common dimensions */
945 17718 : for (i = 0; i < dim; i++)
946 : {
947 23824 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) >
948 11912 : Min(LL_COORD(b, i), UR_COORD(b, i)))
949 184 : return 1;
950 23456 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) <
951 11728 : Min(LL_COORD(b, i), UR_COORD(b, i)))
952 30 : return -1;
953 : }
954 17178 : for (i = 0; i < dim; i++)
955 : {
956 23064 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) >
957 11532 : Max(LL_COORD(b, i), UR_COORD(b, i)))
958 0 : return 1;
959 23064 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) <
960 11532 : Max(LL_COORD(b, i), UR_COORD(b, i)))
961 160 : return -1;
962 : }
963 :
964 : /* compare extra dimensions to zero */
965 5646 : if (DIM(a) > DIM(b))
966 : {
967 48 : for (i = dim; i < DIM(a); i++)
968 : {
969 36 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) > 0)
970 0 : return 1;
971 36 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) < 0)
972 0 : return -1;
973 : }
974 40 : for (i = dim; i < DIM(a); i++)
975 : {
976 36 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) > 0)
977 8 : return 1;
978 28 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) < 0)
979 0 : return -1;
980 : }
981 :
982 : /*
983 : * if all common dimensions are equal, the cube with more dimensions
984 : * wins
985 : */
986 4 : return 1;
987 : }
988 5634 : if (DIM(a) < DIM(b))
989 : {
990 64 : for (i = dim; i < DIM(b); i++)
991 : {
992 48 : if (Min(LL_COORD(b, i), UR_COORD(b, i)) > 0)
993 0 : return -1;
994 48 : if (Min(LL_COORD(b, i), UR_COORD(b, i)) < 0)
995 0 : return 1;
996 : }
997 54 : for (i = dim; i < DIM(b); i++)
998 : {
999 48 : if (Max(LL_COORD(b, i), UR_COORD(b, i)) > 0)
1000 10 : return -1;
1001 38 : if (Max(LL_COORD(b, i), UR_COORD(b, i)) < 0)
1002 0 : return 1;
1003 : }
1004 :
1005 : /*
1006 : * if all common dimensions are equal, the cube with more dimensions
1007 : * wins
1008 : */
1009 6 : return -1;
1010 : }
1011 :
1012 : /* They're really equal */
1013 5618 : return 0;
1014 : }
1015 :
1016 : Datum
1017 44 : cube_cmp(PG_FUNCTION_ARGS)
1018 : {
1019 44 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1020 44 : *b = PG_GETARG_NDBOX_P(1);
1021 : int32 res;
1022 :
1023 44 : res = cube_cmp_v0(a, b);
1024 :
1025 44 : PG_FREE_IF_COPY(a, 0);
1026 44 : PG_FREE_IF_COPY(b, 1);
1027 44 : PG_RETURN_INT32(res);
1028 : }
1029 :
1030 :
1031 : Datum
1032 16 : cube_eq(PG_FUNCTION_ARGS)
1033 : {
1034 16 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1035 16 : *b = PG_GETARG_NDBOX_P(1);
1036 : int32 res;
1037 :
1038 16 : res = cube_cmp_v0(a, b);
1039 :
1040 16 : PG_FREE_IF_COPY(a, 0);
1041 16 : PG_FREE_IF_COPY(b, 1);
1042 16 : PG_RETURN_BOOL(res == 0);
1043 : }
1044 :
1045 :
1046 : Datum
1047 4 : cube_ne(PG_FUNCTION_ARGS)
1048 : {
1049 4 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1050 4 : *b = PG_GETARG_NDBOX_P(1);
1051 : int32 res;
1052 :
1053 4 : res = cube_cmp_v0(a, b);
1054 :
1055 4 : PG_FREE_IF_COPY(a, 0);
1056 4 : PG_FREE_IF_COPY(b, 1);
1057 4 : PG_RETURN_BOOL(res != 0);
1058 : }
1059 :
1060 :
1061 : Datum
1062 16 : cube_lt(PG_FUNCTION_ARGS)
1063 : {
1064 16 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1065 16 : *b = PG_GETARG_NDBOX_P(1);
1066 : int32 res;
1067 :
1068 16 : res = cube_cmp_v0(a, b);
1069 :
1070 16 : PG_FREE_IF_COPY(a, 0);
1071 16 : PG_FREE_IF_COPY(b, 1);
1072 16 : PG_RETURN_BOOL(res < 0);
1073 : }
1074 :
1075 :
1076 : Datum
1077 16 : cube_gt(PG_FUNCTION_ARGS)
1078 : {
1079 16 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1080 16 : *b = PG_GETARG_NDBOX_P(1);
1081 : int32 res;
1082 :
1083 16 : res = cube_cmp_v0(a, b);
1084 :
1085 16 : PG_FREE_IF_COPY(a, 0);
1086 16 : PG_FREE_IF_COPY(b, 1);
1087 16 : PG_RETURN_BOOL(res > 0);
1088 : }
1089 :
1090 :
1091 : Datum
1092 0 : cube_le(PG_FUNCTION_ARGS)
1093 : {
1094 0 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1095 0 : *b = PG_GETARG_NDBOX_P(1);
1096 : int32 res;
1097 :
1098 0 : res = cube_cmp_v0(a, b);
1099 :
1100 0 : PG_FREE_IF_COPY(a, 0);
1101 0 : PG_FREE_IF_COPY(b, 1);
1102 0 : PG_RETURN_BOOL(res <= 0);
1103 : }
1104 :
1105 :
1106 : Datum
1107 0 : cube_ge(PG_FUNCTION_ARGS)
1108 : {
1109 0 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1110 0 : *b = PG_GETARG_NDBOX_P(1);
1111 : int32 res;
1112 :
1113 0 : res = cube_cmp_v0(a, b);
1114 :
1115 0 : PG_FREE_IF_COPY(a, 0);
1116 0 : PG_FREE_IF_COPY(b, 1);
1117 0 : PG_RETURN_BOOL(res >= 0);
1118 : }
1119 :
1120 :
1121 : /* Contains */
1122 : /* Box(A) CONTAINS Box(B) IFF pt(A) < pt(B) */
1123 : bool
1124 188 : cube_contains_v0(NDBOX *a, NDBOX *b)
1125 : {
1126 : int i;
1127 :
1128 188 : if ((a == NULL) || (b == NULL))
1129 0 : return false;
1130 :
1131 188 : if (DIM(a) < DIM(b))
1132 : {
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 0 : for (i = DIM(a); i < DIM(b); i++)
1139 : {
1140 0 : if (LL_COORD(b, i) != 0)
1141 0 : return false;
1142 0 : if (UR_COORD(b, i) != 0)
1143 0 : return false;
1144 : }
1145 : }
1146 :
1147 : /* Can't care less about the excess dimensions of (a), if any */
1148 380 : for (i = 0; i < Min(DIM(a), DIM(b)); i++)
1149 : {
1150 624 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) >
1151 312 : Min(LL_COORD(b, i), UR_COORD(b, i)))
1152 14 : return false;
1153 596 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) <
1154 298 : Max(LL_COORD(b, i), UR_COORD(b, i)))
1155 106 : return false;
1156 : }
1157 :
1158 68 : return true;
1159 : }
1160 :
1161 : Datum
1162 62 : cube_contains(PG_FUNCTION_ARGS)
1163 : {
1164 62 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1165 62 : *b = PG_GETARG_NDBOX_P(1);
1166 : bool res;
1167 :
1168 62 : res = cube_contains_v0(a, b);
1169 :
1170 62 : PG_FREE_IF_COPY(a, 0);
1171 62 : PG_FREE_IF_COPY(b, 1);
1172 62 : PG_RETURN_BOOL(res);
1173 : }
1174 :
1175 : /* Contained */
1176 : /* Box(A) Contained by Box(B) IFF Box(B) Contains Box(A) */
1177 : Datum
1178 30 : cube_contained(PG_FUNCTION_ARGS)
1179 : {
1180 30 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1181 30 : *b = PG_GETARG_NDBOX_P(1);
1182 : bool res;
1183 :
1184 30 : res = cube_contains_v0(b, a);
1185 :
1186 30 : PG_FREE_IF_COPY(a, 0);
1187 30 : PG_FREE_IF_COPY(b, 1);
1188 30 : PG_RETURN_BOOL(res);
1189 : }
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 418 : cube_overlap_v0(NDBOX *a, NDBOX *b)
1195 : {
1196 : int i;
1197 :
1198 418 : if ((a == NULL) || (b == NULL))
1199 0 : return false;
1200 :
1201 : /* swap the box pointers if needed */
1202 418 : if (DIM(a) < DIM(b))
1203 : {
1204 0 : NDBOX *tmp = b;
1205 :
1206 0 : b = a;
1207 0 : a = tmp;
1208 : }
1209 :
1210 : /* compare within the dimensions of (b) */
1211 574 : for (i = 0; i < DIM(b); i++)
1212 : {
1213 536 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) > Max(LL_COORD(b, i), UR_COORD(b, i)))
1214 376 : return false;
1215 160 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) < Min(LL_COORD(b, i), UR_COORD(b, i)))
1216 4 : return false;
1217 : }
1218 :
1219 : /* compare to zero those dimensions in (a) absent in (b) */
1220 48 : for (i = DIM(b); i < DIM(a); i++)
1221 : {
1222 10 : if (Min(LL_COORD(a, i), UR_COORD(a, i)) > 0)
1223 0 : return false;
1224 10 : if (Max(LL_COORD(a, i), UR_COORD(a, i)) < 0)
1225 0 : return false;
1226 : }
1227 :
1228 38 : return true;
1229 : }
1230 :
1231 :
1232 : Datum
1233 16 : cube_overlap(PG_FUNCTION_ARGS)
1234 : {
1235 16 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1236 16 : *b = PG_GETARG_NDBOX_P(1);
1237 : bool res;
1238 :
1239 16 : res = cube_overlap_v0(a, b);
1240 :
1241 16 : PG_FREE_IF_COPY(a, 0);
1242 16 : PG_FREE_IF_COPY(b, 1);
1243 16 : PG_RETURN_BOOL(res);
1244 : }
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 6846 : cube_distance(PG_FUNCTION_ARGS)
1254 : {
1255 6846 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1256 6846 : *b = PG_GETARG_NDBOX_P(1);
1257 6846 : bool swapped = false;
1258 : double d,
1259 : distance;
1260 : int i;
1261 :
1262 : /* swap the box pointers if needed */
1263 6846 : if (DIM(a) < DIM(b))
1264 : {
1265 6 : NDBOX *tmp = b;
1266 :
1267 6 : b = a;
1268 6 : a = tmp;
1269 6 : swapped = true;
1270 : }
1271 :
1272 6846 : distance = 0.0;
1273 : /* compute within the dimensions of (b) */
1274 20204 : for (i = 0; i < DIM(b); i++)
1275 : {
1276 13358 : d = distance_1D(LL_COORD(a, i), UR_COORD(a, i), LL_COORD(b, i), UR_COORD(b, i));
1277 13358 : distance += d * d;
1278 : }
1279 :
1280 : /* compute distance to zero for those dimensions in (a) absent in (b) */
1281 7638 : for (i = DIM(b); i < DIM(a); i++)
1282 : {
1283 792 : d = distance_1D(LL_COORD(a, i), UR_COORD(a, i), 0.0, 0.0);
1284 792 : distance += d * d;
1285 : }
1286 :
1287 6846 : if (swapped)
1288 : {
1289 6 : PG_FREE_IF_COPY(b, 0);
1290 6 : PG_FREE_IF_COPY(a, 1);
1291 : }
1292 : else
1293 : {
1294 6840 : PG_FREE_IF_COPY(a, 0);
1295 6840 : PG_FREE_IF_COPY(b, 1);
1296 : }
1297 :
1298 6846 : PG_RETURN_FLOAT8(sqrt(distance));
1299 : }
1300 :
1301 : Datum
1302 6390 : distance_taxicab(PG_FUNCTION_ARGS)
1303 : {
1304 6390 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1305 6390 : *b = PG_GETARG_NDBOX_P(1);
1306 6390 : bool swapped = false;
1307 : double distance;
1308 : int i;
1309 :
1310 : /* swap the box pointers if needed */
1311 6390 : if (DIM(a) < DIM(b))
1312 : {
1313 2 : NDBOX *tmp = b;
1314 :
1315 2 : b = a;
1316 2 : a = tmp;
1317 2 : swapped = true;
1318 : }
1319 :
1320 6390 : distance = 0.0;
1321 : /* compute within the dimensions of (b) */
1322 19168 : for (i = 0; i < DIM(b); i++)
1323 12778 : distance += fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1324 12778 : LL_COORD(b, i), UR_COORD(b, i)));
1325 :
1326 : /* compute distance to zero for those dimensions in (a) absent in (b) */
1327 6392 : for (i = DIM(b); i < DIM(a); i++)
1328 2 : distance += fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1329 : 0.0, 0.0));
1330 :
1331 6390 : if (swapped)
1332 : {
1333 2 : PG_FREE_IF_COPY(b, 0);
1334 2 : PG_FREE_IF_COPY(a, 1);
1335 : }
1336 : else
1337 : {
1338 6388 : PG_FREE_IF_COPY(a, 0);
1339 6388 : PG_FREE_IF_COPY(b, 1);
1340 : }
1341 :
1342 6390 : PG_RETURN_FLOAT8(distance);
1343 : }
1344 :
1345 : Datum
1346 6390 : distance_chebyshev(PG_FUNCTION_ARGS)
1347 : {
1348 6390 : NDBOX *a = PG_GETARG_NDBOX_P(0),
1349 6390 : *b = PG_GETARG_NDBOX_P(1);
1350 6390 : bool swapped = false;
1351 : double d,
1352 : distance;
1353 : int i;
1354 :
1355 : /* swap the box pointers if needed */
1356 6390 : if (DIM(a) < DIM(b))
1357 : {
1358 2 : NDBOX *tmp = b;
1359 :
1360 2 : b = a;
1361 2 : a = tmp;
1362 2 : swapped = true;
1363 : }
1364 :
1365 6390 : distance = 0.0;
1366 : /* compute within the dimensions of (b) */
1367 19168 : for (i = 0; i < DIM(b); i++)
1368 : {
1369 12778 : d = fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1370 12778 : LL_COORD(b, i), UR_COORD(b, i)));
1371 12778 : if (d > distance)
1372 9440 : distance = d;
1373 : }
1374 :
1375 : /* compute distance to zero for those dimensions in (a) absent in (b) */
1376 6392 : for (i = DIM(b); i < DIM(a); i++)
1377 : {
1378 2 : d = fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i), 0.0, 0.0));
1379 2 : if (d > distance)
1380 0 : distance = d;
1381 : }
1382 :
1383 6390 : if (swapped)
1384 : {
1385 2 : PG_FREE_IF_COPY(b, 0);
1386 2 : PG_FREE_IF_COPY(a, 1);
1387 : }
1388 : else
1389 : {
1390 6388 : PG_FREE_IF_COPY(a, 0);
1391 6388 : PG_FREE_IF_COPY(b, 1);
1392 : }
1393 :
1394 6390 : PG_RETURN_FLOAT8(distance);
1395 : }
1396 :
1397 : Datum
1398 8246 : g_cube_distance(PG_FUNCTION_ARGS)
1399 : {
1400 8246 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1401 8246 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1402 8246 : NDBOX *cube = DatumGetNDBOXP(entry->key);
1403 : double retval;
1404 :
1405 8246 : if (strategy == CubeKNNDistanceCoord)
1406 : {
1407 : /*
1408 : * Handle ordering by ~> operator. See comments of cube_coord_llur()
1409 : * for details
1410 : */
1411 7742 : int coord = PG_GETARG_INT32(1);
1412 7742 : bool isLeaf = GistPageIsLeaf(entry->page);
1413 7742 : bool inverse = false;
1414 :
1415 : /* 0 is the only unsupported coordinate value */
1416 7742 : if (coord == 0)
1417 0 : ereport(ERROR,
1418 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1419 : errmsg("zero cube index is not defined")));
1420 :
1421 : /* Return inversed value for negative coordinate */
1422 7742 : if (coord < 0)
1423 : {
1424 4750 : coord = -coord;
1425 4750 : inverse = true;
1426 : }
1427 :
1428 7742 : if (coord <= 2 * DIM(cube))
1429 : {
1430 : /* dimension index */
1431 7738 : int index = (coord - 1) / 2;
1432 :
1433 : /* whether this is upper bound (lower bound otherwise) */
1434 7738 : bool upper = ((coord - 1) % 2 == 1);
1435 :
1436 7738 : if (IS_POINT(cube))
1437 : {
1438 20 : retval = cube->x[index];
1439 : }
1440 : else
1441 : {
1442 7718 : if (isLeaf)
1443 : {
1444 : /* For leaf just return required upper/lower bound */
1445 7158 : if (upper)
1446 3446 : retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
1447 : else
1448 3712 : retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1449 : }
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 560 : if (!inverse)
1460 280 : retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1461 : else
1462 280 : retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
1463 : }
1464 : }
1465 : }
1466 : else
1467 : {
1468 4 : retval = 0.0;
1469 : }
1470 :
1471 : /* Inverse return value if needed */
1472 7742 : if (inverse)
1473 4750 : retval = -retval;
1474 : }
1475 : else
1476 : {
1477 504 : NDBOX *query = PG_GETARG_NDBOX_P(1);
1478 :
1479 504 : switch (strategy)
1480 : {
1481 168 : case CubeKNNDistanceTaxicab:
1482 168 : retval = DatumGetFloat8(DirectFunctionCall2(distance_taxicab,
1483 : PointerGetDatum(cube), PointerGetDatum(query)));
1484 168 : break;
1485 168 : case CubeKNNDistanceEuclid:
1486 168 : retval = DatumGetFloat8(DirectFunctionCall2(cube_distance,
1487 : PointerGetDatum(cube), PointerGetDatum(query)));
1488 168 : break;
1489 168 : case CubeKNNDistanceChebyshev:
1490 168 : retval = DatumGetFloat8(DirectFunctionCall2(distance_chebyshev,
1491 : PointerGetDatum(cube), PointerGetDatum(query)));
1492 168 : break;
1493 0 : default:
1494 0 : elog(ERROR, "unrecognized cube strategy number: %d", strategy);
1495 : retval = 0; /* keep compiler quiet */
1496 : break;
1497 : }
1498 : }
1499 8246 : PG_RETURN_FLOAT8(retval);
1500 : }
1501 :
1502 : static double
1503 39710 : distance_1D(double a1, double a2, double b1, double b2)
1504 : {
1505 : /* interval (a) is entirely on the left of (b) */
1506 39710 : if ((a1 <= b1) && (a2 <= b1) && (a1 <= b2) && (a2 <= b2))
1507 752 : return (Min(b1, b2) - Max(a1, a2));
1508 :
1509 : /* interval (a) is entirely on the right of (b) */
1510 38958 : if ((a1 > b1) && (a2 > b1) && (a1 > b2) && (a2 > b2))
1511 38488 : return (Min(a1, a2) - Max(b1, b2));
1512 :
1513 : /* the rest are all sorts of intersections */
1514 470 : return 0.0;
1515 : }
1516 :
1517 : /* Test if a box is also a point */
1518 : Datum
1519 402 : cube_is_point(PG_FUNCTION_ARGS)
1520 : {
1521 402 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1522 : bool result;
1523 :
1524 402 : result = cube_is_point_internal(cube);
1525 402 : PG_FREE_IF_COPY(cube, 0);
1526 402 : PG_RETURN_BOOL(result);
1527 : }
1528 :
1529 : static bool
1530 1436348 : cube_is_point_internal(NDBOX *cube)
1531 : {
1532 : int i;
1533 :
1534 1436348 : if (IS_POINT(cube))
1535 594 : return true;
1536 :
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 1436026 : for (i = 0; i < DIM(cube); i++)
1545 : {
1546 1436002 : if (LL_COORD(cube, i) != UR_COORD(cube, i))
1547 1435730 : return false;
1548 : }
1549 24 : return true;
1550 : }
1551 :
1552 : /* Return dimensions in use in the data structure */
1553 : Datum
1554 400 : cube_dim(PG_FUNCTION_ARGS)
1555 : {
1556 400 : NDBOX *c = PG_GETARG_NDBOX_P(0);
1557 400 : int dim = DIM(c);
1558 :
1559 400 : PG_FREE_IF_COPY(c, 0);
1560 400 : PG_RETURN_INT32(dim);
1561 : }
1562 :
1563 : /* Return a specific normalized LL coordinate */
1564 : Datum
1565 302 : cube_ll_coord(PG_FUNCTION_ARGS)
1566 : {
1567 302 : NDBOX *c = PG_GETARG_NDBOX_P(0);
1568 302 : int n = PG_GETARG_INT32(1);
1569 : double result;
1570 :
1571 302 : if (DIM(c) >= n && n > 0)
1572 296 : result = Min(LL_COORD(c, n - 1), UR_COORD(c, n - 1));
1573 : else
1574 6 : result = 0;
1575 :
1576 302 : PG_FREE_IF_COPY(c, 0);
1577 302 : PG_RETURN_FLOAT8(result);
1578 : }
1579 :
1580 : /* Return a specific normalized UR coordinate */
1581 : Datum
1582 36 : cube_ur_coord(PG_FUNCTION_ARGS)
1583 : {
1584 36 : NDBOX *c = PG_GETARG_NDBOX_P(0);
1585 36 : int n = PG_GETARG_INT32(1);
1586 : double result;
1587 :
1588 36 : if (DIM(c) >= n && n > 0)
1589 30 : result = Max(LL_COORD(c, n - 1), UR_COORD(c, n - 1));
1590 : else
1591 6 : result = 0;
1592 :
1593 36 : PG_FREE_IF_COPY(c, 0);
1594 36 : PG_RETURN_FLOAT8(result);
1595 : }
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 20 : cube_coord(PG_FUNCTION_ARGS)
1604 : {
1605 20 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1606 20 : int coord = PG_GETARG_INT32(1);
1607 :
1608 20 : if (coord <= 0 || coord > 2 * DIM(cube))
1609 10 : ereport(ERROR,
1610 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1611 : errmsg("cube index %d is out of bounds", coord)));
1612 :
1613 10 : if (IS_POINT(cube))
1614 4 : PG_RETURN_FLOAT8(cube->x[(coord - 1) % DIM(cube)]);
1615 : else
1616 6 : PG_RETURN_FLOAT8(cube->x[coord - 1]);
1617 : }
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 49906 : cube_coord_llur(PG_FUNCTION_ARGS)
1645 : {
1646 49906 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1647 49906 : int coord = PG_GETARG_INT32(1);
1648 49906 : bool inverse = false;
1649 : float8 result;
1650 :
1651 : /* 0 is the only unsupported coordinate value */
1652 49906 : if (coord == 0)
1653 2 : ereport(ERROR,
1654 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1655 : errmsg("zero cube index is not defined")));
1656 :
1657 : /* Return inversed value for negative coordinate */
1658 49904 : if (coord < 0)
1659 : {
1660 24946 : coord = -coord;
1661 24946 : inverse = true;
1662 : }
1663 :
1664 49904 : if (coord <= 2 * DIM(cube))
1665 : {
1666 : /* dimension index */
1667 49892 : int index = (coord - 1) / 2;
1668 :
1669 : /* whether this is upper bound (lower bound otherwise) */
1670 49892 : bool upper = ((coord - 1) % 2 == 1);
1671 :
1672 49892 : if (IS_POINT(cube))
1673 : {
1674 60 : result = cube->x[index];
1675 : }
1676 : else
1677 : {
1678 49832 : if (upper)
1679 24914 : result = Max(cube->x[index], cube->x[index + DIM(cube)]);
1680 : else
1681 24918 : result = Min(cube->x[index], cube->x[index + DIM(cube)]);
1682 : }
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 12 : result = 0.0;
1692 : }
1693 :
1694 : /* Inverse value if needed */
1695 49904 : if (inverse)
1696 24946 : result = -result;
1697 :
1698 49904 : PG_RETURN_FLOAT8(result);
1699 : }
1700 :
1701 : /* Increase or decrease box size by a radius in at least n dimensions. */
1702 : Datum
1703 108 : cube_enlarge(PG_FUNCTION_ARGS)
1704 : {
1705 108 : NDBOX *a = PG_GETARG_NDBOX_P(0);
1706 108 : double r = PG_GETARG_FLOAT8(1);
1707 108 : int32 n = PG_GETARG_INT32(2);
1708 : NDBOX *result;
1709 108 : int dim = 0;
1710 : int size;
1711 : int i,
1712 : j;
1713 :
1714 108 : if (n > CUBE_MAX_DIM)
1715 0 : n = CUBE_MAX_DIM;
1716 108 : if (r > 0 && n > 0)
1717 80 : dim = n;
1718 108 : if (DIM(a) > dim)
1719 30 : dim = DIM(a);
1720 :
1721 108 : size = CUBE_SIZE(dim);
1722 108 : result = (NDBOX *) palloc0(size);
1723 108 : SET_VARSIZE(result, size);
1724 108 : SET_DIM(result, dim);
1725 :
1726 376 : for (i = 0, j = dim; i < DIM(a); i++, j++)
1727 : {
1728 268 : if (LL_COORD(a, i) >= UR_COORD(a, i))
1729 : {
1730 252 : result->x[i] = UR_COORD(a, i) - r;
1731 252 : result->x[j] = LL_COORD(a, i) + r;
1732 : }
1733 : else
1734 : {
1735 16 : result->x[i] = LL_COORD(a, i) - r;
1736 16 : result->x[j] = UR_COORD(a, i) + r;
1737 : }
1738 268 : if (result->x[i] > result->x[j])
1739 : {
1740 16 : result->x[i] = (result->x[i] + result->x[j]) / 2;
1741 16 : result->x[j] = result->x[i];
1742 : }
1743 : }
1744 : /* dim > a->dim only if r > 0 */
1745 116 : for (; i < dim; i++, j++)
1746 : {
1747 8 : result->x[i] = -r;
1748 8 : result->x[j] = r;
1749 : }
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 108 : if (cube_is_point_internal(result))
1756 : {
1757 16 : size = POINT_SIZE(dim);
1758 16 : SET_VARSIZE(result, size);
1759 16 : SET_POINT_BIT(result);
1760 : }
1761 :
1762 108 : PG_FREE_IF_COPY(a, 0);
1763 108 : PG_RETURN_NDBOX_P(result);
1764 : }
1765 :
1766 : /* Create a one dimensional box with identical upper and lower coordinates */
1767 : Datum
1768 388 : cube_f8(PG_FUNCTION_ARGS)
1769 : {
1770 388 : double x = PG_GETARG_FLOAT8(0);
1771 : NDBOX *result;
1772 : int size;
1773 :
1774 388 : size = POINT_SIZE(1);
1775 388 : result = (NDBOX *) palloc0(size);
1776 388 : SET_VARSIZE(result, size);
1777 388 : SET_DIM(result, 1);
1778 388 : SET_POINT_BIT(result);
1779 388 : result->x[0] = x;
1780 :
1781 388 : PG_RETURN_NDBOX_P(result);
1782 : }
1783 :
1784 : /* Create a one dimensional box */
1785 : Datum
1786 24 : cube_f8_f8(PG_FUNCTION_ARGS)
1787 : {
1788 24 : double x0 = PG_GETARG_FLOAT8(0);
1789 24 : double x1 = PG_GETARG_FLOAT8(1);
1790 : NDBOX *result;
1791 : int size;
1792 :
1793 24 : if (x0 == x1)
1794 : {
1795 8 : size = POINT_SIZE(1);
1796 8 : result = (NDBOX *) palloc0(size);
1797 8 : SET_VARSIZE(result, size);
1798 8 : SET_DIM(result, 1);
1799 8 : SET_POINT_BIT(result);
1800 8 : result->x[0] = x0;
1801 : }
1802 : else
1803 : {
1804 16 : size = CUBE_SIZE(1);
1805 16 : result = (NDBOX *) palloc0(size);
1806 16 : SET_VARSIZE(result, size);
1807 16 : SET_DIM(result, 1);
1808 16 : result->x[0] = x0;
1809 16 : result->x[1] = x1;
1810 : }
1811 :
1812 24 : PG_RETURN_NDBOX_P(result);
1813 : }
1814 :
1815 : /* Add a dimension to an existing cube with the same values for the new
1816 : coordinate */
1817 : Datum
1818 774 : cube_c_f8(PG_FUNCTION_ARGS)
1819 : {
1820 774 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1821 774 : double x = PG_GETARG_FLOAT8(1);
1822 : NDBOX *result;
1823 : int size;
1824 : int i;
1825 :
1826 774 : if (DIM(cube) + 1 > CUBE_MAX_DIM)
1827 2 : ereport(ERROR,
1828 : (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 772 : if (IS_POINT(cube))
1834 : {
1835 766 : size = POINT_SIZE((DIM(cube) + 1));
1836 766 : result = (NDBOX *) palloc0(size);
1837 766 : SET_VARSIZE(result, size);
1838 766 : SET_DIM(result, DIM(cube) + 1);
1839 766 : SET_POINT_BIT(result);
1840 1914 : for (i = 0; i < DIM(cube); i++)
1841 1148 : result->x[i] = cube->x[i];
1842 766 : result->x[DIM(result) - 1] = x;
1843 : }
1844 : else
1845 : {
1846 6 : size = CUBE_SIZE((DIM(cube) + 1));
1847 6 : result = (NDBOX *) palloc0(size);
1848 6 : SET_VARSIZE(result, size);
1849 6 : SET_DIM(result, DIM(cube) + 1);
1850 14 : for (i = 0; i < DIM(cube); i++)
1851 : {
1852 8 : result->x[i] = cube->x[i];
1853 8 : result->x[DIM(result) + i] = cube->x[DIM(cube) + i];
1854 : }
1855 6 : result->x[DIM(result) - 1] = x;
1856 6 : result->x[2 * DIM(result) - 1] = x;
1857 : }
1858 :
1859 772 : PG_FREE_IF_COPY(cube, 0);
1860 772 : PG_RETURN_NDBOX_P(result);
1861 : }
1862 :
1863 : /* Add a dimension to an existing cube */
1864 : Datum
1865 18 : cube_c_f8_f8(PG_FUNCTION_ARGS)
1866 : {
1867 18 : NDBOX *cube = PG_GETARG_NDBOX_P(0);
1868 18 : double x1 = PG_GETARG_FLOAT8(1);
1869 18 : double x2 = PG_GETARG_FLOAT8(2);
1870 : NDBOX *result;
1871 : int size;
1872 : int i;
1873 :
1874 18 : if (DIM(cube) + 1 > CUBE_MAX_DIM)
1875 2 : ereport(ERROR,
1876 : (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 16 : if (IS_POINT(cube) && (x1 == x2))
1882 : {
1883 2 : size = POINT_SIZE((DIM(cube) + 1));
1884 2 : result = (NDBOX *) palloc0(size);
1885 2 : SET_VARSIZE(result, size);
1886 2 : SET_DIM(result, DIM(cube) + 1);
1887 2 : SET_POINT_BIT(result);
1888 4 : for (i = 0; i < DIM(cube); i++)
1889 2 : result->x[i] = cube->x[i];
1890 2 : result->x[DIM(result) - 1] = x1;
1891 : }
1892 : else
1893 : {
1894 14 : size = CUBE_SIZE((DIM(cube) + 1));
1895 14 : result = (NDBOX *) palloc0(size);
1896 14 : SET_VARSIZE(result, size);
1897 14 : SET_DIM(result, DIM(cube) + 1);
1898 30 : for (i = 0; i < DIM(cube); i++)
1899 : {
1900 16 : result->x[i] = LL_COORD(cube, i);
1901 16 : result->x[DIM(result) + i] = UR_COORD(cube, i);
1902 : }
1903 14 : result->x[DIM(result) - 1] = x1;
1904 14 : result->x[2 * DIM(result) - 1] = x2;
1905 : }
1906 :
1907 16 : PG_FREE_IF_COPY(cube, 0);
1908 16 : PG_RETURN_NDBOX_P(result);
1909 : }
|
