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

Generated by: LCOV version 1.14