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