• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.





In this chapter we will be designing Linux File System. But before we do that, let us first dig deeper into the data structures and algorithms that we would use to design an in-memory file system.

Design In-Memory File System:

Designing an in-memory file system may sound intimidating. But it is not. All design problems can be efficiently handled if you break down the system into small components and think logically and in the most systematic way possible. We will do the same thing with this problem.

We will reach our solution by asking ourselves one or more logical question(s):

  • What are the first few things that come to our mind that are a file system consists of ?
    Files and Folders, right ?

A file system, in its most simplistic version, consists of Files and Folders.

Now lets see what are some of the characteristics of Files and Folders.

Below are some of the characteristics associated with Folders:
  • Name
  • Time the folder was created
  • Time the folder was last updated
  • Folder this folder is in (let's call it Parent Directory)
  • Files and Subfolders that this folder contains
  • Size of the folder
  • Folder can be deleted
  • Path of the folder
  • A Folder can be renamed

Below are some of the characteristics associated with Files:
  • Name
  • Time the file was created
  • Time the file was last updated
  • Folder this file is in (let's call it Parent Directory)
  • File Content
  • Size of the file
  • Files can be deleted
  • Full Path of the File
  • A File can be renamed
Also keep in mind, we often change / replace / append / update content of a file, and in most cases, unless and until the size of the updated content and the old content are the same, the size would also change along with the change in content.

Notice how below are the common charasteristics of both Files and Folders:
  • Name
  • Creation Time
  • Time Last Updated
  • Parent Directory
  • Size
  • Deletion operation
  • Full Path
  • Rename operation
Using all our above discoveries, we would be able to very easily come up with the below Low Level Object Oriented Design:


package FileSystem;

/**
 * Created by Abhishek on 7/31/21.
 */
public abstract class FileSystemUnit {
    protected Folder parentDirectory;
    protected String name;
    protected long creationTime;
    protected long lastUpdated;

    public FileSystemUnit(String name, Folder parent) {
        this.name = name;
        this.parentDirectory = parent;
        creationTime = System.currentTimeMillis();
        lastUpdated = System.currentTimeMillis();
    }

    public abstract int size(); // size of a directory or file

    public boolean delete() {
        if (parentDirectory == null) {
            // if parent is null that would mean
            // it is a root directory.
            // We cannot delete a root directory
            return false;
        }
        return parentDirectory.deleteSubfolderOrFile(this); // delete this from its parent directory
    }

    public String getFullPath() {
        if (parentDirectory == null) {
            return name;
        }
        return parentDirectory.getFullPath();
    }

    public long getCreationTime() {
        return creationTime;
    }

    public long getLastUpdatedTime() {
        return lastUpdated;
    }

    public String getName() {
        return name;
    }

    public void rename(String newName) {
        name = newName;
    }
}




package FileSystem;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Abhishek on 7/31/21.
 */
public class Folder extends FileSystemUnit {

    protected List<FileSystemUnit> listOfSubfoldersAndFiles;

    public Folder(String name, Folder parent) {
        super(name, parent);
        listOfSubfoldersAndFiles = new ArrayList<>();
    }


    public boolean deleteSubfolderOrFile(FileSystemUnit fsu) {
        return listOfSubfoldersAndFiles.remove(fsu);
    }

    public void addASubfolderOrAFile(FileSystemUnit fsu) {
        listOfSubfoldersAndFiles.add(fsu);
    }

    public List<FileSystemUnit> getSubfoldersAndFiles() {
        return listOfSubfoldersAndFiles;
    }

    public int size() { // size including all subfolders and files
        int size = 0;
        for (FileSystemUnit fsu : listOfSubfoldersAndFiles) {
            size = fsu.size();
        }
        return size;
    }

    public int numberOfSubfoldersAndFiles() { // returns number of files in this folder as well as in all its subfolders
        int count = 0;
        for (FileSystemUnit fsu : listOfSubfoldersAndFiles) {
            if (fsu instanceof Folder) { // subfolder
                count++;
                count += ((Folder) fsu).numberOfSubfoldersAndFiles();
            } else { // file
                count++;
            }
        }
        return count;
    }
}




package FileSystem;

/**
 * Created by Abhishek on 7/31/21.
 */
public class File extends FileSystemUnit {
    private String content;
    private int size;

    public File(String name, Folder parent, int size) {
        super(name, parent);
        this.size = size;
    }

    public int size() {
        return size;
    }

    public String getContent() {
        return content;
    }

    public void updateContentAndSize(String content, int size) { // if content changes in most cases size would change too
        this.content = content;
        this.size = size;
    }
}


Design Linux File System:

Now let's get down to coding and design a data structure that simulates a Linux File System.

Implement the FileSystem class:

FileSystem() Initializes the object of the system.

List<String> ls(String path):
  • If path is a file path, returns a list that only contains this file's name.
  • If path is a directory path, returns the list of file and directory names in this directory. The answer should in lexicographic order.

void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.

void addContentToFile(String filePath, String content)
  • If filePath does not exist, creates that file containing given content.
  • If filePath already exists, appends the given content to original content.

String readContentFromFile(String filePath) Returns the content in the file at filePath.



Example:
FileSystem fileSystem = new FileSystem();

fileSystem.ls("/"); // return []

fileSystem.mkdir("/a/b/c");

fileSystem.addContentToFile("/a/b/c/d", "hello");

fileSystem.ls("/"); // return ["a"]

fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

Solution:

If you have studied the chapter on Designing Simple File System, you already know that an efficient way to implement a file system is by using Trie Data Structure.
We will build the solution for this problem by:
  • using the knowledge we gained from Designing Simple File System
  • and by reusing the experience we gained from Low Level Design of In-Memory File System we did earlier in this chapter.


public class FileSystem {
	File root; // trie root

	public FileSystem() {
		root = new File();
	}
    
    public void addContentToFile(String path, String content) {
    	File cur = traverse(path);
		cur.setFile();
		cur.addContent(content);
    }
    
    public String readContentFromFile(String path) {
    	File cur = traverse(path);
		return cur.getContent();
    }

	public void mkdir(String path) {
    	traverse(path);
    }
    
    public List<String> ls(String path) {
		File cur = traverse(path);
		List<String> res = new ArrayList<>();
		if (cur.isFile) {
			res.add(cur.getName());
		} else {
			for (File f : cur.getChildren()) {
				res.add(f.getName());
			}
		}
		Collections.sort(res); // lexicographic order
		return res;
    }

    private File traverse(String path) {
		File cur = root;
		String[] paths = path.split("/");
		for (String p : paths) {
			if (p.isEmpty()) {
				continue;
			}
			if (!cur.contains(p)) {
				File f = new File(p);
				cur.addChild(f);
			}
			cur = cur.getChild(p);
		}
		return cur;
    }

    // find all files in the given path
    private List<String> find(String path) {
		File cur = traverse(path);
		List<String> res = new ArrayList<>();
		return find(cur);
    }

    private List<String> find(File f) {
    	List<String> res = new ArrayList<>();
    	if (f == null) {
    		return res;
    	} else if (f.isFile()) {
    		res.add(f.getName());
    	} else {
    		for (File child : f.getChildren()) {
    			res.addAll(find(child));
    		}
    	}
    	return res;
    }

    // rename the file in a given path, do nothing if the file doesn't exist 
    public void rename(String path, String name) {
		File cur = traverse(path);
		cur.rename(name);
    }
    
    // delete the file in a given path; delete the entire folder if it is a directory; do nothing if it is not a file
    public void delete(String path) {
    	File cur = traverse(path);
		cur.delete();
    }

}

// Trie Node
class File {
	boolean isFile;
	Map<String, File> children;
	File parent;
	String name;
	String content;

	public File() {
		children = new HashMap<>();
		isFile = false;
        content = "";
	}

	public File(String name) {
		this();
		this.name = name;
	}

	public void rename(String name) {
		parent.children.remove(this.name);
		this.name = name;
		parent.addChild(this);
	}

	public String getName() {
		return this.name;
	}

	public void addChild(File f) {
		f.parent = this;
		children.put(f.getName(), f);
	}

	public void removeChild(String s) {
		File child = children.get(s);
		if (child != null) {
			child.parent = null;
		}
		children.remove(s);
	}

	public File getChild(String s) {
		return children.get(s);
	}

	public List<File> getChildren() {
		return new ArrayList<>(children.values());
	}

	public boolean contains(String s) {
		return children.containsKey(s);
	}


	public void addContent(String s) {
		this.content += s;
	}

	public String getContent() {
		return this.content;
	}

	public void setFile() {
		this.isFile = true;
	}

	public boolean isFile() {
		return isFile;
	}

	public void delete() {
		parent.removeChild(name);
	}
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem obj = new FileSystem();
 * List<String> param_1 = obj.ls(path);
 * obj.mkdir(path);
 * obj.addContentToFile(filePath,content);
 * String param_4 = obj.readContentFromFile(filePath);
 */



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave