LCOV - code coverage report
Current view: top level - contrib/intarray - _int_gist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 243 260 93.5 %
Date: 2019-11-15 22:06:47 Functions: 15 15 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :  * contrib/intarray/_int_gist.c
       3             :  */
       4             : #include "postgres.h"
       5             : 
       6             : #include <limits.h>
       7             : 
       8             : #include "_int.h"
       9             : #include "access/gist.h"
      10             : #include "access/stratnum.h"
      11             : 
      12             : #define GETENTRY(vec,pos) ((ArrayType *) DatumGetPointer((vec)->vector[(pos)].key))
      13             : 
      14             : /*
      15             :  * Control the maximum sparseness of compressed keys.
      16             :  *
      17             :  * The upper safe bound for this limit is half the maximum allocatable array
      18             :  * size. A lower bound would give more guarantees that pathological data
      19             :  * wouldn't eat excessive CPU and memory, but at the expense of breaking
      20             :  * possibly working (after a fashion) indexes.
      21             :  */
      22             : #define MAXNUMELTS (Min((MaxAllocSize / sizeof(Datum)),((MaxAllocSize - ARR_OVERHEAD_NONULLS(1)) / sizeof(int)))/2)
      23             : /* or: #define MAXNUMELTS 1000000 */
      24             : 
      25             : /*
      26             : ** GiST support methods
      27             : */
      28           4 : PG_FUNCTION_INFO_V1(g_int_consistent);
      29           4 : PG_FUNCTION_INFO_V1(g_int_compress);
      30           4 : PG_FUNCTION_INFO_V1(g_int_decompress);
      31           4 : PG_FUNCTION_INFO_V1(g_int_penalty);
      32           4 : PG_FUNCTION_INFO_V1(g_int_picksplit);
      33           4 : PG_FUNCTION_INFO_V1(g_int_union);
      34           4 : PG_FUNCTION_INFO_V1(g_int_same);
      35             : 
      36             : 
      37             : /*
      38             : ** The GiST Consistent method for _intments
      39             : ** Should return false if for all data items x below entry,
      40             : ** the predicate x op query == false, where op is the oper
      41             : ** corresponding to strategy in the pg_amop table.
      42             : */
      43             : Datum
      44      106232 : g_int_consistent(PG_FUNCTION_ARGS)
      45             : {
      46      106232 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
      47      106232 :     ArrayType  *query = PG_GETARG_ARRAYTYPE_P_COPY(1);
      48      106232 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
      49             : 
      50             :     /* Oid      subtype = PG_GETARG_OID(3); */
      51      106232 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
      52             :     bool        retval;
      53             : 
      54             :     /* this is exact except for RTSameStrategyNumber */
      55      106232 :     *recheck = (strategy == RTSameStrategyNumber);
      56             : 
      57      106232 :     if (strategy == BooleanSearchStrategy)
      58             :     {
      59      113732 :         retval = execconsistent((QUERYTYPE *) query,
      60       56866 :                                 (ArrayType *) DatumGetPointer(entry->key),
      61       56866 :                                 GIST_LEAF(entry));
      62             : 
      63       56866 :         pfree(query);
      64       56866 :         PG_RETURN_BOOL(retval);
      65             :     }
      66             : 
      67             :     /* sort query for fast search, key is already sorted */
      68       49366 :     CHECKARRVALID(query);
      69       49366 :     PREPAREARR(query);
      70             : 
      71       49366 :     switch (strategy)
      72             :     {
      73             :         case RTOverlapStrategyNumber:
      74       12204 :             retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
      75             :                                        query);
      76       12204 :             break;
      77             :         case RTSameStrategyNumber:
      78        3758 :             if (GIST_LEAF(entry))
      79        3592 :                 DirectFunctionCall3(g_int_same,
      80             :                                     entry->key,
      81             :                                     PointerGetDatum(query),
      82             :                                     PointerGetDatum(&retval));
      83             :             else
      84         166 :                 retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
      85             :                                             query);
      86        3758 :             break;
      87             :         case RTContainsStrategyNumber:
      88             :         case RTOldContainsStrategyNumber:
      89       19718 :             retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
      90             :                                         query);
      91       19718 :             break;
      92             :         case RTContainedByStrategyNumber:
      93             :         case RTOldContainedByStrategyNumber:
      94       13686 :             if (GIST_LEAF(entry))
      95       13512 :                 retval = inner_int_contains(query,
      96       13512 :                                             (ArrayType *) DatumGetPointer(entry->key));
      97             :             else
      98             :             {
      99             :                 /*
     100             :                  * Unfortunately, because empty arrays could be anywhere in
     101             :                  * the index, we must search the whole tree.
     102             :                  */
     103         174 :                 retval = true;
     104             :             }
     105       13686 :             break;
     106             :         default:
     107           0 :             retval = false;
     108             :     }
     109       49366 :     pfree(query);
     110       49366 :     PG_RETURN_BOOL(retval);
     111             : }
     112             : 
     113             : Datum
     114       22550 : g_int_union(PG_FUNCTION_ARGS)
     115             : {
     116       22550 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     117       22550 :     int        *size = (int *) PG_GETARG_POINTER(1);
     118             :     int32       i,
     119             :                *ptr;
     120             :     ArrayType  *res;
     121       22550 :     int         totlen = 0;
     122             : 
     123       67968 :     for (i = 0; i < entryvec->n; i++)
     124             :     {
     125       45418 :         ArrayType  *ent = GETENTRY(entryvec, i);
     126             : 
     127       45418 :         CHECKARRVALID(ent);
     128       45418 :         totlen += ARRNELEMS(ent);
     129             :     }
     130             : 
     131       22550 :     res = new_intArrayType(totlen);
     132       22550 :     ptr = ARRPTR(res);
     133             : 
     134       67968 :     for (i = 0; i < entryvec->n; i++)
     135             :     {
     136       45418 :         ArrayType  *ent = GETENTRY(entryvec, i);
     137             :         int         nel;
     138             : 
     139       45418 :         nel = ARRNELEMS(ent);
     140       45418 :         memcpy(ptr, ARRPTR(ent), nel * sizeof(int32));
     141       45418 :         ptr += nel;
     142             :     }
     143             : 
     144       22550 :     QSORT(res, 1);
     145       22550 :     res = _int_unique(res);
     146       22550 :     *size = VARSIZE(res);
     147       22550 :     PG_RETURN_POINTER(res);
     148             : }
     149             : 
     150             : /*
     151             : ** GiST Compress and Decompress methods
     152             : */
     153             : Datum
     154       18172 : g_int_compress(PG_FUNCTION_ARGS)
     155             : {
     156       18172 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     157             :     GISTENTRY  *retval;
     158             :     ArrayType  *r;
     159             :     int         len,
     160             :                 lenr;
     161             :     int        *dr;
     162             :     int         i,
     163             :                 j,
     164             :                 cand;
     165             :     int64       min;
     166             : 
     167       18172 :     if (entry->leafkey)
     168             :     {
     169       13512 :         r = DatumGetArrayTypePCopy(entry->key);
     170       13512 :         CHECKARRVALID(r);
     171       13512 :         PREPAREARR(r);
     172             : 
     173       13512 :         if (ARRNELEMS(r) >= 2 * MAXNUMRANGE)
     174           0 :             elog(NOTICE, "input array is too big (%d maximum allowed, %d current), use gist__intbig_ops opclass instead",
     175             :                  2 * MAXNUMRANGE - 1, ARRNELEMS(r));
     176             : 
     177       13512 :         retval = palloc(sizeof(GISTENTRY));
     178       13512 :         gistentryinit(*retval, PointerGetDatum(r),
     179             :                       entry->rel, entry->page, entry->offset, false);
     180             : 
     181       13512 :         PG_RETURN_POINTER(retval);
     182             :     }
     183             : 
     184             :     /*
     185             :      * leaf entries never compress one more time, only when entry->leafkey
     186             :      * ==true, so now we work only with internal keys
     187             :      */
     188             : 
     189        4660 :     r = DatumGetArrayTypeP(entry->key);
     190        4660 :     CHECKARRVALID(r);
     191        4660 :     if (ARRISEMPTY(r))
     192             :     {
     193           0 :         if (r != (ArrayType *) DatumGetPointer(entry->key))
     194           0 :             pfree(r);
     195           0 :         PG_RETURN_POINTER(entry);
     196             :     }
     197             : 
     198        4660 :     if ((len = ARRNELEMS(r)) >= 2 * MAXNUMRANGE)
     199             :     {                           /* compress */
     200         312 :         if (r == (ArrayType *) DatumGetPointer(entry->key))
     201         312 :             r = DatumGetArrayTypePCopy(entry->key);
     202         312 :         r = resize_intArrayType(r, 2 * (len));
     203             : 
     204         312 :         dr = ARRPTR(r);
     205             : 
     206             :         /*
     207             :          * "len" at this point is the number of ranges we will construct.
     208             :          * "lenr" is the number of ranges we must eventually remove by
     209             :          * merging, we must be careful to remove no more than this number.
     210             :          */
     211         312 :         lenr = len - MAXNUMRANGE;
     212             : 
     213             :         /*
     214             :          * Initially assume we can merge consecutive ints into a range. but we
     215             :          * must count every value removed and stop when lenr runs out
     216             :          */
     217       10178 :         for (j = i = len - 1; i > 0 && lenr > 0; i--, j--)
     218             :         {
     219        9866 :             int         r_end = dr[i];
     220        9866 :             int         r_start = r_end;
     221             : 
     222       64004 :             while (i > 0 && lenr > 0 && dr[i - 1] == r_start - 1)
     223       44272 :                 --r_start, --i, --lenr;
     224        9866 :             dr[2 * j] = r_start;
     225        9866 :             dr[2 * j + 1] = r_end;
     226             :         }
     227             :         /* just copy the rest, if any, as trivial ranges */
     228       21646 :         for (; i >= 0; i--, j--)
     229       21334 :             dr[2 * j] = dr[2 * j + 1] = dr[i];
     230             : 
     231         312 :         if (++j)
     232             :         {
     233             :             /*
     234             :              * shunt everything down to start at the right place
     235             :              */
     236         312 :             memmove((void *) &dr[0], (void *) &dr[2 * j], 2 * (len - j) * sizeof(int32));
     237             :         }
     238             : 
     239             :         /*
     240             :          * make "len" be number of array elements, not ranges
     241             :          */
     242         312 :         len = 2 * (len - j);
     243         312 :         cand = 1;
     244         624 :         while (len > MAXNUMRANGE * 2)
     245             :         {
     246           0 :             min = PG_INT64_MAX;
     247           0 :             for (i = 2; i < len; i += 2)
     248           0 :                 if (min > ((int64) dr[i] - (int64) dr[i - 1]))
     249             :                 {
     250           0 :                     min = ((int64) dr[i] - (int64) dr[i - 1]);
     251           0 :                     cand = i;
     252             :                 }
     253           0 :             memmove((void *) &dr[cand - 1], (void *) &dr[cand + 1], (len - cand - 1) * sizeof(int32));
     254           0 :             len -= 2;
     255             :         }
     256             : 
     257             :         /*
     258             :          * check sparseness of result
     259             :          */
     260         312 :         lenr = internal_size(dr, len);
     261         312 :         if (lenr < 0 || lenr > MAXNUMELTS)
     262           0 :             ereport(ERROR,
     263             :                     (errmsg("data is too sparse, recreate index using gist__intbig_ops opclass instead")));
     264             : 
     265         312 :         r = resize_intArrayType(r, len);
     266         312 :         retval = palloc(sizeof(GISTENTRY));
     267         312 :         gistentryinit(*retval, PointerGetDatum(r),
     268             :                       entry->rel, entry->page, entry->offset, false);
     269         312 :         PG_RETURN_POINTER(retval);
     270             :     }
     271             :     else
     272        4348 :         PG_RETURN_POINTER(entry);
     273             : }
     274             : 
     275             : Datum
     276      352500 : g_int_decompress(PG_FUNCTION_ARGS)
     277             : {
     278      352500 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     279             :     GISTENTRY  *retval;
     280             :     ArrayType  *r;
     281             :     int        *dr,
     282             :                 lenr;
     283             :     ArrayType  *in;
     284             :     int         lenin;
     285             :     int        *din;
     286             :     int         i,
     287             :                 j;
     288             : 
     289      352500 :     in = DatumGetArrayTypeP(entry->key);
     290             : 
     291      352500 :     CHECKARRVALID(in);
     292      352500 :     if (ARRISEMPTY(in))
     293             :     {
     294         252 :         if (in != (ArrayType *) DatumGetPointer(entry->key))
     295             :         {
     296         252 :             retval = palloc(sizeof(GISTENTRY));
     297         252 :             gistentryinit(*retval, PointerGetDatum(in),
     298             :                           entry->rel, entry->page, entry->offset, false);
     299         252 :             PG_RETURN_POINTER(retval);
     300             :         }
     301             : 
     302           0 :         PG_RETURN_POINTER(entry);
     303             :     }
     304             : 
     305      352248 :     lenin = ARRNELEMS(in);
     306             : 
     307      352248 :     if (lenin < 2 * MAXNUMRANGE)
     308             :     {                           /* not compressed value */
     309      346742 :         if (in != (ArrayType *) DatumGetPointer(entry->key))
     310             :         {
     311      169772 :             retval = palloc(sizeof(GISTENTRY));
     312      169772 :             gistentryinit(*retval, PointerGetDatum(in),
     313             :                           entry->rel, entry->page, entry->offset, false);
     314             : 
     315      169772 :             PG_RETURN_POINTER(retval);
     316             :         }
     317      176970 :         PG_RETURN_POINTER(entry);
     318             :     }
     319             : 
     320        5506 :     din = ARRPTR(in);
     321        5506 :     lenr = internal_size(din, lenin);
     322        5506 :     if (lenr < 0 || lenr > MAXNUMELTS)
     323           0 :         ereport(ERROR,
     324             :                 (errmsg("compressed array is too big, recreate index using gist__intbig_ops opclass instead")));
     325             : 
     326        5506 :     r = new_intArrayType(lenr);
     327        5506 :     dr = ARRPTR(r);
     328             : 
     329      556106 :     for (i = 0; i < lenin; i += 2)
     330     1896680 :         for (j = din[i]; j <= din[i + 1]; j++)
     331     1346080 :             if ((!i) || *(dr - 1) != j)
     332     1346080 :                 *dr++ = j;
     333             : 
     334        5506 :     if (in != (ArrayType *) DatumGetPointer(entry->key))
     335        5506 :         pfree(in);
     336        5506 :     retval = palloc(sizeof(GISTENTRY));
     337        5506 :     gistentryinit(*retval, PointerGetDatum(r),
     338             :                   entry->rel, entry->page, entry->offset, false);
     339             : 
     340        5506 :     PG_RETURN_POINTER(retval);
     341             : }
     342             : 
     343             : /*
     344             : ** The GiST Penalty method for _intments
     345             : */
     346             : Datum
     347      155690 : g_int_penalty(PG_FUNCTION_ARGS)
     348             : {
     349      155690 :     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
     350      155690 :     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
     351      155690 :     float      *result = (float *) PG_GETARG_POINTER(2);
     352             :     ArrayType  *ud;
     353             :     float       tmp1,
     354             :                 tmp2;
     355             : 
     356      155690 :     ud = inner_int_union((ArrayType *) DatumGetPointer(origentry->key),
     357      155690 :                          (ArrayType *) DatumGetPointer(newentry->key));
     358      155690 :     rt__int_size(ud, &tmp1);
     359      155690 :     rt__int_size((ArrayType *) DatumGetPointer(origentry->key), &tmp2);
     360      155690 :     *result = tmp1 - tmp2;
     361      155690 :     pfree(ud);
     362             : 
     363      155690 :     PG_RETURN_POINTER(result);
     364             : }
     365             : 
     366             : 
     367             : 
     368             : Datum
     369       26138 : g_int_same(PG_FUNCTION_ARGS)
     370             : {
     371       26138 :     ArrayType  *a = PG_GETARG_ARRAYTYPE_P(0);
     372       26138 :     ArrayType  *b = PG_GETARG_ARRAYTYPE_P(1);
     373       26138 :     bool       *result = (bool *) PG_GETARG_POINTER(2);
     374       26138 :     int32       n = ARRNELEMS(a);
     375             :     int32      *da,
     376             :                *db;
     377             : 
     378       26138 :     CHECKARRVALID(a);
     379       26138 :     CHECKARRVALID(b);
     380             : 
     381       26138 :     if (n != ARRNELEMS(b))
     382             :     {
     383        7220 :         *result = false;
     384        7220 :         PG_RETURN_POINTER(result);
     385             :     }
     386       18918 :     *result = true;
     387       18918 :     da = ARRPTR(a);
     388       18918 :     db = ARRPTR(b);
     389     1941220 :     while (n--)
     390             :     {
     391     1904070 :         if (*da++ != *db++)
     392             :         {
     393         686 :             *result = false;
     394         686 :             break;
     395             :         }
     396             :     }
     397             : 
     398       18918 :     PG_RETURN_POINTER(result);
     399             : }
     400             : 
     401             : /*****************************************************************
     402             : ** Common GiST Method
     403             : *****************************************************************/
     404             : 
     405             : typedef struct
     406             : {
     407             :     OffsetNumber pos;
     408             :     float       cost;
     409             : } SPLITCOST;
     410             : 
     411             : static int
     412       37650 : comparecost(const void *a, const void *b)
     413             : {
     414       37650 :     if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
     415       22306 :         return 0;
     416             :     else
     417       15344 :         return (((const SPLITCOST *) a)->cost > ((const SPLITCOST *) b)->cost) ? 1 : -1;
     418             : }
     419             : 
     420             : /*
     421             : ** The GiST PickSplit method for _intments
     422             : ** We use Guttman's poly time split algorithm
     423             : */
     424             : Datum
     425         170 : g_int_picksplit(PG_FUNCTION_ARGS)
     426             : {
     427         170 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     428         170 :     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
     429             :     OffsetNumber i,
     430             :                 j;
     431             :     ArrayType  *datum_alpha,
     432             :                *datum_beta;
     433             :     ArrayType  *datum_l,
     434             :                *datum_r;
     435             :     ArrayType  *union_d,
     436             :                *union_dl,
     437             :                *union_dr;
     438             :     ArrayType  *inter_d;
     439             :     bool        firsttime;
     440             :     float       size_alpha,
     441             :                 size_beta,
     442             :                 size_union,
     443             :                 size_inter;
     444             :     float       size_waste,
     445             :                 waste;
     446             :     float       size_l,
     447             :                 size_r;
     448             :     int         nbytes;
     449         170 :     OffsetNumber seed_1 = 0,
     450         170 :                 seed_2 = 0;
     451             :     OffsetNumber *left,
     452             :                *right;
     453             :     OffsetNumber maxoff;
     454             :     SPLITCOST  *costvector;
     455             : 
     456             : #ifdef GIST_DEBUG
     457             :     elog(DEBUG3, "--------picksplit %d", entryvec->n);
     458             : #endif
     459             : 
     460         170 :     maxoff = entryvec->n - 2;
     461         170 :     nbytes = (maxoff + 2) * sizeof(OffsetNumber);
     462         170 :     v->spl_left = (OffsetNumber *) palloc(nbytes);
     463         170 :     v->spl_right = (OffsetNumber *) palloc(nbytes);
     464             : 
     465         170 :     firsttime = true;
     466         170 :     waste = 0.0;
     467       20626 :     for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
     468             :     {
     469       20456 :         datum_alpha = GETENTRY(entryvec, i);
     470     1393796 :         for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
     471             :         {
     472     1373340 :             datum_beta = GETENTRY(entryvec, j);
     473             : 
     474             :             /* compute the wasted space by unioning these guys */
     475             :             /* size_waste = size_union - size_inter; */
     476     1373340 :             union_d = inner_int_union(datum_alpha, datum_beta);
     477     1373340 :             rt__int_size(union_d, &size_union);
     478     1373340 :             inter_d = inner_int_inter(datum_alpha, datum_beta);
     479     1373340 :             rt__int_size(inter_d, &size_inter);
     480     1373340 :             size_waste = size_union - size_inter;
     481             : 
     482     1373340 :             pfree(union_d);
     483     1373340 :             pfree(inter_d);
     484             : 
     485             :             /*
     486             :              * are these a more promising split that what we've already seen?
     487             :              */
     488             : 
     489     1373340 :             if (size_waste > waste || firsttime)
     490             :             {
     491         882 :                 waste = size_waste;
     492         882 :                 seed_1 = i;
     493         882 :                 seed_2 = j;
     494         882 :                 firsttime = false;
     495             :             }
     496             :         }
     497             :     }
     498             : 
     499         170 :     left = v->spl_left;
     500         170 :     v->spl_nleft = 0;
     501         170 :     right = v->spl_right;
     502         170 :     v->spl_nright = 0;
     503         170 :     if (seed_1 == 0 || seed_2 == 0)
     504             :     {
     505           0 :         seed_1 = 1;
     506           0 :         seed_2 = 2;
     507             :     }
     508             : 
     509         170 :     datum_alpha = GETENTRY(entryvec, seed_1);
     510         170 :     datum_l = copy_intArrayType(datum_alpha);
     511         170 :     rt__int_size(datum_l, &size_l);
     512         170 :     datum_beta = GETENTRY(entryvec, seed_2);
     513         170 :     datum_r = copy_intArrayType(datum_beta);
     514         170 :     rt__int_size(datum_r, &size_r);
     515             : 
     516         170 :     maxoff = OffsetNumberNext(maxoff);
     517             : 
     518             :     /*
     519             :      * sort entries
     520             :      */
     521         170 :     costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
     522       20966 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
     523             :     {
     524       20796 :         costvector[i - 1].pos = i;
     525       20796 :         datum_alpha = GETENTRY(entryvec, i);
     526       20796 :         union_d = inner_int_union(datum_l, datum_alpha);
     527       20796 :         rt__int_size(union_d, &size_alpha);
     528       20796 :         pfree(union_d);
     529       20796 :         union_d = inner_int_union(datum_r, datum_alpha);
     530       20796 :         rt__int_size(union_d, &size_beta);
     531       20796 :         pfree(union_d);
     532       20796 :         costvector[i - 1].cost = Abs((size_alpha - size_l) - (size_beta - size_r));
     533             :     }
     534         170 :     qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
     535             : 
     536             :     /*
     537             :      * Now split up the regions between the two seeds.  An important property
     538             :      * of this split algorithm is that the split vector v has the indices of
     539             :      * items to be split in order in its left and right vectors.  We exploit
     540             :      * this property by doing a merge in the code that actually splits the
     541             :      * page.
     542             :      *
     543             :      * For efficiency, we also place the new index tuple in this loop. This is
     544             :      * handled at the very end, when we have placed all the existing tuples
     545             :      * and i == maxoff + 1.
     546             :      */
     547             : 
     548             : 
     549       20966 :     for (j = 0; j < maxoff; j++)
     550             :     {
     551       20796 :         i = costvector[j].pos;
     552             : 
     553             :         /*
     554             :          * If we've already decided where to place this item, just put it on
     555             :          * the right list.  Otherwise, we need to figure out which page needs
     556             :          * the least enlargement in order to store the item.
     557             :          */
     558             : 
     559       20796 :         if (i == seed_1)
     560             :         {
     561         170 :             *left++ = i;
     562         170 :             v->spl_nleft++;
     563         170 :             continue;
     564             :         }
     565       20626 :         else if (i == seed_2)
     566             :         {
     567         170 :             *right++ = i;
     568         170 :             v->spl_nright++;
     569         170 :             continue;
     570             :         }
     571             : 
     572             :         /* okay, which page needs least enlargement? */
     573       20456 :         datum_alpha = GETENTRY(entryvec, i);
     574       20456 :         union_dl = inner_int_union(datum_l, datum_alpha);
     575       20456 :         union_dr = inner_int_union(datum_r, datum_alpha);
     576       20456 :         rt__int_size(union_dl, &size_alpha);
     577       20456 :         rt__int_size(union_dr, &size_beta);
     578             : 
     579             :         /* pick which page to add it to */
     580       20456 :         if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, 0.01))
     581             :         {
     582       10176 :             pfree(datum_l);
     583       10176 :             pfree(union_dr);
     584       10176 :             datum_l = union_dl;
     585       10176 :             size_l = size_alpha;
     586       10176 :             *left++ = i;
     587       10176 :             v->spl_nleft++;
     588             :         }
     589             :         else
     590             :         {
     591       10280 :             pfree(datum_r);
     592       10280 :             pfree(union_dl);
     593       10280 :             datum_r = union_dr;
     594       10280 :             size_r = size_beta;
     595       10280 :             *right++ = i;
     596       10280 :             v->spl_nright++;
     597             :         }
     598             :     }
     599         170 :     pfree(costvector);
     600         170 :     *right = *left = FirstOffsetNumber;
     601             : 
     602         170 :     v->spl_ldatum = PointerGetDatum(datum_l);
     603         170 :     v->spl_rdatum = PointerGetDatum(datum_r);
     604             : 
     605         170 :     PG_RETURN_POINTER(v);
     606             : }

Generated by: LCOV version 1.13