CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 4 of 6 · 5 min read

The code

Parse once, then walk.

Every operation starts from the same two helpers. The first turns a path into a clean list of names. The second walks from the root, one name at a time.

private List<String> parts(String path) throws FsException {
    if (path == null || !path.startsWith("/")) throw new FsException("path must start with /: " + path);
    List<String> r = new ArrayList<>();
    for (String p : path.split("/")) {
        if (p.isEmpty() || p.equals(".")) continue;
        if (p.equals("..")) { if (!r.isEmpty()) r.remove(r.size() - 1); }
        else r.add(p);
    }
    return r;
}

private Node find(String path) throws FsException {
    Node cur = root;
    for (String p : parts(path)) {
        if (!(cur instanceof Directory d)) throw new FsException("not a directory: " + cur.path());
        cur = d.kids.get(p);
        if (cur == null) throw new FsException("no such path: " + path);
    }
    return cur;
}

parts cleans the path once, so /docs/work/../archive/./b.txt becomes docs, archive, b.txt. A .. at the root is ignored, as in real systems. After that, every operation is a few lines on top of find.

Creating adds a node under its parent directory:

private void add(String path, Node n) throws FsException {
    List<String> ps = parts(path);
    if (ps.isEmpty()) throw new FsException("cannot create root");
    String last = ps.remove(ps.size() - 1);
    Directory d = dirOf("/" + String.join("/", ps));          // the folder that will hold it
    if (d.kids.containsKey(last)) throw new FsException("already exists: " + path);
    n.parent = d; d.kids.put(last, n); n.modified = ++tick;
}

Read and write refuse a directory, and list gives names in order:

void write(String path, String s) throws FsException {
    Node n = find(path);
    if (!(n instanceof File f)) throw new FsException("is a directory: " + path);
    f.write(s); n.modified = ++tick;
}
List<String> ls(String path) throws FsException {
    Node n = find(path);
    if (n instanceof Directory d) return new ArrayList<>(d.kids.keySet());
    return List.of(n.name);
}

Size is the composite at work. The directory simply adds up its children:

class File extends Node { long size() { return data.length(); } }
class Directory extends Node {
    long size() { long s = 0; for (Node n : kids.values()) s += n.size(); return s; }
}

Move needs care. Before changing anything, it checks that the target folder is not the node itself or one of its descendants, by walking up from the target:

void move(String from, String to) throws FsException {
    Node n = find(from);
    if (n == root) throw new FsException("cannot move root");
    for (Node p = dirOfOrNull(to); p != null; p = p.parent)
        if (p == n) throw new FsException("cannot move a directory into itself");
    ...                                                         // then detach, rename if needed, attach
}

Because a node's name is fixed, a rename makes a copy of the subtree under the new name. A design with a mutable name would only change one field. Say which is chosen and why: a fixed name means the sorted map key and the node name can never disagree.

Find is a recursive walk. Each node checks its own name, and a directory then visits its children.

private void walk(Node n, String suffix, List<String> out) {
    if (n.name.endsWith(suffix) && n != root) out.add(n.path());
    if (n instanceof Directory d) for (Node k : d.kids.values()) walk(k, suffix, out);
}

A run. The tree starts empty.

Step Result
Make /docs, make /docs/work/2026 with parents, create /docs/work/a.txt and write "hello", create /docs/work/2026/b.txt and write "world!!" The tree has two files, of 5 and 7 characters
List /docs/work, read a.txt, size of /docs/work, size of / [2026, a.txt], hello, 12, 12
Find names ending .txt from / /docs/work/2026/b.txt and /docs/work/a.txt
Move /docs/work/2026 to /docs/archive, then list /docs [archive, work], and b.txt reads world!! with the archive size 7
Read /docs/work/../archive/./b.txt world!!. The path is cleaned first
Read /nope/x "no such path: /nope/x"
Read docs "path must start with /: docs"
Read /docs/work/a.txt/zz "not a directory: /docs/work/a.txt"
Make /docs again "already exists: /docs"
Move /docs into /docs/work/inner "cannot move a directory into itself"
Delete / "cannot delete root"
Read /docs "is a directory: /docs"
Delete /docs/archive, then list /docs [work], and the total size is 5

Check yourself: 1. Why does parts run before find? 2. Why does size need no special code for folders of folders? 3. Why does move check the target before changing anything?