LCOV - code coverage report
Current view: top level - contrib/intarray - _int_gist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 19devel Lines: 251 274 91.6 %
Date: 2026-02-08 00:18:15 Functions: 17 17 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             : #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           4 : PG_FUNCTION_INFO_V1(g_int_consistent);
      31           4 : PG_FUNCTION_INFO_V1(g_int_compress);
      32           4 : PG_FUNCTION_INFO_V1(g_int_decompress);
      33           4 : PG_FUNCTION_INFO_V1(g_int_penalty);
      34           4 : PG_FUNCTION_INFO_V1(g_int_picksplit);
      35           4 : PG_FUNCTION_INFO_V1(g_int_union);
      36           4 : PG_FUNCTION_INFO_V1(g_int_same);
      37           4 : 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      264558 : g_int_consistent(PG_FUNCTION_ARGS)
      48             : {
      49      264558 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
      50      264558 :     ArrayType  *query = PG_GETARG_ARRAYTYPE_P_COPY(1);
      51      264558 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
      52             : #ifdef NOT_USED
      53             :     Oid         subtype = PG_GETARG_OID(3);
      54             : #endif
      55      264558 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
      56      264558 :     bool        retval = false; /* silence compiler warning */
      57             : 
      58             :     /* this is exact except for RTSameStrategyNumber */
      59      264558 :     *recheck = (strategy == RTSameStrategyNumber);
      60             : 
      61      264558 :     if (strategy == BooleanSearchStrategy)
      62             :     {
      63      167236 :         retval = execconsistent((QUERYTYPE *) query,
      64      167236 :                                 (ArrayType *) DatumGetPointer(entry->key),
      65      167236 :                                 GIST_LEAF(entry));
      66             : 
      67      167236 :         pfree(query);
      68      167236 :         PG_RETURN_BOOL(retval);
      69             :     }
      70             : 
      71             :     /* sort query for fast search, key is already sorted */
      72       97322 :     CHECKARRVALID(query);
      73       97322 :     PREPAREARR(query);
      74             : 
      75       97322 :     switch (strategy)
      76             :     {
      77       32356 :         case RTOverlapStrategyNumber:
      78       32356 :             retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
      79             :                                        query);
      80       32356 :             break;
      81        9202 :         case RTSameStrategyNumber:
      82        9202 :             if (GIST_LEAF(entry))
      83        8598 :                 DirectFunctionCall3(g_int_same,
      84             :                                     entry->key,
      85             :                                     PointerGetDatum(query),
      86             :                                     PointerGetDatum(&retval));
      87             :             else
      88         604 :                 retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
      89             :                                             query);
      90        9202 :             break;
      91       55764 :         case RTContainsStrategyNumber:
      92             :         case RTOldContainsStrategyNumber:
      93       55764 :             retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
      94             :                                         query);
      95       55764 :             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       97322 :     pfree(query);
     120       97322 :     PG_RETURN_BOOL(retval);
     121             : }
     122             : 
     123             : Datum
     124      114416 : g_int_union(PG_FUNCTION_ARGS)
     125             : {
     126      114416 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     127      114416 :     int        *size = (int *) PG_GETARG_POINTER(1);
     128             :     int32       i,
     129             :                *ptr;
     130             :     ArrayType  *res;
     131      114416 :     int         totlen = 0;
     132             : 
     133      344576 :     for (i = 0; i < entryvec->n; i++)
     134             :     {
     135      230160 :         ArrayType  *ent = GETENTRY(entryvec, i);
     136             : 
     137      230160 :         CHECKARRVALID(ent);
     138      230160 :         totlen += ARRNELEMS(ent);
     139             :     }
     140             : 
     141      114416 :     res = new_intArrayType(totlen);
     142      114416 :     ptr = ARRPTR(res);
     143             : 
     144      344576 :     for (i = 0; i < entryvec->n; i++)
     145             :     {
     146      230160 :         ArrayType  *ent = GETENTRY(entryvec, i);
     147             :         int         nel;
     148             : 
     149      230160 :         nel = ARRNELEMS(ent);
     150      230160 :         memcpy(ptr, ARRPTR(ent), nel * sizeof(int32));
     151      230160 :         ptr += nel;
     152             :     }
     153             : 
     154      114416 :     QSORT(res, 1);
     155      114416 :     res = _int_unique(res);
     156      114416 :     *size = VARSIZE(res);
     157      114416 :     PG_RETURN_POINTER(res);
     158             : }
     159             : 
     160             : /*
     161             : ** GiST Compress and Decompress methods
     162             : */
     163             : Datum
     164       60952 : g_int_compress(PG_FUNCTION_ARGS)
     165             : {
     166       60952 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     167             :     GISTENTRY  *retval;
     168             :     ArrayType  *r;
     169       60952 :     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       60952 :     if (entry->leafkey)
     179             :     {
     180       40544 :         r = DatumGetArrayTypePCopy(entry->key);
     181       40544 :         CHECKARRVALID(r);
     182       40544 :         PREPAREARR(r);
     183             : 
     184       40544 :         if (ARRNELEMS(r) >= 2 * num_ranges)
     185           2 :             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       40542 :         retval = palloc_object(GISTENTRY);
     191       40542 :         gistentryinit(*retval, PointerGetDatum(r),
     192             :                       entry->rel, entry->page, entry->offset, false);
     193             : 
     194       40542 :         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       20408 :     r = DatumGetArrayTypeP(entry->key);
     203       20408 :     CHECKARRVALID(r);
     204       20408 :     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       20408 :     if ((len = ARRNELEMS(r)) >= 2 * num_ranges)
     212             :     {                           /* compress */
     213        2924 :         if (r == (ArrayType *) DatumGetPointer(entry->key))
     214        2924 :             r = DatumGetArrayTypePCopy(entry->key);
     215        2924 :         r = resize_intArrayType(r, 2 * (len));
     216             : 
     217        2924 :         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        2924 :         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      132854 :         for (j = i = len - 1; i > 0 && lenr > 0; i--, j--)
     231             :         {
     232      129930 :             int         r_end = dr[i];
     233      129930 :             int         r_start = r_end;
     234             : 
     235     1424722 :             while (i > 0 && lenr > 0 && dr[i - 1] == r_start - 1)
     236     1294792 :                 --r_start, --i, --lenr;
     237      129930 :             dr[2 * j] = r_start;
     238      129930 :             dr[2 * j + 1] = r_end;
     239             :         }
     240             :         /* just copy the rest, if any, as trivial ranges */
     241      557858 :         for (; i >= 0; i--, j--)
     242      554934 :             dr[2 * j] = dr[2 * j + 1] = dr[i];
     243             : 
     244        2924 :         if (++j)
     245             :         {
     246             :             /*
     247             :              * shunt everything down to start at the right place
     248             :              */
     249        2924 :             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        2924 :         len = 2 * (len - j);
     256        2924 :         cand = 1;
     257        2924 :         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        2924 :         lenr = internal_size(dr, len);
     274        2924 :         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        2924 :         r = resize_intArrayType(r, len);
     280        2924 :         retval = palloc_object(GISTENTRY);
     281        2924 :         gistentryinit(*retval, PointerGetDatum(r),
     282             :                       entry->rel, entry->page, entry->offset, false);
     283        2924 :         PG_RETURN_POINTER(retval);
     284             :     }
     285             :     else
     286       17484 :         PG_RETURN_POINTER(entry);
     287             : }
     288             : 
     289             : Datum
     290     1299358 : g_int_decompress(PG_FUNCTION_ARGS)
     291             : {
     292     1299358 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     293             :     GISTENTRY  *retval;
     294             :     ArrayType  *r;
     295     1299358 :     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     1299358 :     in = DatumGetArrayTypeP(entry->key);
     304             : 
     305     1299358 :     CHECKARRVALID(in);
     306     1299358 :     if (ARRISEMPTY(in))
     307             :     {
     308         738 :         if (in != (ArrayType *) DatumGetPointer(entry->key))
     309             :         {
     310         738 :             retval = palloc_object(GISTENTRY);
     311         738 :             gistentryinit(*retval, PointerGetDatum(in),
     312             :                           entry->rel, entry->page, entry->offset, false);
     313         738 :             PG_RETURN_POINTER(retval);
     314             :         }
     315             : 
     316           0 :         PG_RETURN_POINTER(entry);
     317             :     }
     318             : 
     319     1298620 :     lenin = ARRNELEMS(in);
     320             : 
     321     1298620 :     if (lenin < 2 * num_ranges)
     322             :     {                           /* not compressed value */
     323     1245706 :         if (in != (ArrayType *) DatumGetPointer(entry->key))
     324             :         {
     325      544102 :             retval = palloc_object(GISTENTRY);
     326      544102 :             gistentryinit(*retval, PointerGetDatum(in),
     327             :                           entry->rel, entry->page, entry->offset, false);
     328             : 
     329      544102 :             PG_RETURN_POINTER(retval);
     330             :         }
     331      701604 :         PG_RETURN_POINTER(entry);
     332             :     }
     333             : 
     334       52914 :     din = ARRPTR(in);
     335       52914 :     lenr = internal_size(din, lenin);
     336       52914 :     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       52914 :     r = new_intArrayType(lenr);
     342       52914 :     dr = ARRPTR(r);
     343             : 
     344    12590762 :     for (i = 0; i < lenin; i += 2)
     345             :     {
     346             :         /* use int64 for j in case din[i + 1] is INT_MAX */
     347    50759674 :         for (int64 j = din[i]; j <= din[i + 1]; j++)
     348    38221826 :             if ((!i) || *(dr - 1) != j)
     349    38221826 :                 *dr++ = (int) j;
     350             :     }
     351             : 
     352       52914 :     if (in != (ArrayType *) DatumGetPointer(entry->key))
     353       52914 :         pfree(in);
     354       52914 :     retval = palloc_object(GISTENTRY);
     355       52914 :     gistentryinit(*retval, PointerGetDatum(r),
     356             :                   entry->rel, entry->page, entry->offset, false);
     357             : 
     358       52914 :     PG_RETURN_POINTER(retval);
     359             : }
     360             : 
     361             : /*
     362             : ** The GiST Penalty method for _intments
     363             : */
     364             : Datum
     365      617168 : g_int_penalty(PG_FUNCTION_ARGS)
     366             : {
     367      617168 :     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
     368      617168 :     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
     369      617168 :     float      *result = (float *) PG_GETARG_POINTER(2);
     370             :     ArrayType  *ud;
     371             :     float       tmp1,
     372             :                 tmp2;
     373             : 
     374      617168 :     ud = inner_int_union((ArrayType *) DatumGetPointer(origentry->key),
     375      617168 :                          (ArrayType *) DatumGetPointer(newentry->key));
     376      617168 :     rt__int_size(ud, &tmp1);
     377      617168 :     rt__int_size((ArrayType *) DatumGetPointer(origentry->key), &tmp2);
     378      617168 :     *result = tmp1 - tmp2;
     379      617168 :     pfree(ud);
     380             : 
     381      617168 :     PG_RETURN_POINTER(result);
     382             : }
     383             : 
     384             : 
     385             : 
     386             : Datum
     387      122966 : g_int_same(PG_FUNCTION_ARGS)
     388             : {
     389      122966 :     ArrayType  *a = PG_GETARG_ARRAYTYPE_P(0);
     390      122966 :     ArrayType  *b = PG_GETARG_ARRAYTYPE_P(1);
     391      122966 :     bool       *result = (bool *) PG_GETARG_POINTER(2);
     392      122966 :     int32       n = ARRNELEMS(a);
     393             :     int32      *da,
     394             :                *db;
     395             : 
     396      122966 :     CHECKARRVALID(a);
     397      122966 :     CHECKARRVALID(b);
     398             : 
     399      122966 :     if (n != ARRNELEMS(b))
     400             :     {
     401       24966 :         *result = false;
     402       24966 :         PG_RETURN_POINTER(result);
     403             :     }
     404       98000 :     *result = true;
     405       98000 :     da = ARRPTR(a);
     406       98000 :     db = ARRPTR(b);
     407    29396682 :     while (n--)
     408             :     {
     409    29300116 :         if (*da++ != *db++)
     410             :         {
     411        1434 :             *result = false;
     412        1434 :             break;
     413             :         }
     414             :     }
     415             : 
     416       98000 :     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      126614 : comparecost(const void *a, const void *b)
     431             : {
     432      126614 :     if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
     433       66882 :         return 0;
     434             :     else
     435       59732 :         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        1286 : g_int_picksplit(PG_FUNCTION_ARGS)
     444             : {
     445        1286 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     446        1286 :     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        1286 :     OffsetNumber seed_1 = 0,
     468        1286 :                 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        1286 :     maxoff = entryvec->n - 2;
     479        1286 :     nbytes = (maxoff + 2) * sizeof(OffsetNumber);
     480        1286 :     v->spl_left = (OffsetNumber *) palloc(nbytes);
     481        1286 :     v->spl_right = (OffsetNumber *) palloc(nbytes);
     482             : 
     483        1286 :     firsttime = true;
     484        1286 :     waste = 0.0;
     485       66224 :     for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
     486             :     {
     487       64938 :         datum_alpha = GETENTRY(entryvec, i);
     488     3647056 :         for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
     489             :         {
     490     3582118 :             datum_beta = GETENTRY(entryvec, j);
     491             : 
     492             :             /* compute the wasted space by unioning these guys */
     493             :             /* size_waste = size_union - size_inter; */
     494     3582118 :             union_d = inner_int_union(datum_alpha, datum_beta);
     495     3582118 :             rt__int_size(union_d, &size_union);
     496     3582118 :             inter_d = inner_int_inter(datum_alpha, datum_beta);
     497     3582118 :             rt__int_size(inter_d, &size_inter);
     498     3582118 :             size_waste = size_union - size_inter;
     499             : 
     500     3582118 :             pfree(union_d);
     501     3582118 :             pfree(inter_d);
     502             : 
     503             :             /*
     504             :              * are these a more promising split that what we've already seen?
     505             :              */
     506             : 
     507     3582118 :             if (size_waste > waste || firsttime)
     508             :             {
     509        6162 :                 waste = size_waste;
     510        6162 :                 seed_1 = i;
     511        6162 :                 seed_2 = j;
     512        6162 :                 firsttime = false;
     513             :             }
     514             :         }
     515             :     }
     516             : 
     517        1286 :     left = v->spl_left;
     518        1286 :     v->spl_nleft = 0;
     519        1286 :     right = v->spl_right;
     520        1286 :     v->spl_nright = 0;
     521        1286 :     if (seed_1 == 0 || seed_2 == 0)
     522             :     {
     523           0 :         seed_1 = 1;
     524           0 :         seed_2 = 2;
     525             :     }
     526             : 
     527        1286 :     datum_alpha = GETENTRY(entryvec, seed_1);
     528        1286 :     datum_l = copy_intArrayType(datum_alpha);
     529        1286 :     rt__int_size(datum_l, &size_l);
     530        1286 :     datum_beta = GETENTRY(entryvec, seed_2);
     531        1286 :     datum_r = copy_intArrayType(datum_beta);
     532        1286 :     rt__int_size(datum_r, &size_r);
     533             : 
     534        1286 :     maxoff = OffsetNumberNext(maxoff);
     535             : 
     536             :     /*
     537             :      * sort entries
     538             :      */
     539        1286 :     costvector = palloc_array(SPLITCOST, maxoff);
     540       68796 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
     541             :     {
     542       67510 :         costvector[i - 1].pos = i;
     543       67510 :         datum_alpha = GETENTRY(entryvec, i);
     544       67510 :         union_d = inner_int_union(datum_l, datum_alpha);
     545       67510 :         rt__int_size(union_d, &size_alpha);
     546       67510 :         pfree(union_d);
     547       67510 :         union_d = inner_int_union(datum_r, datum_alpha);
     548       67510 :         rt__int_size(union_d, &size_beta);
     549       67510 :         pfree(union_d);
     550       67510 :         costvector[i - 1].cost = fabsf((size_alpha - size_l) - (size_beta - size_r));
     551             :     }
     552        1286 :     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       68796 :     for (j = 0; j < maxoff; j++)
     568             :     {
     569       67510 :         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       67510 :         if (i == seed_1)
     578             :         {
     579        1286 :             *left++ = i;
     580        1286 :             v->spl_nleft++;
     581        1286 :             continue;
     582             :         }
     583       66224 :         else if (i == seed_2)
     584             :         {
     585        1286 :             *right++ = i;
     586        1286 :             v->spl_nright++;
     587        1286 :             continue;
     588             :         }
     589             : 
     590             :         /* okay, which page needs least enlargement? */
     591       64938 :         datum_alpha = GETENTRY(entryvec, i);
     592       64938 :         union_dl = inner_int_union(datum_l, datum_alpha);
     593       64938 :         union_dr = inner_int_union(datum_r, datum_alpha);
     594       64938 :         rt__int_size(union_dl, &size_alpha);
     595       64938 :         rt__int_size(union_dr, &size_beta);
     596             : 
     597             :         /* pick which page to add it to */
     598       64938 :         if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, 0.01))
     599             :         {
     600       31390 :             pfree(datum_l);
     601       31390 :             pfree(union_dr);
     602       31390 :             datum_l = union_dl;
     603       31390 :             size_l = size_alpha;
     604       31390 :             *left++ = i;
     605       31390 :             v->spl_nleft++;
     606             :         }
     607             :         else
     608             :         {
     609       33548 :             pfree(datum_r);
     610       33548 :             pfree(union_dl);
     611       33548 :             datum_r = union_dr;
     612       33548 :             size_r = size_beta;
     613       33548 :             *right++ = i;
     614       33548 :             v->spl_nright++;
     615             :         }
     616             :     }
     617        1286 :     pfree(costvector);
     618        1286 :     *right = *left = FirstOffsetNumber;
     619             : 
     620        1286 :     v->spl_ldatum = PointerGetDatum(datum_l);
     621        1286 :     v->spl_rdatum = PointerGetDatum(datum_r);
     622             : 
     623        1286 :     PG_RETURN_POINTER(v);
     624             : }
     625             : 
     626             : Datum
     627          26 : g_int_options(PG_FUNCTION_ARGS)
     628             : {
     629          26 :     local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
     630             : 
     631          26 :     init_local_reloptions(relopts, sizeof(GISTIntArrayOptions));
     632          26 :     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          26 :     PG_RETURN_VOID();
     638             : }

Generated by: LCOV version 1.16