home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / winbase / debug / deb / linklist.c < prev    next >
C/C++ Source or Header  |  1997-10-05  |  17KB  |  515 lines
  1. // ************************************************************************
  2. //
  3. //                      Microsoft Developer Support
  4. //             Copyright (c) 1992-1997 Microsoft Corporation
  5. //
  6. // ************************************************************************
  7. // MODULE    : LinkList.C - Ordered Double Linked List Package
  8. // PURPOSE   : Provide a general, sorted, double linked list package
  9. // FUNCTIONS :
  10. //   CreateList        - allocate memory for a new list, registers the
  11. //                       ordering function
  12. //   CreateNode        - allocate memory fpr a new node that can be put
  13. //                       into the linked list
  14. //   InsertNode        - insert a new node into the list
  15. //   SetCurrentNode    - finds the 1st occurence of a node that matches
  16. //                       a key(s) according to the match function
  17. //                       and sets it as the current node
  18. //   SetCurrentNodeEx  - finds the Nth occurence of a node that matches
  19. //                       a key(s) according to the match function
  20. //                       and sets it as the current node
  21. //   GetCurrentNode    - get the current node
  22. //   GetFirstNode      - get the first (left-most) node in the list
  23. //   GetLastNode       - get the last (right-most) node in the list
  24. //   GetNextNode       - get the next (right) node from the current
  25. //   GetPrevNode       - get the previous (left) node from the current
  26. //   DeleteCurrentNode - deletes the current node from the list and
  27. //                       frees the memory associated with it
  28. //   DestroyNode       - deallocates the memory associated with a node
  29. //   DestroyList       - deallocates the memory associated with a list,
  30. //                       does not delete any of the nodes
  31. //   GetListError      - gets the current list error
  32. //
  33. // COMMENTS  : The application must serialize access to the linked list
  34. //
  35. //   Format of the Ordering and Matching functions is as follows:
  36. //   -----------------------------------------------------------
  37. //
  38. //   int OrderFunc( PNODE pNodeOne, PNODE pNodeTwo )
  39. //   {
  40. //     if( (pNodeOne->pNodeData).SortKey <  (pNodeTwo->pNodeData).SortKey )
  41. //       return( LIST_LEFT_OF  );
  42. //     if( (pNodeOne->pNodeData).SortKey == (pNodeTwo->pNodeData).SortKey )
  43. //       return( LIST_MATCH    );
  44. //     if( (pNodeOne->pNodeData).SortKey  > (pNodeTwo->pNodeData).SortKey )
  45. //       return( LIST_RIGHT_OF );
  46. //   }
  47. //
  48. // ************************************************************************
  49. #include <StdLib.H>     // malloc(), free()
  50. #include "LinkList.H"
  51.  
  52. //-- NULL pointer dereferencing checking macro
  53. #define CHECK_POINTER( ppNode )                                       \
  54.           if( ppNode == NULL ) {                                      \
  55.             return( pList->ListError = LIST_ERROR_DEREFERENCE_NULL ); \
  56.           }
  57.  
  58.  
  59. // ************************************************************************
  60. // FUNCTION : CreateList( PLIST* ppList, int (*)(PNODE, PNODE) ) )
  61. // PURPOSE  : allocate a new list, registers the ordering function
  62. // COMMENTS : sets all pointers to NULL
  63. // ************************************************************************
  64. BOOL
  65. CreateList( PLIST* ppList, int (*OrderFunction)( PNODE pNodeOne, PNODE pNodeTwo ) )
  66. {
  67.   *ppList = (PLIST) malloc( sizeof(LIST) );
  68.   if( ppList == NULL ) {
  69.     (*ppList)->ListError = LIST_NO_ERROR;
  70.     return( FALSE );
  71.   }
  72.  
  73.   //-- register the link list data ordering function
  74.   (*ppList)->OrderFunction = OrderFunction;
  75.  
  76.   //-- initialize the general linked list node pointers to NULL
  77.   (*ppList)->pFirstNode   = NULL;
  78.   (*ppList)->pCurrentNode = NULL;
  79.   (*ppList)->pLastNode    = NULL;
  80.  
  81.   //-- indicate no error
  82.   (*ppList)->ListError  = LIST_NO_ERROR;
  83.  
  84.   return( TRUE );
  85. }
  86.  
  87.  
  88. // ************************************************************************
  89. // FUNCTION : CreateNode( PNODE* )
  90. // PURPOSE  : create/allocate a new node that can be put into list
  91. // COMMENTS :
  92. // ************************************************************************
  93. BOOL
  94. CreateNode( PNODE* ppNewNode )
  95. {
  96.   *ppNewNode = (PNODE) malloc( sizeof(NODE) );
  97.   if( *ppNewNode == NULL ) {
  98.     return( FALSE );
  99.   }
  100.  
  101.   //-- initialize the node pointers to NULL
  102.   (*ppNewNode)->pRightLink = NULL;
  103.   (*ppNewNode)->pLeftLink  = NULL;
  104.  
  105.   return( TRUE );
  106. }
  107.  
  108.  
  109. // ************************************************************************
  110. // FUNCTION : InsertNode( PLIST pList, PNODE )
  111. // PURPOSE  : insert a new node into the list
  112. // COMMENTS :
  113. //   All nodes must have a unique key entry (from order function), if a
  114. //   match is found during an insert then the old node gets replaced with
  115. //   the new node.
  116. //
  117. //  NOTE: changes pList->pCurrentNode
  118. // ************************************************************************
  119. BOOL
  120. InsertNode( PLIST pList, PNODE pNewNode )
  121. {
  122.   int Position;
  123.   int LastPosition;
  124.  
  125.   //-- if this is the first node in a new list
  126.   if( pList->pFirstNode == NULL ) {
  127.     pList->pFirstNode   = pNewNode;
  128.     pList->pLastNode    = pNewNode;
  129.     pList->pCurrentNode = pNewNode;
  130.     pList->ListError    = LIST_NO_ERROR;
  131.     return( TRUE );
  132.   }
  133.  
  134.   Position = (*(pList->OrderFunction))( pNewNode, pList->pCurrentNode );
  135.  
  136.   //-- search for insertion point
  137.   while( pList->pCurrentNode != NULL ) {
  138.  
  139.     LastPosition = Position;
  140.     Position = (*(pList->OrderFunction))(pNewNode, pList->pCurrentNode);
  141.  
  142.     if( pList->pFirstNode == pList->pLastNode )
  143.       break;
  144.  
  145.     if( Position != LastPosition )
  146.       break;
  147.  
  148.     if( pList->pCurrentNode == pList->pFirstNode ) {
  149.       if( Position == LIST_RIGHT_OF ) {
  150.         pList->pCurrentNode = pList->pCurrentNode->pRightLink;
  151.         continue;
  152.       }
  153.       break;
  154.     }
  155.  
  156.     if( pList->pCurrentNode == pList->pLastNode ) {
  157.       if( Position == LIST_LEFT_OF ) {
  158.         pList->pCurrentNode = pList->pCurrentNode->pLeftLink;
  159.         continue;
  160.       }
  161.       break;
  162.     }
  163.  
  164.     if( Position == LastPosition ) {
  165.       if( Position == LIST_LEFT_OF) {
  166.         pList->pCurrentNode = pList->pCurrentNode->pLeftLink;
  167.         continue;
  168.       }
  169.       if( Position == LIST_RIGHT_OF ) {
  170.         pList->pCurrentNode = pList->pCurrentNode->pRightLink;
  171.         continue;
  172.       }
  173.       break;
  174.     }
  175.  
  176.   }
  177.  
  178.   //-- now, insert the pNewNode
  179.   switch( Position ) {
  180.  
  181.     case LIST_LEFT_OF:
  182.       pNewNode->pRightLink = pList->pCurrentNode;
  183.       pNewNode->pLeftLink  = pList->pCurrentNode->pLeftLink;
  184.       if( pList->pCurrentNode == pList->pFirstNode )
  185.         pList->pFirstNode = pNewNode;
  186.       else
  187.         pList->pCurrentNode->pLeftLink->pRightLink = pNewNode;
  188.       pList->pCurrentNode->pLeftLink = pNewNode;
  189.       break;
  190.  
  191.   #if 1  // replace duplicates with new data
  192.  
  193.     case LIST_MATCH:
  194.       pNewNode->pLeftLink  = pList->pCurrentNode->pLeftLink;
  195.       pNewNode->pRightLink = pList->pCurrentNode->pRightLink;
  196.       if( pList->pCurrentNode == pList->pLastNode )
  197.         pList->pLastNode = pNewNode;
  198.       else
  199.         pList->pCurrentNode->pRightLink->pLeftLink = pNewNode;
  200.       if( pList->pCurrentNode == pList->pFirstNode )
  201.         pList->pFirstNode = pNewNode;
  202.       else
  203.         pList->pCurrentNode->pLeftLink->pRightLink = pNewNode;
  204.       // note: doesn't destroy extra data associated with the node
  205.       DestroyNode( pList->pCurrentNode );
  206.       break;
  207.  
  208.   #else // or allow duplicates
  209.  
  210.     case LIST_MATCH:
  211.  
  212.   #endif
  213.  
  214.     case LIST_RIGHT_OF:
  215.       pNewNode->pLeftLink  = pList->pCurrentNode;
  216.       pNewNode->pRightLink = pList->pCurrentNode->pRightLink;
  217.       if( pList->pCurrentNode == pList->pLastNode )
  218.         pList->pLastNode = pNewNode;
  219.       else
  220.         pList->pCurrentNode->pRightLink->pLeftLink = pNewNode;
  221.       pList->pCurrentNode->pRightLink = pNewNode;
  222.       break;
  223.  
  224.   }
  225.   pList->pCurrentNode = pNewNode;
  226.   pList->ListError    = LIST_NO_ERROR;
  227.  
  228.   return( TRUE );
  229. }
  230.  
  231.  
  232. // ************************************************************************
  233. // FUNCTION : SetCurrentNode( PLIST pList, PNODE, int (*)(PNODE, PNODE) )
  234. // PURPOSE  : finds the first occurence of a node from the list that matches
  235. //            a key(s) according to the match function.
  236. // COMMENTS :
  237. //   May use the ordering function or a new matching function if not
  238. //   searching for a match based on the primary ordering key.
  239. //   NOTE: the matching and ordering functions have the same definition.
  240. //   NOTE: changes pList->pCurrentNode.
  241. // ************************************************************************
  242. BOOL
  243. SetCurrentNode( PLIST pList, PNODE pKeyNode,
  244.          int (*MatchFunction)( PNODE pNodeOne, PNODE pNodeTwo ) )
  245. {
  246.   return( SetCurrentNodeEx( pList, pKeyNode, MatchFunction, 1 ) );
  247. }
  248.  
  249.  
  250. // ************************************************************************
  251. // FUNCTION : SetCurrentNodeEx( PLIST pList, PNODE, int (*)(PNODE, PNODE), int )
  252. // PURPOSE  : finds the Nth occurence of a node from the list that matches
  253. //            a key(s) according to the match function.
  254. // COMMENTS :
  255. //   May use the ordering function or a new matching function if not
  256. //   searching for a match based on the primary ordering key.
  257. //   NOTE: the matching and ordering functions have the same definition.
  258. //   NOTE: changes pList->pCurrentNode.
  259. // ************************************************************************
  260. BOOL
  261. SetCurrentNodeEx( PLIST pList, PNODE pKeyNode,
  262.   int (*MatchFunction)( PNODE pNodeOne, PNODE pNodeTwo ),
  263.   int Occurence )
  264. {
  265.   int Position;
  266.  
  267.   //-- if list is empty, exit
  268.   if( pList->pCurrentNode == NULL ) {
  269.     pList->ListError = LIST_ERROR_NO_NODE;
  270.     return( FALSE );
  271.   }
  272.  
  273.   //-- if match and order are same function
  274.   if( MatchFunction == (pList->OrderFunction) ) {
  275.     int  LastPosition;
  276.  
  277.     LastPosition = Position = (*MatchFunction)(pKeyNode, pList->pCurrentNode);
  278.  
  279.     while( Occurence ) {
  280.       if( ( Position == LIST_LEFT_OF ) && ( LastPosition == LIST_LEFT_OF )
  281.           && ( pList->pCurrentNode != pList->pFirstNode ) )
  282.         pList->pCurrentNode = pList->pCurrentNode->pLeftLink;
  283.       else if( ( Position == LIST_RIGHT_OF ) && ( LastPosition == LIST_RIGHT_OF )
  284.             && ( pList->pCurrentNode != pList->pLastNode ) )
  285.         pList->pCurrentNode = pList->pCurrentNode->pRightLink;
  286.       else {
  287.         Occurence--;
  288.         continue;
  289.       }
  290.       LastPosition = Position;
  291.       Position = (*MatchFunction)(pKeyNode, pList->pCurrentNode);
  292.     }
  293.  
  294.   }
  295.   //-- match and order are not the same function, thus start
  296.   //   the search at the front of the list
  297.   else {
  298.     pList->pCurrentNode = pList->pFirstNode;
  299.     while( (Occurence > 0) && ( (pList->pCurrentNode) != NULL ) ) {
  300.       Position = (*MatchFunction)(pKeyNode, pList->pCurrentNode);
  301.       if( Position == LIST_MATCH )
  302.         Occurence--;
  303.       if( Occurence > 0 )
  304.         pList->pCurrentNode = pList->pCurrentNode->pRightLink;
  305.     }
  306.   }
  307.  
  308.   if( ( Position == LIST_MATCH ) && ( Occurence == 0 ) ) {
  309.     pList->ListError = LIST_NO_ERROR;
  310.     return( TRUE );
  311.   }
  312.   pList->ListError = LIST_ERROR_NO_MATCH;
  313.  
  314.   return( FALSE );
  315. }
  316.  
  317.  
  318. // ************************************************************************
  319. // FUNCTION : GetCurrentNode( PLIST pList, PNODE* )
  320. // PURPOSE  : gets the current node from the list
  321. // COMMENTS :
  322. //   Does not change pList->pCurrentNode.
  323. //   Changes ppNode, thus do not pass in a ppNode which has additional
  324. //   memory associated with it.
  325. // ************************************************************************
  326. BOOL
  327. GetCurrentNode( PLIST pList, PNODE* ppNode )
  328. {
  329.   CHECK_POINTER( ppNode );
  330.   if( pList->pCurrentNode == NULL ) {
  331.     pList->ListError = LIST_ERROR_NO_NODE;
  332.     return( FALSE );
  333.   }
  334.   *ppNode = pList->pCurrentNode;
  335.   pList->ListError = LIST_NO_ERROR;
  336.  
  337.   return( TRUE );
  338. }
  339.  
  340.  
  341. // ************************************************************************
  342. // FUNCTION : GetFirstNode( PLIST pList, PNODE* )
  343. // PURPOSE  : gets the first (left-most) node from the list
  344. // COMMENTS :
  345. //   Does not change pList->pCurrentNode.
  346. //   Changes ppNode, thus do not pass in a ppNode which has additional
  347. //   memory associated with it.
  348. // ************************************************************************
  349. BOOL
  350. GetFirstNode( PLIST pList, PNODE* ppNode )
  351. {
  352.   CHECK_POINTER( ppNode );
  353.   if( pList->pFirstNode == NULL ) {
  354.     pList->ListError = LIST_ERROR_NO_NODE;
  355.     return( FALSE );
  356.   }
  357.   *ppNode = pList->pFirstNode;
  358.   pList->ListError = LIST_NO_ERROR;
  359.  
  360.   return( TRUE );
  361. }
  362.  
  363.  
  364. // ************************************************************************
  365. // FUNCTION : GetLastNode( PLIST pList, PNODE* )
  366. // PURPOSE  : get the last (right-most) node from the List
  367. // COMMENTS :
  368. //   Does not change pList->pCurrentNode.
  369. //   Changes ppNode, thus do not pass in a ppNode which has additional
  370. //   memory associated with it.
  371. // ************************************************************************
  372. BOOL
  373. GetLastNode( PLIST pList, PNODE* ppNode )
  374. {
  375.   CHECK_POINTER( ppNode );
  376.   if( pList->pLastNode == NULL ) {
  377.     pList->ListError = LIST_ERROR_NO_NODE;
  378.     return( FALSE );
  379.   }
  380.   *ppNode = pList->pLastNode;
  381.   pList->ListError = LIST_NO_ERROR;
  382.  
  383.   return( TRUE );
  384. }
  385.  
  386.  
  387. // ************************************************************************
  388. // FUNCTION : GetNextNode( PLIST pList, PNODE* )
  389. // PURPOSE  : get the next (right) node from the pList->pCurrentNode
  390. // COMMENTS :
  391. //   Does not change pList->pCurrentNode.
  392. //   Changes ppNode, thus do not pass in a ppNode which has additional
  393. //   memory associated with it.
  394. // ************************************************************************
  395. BOOL
  396. GetNextNode( PLIST pList, PNODE* ppNode )
  397. {
  398.   CHECK_POINTER( ppNode );
  399.   if( (*ppNode)->pRightLink == NULL ) {
  400.     pList->ListError = LIST_ERROR_NO_NODE;
  401.     return( FALSE );
  402.   }
  403.   *ppNode = (*ppNode)->pRightLink;
  404.   pList->ListError = LIST_NO_ERROR;
  405.  
  406.   return( TRUE );
  407. }
  408.  
  409.  
  410. // ************************************************************************
  411. // FUNCTION : GetPrevNode( PLIST pList, PNODE* )
  412. // PURPOSE  : get the previous (left) node from the pList->pCurrentNode
  413. // COMMENTS :
  414. //   Does not change pList->pCurrentNode.
  415. //   Changes ppNode, thus do not pass in a ppNode which has additional
  416. //   memory associated with it.
  417. // ************************************************************************
  418. BOOL
  419. GetPrevNode( PLIST pList, PNODE* ppNode )
  420. {
  421.   CHECK_POINTER( ppNode );
  422.   if( (*ppNode)->pLeftLink == NULL ) {
  423.     pList->ListError = LIST_ERROR_NO_NODE;
  424.     return( FALSE );
  425.   }
  426.   *ppNode = (*ppNode)->pLeftLink;
  427.   pList->ListError = LIST_NO_ERROR;
  428.  
  429.   return( TRUE );
  430. }
  431.  
  432.  
  433. // ************************************************************************
  434. // FUNCTION : DeleteCurrentNode( PLIST pList )
  435. // PURPOSE  : deletes the current node from the list and frees the memory
  436. //            associated with it
  437. // COMMENTS :
  438. //   Changes pList->pCurrentNode.
  439. //
  440. //   Typically, SetCurrentNode (or SetCurrentNodeEx) is called first to set
  441. //   pList->pCurrentNode.  Also, any addtional memory associated with this
  442. //   node should be freed first before calling this function.
  443. // ************************************************************************
  444. BOOL
  445. DeleteCurrentNode( PLIST pList )
  446. {
  447.   PNODE pOldCurrentNode;
  448.  
  449.   if( pList->pCurrentNode != NULL ) {
  450.     pOldCurrentNode = pList->pCurrentNode;
  451.  
  452.     if( pOldCurrentNode == pList->pFirstNode ) {
  453.       pList->pFirstNode   = pOldCurrentNode->pRightLink;
  454.       pList->pCurrentNode = pOldCurrentNode->pRightLink;
  455.     }
  456.     else {
  457.       pOldCurrentNode->pLeftLink->pRightLink = pOldCurrentNode->pRightLink;
  458.       pList->pCurrentNode = pOldCurrentNode->pLeftLink;
  459.     }
  460.  
  461.     if( pOldCurrentNode == pList->pLastNode )
  462.       pList->pLastNode = pOldCurrentNode->pLeftLink;
  463.     else
  464.       pOldCurrentNode->pRightLink->pLeftLink = pOldCurrentNode->pLeftLink;
  465.  
  466.     DestroyNode( pOldCurrentNode );
  467.     pList->ListError = LIST_NO_ERROR;
  468.     return( TRUE );
  469.   }
  470.   pList->ListError = LIST_NO_ERROR;
  471.  
  472.   return( TRUE );
  473. }
  474.  
  475.  
  476. // ************************************************************************
  477. // FUNCTION : DestroyNode( PNODE pNode )
  478. // PURPOSE  : deallocates a node
  479. // COMMENTS :
  480. // ************************************************************************
  481. BOOL
  482. DestroyNode( PNODE pNode )
  483. {
  484.   free( pNode );
  485.  
  486.   return( TRUE );
  487. }
  488.  
  489.  
  490. // ************************************************************************
  491. // FUNCTION : DestroyList( PLIST pList )
  492. // PURPOSE  : deallocates a list, does not free any nodes, if present
  493. // COMMENTS :
  494. // ************************************************************************
  495. BOOL
  496. DestroyList( PLIST pList )
  497. {
  498.   free( pList );
  499.   pList->ListError = LIST_NO_ERROR;
  500.  
  501.   return( TRUE );
  502. }
  503.  
  504.  
  505. // ************************************************************************
  506. // FUNCTION : GetListError( PLIST pList )
  507. // PURPOSE  : get the last linked list error
  508. // COMMENTS :
  509. // ************************************************************************
  510. int
  511. GetListError( PLIST pList )
  512. {
  513.   return( pList->ListError );
  514. }
  515.