COMP2011 Assignment 3: File System

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.

Downloads

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

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.
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):

the name of a file or directory should be unique under the same parent directory. This function won't create the file if parameter name is already taken by another file or another directory under dir.
the name cannot be empty, it should contain at least one character (not counting the null character).
the name should only contain these characters: A-Z (uppercase letter), a-z (lowercase letter), 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.
the name cannot be . (a single dot) or .. (double dots). These two names are reserved for representing the current directory and the parent directory in the command line. If the parameter name is either of these two, it is considered as illegal.
the name cannot start with - (minus), it is considered as illegal.

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:

If the directory to be deleted is empty (no sub-file and no sub-directory), delete it no matter what recursive is.
Otherwise, only delete it when recursive is true.

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 list.
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:

          
            // mkdir <dirname>
            mkdir images       // make a directory "images"

            // rm [-r] <name>
            // "-r" option should only matter when deleting dirs, it determines the "recursive" parameter of "deleteDir()"
            rm main.cpp        // remove "main.cpp" (say it's a file)
            rm -r main.cpp     // remove "main.cpp" (say it's a file)
            rm images          // remove "images" (say it's a dir)
            rm -r images       // remove "images" recursively (say it's a dir)

            // mv <target> <destination>
            // <target> can be either File or Dir
            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"

. 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:

          
            // 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);            // fetch from an empty string will give you an empty string

            // rest == ""
            // param1 == ""
            ...

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.

Item	Created by	Released by
the root directory	skeleton codes	skeleton codes
other `Dir` objects	skeleton codes / you	skeleton codes calling your implemented `deleteDir`
`File` objects	skeleton codes / you	skeleton codes calling your implemented `deleteFile`
dynamic array returned by `filesOfTag()`	you	skeleton codes
anything else you use	you	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:

Task name	Number of pre-deadline test cases	Number of all test cases	Contribution to the total score	Weight of each case
createFile & createDir	14	28	10%	≈ 0.357%
deleteFile & deleteDir	12	22	15%	≈ 0.682%
getSize	2	6	15%	≈ 2.5%
moveFile & moveDir	7	22	20%	≈ 0.909%
filesOfTag	2	6	25%	≈ 4.167%
command line	5	9	15%	≈ 1.667%

There are 42 pre-deadline test cases in total, but you will see 84 in ZINC. Test case #43~#84 is a duplicate of #1~#42. Test case #1~#42 ignores memory leak while #43~#84 checks memory leak with -fsanitize. Say if you pass #2 but fail #44, that means your program has some issues reported by -fsanitize in #2.

Submission

Deadline

23:59:00, May 11 (Wed)

Please submit a zip file containing file_sys.cpp and cli.cpp only to ZINC. ZINC usage instructions can be found here. Friendly reminder: before you submit your code, make sure it complies with all the rules in important requirements. No mark will be given if you violate the rules.

Notes:

You may submit your file multiple times, but only the last submission will be graded. You do NOT get to choose which version we grade. If you submit after the deadline, late penalty will be applied according to the submission time of your last submission.
Submit early to avoid any last-minute problem. Only ZINC submissions will be accepted.
The ZINC server will be very busy on the last day especially in the last few hours, so you should expect you would get the grading result report not-very-quickly. However, as long as your submission is successful, we would grade your latest submission with all test cases after the deadline.
In the grading report, pay attention to various errors reported. For example, under the "make" section, if you see a red cross, click on the STDERR tab to see the compilation errors. You must fix those before you can see any program output for the test cases below.

Make sure you submit the correct file yourself. You can download your own file back from ZINC to verify. Again, we only grade what you uploaded last to ZINC.

Compilation Requirement

It is required that your submissions can be compiled and run successfully in our online autograder ZINC. If we cannot even compile your work, it won't be graded. Therefore, for parts that you cannot finish, just put in dummy/empty implementation so that your whole program can be compiled for ZINC to grade the other parts that you have done.

Late submission policy

There will be a penalty of -1 point (out of a maximum 100 points) for every minute you are late. For instance, since the deadline of the assignment is 23:59:00 on May 11th, if you submit your solution at 1:00:00 on May 12th, there will be a penalty of -61 points for your assignment. However, the lowest grade you may get from an assignment is zero: any negative score after the deduction due to late penalty (and any other penalties) will be reset to zero.

Change log

[Explanation] In moveDir(), if tgt is dest, it should still return 4. Because the targets cannot be the destination. (May 6)
[Explanation] Since many asked about the command line, more details are added to the last task. (Apr 27)
[Explanation] rm -r <filename> is equivalent to rm <filename>. (Apr 27)
[Explanation] You are also allowed to write helper functions in cli.cpp as long as you don't modify the existing parts. Some comments in the skeleton codes tell you to write helper functions in file_sys.cpp, we will not update that, just remember that you can also put helper functions in cli.cpp. (Apr 25)
[Explanation] Any errors reported by -fsanitize will lead to the 10% penalty. Make sure you pass #43~#84 of the pre-deadline cases. (Apr 20)
[Explanation] In the last task, you don't need to handle . and .. as input, they will not be in the test cases. (Apr 20)
[Requirement] One additional requirement on names: names cannot begin with -. (Apr 19)

FAQ

Q: What is the meaning of "under"?
A: If A is under B, that means B is A's parent. For those operations that require actions on the sub-sub-dirs and sub-sub-files ...., instruction will explicitly tell you to do it recursively (deleteDir(), getSize(), filesOfTag()).

Q: My code doesn't work / there is an error, here is the code, can you help me to fix it?
A: As the assignment is a major course assessment, to be fair, you are supposed to work on it on your own and we should not finish the tasks for you. We might provide some very general hints to you, but we shall not fix the problem or debug for you.

Q: My code gives perfect results in my own computer, but it gives a different result on ZINC, why?
A: Usually inconsistent strange result (on different machines/platforms, or even different runs on the same machine) is due to relying on uninitialized hence garbage values, missing return statements, accessing out-of-bound array elements, etc.. You may see the explanations and debugging tips in the notes here.

Page last modified at .

COMP2011 Assignment 3: File System

Introduction

About academic integrity

Downloads

The file system

Important requirements

File system tasks

int createFile(Dir* dir, char* name, unsigned int size, Tag tag)

int createDir(Dir* dir, char* name)

int deleteFile(Dir* dir, char* name)

int deleteDir(Dir* dir, char* name, bool recursive)

unsigned int getSize(const Dir* dir)

int moveFile(File* tgt, Dir* dest)

int moveDir(Dir* tgt, Dir* dest)

const File** filesOfTag(const Dir* dir, Tag tag, unsigned int& length)

The last task

Dir *execute(Dir* wd, char* rest, bool& exit)

Memory Leak

Grading scheme

Submission

Deadline

Compilation Requirement

Late submission policy

Change log

FAQ

`int createFile(Dir* dir, char* name, unsigned int size, Tag tag)`

`int createDir(Dir* dir, char* name)`

`int deleteFile(Dir* dir, char* name)`

`int deleteDir(Dir* dir, char* name, bool recursive)`

`unsigned int getSize(const Dir* dir)`

`int moveFile(File* tgt, Dir* dest)`

`int moveDir(Dir* tgt, Dir* dest)`

`const File** filesOfTag(const Dir* dir, Tag tag, unsigned int& length)`

`Dir execute(Dir wd, char* rest, bool& exit)`