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?