LCOV - code coverage report
Current view: top level - src/backend/utils/adt - network_gist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 184 282 65.2 %
Date: 2024-10-07 01:12:31 Functions: 8 10 80.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * network_gist.c
       4             :  *    GiST support for network types.
       5             :  *
       6             :  * The key thing to understand about this code is the definition of the
       7             :  * "union" of a set of INET/CIDR values.  It works like this:
       8             :  * 1. If the values are not all of the same IP address family, the "union"
       9             :  * is a dummy value with family number zero, minbits zero, commonbits zero,
      10             :  * address all zeroes.  Otherwise:
      11             :  * 2. The union has the common IP address family number.
      12             :  * 3. The union's minbits value is the smallest netmask length ("ip_bits")
      13             :  * of all the input values.
      14             :  * 4. Let C be the number of leading address bits that are in common among
      15             :  * all the input values (C ranges from 0 to ip_maxbits for the family).
      16             :  * 5. The union's commonbits value is C.
      17             :  * 6. The union's address value is the same as the common prefix for its
      18             :  * first C bits, and is zeroes to the right of that.  The physical width
      19             :  * of the address value is ip_maxbits for the address family.
      20             :  *
      21             :  * In a leaf index entry (representing a single key), commonbits is equal to
      22             :  * ip_maxbits for the address family, minbits is the same as the represented
      23             :  * value's ip_bits, and the address is equal to the represented address.
      24             :  * Although it may appear that we're wasting a byte by storing the union
      25             :  * format and not just the represented INET/CIDR value in leaf keys, the
      26             :  * extra byte is actually "free" because of alignment considerations.
      27             :  *
      28             :  * Note that this design tracks minbits and commonbits independently; in any
      29             :  * given union value, either might be smaller than the other.  This does not
      30             :  * help us much when descending the tree, because of the way inet comparison
      31             :  * is defined: at non-leaf nodes we can't compare more than minbits bits
      32             :  * even if we know them.  However, it greatly improves the quality of split
      33             :  * decisions.  Preliminary testing suggests that searches are as much as
      34             :  * twice as fast as for a simpler design in which a single field doubles as
      35             :  * the common prefix length and the minimum ip_bits value.
      36             :  *
      37             :  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
      38             :  * Portions Copyright (c) 1994, Regents of the University of California
      39             :  *
      40             :  *
      41             :  * IDENTIFICATION
      42             :  *    src/backend/utils/adt/network_gist.c
      43             :  *
      44             :  *-------------------------------------------------------------------------
      45             :  */
      46             : #include "postgres.h"
      47             : 
      48             : #include <sys/socket.h>
      49             : 
      50             : #include "access/gist.h"
      51             : #include "access/stratnum.h"
      52             : #include "utils/fmgrprotos.h"
      53             : #include "utils/inet.h"
      54             : #include "varatt.h"
      55             : 
      56             : /*
      57             :  * Operator strategy numbers used in the GiST inet_ops opclass
      58             :  */
      59             : #define INETSTRAT_OVERLAPS      RTOverlapStrategyNumber
      60             : #define INETSTRAT_EQ            RTEqualStrategyNumber
      61             : #define INETSTRAT_NE            RTNotEqualStrategyNumber
      62             : #define INETSTRAT_LT            RTLessStrategyNumber
      63             : #define INETSTRAT_LE            RTLessEqualStrategyNumber
      64             : #define INETSTRAT_GT            RTGreaterStrategyNumber
      65             : #define INETSTRAT_GE            RTGreaterEqualStrategyNumber
      66             : #define INETSTRAT_SUB           RTSubStrategyNumber
      67             : #define INETSTRAT_SUBEQ         RTSubEqualStrategyNumber
      68             : #define INETSTRAT_SUP           RTSuperStrategyNumber
      69             : #define INETSTRAT_SUPEQ         RTSuperEqualStrategyNumber
      70             : 
      71             : 
      72             : /*
      73             :  * Representation of a GiST INET/CIDR index key.  This is not identical to
      74             :  * INET/CIDR because we need to keep track of the length of the common address
      75             :  * prefix as well as the minimum netmask length.  However, as long as it
      76             :  * follows varlena header rules, the core GiST code won't know the difference.
      77             :  * For simplicity we always use 1-byte-header varlena format.
      78             :  */
      79             : typedef struct GistInetKey
      80             : {
      81             :     uint8       va_header;      /* varlena header --- don't touch directly */
      82             :     unsigned char family;       /* PGSQL_AF_INET, PGSQL_AF_INET6, or zero */
      83             :     unsigned char minbits;      /* minimum number of bits in netmask */
      84             :     unsigned char commonbits;   /* number of common prefix bits in addresses */
      85             :     unsigned char ipaddr[16];   /* up to 128 bits of common address */
      86             : } GistInetKey;
      87             : 
      88             : #define DatumGetInetKeyP(X) ((GistInetKey *) DatumGetPointer(X))
      89             : #define InetKeyPGetDatum(X) PointerGetDatum(X)
      90             : 
      91             : /*
      92             :  * Access macros; not really exciting, but we use these for notational
      93             :  * consistency with access to INET/CIDR values.  Note that family-zero values
      94             :  * are stored with 4 bytes of address, not 16.
      95             :  */
      96             : #define gk_ip_family(gkptr)     ((gkptr)->family)
      97             : #define gk_ip_minbits(gkptr)    ((gkptr)->minbits)
      98             : #define gk_ip_commonbits(gkptr) ((gkptr)->commonbits)
      99             : #define gk_ip_addr(gkptr)       ((gkptr)->ipaddr)
     100             : #define ip_family_maxbits(fam)  ((fam) == PGSQL_AF_INET6 ? 128 : 32)
     101             : 
     102             : /* These require that the family field has been set: */
     103             : #define gk_ip_addrsize(gkptr) \
     104             :     (gk_ip_family(gkptr) == PGSQL_AF_INET6 ? 16 : 4)
     105             : #define gk_ip_maxbits(gkptr) \
     106             :     ip_family_maxbits(gk_ip_family(gkptr))
     107             : #define SET_GK_VARSIZE(dst) \
     108             :     SET_VARSIZE_SHORT(dst, offsetof(GistInetKey, ipaddr) + gk_ip_addrsize(dst))
     109             : 
     110             : 
     111             : /*
     112             :  * The GiST query consistency check
     113             :  */
     114             : Datum
     115        1224 : inet_gist_consistent(PG_FUNCTION_ARGS)
     116             : {
     117        1224 :     GISTENTRY  *ent = (GISTENTRY *) PG_GETARG_POINTER(0);
     118        1224 :     inet       *query = PG_GETARG_INET_PP(1);
     119        1224 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
     120             : 
     121             :     /* Oid      subtype = PG_GETARG_OID(3); */
     122        1224 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     123        1224 :     GistInetKey *key = DatumGetInetKeyP(ent->key);
     124             :     int         minbits,
     125             :                 order;
     126             : 
     127             :     /* All operators served by this function are exact. */
     128        1224 :     *recheck = false;
     129             : 
     130             :     /*
     131             :      * Check 0: different families
     132             :      *
     133             :      * If key represents multiple address families, its children could match
     134             :      * anything.  This can only happen on an inner index page.
     135             :      */
     136        1224 :     if (gk_ip_family(key) == 0)
     137             :     {
     138             :         Assert(!GIST_LEAF(ent));
     139           0 :         PG_RETURN_BOOL(true);
     140             :     }
     141             : 
     142             :     /*
     143             :      * Check 1: different families
     144             :      *
     145             :      * Matching families do not help any of the strategies.
     146             :      */
     147        1224 :     if (gk_ip_family(key) != ip_family(query))
     148             :     {
     149         216 :         switch (strategy)
     150             :         {
     151          36 :             case INETSTRAT_LT:
     152             :             case INETSTRAT_LE:
     153          36 :                 if (gk_ip_family(key) < ip_family(query))
     154           0 :                     PG_RETURN_BOOL(true);
     155          36 :                 break;
     156             : 
     157          36 :             case INETSTRAT_GE:
     158             :             case INETSTRAT_GT:
     159          36 :                 if (gk_ip_family(key) > ip_family(query))
     160          36 :                     PG_RETURN_BOOL(true);
     161           0 :                 break;
     162             : 
     163          18 :             case INETSTRAT_NE:
     164          18 :                 PG_RETURN_BOOL(true);
     165             :         }
     166             :         /* For all other cases, we can be sure there is no match */
     167         162 :         PG_RETURN_BOOL(false);
     168             :     }
     169             : 
     170             :     /*
     171             :      * Check 2: network bit count
     172             :      *
     173             :      * Network bit count (ip_bits) helps to check leaves for sub network and
     174             :      * sup network operators.  At non-leaf nodes, we know every child value
     175             :      * has ip_bits >= gk_ip_minbits(key), so we can avoid descending in some
     176             :      * cases too.
     177             :      */
     178        1008 :     switch (strategy)
     179             :     {
     180         168 :         case INETSTRAT_SUB:
     181         168 :             if (GIST_LEAF(ent) && gk_ip_minbits(key) <= ip_bits(query))
     182         120 :                 PG_RETURN_BOOL(false);
     183          48 :             break;
     184             : 
     185          84 :         case INETSTRAT_SUBEQ:
     186          84 :             if (GIST_LEAF(ent) && gk_ip_minbits(key) < ip_bits(query))
     187          36 :                 PG_RETURN_BOOL(false);
     188          48 :             break;
     189             : 
     190         168 :         case INETSTRAT_SUPEQ:
     191             :         case INETSTRAT_EQ:
     192         168 :             if (gk_ip_minbits(key) > ip_bits(query))
     193          48 :                 PG_RETURN_BOOL(false);
     194         120 :             break;
     195             : 
     196          84 :         case INETSTRAT_SUP:
     197          84 :             if (gk_ip_minbits(key) >= ip_bits(query))
     198          48 :                 PG_RETURN_BOOL(false);
     199          36 :             break;
     200             :     }
     201             : 
     202             :     /*
     203             :      * Check 3: common network bits
     204             :      *
     205             :      * Compare available common prefix bits to the query, but not beyond
     206             :      * either the query's netmask or the minimum netmask among the represented
     207             :      * values.  If these bits don't match the query, we have our answer (and
     208             :      * may or may not need to descend, depending on the operator).  If they do
     209             :      * match, and we are not at a leaf, we descend in all cases.
     210             :      *
     211             :      * Note this is the final check for operators that only consider the
     212             :      * network part of the address.
     213             :      */
     214         756 :     minbits = Min(gk_ip_commonbits(key), gk_ip_minbits(key));
     215         756 :     minbits = Min(minbits, ip_bits(query));
     216             : 
     217         756 :     order = bitncmp(gk_ip_addr(key), ip_addr(query), minbits);
     218             : 
     219         756 :     switch (strategy)
     220             :     {
     221         276 :         case INETSTRAT_SUB:
     222             :         case INETSTRAT_SUBEQ:
     223             :         case INETSTRAT_OVERLAPS:
     224             :         case INETSTRAT_SUPEQ:
     225             :         case INETSTRAT_SUP:
     226         276 :             PG_RETURN_BOOL(order == 0);
     227             : 
     228         168 :         case INETSTRAT_LT:
     229             :         case INETSTRAT_LE:
     230         168 :             if (order > 0)
     231           0 :                 PG_RETURN_BOOL(false);
     232         168 :             if (order < 0 || !GIST_LEAF(ent))
     233          96 :                 PG_RETURN_BOOL(true);
     234          72 :             break;
     235             : 
     236          60 :         case INETSTRAT_EQ:
     237          60 :             if (order != 0)
     238          42 :                 PG_RETURN_BOOL(false);
     239          18 :             if (!GIST_LEAF(ent))
     240           0 :                 PG_RETURN_BOOL(true);
     241          18 :             break;
     242             : 
     243         168 :         case INETSTRAT_GE:
     244             :         case INETSTRAT_GT:
     245         168 :             if (order < 0)
     246          96 :                 PG_RETURN_BOOL(false);
     247          72 :             if (order > 0 || !GIST_LEAF(ent))
     248           0 :                 PG_RETURN_BOOL(true);
     249          72 :             break;
     250             : 
     251          84 :         case INETSTRAT_NE:
     252          84 :             if (order != 0 || !GIST_LEAF(ent))
     253          48 :                 PG_RETURN_BOOL(true);
     254          36 :             break;
     255             :     }
     256             : 
     257             :     /*
     258             :      * Remaining checks are only for leaves and basic comparison strategies.
     259             :      * See network_cmp_internal() in network.c for the implementation we need
     260             :      * to match.  Note that in a leaf key, commonbits should equal the address
     261             :      * length, so we compared the whole network parts above.
     262             :      */
     263         198 :     Assert(GIST_LEAF(ent));
     264             : 
     265             :     /*
     266             :      * Check 4: network bit count
     267             :      *
     268             :      * Next step is to compare netmask widths.
     269             :      */
     270         198 :     switch (strategy)
     271             :     {
     272          72 :         case INETSTRAT_LT:
     273             :         case INETSTRAT_LE:
     274          72 :             if (gk_ip_minbits(key) < ip_bits(query))
     275           0 :                 PG_RETURN_BOOL(true);
     276          72 :             if (gk_ip_minbits(key) > ip_bits(query))
     277          36 :                 PG_RETURN_BOOL(false);
     278          36 :             break;
     279             : 
     280          18 :         case INETSTRAT_EQ:
     281          18 :             if (gk_ip_minbits(key) != ip_bits(query))
     282           0 :                 PG_RETURN_BOOL(false);
     283          18 :             break;
     284             : 
     285          72 :         case INETSTRAT_GE:
     286             :         case INETSTRAT_GT:
     287          72 :             if (gk_ip_minbits(key) > ip_bits(query))
     288          36 :                 PG_RETURN_BOOL(true);
     289          36 :             if (gk_ip_minbits(key) < ip_bits(query))
     290           0 :                 PG_RETURN_BOOL(false);
     291          36 :             break;
     292             : 
     293          36 :         case INETSTRAT_NE:
     294          36 :             if (gk_ip_minbits(key) != ip_bits(query))
     295          18 :                 PG_RETURN_BOOL(true);
     296          18 :             break;
     297             :     }
     298             : 
     299             :     /*
     300             :      * Check 5: whole address
     301             :      *
     302             :      * Netmask bit counts are the same, so check all the address bits.
     303             :      */
     304         108 :     order = bitncmp(gk_ip_addr(key), ip_addr(query), gk_ip_maxbits(key));
     305             : 
     306         108 :     switch (strategy)
     307             :     {
     308          18 :         case INETSTRAT_LT:
     309          18 :             PG_RETURN_BOOL(order < 0);
     310             : 
     311          18 :         case INETSTRAT_LE:
     312          18 :             PG_RETURN_BOOL(order <= 0);
     313             : 
     314          18 :         case INETSTRAT_EQ:
     315          18 :             PG_RETURN_BOOL(order == 0);
     316             : 
     317          18 :         case INETSTRAT_GE:
     318          18 :             PG_RETURN_BOOL(order >= 0);
     319             : 
     320          18 :         case INETSTRAT_GT:
     321          18 :             PG_RETURN_BOOL(order > 0);
     322             : 
     323          18 :         case INETSTRAT_NE:
     324          18 :             PG_RETURN_BOOL(order != 0);
     325             :     }
     326             : 
     327           0 :     elog(ERROR, "unknown strategy for inet GiST");
     328             :     PG_RETURN_BOOL(false);      /* keep compiler quiet */
     329             : }
     330             : 
     331             : /*
     332             :  * Calculate parameters of the union of some GistInetKeys.
     333             :  *
     334             :  * Examine the keys in elements m..n inclusive of the GISTENTRY array,
     335             :  * and compute these output parameters:
     336             :  * *minfamily_p = minimum IP address family number
     337             :  * *maxfamily_p = maximum IP address family number
     338             :  * *minbits_p = minimum netmask width
     339             :  * *commonbits_p = number of leading bits in common among the addresses
     340             :  *
     341             :  * minbits and commonbits are forced to zero if there's more than one
     342             :  * address family.
     343             :  */
     344             : static void
     345         830 : calc_inet_union_params(GISTENTRY *ent,
     346             :                        int m, int n,
     347             :                        int *minfamily_p,
     348             :                        int *maxfamily_p,
     349             :                        int *minbits_p,
     350             :                        int *commonbits_p)
     351             : {
     352             :     int         minfamily,
     353             :                 maxfamily,
     354             :                 minbits,
     355             :                 commonbits;
     356             :     unsigned char *addr;
     357             :     GistInetKey *tmp;
     358             :     int         i;
     359             : 
     360             :     /* Must be at least one key. */
     361             :     Assert(m <= n);
     362             : 
     363             :     /* Initialize variables using the first key. */
     364         830 :     tmp = DatumGetInetKeyP(ent[m].key);
     365         830 :     minfamily = maxfamily = gk_ip_family(tmp);
     366         830 :     minbits = gk_ip_minbits(tmp);
     367         830 :     commonbits = gk_ip_commonbits(tmp);
     368         830 :     addr = gk_ip_addr(tmp);
     369             : 
     370             :     /* Scan remaining keys. */
     371        3240 :     for (i = m + 1; i <= n; i++)
     372             :     {
     373        2410 :         tmp = DatumGetInetKeyP(ent[i].key);
     374             : 
     375             :         /* Determine range of family numbers */
     376        2410 :         if (minfamily > gk_ip_family(tmp))
     377           0 :             minfamily = gk_ip_family(tmp);
     378        2410 :         if (maxfamily < gk_ip_family(tmp))
     379           0 :             maxfamily = gk_ip_family(tmp);
     380             : 
     381             :         /* Find minimum minbits */
     382        2410 :         if (minbits > gk_ip_minbits(tmp))
     383           0 :             minbits = gk_ip_minbits(tmp);
     384             : 
     385             :         /* Find minimum number of bits in common */
     386        2410 :         if (commonbits > gk_ip_commonbits(tmp))
     387           0 :             commonbits = gk_ip_commonbits(tmp);
     388        2410 :         if (commonbits > 0)
     389        1646 :             commonbits = bitncommon(addr, gk_ip_addr(tmp), commonbits);
     390             :     }
     391             : 
     392             :     /* Force minbits/commonbits to zero if more than one family. */
     393         830 :     if (minfamily != maxfamily)
     394           0 :         minbits = commonbits = 0;
     395             : 
     396         830 :     *minfamily_p = minfamily;
     397         830 :     *maxfamily_p = maxfamily;
     398         830 :     *minbits_p = minbits;
     399         830 :     *commonbits_p = commonbits;
     400         830 : }
     401             : 
     402             : /*
     403             :  * Same as above, but the GISTENTRY elements to examine are those with
     404             :  * indices listed in the offsets[] array.
     405             :  */
     406             : static void
     407           0 : calc_inet_union_params_indexed(GISTENTRY *ent,
     408             :                                OffsetNumber *offsets, int noffsets,
     409             :                                int *minfamily_p,
     410             :                                int *maxfamily_p,
     411             :                                int *minbits_p,
     412             :                                int *commonbits_p)
     413             : {
     414             :     int         minfamily,
     415             :                 maxfamily,
     416             :                 minbits,
     417             :                 commonbits;
     418             :     unsigned char *addr;
     419             :     GistInetKey *tmp;
     420             :     int         i;
     421             : 
     422             :     /* Must be at least one key. */
     423             :     Assert(noffsets > 0);
     424             : 
     425             :     /* Initialize variables using the first key. */
     426           0 :     tmp = DatumGetInetKeyP(ent[offsets[0]].key);
     427           0 :     minfamily = maxfamily = gk_ip_family(tmp);
     428           0 :     minbits = gk_ip_minbits(tmp);
     429           0 :     commonbits = gk_ip_commonbits(tmp);
     430           0 :     addr = gk_ip_addr(tmp);
     431             : 
     432             :     /* Scan remaining keys. */
     433           0 :     for (i = 1; i < noffsets; i++)
     434             :     {
     435           0 :         tmp = DatumGetInetKeyP(ent[offsets[i]].key);
     436             : 
     437             :         /* Determine range of family numbers */
     438           0 :         if (minfamily > gk_ip_family(tmp))
     439           0 :             minfamily = gk_ip_family(tmp);
     440           0 :         if (maxfamily < gk_ip_family(tmp))
     441           0 :             maxfamily = gk_ip_family(tmp);
     442             : 
     443             :         /* Find minimum minbits */
     444           0 :         if (minbits > gk_ip_minbits(tmp))
     445           0 :             minbits = gk_ip_minbits(tmp);
     446             : 
     447             :         /* Find minimum number of bits in common */
     448           0 :         if (commonbits > gk_ip_commonbits(tmp))
     449           0 :             commonbits = gk_ip_commonbits(tmp);
     450           0 :         if (commonbits > 0)
     451           0 :             commonbits = bitncommon(addr, gk_ip_addr(tmp), commonbits);
     452             :     }
     453             : 
     454             :     /* Force minbits/commonbits to zero if more than one family. */
     455           0 :     if (minfamily != maxfamily)
     456           0 :         minbits = commonbits = 0;
     457             : 
     458           0 :     *minfamily_p = minfamily;
     459           0 :     *maxfamily_p = maxfamily;
     460           0 :     *minbits_p = minbits;
     461           0 :     *commonbits_p = commonbits;
     462           0 : }
     463             : 
     464             : /*
     465             :  * Construct a GistInetKey representing a union value.
     466             :  *
     467             :  * Inputs are the family/minbits/commonbits values to use, plus a pointer to
     468             :  * the address field of one of the union inputs.  (Since we're going to copy
     469             :  * just the bits-in-common, it doesn't matter which one.)
     470             :  */
     471             : static GistInetKey *
     472         830 : build_inet_union_key(int family, int minbits, int commonbits,
     473             :                      unsigned char *addr)
     474             : {
     475             :     GistInetKey *result;
     476             : 
     477             :     /* Make sure any unused bits are zeroed. */
     478         830 :     result = (GistInetKey *) palloc0(sizeof(GistInetKey));
     479             : 
     480         830 :     gk_ip_family(result) = family;
     481         830 :     gk_ip_minbits(result) = minbits;
     482         830 :     gk_ip_commonbits(result) = commonbits;
     483             : 
     484             :     /* Clone appropriate bytes of the address. */
     485         830 :     if (commonbits > 0)
     486         488 :         memcpy(gk_ip_addr(result), addr, (commonbits + 7) / 8);
     487             : 
     488             :     /* Clean any unwanted bits in the last partial byte. */
     489         830 :     if (commonbits % 8 != 0)
     490         488 :         gk_ip_addr(result)[commonbits / 8] &= ~(0xFF >> (commonbits % 8));
     491             : 
     492             :     /* Set varlena header correctly. */
     493         830 :     SET_GK_VARSIZE(result);
     494             : 
     495         830 :     return result;
     496             : }
     497             : 
     498             : 
     499             : /*
     500             :  * The GiST union function
     501             :  *
     502             :  * See comments at head of file for the definition of the union.
     503             :  */
     504             : Datum
     505         830 : inet_gist_union(PG_FUNCTION_ARGS)
     506             : {
     507         830 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     508         830 :     GISTENTRY  *ent = entryvec->vector;
     509             :     int         minfamily,
     510             :                 maxfamily,
     511             :                 minbits,
     512             :                 commonbits;
     513             :     unsigned char *addr;
     514             :     GistInetKey *tmp,
     515             :                *result;
     516             : 
     517             :     /* Determine parameters of the union. */
     518         830 :     calc_inet_union_params(ent, 0, entryvec->n - 1,
     519             :                            &minfamily, &maxfamily,
     520             :                            &minbits, &commonbits);
     521             : 
     522             :     /* If more than one family, emit family number zero. */
     523         830 :     if (minfamily != maxfamily)
     524           0 :         minfamily = 0;
     525             : 
     526             :     /* Initialize address using the first key. */
     527         830 :     tmp = DatumGetInetKeyP(ent[0].key);
     528         830 :     addr = gk_ip_addr(tmp);
     529             : 
     530             :     /* Construct the union value. */
     531         830 :     result = build_inet_union_key(minfamily, minbits, commonbits, addr);
     532             : 
     533         830 :     PG_RETURN_POINTER(result);
     534             : }
     535             : 
     536             : /*
     537             :  * The GiST compress function
     538             :  *
     539             :  * Convert an inet value to GistInetKey.
     540             :  */
     541             : Datum
     542        1324 : inet_gist_compress(PG_FUNCTION_ARGS)
     543             : {
     544        1324 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     545             :     GISTENTRY  *retval;
     546             : 
     547        1324 :     if (entry->leafkey)
     548             :     {
     549        1302 :         retval = palloc(sizeof(GISTENTRY));
     550        1302 :         if (DatumGetPointer(entry->key) != NULL)
     551             :         {
     552        1302 :             inet       *in = DatumGetInetPP(entry->key);
     553             :             GistInetKey *r;
     554             : 
     555        1302 :             r = (GistInetKey *) palloc0(sizeof(GistInetKey));
     556             : 
     557        1302 :             gk_ip_family(r) = ip_family(in);
     558        1302 :             gk_ip_minbits(r) = ip_bits(in);
     559        1302 :             gk_ip_commonbits(r) = gk_ip_maxbits(r);
     560        1302 :             memcpy(gk_ip_addr(r), ip_addr(in), gk_ip_addrsize(r));
     561        1302 :             SET_GK_VARSIZE(r);
     562             : 
     563        1302 :             gistentryinit(*retval, PointerGetDatum(r),
     564             :                           entry->rel, entry->page,
     565             :                           entry->offset, false);
     566             :         }
     567             :         else
     568             :         {
     569           0 :             gistentryinit(*retval, (Datum) 0,
     570             :                           entry->rel, entry->page,
     571             :                           entry->offset, false);
     572             :         }
     573             :     }
     574             :     else
     575          22 :         retval = entry;
     576        1324 :     PG_RETURN_POINTER(retval);
     577             : }
     578             : 
     579             : /*
     580             :  * We do not need a decompress function, because the other GiST inet
     581             :  * support functions work with the GistInetKey representation.
     582             :  */
     583             : 
     584             : /*
     585             :  * The GiST fetch function
     586             :  *
     587             :  * Reconstruct the original inet datum from a GistInetKey.
     588             :  */
     589             : Datum
     590          20 : inet_gist_fetch(PG_FUNCTION_ARGS)
     591             : {
     592          20 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     593          20 :     GistInetKey *key = DatumGetInetKeyP(entry->key);
     594             :     GISTENTRY  *retval;
     595             :     inet       *dst;
     596             : 
     597          20 :     dst = (inet *) palloc0(sizeof(inet));
     598             : 
     599          20 :     ip_family(dst) = gk_ip_family(key);
     600          20 :     ip_bits(dst) = gk_ip_minbits(key);
     601          20 :     memcpy(ip_addr(dst), gk_ip_addr(key), ip_addrsize(dst));
     602          20 :     SET_INET_VARSIZE(dst);
     603             : 
     604          20 :     retval = palloc(sizeof(GISTENTRY));
     605          20 :     gistentryinit(*retval, InetPGetDatum(dst), entry->rel, entry->page,
     606             :                   entry->offset, false);
     607             : 
     608          20 :     PG_RETURN_POINTER(retval);
     609             : }
     610             : 
     611             : /*
     612             :  * The GiST page split penalty function
     613             :  *
     614             :  * Charge a large penalty if address family doesn't match, or a somewhat
     615             :  * smaller one if the new value would degrade the union's minbits
     616             :  * (minimum netmask width).  Otherwise, penalty is inverse of the
     617             :  * new number of common address bits.
     618             :  */
     619             : Datum
     620        1446 : inet_gist_penalty(PG_FUNCTION_ARGS)
     621             : {
     622        1446 :     GISTENTRY  *origent = (GISTENTRY *) PG_GETARG_POINTER(0);
     623        1446 :     GISTENTRY  *newent = (GISTENTRY *) PG_GETARG_POINTER(1);
     624        1446 :     float      *penalty = (float *) PG_GETARG_POINTER(2);
     625        1446 :     GistInetKey *orig = DatumGetInetKeyP(origent->key),
     626        1446 :                *new = DatumGetInetKeyP(newent->key);
     627             :     int         commonbits;
     628             : 
     629        1446 :     if (gk_ip_family(orig) == gk_ip_family(new))
     630             :     {
     631        1446 :         if (gk_ip_minbits(orig) <= gk_ip_minbits(new))
     632             :         {
     633        1446 :             commonbits = bitncommon(gk_ip_addr(orig), gk_ip_addr(new),
     634        1446 :                                     Min(gk_ip_commonbits(orig),
     635             :                                         gk_ip_commonbits(new)));
     636        1446 :             if (commonbits > 0)
     637         612 :                 *penalty = 1.0f / commonbits;
     638             :             else
     639         834 :                 *penalty = 2;
     640             :         }
     641             :         else
     642           0 :             *penalty = 3;
     643             :     }
     644             :     else
     645           0 :         *penalty = 4;
     646             : 
     647        1446 :     PG_RETURN_POINTER(penalty);
     648             : }
     649             : 
     650             : /*
     651             :  * The GiST PickSplit method
     652             :  *
     653             :  * There are two ways to split. First one is to split by address families,
     654             :  * if there are multiple families appearing in the input.
     655             :  *
     656             :  * The second and more common way is to split by addresses. To achieve this,
     657             :  * determine the number of leading bits shared by all the keys, then split on
     658             :  * the next bit.  (We don't currently consider the netmask widths while doing
     659             :  * this; should we?)  If we fail to get a nontrivial split that way, split
     660             :  * 50-50.
     661             :  */
     662             : Datum
     663           0 : inet_gist_picksplit(PG_FUNCTION_ARGS)
     664             : {
     665           0 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     666           0 :     GIST_SPLITVEC *splitvec = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
     667           0 :     GISTENTRY  *ent = entryvec->vector;
     668             :     int         minfamily,
     669             :                 maxfamily,
     670             :                 minbits,
     671             :                 commonbits;
     672             :     unsigned char *addr;
     673             :     GistInetKey *tmp,
     674             :                *left_union,
     675             :                *right_union;
     676             :     int         maxoff,
     677             :                 nbytes;
     678             :     OffsetNumber i,
     679             :                *left,
     680             :                *right;
     681             : 
     682           0 :     maxoff = entryvec->n - 1;
     683           0 :     nbytes = (maxoff + 1) * sizeof(OffsetNumber);
     684             : 
     685           0 :     left = (OffsetNumber *) palloc(nbytes);
     686           0 :     right = (OffsetNumber *) palloc(nbytes);
     687             : 
     688           0 :     splitvec->spl_left = left;
     689           0 :     splitvec->spl_right = right;
     690             : 
     691           0 :     splitvec->spl_nleft = 0;
     692           0 :     splitvec->spl_nright = 0;
     693             : 
     694             :     /* Determine parameters of the union of all the inputs. */
     695           0 :     calc_inet_union_params(ent, FirstOffsetNumber, maxoff,
     696             :                            &minfamily, &maxfamily,
     697             :                            &minbits, &commonbits);
     698             : 
     699           0 :     if (minfamily != maxfamily)
     700             :     {
     701             :         /* Multiple families, so split by family. */
     702           0 :         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
     703             :         {
     704             :             /*
     705             :              * If there's more than 2 families, all but maxfamily go into the
     706             :              * left union.  This could only happen if the inputs include some
     707             :              * IPv4, some IPv6, and some already-multiple-family unions.
     708             :              */
     709           0 :             tmp = DatumGetInetKeyP(ent[i].key);
     710           0 :             if (gk_ip_family(tmp) != maxfamily)
     711           0 :                 left[splitvec->spl_nleft++] = i;
     712             :             else
     713           0 :                 right[splitvec->spl_nright++] = i;
     714             :         }
     715             :     }
     716             :     else
     717             :     {
     718             :         /*
     719             :          * Split on the next bit after the common bits.  If that yields a
     720             :          * trivial split, try the next bit position to the right.  Repeat till
     721             :          * success; or if we run out of bits, do an arbitrary 50-50 split.
     722             :          */
     723           0 :         int         maxbits = ip_family_maxbits(minfamily);
     724             : 
     725           0 :         while (commonbits < maxbits)
     726             :         {
     727             :             /* Split using the commonbits'th bit position. */
     728           0 :             int         bitbyte = commonbits / 8;
     729           0 :             int         bitmask = 0x80 >> (commonbits % 8);
     730             : 
     731           0 :             splitvec->spl_nleft = splitvec->spl_nright = 0;
     732             : 
     733           0 :             for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
     734             :             {
     735           0 :                 tmp = DatumGetInetKeyP(ent[i].key);
     736           0 :                 addr = gk_ip_addr(tmp);
     737           0 :                 if ((addr[bitbyte] & bitmask) == 0)
     738           0 :                     left[splitvec->spl_nleft++] = i;
     739             :                 else
     740           0 :                     right[splitvec->spl_nright++] = i;
     741             :             }
     742             : 
     743           0 :             if (splitvec->spl_nleft > 0 && splitvec->spl_nright > 0)
     744           0 :                 break;          /* success */
     745           0 :             commonbits++;
     746             :         }
     747             : 
     748           0 :         if (commonbits >= maxbits)
     749             :         {
     750             :             /* Failed ... do a 50-50 split. */
     751           0 :             splitvec->spl_nleft = splitvec->spl_nright = 0;
     752             : 
     753           0 :             for (i = FirstOffsetNumber; i <= maxoff / 2; i = OffsetNumberNext(i))
     754             :             {
     755           0 :                 left[splitvec->spl_nleft++] = i;
     756             :             }
     757           0 :             for (; i <= maxoff; i = OffsetNumberNext(i))
     758             :             {
     759           0 :                 right[splitvec->spl_nright++] = i;
     760             :             }
     761             :         }
     762             :     }
     763             : 
     764             :     /*
     765             :      * Compute the union value for each side from scratch.  In most cases we
     766             :      * could approximate the union values with what we already know, but this
     767             :      * ensures that each side has minbits and commonbits set as high as
     768             :      * possible.
     769             :      */
     770           0 :     calc_inet_union_params_indexed(ent, left, splitvec->spl_nleft,
     771             :                                    &minfamily, &maxfamily,
     772             :                                    &minbits, &commonbits);
     773           0 :     if (minfamily != maxfamily)
     774           0 :         minfamily = 0;
     775           0 :     tmp = DatumGetInetKeyP(ent[left[0]].key);
     776           0 :     addr = gk_ip_addr(tmp);
     777           0 :     left_union = build_inet_union_key(minfamily, minbits, commonbits, addr);
     778           0 :     splitvec->spl_ldatum = PointerGetDatum(left_union);
     779             : 
     780           0 :     calc_inet_union_params_indexed(ent, right, splitvec->spl_nright,
     781             :                                    &minfamily, &maxfamily,
     782             :                                    &minbits, &commonbits);
     783           0 :     if (minfamily != maxfamily)
     784           0 :         minfamily = 0;
     785           0 :     tmp = DatumGetInetKeyP(ent[right[0]].key);
     786           0 :     addr = gk_ip_addr(tmp);
     787           0 :     right_union = build_inet_union_key(minfamily, minbits, commonbits, addr);
     788           0 :     splitvec->spl_rdatum = PointerGetDatum(right_union);
     789             : 
     790           0 :     PG_RETURN_POINTER(splitvec);
     791             : }
     792             : 
     793             : /*
     794             :  * The GiST equality function
     795             :  */
     796             : Datum
     797         808 : inet_gist_same(PG_FUNCTION_ARGS)
     798             : {
     799         808 :     GistInetKey *left = DatumGetInetKeyP(PG_GETARG_DATUM(0));
     800         808 :     GistInetKey *right = DatumGetInetKeyP(PG_GETARG_DATUM(1));
     801         808 :     bool       *result = (bool *) PG_GETARG_POINTER(2);
     802             : 
     803        2424 :     *result = (gk_ip_family(left) == gk_ip_family(right) &&
     804         808 :                gk_ip_minbits(left) == gk_ip_minbits(right) &&
     805        2424 :                gk_ip_commonbits(left) == gk_ip_commonbits(right) &&
     806         808 :                memcmp(gk_ip_addr(left), gk_ip_addr(right),
     807         808 :                       gk_ip_addrsize(left)) == 0);
     808             : 
     809         808 :     PG_RETURN_POINTER(result);
     810             : }

Generated by: LCOV version 1.14