#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define MAX_PATH_SIZE 100
#define MAX_FILEDIR_NAME_SIZE 10
#define MAX_BLOCKS 20
#define BLOCK_SIZE 1024
typedef struct file_descriptor
{
int is_dir;
int fd_id;
int size;
char file_name[MAX_FILEDIR_NAME_SIZE];
char path[MAX_PATH_SIZE];
int blocks[MAX_BLOCKS];
}fd;
//N-ary tree node
typedef struct tree_node
{
fd *data;
int is_deleted;
struct tree_node *left_child;
struct tree_node *right_siblings;
struct tree_node *parent;
}t_node;
//binary search tree node
typedef struct bst_node
{
struct bst_node *parent;
struct bst_node *left;
struct bst_node *right;
char full_path[MAX_PATH_SIZE+MAX_FILEDIR_NAME_SIZE];
fd *file_desc;
}b_node;
b_node *bst_create()
{
b_node* root=NULL;
return root;
}
int bst_insert(b_node **bst_root_ptr,fd *data)
{
char fullpath[110];
strcpy(fullpath,data->path);
strcat(fullpath,"/");
strcat(fullpath,data->file_name);
if(*bst_root_ptr==NULL)
{
b_node* b1=(b_node*)malloc(sizeof(b_node));
b1->file_desc=data;
strcpy(b1->full_path,fullpath);
b1->left=NULL;
b1->right=NULL;
b1->parent=NULL;
*bst_root_ptr=b1;
return 0;
}
else
{
b_node* b1=(b_node*)malloc(sizeof(b_node));
b1->file_desc=data;
strcpy(b1->full_path,fullpath);
b1->left=NULL;
b1->right=NULL;
b1->parent=NULL;
b_node *curr,*par;
curr=*bst_root_ptr;
while(curr!=NULL)
{
par=curr;
if((strcmp(fullpath,curr->full_path))<0)
{
curr=curr->left;
}
else if((strcmp(fullpath,curr->full_path))>0)
{
curr=curr->right;
}
else if((strcmp(fullpath,curr->full_path))==0)
{
printf("file already present\n");
return 1;
}
}
if((strcmp(fullpath,par->full_path))<0)
{
par->left=b1;
b1->parent=par;
return 0;
}
else if((strcmp(fullpath,par->full_path))>0)
{
par->right=b1;
b1->parent=par;
return 0;
}
}
}
b_node *bst_search(b_node *bst_root,char *fullpath)
{
b_node* temp=bst_root;
if(bst_root==NULL)
{
return NULL;
}
else
{
while(temp!=NULL)
{
if((strcmp(temp->full_path,fullpath))==0)
{
return temp;
}
else if((strcmp(temp->full_path,fullpath))>0)
{
temp=temp->left;
}
else if((strcmp(temp->full_path,fullpath))<0)
{
temp=temp->right;
}
}
return NULL;
}
}
int bst_delete(b_node **bst_root_ptr,char *fullpath)
{
int isfound=0;
if(*bst_root_ptr==NULL)
{
printf("tree is empty\n");
return 1;
}
b_node* root=*bst_root_ptr;
b_node* location;
location=bst_search(root,fullpath);
if(location==NULL)
{
return 1;
}
//if location has no child
else if(location->left==NULL && location->right==NULL)
{
if(location->parent->left==location)
{
location->parent->left=NULL;
}
else if(location->parent->right==location)
{
location->parent->right=NULL;
}
return 0;
}
//if location has only right child
else if(location->left==NULL && location->right!=NULL)
{
if(location->parent->left==location)
{
location->parent->left=location->right;
}
else if(location->parent->right==location)
{
location->parent->right=location->right;
}
return 0;
}
//if location has only left child
else if(location->left!=NULL && location->right==NULL)
{
if(location->parent->left==location)
{
location->parent->left=location->left;
}
else if(location->parent->right==location)
{
location->parent->right=location->left;
}
return 0;
}
//if location has both child
else if(location->left!=NULL && location->right!=NULL)
{
b_node* parent,*x;
parent=location;
x=location;
while(x->left!=NULL)
{
parent=x;
x=x->left;
}
location->file_desc=x->file_desc;
strcpy(location->full_path,x->full_path);
x->parent->left=NULL;
return 0;
}
return 1;
}
int main()
{
b_node *root;
root=bst_create();
fd* dir1 = (fd*)malloc(sizeof(fd));
dir1->is_dir=1;
dir1->fd_id=1;
dir1->size=10;
strcpy(dir1->file_name,"BIN.txt");
strcpy(dir1->path,"/bin/");
dir1->blocks[0]=12;
fd* dir4 = (fd*)malloc(sizeof(fd));
dir4->is_dir=1;
dir4->fd_id=1;
dir4->size=10;
strcpy(dir4->file_name,"CIN.txt");
strcpy(dir4->path,"/bin/");
dir4->blocks[0]=12;
fd* dir5 = (fd*)malloc(sizeof(fd));
dir5->is_dir=1;
dir5->fd_id=1;
dir5->size=10;
strcpy(dir5->file_name,"YFS.txt");
strcpy(dir5->path,"/usr/");
dir5->blocks[0]=12;
int return_insert=bst_insert ( &root,dir1);
return_insert=bst_insert ( &root,dir4);
return_insert=bst_insert ( &root,dir5);
b_node *found =bst_search( root,"/usr/ADB.txt");
if(found != NULL)
printf("\nFilname :%s\n", found->full_path);
int return_delete=bst_delete(&root,"/usr/VFS.txt");
printf("\nReturn Value %d\n", return_delete);
}
