summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorYorhel <git@yorhel.nl>2021-07-26 14:03:08 +0200
committerYorhel <git@yorhel.nl>2021-07-26 14:03:10 +0200
commit36bc405a69797b796348a8b6b64b15725f887f4f (patch)
tree1768d4050dea29c9ec7ba83e113836fb9f08bd15
parentb94db184f415c7df9198d37d2a28c743b63f56c0 (diff)
Add parent node pointers to Dir struct + remove Parents abstraction
While this simplifies the code a bit, it's a regression in the sense that it increases memory use. This commit is yak shaving for another hard link counting approach I'd like to try out, which should be a *LOT* less memory hungry compared to the current approach. Even though it does, indeed, add an extra cost of these parent node pointers.
-rw-r--r--src/browser.zig51
-rw-r--r--src/delete.zig22
-rw-r--r--src/main.zig3
-rw-r--r--src/model.zig199
-rw-r--r--src/scan.zig106
5 files changed, 153 insertions, 228 deletions
diff --git a/src/browser.zig b/src/browser.zig
index a485bc4..e09071b 100644
--- a/src/browser.zig
+++ b/src/browser.zig
@@ -10,8 +10,8 @@ const ui = @import("ui.zig");
const c = @cImport(@cInclude("time.h"));
usingnamespace @import("util.zig");
-// Currently opened directory and its parents.
-pub var dir_parents = model.Parents{};
+// Currently opened directory.
+pub var dir_parent: *model.Dir = undefined;
// Sorted list of all items in the currently opened directory.
// (first item may be null to indicate the "parent directory" item)
@@ -44,12 +44,12 @@ const View = struct {
fn save(self: *@This()) void {
self.cursor_hash = if (dir_items.items.len == 0) 0
else hashEntry(dir_items.items[cursor_idx]);
- opened_dir_views.put(@ptrToInt(dir_parents.top()), self.*) catch {};
+ opened_dir_views.put(@ptrToInt(dir_parent), self.*) catch {};
}
- // Should be called after dir_parents or dir_items has changed, will load the last saved view and find the proper cursor_idx.
+ // Should be called after dir_parent or dir_items has changed, will load the last saved view and find the proper cursor_idx.
fn load(self: *@This(), sel: ?*const model.Entry) void {
- if (opened_dir_views.get(@ptrToInt(dir_parents.top()))) |v| self.* = v
+ if (opened_dir_views.get(@ptrToInt(dir_parent))) |v| self.* = v
else self.* = @This(){};
cursor_idx = 0;
for (dir_items.items) |e, i| {
@@ -123,7 +123,7 @@ fn sortDir(next_sel: ?*const model.Entry) void {
}
// Must be called when:
-// - dir_parents changes (i.e. we change directory)
+// - dir_parent changes (i.e. we change directory)
// - config.show_hidden changes
// - files in this dir have been added or removed
pub fn loadDir(next_sel: ?*const model.Entry) void {
@@ -132,9 +132,9 @@ pub fn loadDir(next_sel: ?*const model.Entry) void {
dir_max_blocks = 1;
dir_has_shared = false;
- if (!dir_parents.isRoot())
+ if (dir_parent != model.root)
dir_items.append(null) catch unreachable;
- var it = dir_parents.top().sub;
+ var it = dir_parent.sub;
while (it) |e| {
if (e.blocks > dir_max_blocks) dir_max_blocks = e.blocks;
if (e.size > dir_max_size) dir_max_size = e.size;
@@ -219,8 +219,8 @@ const Row = struct {
if (main.config.show_graph == .both or main.config.show_graph == .percent) {
self.bg.fg(.num);
ui.addprint("{d:>5.1}", .{ 100*
- if (main.config.show_blocks) @intToFloat(f32, item.blocks) / @intToFloat(f32, std.math.max(1, dir_parents.top().entry.blocks))
- else @intToFloat(f32, item.size) / @intToFloat(f32, std.math.max(1, dir_parents.top().entry.size))
+ if (main.config.show_blocks) @intToFloat(f32, item.blocks) / @intToFloat(f32, std.math.max(1, dir_parent.entry.blocks))
+ else @intToFloat(f32, item.size) / @intToFloat(f32, std.math.max(1, dir_parent.entry.size))
});
self.bg.fg(.default);
ui.addch('%');
@@ -276,7 +276,7 @@ const Row = struct {
if (!main.config.show_mtime or self.col + 37 > ui.cols) return;
defer self.col += 27;
ui.move(self.row, self.col+1);
- const ext = (if (self.item) |e| e.ext() else @as(?*model.Ext, null)) orelse dir_parents.top().entry.ext();
+ const ext = (if (self.item) |e| e.ext() else @as(?*model.Ext, null)) orelse dir_parent.entry.ext();
if (ext) |e| ui.addts(self.bg, e.mtime)
else ui.addstr(" no mtime");
}
@@ -359,7 +359,7 @@ const info = struct {
state = .info;
tab = t;
if (tab == .links and links == null) {
- links = model.LinkPaths.find(&dir_parents, e.?.link().?);
+ links = model.LinkPaths.find(dir_parent, e.?.link().?);
for (links.?.paths.items) |n,i| {
if (&n.node.entry == e) {
links_idx = i;
@@ -536,8 +536,7 @@ const info = struct {
return true;
if (ch == 10) { // Enter - go to selected entry
const p = links.?.paths.items[links_idx];
- dir_parents.stack.shrinkRetainingCapacity(0);
- dir_parents.stack.appendSlice(p.path.stack.items) catch unreachable;
+ dir_parent = p.path;
loadDir(&p.node.entry);
set(null, .info);
}
@@ -730,7 +729,7 @@ pub fn draw() void {
ui.style(.dir);
var pathbuf = std.ArrayList(u8).init(main.allocator);
- dir_parents.fmtPath(true, &pathbuf);
+ dir_parent.fmtPath(true, &pathbuf);
ui.addstr(ui.shorten(ui.toUtf8(arrayListBufZ(&pathbuf)), saturateSub(ui.cols, 5)));
pathbuf.deinit();
@@ -760,12 +759,12 @@ pub fn draw() void {
ui.move(ui.rows-1, 1);
ui.style(if (main.config.show_blocks) .bold_hd else .hd);
ui.addstr("Total disk usage: ");
- ui.addsize(.hd, blocksToSize(dir_parents.top().entry.blocks));
+ ui.addsize(.hd, blocksToSize(dir_parent.entry.blocks));
ui.style(if (main.config.show_blocks) .hd else .bold_hd);
ui.addstr(" Apparent size: ");
- ui.addsize(.hd, dir_parents.top().entry.size);
+ ui.addsize(.hd, dir_parent.entry.size);
ui.addstr(" Items: ");
- ui.addnum(.hd, dir_parents.top().items);
+ ui.addnum(.hd, dir_parent.items);
switch (state) {
.main => {},
@@ -832,7 +831,7 @@ pub fn keyInput(ch: i32) void {
message = "Directory imported from file, refreshing is disabled."
else {
main.state = .refresh;
- scan.setupRefresh(dir_parents.copy());
+ scan.setupRefresh(dir_parent);
}
},
'b' => {
@@ -855,7 +854,7 @@ pub fn keyInput(ch: i32) void {
if (cursor_idx+1 < dir_items.items.len) dir_items.items[cursor_idx+1]
else if (cursor_idx == 0) null
else dir_items.items[cursor_idx-1];
- delete.setup(dir_parents.copy(), e, next);
+ delete.setup(dir_parent, e, next);
}
},
@@ -890,20 +889,20 @@ pub fn keyInput(ch: i32) void {
if (dir_items.items.len == 0) {
} else if (dir_items.items[cursor_idx]) |e| {
if (e.dir()) |d| {
- dir_parents.push(d);
+ dir_parent = d;
loadDir(null);
state = .main;
}
- } else if (!dir_parents.isRoot()) {
- dir_parents.pop();
+ } else if (dir_parent.parent) |p| {
+ dir_parent = p;
loadDir(null);
state = .main;
}
},
'h', '<', ui.c.KEY_BACKSPACE, ui.c.KEY_LEFT => {
- if (!dir_parents.isRoot()) {
- const e = dir_parents.top();
- dir_parents.pop();
+ if (dir_parent.parent) |p| {
+ const e = dir_parent;
+ dir_parent = p;
loadDir(&e.entry);
state = .main;
}
diff --git a/src/delete.zig b/src/delete.zig
index b690d80..d999a0c 100644
--- a/src/delete.zig
+++ b/src/delete.zig
@@ -8,7 +8,7 @@ const ui = @import("ui.zig");
const browser = @import("browser.zig");
usingnamespace @import("util.zig");
-var parents: model.Parents = .{};
+var parent: *model.Dir = undefined;
var entry: *model.Entry = undefined;
var next_sel: ?*model.Entry = undefined; // Which item to select if deletion succeeds
var state: enum { confirm, busy, err } = .confirm;
@@ -16,9 +16,8 @@ var confirm: enum { yes, no, ignore } = .no;
var error_option: enum { abort, ignore, all } = .abort;
var error_code: anyerror = undefined;
-// ownership of p is passed to this function
-pub fn setup(p: model.Parents, e: *model.Entry, n: ?*model.Entry) void {
- parents = p;
+pub fn setup(p: *model.Dir, e: *model.Entry, n: ?*model.Entry) void {
+ parent = p;
entry = e;
next_sel = n;
state = if (main.config.confirm_delete) .confirm else .busy;
@@ -49,8 +48,8 @@ fn deleteItem(dir: std.fs.Dir, path: [:0]const u8, ptr: *align(1) ?*model.Entry)
var fd = dir.openDirZ(path, .{ .access_sub_paths = true, .iterate = false })
catch |e| return err(e);
var it = &d.sub;
- parents.push(d);
- defer parents.pop();
+ parent = d;
+ defer parent = parent.parent.?;
while (it.*) |n| {
if (deleteItem(fd, n.name(), it)) {
fd.close();
@@ -64,14 +63,13 @@ fn deleteItem(dir: std.fs.Dir, path: [:0]const u8, ptr: *align(1) ?*model.Entry)
return if (e != error.DirNotEmpty or d.sub == null) err(e) else false;
} else
dir.deleteFileZ(path) catch |e| return err(e);
- ptr.*.?.delStats(&parents);
+ ptr.*.?.delStats(parent);
ptr.* = ptr.*.?.next;
return false;
}
// Returns the item that should be selected in the browser.
pub fn delete() ?*model.Entry {
- defer parents.deinit();
while (main.state == .delete and state == .confirm)
main.handleEvent(true, false);
if (main.state != .delete)
@@ -79,14 +77,14 @@ pub fn delete() ?*model.Entry {
// Find the pointer to this entry
const e = entry;
- var it = &parents.top().sub;
+ var it = &parent.sub;
while (it.*) |n| : (it = &n.next)
if (it.* == entry)
break;
var path = std.ArrayList(u8).init(main.allocator);
defer path.deinit();
- parents.fmtPath(true, &path);
+ parent.fmtPath(true, &path);
if (path.items.len == 0 or path.items[path.items.len-1] != '/')
path.append('/') catch unreachable;
path.appendSlice(entry.name()) catch unreachable;
@@ -125,7 +123,7 @@ fn drawConfirm() void {
fn drawProgress() void {
var path = std.ArrayList(u8).init(main.allocator);
defer path.deinit();
- parents.fmtPath(false, &path);
+ parent.fmtPath(false, &path);
path.append('/') catch unreachable;
path.appendSlice(entry.name()) catch unreachable;
@@ -145,7 +143,7 @@ fn drawProgress() void {
fn drawErr() void {
var path = std.ArrayList(u8).init(main.allocator);
defer path.deinit();
- parents.fmtPath(false, &path);
+ parent.fmtPath(false, &path);
path.append('/') catch unreachable;
path.appendSlice(entry.name()) catch unreachable;
diff --git a/src/main.zig b/src/main.zig
index a6ca14b..e12ffbe 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -187,7 +187,7 @@ fn spawnShell() void {
var path = std.ArrayList(u8).init(allocator);
defer path.deinit();
- browser.dir_parents.fmtPath(true, &path);
+ browser.dir_parent.fmtPath(true, &path);
var env = std.process.getEnvMap(allocator) catch unreachable;
defer env.deinit();
@@ -338,6 +338,7 @@ pub fn main() void {
config.scan_ui = .full; // in case we're refreshing from the UI, always in full mode.
ui.init();
state = .browse;
+ browser.dir_parent = model.root;
browser.loadDir(null);
while (true) {
diff --git a/src/model.zig b/src/model.zig
index 991d87d..25de648 100644
--- a/src/model.zig
+++ b/src/model.zig
@@ -99,29 +99,27 @@ pub const Entry = packed struct {
}
// Set the 'err' flag on Dirs and Files, propagating 'suberr' to parents.
- pub fn set_err(self: *Self, parents: *const Parents) void {
+ pub fn setErr(self: *Self, parent: *Dir) void {
if (self.dir()) |d| d.err = true
else if (self.file()) |f| f.err = true
else unreachable;
- var it = parents.iter();
- if (&parents.top().entry == self) _ = it.next();
- while (it.next()) |p| {
+ var it: ?*Dir = if (&parent.entry == self) parent.parent else parent;
+ while (it) |p| : (it = p.parent) {
if (p.suberr) break;
p.suberr = true;
}
}
- pub fn addStats(self: *Entry, parents: *const Parents) void {
+ pub fn addStats(self: *Entry, parent: *Dir) void {
if (self.counted) return;
self.counted = true;
- const dev = parents.top().dev;
// Set if this is the first time we've found this hardlink in the bottom-most directory of the given dev.
// Means we should count it for other-dev parent dirs, too.
var new_hl = false;
- var it = parents.iter();
- while(it.next()) |p| {
+ var it: ?*Dir = parent;
+ while(it) |p| : (it = p.parent) {
var add_total = false;
if (self.ext()) |e|
@@ -130,12 +128,12 @@ pub const Entry = packed struct {
p.items = saturateAdd(p.items, 1);
// Hardlink in a subdirectory with a different device, only count it the first time.
- if (self.etype == .link and dev != p.dev) {
+ if (self.etype == .link and parent.dev != p.dev) {
add_total = new_hl;
} else if (self.link()) |l| {
const n = devices.HardlinkNode{ .ino = l.ino, .dir = p };
- var d = devices.list.items[dev].hardlinks.getOrPut(n) catch unreachable;
+ var d = devices.list.items[parent.dev].hardlinks.getOrPut(n) catch unreachable;
new_hl = !d.found_existing;
// First time we encounter this file in this dir, count it.
if (!d.found_existing) {
@@ -175,29 +173,28 @@ pub const Entry = packed struct {
//
// This function assumes that, for directories, all sub-entries have
// already been un-counted.
- pub fn delStats(self: *Entry, parents: *const Parents) void {
+ pub fn delStats(self: *Entry, parent: *Dir) void {
if (!self.counted) return;
self.counted = false;
- const dev = parents.top().dev;
var del_hl = false;
- var it = parents.iter();
- while(it.next()) |p| {
+ var it: ?*Dir = parent;
+ while(it) |p| : (it = p.parent) {
var del_total = false;
p.items = saturateSub(p.items, 1);
- if (self.etype == .link and dev != p.dev) {
+ if (self.etype == .link and parent.dev != p.dev) {
del_total = del_hl;
} else if (self.link()) |l| {
const n = devices.HardlinkNode{ .ino = l.ino, .dir = p };
- var dp = devices.list.items[dev].hardlinks.getEntry(n);
+ var dp = devices.list.items[parent.dev].hardlinks.getEntry(n);
if (dp) |d| {
d.value_ptr.* -= 1;
del_total = d.value_ptr.* == 0;
del_hl = del_total;
if (del_total)
- _ = devices.list.items[dev].hardlinks.remove(n);
+ _ = devices.list.items[parent.dev].hardlinks.remove(n);
}
} else
del_total = true;
@@ -208,28 +205,13 @@ pub const Entry = packed struct {
}
}
- pub fn delStatsRec(self: *Entry, parents: *Parents) void {
+ pub fn delStatsRec(self: *Entry, parent: *Dir) void {
if (self.dir()) |d| {
- parents.push(d);
var it = d.sub;
while (it) |e| : (it = e.next)
- e.delStatsRec(parents);
- parents.pop();
+ e.delStatsRec(d);
}
- self.delStats(parents);
- }
-
- // Insert this entry into the tree at the given directory, updating parent sizes and item counts.
- pub fn insert(self: *Entry, parents: *const Parents) void {
- self.next = parents.top().sub;
- parents.top().sub = self;
- if (self.dir()) |d| std.debug.assert(d.sub == null);
-
- // Links with nlink == 0 are counted after we're done scanning.
- if (if (self.link()) |l| l.nlink == 0 else false)
- link_count.add(parents.top().dev, self.link().?.ino)
- else
- self.addStats(parents);
+ self.delStats(parent);
}
};
@@ -239,6 +221,7 @@ pub const Dir = packed struct {
entry: Entry,
sub: ?*Entry,
+ parent: ?*Dir,
// entry.{blocks,size}: Total size of all unique files + dirs. Non-shared hardlinks are counted only once.
// (i.e. the space you'll need if you created a filesystem with only this dir)
@@ -258,6 +241,23 @@ pub const Dir = packed struct {
// Only used to find the @byteOffsetOff, the name is written at this point as a 0-terminated string.
// (Old C habits die hard)
name: u8,
+
+ pub fn fmtPath(self: *const @This(), withRoot: bool, out: *std.ArrayList(u8)) void {
+ var components = std.ArrayList([:0]const u8).init(main.allocator);
+ defer components.deinit();
+ var it: ?*const @This() = self;
+ while (it) |e| : (it = e.parent)
+ if (withRoot or e != root)
+ components.append(e.entry.name()) catch unreachable;
+
+ var i: usize = components.items.len-1;
+ while (true) {
+ if (i != components.items.len-1) out.append('/') catch unreachable;
+ out.appendSlice(components.items[i]) catch unreachable;
+ if (i == 0) break;
+ i -= 1;
+ }
+ }
};
// File that's been hardlinked (i.e. nlink > 1)
@@ -420,23 +420,16 @@ pub const link_count = struct {
if (d.found_existing) d.key_ptr.*.count += 1;
}
- var final_dir: Parents = undefined;
-
- fn final_rec() void {
- var it = final_dir.top().sub;
+ fn finalRec(parent: *Dir) void {
+ var it = parent.sub;
while (it) |e| : (it = e.next) {
- if (e.dir()) |d| {
- final_dir.push(d);
- final_rec();
- final_dir.pop();
- continue;
- }
+ if (e.dir()) |d| finalRec(d);
const l = e.link() orelse continue;
if (l.nlink > 0) continue;
- const s = Node{ .dev = final_dir.top().dev, .ino = l.ino, .count = 0 };
+ const s = Node{ .dev = parent.dev, .ino = l.ino, .count = 0 };
if (nodes.getEntry(s)) |n| {
l.nlink = n.key_ptr.*.count;
- e.addStats(&final_dir);
+ e.addStats(parent);
}
}
}
@@ -445,96 +438,30 @@ pub const link_count = struct {
// find all links, update their nlink count and parent sizes.
pub fn final() void {
if (nodes.count() == 0) return;
- final_dir = Parents{};
- final_rec();
+ finalRec(root);
nodes.clearAndFree();
- final_dir.deinit();
}
};
pub var root: *Dir = undefined;
-// Stack of parent directories, convenient helper when constructing and traversing the tree.
-// The 'root' node is always implicitely at the bottom of the stack.
-pub const Parents = struct {
- stack: std.ArrayList(*Dir) = std.ArrayList(*Dir).init(main.allocator),
-
- const Self = @This();
-
- pub fn push(self: *Self, dir: *Dir) void {
- return self.stack.append(dir) catch unreachable;
- }
-
- pub fn isRoot(self: *Self) bool {
- return self.stack.items.len == 0;
- }
-
- // Attempting to remove the root node is considered a bug.
- pub fn pop(self: *Self) void {
- _ = self.stack.pop();
- }
-
- pub fn top(self: *const Self) *Dir {
- return if (self.stack.items.len == 0) root else self.stack.items[self.stack.items.len-1];
- }
-
- pub const Iterator = struct {
- lst: *const Self,
- index: usize = 0, // 0 = top of the stack, counts upwards to go down
-
- pub fn next(it: *Iterator) ?*Dir {
- const len = it.lst.stack.items.len;
- if (it.index > len) return null;
- it.index += 1;
- return if (it.index > len) root else it.lst.stack.items[len-it.index];
- }
- };
-
- // Iterate from top to bottom of the stack.
- pub fn iter(self: *const Self) Iterator {
- return .{ .lst = self };
- }
-
- // Append the path to the given arraylist. The list is assumed to use main.allocator, so it can't fail.
- pub fn fmtPath(self: *const Self, withRoot: bool, out: *std.ArrayList(u8)) void {
- const r = root.entry.name();
- if (withRoot) out.appendSlice(r) catch unreachable;
- var i: usize = 0;
- while (i < self.stack.items.len) {
- if (i != 0 or (withRoot and r[r.len-1] != '/')) out.append('/') catch unreachable;
- out.appendSlice(self.stack.items[i].entry.name()) catch unreachable;
- i += 1;
- }
- }
-
- pub fn copy(self: *const Self) Self {
- var c = Self{};
- c.stack.appendSlice(self.stack.items) catch unreachable;
- return c;
- }
-
- pub fn deinit(self: *Self) void {
- self.stack.deinit();
- }
-};
-
// List of paths for the same inode.
pub const LinkPaths = struct {
paths: std.ArrayList(Path) = std.ArrayList(Path).init(main.allocator),
pub const Path = struct {
- path: Parents,
+ path: *Dir,
node: *Link,
fn lt(_: void, a: Path, b: Path) bool {
- var i: usize = 0;
- while (i < a.path.stack.items.len and i < b.path.stack.items.len) : (i += 1)
- if (a.path.stack.items[i] != b.path.stack.items[i])
- return std.mem.lessThan(u8, a.path.stack.items[i].entry.name(), b.path.stack.items[i].entry.name());
- if (a.path.stack.items.len != b.path.stack.items.len)
- return a.path.stack.items.len < b.path.stack.items.len;
- return std.mem.lessThan(u8, a.node.entry.name(), b.node.entry.name());
+ var pa = std.ArrayList(u8).init(main.allocator);
+ var pb = std.ArrayList(u8).init(main.allocator);
+ defer pa.deinit();
+ defer pb.deinit();
+ a.fmtPath(false, &pa);
+ b.fmtPath(false, &pb);
+ return std.mem.lessThan(u8, pa.items, pb.items);
}
pub fn fmtPath(self: Path, withRoot: bool, out: *std.ArrayList(u8)) void {
@@ -546,42 +473,36 @@ pub const LinkPaths = struct {
const Self = @This();
- fn findRec(self: *Self, parent: *Parents, node: *const Link) void {
- var entry = parent.top().sub;
+ fn findRec(self: *Self, parent: *Dir, node: *const Link) void {
+ var entry = parent.sub;
while (entry) |e| : (entry = e.next) {
if (e.link()) |l| {
if (l.ino == node.ino)
- self.paths.append(Path{ .path = parent.copy(), .node = l }) catch unreachable;
- }
- if (e.dir()) |d| {
- if (d.dev == parent.top().dev) {
- parent.push(d);
- self.findRec(parent, node);
- parent.pop();
- }
+ self.paths.append(Path{ .path = parent, .node = l }) catch unreachable;
}
+ if (e.dir()) |d|
+ if (d.dev == parent.dev)
+ self.findRec(d, node);
}
}
// Find all paths for the given link
- pub fn find(parents_: *const Parents, node: *const Link) Self {
- var parents = parents_.copy();
+ pub fn find(parent_: *Dir, node: *const Link) Self {
+ var parent = parent_;
var self = Self{};
// First find the bottom-most parent that has no shared_size,
// all links are guaranteed to be inside that directory.
- while (!parents.isRoot() and parents.top().shared_size > 0)
- parents.pop();
- self.findRec(&parents, node);
+ while (parent.parent != null and parent.shared_size > 0)
+ parent = parent.parent.?;
+ self.findRec(parent, node);
// TODO: Zig's sort() implementation is type-generic and not very
// small. I suspect we can get a good save on our binary size by using
// a smaller or non-generic sort. This doesn't have to be very fast.
std.sort.sort(Path, self.paths.items, @as(void, undefined), Path.lt);
- parents.deinit();
return self;
}
pub fn deinit(self: *Self) void {
- for (self.paths.items) |*p| p.path.deinit();
self.paths.deinit();
}
};
diff --git a/src/scan.zig b/src/scan.zig
index dfa4e8c..c53d983 100644
--- a/src/scan.zig
+++ b/src/scan.zig
@@ -107,6 +107,8 @@ fn writeJsonString(wr: anytype, s: []const u8) !void {
// entries read from disk can be merged into, without doing an O(1) lookup for
// each entry.
const ScanDir = struct {
+ dir: *model.Dir,
+
// Lookup table for name -> *entry.
// null is never stored in the table, but instead used pass a name string
// as out-of-band argument for lookups.
@@ -130,21 +132,24 @@ const ScanDir = struct {
const Self = @This();
- fn init(parents: *const model.Parents) Self {
- var self = Self{ .entries = Map.initContext(main.allocator, HashContext{}) };
+ fn init(dir: *model.Dir) Self {
+ var self = Self{
+ .dir = dir,
+ .entries = Map.initContext(main.allocator, HashContext{}),
+ };
var count: Map.Size = 0;
- var it = parents.top().sub;
+ var it = dir.sub;
while (it) |e| : (it = e.next) count += 1;
self.entries.ensureCapacity(count) catch unreachable;
- it = parents.top().sub;
+ it = dir.sub;
while (it) |e| : (it = e.next)
self.entries.putAssumeCapacity(e, @as(void,undefined));
return self;
}
- fn addSpecial(self: *Self, parents: *model.Parents, name: []const u8, t: Context.Special) void {
+ fn addSpecial(self: *Self, name: []const u8, t: Context.Special) void {
var e = blk: {
if (self.entries.getEntryAdapted(@as(?*model.Entry,null), HashContext{ .cmp = name })) |entry| {
// XXX: If the type doesn't match, we could always do an
@@ -153,32 +158,32 @@ const ScanDir = struct {
var e = entry.key_ptr.*.?;
if (e.etype == .file) {
if (e.size > 0 or e.blocks > 0) {
- e.delStats(parents);
+ e.delStats(self.dir);
e.size = 0;
e.blocks = 0;
- e.addStats(parents);
+ e.addStats(self.dir);
}
e.file().?.resetFlags();
_ = self.entries.removeAdapted(@as(?*model.Entry,null), HashContext{ .cmp = name });
break :blk e;
- } else e.delStatsRec(parents);
+ } else e.delStatsRec(self.dir);
}
var e = model.Entry.create(.file, false, name);
- e.next = parents.top().sub;
- parents.top().sub = e;
- e.addStats(parents);
+ e.next = self.dir.sub;
+ self.dir.sub = e;
+ e.addStats(self.dir);
break :blk e;
};
var f = e.file().?;
switch (t) {
- .err => e.set_err(parents),
+ .err => e.setErr(self.dir),
.other_fs => f.other_fs = true,
.kernfs => f.kernfs = true,
.excluded => f.excluded = true,
}
}
- fn addStat(self: *Self, parents: *model.Parents, name: []const u8, stat: *Stat) *model.Entry {
+ fn addStat(self: *Self, name: []const u8, stat: *Stat) *model.Entry {
const etype = if (stat.dir) model.EType.dir
else if (stat.hlinkc) model.EType.link
else model.EType.file;
@@ -192,11 +197,11 @@ const ScanDir = struct {
if (e.etype == etype and samedev and sameino) {
_ = self.entries.removeAdapted(@as(?*model.Entry,null), HashContext{ .cmp = name });
break :blk e;
- } else e.delStatsRec(parents);
+ } else e.delStatsRec(self.dir);
}
var e = model.Entry.create(etype, main.config.extended, name);
- e.next = parents.top().sub;
- parents.top().sub = e;
+ e.next = self.dir.sub;
+ self.dir.sub = e;
break :blk e;
};
// Ignore the new size/blocks field for directories, as we don't know
@@ -205,11 +210,14 @@ const ScanDir = struct {
// sizes. The current approach may result in incorrect sizes after
// refresh, but I expect the difference to be fairly minor.
if (!(e.etype == .dir and e.counted) and (e.blocks != stat.blocks or e.size != stat.size)) {
- e.delStats(parents);
+ e.delStats(self.dir);
e.blocks = stat.blocks;
e.size = stat.size;
}
- if (e.dir()) |d| d.dev = model.devices.getId(stat.dev);
+ if (e.dir()) |d| {
+ d.parent = self.dir;
+ d.dev = model.devices.getId(stat.dev);
+ }
if (e.file()) |f| {
f.resetFlags();
f.notreg = !stat.dir and !stat.reg;
@@ -228,19 +236,19 @@ const ScanDir = struct {
// Assumption: l.link == 0 only happens on import, not refresh.
if (if (e.link()) |l| l.nlink == 0 else false)
- model.link_count.add(parents.top().dev, e.link().?.ino)
+ model.link_count.add(self.dir.dev, e.link().?.ino)
else
- e.addStats(parents);
+ e.addStats(self.dir);
return e;
}
- fn final(self: *Self, parents: *model.Parents) void {
+ fn final(self: *Self) void {
if (self.entries.count() == 0) // optimization for the common case
return;
- var it = &parents.top().sub;
+ var it = &self.dir.sub;
while (it.*) |e| {
if (self.entries.contains(e)) {
- e.delStatsRec(parents);
+ e.delStatsRec(self.dir);
it.* = e.next;
} else
it = &e.next;
@@ -264,8 +272,7 @@ const ScanDir = struct {
//
const Context = struct {
// When scanning to RAM
- parents: ?model.Parents = null,
- parent_entries: std.ArrayList(ScanDir) = std.ArrayList(ScanDir).init(main.allocator),
+ parents: ?std.ArrayList(ScanDir) = std.ArrayList(ScanDir).init(main.allocator),
// When scanning to a file
wr: ?*Writer = null,
@@ -303,10 +310,10 @@ const Context = struct {
return self;
}
- // Ownership of p is passed to the object, it will be deallocated on deinit().
- fn initMem(p: model.Parents) *Self {
+ fn initMem(dir: ?*model.Dir) *Self {
var self = main.allocator.create(Self) catch unreachable;
- self.* = .{ .parents = p };
+ self.* = .{ .parents = std.ArrayList(ScanDir).init(main.allocator) };
+ if (dir) |d| self.parents.?.append(ScanDir.init(d)) catch unreachable;
return self;
}
@@ -335,10 +342,11 @@ const Context = struct {
if (self.stat.dir) {
if (self.parents) |*p| {
- var d = self.parent_entries.pop();
- d.final(p);
- d.deinit();
- if (!p.isRoot()) p.pop();
+ if (p.items.len > 0) {
+ var d = p.pop();
+ d.final();
+ d.deinit();
+ }
}
if (self.wr) |w| w.writer().writeByte(']') catch |e| writeErr(e);
} else
@@ -352,7 +360,7 @@ const Context = struct {
// Set a flag to indicate that there was an error listing file entries in the current directory.
// (Such errors are silently ignored when exporting to a file, as the directory metadata has already been written)
fn setDirlistError(self: *Self) void {
- if (self.parents) |*p| p.top().entry.set_err(p);
+ if (self.parents) |*p| p.items[p.items.len-1].dir.entry.setErr(p.items[p.items.len-1].dir);
}
const Special = enum { err, other_fs, kernfs, excluded };
@@ -383,7 +391,7 @@ const Context = struct {
}
if (self.parents) |*p|
- self.parent_entries.items[self.parent_entries.items.len-1].addSpecial(p, self.name, t)
+ p.items[p.items.len-1].addSpecial(self.name, t)
else if (self.wr) |wr|
self.writeSpecial(wr.writer(), t) catch |e| writeErr(e);
@@ -410,7 +418,7 @@ const Context = struct {
// Insert current path as a counted file/dir/hardlink, with information from self.stat
fn addStat(self: *Self, dir_dev: u64) void {
if (self.parents) |*p| {
- var e = if (self.items_seen == 0) blk: {
+ var e = if (p.items.len == 0) blk: {
// Root entry
var e = model.Entry.create(.dir, main.config.extended, self.name);
e.blocks = self.stat.blocks;
@@ -420,12 +428,10 @@ const Context = struct {
model.root.dev = model.devices.getId(self.stat.dev);
break :blk e;
} else
- self.parent_entries.items[self.parent_entries.items.len-1].addStat(p, self.name, &self.stat);
+ p.items[p.items.len-1].addStat(self.name, &self.stat);
- if (e.dir()) |d| { // Enter the directory
- if (self.items_seen != 0) p.push(d);
- self.parent_entries.append(ScanDir.init(p)) catch unreachable;
- }
+ if (e.dir()) |d| // Enter the directory
+ p.append(ScanDir.init(d)) catch unreachable;
} else if (self.wr) |wr|
self.writeStat(wr.writer(), dir_dev) catch |e| writeErr(e);
@@ -435,11 +441,13 @@ const Context = struct {
fn deinit(self: *Self) void {
if (self.last_error) |p| main.allocator.free(p);
- if (self.parents) |*p| p.deinit();
+ if (self.parents) |*p| {
+ for (p.items) |*i| i.deinit();
+ p.deinit();
+ }
if (self.wr) |p| main.allocator.destroy(p);
self.path.deinit();
self.path_indices.deinit();
- self.parent_entries.deinit();
main.allocator.destroy(self);
}
};
@@ -533,7 +541,7 @@ fn scanDir(ctx: *Context, dir: std.fs.Dir, dir_dev: u64) void {
}
pub fn scanRoot(path: []const u8, out: ?std.fs.File) !void {
- active_context = if (out) |f| Context.initFile(f) else Context.initMem(.{});
+ active_context = if (out) |f| Context.initFile(f) else Context.initMem(null);
const full_path = std.fs.realpathAlloc(main.allocator, path) catch null;
defer if (full_path) |p| main.allocator.free(p);
@@ -545,16 +553,14 @@ pub fn scanRoot(path: []const u8, out: ?std.fs.File) !void {
scan();
}
-pub fn setupRefresh(parents: model.Parents) void {
- active_context = Context.initMem(parents);
+pub fn setupRefresh(parent: *model.Dir) void {
+ active_context = Context.initMem(parent);
var full_path = std.ArrayList(u8).init(main.allocator);
defer full_path.deinit();
- parents.fmtPath(true, &full_path);
+ parent.fmtPath(true, &full_path);
active_context.pushPath(full_path.items);
- active_context.parent_entries.append(ScanDir.init(&parents)) catch unreachable;
active_context.stat.dir = true;
- active_context.stat.dev = model.devices.getDev(parents.top().dev);
- active_context.items_seen = 1; // The "root" item has already been added.
+ active_context.stat.dev = model.devices.getDev(parent.dev);
}
// To be called after setupRefresh() (or from scanRoot())
@@ -969,7 +975,7 @@ pub fn importRoot(path: [:0]const u8, out: ?std.fs.File) void {
catch |e| ui.die("Error reading file: {s}.\n", .{ui.errorString(e)});
defer fd.close();
- active_context = if (out) |f| Context.initFile(f) else Context.initMem(.{});
+ active_context = if (out) |f| Context.initFile(f) else Context.initMem(null);
var imp = Import{ .ctx = active_context, .rd = fd };
defer imp.ctx.deinit();
imp.root();