LCOV - code coverage report
Current view: top level - contrib/cube - cube.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 718 792 90.7 %
Date: 2020-06-03 10:06:28 Functions: 87 91 95.6 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13