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

Generated by: LCOV version 1.13