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

Generated by: LCOV version 2.0-1