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

Generated by: LCOV version 1.13