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

Generated by: LCOV version 1.14