node.c

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

//--------------------------------------------------------------------------
// Ip Stack
//--------------------------------------------------------------------------
// Node.C
//
// Route Node Object
//
// Author: Michael A. Denio
// Copyright 1999 by Texas Instruments Inc.
//-------------------------------------------------------------------------
#include <stkmain.h>

//---------------------
// Node
//---------------------

// Node Structure
typedef struct _node {
    uint                Type;           // Set to HTYPE_NODE
    uint                RefCount;       // # of open alloc's to this entry
    struct _node        *pUp;           // Up Node
    struct _node        *pLeft;         // 0 Node
    struct _node        *pRight;        // 1 Node
    uint                Flags;          // See flags
    uint                BitOffset;      // 0=MSB 31=LSB
    IPN                 dwTestMask;     // Bit `AND' compare value
    HANDLE              hRt;            // First Rt entry (leaf node only)
    uint                LastMaskBits;   // 0 to 32 (also bit offset of passlft)
    IPN                 dwLastIPAddr;   // MASKED Least restrictve IP hRt list
    IPN                 dwLastIPMask;   // Least restrictve Mask in hRt list
    } NODE;

#define NODE_FLG_PASSLEFT    0x0001  // Pass backtrack from right to left
#define NODE_FLG_LEAF        0x0002  // Leaf node
#define NODE_FLG_ENDL        0x0004  // Left Endpoint
#define NODE_FLG_ENDR        0x0008  // Right Endpoint

static NODE* pRoot = 0;

//--------------------------------------------------------------------
// NodeNew()
//
// Create
//--------------------------------------------------------------------
static HANDLE NodeNew( uint Flags, uint wBitOffset )
{
    NODE  *pn;
    UINT32 dwTmp;

    // If we can't get a message, we may as well lock up.
    if( !(pn = mmAlloc(sizeof(NODE))) )
    {
        DbgPrintf(DBG_WARN,"NodeNew: OOM");
        ExecLowResource();
        return(0);
    }

    // Initialize type
    pn->Type = HTYPE_NODE;

    // Initialize refcount
    pn->RefCount = 1;

    // Initialize defaults
    pn->pUp    = 0;
    pn->pLeft  = 0;
    pn->pRight = 0;
    pn->Flags  = Flags;
    pn->hRt    = 0;

    // If we're not a leaf, we need to calc the test mask
    if( !(Flags & NODE_FLG_LEAF) )
    {
        dwTmp = ( 1l << (31 - wBitOffset) );
        pn->BitOffset = wBitOffset;
        pn->dwTestMask = HNC32( dwTmp );
    }

    return( (HANDLE)pn );
}

//--------------------------------------------------------------------
// NodeFree()
//
// Destroy
//--------------------------------------------------------------------
static void NodeFree( HANDLE h )
{
    NODE *pn = (NODE *)h;

#ifdef _STRONG_CHECKING
    if( pn->Type != HTYPE_NODE )
    {
        DbgPrintf(DBG_ERROR,"NodeFree: HTYPE %04x",pn->Type);
        return;
    }
#endif

    // Kill type for debug
    pn->Type = 0;

    // Free the handle if we're done with it
    mmFree( pn );
}

//--------------------------------------------------------------------
// NodeUpdatePL()
//
// Update pass left values starting at the given leaf node
//--------------------------------------------------------------------
static void NodeUpdatePL( NODE *pn )
{
    NODE   *pnFrom;
    uint wLastMaskBits;
    IPN    dwLastIPMask;

    wLastMaskBits = pn->LastMaskBits;
    dwLastIPMask  = pn->dwLastIPMask;

    // Start Updating
    while( pn->pUp )
    {
        pnFrom = pn;
        pn = pn->pUp;

        // Only "left" children affect our pass left flag
        if( pnFrom != pn->pLeft )
            return;

        // We "pass left" if our bit offset is in the ZERO
        // portion of the child's mask bits
        if( pn->BitOffset >= wLastMaskBits )
        {
            pn->Flags |= NODE_FLG_PASSLEFT;
            pn->LastMaskBits = wLastMaskBits;  // Required for child updates
            pn->dwLastIPMask  = dwLastIPMask;   // This used by "NodeFind"
        }
        else
        {
            pn->Flags &= ~NODE_FLG_PASSLEFT;
            pn->LastMaskBits = 32;             // Full Mask
            pn->dwLastIPMask  = 0xffffffff;     // Full Mask
        }
    }
}

//--------------------------------------------------------------------
// NodeTreeNew()
//
// Initialze the node tree
//--------------------------------------------------------------------
void NodeTreeNew()
{
    NODE *pnL, *pnR;

    pRoot = (NODE *)NodeNew( 0, 0 );
    pnL   = (NODE *)NodeNew( NODE_FLG_LEAF|NODE_FLG_ENDL, 0 );
    pnR   = (NODE *)NodeNew( NODE_FLG_LEAF|NODE_FLG_ENDR, 0 );

    if( !pRoot || !pnL || !pnR )
    {
        DbgPrintf(DBG_ERROR,"NodeInit: OOM");
        return;
    }

    // Setup Root
    pRoot->pLeft  = pnL;
    pRoot->pRight = pnR;

    // Setup Left
    pnL->pUp           = pRoot;
    pnL->LastMaskBits = 0;
    pnL->dwLastIPMask  = 0;
    pnL->dwLastIPAddr  = 0;

    // Setup Right
    pnR->pUp           = pRoot;
    pnR->LastMaskBits = 32;
    pnR->dwLastIPMask  = 0xFFFFFFFF;
    pnR->dwLastIPAddr  = 0xFFFFFFFF;

    // Update the Pass Left Flags
    NodeUpdatePL( pnL );
}

//--------------------------------------------------------------------
// NodeTreeFree()
//
// Destroy the node table
//--------------------------------------------------------------------
void NodeTreeFree()
{
    NODE *pnL, *pnR;

    pnL   = pRoot->pLeft;
    pnR   = pRoot->pRight;

    if( !pRoot || !pnL || !pnR )
    {
        DbgPrintf(DBG_WARN,"NodeTreeFree: Null endpoints");
        return;
    }

    if( !(pnL->Flags & NODE_FLG_ENDL ) )
        DbgPrintf(DBG_WARN,"NodeTreeFree: Didn't find left");
    else if( !(pnR->Flags & NODE_FLG_ENDR ) )
        DbgPrintf(DBG_WARN,"NodeTreeFree: Didn't find right");
    else if( pnL->pLeft || pnL->pRight )
        DbgPrintf(DBG_WARN,"NodeTreeFree: Left has Children");
    else if( pnR->pLeft || pnR->pRight )
        DbgPrintf(DBG_WARN,"NodeTreeFree: Right has Children");

    NodeFree( pnL );
    NodeFree( pnR );
    NodeFree( pRoot );
    pRoot = 0;
}

//--------------------------------------------------------------------
// NodeAdd()
//
// Called to POTENTIALLY create a new leaf node.
//
// Increments Reference Count of the Node it returns.
//--------------------------------------------------------------------
HANDLE NodeAdd( IPN dwIPAddr, IPN dwIPMask, uint wMaskBits )
{
    NODE  *pn = pRoot;
    UINT32 dwMaskedAddr;

    // Use the most generic address to find a place in the table. This
    // way we are guaranteed not to backtrack.
    dwMaskedAddr = dwIPAddr & dwIPMask;

    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 are a valid node for this leaf,
            // then we'll just task ourselves on.

            // A leaf node can be shared if both addrs are equal when
            // their own respective masks are applied.
            if( pn->dwLastIPAddr == dwMaskedAddr )
            {
                // This leaf can be shared

                // Reference it
                NodeRef( pn );

                // Set the new "least restritive" mask
                if( wMaskBits < pn->LastMaskBits )
                {
                    pn->LastMaskBits = wMaskBits;
                    pn->dwLastIPMask  = dwIPMask;
                    NodeUpdatePL( pn );
                }
                goto NODE_ADD_DONE;
            }
            else
            {
                // Leaf can not be shared. We thus need two additional
                // nodes. One will be a new branch node, and the other
                // will be a new leaf.
                NODE* pnLeaf;
                NODE* pnBranch;

                // The last thing to determine is the bit offset of the
                // first "different" bit in the two addresses.
                UINT32 dwTest1,dwTest2;
                uint  w;

                dwTest1 = dwMaskedAddr ^ pn->dwLastIPAddr;
                dwTest1 = HNC32( dwTest1 );
                dwTest2 = 0x80000000;
                w = 0;

                // Find the first "different" bit
                while( !( dwTest1 & dwTest2 ) )
                {
                    w++;
                    dwTest2 >>= 1;
                }

                // Now we have the first diffent bit in w, where 0=MSB
                if( !(pnBranch = (NODE *)NodeNew( 0, w )) )
                {
                    pn = 0;
                    goto NODE_ADD_DONE;
                }

                if( !(pnLeaf = (NODE *)NodeNew( NODE_FLG_LEAF, 0 )) )
                {
                    NodeFree( pnBranch );
                    pn = 0;
                    goto NODE_ADD_DONE;
                }

                // Now we need to insert the node in its correct location.
                while( pn->pUp->BitOffset > w )
                    pn = pn->pUp;

                // Start Inserting
                pnBranch->pUp = pn->pUp;