LCOV - code coverage report
Current view: top level - src/backend/utils/adt - network_spgist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 134 301 44.5 %
Date: 2024-07-18 17:11:54 Functions: 3 7 42.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * network_spgist.c
       4             :  *    SP-GiST support for network types.
       5             :  *
       6             :  * We split inet index entries first by address family (IPv4 or IPv6).
       7             :  * If the entries below a given inner tuple are all of the same family,
       8             :  * we identify their common prefix and split by the next bit of the address,
       9             :  * and by whether their masklens exceed the length of the common prefix.
      10             :  *
      11             :  * An inner tuple that has both IPv4 and IPv6 children has a null prefix
      12             :  * and exactly two nodes, the first being for IPv4 and the second for IPv6.
      13             :  *
      14             :  * Otherwise, the prefix is a CIDR value representing the common prefix,
      15             :  * and there are exactly four nodes.  Node numbers 0 and 1 are for addresses
      16             :  * with the same masklen as the prefix, while node numbers 2 and 3 are for
      17             :  * addresses with larger masklen.  (We do not allow a tuple to contain
      18             :  * entries with masklen smaller than its prefix's.)  Node numbers 0 and 1
      19             :  * are distinguished by the next bit of the address after the common prefix,
      20             :  * and likewise for node numbers 2 and 3.  If there are no more bits in
      21             :  * the address family, everything goes into node 0 (which will probably
      22             :  * lead to creating an allTheSame tuple).
      23             :  *
      24             :  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
      25             :  * Portions Copyright (c) 1994, Regents of the University of California
      26             :  *
      27             :  * IDENTIFICATION
      28             :  *          src/backend/utils/adt/network_spgist.c
      29             :  *
      30             :  *-------------------------------------------------------------------------
      31             :  */
      32             : #include "postgres.h"
      33             : 
      34             : #include <sys/socket.h>
      35             : 
      36             : #include "access/spgist.h"
      37             : #include "catalog/pg_type.h"
      38             : #include "utils/fmgrprotos.h"
      39             : #include "utils/inet.h"
      40             : #include "varatt.h"
      41             : 
      42             : 
      43             : static int  inet_spg_node_number(const inet *val, int commonbits);
      44             : static int  inet_spg_consistent_bitmap(const inet *prefix, int nkeys,
      45             :                                        ScanKey scankeys, bool leaf);
      46             : 
      47             : /*
      48             :  * The SP-GiST configuration function
      49             :  */
      50             : Datum
      51          18 : inet_spg_config(PG_FUNCTION_ARGS)
      52             : {
      53             :     /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
      54          18 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
      55             : 
      56          18 :     cfg->prefixType = CIDROID;
      57          18 :     cfg->labelType = VOIDOID;
      58          18 :     cfg->canReturnData = true;
      59          18 :     cfg->longValuesOK = false;
      60             : 
      61          18 :     PG_RETURN_VOID();
      62             : }
      63             : 
      64             : /*
      65             :  * The SP-GiST choose function
      66             :  */
      67             : Datum
      68           0 : inet_spg_choose(PG_FUNCTION_ARGS)
      69             : {
      70           0 :     spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
      71           0 :     spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
      72           0 :     inet       *val = DatumGetInetPP(in->datum),
      73             :                *prefix;
      74             :     int         commonbits;
      75             : 
      76             :     /*
      77             :      * If we're looking at a tuple that splits by address family, choose the
      78             :      * appropriate subnode.
      79             :      */
      80           0 :     if (!in->hasPrefix)
      81             :     {
      82             :         /* allTheSame isn't possible for such a tuple */
      83             :         Assert(!in->allTheSame);
      84             :         Assert(in->nNodes == 2);
      85             : 
      86           0 :         out->resultType = spgMatchNode;
      87           0 :         out->result.matchNode.nodeN = (ip_family(val) == PGSQL_AF_INET) ? 0 : 1;
      88           0 :         out->result.matchNode.restDatum = InetPGetDatum(val);
      89             : 
      90           0 :         PG_RETURN_VOID();
      91             :     }
      92             : 
      93             :     /* Else it must split by prefix */
      94             :     Assert(in->nNodes == 4 || in->allTheSame);
      95             : 
      96           0 :     prefix = DatumGetInetPP(in->prefixDatum);
      97           0 :     commonbits = ip_bits(prefix);
      98             : 
      99             :     /*
     100             :      * We cannot put addresses from different families under the same inner
     101             :      * node, so we have to split if the new value's family is different.
     102             :      */
     103           0 :     if (ip_family(val) != ip_family(prefix))
     104             :     {
     105             :         /* Set up 2-node tuple */
     106           0 :         out->resultType = spgSplitTuple;
     107           0 :         out->result.splitTuple.prefixHasPrefix = false;
     108           0 :         out->result.splitTuple.prefixNNodes = 2;
     109           0 :         out->result.splitTuple.prefixNodeLabels = NULL;
     110             : 
     111             :         /* Identify which node the existing data goes into */
     112           0 :         out->result.splitTuple.childNodeN =
     113           0 :             (ip_family(prefix) == PGSQL_AF_INET) ? 0 : 1;
     114             : 
     115           0 :         out->result.splitTuple.postfixHasPrefix = true;
     116           0 :         out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
     117             : 
     118           0 :         PG_RETURN_VOID();
     119             :     }
     120             : 
     121             :     /*
     122             :      * If the new value does not match the existing prefix, we have to split.
     123             :      */
     124           0 :     if (ip_bits(val) < commonbits ||
     125           0 :         bitncmp(ip_addr(prefix), ip_addr(val), commonbits) != 0)
     126             :     {
     127             :         /* Determine new prefix length for the split tuple */
     128           0 :         commonbits = bitncommon(ip_addr(prefix), ip_addr(val),
     129           0 :                                 Min(ip_bits(val), commonbits));
     130             : 
     131             :         /* Set up 4-node tuple */
     132           0 :         out->resultType = spgSplitTuple;
     133           0 :         out->result.splitTuple.prefixHasPrefix = true;
     134           0 :         out->result.splitTuple.prefixPrefixDatum =
     135           0 :             InetPGetDatum(cidr_set_masklen_internal(val, commonbits));
     136           0 :         out->result.splitTuple.prefixNNodes = 4;
     137           0 :         out->result.splitTuple.prefixNodeLabels = NULL;
     138             : 
     139             :         /* Identify which node the existing data goes into */
     140           0 :         out->result.splitTuple.childNodeN =
     141           0 :             inet_spg_node_number(prefix, commonbits);
     142             : 
     143           0 :         out->result.splitTuple.postfixHasPrefix = true;
     144           0 :         out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
     145             : 
     146           0 :         PG_RETURN_VOID();
     147             :     }
     148             : 
     149             :     /*
     150             :      * All OK, choose the node to descend into.  (If this tuple is marked
     151             :      * allTheSame, the core code will ignore our choice of nodeN; but we need
     152             :      * not account for that case explicitly here.)
     153             :      */
     154           0 :     out->resultType = spgMatchNode;
     155           0 :     out->result.matchNode.nodeN = inet_spg_node_number(val, commonbits);
     156           0 :     out->result.matchNode.restDatum = InetPGetDatum(val);
     157             : 
     158           0 :     PG_RETURN_VOID();
     159             : }
     160             : 
     161             : /*
     162             :  * The GiST PickSplit method
     163             :  */
     164             : Datum
     165           0 : inet_spg_picksplit(PG_FUNCTION_ARGS)
     166             : {
     167           0 :     spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
     168           0 :     spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
     169             :     inet       *prefix,
     170             :                *tmp;
     171             :     int         i,
     172             :                 commonbits;
     173           0 :     bool        differentFamilies = false;
     174             : 
     175             :     /* Initialize the prefix with the first item */
     176           0 :     prefix = DatumGetInetPP(in->datums[0]);
     177           0 :     commonbits = ip_bits(prefix);
     178             : 
     179             :     /* Examine remaining items to discover minimum common prefix length */
     180           0 :     for (i = 1; i < in->nTuples; i++)
     181             :     {
     182           0 :         tmp = DatumGetInetPP(in->datums[i]);
     183             : 
     184           0 :         if (ip_family(tmp) != ip_family(prefix))
     185             :         {
     186           0 :             differentFamilies = true;
     187           0 :             break;
     188             :         }
     189             : 
     190           0 :         if (ip_bits(tmp) < commonbits)
     191           0 :             commonbits = ip_bits(tmp);
     192           0 :         commonbits = bitncommon(ip_addr(prefix), ip_addr(tmp), commonbits);
     193           0 :         if (commonbits == 0)
     194           0 :             break;
     195             :     }
     196             : 
     197             :     /* Don't need labels; allocate output arrays */
     198           0 :     out->nodeLabels = NULL;
     199           0 :     out->mapTuplesToNodes = (int *) palloc(sizeof(int) * in->nTuples);
     200           0 :     out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * in->nTuples);
     201             : 
     202           0 :     if (differentFamilies)
     203             :     {
     204             :         /* Set up 2-node tuple */
     205           0 :         out->hasPrefix = false;
     206           0 :         out->nNodes = 2;
     207             : 
     208           0 :         for (i = 0; i < in->nTuples; i++)
     209             :         {
     210           0 :             tmp = DatumGetInetPP(in->datums[i]);
     211           0 :             out->mapTuplesToNodes[i] =
     212           0 :                 (ip_family(tmp) == PGSQL_AF_INET) ? 0 : 1;
     213           0 :             out->leafTupleDatums[i] = InetPGetDatum(tmp);
     214             :         }
     215             :     }
     216             :     else
     217             :     {
     218             :         /* Set up 4-node tuple */
     219           0 :         out->hasPrefix = true;
     220           0 :         out->prefixDatum =
     221           0 :             InetPGetDatum(cidr_set_masklen_internal(prefix, commonbits));
     222           0 :         out->nNodes = 4;
     223             : 
     224           0 :         for (i = 0; i < in->nTuples; i++)
     225             :         {
     226           0 :             tmp = DatumGetInetPP(in->datums[i]);
     227           0 :             out->mapTuplesToNodes[i] = inet_spg_node_number(tmp, commonbits);
     228           0 :             out->leafTupleDatums[i] = InetPGetDatum(tmp);
     229             :         }
     230             :     }
     231             : 
     232           0 :     PG_RETURN_VOID();
     233             : }
     234             : 
     235             : /*
     236             :  * The SP-GiST query consistency check for inner tuples
     237             :  */
     238             : Datum
     239           0 : inet_spg_inner_consistent(PG_FUNCTION_ARGS)
     240             : {
     241           0 :     spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
     242           0 :     spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
     243             :     int         i;
     244             :     int         which;
     245             : 
     246           0 :     if (!in->hasPrefix)
     247             :     {
     248             :         Assert(!in->allTheSame);
     249             :         Assert(in->nNodes == 2);
     250             : 
     251             :         /* Identify which child nodes need to be visited */
     252           0 :         which = 1 | (1 << 1);
     253             : 
     254           0 :         for (i = 0; i < in->nkeys; i++)
     255             :         {
     256           0 :             StrategyNumber strategy = in->scankeys[i].sk_strategy;
     257           0 :             inet       *argument = DatumGetInetPP(in->scankeys[i].sk_argument);
     258             : 
     259           0 :             switch (strategy)
     260             :             {
     261           0 :                 case RTLessStrategyNumber:
     262             :                 case RTLessEqualStrategyNumber:
     263           0 :                     if (ip_family(argument) == PGSQL_AF_INET)
     264           0 :                         which &= 1;
     265           0 :                     break;
     266             : 
     267           0 :                 case RTGreaterEqualStrategyNumber:
     268             :                 case RTGreaterStrategyNumber:
     269           0 :                     if (ip_family(argument) == PGSQL_AF_INET6)
     270           0 :                         which &= (1 << 1);
     271           0 :                     break;
     272             : 
     273           0 :                 case RTNotEqualStrategyNumber:
     274           0 :                     break;
     275             : 
     276           0 :                 default:
     277             :                     /* all other ops can only match addrs of same family */
     278           0 :                     if (ip_family(argument) == PGSQL_AF_INET)
     279           0 :                         which &= 1;
     280             :                     else
     281           0 :                         which &= (1 << 1);
     282           0 :                     break;
     283             :             }
     284             :         }
     285             :     }
     286           0 :     else if (!in->allTheSame)
     287             :     {
     288             :         Assert(in->nNodes == 4);
     289             : 
     290             :         /* Identify which child nodes need to be visited */
     291           0 :         which = inet_spg_consistent_bitmap(DatumGetInetPP(in->prefixDatum),
     292             :                                            in->nkeys, in->scankeys, false);
     293             :     }
     294             :     else
     295             :     {
     296             :         /* Must visit all nodes; we assume there are less than 32 of 'em */
     297           0 :         which = ~0;
     298             :     }
     299             : 
     300           0 :     out->nNodes = 0;
     301             : 
     302           0 :     if (which)
     303             :     {
     304           0 :         out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     305             : 
     306           0 :         for (i = 0; i < in->nNodes; i++)
     307             :         {
     308           0 :             if (which & (1 << i))
     309             :             {
     310           0 :                 out->nodeNumbers[out->nNodes] = i;
     311           0 :                 out->nNodes++;
     312             :             }
     313             :         }
     314             :     }
     315             : 
     316           0 :     PG_RETURN_VOID();
     317             : }
     318             : 
     319             : /*
     320             :  * The SP-GiST query consistency check for leaf tuples
     321             :  */
     322             : Datum
     323        1224 : inet_spg_leaf_consistent(PG_FUNCTION_ARGS)
     324             : {
     325        1224 :     spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
     326        1224 :     spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
     327        1224 :     inet       *leaf = DatumGetInetPP(in->leafDatum);
     328             : 
     329             :     /* All tests are exact. */
     330        1224 :     out->recheck = false;
     331             : 
     332             :     /* Leaf is what it is... */
     333        1224 :     out->leafValue = InetPGetDatum(leaf);
     334             : 
     335             :     /* Use common code to apply the tests. */
     336        1224 :     PG_RETURN_BOOL(inet_spg_consistent_bitmap(leaf, in->nkeys, in->scankeys,
     337             :                                               true));
     338             : }
     339             : 
     340             : /*
     341             :  * Calculate node number (within a 4-node, single-family inner index tuple)
     342             :  *
     343             :  * The value must have the same family as the node's prefix, and
     344             :  * commonbits is the mask length of the prefix.  We use even or odd
     345             :  * nodes according to the next address bit after the commonbits,
     346             :  * and low or high nodes according to whether the value's mask length
     347             :  * is larger than commonbits.
     348             :  */
     349             : static int
     350           0 : inet_spg_node_number(const inet *val, int commonbits)
     351             : {
     352           0 :     int         nodeN = 0;
     353             : 
     354           0 :     if (commonbits < ip_maxbits(val) &&
     355           0 :         ip_addr(val)[commonbits / 8] & (1 << (7 - commonbits % 8)))
     356           0 :         nodeN |= 1;
     357           0 :     if (commonbits < ip_bits(val))
     358           0 :         nodeN |= 2;
     359             : 
     360           0 :     return nodeN;
     361             : }
     362             : 
     363             : /*
     364             :  * Calculate bitmap of node numbers that are consistent with the query
     365             :  *
     366             :  * This can be used either at a 4-way inner tuple, or at a leaf tuple.
     367             :  * In the latter case, we should return a boolean result (0 or 1)
     368             :  * not a bitmap.
     369             :  *
     370             :  * This definition is pretty odd, but the inner and leaf consistency checks
     371             :  * are mostly common and it seems best to keep them in one function.
     372             :  */
     373             : static int
     374        1224 : inet_spg_consistent_bitmap(const inet *prefix, int nkeys, ScanKey scankeys,
     375             :                            bool leaf)
     376             : {
     377             :     int         bitmap;
     378             :     int         commonbits,
     379             :                 i;
     380             : 
     381             :     /* Initialize result to allow visiting all children */
     382        1224 :     if (leaf)
     383        1224 :         bitmap = 1;
     384             :     else
     385           0 :         bitmap = 1 | (1 << 1) | (1 << 2) | (1 << 3);
     386             : 
     387        1224 :     commonbits = ip_bits(prefix);
     388             : 
     389        1656 :     for (i = 0; i < nkeys; i++)
     390             :     {
     391        1224 :         inet       *argument = DatumGetInetPP(scankeys[i].sk_argument);
     392        1224 :         StrategyNumber strategy = scankeys[i].sk_strategy;
     393             :         int         order;
     394             : 
     395             :         /*
     396             :          * Check 0: different families
     397             :          *
     398             :          * Matching families do not help any of the strategies.
     399             :          */
     400        1224 :         if (ip_family(argument) != ip_family(prefix))
     401             :         {
     402         216 :             switch (strategy)
     403             :             {
     404          36 :                 case RTLessStrategyNumber:
     405             :                 case RTLessEqualStrategyNumber:
     406          36 :                     if (ip_family(argument) < ip_family(prefix))
     407          36 :                         bitmap = 0;
     408          36 :                     break;
     409             : 
     410          36 :                 case RTGreaterEqualStrategyNumber:
     411             :                 case RTGreaterStrategyNumber:
     412          36 :                     if (ip_family(argument) > ip_family(prefix))
     413           0 :                         bitmap = 0;
     414          36 :                     break;
     415             : 
     416          18 :                 case RTNotEqualStrategyNumber:
     417          18 :                     break;
     418             : 
     419         126 :                 default:
     420             :                     /* For all other cases, we can be sure there is no match */
     421         126 :                     bitmap = 0;
     422         126 :                     break;
     423             :             }
     424             : 
     425         216 :             if (!bitmap)
     426         162 :                 break;
     427             : 
     428             :             /* Other checks make no sense with different families. */
     429          54 :             continue;
     430             :         }
     431             : 
     432             :         /*
     433             :          * Check 1: network bit count
     434             :          *
     435             :          * Network bit count (ip_bits) helps to check leaves for sub network
     436             :          * and sup network operators.  At non-leaf nodes, we know every child
     437             :          * value has greater ip_bits, so we can avoid descending in some cases
     438             :          * too.
     439             :          *
     440             :          * This check is less expensive than checking the address bits, so we
     441             :          * are doing this before, but it has to be done after for the basic
     442             :          * comparison strategies, because ip_bits only affect their results
     443             :          * when the common network bits are the same.
     444             :          */
     445        1008 :         switch (strategy)
     446             :         {
     447         168 :             case RTSubStrategyNumber:
     448         168 :                 if (commonbits <= ip_bits(argument))
     449         120 :                     bitmap &= (1 << 2) | (1 << 3);
     450         168 :                 break;
     451             : 
     452          84 :             case RTSubEqualStrategyNumber:
     453          84 :                 if (commonbits < ip_bits(argument))
     454          36 :                     bitmap &= (1 << 2) | (1 << 3);
     455          84 :                 break;
     456             : 
     457          84 :             case RTSuperStrategyNumber:
     458          84 :                 if (commonbits == ip_bits(argument) - 1)
     459           0 :                     bitmap &= 1 | (1 << 1);
     460          84 :                 else if (commonbits >= ip_bits(argument))
     461          48 :                     bitmap = 0;
     462          84 :                 break;
     463             : 
     464          84 :             case RTSuperEqualStrategyNumber:
     465          84 :                 if (commonbits == ip_bits(argument))
     466          24 :                     bitmap &= 1 | (1 << 1);
     467          60 :                 else if (commonbits > ip_bits(argument))
     468          24 :                     bitmap = 0;
     469          84 :                 break;
     470             : 
     471          84 :             case RTEqualStrategyNumber:
     472          84 :                 if (commonbits < ip_bits(argument))
     473          36 :                     bitmap &= (1 << 2) | (1 << 3);
     474          48 :                 else if (commonbits == ip_bits(argument))
     475          24 :                     bitmap &= 1 | (1 << 1);
     476             :                 else
     477          24 :                     bitmap = 0;
     478          84 :                 break;
     479             :         }
     480             : 
     481        1008 :         if (!bitmap)
     482         288 :             break;
     483             : 
     484             :         /*
     485             :          * Check 2: common network bits
     486             :          *
     487             :          * Compare available common prefix bits to the query, but not beyond
     488             :          * either the query's netmask or the minimum netmask among the
     489             :          * represented values.  If these bits don't match the query, we can
     490             :          * eliminate some cases.
     491             :          */
     492         720 :         order = bitncmp(ip_addr(prefix), ip_addr(argument),
     493         720 :                         Min(commonbits, ip_bits(argument)));
     494             : 
     495         720 :         if (order != 0)
     496             :         {
     497         396 :             switch (strategy)
     498             :             {
     499          96 :                 case RTLessStrategyNumber:
     500             :                 case RTLessEqualStrategyNumber:
     501          96 :                     if (order > 0)
     502           0 :                         bitmap = 0;
     503          96 :                     break;
     504             : 
     505          96 :                 case RTGreaterEqualStrategyNumber:
     506             :                 case RTGreaterStrategyNumber:
     507          96 :                     if (order < 0)
     508          96 :                         bitmap = 0;
     509          96 :                     break;
     510             : 
     511          48 :                 case RTNotEqualStrategyNumber:
     512          48 :                     break;
     513             : 
     514         156 :                 default:
     515             :                     /* For all other cases, we can be sure there is no match */
     516         156 :                     bitmap = 0;
     517         156 :                     break;
     518             :             }
     519             : 
     520         396 :             if (!bitmap)
     521         252 :                 break;
     522             : 
     523             :             /*
     524             :              * Remaining checks make no sense when common bits don't match.
     525             :              */
     526         144 :             continue;
     527             :         }
     528             : 
     529             :         /*
     530             :          * Check 3: next network bit
     531             :          *
     532             :          * We can filter out branch 2 or 3 using the next network bit of the
     533             :          * argument, if it is available.
     534             :          *
     535             :          * This check matters for the performance of the search. The results
     536             :          * would be correct without it.
     537             :          */
     538         324 :         if (bitmap & ((1 << 2) | (1 << 3)) &&
     539           0 :             commonbits < ip_bits(argument))
     540             :         {
     541             :             int         nextbit;
     542             : 
     543           0 :             nextbit = ip_addr(argument)[commonbits / 8] &
     544           0 :                 (1 << (7 - commonbits % 8));
     545             : 
     546           0 :             switch (strategy)
     547             :             {
     548           0 :                 case RTLessStrategyNumber:
     549             :                 case RTLessEqualStrategyNumber:
     550           0 :                     if (!nextbit)
     551           0 :                         bitmap &= 1 | (1 << 1) | (1 << 2);
     552           0 :                     break;
     553             : 
     554           0 :                 case RTGreaterEqualStrategyNumber:
     555             :                 case RTGreaterStrategyNumber:
     556           0 :                     if (nextbit)
     557           0 :                         bitmap &= 1 | (1 << 1) | (1 << 3);
     558           0 :                     break;
     559             : 
     560           0 :                 case RTNotEqualStrategyNumber:
     561           0 :                     break;
     562             : 
     563           0 :                 default:
     564           0 :                     if (!nextbit)
     565           0 :                         bitmap &= 1 | (1 << 1) | (1 << 2);
     566             :                     else
     567           0 :                         bitmap &= 1 | (1 << 1) | (1 << 3);
     568           0 :                     break;
     569             :             }
     570             : 
     571           0 :             if (!bitmap)
     572           0 :                 break;
     573             :         }
     574             : 
     575             :         /*
     576             :          * Remaining checks are only for the basic comparison strategies. This
     577             :          * test relies on the strategy number ordering defined in stratnum.h.
     578             :          */
     579         324 :         if (strategy < RTEqualStrategyNumber ||
     580             :             strategy > RTGreaterEqualStrategyNumber)
     581         126 :             continue;
     582             : 
     583             :         /*
     584             :          * Check 4: network bit count
     585             :          *
     586             :          * At this point, we know that the common network bits of the prefix
     587             :          * and the argument are the same, so we can go forward and check the
     588             :          * ip_bits.
     589             :          */
     590         198 :         switch (strategy)
     591             :         {
     592          72 :             case RTLessStrategyNumber:
     593             :             case RTLessEqualStrategyNumber:
     594          72 :                 if (commonbits == ip_bits(argument))
     595          36 :                     bitmap &= 1 | (1 << 1);
     596          36 :                 else if (commonbits > ip_bits(argument))
     597          36 :                     bitmap = 0;
     598          72 :                 break;
     599             : 
     600          72 :             case RTGreaterEqualStrategyNumber:
     601             :             case RTGreaterStrategyNumber:
     602          72 :                 if (commonbits < ip_bits(argument))
     603           0 :                     bitmap &= (1 << 2) | (1 << 3);
     604          72 :                 break;
     605             :         }
     606             : 
     607         198 :         if (!bitmap)
     608          36 :             break;
     609             : 
     610             :         /* Remaining checks don't make sense with different ip_bits. */
     611         162 :         if (commonbits != ip_bits(argument))
     612          54 :             continue;
     613             : 
     614             :         /*
     615             :          * Check 5: next host bit
     616             :          *
     617             :          * We can filter out branch 0 or 1 using the next host bit of the
     618             :          * argument, if it is available.
     619             :          *
     620             :          * This check matters for the performance of the search. The results
     621             :          * would be correct without it.  There is no point in running it for
     622             :          * leafs as we have to check the whole address on the next step.
     623             :          */
     624         108 :         if (!leaf && bitmap & (1 | (1 << 1)) &&
     625           0 :             commonbits < ip_maxbits(argument))
     626             :         {
     627             :             int         nextbit;
     628             : 
     629           0 :             nextbit = ip_addr(argument)[commonbits / 8] &
     630           0 :                 (1 << (7 - commonbits % 8));
     631             : 
     632           0 :             switch (strategy)
     633             :             {
     634           0 :                 case RTLessStrategyNumber:
     635             :                 case RTLessEqualStrategyNumber:
     636           0 :                     if (!nextbit)
     637           0 :                         bitmap &= 1 | (1 << 2) | (1 << 3);
     638           0 :                     break;
     639             : 
     640           0 :                 case RTGreaterEqualStrategyNumber:
     641             :                 case RTGreaterStrategyNumber:
     642           0 :                     if (nextbit)
     643           0 :                         bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
     644           0 :                     break;
     645             : 
     646           0 :                 case RTNotEqualStrategyNumber:
     647           0 :                     break;
     648             : 
     649           0 :                 default:
     650           0 :                     if (!nextbit)
     651           0 :                         bitmap &= 1 | (1 << 2) | (1 << 3);
     652             :                     else
     653           0 :                         bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
     654           0 :                     break;
     655             :             }
     656             : 
     657           0 :             if (!bitmap)
     658           0 :                 break;
     659             :         }
     660             : 
     661             :         /*
     662             :          * Check 6: whole address
     663             :          *
     664             :          * This is the last check for correctness of the basic comparison
     665             :          * strategies.  It's only appropriate at leaf entries.
     666             :          */
     667         108 :         if (leaf)
     668             :         {
     669             :             /* Redo ordering comparison using all address bits */
     670         108 :             order = bitncmp(ip_addr(prefix), ip_addr(argument),
     671         108 :                             ip_maxbits(prefix));
     672             : 
     673         108 :             switch (strategy)
     674             :             {
     675          18 :                 case RTLessStrategyNumber:
     676          18 :                     if (order >= 0)
     677          18 :                         bitmap = 0;
     678          18 :                     break;
     679             : 
     680          18 :                 case RTLessEqualStrategyNumber:
     681          18 :                     if (order > 0)
     682          12 :                         bitmap = 0;
     683          18 :                     break;
     684             : 
     685          18 :                 case RTEqualStrategyNumber:
     686          18 :                     if (order != 0)
     687          12 :                         bitmap = 0;
     688          18 :                     break;
     689             : 
     690          18 :                 case RTGreaterEqualStrategyNumber:
     691          18 :                     if (order < 0)
     692           0 :                         bitmap = 0;
     693          18 :                     break;
     694             : 
     695          18 :                 case RTGreaterStrategyNumber:
     696          18 :                     if (order <= 0)
     697           6 :                         bitmap = 0;
     698          18 :                     break;
     699             : 
     700          18 :                 case RTNotEqualStrategyNumber:
     701          18 :                     if (order == 0)
     702           6 :                         bitmap = 0;
     703          18 :                     break;
     704             :             }
     705             : 
     706         108 :             if (!bitmap)
     707          54 :                 break;
     708             :         }
     709             :     }
     710             : 
     711        1224 :     return bitmap;
     712             : }

Generated by: LCOV version 1.14