A file system consists of directories and files allocated to disk blocks. Directories can contain other directories and files. For simplicity we assume that only files occupy disk space. The disk is partitioned in blocks of size 1 KB and blocks are numbered 0, 1, 2,... For simplicity we assume that file size is always an integer and that a file of n KB occupies n disk blocks, not necessarily consecutive.
The top level directory is
called root. You may assume that names of files and directories are
strings which only contain 26 ASCII lower case characters and
numerals 0-9 (in any order, no spaces, no other symbols). The unique
name of a file or directory is an array of strings which describes the
path from the root to the file,
the last string in the array being the file name (see example below).
For example, the full name of file4 is [root,mail,inbox,file4].
added 10/11/06 There can be several things called file4, so long
as they are in different
directories they have different file names.
The methods of the
root
/ | \
/ | \
/ | \
mail docs java
/ \ | \
/ \ file1 (2 KB) \
/ \ \
file0 (3 KB) inbox file2 (2 KB)
/ \
/ \
file3 (1 KB) file4 (1 KB)
block 0 - [root,mail,file0]
block 1 - [root,mail,inbox,file3]
block 2 - [root,mail,file0]
block 3 - [root,docs,file1]
block 4 - [root,mail,file0]
block 5 - [root,mail,inbox,file4]
block 6 - null (this block is free)
block 7 - [root,docs,file1]
block 8 - null
block 9 - [root,java,file2]
block 10 - [root,java,file2]
FileSystemclass are:
FileSystem(int m)intitializes a file system with the empty root directory and m KB of disk blocks.
void file(String[] name, int k)creates the file of size k KB in the directory indicated by the file name, and allocates disk blocks to it. If any of the directories in the file name don't exist, they are also created. If there are not enough free blocks for the file, throws OutOfSpaceException. If the first directory is not root, throws BadFileNameException. You do not have to check that the file name contains only lower case alphanumeric characters. Added 8/11/2006: if the file already exists, removes the old version (de-allocates disk blocks) and creates the new one. If it is a name of an existing directory, throws BadFileNameException. Added 10/11/2006: if the existing file takes less disk space than the version which is being created, and the current version causes OutOfSpaceException, this is thrown without deleting the old version of the file.
void dir(String[] name)creates an empty directory with the given name. Added 8/11/2006: if the directory already exists, does nothing. If there is already a file with the same name or the name of the directory does not start with root, throws BadFileNameException.
void rmfile(String[] name)removes the file and frees the disk space. If the file does not exist does nothing.
void rmdir(String[] name)removes the directory if it does not contain any files, otherwise throws DirectoryNotEmptyException. If the directory does not exist does nothing.
String[] lsdir(String[] name)returns the list of names of files and subdirectories in the directory (short names, e.g. below lsdir([root,mail]) should return [file0,inbox]). If the directory does not exist returns null.
String[][] disk()returns an array where each index corresponds to a disk block and the entry is either null if the block is free or an array of strings which is the name of the file which occupies that block.
You are reminded of the School's Policy on Plagiarism.
Programs will be marked by humans, but I will also run correctness and
timing tests. A simple test harness is available here:
SimpleTest.java Note that it will only
compile if you have the FileSystem class (with at least a dummy implementation
of all methods).
Here is TimingTest.java . On marian, the first timed operation - creating an array of 100000 file names - takes about 300 ms. The second (real) timing test, creating the corresponding files, took about 40 seconds for an inefficient version and about 900 ms for a more efficient one.