操作系统课程设计--文件管理系统

/* 定义控制台应用程序的入口点 */
#include <map>
#include<iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>

//#include <windows.h>  //linux lab 无法引用 
#define PHYSICAL_BLOCK_SIZE 1024
#define LOGICAL_BLOCK_SIZE 1024
#define NAME_LEN 14
#define START_PARTITION_TABLE 0x1be

using namespace std;

void print_char(char c);
void get_inode(unsigned short inode_id, struct d_inode* inode);
void puts(const char s[],const int ma);
bool print_file(unsigned short id);
string new_string(const char *s,const int ma);
void load_logical_bitmap();
void write_load_logical_bitmap();
int is_logical_valid(unsigned short inode_id);
bool update_logical_valid(unsigned short inode_id);
void delete_inode_father(unsigned short id);

//分区表结构
struct par_table_entry {
	char boot_indicator;	//导入指示器，绝大多数情况都是0
	char start_chs_val[3];	//起始柱面磁头扇区值，3个字节分别对应柱面号、磁头号、扇区号
	char par_type;			//分区类型
	char end_chs_val[3];	//终止柱面磁头扇区值
	int start_sector;		//起始盘块号
	int par_size;			//分区大小
};

// 超级块结构体
struct super_block
{
  unsigned short s_ninodes;		//  
  unsigned short s_nzones;		// 逻辑块数。
  unsigned short s_imap_blocks;	// i 节点位图所占用的数据块数。
  unsigned short s_zmap_blocks;	// 逻辑块位图所占用的数据块数。
  unsigned short s_firstdatazone;	// 第一个数据逻辑块号。
  unsigned short s_log_zone_size;	// log(数据块数/逻辑块)。（以2 为底）。
  unsigned long s_max_size;		// 文件最大长度。
  unsigned short s_magic;		// 文件系统魔数。
};

// i节点结构体
struct d_inode
{
  unsigned short i_mode;		// 文件类型和属性(rwx 位)。
  unsigned short i_uid;			// 用户id（文件拥有者标识符）。
  unsigned long i_size;			// 文件大小（字节数）。
  unsigned long i_time;			// 修改时间（自1970.1.1:0 算起，秒）。
  unsigned char i_gid;			// 组id(文件拥有者所在的组)。
  unsigned char i_nlinks;		// 链接数（多少个文件目录项指向该i 节点）。
  unsigned short i_zone[9];		// 直接(0-6)、间接(7)或双重间接(8)逻辑块号。
								// zone 是区的意思，可译成区段，或逻辑块。
};

//目录项结构
struct dir_entry{
	unsigned short inode;	//i节点号
	char name[NAME_LEN];	//文件名
	dir_entry(unsigned short x,char y[NAME_LEN]){
		inode = x;
		for(int ii=0;ii<NAME_LEN;ii++){
			name[ii]=y[ii];
		}
	}
	dir_entry(){}
};
struct super_block sblock;		//超级块
struct par_table_entry pte[4];	//分区表数组
FILE* fd;						//文件指针
char physical_block[PHYSICAL_BLOCK_SIZE]; //存储物理块
char logical_block[LOGICAL_BLOCK_SIZE];  //存储逻辑块
char *inode_bitmap;		//i节点位图指针
char *logical_bitmap;	//逻辑块位图指针
map<unsigned short,unsigned short> inode_father;  //临时存储文件 id节点的父节点 

//读取一个物理块
void get_physical_block(int block_num)
{
	//减1是因为物理盘块是从1开始计数
	fseek(fd, (block_num - 1) * PHYSICAL_BLOCK_SIZE, SEEK_SET);
	fread(physical_block, PHYSICAL_BLOCK_SIZE, 1, fd);
	fflush(stdin);
}

//写入一个物理块 
void write_physical_block(int block_num){
	//减1是因为物理盘块是从1开始计数
	
	fseek(fd, (block_num - 1) * PHYSICAL_BLOCK_SIZE, SEEK_SET);
	fwrite(physical_block, PHYSICAL_BLOCK_SIZE, 1, fd);
	fflush(stdout);
	

}

//读取第一个分区的一个逻辑块
void get_partition_logical_block(int block_num)
{
	//block_num前面加的1表示在第一个分区前还有一个主引导记录（MBR）块，
	//后面加的1是因为物理盘块是从1开始计数的,而逻辑块是从0开始计数的
	get_physical_block(1 + block_num + 1);
	memcpy(logical_block, physical_block, LOGICAL_BLOCK_SIZE);
}

//写入一个逻辑块
void write_partition_logical_block(int block_num)
{
	//block_num前面加的1表示在第一个分区前还有一个主引导记录（MBR）块，
	//后面加的1是因为物理盘块是从1开始计数的,而逻辑块是从0开始计数的
	memcpy(physical_block,logical_block , LOGICAL_BLOCK_SIZE);
	
	write_physical_block(1 + block_num + 1);
	
	
}

//读取分区表
void get_partition_table()
{
	int i = 0;

	//分区表有4个16字节的表项组成，第一个表项的起始地址为START_PARTITION_TABLE
	get_physical_block( 1 );	//分区表在物理盘块的第1块
	memcpy(pte, &physical_block[START_PARTITION_TABLE], sizeof(pte));
	for(i = 0; i < 4; i++)
	{
		printf("**************pattition table%d****************\n", i+1);
		printf("Boot Indicator:%d\n", pte[i].boot_indicator);
		printf("start CHS value:0x%04x\n", pte[i].start_chs_val);
		printf("partition type:%ld\n", pte[i].par_type);
		printf("end CHS value:0x%04x\n", pte[i].end_chs_val);
		printf("start sector:%d\n", pte[i].start_sector);
		printf("partition size:%d\n", pte[i].par_size);
	}
}

//读取第一个分区的超级块
void get_super_block()
{	
	get_partition_logical_block( 1 );
	memcpy(&sblock, logical_block, sizeof(sblock));
	
	printf("**************super block****************\n");
	printf("ninodes：%d\n", sblock.s_ninodes);
	printf("nzones：%d\n", sblock.s_nzones);
	printf("imap_blocks：%d\n", sblock.s_imap_blocks);
	printf("zmap_blocks：%d\n", sblock.s_zmap_blocks);
	printf("firstdatazone：0x%04x\n", sblock.s_firstdatazone);
	printf("log_zone_size：%d\n", sblock.s_log_zone_size);
	printf("max_size：0x%x = %dByte\n", sblock.s_max_size,sblock.s_max_size);
	printf("magic：0x%x\n", sblock.s_magic);
}	

/*************i节点位图相关操作函数*********************/ 
//加载i节点位图
void load_inode_bitmap()
{
	inode_bitmap = (char*)malloc(sblock.s_imap_blocks * LOGICAL_BLOCK_SIZE);
	int i = 0;
	for(i = 0; i < sblock.s_imap_blocks; i++)
	{
		//i节点位图前有1个引导块和一个超级块
		get_partition_logical_block(1 + 1 + i);	
		memcpy(&inode_bitmap[i * LOGICAL_BLOCK_SIZE], &logical_block, LOGICAL_BLOCK_SIZE);
	}
}

//写入i节点位图 
void write_load_inode_bitmap()
{
	
	for(int i = 0; i < sblock.s_imap_blocks; i++)
	{
		
		//i节点位图前有1个引导块和一个超级块
		memcpy(&logical_block, &inode_bitmap[i * LOGICAL_BLOCK_SIZE], LOGICAL_BLOCK_SIZE);
		
		write_partition_logical_block(1 + 1 + i);	
	}
}

//根据i节点位图判断其对应的i节点是否有效
//参数inode_id为i节点的id
//有效返回1，无效返回0
int is_inode_valid(unsigned short inode_id)
{
	if(inode_id > sblock.s_ninodes)
		return 0;
		
	char byte = inode_bitmap[(inode_id - 1) / 8]; //inode_id减1是因为i节点是从1开始计数的
	return (byte >> (7 - (inode_id - 1) % 8) ) & 0x1;	//取一个字节中的某位与1做位运算
}

//修改i节点位图,将i节点位图置为0或1 
bool update_inode_valid(unsigned short inode_id,int val){
	if(inode_id > sblock.s_ninodes)
		return 0; 
	
	char byte = inode_bitmap[(inode_id - 1) / 8]; //inode_id减1是因为i节点是从1开始计数的
	int now_val = ((byte >> (7 - (inode_id - 1) % 8) ) & 0x1);
	if(now_val==1&&val!=1){
		char x = (1<<(7 - (inode_id - 1) % 8) );
		inode_bitmap[(inode_id - 1) / 8] = byte - x; 
		 
	}else if(now_val==0&&val!=0){
		char x = (1<<(7 - (inode_id - 1) % 8) );
		inode_bitmap[(inode_id - 1) / 8] = byte + x; 
	}
	write_load_inode_bitmap();  //对应 i节点写回软盘
	return 1;
}

/*************逻辑块位图相关操作函数*********************/ 
//加载逻辑块位图
void load_logical_bitmap(){
	logical_bitmap = (char*)malloc(sblock.s_zmap_blocks * LOGICAL_BLOCK_SIZE);
	int i = 0;
	for(i = 0; i < sblock.s_zmap_blocks; i++)
	{
		//逻辑块位图前有1个引导块 ,一个超级块 , 三个 i 节点位图逻辑块 
		get_partition_logical_block(1 + 1 + i+sblock.s_imap_blocks);	
		memcpy(&logical_bitmap[i * LOGICAL_BLOCK_SIZE], &logical_block, LOGICAL_BLOCK_SIZE);
	}
}

//写入逻辑块位图 
void write_load_logical_bitmap()
{
	
	for(int i = 0; i < sblock.s_zmap_blocks; i++)
	{
		
		//逻辑块位图前有1个引导块 ,一个超级块 , 三个 i 节点位图逻辑块 
		memcpy(&logical_block, &logical_bitmap[i * LOGICAL_BLOCK_SIZE], LOGICAL_BLOCK_SIZE);
		
		write_partition_logical_block(sblock.s_imap_blocks+1 + 1 + i);	
	}
}

//判断 inode_id 数据逻辑块（位图）是否被占用 
int is_logical_valid(unsigned short inode_id)
{
	
		
	char byte = logical_bitmap[(inode_id - 1) / 8]; //inode_id减1是因为i节点是从1开始计数的
	return (byte >> (7 - (inode_id - 1) % 8) ) & 0x1;	//取一个字节中的某位与1做位运算
}

//inode_id 数据逻辑块位图修改 
bool update_logical_valid(unsigned short inode_id,int val){
	
	char byte = logical_bitmap[(inode_id - 1) / 8]; //inode_id减1是因为i节点是从1开始计数的
	int now_val = ((byte >> (7 - (inode_id - 1) % 8) ) & 0x1);
	if(now_val==1&&val!=1){
		char x = (1<<(7 - (inode_id - 1) % 8) );
		logical_bitmap[(inode_id - 1) / 8] = byte - x;
		
	}else if(now_val==0&&val!=0){
		char x = (1<<(7 - (inode_id - 1) % 8) );
		logical_bitmap[(inode_id - 1) / 8] = byte + x;
		
	}
	write_load_logical_bitmap();   //逻辑块位图写回软盘 
	return 1;
}

//根据i节点id读取i节点信息 
void get_inode(unsigned short inode_id, struct d_inode* inode)
{
	//一个引导块，一个超级块，sblock.s_imap_blocks个i节点位图，sblock.s_zmap_blocks个逻辑块位图	
	//一个i节点占32个字节，一个盘块有LOGICAL_BLOCK_SIZE/32个节点，所以inode_id/(LOGICAL_BLOCK_SIZE/32)
	//减1是因为i节点号是从1开始计数的，而逻辑块号是从0开始计数的
	//inode_blocknum是i节点在逻辑块中的偏移块数
	int inode_blocknum = 1 + 1 + sblock.s_imap_blocks + sblock.s_zmap_blocks + (inode_id - 1) / (LOGICAL_BLOCK_SIZE/32) ;
	get_partition_logical_block(inode_blocknum);
	memcpy((char*)inode, &logical_block[((inode_id - 1) % sizeof(struct d_inode)) * sizeof(struct d_inode)], sizeof(struct d_inode));
}

//根据i节点信息写回软盘 
void write_inode(unsigned short inode_id, struct d_inode inode)
{
	int inode_blocknum = 1 + 1 + sblock.s_imap_blocks + sblock.s_zmap_blocks + (inode_id - 1) / (LOGICAL_BLOCK_SIZE/32) ;
	get_partition_logical_block(inode_blocknum);
	memcpy(&logical_block[((inode_id - 1) % sizeof(struct d_inode)) * sizeof(struct d_inode)],(char*)&inode , sizeof(struct d_inode));
	
	write_partition_logical_block(inode_blocknum);
	
}

/*****************打印，查找 id逻辑块信息**************************/ 
//递归打印 i节点下的目录
void print_inode(unsigned short id, int tab_count, const char* name)
{
	int i, m, n;
	struct d_inode inode;
	struct dir_entry dir;
	//如果i节点号对应在i节点位图相应位的值为1,说明此i节点已使用
	//否则说明此i节点无用或已被删除，则直接返回
	if(is_inode_valid(id) != 1)return ;
		
	get_inode(id, &inode);
	tab_count++;
	unsigned short mode = inode.i_mode >> 12; //高4位存放的是文件类型
	//如果是目录文件
	//	if(new_string(name,NAME_LEN)=="file.txt"){
	//		cout<<inode.i_mode<<" "<<mode<<endl;
	//	} 
	if(mode == 4)
	{
		//打印tab键，为了使目录有层次感
		for(i=0; i<tab_count; i++)
		{
			printf("\t");
		}
		//printf("%s\n", name);
		cout<<new_string(name,NAME_LEN)<<" "<<id<<endl;
		//循环读取i节点中的i_zones[]数组
		for(m = 0; m<7; m++)
		{
			//如果数组数据为0，则跳过
			if(inode.i_zone[m] == 0)
				continue;
			
			//一个逻辑块最多存储64个目录项,循环读取64个目录项
			//其中前两项分别为 . 和 .. 
			for(n = 0; n < 64; n++)
			{
				get_partition_logical_block(inode.i_zone[m]);
				//将逻辑块中的数据拷贝到目录项结构体
				memcpy((char*)&dir, &logical_block[n * sizeof(dir)], sizeof(dir));
				
				//如果是 .和..则继续循环
				if(n == 0 || n == 1)
					continue;
					
				//如果目录项中没有内容了则不再读取
				if(dir.inode == 0)
					break;
				
				//递归打印子目录
				print_inode(dir.inode, tab_count, dir.name);
				if(new_string(dir.name,NAME_LEN)=="root"){
					//cout<<"this is "<<new_string(dir.name,NAME_LEN)<<" id="<<dir.inode<<"if true"<<is_inode_valid(dir.inode)<<endl;
					//Sleep(2000);
					//exit(0);
				}
			}
		}
	}
	
	//如果是常规文件
	else if(mode == 8)
	{
		for(i=0; i<tab_count; i++)
		{
			printf("\t");
		}
		//puts(name,NAME_LEN);
		cout<<new_string(name,NAME_LEN)<<" "<<id<<endl;
		//printf("%s %d\n", name,id);
		//if(new_string(name,NAME_LEN)=="myfiles"){
		//Sleep(3000);

	}else if(mode = 9){
		
	}
	//如果块设备文件、字符设备文件等其他类型文件，请读者尝试自己实现
}

//查找 id 的i节点的文件夹下的名为 find_name 的子文件，并返回其 i节点id号 
unsigned short find_inode(unsigned short id, string find_name)
{
	int i, m, n;
	struct d_inode inode;
	struct dir_entry dir;
	
	//如果i节点号对应在i节点位图相应位的值为1,说明此i节点已使用
	//否则说明此i节点无用或已被删除，则直接返回
	if(is_inode_valid(id) != 1)
		return 0;
		
	get_inode(id, &inode);
	unsigned short mode = inode.i_mode >> 12; //高4位存放的是文件类型
	//如果是目录文件
	//cout<<mode<<endl;
	//mode=4;
	if(mode!=4){
		return 0;
	}

	//循环读取i节点中的i_zones[]数组
	for(m = 0; m<7; m++)
	{
		//cout<<inode.i_zone[m]<<endl;
		//如果数组数据为0，则跳过
		if(inode.i_zone[m] == 0)
			continue;
		
		//一个逻辑块最多存储64个目录项,循环读取64个目录项
		//其中前两项分别为 . 和 .. 
		for(n = 0; n < 64; n++)
		{
			get_partition_logical_block(inode.i_zone[m]);
			//将逻辑块中的数据拷贝到目录项结构体
			memcpy((char*)&dir, &logical_block[n * sizeof(dir)], sizeof(dir));
			
			//如果是 .和..则继续循环
			if(n == 0 || n == 1)
				continue;
				
			//如果目录项中没有内容了则不再读取
			if(dir.inode == 0)
				break;
			
			//递归打印子目录
			//find_inode(dir.inode, tab_count, dir.name,find_name);
			//cout<<"*"<<new_string(dir.name,NAME_LEN)<<"* "<<dir.inode<<"*"<<find_name<<"*\n";
			if(new_string(dir.name,NAME_LEN)==find_name){//表示查找到 
				return dir.inode;
			}
		}
	}
	return 0;
}

//对(id=1 绝对)路径下的文件查找其 i 节点 id 
unsigned short find_root_inode(string find_name,int start_id){  
	if(find_name=="/")return 1;
	if(find_name[find_name.size()-1]!='/')find_name+="/";
	if(find_name[0]!='/')find_name = "/"+find_name;
	//确保其绝对路径为 "/name_1/name_2/name_3" 的形式 
	int last=0;
	int id=start_id;
	
	for(int i=1;i<find_name.size();i++){
		if(find_name[i]=='/'){
			
			//cout<<id<<" "<<string(find_name.begin()+last+1,find_name.begin()+i)<<endl; 
			id=find_inode(id,string(find_name.begin()+last+1,find_name.begin()+i));
			last=i;
			
			if(id==0)return 0;
		}
	} 
	return id;
}

//输出打印name文件（绝对）路径下的文件内容 
void print_file(string name){
	puts("-------------cout-----------------");
	unsigned short id = find_root_inode(name,1);
	if(id==0){
		cout<<"error no file  "<<name<<"\n";
	
	}else if(!print_file(id))cout<<"error no last file  "<<name<<"\n";
	puts("-------------endl-----------------");
}

//重载打印函数，对start_i下的文件内容打印（相对路径） 
void print_file(string name,int start_id){
	puts("-------------cout-----------------");
	unsigned short id = find_root_inode(name,start_id);
	if(id==0){
		cout<<"error no file  "<<name<<"\n";
	
	}else if(!print_file(id))cout<<"error no purpose file  "<<name<<"\n";
	puts("-------------endl-----------------");
}

//打印 id 节点下文件内容 
bool print_file(unsigned short id){
	int i, m, n;
	struct d_inode inode;
	struct dir_entry dir;
	//如果i节点号对应在i节点位图相应位的值为1,说明此i节点已使用
	//否则说明此i节点无用或已被删除，则直接返回
	if(is_inode_valid(id) != 1){
		//cout<<"this 1"<<endl;
		return 0;
	}
		
		
	get_inode(id, &inode);
	unsigned short mode = inode.i_mode >> 12; //高4位存放的是文件类型
	//如果是目录文件，打印其子文件夹 
	if(mode == 4)
	{
		//循环读取i节点中的i_zones[]数组
		for(m = 0; m<7; m++)
		{
			//如果数组数据为0，则跳过
			if(inode.i_zone[m] == 0)
				continue;
			
			//一个逻辑块最多存储64个目录项,循环读取64个目录项
			//其中前两项分别为 . 和 .. 
			for(n = 0; n < 64; n++)
			{
				get_partition_logical_block(inode.i_zone[m]);
				//将逻辑块中的数据拷贝到目录项结构体
				memcpy((char*)&dir, &logical_block[n * sizeof(dir)], sizeof(dir));
				
				//如果是 .和..则继续循环
				if(n == 0 || n == 1)
					continue;
					
				//如果目录项中没有内容了则不再读取
				if(dir.inode == 0)
					break;
				
				
				puts(dir.name,NAME_LEN);
			}
		}
		return 1;
	}
	//cout<<"----strat----"<<endl;
	for(m = 0; m<7; m++){
		//如果数组数据为0，则跳过
		//cout<<inode.i_zone[m]<<endl;
		if(inode.i_zone[m] == 0)
			break;
		
		if(is_logical_valid(inode.i_zone[m]) != 1){cout<<"file be delete a part\n";return 0;}
		//cout<<m<<" "<<inode.i_zone[m]<<endl;
		get_partition_logical_block(inode.i_zone[m]);
		puts(logical_block,PHYSICAL_BLOCK_SIZE);

	}
	
	if(inode.i_zone[7]){
		
		for(n = 0; n < 512; n++)
		{
			unsigned short dete_id;
			get_partition_logical_block(inode.i_zone[7]);
			//将逻辑块中的数据拷贝到目录项结构体
			memcpy((char*)&dete_id, &logical_block[n*sizeof(dete_id)], sizeof(dete_id));
			//cout<<(dete_id);cout<<endl;
			//cout<<7<<" "<<dete_id<<endl;
			if(dete_id==0)break;
			if(is_logical_valid(dete_id) != 1){cout<<"file be delete a part\n";return 0;}
			
			get_partition_logical_block(dete_id);
			puts(logical_block,PHYSICAL_BLOCK_SIZE);
		}
	}

	if(inode.i_zone[8]){
	
		for(int n1 = 0; n1 < 512; n1++)
		{
			unsigned short dete_id_1;
			get_partition_logical_block(inode.i_zone[8]);
			//将逻辑块中的数据拷贝到目录项结构体
			memcpy((char*)&dete_id_1, &logical_block[n1*2], 2);
			//print_char(dete_id[0]);cout<<endl;
			if(dete_id_1==0)break;
			if(is_logical_valid(dete_id_1) != 1){cout<<"file be delete a part\n";return 0;}
			for(int n2 = 0; n2 < 512; n2++)
			{
				unsigned short dete_id_2;
				get_partition_logical_block(dete_id_1);
				//将逻辑块中的数据拷贝到目录项结构体
				memcpy((char*)&dete_id_2, &logical_block[n2*2], 2);
				//print_char(dete_id[0]);cout<<endl;
				if(dete_id_2==0)break;
				if(is_logical_valid(dete_id_2) != 1){cout<<"file be delete a part\n";return 0;}
				get_partition_logical_block(dete_id_2);
				puts(logical_block,PHYSICAL_BLOCK_SIZE);
			}
		}
	}
	return 1;
	
}

/****************删除文件************************/
// 删除  inode_id 文件以及下属所有子文件以及释放下属所有逻辑块 
bool delete_file_inode_valid(unsigned short inode_id){
	int  m, n;
	struct d_inode inode;
	struct dir_entry dir;
	
	//如果i节点号对应在i节点位图相应位的值为1,说明此i节点已使用
	//否则说明此i节点无用或已被删除，则直接返回
	if(is_inode_valid(inode_id) != 1)
		return 0;
		
	get_inode(inode_id, &inode);
	
	unsigned short mode = inode.i_mode >> 12; //高4位存放的是文件类型
	//如果是目录文件
	if(mode == 4)
	{
		//循环读取i节点中的i_zones[]数组
		for(m = 0; m<7; m++)
		{
			//如果数组数据为0，则跳过
			if(inode.i_zone[m] == 0)
				continue;
			
			//一个逻辑块最多存储64个目录项,循环读取64个目录项
			//其中前两项分别为 . 和 .. 
			for(n = 0; n < 64; n++)
			{
				get_partition_logical_block(inode.i_zone[m]);
				//将逻辑块中的数据拷贝到目录项结构体
				memcpy((char*)&dir, &logical_block[n * sizeof(dir)], sizeof(dir));
				
				//如果是 .和..则继续循环
				if(n == 0 || n == 1)
					continue;
					
				//如果目录项中没有内容了则不再读取
				if(dir.inode == 0)
					break;
				
				//递归打印子目录
				delete_file_inode_valid(dir.inode);
			}
		}
	}
	
	//如果是其他文件
	else{
		
		for(m = 0; m<7; m++)
		{
			//如果数组数据为0，则跳过
			if(inode.i_zone[m] == 0)
				continue;
			
			update_logical_valid(inode.i_zone[m],0);//将对应的数据逻辑位图释放 
			
		}
		if(inode.i_zone[7]){
			
			for(n = 0; n < 512; n++)
			{
				unsigned short dete_id;
				get_partition_logical_block(inode.i_zone[7]);
				//将逻辑块中的数据拷贝到目录项结构体
				memcpy((char*)&dete_id, &logical_block[n*2], 2);
				//print_char(dete_id[0]);cout<<endl;
				if(dete_id==0)continue;
				update_logical_valid(inode_id,0);  //释放二级数据逻辑块位图 
			}
			update_logical_valid(inode.i_zone[7],0);//将对应的一级数据逻辑位图释放 
		}
	
		if(inode.i_zone[8]){
			
			
		
			for(int n1 = 0; n1 < 512; n1++)
			{
				unsigned short dete_id_1;
				get_partition_logical_block(inode.i_zone[8]);
				//将逻辑块中的数据拷贝到目录项结构体
				memcpy((char*)&dete_id_1, &logical_block[n1*2], 2);
				//print_char(dete_id[0]);cout<<endl;
				if(dete_id_1==0)continue;
				
				for(int n2 = 0; n2 < 512; n2++)
				{
					unsigned short dete_id_2;
					get_partition_logical_block(dete_id_1);
					//将逻辑块中的数据拷贝到目录项结构体
					memcpy((char*)&dete_id_2, &logical_block[n2*2], 2);
					//print_char(dete_id[0]);cout<<endl;
					if(dete_id_2==0)continue;
					update_logical_valid(inode_id,0);////将对应的三级数据逻辑位图释放 
				}
				update_logical_valid(dete_id_1,0);//将对应的二级数据逻辑位图释放
			}
			update_logical_valid(inode.i_zone[8],0);//将对应的一级数据逻辑位图释放 
		}
		
	}
	update_inode_valid(inode_id,0);//最后释放inode_id节点文件的 i节点位图 
	return 1;
}

//删除其父目录文件下的子文件信息 
void delete_inode_father(unsigned short id){
	unsigned short fat = inode_father[id];
	struct d_inode inode;
	struct dir_entry dir;
	
	//如果i节点号对应在i节点位图相应位的值为1,说明此i节点已使用
	//否则说明此i节点无用或已被删除，则直接返回
	if(is_inode_valid(fat) != 1)
		return ;
	get_inode(fat, &inode);
	//cout<<fat<<endl;
	for(int i = 0; i<7; i++)
	{
		//如果数组数据为0，则跳过
		if(inode.i_zone[i] == 0)
			continue;
		
		//一个逻辑块最多存储64个目录项,循环读取64个目录项
		//其中前两项分别为 . 和 .. 
		for(int j = 0; j < 64; j++)
		{
			get_partition_logical_block(inode.i_zone[i]);
			//将逻辑块中的数据拷贝到目录项结构体
			memcpy((char*)&dir, &logical_block[j * sizeof(dir)], sizeof(dir));
			
			//如果是 .和..则继续循环
			if(j == 0 || j == 1)
				continue;
				
			//如果目录项中没有内容了则不再读取
			if(dir.inode == 0)
				break;
			
			//找到子目录/文件 
			if(dir.inode==id){
				/*
				因为要删除 1 个逻辑块中的16个字节的信息，
				首先要将该十六个字节内容置为空（避免要删除的信息在最后） 
				然后该逻辑块后面的内容一次向前移 
				*/
				dir.inode=0;
				memset(dir.name,0,sizeof(dir.name));
				memcpy(&logical_block[j * sizeof(dir)],(char*)&dir, sizeof(dir));
				//puts(dir.name);
				j++;
				while(j<64){
					memcpy((char*)&dir, &logical_block[j * sizeof(dir)], sizeof(dir));
					memcpy(&logical_block[(j-1) * sizeof(dir)],(char*)&dir, sizeof(dir));
					j++;
				}
				
				write_partition_logical_block(inode.i_zone[i]);
				return ;
			}
			
		}
	}
}

//对文件绝对路径下name文件执行删除操作 
void delete_file(string name){
	unsigned short id = find_root_inode(name,1);
	
	if(id==0){
		cout<<"error no file "<<name<<"\n";
		return ;
	}
	if(delete_file_inode_valid(id)){  //正式执行删除该文件操作 
		delete_inode_father(id);  //删除父节点（父目录）下的该文件信息 
		cout<<"success\n";
	}else{
		cout<<"no know error\n";
	}
	
}


/***************其他**************************/ 
//将字符类型转换二进制打印 
void print_char(char c){
	for(int i=7;i>=0;i--){
		if((c>>i)&1){
			cout<<"1 ";
		}
		else cout<<"0 ";
	}
}

//打印字符串(限制最大打印长度 
//（对于一些字符串可能会占满字符数组长度上限,
//导致正常打印末尾没有结束符'\0'从而导致访问越界） 
void puts(const char s[],const int ma){
	for(int i=0;i<ma;i++){
		if(s[i]=='\0')break;
		putchar(s[i]);
	}putchar('\n');
}

//char 强制类型转换 string 
//原因同上 
string new_string(const char *s,const int ma){
	string ans="";
	for(int i=0;i<ma;i++){
		if(s[i]=='\0')break;
		ans+=s[i];
	}
	return ans;
	
}

//加载 map<unsigned short,unsigned short> inode_father; 
void load_inode_father(unsigned short id, const char* name)
{
	int i, m, n;
	struct d_inode inode;
	struct dir_entry dir;
	
	//如果i节点号对应在i节点位图相应位的值为1,说明此i节点已使用
	//否则说明此i节点无用或已被删除，则直接返回
	if(is_inode_valid(id) != 1)
		return;
		
	get_inode(id, &inode);
	
	unsigned short mode = inode.i_mode >> 12; //高4位存放的是文件类型
	//如果是目录文件
	if(mode == 4)
	{
		//循环读取i节点中的i_zones[]数组
		for(m = 0; m<7; m++)
		{
			//如果数组数据为0，则跳过
			if(inode.i_zone[m] == 0)
				continue;
			
			//一个逻辑块最多存储64个目录项,循环读取64个目录项
			//其中前两项分别为 . 和 .. 
			for(n = 0; n < 64; n++)
			{
				get_partition_logical_block(inode.i_zone[m]);
				//将逻辑块中的数据拷贝到目录项结构体
				memcpy((char*)&dir, &logical_block[n * sizeof(dir)], sizeof(dir));
				
				//如果是 .和..则继续循环
				if(n == 0 || n == 1)
					continue;
					
				//如果目录项中没有内容了则不再读取
				if(dir.inode == 0)
					break;
				//cout<<dir.inode<<" ";
				inode_father[dir.inode] = id;
				
				load_inode_father(dir.inode,dir.name);
			}
		}
	}
}


/**********************新建文件******************/
//申请一个位于i节点内的逻辑块 
unsigned short apply_inode_valid()
{

	for(unsigned short i=2;i<=sblock.s_ninodes;i++){
		if(is_inode_valid(i)!=1){
			update_inode_valid(i,1);
			//cout<<is_inode_valid(i)<<endl;
			return i;
		}
	}
	//申请失败，内存已满。 
	return 0;
}

//申请数据区逻辑块 
unsigned short apply_logical_valid(){
		for(unsigned short i=sblock.s_ninodes;i<=sblock.s_nzones;i++){
		if(is_logical_valid(i)!=1){
			update_logical_valid(i,1);
			//cout<<is_logical_valid(i)<<endl;
			return i;
		}
	}
	return 0;
}


//添加其父目录文件下的子文件 
bool add_inode_father(unsigned short fat,dir_entry chi){
	struct d_inode inode;
	struct dir_entry dir;
	
	
	if(is_inode_valid(fat) != 1)
		return 0;
	//fat=406;
	get_inode(fat, &inode);
	//cout<<fat<<endl;
	for(int i = 0; i<7; i++)
	{
		//如果数组数据为0，添加新的数据块 
		if(inode.i_zone[i] == 0){
			inode.i_zone[i] = apply_logical_valid();
			memset(logical_block,0,sizeof(logical_block));
			memcpy(&logical_block[2 * sizeof(chi)],(char*)&chi, sizeof(chi));
			write_partition_logical_block(inode.i_zone[i]);
			return 1;
		}
			
		//一个逻辑块最多存储64个目录项,循环读取64个目录项
		//其中前两项分别为 . 和 .. 
		for(int j = 0; j < 64; j++)
		{
			get_partition_logical_block(inode.i_zone[i]);
			//将逻辑块中的数据拷贝到目录项结构体
			memcpy((char*)&dir, &logical_block[j * sizeof(dir)], sizeof(dir));
			//if(j>12)for(int k=0;k<1024;k++)print_char(logical_block[k]);cout<<endl;
			//如果是 .和..则继续循环
			if(j == 0 || j == 1)
				continue;
				
			//如果目录项中没有内容了则不再读取
			
			if(dir.inode == 0){
				//dir_entry new_child = dir_entry(chi.inode,chi.name);
				//cout<<chi.inode<<" "<<j<<endl;
				//for(int k=0;k<4;k++)print_char(logical_block[j*2+k-2]);cout<<endl;
				//for(int k=0;k<sizeof(new_child);k++)logical_block[j*2+k]=((char*)& new_child)[k];
				memcpy(&logical_block[j * sizeof(chi)],(char*)& chi, sizeof(chi));
				
				//write_partition_logical_block(inode.i_zone[i]);
				//if(j>12)for(int k=0;k<1024;k++)print_char(logical_block[k]);cout<<endl;
				//if(j+1<64)memcpy(&logical_block[(j+1) * sizeof(dir)],(char*)&dir, sizeof(dir));
				write_partition_logical_block(inode.i_zone[i]);
				return 1;
			}
				
			
			
			
		}
	}
	cout<<"father_files is fulled\n";
	return 0;
} 


//修改文件大小 
bool update_size_file(unsigned short id,int file_size){
	struct d_inode inode;
	get_inode(id, &inode);
	if(file_size<=7){
		for(int i=0;i<file_size;i++){
			inode.i_zone[i]=apply_logical_valid();
		}
	}else if(file_size<=7+1024/2){
		for(int i=0;i<7;i++){
			inode.i_zone[i]=apply_logical_valid();
		}
		inode.i_zone[7]=apply_logical_valid();
		file_size-=7;
		memset(logical_block,0,sizeof(logical_block));
		unsigned short dete_id[512];
		for(int j = 0; j < file_size; j++){
			dete_id[j]=apply_logical_valid();
			//cout<<dete_id[j]<<endl; 
			//memcpy(&logical_block[j*sizeof(dete_id)], (char*)&dete_id, sizeof(dete_id));
			//print_char(dete_id[0]);cout<<endl;
			//cout<<"\t\t"<<j<<" ";for(int k=0;k<6;k++)print_char(logical_block[k]);cout<<endl;
			//write_partition_logical_block(inode.i_zone[7]);
		}
		
		memcpy(&logical_block[0], (char*)&dete_id[0], sizeof(dete_id[0])*file_size);
		//print_char(dete_id[0]);cout<<endl;
		//cout<<"\t\t"<<sizeof(dete_id[0])*file_size<<" ";for(int k=0;k<6;k++)print_char(logical_block[k]);cout<<endl;
		write_partition_logical_block(inode.i_zone[7]);
	}else if(file_size<=7+512+512*512){
		for(int i=0;i<7;i++){
			inode.i_zone[i]=apply_logical_valid();
		}
		inode.i_zone[7]=apply_logical_valid();
		file_size-=7;
		memset(logical_block,0,sizeof(logical_block));
		unsigned short dete_id[512];
		for(int j = 0; j < file_size; j++){
			dete_id[j]=apply_logical_valid();
			//cout<<dete_id[j]<<endl; 
			//memcpy(&logical_block[j*sizeof(dete_id)], (char*)&dete_id, sizeof(dete_id));
			//print_char(dete_id[0]);cout<<endl;
			//cout<<"\t\t"<<j<<" ";for(int k=0;k<6;k++)print_char(logical_block[k]);cout<<endl;
			//write_partition_logical_block(inode.i_zone[7]);
		}
		
		memcpy(&logical_block[0], (char*)&dete_id[0], sizeof(dete_id[0])*file_size);
		//print_char(dete_id[0]);cout<<endl;
		//cout<<"\t\t"<<sizeof(dete_id[0])*file_size<<" ";for(int k=0;k<6;k++)print_char(logical_block[k]);cout<<endl;
		write_partition_logical_block(inode.i_zone[7]);
		
		inode.i_zone[8]=apply_logical_valid();
		file_size-=(7+1024/2);
		memset(logical_block,0,sizeof(logical_block));
		for(int n1 = 0; n1 < (511+file_size)/512; n1++)
		{
			dete_id[n1]=apply_logical_valid();
			
		}
		memcpy(&logical_block[0],(char*)&dete_id[0] , sizeof(dete_id[0])*(511+file_size)/512);
		//print_char(dete_id[0]);cout<<endl;
		write_partition_logical_block(inode.i_zone[8]);
		
		
		for(int n1 = 0; n1 < (511+file_size)/512; n1++)
		{
			int ma_n2=512;
			if(n1==(511+file_size)/512-1){
				ma_n2=file_size%512;
			}
			memset(logical_block,0,sizeof(logical_block));
			unsigned short dete_id_2[512];
			for(int n2 = 0; n2 < ma_n2; n2++)
			{
				dete_id_2[n2]=apply_logical_valid();
			
			}
			memcpy(&logical_block[0],(char*)&dete_id_2[0] , sizeof(dete_id_2[0])*ma_n2);
			//print_char(dete_id[0]);cout<<endl;
			write_partition_logical_block(dete_id[n1]);
			
		}
		
	}else  return 0;
	write_inode(id, inode);
	return 1;
}

//i节点文件写入内存 
bool write_files_inode(unsigned short id,int type_file,int size_file){
	struct d_inode inode;
	get_inode(id, &inode);
	
	inode.i_mode=(type_file<<12);
	inode.i_uid=0;
	inode.i_size= size_file; 
	//inode.i_time=(long)time(NULL);
	inode.i_time=0;
	inode.i_gid=0;
	inode.i_nlinks=0;
	//cout<<(inode.i_mode>>12)<<endl;
	
	for(int i=0;i<9;i++)inode.i_zone[i]=0;
	//memset(inode.i_zone,0,sizeof(inode.i_zone));
	write_inode(id,inode);
	update_size_file(id,size_file);
	return 1;
}

//判断父目录下是否存在名为 child_name 的文件 
bool find_father_id_child_name(unsigned short id, string child_name)
{
	struct d_inode inode;
	struct dir_entry dir;
	
	//如果i节点号对应在i节点位图相应位的值为1,说明此i节点已使用
	//否则说明此i节点无用或已被删除，则直接返回
	if(is_inode_valid(id) != 1)
		return 0;
		
	get_inode(id, &inode);
	for(int m = 0; m<7; m++)
	{
		//如果数组数据为0，则跳过
		if(inode.i_zone[m] == 0)
			continue;
		for(int n = 0; n < 64; n++)
		{
			get_partition_logical_block(inode.i_zone[m]);
			//将逻辑块中的数据拷贝到目录项结构体
			memcpy((char*)&dir, &logical_block[n * sizeof(dir)], sizeof(dir));
			
			//如果是 .和..则继续循环
			if(n == 0 || n == 1)
				continue;
				
			//如果目录项中没有内容了则不再读取
			if(dir.inode == 0)
				break;
			
			if(new_string(dir.name,NAME_LEN)==child_name){
				return 1;
			}
		}
		
	}
	
	return 0;
}

//创建文件夹
bool built_files(string lur,string files_name){
	unsigned short father_id = find_root_inode(lur,1);//在father_id 节点目录下创建文件 
	if(father_id==0){
		return 0;
	}
	if(find_father_id_child_name(father_id,files_name)){
		cout<<" error: no build "<<files_name<<",  "<<files_name<<" was existed\n";
		return 0;
	} 
	unsigned short inode_id = apply_inode_valid();
	
	char name[NAME_LEN];memset(name,0,sizeof(name));
	for(int i=0;i<files_name.size();i++)name[i]=files_name[i];
	name[files_name.size()]='\0';
	dir_entry new_inode_files = dir_entry(inode_id,name);
	if(!add_inode_father(father_id,new_inode_files))return 0;
	write_files_inode(inode_id,4,0);
	
	inode_father[inode_id]=father_id;
	cout<<"success\n";
	return 1;
} 

//创建普通文件
bool built_file(string lur,string files_name,int file_size){
	unsigned short father_id = find_root_inode(lur,1);//在father_id 节点目录下创建文件 
	
	if(father_id==0){
		return 0;
	}
	if(find_father_id_child_name(father_id,files_name)){
		cout<<" error: no build "<<files_name<<",  "<<files_name<<" was existed\n";
		return 0;
	} 
	unsigned short inode_id = apply_inode_valid();
	
	char name[NAME_LEN];memset(name,0,sizeof(name));
	for(int i=0;i<files_name.size();i++)name[i]=files_name[i];
	name[files_name.size()]='\0';
	dir_entry new_inode_files = dir_entry(inode_id,name);
	if(!add_inode_father(father_id,new_inode_files))return 0;
	write_files_inode(inode_id,8,file_size);
	
	inode_father[inode_id]=father_id;
	cout<<"success\n";
	return 1;
}

//初始化函数 
void init(int argc, char* argv[]){
	
	int bit;
	struct d_inode* inode = (struct d_inode*)malloc(sizeof(struct d_inode));
	
	char* path = "harddisk.img";
	
	if(argc>1)path=argv[1];
	fd = fopen(path, "rb+");
	//fw = fopen(path, "wb");
	if(fd==NULL)
		printf("open file failed!\n");
		
	//读取分区表
	get_partition_table();
	//读取超级块
	get_super_block();
	
	//加载i节点逻辑块位图
	load_inode_bitmap();
	//加载数据逻辑块位图 
	load_logical_bitmap(); 
	//i节点位图的第一位对应文件系统的根节点
	//如果第一位为1，则打印根节点
	bit = is_inode_valid(1);
	if(bit == 1){
		
		print_inode(1, -1, "\\");
		load_inode_father(1,"\\");
	}
	else
		printf("root node lost！\n");
	cout<<"-----------------------------------\n";
}

//文件系统入口 
void solve(){
	string scan;
	string now_file;

	while(true){
		cout<<now_file<<"\/> ";
		cin>>scan;
		if(scan=="exit")break;
		if(scan=="print"){
			cin>>scan;
			print_file(now_file+"/"+scan);
		}else if(scan=="dir"){
			print_file(now_file);
		}else if(scan=="cd"){
			cin>>scan;
			
			if(find_root_inode(now_file,1)){
				now_file += "/"+scan;
				
			}else{
				cout<<"no file\n";
			}
		}else if(scan=="delete"){
			cin>>scan;
			delete_file(now_file+"/"+scan);
		}else if(scan=="build"){
			int type,file_size;
			cin>>scan;cin>>type;
			if(type==8){
				cin>>file_size;
				built_file(now_file,scan,file_size);
			}else if(type==4){
				built_files(now_file,scan);
			}else{
				cout<<"no built type file"<<endl;
			}
		}else{
			cout<<" not commond\n";
		}
		
	}
	
}
int main(int argc, char* argv[])
{
	//freopen("1.out","w",stdout);
	init(argc,argv);

	//solve();
	//print_file("/usr/src/linux-0.11.org/mm/memory.c");
	//print_file("/usr/root/hello.c");
	//delete_file("/usr/root/hello.c");
	//delete_file("/usr/root/shoe");
 	//built_files("/usr/root","dir");
	//print_file("/usr/root/dir");
	//built_file("/usr/root","file.txt",10);
	//print_file("/usr/root/file.txt");
	
	return 0;
}