Assignment 1

All changes to the assignment specification and files will be listed here.

• [08/10 10:00] Assignment released
• [09/10 16:30] Fixed minor typo in FsMkfile example
• [14/10 17:00] Added clarification for FsMv - you may assume none of the paths in the src array contain the current working directory
• [14/10 17:00] Slightly changed the marking scheme for correctness - a completely working implementation of Stages 1 and 2 is now worth 80%
• [15/10 01:00] Added an important clarification to the FsPut function and an example demonstrating this clarification
• [17/10 16:20] Slightly improved wording of FsGetCwd
• [18/10 09:00] Added a new method for testing via an interactive program (see the Testing section for details)
• [18/10 14:40] Changed listFile.c slightly so that no colour codes get printed when COLORED is not defined - download the new version here
• [18/10 16:10] Added a usage example for FsGetCwd

Marks

contributes 15% towards your final mark (see Assessment section for more details)

Submit

see the Submission section

Deadline

5pm on Friday of Week 7

Late penalty

1% off the maximum mark for each hour late. For example if an assignment worth 80% was submitted 15 hours late, the late penalty would have no effect. If the same assignment was submitted 24 hours late it would be awarded 76%, the maximum mark it can achieve at that time.

File Systems

A file system is a data structure that an operating system uses to control how data is stored and retrieved. A file system consists mostly of directories (folders) and regular files, and users use file systems to organise their data by creating, deleting, moving and renaming files.

Due to their hierarchical nature, most file systems can be viewed as trees where each node represents a file. Internal nodes (nodes that have at least one child) correspond to directories, while leaves correspond to either regular files or empty directories. Here is an example of a file system:

In this assignment, you'll be implementing an ADT to simulate a simplfied Linux file system. Importantly, the file system will be in-memory, which means no real files are actually created on disk. Instead, you will use structs to simulate files, so these so-called "files" will only exist in RAM and will no longer exist once the program terminates.

Files

In Linux, there are many different types of files: regular files (such as text files, object files and executables), directories (that's right - directories are files), symbolic links, sockets, named pipes, character devices and block devices. In this assignment, you won't need to deal with all of these types of files - you'll only need to handle regular files (specifically, text files) and directories.

Home Directories

File systems usually contain a home directory for each user under the /home directory. For example, /home/jas would be the home directory for the user "jas". In Linux, if you use the cd command without any arguments, you'll be taken to your home directory. To simplify things in this assignment, you won't need to deal with home directories.

Filenames

In Linux, filenames are case sensitive and may contain any character except forward slash (/), which is reserved as the separator between files and directories in a path. To simplify things in this assignment, you can assume that filenames contain only alphanumeric characters, dot (.), hyphen (-) and underscore (_). In this assignment, you may make no assumptions about filename length - filenames can be arbitrarily long.

All directories implicitly contain two files named . (dot) and .. (dot dot). . refers back to the directory itself, while .. refers to the parent directory. These files are hidden, so they will not be listed if you use the ls command without the -a option. In this assignment, most commands (including ls) will not have options.

In Linux, filenames that begin with dot (.) are automatically hidden. In this assignment, you can assume that filenames won't start with ., except for . and .. which are implicitly contained in every directory. This means that you could implement the hidden file feature if you want, but it will not be tested.

Paths

How do we describe the location of files and navigate around the file system? We use paths! A path is a sequence of filenames separated by forward slashes (/). Consecutive forward slashes are treated as if they were a single forward slash. There are two kinds of paths: absolute paths, which begin with a slash and describe the location of a file relative to the root directory (the directory at the top of the file system), and relative paths, which describe a location relative to the current working directory. The current working directory (cwd) is the directory that the program/terminal is currently working from, and can be changed with the cd command.

Here are some examples of absolute paths:

• / - this path refers the root directory.
• /tmp - this path refers to the tmp file under the root directory.
• /tmp/tmp.123 - this path refers to the tmp.123 file which is in the tmp directory, which is in the root directory.
• /tmp//tmp.123 - this also refers to the tmp.123 file in the tmp directory, since consecutive forward slashes are treated as if they were a single forward slash.

Now suppose that the tmp directory in the image below is the current working directory. Here are some examples of relative paths:

• . - this refers to the tmp directory.
• .. - this refers to the parent directory of the tmp directory, i.e. the root directory.
• tmpdir - this refers to the tmpdir file which is in the tmp directory.
• ../bin/ls - this refers to the ls file in the bin directory.
• ../home/jas - this refers to the jas file in the home directory.
• ../../../home/jas - since the parent directory of the root directory is itself, this still refers to the jas file in the home directory.

Note that due to the existence of the files . and .. in every directory and the fact that paths can be absolute or relative, it is possible for many different paths to refer to the same file. For example, in the above file system, the following paths are equivalent:

• /etc/passwd
• ../etc/passwd
• ../etc/./passwd
• ./../../bin/../etc/ssh/../passwd

Therefore, we introduce the notion of a canonical path. The canonical path of a file is the unique absolute path of the file that does not contain . or ... For example, the canonical path of the passwd file in the above image is /etc/passwd.

Path Prefixes

Here we will describe what is meant by a prefix or proper prefix of a path, which are terms used later in the specification.

A path \( P \) is a prefix of a path \( Q \) if \( P \) can be extended by zero or more filenames to obtain \( Q \). For example, the prefixes of the path /home/jas/cs2521/lecs are: /, /home, /home/jas, /home/jas/cs2521 and /home/jas/cs2521/lecs. The prefixes of the path ../cs2521/labs are: .., ../cs2521 and ../cs2521/labs.

A path \( P \) is a proper prefix of a path \( Q \) if \( P \) can be extended by one or more filenames to obtain \( Q \). For example, the proper prefixes of the path /home/jas/cs2521/lecs are: /, /home, /home/jas and /home/jas/cs2521.

Change into the directory you created for the assignment and run the following command:

unzip /web/cs2521/21T3/ass/ass1/downloads/files.zip

If you're working at home, download files.zip by clicking on the above link and then run the unzip command on the downloaded file.

If you've done the above correctly, you should now have the following files:

Makefile

a set of dependencies used to control compilation

Fs.h

the interface to the File System ADT

Fs.c

the implementation of the File System ADT (incomplete)

utility.h

the interface to your utility data structures and functions

utility.c

the implementation of your utility functions

FileType.h

contains the definition of the FileType enum

listFile.c

contains the listFile function, which prints filenames

testFs.c

a main program to test the File System ADT

First, compile the original version of the files using the make command. You'll see that it produces two executables: testFs and testFsColored. If you use the provided listFile function to print out filenames (which we recommend), testFsColored will apply coloring to directory names, which will help you distinguish regular files and directories when running your tests in the terminal. testFs will print uncolored filenames.

Most of your file system implementation will go in Fs.c. Here you may define your own constants, structs and helper functions. We have also provided the files utility.c and utility.h where you can place data structures and functions that you think should go in a separate file. The only files you are allowed to submit are Fs.c, utility.c and utility.h, so all your code must be in these three files.

testFs.c is the main program that you will be using to test your implementation. At the moment it contains only one basic test, but you should add more tests to it. There are many example tests below that you could use.

FsNew

The FsNew function has the signature:

Fs FsNew(void);

This function should allocate and initialise a new struct FsRep, create the root directory for the file system and make the root directory the current working directory. It should then return a pointer to the allocated struct FsRep.

FsGetCwd

The FsGetCwd function has the signature:

void FsGetCwd(Fs fs, char cwd[PATH_MAX + 1]);

This function should put the canonical path of the current working directory into the given cwd array. It can assume that the canonical path of the current working directory is no longer than PATH_MAX characters.

Usage Examples

• Example 1

int main(void) {
	Fs fs = FsNew();
	
	char cwd[PATH_MAX + 1];
	FsGetCwd(fs, cwd);
	printf("cwd: %s\n", cwd);
	
	FsMkdir(fs, "tmp"); // see Stage 1 for FsCd and FsMkdir
	FsCd(fs, "tmp");
	FsGetCwd(fs, cwd);
	printf("cwd: %s\n", cwd);
	
	FsMkdir(fs, "abc");
	FsCd(fs, "abc");
	FsGetCwd(fs, cwd);
	printf("cwd: %s\n", cwd);
}

cwd: /
cwd: /tmp
cwd: /tmp/abc

FsFree

The FsFree function has the signature:

void FsFree(Fs fs);

This function should free all memory associated with the given Fs. You may need to update this function as you work on each stage to free any new data structures that you created.

FsMkdir

The FsMkdir function has the signature:

void FsMkdir(Fs fs, char *path);

The function takes a path and creates a new directory at that path in the given file system. FsMkdir performs roughly the same function as the mkdir command in Linux.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

mkdir: cannot create directory 'labs/lab01': File exists

Usage Examples

• Example 1
• Example 2
• Example 3
• Example 4
• Example 5

int main(void) {
	Fs fs = FsNew();
	
	// this is equivalent to FsMkdir(fs, "tmp"); because initially,
	// the current working directory is the root directory
	FsMkdir(fs, "/tmp");
	
	FsMkdir(fs, "/tmp/tmp.123");
	FsMkdir(fs, "/usr");
	FsMkdir(fs, "/bin");
	
	// see the section for FsTree for details
	FsTree(fs, NULL);
}

/
    bin
    tmp
        tmp.123
    usr

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "/tmp");
	FsMkdir(fs, "tmp");
	FsMkdir(fs, "./tmp");
}

mkdir: cannot create directory 'tmp': File exists
mkdir: cannot create directory './tmp': File exists

int main(void) {
	Fs fs = FsNew();
	
	// see the section for FsMkfile for details
	FsMkfile(fs, "hello.txt");
	
	FsTree(fs, NULL);
	FsMkdir(fs, "hello.txt/world");
	FsMkdir(fs, "html");
	FsMkfile(fs, "html/index.html");
	FsMkdir(fs, "html/index.html/hi");
	FsTree(fs, NULL);
}

/
    hello.txt
mkdir: cannot create directory 'hello.txt/world': Not a directory
mkdir: cannot create directory 'html/index.html/hi': Not a directory
/
    hello.txt
    html
        index.html

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello/world");
}

mkdir: cannot create directory 'hello/world': No such file or directory

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, ".");
	FsMkdir(fs, "..");
}

mkdir: cannot create directory '.': File exists
mkdir: cannot create directory '..': File exists

FsMkfile

The FsMkfile function has the signature:

void FsMkfile(Fs fs, char *path);

The function takes a path and creates a new empty regular file at that path in the given file system. This function does not have a direct equivalent command in Linux, but the closest command is touch, which can be used to create empty regular files, but also has other uses such as updating timestamps.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

Usage Examples

• Example 1
• Example 2
• Example 3
• Example 4
• Example 5

int main(void) {
	Fs fs = FsNew();
	
	// this is equivalent to FsMkfile(fs, "hello.c"); because initially,
	// the current working directory is the root directory
	FsMkfile(fs, "/hello.c");
	
	FsMkfile(fs, "world.c");
	FsMkdir(fs, "/bin");
	FsMkfile(fs, "bin/mkdir");
	FsMkfile(fs, "bin/mkfile");
	
	// see the section for FsTree for details
	FsTree(fs, NULL);
}

/
    bin
        mkdir
        mkfile
    hello.c
    world.c

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "/tmp");
	FsMkfile(fs, "tmp");
	FsMkfile(fs, "./tmp");
}

mkfile: cannot create file 'tmp': File exists
mkfile: cannot create file './tmp': File exists

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello");
	FsTree(fs, NULL);
	FsMkfile(fs, "hello/world");
	FsMkdir(fs, "html");
	FsMkfile(fs, "html/index.html");
	FsMkfile(fs, "html/index.html/hi");
	FsTree(fs, NULL);
}

/
    hello
mkfile: cannot create file 'hello/world': Not a directory
mkfile: cannot create file 'html/index.html/hi': Not a directory
/
    hello
    html
        index.html

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello/world");
}

mkfile: cannot create file 'hello/world': No such file or directory

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, ".");
	FsMkfile(fs, "..");
}

mkfile: cannot create file '.': File exists
mkfile: cannot create file '..': File exists

FsCd

The FsCd function has the signature:

void FsCd(Fs fs, char *path);

The function takes a path which may be NULL.

If the path is not NULL, the function should change the current working directory to that path.

If the path is NULL, it defaults to the root directory (not the home directory, since we do not have home directories in this assignment).

This function roughly corresponds to the cd command in Linux.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

Usage Examples

• Example 1
• Example 2
• Example 3
• Example 4
• Example 5

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "/home");
	FsCd(fs, "home");
	FsMkdir(fs, "jas");
	FsCd(fs, "jas");
	FsMkdir(fs, "cs2521");
	FsCd(fs, "cs2521");
	FsMkdir(fs, "lectures");
	FsMkdir(fs, "tutes");
	FsMkdir(fs, "labs");
	FsTree(fs, NULL);
}

/
    home
        jas
            cs2521
                labs
                lectures
                tutes

int main(void) {
	Fs fs = FsNew();
	FsCd(fs, "."); // does nothing
	FsCd(fs, ".."); // does nothing, since the parent of the root directory is itself
	FsCd(fs, "./.././../."); // also does nothing
	FsMkdir(fs, "tmp");
	FsCd(fs, "tmp");
	FsMkfile(fs, "random.txt");
	FsMkdir(fs, "../bin");
	FsMkdir(fs, "./../home");
	FsTree(fs, NULL);
}

/
    bin
    home
    tmp
        random.txt

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "tmp");
	FsCd(fs, "tmp");
	FsCd(fs, NULL);
	FsMkfile(fs, "hello.txt");
	FsTree(fs, NULL);
}

/
    hello.txt
    tmp

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello");
	FsCd(fs, "hello");
	FsCd(fs, "hello/world");
}

cd: 'hello': Not a directory
cd: 'hello/world': Not a directory

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "tmp");
	FsCd(fs, "bin");
	FsCd(fs, "tmp/dir123");
}

cd: 'bin': No such file or directory
cd: 'tmp/dir123': No such file or directory

FsLs

The FsLs function has the signature:

void FsLs(Fs fs, char *path);

The function takes a path which may be NULL.

If the path is not NULL and refers to a directory, then the function should print the names of all the files in that directory (except for . and ..) in ASCII order, one per line. If the path refers to a regular file, then the function should just print the given path if it exists in the file system.

If the path is NULL, it defaults to the current working directory.

This function roughly corresponds to the ls command in Linux.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

Usage Examples

• Example 1
• Example 2
• Example 3
• Example 4
• Example 5

int main(void) {
	Fs fs = FsNew();
	printf("---\n"); // marker to separate output
	FsLs(fs, "/");
	printf("---\n");
	FsMkfile(fs, "hello.txt");
	FsMkdir(fs, "tmp");
	FsLs(fs, "/");
}

---
---
hello.txt
tmp

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsMkdir(fs, "tmp");
	FsMkfile(fs, "tmp/world.txt");
	FsLs(fs, "hello.txt");
	FsLs(fs, "tmp/world.txt");
	FsLs(fs, "tmp/.././hello.txt");
}

hello.txt
tmp/world.txt
tmp/.././hello.txt

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "tmp");
	FsMkfile(fs, "tmp/hello.txt");
	FsMkfile(fs, "tmp/world.txt");
	FsCd(fs, "tmp");
	FsLs(fs, NULL);
}

hello.txt
world.txt

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello");
	FsLs(fs, "hello/world");
	FsLs(fs, "hello/.");
}

ls: cannot access 'hello/world': Not a directory
ls: cannot access 'hello/.': Not a directory

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "tmp");
	FsLs(fs, "hello");
	FsLs(fs, "tmp/world");
}

ls: cannot access 'hello': No such file or directory
ls: cannot access 'tmp/world': No such file or directory

FsPwd

The FsPwd function has the signature:

void FsPwd(Fs fs);

The function prints the canonical path of the current working directory.

This function roughly corresponds to the pwd command in Linux.

Usage Examples

• Example 1
• Example 2

int main(void) {
	Fs fs = FsNew();
	FsPwd(fs);
	FsMkdir(fs, "home");
	FsCd(fs, "home");
	FsPwd(fs);
	FsMkdir(fs, "jas");
	FsCd(fs, "jas");
	FsPwd(fs);
}

/
/home
/home/jas

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "home");
	FsMkdir(fs, "home/jas");
	FsMkdir(fs, "home/jas/Documents");
	FsCd(fs, "home/jas/Documents");
	FsPwd(fs);
	FsCd(fs, "..");
	FsPwd(fs);
	FsCd(fs, "..");
	FsPwd(fs);
	FsCd(fs, "..");
	FsPwd(fs);
	FsCd(fs, "..");
	FsPwd(fs);
}

/home/jas/Documents
/home/jas
/home
/
/

FsTree

The FsTree function has the signature:

void FsTree(Fs fs, char *path);

The function takes one path which may be NULL.

If the path is NULL, it defaults to the root directory.

If the path is not NULL, it is expected to refer to a directory and the function should print the contents of the directory in a tree-like format (see below).

This function roughly corresponds to the tree command in Linux.

Output Format

The first line of the output should contain the given path if it exists and refers to a directory. The following lines should display all the files under the given directory in ASCII order, one per line, with indentation to show which files are contained under which directories. Indentation should increase by 4 spaces per level. See the Usage Examples section for examples.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

Usage Examples

• Example 1
• Example 2
• Example 3

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsMkfile(fs, "world.txt");
	FsMkdir(fs, "bin");
	FsMkfile(fs, "bin/ls");
	FsMkfile(fs, "bin/pwd");
	FsMkdir(fs, "home");
	FsMkdir(fs, "home/jas");
	FsMkfile(fs, "home/jas/todo.txt");
	FsMkfile(fs, "home/jas/mail.txt");
	FsTree(fs, "/home/jas");
	printf("---\n"); // marker to separate output
	FsTree(fs, NULL);
}

/home/jas
    mail.txt
    todo.txt
---
/
    bin
        ls
        pwd
    hello.txt
    home
        jas
            mail.txt
            todo.txt
    world.txt

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello");
	FsTree(fs, "hello");
	FsTree(fs, "./hello/world");
}

tree: 'hello': Not a directory
tree: './hello/world': Not a directory

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "tmp");
	FsTree(fs, "hello");
	FsTree(fs, "tmp/world");
}

tree: 'hello': No such file or directory
tree: 'tmp/world': No such file or directory

FsPut

The FsPut function has the signature:

void FsPut(Fs fs, char *path, char *content);

The function takes a path and a string, and sets the content of the regular file at that path to the given string. If the file already had some content, then it will be overwritten.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

Usage Examples

• Example 1
• Example 2
• Example 3
• Example 4
• Example 5

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsPut(fs, "./hello.txt", "world\n"); // overwrites existing content
}

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsPut(fs, "hello", "random-message\n");
	FsPut(fs, ".", "random-message\n");
	FsPut(fs, "/", "random-message\n");
}

put: 'hello': Is a directory
put: '.': Is a directory
put: '/': Is a directory

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello");
	FsPut(fs, "hello/world", "random-message\n");
}

put: 'hello/world': Not a directory

int main(void) {
	Fs fs = FsNew();
	FsPut(fs, "hello/world", "random-message\n");
}

put: 'hello/world': No such file or directory

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	char str[] = "hello\n";
	FsPut(fs, "hello.txt", str);
	strcpy(str, "world\n");
	FsCat(fs, "hello.txt"); // see section on FsCat for details
}

hello

FsCat

The FsCat function has the signature:

void FsCat(Fs fs, char *path);

The function takes a path and prints the content of the regular file at that path. This function roughly corresponds to the cat command in Linux.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

Usage Examples

• Example 1
• Example 2
• Example 3
• Example 4

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsCat(fs, "hello.txt");
	FsPut(fs, "./hello.txt", "world\n"); // overwrites existing content
	FsCat(fs, "/hello.txt");
}

hello
world

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsCat(fs, "hello");
	FsCat(fs, ".");
	FsCat(fs, "/");
}

cat: 'hello': Is a directory
cat: '.': Is a directory
cat: '/': Is a directory

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello");
	FsCat(fs, "hello/world");
}

cat: 'hello/world': Not a directory

int main(void) {
	Fs fs = FsNew();
	FsCat(fs, "hello/world");
}

cat: 'hello/world': No such file or directory

FsDldir

The FsDldir function has the signature:

void FsDldir(Fs fs, char *path);

The function takes a path which is expected to refer to a directory and deletes the directory if and only if it is empty. This function roughly corresponds to the rmdir command in Linux.

For simplicity, you may assume that the given path does not contain the current working directory. Note that this means that the given path will never be the root directory. You can handle this situation if you want (for completeness' sake), but it will not be tested.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

Usage Examples

• Example 1
• Example 2
• Example 3
• Example 4

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsMkdir(fs, "hello/world");
	FsTree(fs, NULL);
	printf("---\n"); // marker to separate output
	FsDldir(fs, "hello/world");
	FsDldir(fs, "hello");
	FsTree(fs, NULL);
}

/
    hello
        world
---
/

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsMkdir(fs, "hello/world");
	FsDldir(fs, "hello");
	FsTree(fs, NULL);
}

dldir: failed to remove 'hello': Directory not empty
/
    hello
        world

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello");
	FsDldir(fs, "hello/world");
}

dldir: failed to remove 'hello/world': Not a directory

int main(void) {
	Fs fs = FsNew();
	FsDldir(fs, "hello/world");
}

dldir: failed to remove 'hello/world': No such file or directory

FsDl

The FsDl function has the signature:

void FsDl(Fs fs, bool recursive, char *path);

The function takes a path and deletes the file at that path. By default, the function refuses to delete directories; it will only delete a directory (and all of its contents recursively) if recursive is true. If the path refers to a regular file, then the recursive argument is irrelevant. This function roughly corresponds to the rm command in Linux, and recursive being true corresponds to the -r option being used in the rm command.

For simplicity, you may assume that the given path does not contain the current working directory. Note that this means that the given path will never be the root directory. You can handle this situation if you want (for completeness' sake), but it will not be tested.

Errors

You must handle the following errors and produce error messages exactly as shown here. If multiple errors apply, only print an error message for the first error from the table that applies.

Usage Examples

• Example 1
• Example 2
• Example 3
• Example 4

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsMkfile(fs, "hello/world.txt");
	FsMkfile(fs, "abc.txt");
	FsTree(fs, NULL);
	printf("---\n"); // marker to separate output
	FsDl(fs, true, "abc.txt");
	FsTree(fs, NULL);
	printf("---\n"); // marker to separate output
	FsDl(fs, true, "hello");
	FsTree(fs, NULL);
}

/
    abc.txt
    hello
        world.txt
---
/
    hello
        world.txt
---
/

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsDl(fs, false, "hello");
}

dl: cannot remove 'hello': Is a directory

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello");
	FsDl(fs, false, "hello/world");
}

dl: cannot remove 'hello/world': Not a directory

int main(void) {
	Fs fs = FsNew();
	FsDl(fs, false, "hello/world");
}

dl: cannot remove 'hello/world': No such file or directory

FsCp

The FsCp function has the signature:

void FsCp(Fs fs, bool recursive, char *src[], char *dest);

The function takes a NULL-terminated array of paths src and a path dest. If the src array contains exactly one path, then it should copy the file at src to dest. If the src array contains more than one path, then dest is expected to refer to a directory, and the function should copy all the files at the paths in the src array to the directory at dest. By default, the function does not copy directories - it should only copy directories if recursive is true.

This function roughly corresponds to the cp command in Linux.

Errors

If you experiment with the cp command in Linux, you will find that many different errors are possible (more than 10). Since we don't want the focus of the assignment to be on handling errors, you can assume that the arguments given to FsCp will not result in an error. However, we've provided a list of possible error messages for your curiosity:

Usage Examples

We've provided examples where the src array contains exactly one path.

• Example 1
• Example 2
• Example 3
• Example 4
• Example 5

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsMkfile(fs, "world.txt");
	FsPut(fs, "world.txt", "world\n");
	FsCat(fs, "world.txt");
	printf("---\n");
	char *src[] = { "hello.txt", NULL };
	FsCp(fs, false, src, "world.txt");
	FsCat(fs, "world.txt");
	printf("---\n");
	FsTree(fs, NULL);
}

world
---
hello
---
/
    hello.txt
    world.txt

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsMkdir(fs, "world");
	FsTree(fs, NULL);
	printf("---\n");
	char *src[] = { "hello.txt", NULL };
	FsCp(fs, false, src, "world");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "world/hello.txt");
}

/
    hello.txt
    world
---
/
    hello.txt
    world
        hello.txt
---
hello

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsMkdir(fs, "world");
	FsMkfile(fs, "world/hello.txt");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "world/hello.txt");
	printf("---\n");
	char *src[] = { "hello.txt", NULL };
	FsCp(fs, false, src, "world");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "world/hello.txt");
}

/
    hello.txt
    world
        hello.txt
---
---
/
    hello.txt
    world
        hello.txt
---
hello

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsMkfile(fs, "hello/a.txt");
	FsTree(fs, NULL);
	printf("---\n");
	char *src[] = { "hello", NULL };
	FsCp(fs, true, src, "world");
	FsTree(fs, NULL);
}

/
    hello
        a.txt
---
/
    hello
        a.txt
    world
        a.txt

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsMkfile(fs, "hello/a.txt");
	FsMkdir(fs, "world");
	FsTree(fs, NULL);
	printf("---\n");
	char *src[] = { "hello", NULL };
	FsCp(fs, true, src, "world");
	FsTree(fs, NULL);
}

/
    hello
        a.txt
    world
---
/
    hello
        a.txt
    world
        hello
            a.txt

We leave you to determine the specific behaviour when the src array contains more than one path. You can do this by experimenting with the cp command in Linux - the behaviour of your file system should mimic what Linux does.

FsMv

The FsMv function has the signature:

void FsMv(Fs fs, char *src[], char *dest);

The function takes a NULL-terminated array of paths src and a path dest. It should move all the files referred to by paths in src to dest.

This function roughly corresponds to the mv command in Linux.

For example, consider the file system shown in the Background section. If the bin directory is moved to the tmp directory, then the file system would now look like:

This move would be achieved by the following piece of code in testFs.c:

char *src[] = { "/bin", NULL };
FsMv(fs, src, "/tmp");

For simplicity, you may assume that none of the files referred to by paths in src are the same as or contain the current working directory.

Errors

Like in Stage 3, to keep the focus on the implementation, you can assume that the arguments given to FsMv will not result in an error. However, for your curiosity, here are some of the possible errors that you could get from the Linux mv command:

Like in Stage 3, we've provided examples where the src array contains exactly one path. It is up to you to determine the correct behaviour when the src array contains multiple paths by experimenting with the Linux mv command.

• Example 1
• Example 2
• Example 3
• Example 4
• Example 5

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsTree(fs, NULL);
	printf("---\n");
	char *src[] = { "hello.txt", NULL };
	FsMv(fs, src, "world.txt");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "world.txt");
}

/
    hello.txt
---
/
    world.txt
---
hello

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsMkfile(fs, "world.txt");
	FsPut(fs, "world.txt", "world\n");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "hello.txt");
	FsCat(fs, "world.txt");
	printf("---\n");
	char *src[] = { "hello.txt", NULL };
	FsMv(fs, src, "world.txt");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "world.txt");
}

/
    hello.txt
    world.txt
---
hello
world
---
/
    world.txt
---
hello

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsMkdir(fs, "world");
	FsTree(fs, NULL);
	printf("---\n");
	char *src[] = { "hello.txt", NULL };
	FsMv(fs, src, "world");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "world/hello.txt");
}

/
    hello.txt
    world
---
/
    world
        hello.txt
---
hello

int main(void) {
	Fs fs = FsNew();
	FsMkfile(fs, "hello.txt");
	FsPut(fs, "hello.txt", "hello\n");
	FsMkdir(fs, "world");
	FsMkfile(fs, "world/hello.txt");
	FsPut(fs, "world/hello.txt", "world\n");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "hello.txt");
	FsCat(fs, "world/hello.txt");
	printf("---\n");
	char *src[] = { "hello.txt", NULL };
	FsMv(fs, src, "world");
	FsTree(fs, NULL);
	printf("---\n");
	FsCat(fs, "world/hello.txt");
}

/
    hello.txt
    world
        hello.txt
---
hello
world
---
/
    world
        hello.txt
---
hello

int main(void) {
	Fs fs = FsNew();
	FsMkdir(fs, "hello");
	FsMkfile(fs, "hello/a.txt");
	FsMkdir(fs, "world");
	FsMkdir(fs, "world/hello");
	FsTree(fs, NULL);
	printf("---\n");
	char *src[] = { "hello", NULL };
	FsMv(fs, src, "world");
	FsTree(fs, NULL);
}

/
    hello
        a.txt
    world
        hello
---
/
    world
        hello
            a.txt

You are mostly free to implement your file system however you choose, and you can use whatever data structures you believe will be useful. This is how we will answer questions like "how should we implement the assignment?", as we prefer not to hinder creativity by hinting at specific methods. However if you still are unsure, remember from the Background section that file systems are typically viewed as trees, and the main difference between file system trees and the binary trees you have seen in lectures is that the "nodes" of file system trees can have an arbitrary number of children.

There are just a few restrictions, which is that your in-memory file system is not permitted to create any external files, start any new programs or communicate with external programs. Everything should be done in memory.

Debugging is an important and inevitable aspect of programming. We expect everyone to have an understanding of basic debugging methods, including using print statements, knowing basic GDB commands and running Valgrind. In the forum and in help sessions, tutors will expect you to have made a reasonable attempt to debug your program yourself using these methods before asking for help, and you should be able to explain what you found during your debugging attempts.

You can learn about GDB and Valgrind in the Debugging with GDB and Valgrind lab exercise.

We have provided a program testFs.c that you can modify to test your File System ADT. This is the recommended way to test your code. Here, we supply an additional testing program which allows you interact with your file system in the terminal.

To download the files for this, run the following command:

unzip /web/cs2521/21T3/ass/ass1/downloads/cli.zip

If you're working at home, download cli.zip by clicking on the above link and then run the unzip command on the downloaded file.

cli.zip includes an updated Makefile and mimFs.c, a main program that provides a command-line interface to the File System ADT.

• Are we allowed to use helper functions? Of course.
• The specification states that we can assume something. Do we need to check whether this assumption is satisfied? No. If the specification says you can assume something, it means you don't need to check it.
• What other errors do we need to check for? The only errors you need to handle are the errors given in the tables under each function. This means besides these errors, you can assume that the arguments given to each function are valid. For example, you can assume that the path argument given to FsMkdir is not NULL, because it would not make sense for it to be NULL. You can also assume that any paths given to functions are not empty, because it would not make sense for them to be empty. We rely on your judgement to determine what makes sense and what doesn't.
• Will we be assessed on our tests? No. You will not be submitting testFs.c or any other test files, and therefore you will not be assessed on them.
• Are we allowed to share tests? No. Testing and coming up with test cases is an important part of software design. Students that test their code more will likely have more correct code, so to ensure fairness, each student should independently develop their own tests.

You need to submit three files: Fs.c, utility.c and utility.h. You can submit via the command line using the give command:

give cs2521 ass1 Fs.c utility.c utility.h

or you can submit via WebCMS. You may not submit any other files. You can submit multiple times. Only your last submission will be marked. You can check the files you have submitted here.

Note that you must submit utility.c and utility.h, even if you did not use them.

Importantly, you must ensure that your final submission compiles on CSE machines. Submitting non-compiling code leads to extra administrative overhead and will result in a 10% penalty.

This assignment will contribute 15% to your final mark.

Correctness

80% of the marks for this assignment will be based on the correctness of the code you write in Fs.c, and will be based on autotesting. Marks for correctness will be awarded roughly according to the below scheme.

Additionally, you must ensure that your code does not contain memory errors or leaks, as code that contains memory errors is unsafe and it is bad practice to leave memory leaks in your program. Note that our tests will always call FsFree at the end of the program to free all memory associated with the file system. Submissions that contain memory errors or leaks will receive a penalty of 10% of the correctness mark. Specifically, there will be a separate memory error/leak check for each stage, and the penalty will be 10% of the marks for that stage. You can check for memory errors and leaks with the valgrind command:

valgrind -q --leak-check=full ./testFs > /dev/null

A program that contains no memory errors or leaks will produce no output from this command. You can learn more about memory errors and leaks in the Debugging with GDB and Valgrind lab exercise.

Style

20% of the marks for this assignment will come from hand marking of the readability of the code you have written. These marks will be awarded on the basis of clarity, commenting, elegance and style. The following is an indicative list of characteristics that will be assessed, though your program will be assessed wholistically so other characteristics may be assessed too (see the style guide for more details):

• Consistent and sensible indentation and spacing
• Using blank lines and whitespace
• Using functions to avoid repeating code
• Decomposing code into functions and not having overly long functions
• Using comments effectively and not leaving planning or debugging comments

The course staff may vary the assessment scheme after inspecting the assignment submissions but it will remain broadly similar to the description above.

This is an individual assignment. The work you submit must be your own work and only your work apart from exceptions below. Joint work is not permitted. At no point should a student read or have a copy of another student's assignment code.

You may use small amounts (< 10 lines) of general purpose code (not specific to the assignment) obtained from sites such as Stack Overflow or other publicly available resources. You should clearly attribute the source of this code in a comment with it.

You are not permitted to request help with the assignment apart from in the course forum, help sessions or from course lecturers or tutors.

Do not provide or show your assignment work to any other person ( including by posting it on the forum) apart from the teaching staff of COMP2521. When posting on the course forum, teaching staff will be able to view the assignment code you have recently submitted with give.

The work you submit must otherwise be entirely your own work. Submission of work partially or completely derived from any other person or jointly written with any other person is not permitted. The penalties for such an offence may include negative marks, automatic failure of the course and possibly other academic discipline. Assignment submissions will be examined both automatically and manually for such issues.

Relevant scholarship authorities will be informed if students holding scholarships are involved in an incident of plagiarism or other misconduct. If you knowingly provide or show your assignment work to another person for any reason, and work derived from it is submitted you may be penalised, even if the work was submitted without your knowledge or consent. This may apply even if your work is submitted by a third party unknown to you.