home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 2 / crawlyvol2.bin / program / c / memdebug / memfree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-08  |  19.6 KB  |  721 lines
  1.  
  2.  
  3. /********************************************************************************/
  4. /* REMARK: set tab width to 4 spaces for best format                            */
  5. /********************************************************************************/
  6. /********************************************************************************/
  7. /*                                                                                 */
  8. /* Copyright (C) 1992    All Rights Reserved                                        */
  9. /* Centre de Recherche Public Henri Tudor (CRP-HT)                                */
  10. /* 6, rue Coudenhove-Kalergi                                                    */
  11. /* L1359 Luxembourg-Kirchberg                                                    */
  12. /*                                                                                 */
  13. /* Author            : Schmit Rene                                                */
  14. /* Internet            : Rene.Schmit@crpht.lu                                        */
  15. /* Creation Date    : Friday, October 02 1992                                     */
  16. /* File name        : AVL_TREE.C                                                */
  17. /* Project            : Library                                                    */
  18. /*                                                                                 */
  19. /* This software may be copied, distributed, ported and modified in source or    */
  20. /* object format as long as :                                                    */
  21. /*                                                                                 */
  22. /*     1) No distribution for commercial purposes is made.                            */
  23. /*     2) No third-party copyrights (such as runtime licenses) are involved        */
  24. /*     3) This copyright notice is not removed or changed.                            */
  25. /*                                                                                 */
  26. /* No responsibility is assumed for any damages that may result                 */
  27. /* from any defect in this software.                                            */
  28. /*                                                                                 */
  29. /********************************************************************************/
  30. /********************************************************************************/
  31.  
  32. /*
  33.     Main file of the AVL_TREE library
  34. */
  35.  
  36. #include <ctype.h>
  37. #include <limits.h>
  38. #include <stdlib.h>
  39. #include <stdio.h>
  40. #include <string.h>
  41. #include <time.h>
  42.  
  43. #include "memfree.h"
  44.  
  45.  
  46. /********************************************************************************/
  47. /******************************* Constants **************************************/
  48. /********************************************************************************/
  49.  
  50. #define true 1
  51. #define false 0
  52.  
  53. #ifndef NULL
  54. #define NULL 0
  55. #endif
  56.  
  57.  
  58. /********************************************************************************/
  59. /******************************* Data Types *************************************/
  60. /********************************************************************************/
  61.  
  62. enum t_Balance 
  63. {
  64.     c_Left,
  65.     c_Equal,
  66.     c_Right
  67. };
  68.  
  69. typedef enum t_Balance t_Balance;
  70.  
  71. /********************************************************************************/
  72.  
  73. struct t_NotFreeBlockTreeNode 
  74. {
  75.     t_BlockDescriptor*                    f_Element;
  76.     t_Balance                        f_Balance;
  77.     struct t_NotFreeBlockTreeNode *    f_Left;
  78.     struct t_NotFreeBlockTreeNode *    f_Right;
  79. };
  80.  
  81. typedef struct t_NotFreeBlockTreeNode t_NotFreeBlockTreeNode;
  82.  
  83. /********************************************************************************/
  84. /**************************** File global data **********************************/
  85. /********************************************************************************/
  86.  
  87. static    t_NotFreeBlockTreeNode      *    g_HelpNotFreeBlockNode;
  88.  
  89. static    t_NotFreeBlockTreeNode      *    g_SpareNotFreeBlockNode;
  90.  
  91. static    t_NotFreeBlockTreeNode      * g_Root;
  92.  
  93. /********************************************************************************/
  94. /*********************** Local function prototypes ******************************/
  95. /********************************************************************************/
  96.  
  97. static    int                         check_NotFreeBlockEmpty          (    t_NotFreeBlockTreeNode  *    p_Tree);
  98.  
  99. static    int                            NotFreeBlock_max                     (    int p_x,
  100.                                                                     int p_y
  101.                                                                   );
  102.  
  103. static    t_NotFreeBlockTreeNode      *    balance_NotFreeBlockLeft          (    t_NotFreeBlockTreeNode  *    p_Tree,
  104.                                                                     int                   *    p_Higher
  105.                                                                   );
  106. static    t_NotFreeBlockTreeNode      *    balance_NotFreeBlockRight           (    t_NotFreeBlockTreeNode  *    p_Tree,
  107.                                                                     int                   * p_Higher
  108.                                                                   );
  109. static    t_NotFreeBlockTreeNode      *    eliminate_NotFreeBlock          (    t_NotFreeBlockTreeNode  * p_Tree,
  110.                                                                     int                      * p_Higher
  111.                                                                   );
  112.  
  113. static t_NotFreeBlockTreeNode          *    insert_NotFreeBlock_into_Tree1  (    t_NotFreeBlockTreeNode  *    p_Tree,
  114.                                                                     t_BlockDescriptor*            p_data,
  115.                                                                     int *p_Higher
  116.                                                                   );
  117.  
  118. static int                            search_NotFreeBlock_in_Tree1      (    t_NotFreeBlockTreeNode  * p_Tree,
  119.                                                                     t_BlockDescriptor*          * p_data
  120.                                                                   );
  121.  
  122. static t_NotFreeBlockTreeNode          *    remove_NotFreeBlock_from_Tree1  (    t_NotFreeBlockTreeNode  *    p_Tree,
  123.                                                                     t_BlockDescriptor*            p_data,
  124.                                                                     int                      *    p_Higher
  125.                                                                   );
  126.  
  127. static void                         delete_NotFreeBlockTree1          (    t_NotFreeBlockTreeNode **    p_Tree);
  128. static int                            get_Height_of_NotFreeBlockTree1 (    t_NotFreeBlockTreeNode  *    p_Tree);
  129. static int                            get_Card_of_NotFreeBlockTree1      (    t_NotFreeBlockTreeNode  *    p_Tree);
  130.  
  131.  
  132. static void                            free_NotFreeBlockTree1      (    t_NotFreeBlockTreeNode      *    p_Tree);
  133.  
  134. static void                            print_NotFreeBlockTree1      (    t_NotFreeBlockTreeNode      *    p_Tree);
  135.  
  136. /********************************************************************************/
  137. /**************************** Local functions ***********************************/
  138. /********************************************************************************/
  139.  
  140. static int check_NotFreeBlockEmpty(t_NotFreeBlockTreeNode *p_Tree)
  141. {
  142.     if (p_Tree == NULL)
  143.         return (true);
  144.     else
  145.         return (false);
  146. }
  147.  
  148.  
  149. /********************************************************************************/
  150.  
  151. static int NotFreeBlock_max      (    int p_x,
  152.                                 int p_y
  153.                               )
  154.  
  155. {
  156.     if (p_x > p_y)
  157.         return p_x;
  158.     else
  159.         return p_y;
  160. }
  161.  
  162. /********************************************************************************/
  163.  
  164. static t_NotFreeBlockTreeNode      *    insert_NotFreeBlock_into_Tree1  (    t_NotFreeBlockTreeNode  *    p_Tree,
  165.                                                                 t_BlockDescriptor*            p_data,
  166.                                                                 int                   * p_Higher
  167.                                                               )
  168.  
  169. {
  170. t_NotFreeBlockTreeNode  *    l_Temp1;
  171. t_NotFreeBlockTreeNode  *    l_Temp2;
  172.  
  173.     if (check_NotFreeBlockEmpty(p_Tree))
  174.     {
  175.         p_Tree = (t_NotFreeBlockTreeNode  *) malloc(sizeof(t_NotFreeBlockTreeNode));
  176.         if (p_Tree == NULL)
  177.         {
  178.             p_Tree = g_SpareNotFreeBlockNode;
  179.             g_SpareNotFreeBlockNode = NULL;
  180.         }
  181.         if (p_Tree == NULL)
  182.             
  183.         {
  184.             treat_InternalError(3);    
  185.             return (NULL);                                    
  186.         }
  187.         
  188.         p_Tree->f_Element    = p_data ;
  189.         p_Tree->f_Left        = NULL;
  190.         p_Tree->f_Right        = NULL;
  191.         p_Tree->f_Balance    = c_Equal;
  192.         *p_Higher            = true;
  193.     }
  194.     else
  195.     {
  196.         if (compare_BlockPointers(p_data,p_Tree->f_Element) < 0)
  197.         {
  198.             p_Tree->f_Left = insert_NotFreeBlock_into_Tree1(p_Tree->f_Left,p_data,p_Higher);
  199.             if (*p_Higher)
  200.                 switch (p_Tree->f_Balance)
  201.                 {
  202.                     case c_Left      : l_Temp1 = p_Tree->f_Left;
  203.                                     if(l_Temp1->f_Balance == c_Left)
  204.                                     {
  205.                                         p_Tree ->f_Left        = l_Temp1->f_Right;
  206.                                         l_Temp1->f_Right    = p_Tree;
  207.                                         p_Tree ->f_Balance    = c_Equal;
  208.                                         p_Tree                = l_Temp1;
  209.                                     }
  210.                                     else
  211.                                     {
  212.                                         l_Temp2                = l_Temp1->f_Right;
  213.                                         l_Temp1->f_Right    = l_Temp2->f_Left;
  214.                                         l_Temp2->f_Left        = l_Temp1;
  215.                                         p_Tree ->f_Left        = l_Temp2->f_Right;
  216.                                         l_Temp2->f_Right    = p_Tree;
  217.                                         
  218.                                         if (l_Temp2->f_Balance == c_Left)
  219.                                             p_Tree->f_Balance = c_Right;
  220.                                         else
  221.                                             p_Tree->f_Balance = c_Equal;
  222.                                             
  223.                                         if (l_Temp2->f_Balance == c_Right)
  224.                                             l_Temp1->f_Balance = c_Left;
  225.                                         else
  226.                                             l_Temp1->f_Balance = c_Equal;
  227.                                             
  228.                                         p_Tree = l_Temp2;
  229.                                     }
  230.                                     p_Tree->f_Balance    = c_Equal;
  231.                                     *p_Higher            = false;
  232.                                     break;
  233.                                         
  234.                     case c_Equal  : p_Tree->f_Balance    = c_Left;
  235.                                     break;
  236.                                         
  237.                     case c_Right  : p_Tree->f_Balance    = c_Equal;
  238.                                     *p_Higher            = false;
  239.                                     break;
  240.                 }
  241.         }
  242.         else
  243.             if (compare_BlockPointers(p_data,p_Tree->f_Element) > 0)
  244.             {
  245.                 p_Tree->f_Right = insert_NotFreeBlock_into_Tree1(p_Tree->f_Right,p_data,p_Higher);
  246.                 if (*p_Higher)
  247.                     switch (p_Tree->f_Balance)
  248.                     {
  249.                         case c_Left      : p_Tree->f_Balance    = c_Equal;
  250.                                         *p_Higher            = false;
  251.                                         break;
  252.  
  253.                         case c_Equal  : p_Tree->f_Balance    = c_Right;
  254.                                         break;
  255.                                             
  256.                         case c_Right  : l_Temp1 = p_Tree->f_Right;
  257.                                         if(l_Temp1->f_Balance == c_Right)
  258.                                         {
  259.                                             p_Tree->f_Right        = l_Temp1->f_Left;
  260.                                             l_Temp1->f_Left        = p_Tree;
  261.                                             p_Tree->f_Balance    = c_Equal;
  262.                                             p_Tree                = l_Temp1;
  263.                                         }
  264.                                         else
  265.                                         {
  266.                                             l_Temp2                = l_Temp1->f_Left;
  267.                                             l_Temp1->f_Left        = l_Temp2->f_Right;
  268.                                             l_Temp2->f_Right    = l_Temp1;
  269.                                             p_Tree ->f_Right    = l_Temp2->f_Left;
  270.                                             l_Temp2->f_Left        = p_Tree;
  271.                                             
  272.                                             if (l_Temp2->f_Balance == c_Right)
  273.                                                 p_Tree->f_Balance =    c_Left;
  274.                                             else
  275.                                                 p_Tree->f_Balance =    c_Equal;
  276.                                             
  277.                                             if (l_Temp2->f_Balance == c_Left)
  278.                                                 l_Temp1->f_Balance = c_Right;
  279.                                             else
  280.                                                 l_Temp1->f_Balance = c_Equal;
  281.                                                 
  282.                                             p_Tree = l_Temp2;
  283.                                         }
  284.                                         p_Tree->f_Balance= c_Equal;
  285.                                         *p_Higher = false;
  286.                                         break;
  287.                                             
  288.                     }
  289.         }
  290.         else
  291.         {
  292.             *p_Higher = false;
  293.         
  294.             treat_InternalError(1);
  295.             return (p_Tree) ;                                
  296.         
  297.         }
  298.     }
  299.     return (p_Tree);
  300. }
  301.  
  302. /********************************************************************************/
  303.  
  304. static t_NotFreeBlockTreeNode      *    balance_NotFreeBlockRight    (    t_NotFreeBlockTreeNode  * p_Tree,
  305.                                                             int                      * p_Higher
  306.                                                         )
  307.                                             
  308. {
  309. t_NotFreeBlockTreeNode  *    l_Temp1;
  310. t_NotFreeBlockTreeNode  *    l_Temp2;
  311. t_Balance                l_Balance1;
  312. t_Balance                l_Balance2;
  313.  
  314.     switch(p_Tree->f_Balance)
  315.     {
  316.         case c_Left          :    p_Tree->f_Balance    = c_Equal;
  317.                             break ;
  318.                             
  319.         case c_Equal      :    p_Tree->f_Balance    = c_Right;
  320.                             * p_Higher            = false;
  321.                             break ;
  322.                             
  323.         case c_Right      :    l_Temp1        = p_Tree->f_Right;
  324.                             l_Balance1    = l_Temp1->f_Balance;
  325.                             if (l_Balance1 >= c_Equal)
  326.                             {
  327.                                 p_Tree->f_Right = l_Temp1->f_Left;
  328.                                 l_Temp1->f_Left = p_Tree;
  329.                                 
  330.                                 if (l_Balance1 == c_Equal)
  331.                                 {
  332.                                     p_Tree->f_Balance    = c_Right;
  333.                                     l_Temp1->f_Balance    = c_Left;
  334.                                     *p_Higher            = false;
  335.                                 }
  336.                                 else
  337.                                 {
  338.                                     p_Tree->f_Balance    = c_Equal;
  339.                                     l_Temp1->f_Balance    = c_Equal;
  340.                                 }
  341.                                 p_Tree = l_Temp1;
  342.                             }
  343.                             else
  344.                             {
  345.                                 l_Temp2                = l_Temp1->f_Left;
  346.                                 l_Balance2            = l_Temp2->f_Balance;
  347.                                 l_Temp1->f_Left        = l_Temp2->f_Right;
  348.                                 l_Temp2->f_Right    = l_Temp1;
  349.                                 p_Tree ->f_Right    = l_Temp2->f_Left;
  350.                                 l_Temp2->f_Left        = p_Tree;
  351.                                 
  352.                                 if (l_Balance2 == c_Right)
  353.                                     p_Tree ->f_Balance    = c_Left;
  354.                                 else
  355.                                     p_Tree ->f_Balance    = c_Equal;
  356.                                 
  357.                                 if (l_Balance2 == c_Left )
  358.                                     l_Temp1->f_Balance    = c_Right;
  359.                                 else
  360.                                     l_Temp1->f_Balance    = c_Equal;
  361.                                 
  362.                                 p_Tree                = l_Temp2;
  363.                                 l_Temp2->f_Balance    = c_Equal;
  364.                             }
  365.                             break ;
  366.     }
  367.     return(p_Tree);
  368. }
  369.  
  370. /********************************************************************************/
  371.  
  372. static t_NotFreeBlockTreeNode      *    balance_NotFreeBlockLeft    (    t_NotFreeBlockTreeNode  * p_Tree,
  373.                                                             int                      * p_Higher
  374.                                                         )
  375.                                             
  376. {
  377. t_NotFreeBlockTreeNode  *    l_Temp1;
  378. t_NotFreeBlockTreeNode  *    l_Temp2;
  379. t_Balance                l_Balance1;
  380. t_Balance                l_Balance2;
  381.  
  382.     switch(p_Tree->f_Balance)
  383.     {
  384.         case c_Left          :    l_Temp1        = p_Tree->f_Left;
  385.                             l_Balance1    = l_Temp1->f_Balance;
  386.                             if (l_Balance1 <= c_Equal)
  387.                             {
  388.                                 p_Tree->f_Left        = l_Temp1->f_Right;
  389.                                 l_Temp1->f_Right    = p_Tree;
  390.                                 
  391.                                 if (l_Balance1 == c_Equal)
  392.                                 {
  393.                                     p_Tree->f_Balance    = c_Left;
  394.                                     l_Temp1->f_Balance    = c_Right;
  395.                                     *p_Higher            = false;
  396.                                 }
  397.                                 else
  398.                                 {
  399.                                     p_Tree->f_Balance    = c_Equal;
  400.                                     l_Temp1->f_Balance    = c_Equal;
  401.                                 }
  402.                                 p_Tree = l_Temp1;
  403.                             }
  404.                             else
  405.                             {
  406.                                 l_Temp2                = l_Temp1->f_Right;
  407.                                 l_Balance2            = l_Temp2->f_Balance;
  408.                                 l_Temp1->f_Right    = l_Temp2->f_Left;
  409.                                 l_Temp2->f_Left        = l_Temp1;
  410.                                 p_Tree ->f_Left        = l_Temp2->f_Right;
  411.                                 l_Temp2->f_Right    = p_Tree;
  412.                                 
  413.                                 if (l_Balance2 == c_Left) 
  414.                                     p_Tree ->f_Balance    = c_Right;
  415.                                 else
  416.                                     p_Tree ->f_Balance    = c_Equal;
  417.                                     
  418.                                 if (l_Balance2 == c_Right)
  419.                                     l_Temp1->f_Balance    = c_Left;
  420.                                 else
  421.                                     l_Temp1->f_Balance    = c_Equal;
  422.                                 
  423.                                 p_Tree                = l_Temp2;
  424.                                 l_Temp2->f_Balance    = c_Equal;
  425.                             }
  426.                             break ;
  427.  
  428.         case c_Equal      :    p_Tree->f_Balance    = c_Left;
  429.                             * p_Higher            = false;
  430.                             break ;
  431.                             
  432.         case c_Right      :    p_Tree->f_Balance    = c_Equal;
  433.                             break ;
  434.     }
  435.     return(p_Tree);
  436. }
  437.  
  438.  
  439. /********************************************************************************/
  440.  
  441. static    t_NotFreeBlockTreeNode      *    eliminate_NotFreeBlock      (    t_NotFreeBlockTreeNode  * p_Tree,
  442.                                                                 int                      * p_Higher
  443.                                                               )
  444.                                                                   
  445. {
  446.     if (!(check_NotFreeBlockEmpty(p_Tree->f_Right)))
  447.     {
  448.         p_Tree->f_Right = eliminate_NotFreeBlock(p_Tree->f_Right,p_Higher);
  449.         if (*p_Higher)
  450.             p_Tree = balance_NotFreeBlockLeft(p_Tree,p_Higher);
  451.     }
  452.     else
  453.     {
  454.     t_NotFreeBlockTreeNode      * l_ObsoleteNode;
  455.     
  456.         l_ObsoleteNode = p_Tree;
  457.         g_HelpNotFreeBlockNode->f_Element = p_Tree->f_Element;
  458.         p_Tree                            = p_Tree->f_Left;
  459.         free(l_ObsoleteNode);
  460.         *p_Higher                        = true;
  461.     }
  462.     return p_Tree;
  463. }
  464.  
  465. /********************************************************************************/
  466.  
  467. static t_NotFreeBlockTreeNode  *    remove_NotFreeBlock_from_Tree1  (    t_NotFreeBlockTreeNode  *    p_Tree,
  468.                                                                 t_BlockDescriptor*            p_data,
  469.                                                                 int                      *    p_Higher
  470.                                                               )
  471.  
  472. {
  473.     if (check_NotFreeBlockEmpty(p_Tree))
  474.     {
  475.         *p_Higher = false;
  476.             
  477.                 treat_InternalError(2);
  478.                 return (p_Tree);                                    
  479.             
  480.     }
  481.     else
  482.         if (compare_BlockPointers(p_data,p_Tree->f_Element) < 0)
  483.         {
  484.             p_Tree->f_Left = remove_NotFreeBlock_from_Tree1(p_Tree->f_Left,p_data,p_Higher);
  485.             if (*p_Higher)
  486.                 p_Tree = balance_NotFreeBlockRight(p_Tree,p_Higher);
  487.         }
  488.         else
  489.             if (compare_BlockPointers(p_data,p_Tree->f_Element) > 0)
  490.             {
  491.                 p_Tree->f_Right = remove_NotFreeBlock_from_Tree1(p_Tree->f_Right,p_data,p_Higher);
  492.                 if (*p_Higher)
  493.                     p_Tree = balance_NotFreeBlockLeft(p_Tree,p_Higher);
  494.             }
  495.             else
  496.             {
  497.                 g_HelpNotFreeBlockNode = p_Tree;
  498.                 if (check_NotFreeBlockEmpty(g_HelpNotFreeBlockNode->f_Right))
  499.                 {
  500.                     p_Tree        = g_HelpNotFreeBlockNode->f_Left;
  501.                     free(g_HelpNotFreeBlockNode);
  502.                     *p_Higher    = true;
  503.                 }
  504.                 else
  505.                     if (check_NotFreeBlockEmpty(g_HelpNotFreeBlockNode->f_Left))
  506.                     {
  507.                         p_Tree        = g_HelpNotFreeBlockNode->f_Right;
  508.                         free(g_HelpNotFreeBlockNode);
  509.                         *p_Higher    = true;
  510.                     }
  511.                     else
  512.                     {
  513.                         g_HelpNotFreeBlockNode->f_Left = eliminate_NotFreeBlock(g_HelpNotFreeBlockNode->f_Left,p_Higher);
  514.                         if (*p_Higher)
  515.                             p_Tree = balance_NotFreeBlockRight(p_Tree,p_Higher);
  516.                     }
  517.             }
  518.     return p_Tree;
  519. }
  520.  
  521. /********************************************************************************/
  522.  
  523. static    int    search_NotFreeBlock_in_Tree1      (    t_NotFreeBlockTreeNode  * p_Tree,
  524.                                             t_BlockDescriptor*          * p_data)
  525.  
  526. {
  527.     if (!(check_NotFreeBlockEmpty(p_Tree)))
  528.         if (compare_BlockPointers(* p_data,p_Tree->f_Element) < 0)
  529.             return (search_NotFreeBlock_in_Tree1(p_Tree->f_Left,p_data));
  530.         else
  531.             if (compare_BlockPointers(* p_data,p_Tree->f_Element) > 0)
  532.                 return (search_NotFreeBlock_in_Tree1(p_Tree->f_Right,p_data));
  533.             else
  534.             {
  535.                 *p_data = p_Tree->f_Element;
  536.                 return (true);
  537.             }
  538.     else
  539.         return (false);
  540. }
  541.  
  542. /********************************************************************************/
  543.  
  544. static void delete_NotFreeBlockTree1    (t_NotFreeBlockTreeNode      **    p_Tree)
  545.  
  546. {
  547.     if (!(check_NotFreeBlockEmpty(*p_Tree)))
  548.     {
  549.         delete_NotFreeBlockTree1(&((*p_Tree)->f_Left));
  550.         delete_NotFreeBlockTree1(&((*p_Tree)->f_Right));
  551.         free(*p_Tree);
  552.         *p_Tree = NULL;
  553.     }
  554. }
  555.  
  556. /********************************************************************************/
  557.  
  558. static    int get_Height_of_NotFreeBlockTree1(t_NotFreeBlockTreeNode *p_Tree)
  559.  
  560. {
  561.     if (check_NotFreeBlockEmpty(p_Tree))
  562.         return 0;
  563.     else
  564.     {
  565.         return    (1 + NotFreeBlock_max(    get_Height_of_NotFreeBlockTree1(p_Tree->f_Left),
  566.                                         get_Height_of_NotFreeBlockTree1(p_Tree->f_Right)
  567.                                     )
  568.                 );
  569.     }
  570. }
  571.  
  572. /********************************************************************************/
  573.  
  574. static    int get_Card_of_NotFreeBlockTree1      (    t_NotFreeBlockTreeNode  *    p_Tree)
  575.  
  576. {
  577.     if (!(check_NotFreeBlockEmpty(p_Tree)))
  578.         return    (    1
  579.                 +    get_Card_of_NotFreeBlockTree1(p_Tree->f_Left)
  580.                 +    get_Card_of_NotFreeBlockTree1(p_Tree->f_Right)
  581.                 );
  582.     else
  583.         return 0;
  584. }
  585.  
  586.  
  587.  
  588. /********************************************************************************/
  589.     
  590. static void    free_NotFreeBlockTree1      (t_NotFreeBlockTreeNode  *    p_Tree)
  591.  
  592. {
  593.     if (!(check_NotFreeBlockEmpty(p_Tree)))
  594.     {
  595.         free_NotFreeBlockTree1(p_Tree->f_Left);
  596.  
  597.         delete_Descriptor(p_Tree->f_Element);
  598.     
  599.         free_NotFreeBlockTree1(p_Tree->f_Right);
  600.     }
  601. }
  602.  
  603.  
  604. /********************************************************************************/
  605.     
  606. static void    print_NotFreeBlockTree1      (t_NotFreeBlockTreeNode  *    p_Tree)
  607.  
  608. {
  609.     if (!(check_NotFreeBlockEmpty(p_Tree)))
  610.     {
  611.         print_NotFreeBlockTree1(p_Tree->f_Left);
  612.  
  613.         print_NotFreeBlock(p_Tree->f_Element);
  614.     
  615.         print_NotFreeBlockTree1(p_Tree->f_Right);
  616.     }
  617. }
  618.  
  619.  
  620. /********************************************************************************/
  621. /**************************** Global functions **********************************/
  622. /********************************************************************************/
  623.  
  624. void    create_NotFreeBlockTree ( void )
  625.  
  626. {
  627.     g_SpareNotFreeBlockNode    = (t_NotFreeBlockTreeNode  *)        malloc(sizeof(t_NotFreeBlockTreeNode    ));
  628.     g_Root                    = NULL;
  629. }
  630.  
  631. /********************************************************************************/
  632.  
  633. void    insert_NotFreeBlock_into_Tree      (    t_BlockDescriptor*            p_data )
  634.  
  635. {
  636. int l_Dummy = false;
  637.     g_Root = insert_NotFreeBlock_into_Tree1 (g_Root,p_data,&l_Dummy);
  638. }
  639.  
  640. /********************************************************************************/
  641.  
  642. int    search_NotFreeBlock_in_Tree      (    t_BlockDescriptor*          * p_data)
  643.  
  644. {
  645.     return (search_NotFreeBlock_in_Tree1(g_Root,p_data));
  646. }
  647.  
  648. /********************************************************************************/
  649.  
  650. void    remove_NotFreeBlock_from_Tree      (t_BlockDescriptor*        p_data )
  651.  
  652. {
  653. int l_Dummy = false;
  654.     g_Root = remove_NotFreeBlock_from_Tree1(g_Root,p_data,&l_Dummy);
  655.     if (g_SpareNotFreeBlockNode == NULL)
  656.         g_SpareNotFreeBlockNode =  (t_NotFreeBlockTreeNode  *) malloc(sizeof(t_NotFreeBlockTreeNode));
  657. }
  658.  
  659. /********************************************************************************/
  660.  
  661. void delete_NotFreeBlockTree    ( void )
  662.  
  663. {
  664.     if (g_SpareNotFreeBlockNode)
  665.     {
  666.         free(g_SpareNotFreeBlockNode);
  667.         g_SpareNotFreeBlockNode = NULL;
  668.     }
  669.     delete_NotFreeBlockTree1(&g_Root);
  670. }
  671.  
  672. /********************************************************************************/
  673.  
  674. int     check_NotFreeBlockFull        ( void )
  675.  
  676. {
  677.     if (g_SpareNotFreeBlockNode == NULL)
  678.         g_SpareNotFreeBlockNode =  (t_NotFreeBlockTreeNode  *) malloc(sizeof(t_NotFreeBlockTreeNode));
  679.     return (g_SpareNotFreeBlockNode == NULL);
  680. }
  681.  
  682. /********************************************************************************/
  683.  
  684. int get_Height_of_NotFreeBlockTree    ( void )
  685.  
  686. {
  687.     return (get_Height_of_NotFreeBlockTree1    (g_Root));
  688. }
  689.  
  690. /********************************************************************************/
  691.  
  692. int get_Card_of_NotFreeBlockTree        ( void )
  693.  
  694. {
  695.     return (get_Card_of_NotFreeBlockTree1        (g_Root));
  696. }
  697.  
  698. /********************************************************************************/
  699.  
  700.  
  701.     
  702. void    free_NotFreeBlockTree      ( void )
  703.  
  704. {
  705.     free_NotFreeBlockTree1(g_Root);
  706. }
  707.  
  708. /********************************************************************************/
  709.  
  710.     
  711. void    print_NotFreeBlockTree      ( void )
  712.  
  713. {
  714.     print_NotFreeBlockTree1(g_Root);
  715. }
  716.  
  717. /********************************************************************************/
  718.  
  719. /********************************************************************************/
  720.  
  721.