Assignment 3
Introduction
COMP2011 Assignment 3: File System
Course Webpage
Copyright By PowCoder代写 加微信 powcoder
The file system
Important requirements
File system tasks
The last task
Memory Leak
Grading scheme
Submission
Change log
Introduction
In this assignment, you will practice pointers and dynamic memory. It is challenging, so you are highly recommended to start early. If you need clarification of the requirements, please feel free to post on the Piazza with the pa3 tag. However, to avoid cluttering the forum with repeated/trivial questions, please do read all the given code, webpage description, sample output, and latest FAQ (refresh this page regularly) carefully before you post your questions. Also please be reminded that we won’t debug any student’s assignment for the sake of fairness.
About academic integrity
We value academic integrity very highly. Please read the Honor Code section on our course webpage to make sure you understand what is considered as plagiarism and what the penalties are. The following are some of the highlights:
Do NOT try your “luck” – we use sophisticated plagiarism detection software to find cheaters. We also review codes for potential cases manually.
The penalty (for BOTH the copier and the copiee) is not just getting a zero in your assignment. Please read the Honor Code thoroughly. Serious offenders will fail the course immediately, and there may be additional disciplinary actions from the department and university, upto and including expulsion.
Download the skeleton codes HERE. Please download and open it now, as we will refer to it from time to time in the description below. We had an introduction session on Apr 22. Here is the zoom recording and the slides.
The file system
In this assignment, you will implement a simple file system. Just like the one in your computer, our file system is a tree of directories and files, where a directory could contain other directories and files, but a file cannot. In file_sys.h, you can find the definition of two structures, Dir and File. These are the two structures that we use to represent directories and files in this assignment. Here are the meanings of their attributes:
Dir* next: a pointer to the next directory in the linked list. File
char name[MAX_NAME_LEN]: the name of the file, it’s a C-string (character array) with a null character at the end. Dir* parent: a pointer to the parent directory.
unsigned int size: the size of the file.
Tag tag: the tag of the file (introduced below).
File* next: a pointer to the next file in the linked list.
You will also find an enumeration type enum Tag{VIDEO, IMAGE, DOC, COMPRESSED, PROGRAM, MUSIC, OTHER}. There are 7 different
tags in this assignment, and each file will have one and only one tag.
Then we use an example to elaborate more on the pointers in Dir and File. The figure below shows a file system from a user’s view (left side) and how it looks in this assignment (right side). We only show the pointers here for simplicity. In this example, the directory “/” has two sub- directories “A”, “B” and one sub-file “C”. Directory “A” is empty, and directory “B” has two sub-files “D” and “E”.
The parent pointer of a directory or a file will always point to the directory which contains it, so here the parent pointers of “A”, “B” and “C” are all pointing to “/”, while the parent pointer of “D” and “E” is pointing to “B”. However, directory “/” is a bit special, it is a root directory. The root directory doesn’t have a parent, just like a root node in the tree doesn’t have a parent node. In this assignment, we let the
parent pointer of the root directory point to itself. This is only applicable to the root directory, any other directories’ parent pointer must point to a different directory. In our file system, there will be one and only one root directory. For any files or directories, if you keep moving to the parent, you should always reach the root directory eventually.
The subfile pointer will point to the first sub-file in the linked list. If there is no sub-file, the pointer will be null. So here the subfile pointer of “/” points to “C”, and the subfile pointer of “B” points to “D”. Directory “A” doesn’t have sub-files, so its subfile pointer is
null. Why “D” is in front of “E” and “A” is in front of “B” in the linked list? This actually depends on how we insert into the linked list and will be introduced in that specific function later.
The subdir pointer is very similar to the subfile pointer. You can just take a look at the subdir pointer of “/”, “A” and “B”.
The next pointer points to the next file or the next directory in a linked list. For example, “A” points “B” and “D” points “E”. If it is the last element in the linked list, the next pointer will naturally be null like “B”, “C” and “E” here. It is also clear that the root directory could never have a sibling directory, so the next pointer of the root directory will always be null.
Finally, you don’t have to worry whether a name is too long, we won’t test any cases with names beyond MAX_NAME_LEN. The name of the root directory is, by convention, always “/”.
Important requirements
There are a few things you CANNOT do. Failure to observe these rules would potentially result in ZERO mark for your assignment. Please carefully check your code before you submit it.
You are NOT allowed to define any global variable, or static variable like static int x. You can only use those provided in the skeleton codes.
You are NOT allowed to include any additional libraries yourself. Everything you need is already included. However, feel free to implement any helper functions you need.
You are NOT allowed to modify any of the given function prototypes including the return types, function names, and parameter lists. (but you can overload them if you want)
File system tasks
There are 8 functions you need to implement in this section which are all file system operations. Implement these functions and your own helper functions in file_sys.cpp.
int createFile(Dir* dir, char* name, unsigned int size, Tag tag)
This function creates new files. It returns an integer status code that indicates the status of running this function. Dir* dir: the newly created file will be placed under this directory.
char* name: the name of the file to be created.
unsigned int size: the size of the file to be created.
Tag tag: the tag of the file to be created.
The newly created file will be added to the head of the linked list. Plus, we have some extra requirements on name (which is also applicable to the next function):
1. thenameofafileordirectoryshouldbeuniqueunderthesameparentdirectory.Thisfunctionwon’tcreatethefileifparameternameis already taken by another file or another directory under dir.
2. thenamecannotbeempty,itshouldcontainatleastonecharacter(notcountingthenullcharacter).
3. thenameshouldonlycontainthesecharacters:A-Z(uppercaseletter),a-z(lowercaseletter),0-9(digit),.(dot),-(minus)and_
(underscore). If the name contains any other characters, it is considered as an illegal name and this function won’t create the file.
4. thenamecannotbe.(asingledot)or..(doubledots).Thesetwonamesarereservedforrepresentingthecurrentdirectoryandthe
parent directory in the command line. If the parameter name is either of these two, it is considered as illegal.
5. thenamecannotstartwith-(minus),itisconsideredasillegal.
It will return:
-1: when the function is not yet implemented. The skeleton codes always return -1, remove that line after you finished this function. 1: when parameter dir or name is null.
2: when the name is illegal.
3: when there is a name conflict with an existing file or directory.
0: when nothing above happens and the file is successfully created.
Except 0, all other status codes indicate an error. When there are more than one error, always return the smallest status code. For example, if dir is null and at the same time name has a conflict, you should still return 1. Functions you may need: strcpy(), strcmp(), strlen().
int createDir(Dir* dir, char* name)
This function creates new directories. It returns an integer status code.
Dir* dir: the newly created directory will be placed under this directory. char* name: the name of the directory to be created.
You should check the name in this function as well by the criteria mentioned in last function (unique, non-empty, leagal, non-keyword, beginning- character). The newly created directory will be added to the head of the linked list. This function will return:
-1: when the function is not yet implemented. The skeleton codes always return -1, remove that line after you finished this function. 1: when parameter dir or name is null.
2: when the name is illegal.
3: when there is a name conflict with an existing file or directory.
0: when nothing above happens and the directory is successfully created.
Again, return the smallest one if there are multiple errors. Functions you may need: strcpy(), strcmp(), strlen().
int deleteFile(Dir* dir, char* name)
This function deletes files. It returns an integer status code. Dir* dir: the parent directory of the file to be deleted. char* name: the name of the file to be deleted.
The dynamic memory allocated for this file object should be released, and the linked list that contains this file object should be correctly updated. This function will return:
-1: when the function is not yet implemented. The skeleton codes always return -1, remove that line after you finished this function. 1: when parameter dir or name is null.
2: when you cannot find a sub-file under dir with this name.
0: when nothing above happens and the file is successfully deleted.
Again, return the smallest one if there are multiple errors.
int deleteDir(Dir* dir, char* name, bool recursive)
This function deletes directories. We add one more parameter recursive. It works like this:
1. Ifthedirectorytobedeletedisempty(nosub-fileandnosub-directory),deleteitnomatterwhatrecursiveis. 2. Otherwise,onlydeleteitwhenrecursiveistrue.
Parameters:
Dir* dir: will search under this directory for the directory to be deleted. char* name: the name of the directory to be deleted.
bool recursive: whether to recursively delete sub-files and sub-directories.
Like last function, you should correctly release dynamic memory and update the linked list. This function will return:
-1: when the function is not yet implemented. The skeleton codes always return -1, remove that line after you finished this function. 1: when parameter dir or name is null.
2: when you cannot find a sub-directory under dir with this name.
3: when the directory is not empty and recursive is false.
0: when nothing above happens and the directory is successfully deleted.
Again, return the smallest one if there are multiple errors.
unsigned int getSize(const Dir* dir)
This function computes and returns the size of a directory. The size of a directory is defined recursively as the sum of the size of all sub-files and sub-directories. The size of an empty directory is 0.
const Dir* dir: the target directory.
int moveFile(File* tgt, Dir* dest)
This function moves files. It returns an integer status code. File* tgt: the target file to be moved.
Dir* dest: the destination directory.
The target file will be removed from the old linked list and added to the head of the new linked list. This function will return:
-1: when the function is not yet implemented. The skeleton codes always return -1, remove that line after you finished this function.
1: when parameter tgt or dest is null.
2: when dest is the parent of tgt, then the moving operation is meaningless, the file should stay at its original position in the linked list. 3: when there is a name conflict (the name of tgt is already taken by something under dest).
0: when nothing above happens and the file is successfully moved.
Again, return the smallest one if there are multiple errors.
int moveDir(Dir* tgt, Dir* dest)
This function moves directories. It returns an integer status code. Dir* tgt: the target directory to be moved.
Dir* dest: the destination directory.
Note that a directory cannot be moved to any of its descendants (a descendant is a sub-directory or a sub-sub-directory or sub-sub-sub …). This is because the descendants will also be moved together with the target, so they cannot be the destination. The target directory will be added to the head of the new linked list. This function will return:
-1: when the function is not yet implemented. The skeleton codes always return -1, remove that line after you finished this function.
1: when parameter tgt or dest is null.
2: when dest is the parent of tgt, then the moving operation is meaningless, the directory should stay at its original position in the linked
3: when there is a name conflict (the name of tgt is already taken by something under dest). 4: when dest is a descendant of tgt, or when dest is tgt.
0: when nothing above happens and the directory is successfully moved.
Again, return the smallest one if there are multiple errors.
const File** filesOfTag(const Dir* dir, Tag tag, unsigned int& length)
This function looks for all the files of a certain tag and returns them in a dynamic array.
const Dir* dir: will search recursively under this directory.
Tag tag: the target tag.
unsigned int& length: an unsigned integer passed by reference. Its value should be the size of the returned dynamic array (number of
elements) after this function returns.
This function returns a dynamic array of pointers. Each pointer here points to a file of the specified tag. Also remember to set length to the correct value. If dir is null or you cannot find any files of that tag, length should be set to 0 and the function should return null. Don’t create a dynamic array with size 0. The order of the pointers doesn’t matter, we will sort your array while grading.
The last task
Here is the last task of this assignment, which is to use the functions above to build a simple command line tool so that you can play with your file system interactively. It is also a tool to help you debug your code. Don’t worry, you only need to finish a very small part, the skeleton codes will take care of the rest. A quick introduction to command line. A command line is a tool where you use commands to interact with your machine. A command is simply a string with certain syntax that asks the machine to do something. It usually starts with the command name followed by some parameters separated by whitespaces.
cmd param1 param2 param3 …
Besides, a command line usually has a status called “working directory”, it is a directory that you are currently at. When you specify a file or a
directory by its name, the command line will usually search for that under the working directory only.
If you don’t modify main.cpp, you can compile and run the program, it will start the command line for you. You can type help and “enter”, then it will show you all the commands and their usages. Please also check the zoom recording of PA3 introduction (held on 22th) if you still have questions.
Your task is to finish the function that handles such commands introduced above. It is in cli.cpp: Dir *execute(Dir* wd, char* rest, bool& exit)
This function contains a lot of if blocks, each block handling one type of command. Some blocks are already implemented, you can regard them as examples to implement the remaining three blocks. In this task you only need the first two function parameters Dir* wd and char* rest, you don’t need to deal with bool& exit and you don’t need to write any return statements. Plus, please don’t write any output statements in this task. You can add some while debugging, but remember to remove them before submission, the three blocks you implement should output nothing to the standard output while grading.
Dir* wd: the working directory.
char* rest: a string of command parameters, like “param1 param2 param3 …”
You will finish three commands: mkdir, rm and mv, they will be used like this:
. and .. will not appeared as input in the test cases, you don’t need to handle them.
We provide you a helper function fetch to easily extract parameters from char* rest. You do it like this:
Memory Leak
Since this assignment is about dynamic memory, it is also important that your program doesn’t have any memory leak. Below is a table specifying the dynamic memory and by whom it should be created and released.
Prepared by: SONG, Sizhe
char name[MAX_NAME_LEN]: the name of the directory, it’s a C-string (character array) with a null character at the end. Dir* parent: a pointer to the parent directory.
Dir* subdir: the head of a linked list that stores the sub-directories.
File* subfile: the head of a linked list that stores the sub-files.
// mkdir
mkdir images // make a directory “images”
// rm [-r]
// “-r” option should only matter when deleting dirs, it determines the “recursive” parameter of “deleteDir(
rm main.cpp
rm -r main.cpp rm images
rm -r images
// remove // remove // remove // remove
“main.cpp” (say it’s a file) “main.cpp” (say it’s a file)
“images” (say it’s a dir)
“images” recursively (say it’s a dir)
// mv
//
mv lecture.pdf download // move “lecture.pdf” (say it’s a file) to “download” mv comp2011 download // move “comp2011” (say it’s a dir) to “download”
// rest == “hello world”;
char param1[MAX_CMD_LEN] = “”; // define an empty string
fetch(rest, param1); // fetch the next parameter into the string you just defined // rest == “world”
// param1 == “hello”
char param2[MAX_CMD_LEN] = “”; // do it again to fetch more parameters
fetch(rest, param2); // rest == “”
// param2 == “world”
char param3[MAX_CMD_LEN] = “”;
fetch(rest, param3);
// rest == “” // param1 == “” …
// fetch from an empty string will give you an empty string
the root directory
other Dir objects File objects
Created by
skeleton codes
skeleton codes / you
skeleton codes / you
Released by
skeleton codes
skeleton codes calling your implemented deleteDir skeleton codes calling your implemented deleteFile skeletoncodes
dynamicarrayreturnedbyfilesOfTag() you anything else you use you
Memory leak checking is done via the -fsanitize=address,leak,undefined option (related documentation here) of a recent g++ compiler on Linux (it won’t work on Windows for the versions we have tested). Check the “Errors” tab (next to “Your Output” tab in the test case details popup) for errors such as memory leak. Other errors/bugs such as out-of-bounds, use-after-free bugs, and some undefined-behavior-related bugs may also be detected. Note that if your program has no errors detected by the sanitizers, then the “Errors” tab may not appear. If you wish to check for memory leak yourself using the same options, you may follow our Checking for memory leak yourself guide.
If your program has any error reported by -fsanitize, you will receive a penalty of 10% of the total score. So, please pay attention to the relevant pre-deadline test cases in ZINC.
Grading scheme
ZINC will grade your submission on some pre-deadline test cases to help you debug. After the deadline, ZINC will release all the test cases and regrade your submission. Also note that each test case is only given at most 5 seconds to run on ZINC. If your program takes more time than that to be done with a test case, ZINC will give you 0 for that. Five seconds should be more than enough for any test cases in this assignment. If your program runs for more than 5 seconds, it is very likely that there is an infinite loop/recursion. For example, if your pointers are messed up, and there is a circular linked list, this could easily trigger an infinite loop/recursion.
The table below gives you a rough idea of the weights of the tasks:
deleteFile & deleteDir
moveFile & moveDir
filesOfTag
command line
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com