/********************************************************************************/ /* REMARK: set tab width to 4 spaces for best format */ /********************************************************************************/ /********************************************************************************/ /* */ /* Copyright (C) 1992 All Rights Reserved */ /* Centre de Recherche Public Henri Tudor (CRP-HT) */ /* 6, rue Coudenhove-Kalergi */ /* L1359 Luxembourg-Kirchberg */ /* */ /* Author : Schmit Rene */ /* Internet : Rene.Schmit@crpht.lu */ /* Creation Date : Friday, October 02 1992 */ /* File name : AVL_TREE.C */ /* Project : Library */ /* */ /* This software may be copied, distributed, ported and modified in source or */ /* object format as long as : */ /* */ /* 1) No distribution for commercial purposes is made. */ /* 2) No third-party copyrights (such as runtime licenses) are involved */ /* 3) This copyright notice is not removed or changed. */ /* */ /* No responsibility is assumed for any damages that may result */ /* from any defect in this software. */ /* */ /********************************************************************************/ /********************************************************************************/ /* Main file of the AVL_TREE library */ #include #include #include #include #include #include #include "memfree.h" /********************************************************************************/ /******************************* Constants **************************************/ /********************************************************************************/ #define true 1 #define false 0 #ifndef NULL #define NULL 0 #endif /********************************************************************************/ /******************************* Data Types *************************************/ /********************************************************************************/ enum t_Balance { c_Left, c_Equal, c_Right }; typedef enum t_Balance t_Balance; /********************************************************************************/ struct t_NotFreeBlockTreeNode { t_BlockDescriptor* f_Element; t_Balance f_Balance; struct t_NotFreeBlockTreeNode * f_Left; struct t_NotFreeBlockTreeNode * f_Right; }; typedef struct t_NotFreeBlockTreeNode t_NotFreeBlockTreeNode; /********************************************************************************/ /**************************** File global data **********************************/ /********************************************************************************/ static t_NotFreeBlockTreeNode * g_HelpNotFreeBlockNode; static t_NotFreeBlockTreeNode * g_SpareNotFreeBlockNode; static t_NotFreeBlockTreeNode * g_Root; /********************************************************************************/ /*********************** Local function prototypes ******************************/ /********************************************************************************/ static int check_NotFreeBlockEmpty ( t_NotFreeBlockTreeNode * p_Tree); static int NotFreeBlock_max ( int p_x, int p_y ); static t_NotFreeBlockTreeNode * balance_NotFreeBlockLeft ( t_NotFreeBlockTreeNode * p_Tree, int * p_Higher ); static t_NotFreeBlockTreeNode * balance_NotFreeBlockRight ( t_NotFreeBlockTreeNode * p_Tree, int * p_Higher ); static t_NotFreeBlockTreeNode * eliminate_NotFreeBlock ( t_NotFreeBlockTreeNode * p_Tree, int * p_Higher ); static t_NotFreeBlockTreeNode * insert_NotFreeBlock_into_Tree1 ( t_NotFreeBlockTreeNode * p_Tree, t_BlockDescriptor* p_data, int *p_Higher ); static int search_NotFreeBlock_in_Tree1 ( t_NotFreeBlockTreeNode * p_Tree, t_BlockDescriptor* * p_data ); static t_NotFreeBlockTreeNode * remove_NotFreeBlock_from_Tree1 ( t_NotFreeBlockTreeNode * p_Tree, t_BlockDescriptor* p_data, int * p_Higher ); static void delete_NotFreeBlockTree1 ( t_NotFreeBlockTreeNode ** p_Tree); static int get_Height_of_NotFreeBlockTree1 ( t_NotFreeBlockTreeNode * p_Tree); static int get_Card_of_NotFreeBlockTree1 ( t_NotFreeBlockTreeNode * p_Tree); static void free_NotFreeBlockTree1 ( t_NotFreeBlockTreeNode * p_Tree); static void print_NotFreeBlockTree1 ( t_NotFreeBlockTreeNode * p_Tree); /********************************************************************************/ /**************************** Local functions ***********************************/ /********************************************************************************/ static int check_NotFreeBlockEmpty(t_NotFreeBlockTreeNode *p_Tree) { if (p_Tree == NULL) return (true); else return (false); } /********************************************************************************/ static int NotFreeBlock_max ( int p_x, int p_y ) { if (p_x > p_y) return p_x; else return p_y; } /********************************************************************************/ static t_NotFreeBlockTreeNode * insert_NotFreeBlock_into_Tree1 ( t_NotFreeBlockTreeNode * p_Tree, t_BlockDescriptor* p_data, int * p_Higher ) { t_NotFreeBlockTreeNode * l_Temp1; t_NotFreeBlockTreeNode * l_Temp2; if (check_NotFreeBlockEmpty(p_Tree)) { p_Tree = (t_NotFreeBlockTreeNode *) malloc(sizeof(t_NotFreeBlockTreeNode)); if (p_Tree == NULL) { p_Tree = g_SpareNotFreeBlockNode; g_SpareNotFreeBlockNode = NULL; } if (p_Tree == NULL) { treat_InternalError(3); return (NULL); } p_Tree->f_Element = p_data ; p_Tree->f_Left = NULL; p_Tree->f_Right = NULL; p_Tree->f_Balance = c_Equal; *p_Higher = true; } else { if (compare_BlockPointers(p_data,p_Tree->f_Element) < 0) { p_Tree->f_Left = insert_NotFreeBlock_into_Tree1(p_Tree->f_Left,p_data,p_Higher); if (*p_Higher) switch (p_Tree->f_Balance) { case c_Left : l_Temp1 = p_Tree->f_Left; if(l_Temp1->f_Balance == c_Left) { p_Tree ->f_Left = l_Temp1->f_Right; l_Temp1->f_Right = p_Tree; p_Tree ->f_Balance = c_Equal; p_Tree = l_Temp1; } else { l_Temp2 = l_Temp1->f_Right; l_Temp1->f_Right = l_Temp2->f_Left; l_Temp2->f_Left = l_Temp1; p_Tree ->f_Left = l_Temp2->f_Right; l_Temp2->f_Right = p_Tree; if (l_Temp2->f_Balance == c_Left) p_Tree->f_Balance = c_Right; else p_Tree->f_Balance = c_Equal; if (l_Temp2->f_Balance == c_Right) l_Temp1->f_Balance = c_Left; else l_Temp1->f_Balance = c_Equal; p_Tree = l_Temp2; } p_Tree->f_Balance = c_Equal; *p_Higher = false; break; case c_Equal : p_Tree->f_Balance = c_Left; break; case c_Right : p_Tree->f_Balance = c_Equal; *p_Higher = false; break; } } else if (compare_BlockPointers(p_data,p_Tree->f_Element) > 0) { p_Tree->f_Right = insert_NotFreeBlock_into_Tree1(p_Tree->f_Right,p_data,p_Higher); if (*p_Higher) switch (p_Tree->f_Balance) { case c_Left : p_Tree->f_Balance = c_Equal; *p_Higher = false; break; case c_Equal : p_Tree->f_Balance = c_Right; break; case c_Right : l_Temp1 = p_Tree->f_Right; if(l_Temp1->f_Balance == c_Right) { p_Tree->f_Right = l_Temp1->f_Left; l_Temp1->f_Left = p_Tree; p_Tree->f_Balance = c_Equal; p_Tree = l_Temp1; } else { l_Temp2 = l_Temp1->f_Left; l_Temp1->f_Left = l_Temp2->f_Right; l_Temp2->f_Right = l_Temp1; p_Tree ->f_Right = l_Temp2->f_Left; l_Temp2->f_Left = p_Tree; if (l_Temp2->f_Balance == c_Right) p_Tree->f_Balance = c_Left; else p_Tree->f_Balance = c_Equal; if (l_Temp2->f_Balance == c_Left) l_Temp1->f_Balance = c_Right; else l_Temp1->f_Balance = c_Equal; p_Tree = l_Temp2; } p_Tree->f_Balance= c_Equal; *p_Higher = false; break; } } else { *p_Higher = false; treat_InternalError(1); return (p_Tree) ; } } return (p_Tree); } /********************************************************************************/ static t_NotFreeBlockTreeNode * balance_NotFreeBlockRight ( t_NotFreeBlockTreeNode * p_Tree, int * p_Higher ) { t_NotFreeBlockTreeNode * l_Temp1; t_NotFreeBlockTreeNode * l_Temp2; t_Balance l_Balance1; t_Balance l_Balance2; switch(p_Tree->f_Balance) { case c_Left : p_Tree->f_Balance = c_Equal; break ; case c_Equal : p_Tree->f_Balance = c_Right; * p_Higher = false; break ; case c_Right : l_Temp1 = p_Tree->f_Right; l_Balance1 = l_Temp1->f_Balance; if (l_Balance1 >= c_Equal) { p_Tree->f_Right = l_Temp1->f_Left; l_Temp1->f_Left = p_Tree; if (l_Balance1 == c_Equal) { p_Tree->f_Balance = c_Right; l_Temp1->f_Balance = c_Left; *p_Higher = false; } else { p_Tree->f_Balance = c_Equal; l_Temp1->f_Balance = c_Equal; } p_Tree = l_Temp1; } else { l_Temp2 = l_Temp1->f_Left; l_Balance2 = l_Temp2->f_Balance; l_Temp1->f_Left = l_Temp2->f_Right; l_Temp2->f_Right = l_Temp1; p_Tree ->f_Right = l_Temp2->f_Left; l_Temp2->f_Left = p_Tree; if (l_Balance2 == c_Right) p_Tree ->f_Balance = c_Left; else p_Tree ->f_Balance = c_Equal; if (l_Balance2 == c_Left ) l_Temp1->f_Balance = c_Right; else l_Temp1->f_Balance = c_Equal; p_Tree = l_Temp2; l_Temp2->f_Balance = c_Equal; } break ; } return(p_Tree); } /********************************************************************************/ static t_NotFreeBlockTreeNode * balance_NotFreeBlockLeft ( t_NotFreeBlockTreeNode * p_Tree, int * p_Higher ) { t_NotFreeBlockTreeNode * l_Temp1; t_NotFreeBlockTreeNode * l_Temp2; t_Balance l_Balance1; t_Balance l_Balance2; switch(p_Tree->f_Balance) { case c_Left : l_Temp1 = p_Tree->f_Left; l_Balance1 = l_Temp1->f_Balance; if (l_Balance1 <= c_Equal) { p_Tree->f_Left = l_Temp1->f_Right; l_Temp1->f_Right = p_Tree; if (l_Balance1 == c_Equal) { p_Tree->f_Balance = c_Left; l_Temp1->f_Balance = c_Right; *p_Higher = false; } else { p_Tree->f_Balance = c_Equal; l_Temp1->f_Balance = c_Equal; } p_Tree = l_Temp1; } else { l_Temp2 = l_Temp1->f_Right; l_Balance2 = l_Temp2->f_Balance; l_Temp1->f_Right = l_Temp2->f_Left; l_Temp2->f_Left = l_Temp1; p_Tree ->f_Left = l_Temp2->f_Right; l_Temp2->f_Right = p_Tree; if (l_Balance2 == c_Left) p_Tree ->f_Balance = c_Right; else p_Tree ->f_Balance = c_Equal; if (l_Balance2 == c_Right) l_Temp1->f_Balance = c_Left; else l_Temp1->f_Balance = c_Equal; p_Tree = l_Temp2; l_Temp2->f_Balance = c_Equal; } break ; case c_Equal : p_Tree->f_Balance = c_Left; * p_Higher = false; break ; case c_Right : p_Tree->f_Balance = c_Equal; break ; } return(p_Tree); } /********************************************************************************/ static t_NotFreeBlockTreeNode * eliminate_NotFreeBlock ( t_NotFreeBlockTreeNode * p_Tree, int * p_Higher ) { if (!(check_NotFreeBlockEmpty(p_Tree->f_Right))) { p_Tree->f_Right = eliminate_NotFreeBlock(p_Tree->f_Right,p_Higher); if (*p_Higher) p_Tree = balance_NotFreeBlockLeft(p_Tree,p_Higher); } else { t_NotFreeBlockTreeNode * l_ObsoleteNode; l_ObsoleteNode = p_Tree; g_HelpNotFreeBlockNode->f_Element = p_Tree->f_Element; p_Tree = p_Tree->f_Left; free(l_ObsoleteNode); *p_Higher = true; } return p_Tree; } /********************************************************************************/ static t_NotFreeBlockTreeNode * remove_NotFreeBlock_from_Tree1 ( t_NotFreeBlockTreeNode * p_Tree, t_BlockDescriptor* p_data, int * p_Higher ) { if (check_NotFreeBlockEmpty(p_Tree)) { *p_Higher = false; treat_InternalError(2); return (p_Tree); } else if (compare_BlockPointers(p_data,p_Tree->f_Element) < 0) { p_Tree->f_Left = remove_NotFreeBlock_from_Tree1(p_Tree->f_Left,p_data,p_Higher); if (*p_Higher) p_Tree = balance_NotFreeBlockRight(p_Tree,p_Higher); } else if (compare_BlockPointers(p_data,p_Tree->f_Element) > 0) { p_Tree->f_Right = remove_NotFreeBlock_from_Tree1(p_Tree->f_Right,p_data,p_Higher); if (*p_Higher) p_Tree = balance_NotFreeBlockLeft(p_Tree,p_Higher); } else { g_HelpNotFreeBlockNode = p_Tree; if (check_NotFreeBlockEmpty(g_HelpNotFreeBlockNode->f_Right)) { p_Tree = g_HelpNotFreeBlockNode->f_Left; free(g_HelpNotFreeBlockNode); *p_Higher = true; } else if (check_NotFreeBlockEmpty(g_HelpNotFreeBlockNode->f_Left)) { p_Tree = g_HelpNotFreeBlockNode->f_Right; free(g_HelpNotFreeBlockNode); *p_Higher = true; } else { g_HelpNotFreeBlockNode->f_Left = eliminate_NotFreeBlock(g_HelpNotFreeBlockNode->f_Left,p_Higher); if (*p_Higher) p_Tree = balance_NotFreeBlockRight(p_Tree,p_Higher); } } return p_Tree; } /********************************************************************************/ static int search_NotFreeBlock_in_Tree1 ( t_NotFreeBlockTreeNode * p_Tree, t_BlockDescriptor* * p_data) { if (!(check_NotFreeBlockEmpty(p_Tree))) if (compare_BlockPointers(* p_data,p_Tree->f_Element) < 0) return (search_NotFreeBlock_in_Tree1(p_Tree->f_Left,p_data)); else if (compare_BlockPointers(* p_data,p_Tree->f_Element) > 0) return (search_NotFreeBlock_in_Tree1(p_Tree->f_Right,p_data)); else { *p_data = p_Tree->f_Element; return (true); } else return (false); } /********************************************************************************/ static void delete_NotFreeBlockTree1 (t_NotFreeBlockTreeNode ** p_Tree) { if (!(check_NotFreeBlockEmpty(*p_Tree))) { delete_NotFreeBlockTree1(&((*p_Tree)->f_Left)); delete_NotFreeBlockTree1(&((*p_Tree)->f_Right)); free(*p_Tree); *p_Tree = NULL; } } /********************************************************************************/ static int get_Height_of_NotFreeBlockTree1(t_NotFreeBlockTreeNode *p_Tree) { if (check_NotFreeBlockEmpty(p_Tree)) return 0; else { return (1 + NotFreeBlock_max( get_Height_of_NotFreeBlockTree1(p_Tree->f_Left), get_Height_of_NotFreeBlockTree1(p_Tree->f_Right) ) ); } } /********************************************************************************/ static int get_Card_of_NotFreeBlockTree1 ( t_NotFreeBlockTreeNode * p_Tree) { if (!(check_NotFreeBlockEmpty(p_Tree))) return ( 1 + get_Card_of_NotFreeBlockTree1(p_Tree->f_Left) + get_Card_of_NotFreeBlockTree1(p_Tree->f_Right) ); else return 0; } /********************************************************************************/ static void free_NotFreeBlockTree1 (t_NotFreeBlockTreeNode * p_Tree) { if (!(check_NotFreeBlockEmpty(p_Tree))) { free_NotFreeBlockTree1(p_Tree->f_Left); delete_Descriptor(p_Tree->f_Element); free_NotFreeBlockTree1(p_Tree->f_Right); } } /********************************************************************************/ static void print_NotFreeBlockTree1 (t_NotFreeBlockTreeNode * p_Tree) { if (!(check_NotFreeBlockEmpty(p_Tree))) { print_NotFreeBlockTree1(p_Tree->f_Left); print_NotFreeBlock(p_Tree->f_Element); print_NotFreeBlockTree1(p_Tree->f_Right); } } /********************************************************************************/ /**************************** Global functions **********************************/ /********************************************************************************/ void create_NotFreeBlockTree ( void ) { g_SpareNotFreeBlockNode = (t_NotFreeBlockTreeNode *) malloc(sizeof(t_NotFreeBlockTreeNode )); g_Root = NULL; } /********************************************************************************/ void insert_NotFreeBlock_into_Tree ( t_BlockDescriptor* p_data ) { int l_Dummy = false; g_Root = insert_NotFreeBlock_into_Tree1 (g_Root,p_data,&l_Dummy); } /********************************************************************************/ int search_NotFreeBlock_in_Tree ( t_BlockDescriptor* * p_data) { return (search_NotFreeBlock_in_Tree1(g_Root,p_data)); } /********************************************************************************/ void remove_NotFreeBlock_from_Tree (t_BlockDescriptor* p_data ) { int l_Dummy = false; g_Root = remove_NotFreeBlock_from_Tree1(g_Root,p_data,&l_Dummy); if (g_SpareNotFreeBlockNode == NULL) g_SpareNotFreeBlockNode = (t_NotFreeBlockTreeNode *) malloc(sizeof(t_NotFreeBlockTreeNode)); } /********************************************************************************/ void delete_NotFreeBlockTree ( void ) { if (g_SpareNotFreeBlockNode) { free(g_SpareNotFreeBlockNode); g_SpareNotFreeBlockNode = NULL; } delete_NotFreeBlockTree1(&g_Root); } /********************************************************************************/ int check_NotFreeBlockFull ( void ) { if (g_SpareNotFreeBlockNode == NULL) g_SpareNotFreeBlockNode = (t_NotFreeBlockTreeNode *) malloc(sizeof(t_NotFreeBlockTreeNode)); return (g_SpareNotFreeBlockNode == NULL); } /********************************************************************************/ int get_Height_of_NotFreeBlockTree ( void ) { return (get_Height_of_NotFreeBlockTree1 (g_Root)); } /********************************************************************************/ int get_Card_of_NotFreeBlockTree ( void ) { return (get_Card_of_NotFreeBlockTree1 (g_Root)); } /********************************************************************************/ void free_NotFreeBlockTree ( void ) { free_NotFreeBlockTree1(g_Root); } /********************************************************************************/ void print_NotFreeBlockTree ( void ) { print_NotFreeBlockTree1(g_Root); } /********************************************************************************/ /********************************************************************************/