Windows编程

开发平台：
Visual C++

ALGO.C：源码内容
							/*++
Copyright (c) 1995  Microsoft Corporation
Module Name:
    netiplookupalgo.c
Abstract:
Revision History:
--*/
DWORD g_dwBitMask = {0x00000001,
                     0x00000002,
                     0x00000004,
                     0x00000008,
                     0x00000010,
                     0x00000020,
                     0x00000040,
                     0x00000080,
                     0x00000100,
                     0x00000200,
                     0x00000400,
                     0x00000800,
                     0x00001000,
                     0x00002000,
                     0x00004000,
                     0x00008000,
                     0x00010000,
                     0x00020000,
                     0x00040000,
                     0x00080000,
                     0x00100000,
                     0x00200000,
                     0x00400000,
                     0x00800000,
                     0x01000000,
                     0x02000000,
                     0x04000000,
                     0x08000000,
                     0x10000000,
                     0x20000000,
                     0x40000000,
                     0x80000000};
DWORD g_dwPrefixMask = {0x00000001,
                        0x00000003,
                        0x00000007,
                        0x0000000F,
                        0x0000001F,
                        0x0000003F,
                        0x0000007F,
                        0x000000FF,
                        0x000001FF,
                        0x000003FF,
                        0x000007FF,
                        0x00000FFF,
                        0x00001FFF,
                        0x00003FFF,
                        0x00007FFF,
                        0x0000FFFF,
                        0x0001FFFF,
                        0x0003FFFF,
                        0x0007FFFF,
                        0x000FFFFF,
                        0x001FFFFF,
                        0x003FFFFF,
                        0x007FFFFF,
                        0x00FFFFFF,
                        0x01FFFFFF,
                        0x03FFFFFF,
                        0x07FFFFFF,
                        0x0FFFFFFF,
                        0x1FFFFFFF,
                        0x3FFFFFFF,
                        0x7FFFFFFF,
                        0xFFFFFFFF}
BYTE
DistPos(
    IN  PTRIE_KEY   ptkKey1,
    IN  PTRIE_KEY   ptkKey2
    )
/*++
  Routine Description
      Returns the position of the distinguishing bit for two keys. This is
      the first bit that differs between the two keys.  If one key is a prefix
      of another (strict or non strict), then the dist bit is 1+width of the smaller
      key (== length of smaller key)
      
      Notationally:
      DistBit(K1, K2) = Min{i|K1[i] != K2[i]}
      DistBit(K1, K2) = Length(K1) iff K1 is a prefix of K2
      
      
  Arguments
  Return Value
      NO_ERROR
--*/
{
    BYTE    byLength;
    
    byLength = MAX(Length(ptkKey1),
                   Length(ptkKey2));
    
    for(i = 0; i < byLength; i++)
    {
        if(ptkKey1->dwAddr & g_dwBitMask[i] isnot
           ptkKey2->dwAddr & g_dwBitMask[i])
        {
            break;
        }
    }
    
    return i;
}
    
PTRIE_KEY
GetKey(
    IN  PTRIE_NODE  ptnNode,
    IN  PTRIE_KEY   ptkKey,
    OUT PBYTE       pbyPosition
    )
/*++
  Routine Description
      Given a input key and node, returns the stored key in the node
      whose index bit matches with the input key
  Arguments
  Return Value
      NO_ERROR
--*/
{
    
    if(Width(ptkKey) < Index(ptnNode))
    {
        return NULL;
    }
    *pbyPosition = GetRelevantBit(ptkKey->dwAddr, Index(ptnNode));
    
#if DBG
    //
    // A little consistency check here
    //
    
    if(LeftKey(ptnNode))
    {
        ASSERT(ptnNode->byPosition is LEFT);
    }
    if(RightKey(ptnNode))
    {
        ASSERT(ptnNode->byPosition is RIGHT);
    }
    
#endif
    
    return GetKeyByPosition(ptnNode,
                            *pbyPosition);
}
PTRIE_NODE
GetSubTrie(
    IN  PTRIE_NODE  ptnNode,
    IN  PTRIE_KEY   ptkKey,
    OUT PBYTE       pbyPosition
    )
/*++
  Routine Description
  Locks
  Arguments
  Return Value
      NO_ERROR
--*/
{
    
    if(Width(ptkKey) < Index(ptnNode))
    {
        return NULL;
    }
    *pbyPosition = GetRelevantBit(ptkKey->dwAddr, Index(ptnNode));
#if DBG
    //
    // A little consistency check here
    //
    
    if(LeftSubTrie(ptnNode))
    {
        ASSERT(ptnNode->ptnTrie[LEFT]->byPosition is LEFT);
    }
    if(RightSubTrie(ptnNode))
    {
        ASSERT(ptnNode->ptnTrie[RIGHT]->byPosition is RIGHT);
    }
    
#endif
    return GetSubTrieByPosition(ptnNode,
                                *pbyPosition);
    
}
PTRIE_KEY
GetClosestKey(
    PTRIE_NODE  ptnNode,
    PTRIE_KEY   ptkKey
    )
/*++
  Routine Description
      If the length of the key is greater than or equal to the index, return
      any Key.
      else
         If a key with matching relevant bit is found, return that, else
         return the other key
  Locks
  Arguments
  Return Value
      NO_ERROR
--*/
{
    PTRIE_KEY   ptkTemp;
    BYTE        byPos;
    
    if(Width(ptkKey) >= Index(ptnNode))
    {
        ptkTemp = GetKey(ptnNode,
                         ptkKey,
                         &byPos);
        
        if(ptkTemp isnot NULL)
        {
            return ptkTemp;
        }
        else
        {
            return GetKeyByPosition(ptnNode,
                                    ComplementPosition(byPos))
        }
    }
    else
    {
        //
        // For now we return the left key first
        //
        ptkTemp = GetKeyByPosition(ptnNode,
                                   LEFT);
        
        if(ptkTemp)
        {
            return ptkTemp;
        }
        else
        {
            return GetKeyByPosition(ptnNode,
                                    RIGHT);
        }
    }
}
PTRIE_NODE
GetClosestSubTrie(
    PTRIE_NODE  ptnNode,
    PTRIE_KEY   ptkKey
    )
/*++
  Routine Description
      If the length of the key is greater than or equal to the index, return
      any sub trie.
      else
         If a trie with matching relevant bit is found, return that, else
         return the other trie
  Locks
  Arguments
  Return Value
      NO_ERROR
--*/
{
    PTRIE_NODE  ptnTemp;
    BYTE        byPos;
    
    if(Width(ptkKey) >= Index(ptnNode))
    {
        ptnTemp = GetSubTrie(ptnNode,
                             ptkKey,
                             &byPos);
        
        if(ptnTemp isnot NULL)
        {
            return ptnTemp;
        }
        else
        {
            return GetSubTrieByPosition(ptnNode,
                                        ComplementPosition(byPos))
        }
    }
    else
    {
        //
        // For now we return the left trie first
        //
        ptkTemp = GetSubTrieByPosition(ptnNode,
                                       LEFT);
        
        if(ptkTemp)
        {
            return ptkTemp;
        }
        else
        {
            return GetSubTrieByPosition(ptnNode,
                                        RIGHT);
        }
    }
}
PTRIE_NODE
CreateNode(
    IN  BYTE        byIndex,
    IN  PTRIE_KEY   ptkKey
    )
/*++
  Routine Description
  Locks
  Arguments
  Return Value
      NO_ERROR
--*/
{
    PTRIE_NODE  ptnNode;
    ptnNode = HeapAlloc(g_hPrivateHeap,
                        0,
                        sizeof(TRIE_NODE));
    if(ptnNode is NULL)
    {
        printf("Unable to allocate node. Error %dn",
               GetLastError());
        return NULL;
    }
    
    ptnNode->ptnTrie[LEFT]  = NULL;
    ptnNode->ptnTrie[RIGHT] = NULL;
    
    ptnNode->ptnParent      = NULL;
    ptnNode->byIndex        = byIndex;
    //
    // See where the key would go into the allocated node
    //
    
    GetKey(ptnNode,
           ptkKey,
           &byPos);
    //
    // Since we are going to be inserting the key here, set
    // its position field also
    //
    ptkKey->byPos = byPos;
    
    ptnNode->rgptkKey[byPos]  = ptkKey;
    
    ptnNode->rgptkKey[ComplementPosition(byPos)] = NULL;
    return ptnNode;
}
DWORD
InsertKey(
    PTRIE_NODE  *pptnRoot,
    PTRIE_KEY   ptkKey
    )
/*++
  Routine Description
  Locks
  Arguments
  Return Value
      NO_ERROR
--*/
{
    PTRIE_NODE  ptnTempNode;
    if(*pptnRoot is NULL)
    {
        *pptnRoot = AllocateNode(Width(ptkKey),
                                 ptkKey);
        if(*pptnRoot is NULL)
        {
            return ERROR_NOT_ENOUGH_MEMORY;
        }
        return NO_ERROR;
    }
    ptnTempNode = *pptnRoot;
    //
    // Descend the tree, branching according to the Index bit
    // Stop when the node is a leaf OR
    // when the index is greater than the width of the key OR
    // when the prefix of the node is not the same as the key
    //
    // The prefix is found by (ptkKey->dwAddr & g_dwPrefixMask[Index])
    //
    
    while(!IsLeafNode(ptnTempNode) and
          (Width(ptkKey) > Index(ptnTempNode)) and
          (ptnTempNode->rgptkKey[ptnTempNode->byNonNullKey] & g_dwPrefixMask[Index(ptnTempNode)] is
           ptkKey[
    {
        ptnTempNode = ClosestSubTrie(ptnTempNode,
                                     ptkKey);
    }
    byDistPost = DistPos(key,
                         ClosestKey(ptnNode,ptkKey));
    byIndex = MIN(Lenght(Key), byDistPos);
    if(ptnTempNode is *pptnRoot)
    {
        InsertInOrAbove(pptnRoot,
                        ptnTempNode,
                        ptkKey,
                        byDistPos);
    }
    else
    {
        if(GetSubTrie(ptnNode, ptkKey) is NULL)
        {
            InsertWithEmptySubTrie(ptnNode,
                                   ptkKey,
                                   byDistPos);
        }
        else
        {
            InsertWithNonEmptySubTrie(ptnNode,
                                      ptkKey,
                                      byDistPos);
        }
    }
    return NO_ERROR;
}
    
DWORD
InsertInOrAbove(
    PTRIE_NODE  *pptnRoot,
    PTRIE_NODE  ptnNode,
    PTRIE_KEY   ptkKey,
    BYTE        byDistPos
    )
/*++
  Routine Description
  Locks
  Arguments
  Return Value
      NO_ERROR
--*/
{
    if(

						