network_spgist.c File Reference

#include "postgres.h"
#include <sys/socket.h>
#include "access/spgist.h"
#include "catalog/pg_type.h"
#include "utils/fmgrprotos.h"
#include "utils/inet.h"
#include "varatt.h"

Include dependency graph for network_spgist.c:

Go to the source code of this file.

Functions
static int	inet_spg_node_number (const inet *val, int commonbits)
static int	inet_spg_consistent_bitmap (const inet *prefix, int nkeys, ScanKey scankeys, bool leaf)
Datum	inet_spg_config (PG_FUNCTION_ARGS)
Datum	inet_spg_choose (PG_FUNCTION_ARGS)
Datum	inet_spg_picksplit (PG_FUNCTION_ARGS)
Datum	inet_spg_inner_consistent (PG_FUNCTION_ARGS)
Datum	inet_spg_leaf_consistent (PG_FUNCTION_ARGS)

Function Documentation

inet_spg_choose()

Datum inet_spg_choose

(

PG_FUNCTION_ARGS

)

Definition at line 68 of file network_spgist.c.

{
    spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
    spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
    inet       *val = DatumGetInetPP(in->datum),
               *prefix;
    int         commonbits;
 
    /*
     * If we're looking at a tuple that splits by address family, choose the
     * appropriate subnode.
     */
    if (!in->hasPrefix)
    {
        /* allTheSame isn't possible for such a tuple */
        Assert(!in->allTheSame);
        Assert(in->nNodes == 2);
 
        out->resultType = spgMatchNode;
        out->result.matchNode.nodeN = (ip_family(val) == PGSQL_AF_INET) ? 0 : 1;
        out->result.matchNode.restDatum = InetPGetDatum(val);
 
        PG_RETURN_VOID();
    }
 
    /* Else it must split by prefix */
    Assert(in->nNodes == 4 || in->allTheSame);
 
    prefix = DatumGetInetPP(in->prefixDatum);
    commonbits = ip_bits(prefix);
 
    /*
     * We cannot put addresses from different families under the same inner
     * node, so we have to split if the new value's family is different.
     */
    if (ip_family(val) != ip_family(prefix))
    {
        /* Set up 2-node tuple */
        out->resultType = spgSplitTuple;
        out->result.splitTuple.prefixHasPrefix = false;
        out->result.splitTuple.prefixNNodes = 2;
        out->result.splitTuple.prefixNodeLabels = NULL;
 
        /* Identify which node the existing data goes into */
        out->result.splitTuple.childNodeN =
            (ip_family(prefix) == PGSQL_AF_INET) ? 0 : 1;
 
        out->result.splitTuple.postfixHasPrefix = true;
        out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
 
        PG_RETURN_VOID();
    }
 
    /*
     * If the new value does not match the existing prefix, we have to split.
     */
    if (ip_bits(val) < commonbits ||
        bitncmp(ip_addr(prefix), ip_addr(val), commonbits) != 0)
    {
        /* Determine new prefix length for the split tuple */
        commonbits = bitncommon(ip_addr(prefix), ip_addr(val),
                                Min(ip_bits(val), commonbits));
 
        /* Set up 4-node tuple */
        out->resultType = spgSplitTuple;
        out->result.splitTuple.prefixHasPrefix = true;
        out->result.splitTuple.prefixPrefixDatum =
            InetPGetDatum(cidr_set_masklen_internal(val, commonbits));
        out->result.splitTuple.prefixNNodes = 4;
        out->result.splitTuple.prefixNodeLabels = NULL;
 
        /* Identify which node the existing data goes into */
        out->result.splitTuple.childNodeN =
            inet_spg_node_number(prefix, commonbits);
 
        out->result.splitTuple.postfixHasPrefix = true;
        out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
 
        PG_RETURN_VOID();
    }
 
    /*
     * All OK, choose the node to descend into.  (If this tuple is marked
     * allTheSame, the core code will ignore our choice of nodeN; but we need
     * not account for that case explicitly here.)
     */
    out->resultType = spgMatchNode;
    out->result.matchNode.nodeN = inet_spg_node_number(val, commonbits);
    out->result.matchNode.restDatum = InetPGetDatum(val);
 
    PG_RETURN_VOID();
}

References spgChooseIn::allTheSame, Assert, bitncmp(), bitncommon(), cidr_set_masklen_internal(), spgChooseIn::datum, DatumGetInetPP(), spgChooseIn::hasPrefix, inet_spg_node_number(), InetPGetDatum(), ip_addr, ip_bits, ip_family, spgChooseOut::matchNode, Min, spgChooseIn::nNodes, PG_GETARG_POINTER, PG_RETURN_VOID, PGSQL_AF_INET, spgChooseIn::prefixDatum, spgChooseOut::result, spgChooseOut::resultType, spgMatchNode, spgSplitTuple, spgChooseOut::splitTuple, and val.

inet_spg_config()

Datum inet_spg_config

(

PG_FUNCTION_ARGS

)

Definition at line 51 of file network_spgist.c.

{
    /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
    spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
 
    cfg->prefixType = CIDROID;
    cfg->labelType = VOIDOID;
    cfg->canReturnData = true;
    cfg->longValuesOK = false;
 
    PG_RETURN_VOID();
}

References spgConfigOut::canReturnData, spgConfigOut::labelType, spgConfigOut::longValuesOK, PG_GETARG_POINTER, PG_RETURN_VOID, and spgConfigOut::prefixType.

inet_spg_consistent_bitmap()

static int inet_spg_consistent_bitmap ( const inet *  prefix, int  nkeys, ScanKey  scankeys, bool  leaf  )

static

Definition at line 374 of file network_spgist.c.

{
    int         bitmap;
    int         commonbits,
                i;
 
    /* Initialize result to allow visiting all children */
    if (leaf)
        bitmap = 1;
    else
        bitmap = 1 | (1 << 1) | (1 << 2) | (1 << 3);
 
    commonbits = ip_bits(prefix);
 
    for (i = 0; i < nkeys; i++)
    {
        inet       *argument = DatumGetInetPP(scankeys[i].sk_argument);
        StrategyNumber strategy = scankeys[i].sk_strategy;
        int         order;
 
        /*
         * Check 0: different families
         *
         * Matching families do not help any of the strategies.
         */
        if (ip_family(argument) != ip_family(prefix))
        {
            switch (strategy)
            {
                case RTLessStrategyNumber:
                case RTLessEqualStrategyNumber:
                    if (ip_family(argument) < ip_family(prefix))
                        bitmap = 0;
                    break;
 
                case RTGreaterEqualStrategyNumber:
                case RTGreaterStrategyNumber:
                    if (ip_family(argument) > ip_family(prefix))
                        bitmap = 0;
                    break;
 
                case RTNotEqualStrategyNumber:
                    break;
 
                default:
                    /* For all other cases, we can be sure there is no match */
                    bitmap = 0;
                    break;
            }
 
            if (!bitmap)
                break;
 
            /* Other checks make no sense with different families. */
            continue;
        }
 
        /*
         * Check 1: network bit count
         *
         * Network bit count (ip_bits) helps to check leaves for sub network
         * and sup network operators.  At non-leaf nodes, we know every child
         * value has greater ip_bits, so we can avoid descending in some cases
         * too.
         *
         * This check is less expensive than checking the address bits, so we
         * are doing this before, but it has to be done after for the basic
         * comparison strategies, because ip_bits only affect their results
         * when the common network bits are the same.
         */
        switch (strategy)
        {
            case RTSubStrategyNumber:
                if (commonbits <= ip_bits(argument))
                    bitmap &= (1 << 2) | (1 << 3);
                break;
 
            case RTSubEqualStrategyNumber:
                if (commonbits < ip_bits(argument))
                    bitmap &= (1 << 2) | (1 << 3);
                break;
 
            case RTSuperStrategyNumber:
                if (commonbits == ip_bits(argument) - 1)
                    bitmap &= 1 | (1 << 1);
                else if (commonbits >= ip_bits(argument))
                    bitmap = 0;
                break;
 
            case RTSuperEqualStrategyNumber:
                if (commonbits == ip_bits(argument))
                    bitmap &= 1 | (1 << 1);
                else if (commonbits > ip_bits(argument))
                    bitmap = 0;
                break;
 
            case RTEqualStrategyNumber:
                if (commonbits < ip_bits(argument))
                    bitmap &= (1 << 2) | (1 << 3);
                else if (commonbits == ip_bits(argument))
                    bitmap &= 1 | (1 << 1);
                else
                    bitmap = 0;
                break;
        }
 
        if (!bitmap)
            break;
 
        /*
         * Check 2: common network bits
         *
         * Compare available common prefix bits to the query, but not beyond
         * either the query's netmask or the minimum netmask among the
         * represented values.  If these bits don't match the query, we can
         * eliminate some cases.
         */
        order = bitncmp(ip_addr(prefix), ip_addr(argument),
                        Min(commonbits, ip_bits(argument)));
 
        if (order != 0)
        {
            switch (strategy)
            {
                case RTLessStrategyNumber:
                case RTLessEqualStrategyNumber:
                    if (order > 0)
                        bitmap = 0;
                    break;
 
                case RTGreaterEqualStrategyNumber:
                case RTGreaterStrategyNumber:
                    if (order < 0)
                        bitmap = 0;
                    break;
 
                case RTNotEqualStrategyNumber:
                    break;
 
                default:
                    /* For all other cases, we can be sure there is no match */
                    bitmap = 0;
                    break;
            }
 
            if (!bitmap)
                break;
 
            /*
             * Remaining checks make no sense when common bits don't match.
             */
            continue;
        }
 
        /*
         * Check 3: next network bit
         *
         * We can filter out branch 2 or 3 using the next network bit of the
         * argument, if it is available.
         *
         * This check matters for the performance of the search. The results
         * would be correct without it.
         */
        if (bitmap & ((1 << 2) | (1 << 3)) &&
            commonbits < ip_bits(argument))
        {
            int         nextbit;
 
            nextbit = ip_addr(argument)[commonbits / 8] &
                (1 << (7 - commonbits % 8));
 
            switch (strategy)
            {
                case RTLessStrategyNumber:
                case RTLessEqualStrategyNumber:
                    if (!nextbit)
                        bitmap &= 1 | (1 << 1) | (1 << 2);
                    break;
 
                case RTGreaterEqualStrategyNumber:
                case RTGreaterStrategyNumber:
                    if (nextbit)
                        bitmap &= 1 | (1 << 1) | (1 << 3);
                    break;
 
                case RTNotEqualStrategyNumber:
                    break;
 
                default:
                    if (!nextbit)
                        bitmap &= 1 | (1 << 1) | (1 << 2);
                    else
                        bitmap &= 1 | (1 << 1) | (1 << 3);
                    break;
            }
 
            if (!bitmap)
                break;
        }
 
        /*
         * Remaining checks are only for the basic comparison strategies. This
         * test relies on the strategy number ordering defined in stratnum.h.
         */
        if (strategy < RTEqualStrategyNumber ||
            strategy > RTGreaterEqualStrategyNumber)
            continue;
 
        /*
         * Check 4: network bit count
         *
         * At this point, we know that the common network bits of the prefix
         * and the argument are the same, so we can go forward and check the
         * ip_bits.
         */
        switch (strategy)
        {
            case RTLessStrategyNumber:
            case RTLessEqualStrategyNumber:
                if (commonbits == ip_bits(argument))
                    bitmap &= 1 | (1 << 1);
                else if (commonbits > ip_bits(argument))
                    bitmap = 0;
                break;
 
            case RTGreaterEqualStrategyNumber:
            case RTGreaterStrategyNumber:
                if (commonbits < ip_bits(argument))
                    bitmap &= (1 << 2) | (1 << 3);
                break;
        }
 
        if (!bitmap)
            break;
 
        /* Remaining checks don't make sense with different ip_bits. */
        if (commonbits != ip_bits(argument))
            continue;
 
        /*
         * Check 5: next host bit
         *
         * We can filter out branch 0 or 1 using the next host bit of the
         * argument, if it is available.
         *
         * This check matters for the performance of the search. The results
         * would be correct without it.  There is no point in running it for
         * leafs as we have to check the whole address on the next step.
         */
        if (!leaf && bitmap & (1 | (1 << 1)) &&
            commonbits < ip_maxbits(argument))
        {
            int         nextbit;
 
            nextbit = ip_addr(argument)[commonbits / 8] &
                (1 << (7 - commonbits % 8));
 
            switch (strategy)
            {
                case RTLessStrategyNumber:
                case RTLessEqualStrategyNumber:
                    if (!nextbit)
                        bitmap &= 1 | (1 << 2) | (1 << 3);
                    break;
 
                case RTGreaterEqualStrategyNumber:
                case RTGreaterStrategyNumber:
                    if (nextbit)
                        bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
                    break;
 
                case RTNotEqualStrategyNumber:
                    break;
 
                default:
                    if (!nextbit)
                        bitmap &= 1 | (1 << 2) | (1 << 3);
                    else
                        bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
                    break;
            }
 
            if (!bitmap)
                break;
        }
 
        /*
         * Check 6: whole address
         *
         * This is the last check for correctness of the basic comparison
         * strategies.  It's only appropriate at leaf entries.
         */
        if (leaf)
        {
            /* Redo ordering comparison using all address bits */
            order = bitncmp(ip_addr(prefix), ip_addr(argument),
                            ip_maxbits(prefix));
 
            switch (strategy)
            {
                case RTLessStrategyNumber:
                    if (order >= 0)
                        bitmap = 0;
                    break;
 
                case RTLessEqualStrategyNumber:
                    if (order > 0)
                        bitmap = 0;
                    break;
 
                case RTEqualStrategyNumber:
                    if (order != 0)
                        bitmap = 0;
                    break;
 
                case RTGreaterEqualStrategyNumber:
                    if (order < 0)
                        bitmap = 0;
                    break;
 
                case RTGreaterStrategyNumber:
                    if (order <= 0)
                        bitmap = 0;
                    break;
 
                case RTNotEqualStrategyNumber:
                    if (order == 0)
                        bitmap = 0;
                    break;
            }
 
            if (!bitmap)
                break;
        }
    }
 
    return bitmap;
}

References bitncmp(), DatumGetInetPP(), i, ip_addr, ip_bits, ip_family, ip_maxbits, Min, RTEqualStrategyNumber, RTGreaterEqualStrategyNumber, RTGreaterStrategyNumber, RTLessEqualStrategyNumber, RTLessStrategyNumber, RTNotEqualStrategyNumber, RTSubEqualStrategyNumber, RTSubStrategyNumber, RTSuperEqualStrategyNumber, RTSuperStrategyNumber, and ScanKeyData::sk_strategy.

Referenced by inet_spg_inner_consistent(), and inet_spg_leaf_consistent().

inet_spg_inner_consistent()

Datum inet_spg_inner_consistent

(

PG_FUNCTION_ARGS

)

Definition at line 239 of file network_spgist.c.

{
    spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
    spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
    int         i;
    int         which;
 
    if (!in->hasPrefix)
    {
        Assert(!in->allTheSame);
        Assert(in->nNodes == 2);
 
        /* Identify which child nodes need to be visited */
        which = 1 | (1 << 1);
 
        for (i = 0; i < in->nkeys; i++)
        {
            StrategyNumber strategy = in->scankeys[i].sk_strategy;
            inet       *argument = DatumGetInetPP(in->scankeys[i].sk_argument);
 
            switch (strategy)
            {
                case RTLessStrategyNumber:
                case RTLessEqualStrategyNumber:
                    if (ip_family(argument) == PGSQL_AF_INET)
                        which &= 1;
                    break;
 
                case RTGreaterEqualStrategyNumber:
                case RTGreaterStrategyNumber:
                    if (ip_family(argument) == PGSQL_AF_INET6)
                        which &= (1 << 1);
                    break;
 
                case RTNotEqualStrategyNumber:
                    break;
 
                default:
                    /* all other ops can only match addrs of same family */
                    if (ip_family(argument) == PGSQL_AF_INET)
                        which &= 1;
                    else
                        which &= (1 << 1);
                    break;
            }
        }
    }
    else if (!in->allTheSame)
    {
        Assert(in->nNodes == 4);
 
        /* Identify which child nodes need to be visited */
        which = inet_spg_consistent_bitmap(DatumGetInetPP(in->prefixDatum),
                                           in->nkeys, in->scankeys, false);
    }
    else
    {
        /* Must visit all nodes; we assume there are less than 32 of 'em */
        which = ~0;
    }
 
    out->nNodes = 0;
 
    if (which)
    {
        out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
 
        for (i = 0; i < in->nNodes; i++)
        {
            if (which & (1 << i))
            {
                out->nodeNumbers[out->nNodes] = i;
                out->nNodes++;
            }
        }
    }
 
    PG_RETURN_VOID();
}

References spgInnerConsistentIn::allTheSame, Assert, DatumGetInetPP(), spgInnerConsistentIn::hasPrefix, i, inet_spg_consistent_bitmap(), ip_family, spgInnerConsistentIn::nkeys, spgInnerConsistentIn::nNodes, spgInnerConsistentOut::nNodes, spgInnerConsistentOut::nodeNumbers, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, PGSQL_AF_INET, PGSQL_AF_INET6, spgInnerConsistentIn::prefixDatum, RTGreaterEqualStrategyNumber, RTGreaterStrategyNumber, RTLessEqualStrategyNumber, RTLessStrategyNumber, RTNotEqualStrategyNumber, spgInnerConsistentIn::scankeys, ScanKeyData::sk_argument, and ScanKeyData::sk_strategy.

inet_spg_leaf_consistent()

Datum inet_spg_leaf_consistent

(

PG_FUNCTION_ARGS

)

Definition at line 323 of file network_spgist.c.

{
    spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
    spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
    inet       *leaf = DatumGetInetPP(in->leafDatum);
 
    /* All tests are exact. */
    out->recheck = false;
 
    /* Leaf is what it is... */
    out->leafValue = InetPGetDatum(leaf);
 
    /* Use common code to apply the tests. */
    PG_RETURN_BOOL(inet_spg_consistent_bitmap(leaf, in->nkeys, in->scankeys,
                                              true));
}

References DatumGetInetPP(), inet_spg_consistent_bitmap(), InetPGetDatum(), spgLeafConsistentIn::leafDatum, spgLeafConsistentOut::leafValue, spgLeafConsistentIn::nkeys, PG_GETARG_POINTER, PG_RETURN_BOOL, spgLeafConsistentOut::recheck, and spgLeafConsistentIn::scankeys.

inet_spg_node_number()

static int inet_spg_node_number ( const inet *  val, int  commonbits  )

static

Definition at line 350 of file network_spgist.c.

{
    int         nodeN = 0;
 
    if (commonbits < ip_maxbits(val) &&
        ip_addr(val)[commonbits / 8] & (1 << (7 - commonbits % 8)))
        nodeN |= 1;
    if (commonbits < ip_bits(val))
        nodeN |= 2;
 
    return nodeN;
}

References ip_addr, ip_bits, ip_maxbits, and val.

Referenced by inet_spg_choose(), and inet_spg_picksplit().

inet_spg_picksplit()

Datum inet_spg_picksplit

(

PG_FUNCTION_ARGS

)

Definition at line 165 of file network_spgist.c.

{
    spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
    spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
    inet       *prefix,
               *tmp;
    int         i,
                commonbits;
    bool        differentFamilies = false;
 
    /* Initialize the prefix with the first item */
    prefix = DatumGetInetPP(in->datums[0]);
    commonbits = ip_bits(prefix);
 
    /* Examine remaining items to discover minimum common prefix length */
    for (i = 1; i < in->nTuples; i++)
    {
        tmp = DatumGetInetPP(in->datums[i]);
 
        if (ip_family(tmp) != ip_family(prefix))
        {
            differentFamilies = true;
            break;
        }
 
        if (ip_bits(tmp) < commonbits)
            commonbits = ip_bits(tmp);
        commonbits = bitncommon(ip_addr(prefix), ip_addr(tmp), commonbits);
        if (commonbits == 0)
            break;
    }
 
    /* Don't need labels; allocate output arrays */
    out->nodeLabels = NULL;
    out->mapTuplesToNodes = (int *) palloc(sizeof(int) * in->nTuples);
    out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * in->nTuples);
 
    if (differentFamilies)
    {
        /* Set up 2-node tuple */
        out->hasPrefix = false;
        out->nNodes = 2;
 
        for (i = 0; i < in->nTuples; i++)
        {
            tmp = DatumGetInetPP(in->datums[i]);
            out->mapTuplesToNodes[i] =
                (ip_family(tmp) == PGSQL_AF_INET) ? 0 : 1;
            out->leafTupleDatums[i] = InetPGetDatum(tmp);
        }
    }
    else
    {
        /* Set up 4-node tuple */
        out->hasPrefix = true;
        out->prefixDatum =
            InetPGetDatum(cidr_set_masklen_internal(prefix, commonbits));
        out->nNodes = 4;
 
        for (i = 0; i < in->nTuples; i++)
        {
            tmp = DatumGetInetPP(in->datums[i]);
            out->mapTuplesToNodes[i] = inet_spg_node_number(tmp, commonbits);
            out->leafTupleDatums[i] = InetPGetDatum(tmp);
        }
    }
 
    PG_RETURN_VOID();
}

References bitncommon(), cidr_set_masklen_internal(), DatumGetInetPP(), spgPickSplitIn::datums, spgPickSplitOut::hasPrefix, i, inet_spg_node_number(), InetPGetDatum(), ip_addr, ip_bits, ip_family, spgPickSplitOut::leafTupleDatums, spgPickSplitOut::mapTuplesToNodes, spgPickSplitOut::nNodes, spgPickSplitOut::nodeLabels, spgPickSplitIn::nTuples, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, PGSQL_AF_INET, and spgPickSplitOut::prefixDatum.