300字范文 > Nachos文件系统目录树实现

Nachos文件系统目录树实现

时间：2024-05-21 18:01:56

相关推荐

Nachos文件系统目录树实现

扩展Nachos的文件系统

实验任务

拓展（选做）：目前Nachos文件系统仅仅实现了单级目录结构，只有一个根目录。可以尝试采用目录树对文件进行管理。

设计思路

整体思路

在数据结构课设中，实现过带父结点指针的兄弟链表所实现的目录树，但是阅读Nachos代码，发现目录节点是DirectoryEntry并且在一开始初始化目录的时候，是以数组的形式初始化的，这样就不好进行像链表那样的动态新建目录或者文件的操作，也没法像链表一样索引关联节点。但是可以使用模拟指针的思想，以下标作为索引值，来找到某个文件/目录的父目录、左孩子、以及兄弟结点，从而能够遍历整颗树。

按照上面的思路进行编程发现，不需要那么强的拓展功能，所以不采用兄弟链表作为数据结构了，而是采用带模拟指针的多叉树数据结构来实现目录树和多级目录，并且使用graphviz+dot 可视化目录树。

修改DirectoryEntry

首先修改DirectoryEntry，加入两个模拟指针以及孩子数的记录如下

class DirectoryEntry {public:bool inUse; // Is this directory entry in use?int sector; // Location on disk to find the // FileHeader for this file char name[FileNameMaxLen + 1]; // Text name for file, with +1 for // the trailing '\0'int parent; // father dir 's indexint Child_Num; // dir's child numint children[MaxDirChildNUm]; // dir's children// bool filetype; // 0文件 1目录};

Directory 的构造函数

在Directory 的构造函数中，设置0目录项是根目录Root，初始化的相关信息。他的父节点为-1，即没有，且children全为-1，即未分配。

Directory::Directory(int size){table = new DirectoryEntry[size];tableSize = size;for (int i = 0; i < tableSize; i++){table[i].inUse = FALSE;// updatetable[i].Child_Num = 0;table[i].parent = 0;for(int j = 0; j < MaxDirChildNUm; j ++){table[i].children[j] = -1;}}// set table[0] as roottable[0].parent = -1;table[0].inUse = TRUE;}

Directory::Add

阅读代码发现，在目录中，真正在cp命令时发挥作用的是FindIndex 以及 Add函数，首先修改Add函数

思路：

看文件是否存在

分割路径(因为可能是多级目录路径)

找到要添加的节点的父节点

加入新节点并且更新新节点信息

更新父节点信息

代码

boolDirectory::Add(char *name, int newSector){ // My Code// 1. Judge whether file is alread existsif (FindIndex(name) != -1)return FALSE;// 2. Split the pathstring copy_name = name;// Split it from the last file// For example: dir1/dir2/dir3/file cut into:<dir1/dir2/dir3,file>int cutpos = -1;// Seek Cut Positionfor(int i=0;i<copy_name.length();i++)if(copy_name[i] == '/')cutpos = i;string ParentDir = "";string ChildName = "";for(int i=0;i<cutpos;i++)ParentDir+=copy_name[i];for(int i=cutpos+1;i<copy_name.length();i++)ChildName += copy_name[i];// 3. Find ParentDir's ID // Initially set it = rootint ParentDirId = 0;// Maybe ParentDir is emptyif(ParentDir.length() > 0){// Limit 100 levelchar cstrParentName[1000];strcpy(cstrParentName , ParentDir.c_str());ParentDirId = FindIndex(cstrParentName);}// 4. Add new node in DirTable, and add info into Table Treefor(int i=1;i<tableSize;i++){// find a empty DirEntry if(!table[i].inUse){// Set attributestable[i].inUse = TRUE;table[i].sector = newSector;table[i].parent = ParentDirId;table[i].Child_Num = 0;// Renamefor(int j=0;j<FileNameMaxLen;j++){if(j<ChildName.length())table[i].name[j] = ChildName[j];elsetable[i].name[j] = '\0';}// Update parent's infotable[ParentDirId].children[table[ParentDirId].Child_Num] = i;table[ParentDirId].Child_Num++;printf("Add File/Dir Successly\n");return TRUE;}}return FALSE;}

修改FindIndex

修改FindIndex函数使其能够正确根据多级路径查找目录表项

思路

检查是否DISK初始化(即存在根目录)

分割路径

从上到下进行扫描，匹配路径名称直到找到最后一个文件/目录

代码

intDirectory::FindIndex(char *name){// origin code/*for (int i = 0; i < tableSize; i++)if (table[i].inUse && !strncmp(table[i].name, name, FileNameMaxLen))return i;return -1;// name not in directory*/// My updated code// List();// 1. Check whether there is dir or file from rootif(table[0].Child_Num <= 0){printf("No dir or file from root\n");return -1;}// 2. Split the multi pathvector<string> PathTable = SplitPath(name);// 3. Find the first root dir ForExample : dir1/dir2/dir3/txt// We need to find dir1 firstly // to scanstring scandir = PathTable[0];// index of the first dirint firstDirIndex = -1;for(int i = 0; i < table[0].Child_Num; i ++){int index = table[0].children[i];// judge inuseif(!table[index].inUse)continue;// judge Name Equalbool issame = JudgeNameEqual(scandir,index,table);if(issame){firstDirIndex = index;break;}}// check validif(firstDirIndex == -1)return -1;// 4. From up to bottom scan the Tree and match// To find final parent dir// maybe just one dirif(PathTable.size() == 1)return firstDirIndex;// multi dir// and parent Id is the parent of target file (which means target dir)int parentId = firstDirIndex;// scan multi dir to match namefor(int i = 1; i < PathTable.size(); i ++){// find flag bool isfind = FALSE;// scan this level's child to matchfor(int j = 0; j < table[parentId].Child_Num; j++){// In this level, current scan IDint currentId = table[parentId].children[j];// check inuseif(!table[currentId].inUse)continue;// check namebool issame = JudgeNameEqual(PathTable[i],currentId,table);if(issame){// we find the next dirisfind = true;// record the last dir in parentIdparentId = currentId;break;}}// Find Failedif(!isfind)return -1;} printf("Successfully Find: %s",parentId);// return the parent Dirreturn parentId; }

List

为了展示目录树，修改List代码

思路

从table[0] 即根目录开始向下遍历，迭代输出所有文件和目录的名称

代码

voidDirectory::List(){// My codes:// List all the file names in dirprintf("Directory Contents:\n");printf("/root\n");// from the rootfor(int i=1;i<tableSize;i++){// check ustif(table[i].inUse){// compose name and pathvector<string> PathTable;int index = i;// find the parentswhile(table[index].parent != -1){string tmp = table[index].name;PathTable.push_back(tmp);index = table[index].parent;}// cout the pathprintf("/root");for(int j = PathTable.size() - 1; j >= 0; j --){printf( "/");cout << PathTable[j];}printf("\n");}}}

Print

修改Print函数使-D 指令能够正常执行

思路

从上到下进行层次遍历，名字记录在vector里，然后输出

代码

voidDirectory::Print(){ // My CodesFileHeader *hdr = new FileHeader;printf("Directory contents:\n");for (int i = 0; i < tableSize; i++){if (table[i].inUse) {vector<string> PathTable;int index = i;// not to rootwhile(table[index].parent != -1){string temp = table[index].name;PathTable.push_back(temp);index = table[index].parent;}printf("Name: /root");// the next pathfor(int j=PathTable.size()-1;j>=0;j--){printf("/");cout<<PathTable[j];}printf("\n");printf("Sector: %d\n",table[i].sector);hdr->FetchFrom(table[i].sector);hdr->Print();}}printf("\n");delete hdr;}

Remove

重写Remove函数，使其能够正常删除多级目录，并且能够递归删除含有文件或者目录的目录

思路

根据多级目录找到该文件修改目录表项的InUse信息更新有关父节点的信息如果删除的是目录，递归删除该目录所有内容

代码

boolDirectory::Remove(char *name){ // MY codes:int i = FindIndex(name);// name not in directoryif (i == -1)return FALSE; // clean dir table set falsetable[i].inUse = FALSE;// Update parentint parentId = table[i].parent;// Until Roorif(parentId != -1){// record other child except Ivector<int> tempChild;for(int j=0;j<table[parentId].Child_Num;j++)// Find other Childif(table[parentId].children[j] != i)tempChild.push_back(table[parentId].children[j]);// Rebuild parent's children arrayfor(int j=0;j<tempChild.size();j++)table[parentId].children[j] = tempChild[j];// update ChildNumtable[parentId].Child_Num--;}// Delete i's childrenfor(int j=0;j<table[i].Child_Num;j++){int index = table[i].children[j];if(table[index].inUse){table[index].inUse = FALSE;table[index].Child_Num = 0;DeteleChildren(index);}}return TRUE;

递归删除子目录或者子文件DeteleChildren

//---------------------------------------------------------------------// Directory::DeteleChildren//// "name" -- the file name to be removed//----------------------------------------------------------------------void Directory::DeteleChildren(int i){for(int j = 0; j < table[i].Child_Num; j ++){int index = table[i].children[j];if(table[index].inUse){table[index].inUse = FALSE;table[index].Child_Num = 0;DeteleChildren(index);}}}

可视化

(1) 增加 -V 参数代表visualize Catalog Tree

(2) 在filesys 添加相应成员函数

以及

//---------------------------------------------------------------------// FileSystem::VisualTree// Visual CataLog TRee//---------------------------------------------------------------------voidFileSystem::VisualTree(){Directory *directory = new Directory(NumDirEntries);directory->FetchFrom(directoryFile);directory->VisualCataLogTree();delete directory;}

(3) 在目录类中加入可视化函数:

思路

使用graphviz + dot 作图ofstream写出到文件dot代码通过层次遍历添加dot代码系统执行进行作图

代码

//--------------------------------------------------------------------// Directory::VisualCataLogTree// VisualCataLogTree//--------------------------------------------------------------------void Directory::VisualCataLogTree(){ofstream fout;fout.open("VisualCataLogTree.dot");fout<<"strict digraph s{\n";fout<<"root[shape=record,color=green];\n";for(int i=0;i<tableSize;i++){if(table[i].inUse){int index = i;vector<string> PathTable;while(table[index].parent != -1){string s = table[index].name;PathTable.push_back(s);index = table[index].parent;}PathTable.push_back("root");for(int j=PathTable.size()-1;j>=1;j--)fout<<PathTable[j] << " -> "<<PathTable[j-1]<<";\n";}}fout<<"}\n";fout.close();system("dot -Tpng VisualCataLogTree.dot -o VisualCataLogTree.png");return ;}

完成！

测试CataLogTree

修改宏定义

在directory.h

#define MaxDirChildNUm 20 // the number of child that a dir can have

使得最多有20个孩子

在中

#define NumDirEntries 20

使得目录表可以有20项，最多20个文件+目录

测试cp命令

执行如下代码

rm DISK./nachos -f./nachos -cp test/small /file1./nachos -cp test/empty /dir1./nachos -cp test/empty /dir12./nachos -cp test/medium /file2./nachos -cp test/medium /dir1/file21./nachos -cp test/empty /dir1/dir2./nachos -cp test/small /dir1/file22./nachos -cp test/small /dir12/file121./nachos -cp test/empty /dir12/dir21./nachos -cp test/small /dir12/file122