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

Generated by: LCOV version 1.14