home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / netds / rras / lookup / algo.c next >
Encoding:
Text File  |  1997-06-10  |  10.6 KB  |  536 lines
  1. /*++
  2.  
  3. Copyright (c) 1995  Microsoft Corporation
  4.  
  5. Module Name:
  6.  
  7.     net\ip\lookup\algo.c
  8.  
  9. Abstract:
  10.  
  11.  
  12. Revision History:
  13.  
  14.  
  15.  
  16. --*/
  17.  
  18. DWORD g_dwBitMask = {0x00000001,
  19.                      0x00000002,
  20.                      0x00000004,
  21.                      0x00000008,
  22.                      0x00000010,
  23.                      0x00000020,
  24.                      0x00000040,
  25.                      0x00000080,
  26.                      0x00000100,
  27.                      0x00000200,
  28.                      0x00000400,
  29.                      0x00000800,
  30.                      0x00001000,
  31.                      0x00002000,
  32.                      0x00004000,
  33.                      0x00008000,
  34.                      0x00010000,
  35.                      0x00020000,
  36.                      0x00040000,
  37.                      0x00080000,
  38.                      0x00100000,
  39.                      0x00200000,
  40.                      0x00400000,
  41.                      0x00800000,
  42.                      0x01000000,
  43.                      0x02000000,
  44.                      0x04000000,
  45.                      0x08000000,
  46.                      0x10000000,
  47.                      0x20000000,
  48.                      0x40000000,
  49.                      0x80000000};
  50.  
  51.  
  52. DWORD g_dwPrefixMask = {0x00000001,
  53.                         0x00000003,
  54.                         0x00000007,
  55.                         0x0000000F,
  56.                         0x0000001F,
  57.                         0x0000003F,
  58.                         0x0000007F,
  59.                         0x000000FF,
  60.                         0x000001FF,
  61.                         0x000003FF,
  62.                         0x000007FF,
  63.                         0x00000FFF,
  64.                         0x00001FFF,
  65.                         0x00003FFF,
  66.                         0x00007FFF,
  67.                         0x0000FFFF,
  68.                         0x0001FFFF,
  69.                         0x0003FFFF,
  70.                         0x0007FFFF,
  71.                         0x000FFFFF,
  72.                         0x001FFFFF,
  73.                         0x003FFFFF,
  74.                         0x007FFFFF,
  75.                         0x00FFFFFF,
  76.                         0x01FFFFFF,
  77.                         0x03FFFFFF,
  78.                         0x07FFFFFF,
  79.                         0x0FFFFFFF,
  80.                         0x1FFFFFFF,
  81.                         0x3FFFFFFF,
  82.                         0x7FFFFFFF,
  83.                         0xFFFFFFFF}
  84.  
  85.  
  86.  
  87. BYTE
  88. DistPos(
  89.     IN  PTRIE_KEY   ptkKey1,
  90.     IN  PTRIE_KEY   ptkKey2
  91.     )
  92. /*++
  93.   Routine Description
  94.       Returns the position of the distinguishing bit for two keys. This is
  95.       the first bit that differs between the two keys.  If one key is a prefix
  96.       of another (strict or non strict), then the dist bit is 1+width of the smaller
  97.       key (== length of smaller key)
  98.       
  99.       Notationally:
  100.       DistBit(K1, K2) = Min{i|K1[i] != K2[i]}
  101.       DistBit(K1, K2) = Length(K1) iff K1 is a prefix of K2
  102.       
  103.       
  104.   Arguments
  105.  
  106.  
  107.   Return Value
  108.       NO_ERROR
  109.  
  110. --*/
  111. {
  112.     BYTE    byLength;
  113.     
  114.     byLength = MAX(Length(ptkKey1),
  115.                    Length(ptkKey2));
  116.     
  117.     for(i = 0; i < byLength; i++)
  118.     {
  119.         if(ptkKey1->dwAddr & g_dwBitMask[i] isnot
  120.            ptkKey2->dwAddr & g_dwBitMask[i])
  121.         {
  122.             break;
  123.         }
  124.     }
  125.     
  126.     return i;
  127. }
  128.  
  129.  
  130.  
  131.  
  132.  
  133.     
  134. PTRIE_KEY
  135. GetKey(
  136.     IN  PTRIE_NODE  ptnNode,
  137.     IN  PTRIE_KEY   ptkKey,
  138.     OUT PBYTE       pbyPosition
  139.     )
  140. /*++
  141.   Routine Description
  142.       Given a input key and node, returns the stored key in the node
  143.       whose index bit matches with the input key
  144.  
  145.   Arguments
  146.  
  147.  
  148.   Return Value
  149.       NO_ERROR
  150.  
  151. --*/
  152. {
  153.     
  154.     if(Width(ptkKey) < Index(ptnNode))
  155.     {
  156.         return NULL;
  157.     }
  158.  
  159.     *pbyPosition = GetRelevantBit(ptkKey->dwAddr, Index(ptnNode));
  160.     
  161. #if DBG
  162.  
  163.     //
  164.     // A little consistency check here
  165.     //
  166.     
  167.     if(LeftKey(ptnNode))
  168.     {
  169.         ASSERT(ptnNode->byPosition is LEFT);
  170.     }
  171.  
  172.     if(RightKey(ptnNode))
  173.     {
  174.         ASSERT(ptnNode->byPosition is RIGHT);
  175.     }
  176.     
  177. #endif
  178.     
  179.     return GetKeyByPosition(ptnNode,
  180.                             *pbyPosition);
  181. }
  182.  
  183. PTRIE_NODE
  184. GetSubTrie(
  185.     IN  PTRIE_NODE  ptnNode,
  186.     IN  PTRIE_KEY   ptkKey,
  187.     OUT PBYTE       pbyPosition
  188.     )
  189. /*++
  190.   Routine Description
  191.  
  192.  
  193.   Locks
  194.  
  195.  
  196.   Arguments
  197.  
  198.  
  199.   Return Value
  200.       NO_ERROR
  201.  
  202. --*/
  203. {
  204.     
  205.     if(Width(ptkKey) < Index(ptnNode))
  206.     {
  207.         return NULL;
  208.     }
  209.  
  210.     *pbyPosition = GetRelevantBit(ptkKey->dwAddr, Index(ptnNode));
  211.  
  212. #if DBG
  213.  
  214.     //
  215.     // A little consistency check here
  216.     //
  217.     
  218.     if(LeftSubTrie(ptnNode))
  219.     {
  220.         ASSERT(ptnNode->ptnTrie[LEFT]->byPosition is LEFT);
  221.     }
  222.  
  223.     if(RightSubTrie(ptnNode))
  224.     {
  225.         ASSERT(ptnNode->ptnTrie[RIGHT]->byPosition is RIGHT);
  226.     }
  227.     
  228. #endif
  229.  
  230.     return GetSubTrieByPosition(ptnNode,
  231.                                 *pbyPosition);
  232.     
  233. }
  234.  
  235. PTRIE_KEY
  236. GetClosestKey(
  237.     PTRIE_NODE  ptnNode,
  238.     PTRIE_KEY   ptkKey
  239.     )
  240. /*++
  241.   Routine Description
  242.       If the length of the key is greater than or equal to the index, return
  243.       any Key.
  244.       else
  245.          If a key with matching relevant bit is found, return that, else
  246.          return the other key
  247.  
  248.   Locks
  249.  
  250.  
  251.   Arguments
  252.  
  253.  
  254.   Return Value
  255.       NO_ERROR
  256.  
  257. --*/
  258. {
  259.     PTRIE_KEY   ptkTemp;
  260.     BYTE        byPos;
  261.     
  262.     if(Width(ptkKey) >= Index(ptnNode))
  263.     {
  264.         ptkTemp = GetKey(ptnNode,
  265.                          ptkKey,
  266.                          &byPos);
  267.         
  268.         if(ptkTemp isnot NULL)
  269.         {
  270.             return ptkTemp;
  271.         }
  272.         else
  273.         {
  274.             return GetKeyByPosition(ptnNode,
  275.                                     ComplementPosition(byPos))
  276.         }
  277.     }
  278.     else
  279.     {
  280.         //
  281.         // For now we return the left key first
  282.         //
  283.  
  284.         ptkTemp = GetKeyByPosition(ptnNode,
  285.                                    LEFT);
  286.         
  287.         if(ptkTemp)
  288.         {
  289.             return ptkTemp;
  290.         }
  291.         else
  292.         {
  293.             return GetKeyByPosition(ptnNode,
  294.                                     RIGHT);
  295.         }
  296.     }
  297. }
  298.  
  299. PTRIE_NODE
  300. GetClosestSubTrie(
  301.     PTRIE_NODE  ptnNode,
  302.     PTRIE_KEY   ptkKey
  303.     )
  304. /*++
  305.   Routine Description
  306.       If the length of the key is greater than or equal to the index, return
  307.       any sub trie.
  308.       else
  309.          If a trie with matching relevant bit is found, return that, else
  310.          return the other trie
  311.  
  312.   Locks
  313.  
  314.  
  315.   Arguments
  316.  
  317.  
  318.   Return Value
  319.       NO_ERROR
  320.  
  321. --*/
  322. {
  323.     PTRIE_NODE  ptnTemp;
  324.     BYTE        byPos;
  325.  
  326.     
  327.     if(Width(ptkKey) >= Index(ptnNode))
  328.     {
  329.         ptnTemp = GetSubTrie(ptnNode,
  330.                              ptkKey,
  331.                              &byPos);
  332.         
  333.         if(ptnTemp isnot NULL)
  334.         {
  335.             return ptnTemp;
  336.         }
  337.         else
  338.         {
  339.             return GetSubTrieByPosition(ptnNode,
  340.                                         ComplementPosition(byPos))
  341.         }
  342.     }
  343.     else
  344.     {
  345.         //
  346.         // For now we return the left trie first
  347.         //
  348.  
  349.         ptkTemp = GetSubTrieByPosition(ptnNode,
  350.                                        LEFT);
  351.         
  352.         if(ptkTemp)
  353.         {
  354.             return ptkTemp;
  355.         }
  356.         else
  357.         {
  358.             return GetSubTrieByPosition(ptnNode,
  359.                                         RIGHT);
  360.         }
  361.     }
  362. }
  363.  
  364. PTRIE_NODE
  365. CreateNode(
  366.     IN  BYTE        byIndex,
  367.     IN  PTRIE_KEY   ptkKey
  368.     )
  369. /*++
  370.   Routine Description
  371.  
  372.  
  373.   Locks
  374.  
  375.  
  376.   Arguments
  377.  
  378.  
  379.   Return Value
  380.       NO_ERROR
  381.  
  382. --*/
  383. {
  384.     PTRIE_NODE  ptnNode;
  385.  
  386.     ptnNode = HeapAlloc(g_hPrivateHeap,
  387.                         0,
  388.                         sizeof(TRIE_NODE));
  389.  
  390.     if(ptnNode is NULL)
  391.     {
  392.         printf("Unable to allocate node. Error %d\n",
  393.                GetLastError());
  394.  
  395.         return NULL;
  396.     }
  397.     
  398.     ptnNode->ptnTrie[LEFT]  = NULL;
  399.     ptnNode->ptnTrie[RIGHT] = NULL;
  400.     
  401.     ptnNode->ptnParent      = NULL;
  402.  
  403.     ptnNode->byIndex        = byIndex;
  404.  
  405.     //
  406.     // See where the key would go into the allocated node
  407.     //
  408.     
  409.     GetKey(ptnNode,
  410.            ptkKey,
  411.            &byPos);
  412.  
  413.     //
  414.     // Since we are going to be inserting the key here, set
  415.     // its position field also
  416.     //
  417.  
  418.     ptkKey->byPos = byPos;
  419.     
  420.     ptnNode->rgptkKey[byPos]  = ptkKey;
  421.     
  422.     ptnNode->rgptkKey[ComplementPosition(byPos)] = NULL;
  423.  
  424.     return ptnNode;
  425. }
  426.  
  427. DWORD
  428. InsertKey(
  429.     PTRIE_NODE  *pptnRoot,
  430.     PTRIE_KEY   ptkKey
  431.     )
  432. /*++
  433.   Routine Description
  434.  
  435.  
  436.   Locks
  437.  
  438.  
  439.   Arguments
  440.  
  441.  
  442.   Return Value
  443.       NO_ERROR
  444.  
  445. --*/
  446. {
  447.     PTRIE_NODE  ptnTempNode;
  448.  
  449.     if(*pptnRoot is NULL)
  450.     {
  451.         *pptnRoot = AllocateNode(Width(ptkKey),
  452.                                  ptkKey);
  453.  
  454.         if(*pptnRoot is NULL)
  455.         {
  456.             return ERROR_NOT_ENOUGH_MEMORY;
  457.         }
  458.  
  459.         return NO_ERROR;
  460.     }
  461.  
  462.     ptnTempNode = *pptnRoot;
  463.  
  464.     //
  465.     // Descend the tree, branching according to the Index bit
  466.     // Stop when the node is a leaf OR
  467.     // when the index is greater than the width of the key OR
  468.     // when the prefix of the node is not the same as the key
  469.     //
  470.     // The prefix is found by (ptkKey->dwAddr & g_dwPrefixMask[Index])
  471.     //
  472.     
  473.     while(!IsLeafNode(ptnTempNode) and
  474.           (Width(ptkKey) > Index(ptnTempNode)) and
  475.           (ptnTempNode->rgptkKey[ptnTempNode->byNonNullKey] & g_dwPrefixMask[Index(ptnTempNode)] is
  476.            ptkKey[
  477.     {
  478.         ptnTempNode = ClosestSubTrie(ptnTempNode,
  479.                                      ptkKey);
  480.     }
  481.  
  482.     byDistPost = DistPos(key,
  483.                          ClosestKey(ptnNode,ptkKey));
  484.  
  485.     byIndex = MIN(Lenght(Key), byDistPos);
  486.  
  487.     if(ptnTempNode is *pptnRoot)
  488.     {
  489.         InsertInOrAbove(pptnRoot,
  490.                         ptnTempNode,
  491.                         ptkKey,
  492.                         byDistPos);
  493.     }
  494.     else
  495.     {
  496.         if(GetSubTrie(ptnNode, ptkKey) is NULL)
  497.         {
  498.             InsertWithEmptySubTrie(ptnNode,
  499.                                    ptkKey,
  500.                                    byDistPos);
  501.         }
  502.         else
  503.         {
  504.             InsertWithNonEmptySubTrie(ptnNode,
  505.                                       ptkKey,
  506.                                       byDistPos);
  507.         }
  508.     }
  509.  
  510.     return NO_ERROR;
  511. }
  512.     
  513. DWORD
  514. InsertInOrAbove(
  515.     PTRIE_NODE  *pptnRoot,
  516.     PTRIE_NODE  ptnNode,
  517.     PTRIE_KEY   ptkKey,
  518.     BYTE        byDistPos
  519.     )
  520. /*++
  521.   Routine Description
  522.  
  523.  
  524.   Locks
  525.  
  526.  
  527.   Arguments
  528.  
  529.  
  530.   Return Value
  531.       NO_ERROR
  532.  
  533. --*/
  534. {
  535.     if(
  536.