node.c

代码在ti的c67系列单片机上实现了完整的TCPIP协议栈

                pn->pUp       = pnBranch;
                pnLeaf->pUp   = pnBranch;

                // Make old node's parent branch to our new branch node
                if( pnBranch->pUp->pRight == pn )
                {
                    // Old leaf node was on the right
                    pnBranch->pUp->pRight = pnBranch;
                }
                else
                {
                    // Old leaf node was on the left
                    pnBranch->pUp->pLeft = pnBranch;
                }

                // Make new branch node brach to our children
                if( pnBranch->dwTestMask & dwMaskedAddr )
                {
                    // New leaf node is on the right
                    pnBranch->pRight = pnLeaf;
                    pnBranch->pLeft  = pn;
                }
                else
                {
                    // New leaf node is on the left
                    pnBranch->pLeft  = pnLeaf;
                    pnBranch->pRight = pn;
                }

                // Init the Leaf Node
                pnLeaf->dwLastIPAddr  = dwMaskedAddr;
                pnLeaf->dwLastIPMask  = dwIPMask;
                pnLeaf->LastMaskBits = wMaskBits;

                // Put return value in pn
                pn = pnLeaf;

                // Update new brach with its LEFT node
                NodeUpdatePL( pnBranch->pLeft );

                goto NODE_ADD_DONE;
            }
        }
    }

NODE_ADD_DONE:
    return( pn );
}

//--------------------------------------------------------------------
// NodeFind()
//
// Called to find the node with the closest IP match.
//
// Increments Reference Count of the Node it returns.
// Decrements Reference Count of any Continue Node supplied
//--------------------------------------------------------------------
HANDLE NodeFind( IPN dwIPAddr, HANDLE hNodeContinue )
{
    NODE  *pn = pRoot;
    NODE  *pnContinue = (NODE *)hNodeContinue;
    UINT32 dwMaskedAddr;

#ifdef _STRONG_CHECKING
    // Validate hNodeContinue
    if( hNodeContinue && ( (pnContinue->Type != HTYPE_NODE)
                           || !(pnContinue->Flags & NODE_FLG_LEAF)) )
    {
        DbgPrintf(DBG_ERROR,"NodeFind: HTYPE %04x : Continue an non-Leaf",pnContinue->Type);
        return(0);
    }
#endif

    // Start out with the most specific IP address, but be prepared to
    // apply as when needed.
    dwMaskedAddr = dwIPAddr;

    // We have the ability to continue off a previous search. If we
    // are continuing, we will NEVER match on the first leaf.
    // We also start at the continue point
    if( pnContinue )
        pn = pnContinue;

    // Start search. Note this algorithm is unconcerned with the
    // "no match" case since it is impossible not to match on (at least)
    // the left end node.
    for(;;)
    {
        // If we are not a leaf, then get the next node
        if( !(pn->Flags & NODE_FLG_LEAF) )
        {
            if( (dwMaskedAddr & pn->dwTestMask) == 0 )
                pn = pn->pLeft;
            else
                pn = pn->pRight;
        }
        else
        {
            // If we got here, we got to a leaf. Now we'll have one
            // of two cases. If we match this leaf, we're done. Otherwise
            // we have to backtrack.
            if( (pn->dwLastIPAddr == (dwMaskedAddr & pn->dwLastIPMask))
                && pn != pnContinue )
            {
                // This leaf is the match!

                // Reference it
                NodeRef( pn );

                break;
            }
            else
            {
                // Leaf it not a match. We must backtrack. We continue
                // to backtrack while either of the following is true:
                // - We (node just checked) were a left branch
                // - The PASSLEFT flag is not set on our parent
                NODE* pnBranch;

                pnBranch = pn->pUp;
                while( (pnBranch->pLeft == pn) ||
                       !(pnBranch->Flags & NODE_FLG_PASSLEFT) )
                {
                    pn = pnBranch;
                    pnBranch = pn->pUp;
                }

                // Once we get here (and we always will) we know we
                // were a right branch AND the PASSLEFT flag is set
                // on pnBranch. Therefore, we KNOW we're going left...

                // First apply the mask
                dwMaskedAddr &= pnBranch->dwLastIPMask;

                // Then go left
                pn = pnBranch->pLeft;
            }
        }
    }

    // If we were continuing, we done with the continue node.
    if( pnContinue )
        NodeDeRef(pnContinue);

    return( pn );
}

//--------------------------------------------------------------------
// NodeDeRef()
//
// Called to POTENTIALLY remove a new leaf node, but will at least dec
// the RefCount.
//--------------------------------------------------------------------
void NodeDeRef( HANDLE h )
{
    NODE *pn = (NODE *)h;

#ifdef _STRONG_CHECKING
    // We MUST start with a leaf node!
    if( (pn->Type != HTYPE_NODE) || !(pn->Flags & NODE_FLG_LEAF) )
    {
        DbgPrintf(DBG_ERROR,"NodeDeRef: HTYPE %04x : Not Leaf",pn->Type);
        return;
    }
#endif

    // Standard DeRef
    if( pn->RefCount == 65535 )
        return;
    if( pn->RefCount > 1 )
    {
        pn->RefCount--;                // Deref one count
        return;
    }

    // We only remove non-endpoint leafs
    else if( !(pn->Flags & (NODE_FLG_ENDL|NODE_FLG_ENDR)) )
    {
        // Here we must remove the node, and collapse one branch.
        NODE *pnUp;
        NODE *pnUpUp;
        NODE *pnSurvivor;

        pnUp   = pn->pUp;
        pnUpUp = pnUp->pUp;

        // Get a pointer to the surviving node
        if( pnUp->pLeft == pn )
        {
            // Leaf was left, so the survivor is right
            pnSurvivor = pnUp->pRight;
        }
        else
        {
            // Leaf was right, so the survivor is left
            pnSurvivor = pnUp->pLeft;
        }

        // Update survivor's parent
        pnSurvivor->pUp = pnUpUp;

        // Update removed branch's parent to point to surviving node
        if( pnUpUp->pRight == pnUp )
        {
            // Branch was right, so the survivor is now on right
            pnUpUp->pRight = pnSurvivor;
        }
        else
        {
            // Branch was left, so the survivor is now on left
            pnUpUp->pLeft = pnSurvivor;

            // This case is slightly more complicated, since
            // we need to update the pass left flag for (at least)
            // the UpUp node.
            NodeUpdatePL( pnSurvivor );
        }

        // Now we can remove the nodes
        NodeFree( pn );
        NodeFree( pnUp );
    }
}

//--------------------------------------------------------------------
// NodeSetRt()
//
// Set NODE Route list head
//--------------------------------------------------------------------
void NodeSetRt( HANDLE h, HANDLE hRt )
{
    NODE *pn = (NODE *)h;

#ifdef _STRONG_CHECKING
    // We MUST start with a leaf node!
    if( (pn->Type != HTYPE_NODE) || !(pn->Flags & NODE_FLG_LEAF) )
    {
        DbgPrintf(DBG_ERROR,"NodeSetRt: HTYPE %04x : Not Leaf",pn->Type);
        return;
    }
#endif

    // Set new route head
    pn->hRt = hRt;
}

//--------------------------------------------------------------------
// NodeGetRt()
//
// Get Route at head of list
//--------------------------------------------------------------------
HANDLE NodeGetRt( HANDLE h )
{
    NODE *pn = (NODE *)h;

#ifdef _STRONG_CHECKING
    // We MUST start with a leaf node!
    if( (pn->Type != HTYPE_NODE) || !(pn->Flags & NODE_FLG_LEAF) )
    {
        DbgPrintf(DBG_ERROR,"NodeGetRt: HTYPE %04x : Not Leaf",pn->Type);
        return(0);
    }
#endif

    // Return the route handle
    return( pn->hRt );
}

//--------------------------------------------------------------------
// NodeWalk()
//
// This function walks the node tree. It is used by RtWalk.
// CALLED IN CRIT SECTION ONLY!
//--------------------------------------------------------------------
HANDLE NodeWalk( HANDLE h )
{
    NODE *pn = (NODE *)h;
    NODE *pnUse = 0;

    if( !pn )
        pnUse = pRoot;
    else
    {
        // Here we're continuing an old walk. If we were the left
        // node, try the right, else go up
        NODE *pnParent = pn->pUp;

        while( pnParent && !pnUse )
        {
            if( pn == pnParent->pLeft && pnParent->pRight )
                pnUse = pnParent->pRight;
            else
            {
                pn = pnParent;
                pnParent = pnParent->pUp;
            }
        }
    }

    // Walk to the first leaf
    while( pnUse && !(pnUse->Flags & NODE_FLG_LEAF) )
    {
        if( pnUse->pLeft )
            pnUse = pnUse->pLeft;
        else
            pnUse = pnUse->pRight;
    }

    return( pnUse );
}