Root: migrate {all,active}_outputs to wl.list

As discussed with ifreund on irc. This avoids extra allocation in case
of all_outputs and confusion in case of active_outputs (because with the
Output embedded in the Node, i thought its value was copied instead of
its pointer).

8 files changed, 88 insertions, 85 deletions

diff --git a/river/Cursor.zig b/river/Cursor.zig
index bd110a5..93b75d6 100644
--- a/river/Cursor.zig
+++ b/river/Cursor.zig
@@ -258,9 +258,9 @@ pub fn setTheme(self: *Self, theme: ?[*:0]const u8, _size: ?u32) !void {
     self.xcursor_manager = try wlr.XcursorManager.create(theme, size);
 
     // For each output, ensure a theme of the proper scale is loaded
-    var it = server.root.active_outputs.first;
-    while (it) |node| : (it = node.next) {
-        const wlr_output = node.data.wlr_output;
+    var it = server.root.active_outputs.iterator(.forward);
+    while (it.next()) |output| {
+        const wlr_output = output.wlr_output;
         self.xcursor_manager.load(wlr_output.scale) catch
             log.err("failed to load xcursor theme '{?s}' at scale {}", .{ theme, wlr_output.scale });
     }
diff --git a/river/Layout.zig b/river/Layout.zig
index 97634eb..3508a19 100644
--- a/river/Layout.zig
+++ b/river/Layout.zig
@@ -69,10 +69,10 @@ pub fn create(client: *wl.Client, version: u32, id: u32, output: *Output, namesp
 /// Returns true if the given namespace is already in use on the given output
 /// or on another output by a different client.
 fn namespaceInUse(namespace: []const u8, output: *Output, client: *wl.Client) bool {
-    var output_it = server.root.active_outputs.first;
-    while (output_it) |output_node| : (output_it = output_node.next) {
-        var layout_it = output_node.data.layouts.first;
-        if (output_node.data.wlr_output == output.wlr_output) {
+    var output_it = server.root.active_outputs.iterator(.forward);
+    while (output_it.next()) |o| {
+        var layout_it = output.layouts.first;
+        if (o == output) {
             // On this output, no other layout can have our namespace.
             while (layout_it) |layout_node| : (layout_it = layout_node.next) {
                 if (mem.eql(u8, namespace, layout_node.data.namespace)) return true;
diff --git a/river/LockManager.zig b/river/LockManager.zig
index ae44c96..8da7778 100644
--- a/river/LockManager.zig
+++ b/river/LockManager.zig
@@ -138,10 +138,8 @@ fn handleLockSurfacesTimeout(manager: *LockManager) c_int {
     manager.state = .waiting_for_blank;
 
     {
-        var it = server.root.active_outputs.first;
-        while (it) |node| : (it = node.next) {
-            const output = &node.data;
-
+        var it = server.root.active_outputs.iterator(.forward);
+        while (it.next()) |output| {
             output.normal_content.node.setEnabled(false);
             output.locked_content.node.setEnabled(true);
         }
@@ -157,9 +155,8 @@ pub fn maybeLock(manager: *LockManager) void {
     var all_outputs_blanked = true;
     var all_outputs_rendered_lock_surface = true;
     {
-        var it = server.root.active_outputs.first;
-        while (it) |node| : (it = node.next) {
-            const output = &node.data;
+        var it = server.root.active_outputs.iterator(.forward);
+        while (it.next()) |output| {
             switch (output.lock_render_state) {
                 .pending_unlock, .unlocked, .pending_blank, .pending_lock_surface => {
                     all_outputs_blanked = false;
@@ -205,10 +202,8 @@ fn handleUnlock(listener: *wl.Listener(void)) void {
     log.info("session unlocked", .{});
 
     {
-        var it = server.root.active_outputs.first;
-        while (it) |node| : (it = node.next) {
-            const output = &node.data;
-
+        var it = server.root.active_outputs.iterator(.forward);
+        while (it.next()) |output| {
             assert(!output.normal_content.node.enabled);
             output.normal_content.node.setEnabled(true);
 
diff --git a/river/Output.zig b/river/Output.zig
index c9acada..88358f2 100644
--- a/river/Output.zig
+++ b/river/Output.zig
@@ -41,6 +41,12 @@ const log = std.log.scoped(.output);
 
 wlr_output: *wlr.Output,
 
+/// For Root.all_outputs
+all_link: wl.list.Link,
+
+/// For Root.active_outputs
+active_link: wl.list.Link,
+
 /// The area left for views and other layer surfaces after applying the
 /// exclusive zones of exclusive layer surfaces.
 /// TODO: this should be part of the output's State
@@ -184,9 +190,8 @@ frame: wl.Listener(*wlr.Output) = wl.Listener(*wlr.Output).init(handleFrame),
 present: wl.Listener(*wlr.Output.event.Present) = wl.Listener(*wlr.Output.event.Present).init(handlePresent),
 
 pub fn create(wlr_output: *wlr.Output) !void {
-    const node = try util.gpa.create(std.TailQueue(Self).Node);
-    errdefer util.gpa.destroy(node);
-    const output = &node.data;
+    const output = try util.gpa.create(Self);
+    errdefer util.gpa.destroy(output);
 
     if (!wlr_output.initRender(server.allocator, server.renderer)) return error.InitRenderFailed;
 
@@ -216,6 +221,8 @@ pub fn create(wlr_output: *wlr.Output) !void {
 
     output.* = .{
         .wlr_output = wlr_output,
+        .all_link = undefined,
+        .active_link = undefined,
         .tree = tree,
         .normal_content = normal_content,
         .locked_content = try tree.createSceneTree(),
@@ -279,9 +286,8 @@ pub fn create(wlr_output: *wlr.Output) !void {
 
     output.setTitle();
 
-    const ptr_node = try util.gpa.create(std.TailQueue(*Self).Node);
-    ptr_node.data = &node.data;
-    server.root.all_outputs.append(ptr_node);
+    output.active_link.init();
+    server.root.all_outputs.append(output);
 
     handleEnable(&output.enable, wlr_output);
 }
@@ -361,13 +367,7 @@ fn handleDestroy(listener: *wl.Listener(*wlr.Output), _: *wlr.Output) void {
     assert(output.inflight.layout_demand == null);
     assert(output.layouts.len == 0);
 
-    var it = server.root.all_outputs.first;
-    while (it) |all_node| : (it = all_node.next) {
-        if (all_node.data == output) {
-            server.root.all_outputs.remove(all_node);
-            break;
-        }
-    }
+    output.all_link.remove();
 
     output.destroy.link.remove();
     output.enable.link.remove();
@@ -381,8 +381,7 @@ fn handleDestroy(listener: *wl.Listener(*wlr.Output), _: *wlr.Output) void {
 
     output.wlr_output.data = 0;
 
-    const node = @fieldParentPtr(std.TailQueue(Self).Node, "data", output);
-    util.gpa.destroy(node);
+    util.gpa.destroy(output);
 
     server.root.applyPending();
 }
diff --git a/river/Root.zig b/river/Root.zig
index 4eb8fd2..c41ef34 100644
--- a/river/Root.zig
+++ b/river/Root.zig
@@ -103,11 +103,11 @@ power_manager_set_mode: wl.Listener(*wlr.OutputPowerManagerV1.event.SetMode) =
     wl.Listener(*wlr.OutputPowerManagerV1.event.SetMode).init(handlePowerManagerSetMode),
 
 /// A list of all outputs
-all_outputs: std.TailQueue(*Output) = .{},
+all_outputs: wl.list.Head(Output, .all_link),
 
 /// A list of all active outputs (any one that can be interacted with, even if
 /// it's turned off by dpms)
-active_outputs: std.TailQueue(Output) = .{},
+active_outputs: wl.list.Head(Output, .active_link),
 
 /// Number of layout demands before sending configures to clients.
 inflight_layout_demands: u32 = 0,
@@ -175,6 +175,8 @@ pub fn init(self: *Self) !void {
         },
         .views = undefined,
         .output_layout = output_layout,
+        .all_outputs = undefined,
+        .active_outputs = undefined,
         .output_manager = try wlr.OutputManagerV1.create(server.wl_server),
         .power_manager = try wlr.OutputPowerManagerV1.create(server.wl_server),
         .transaction_timeout = transaction_timeout,
@@ -190,6 +192,8 @@ pub fn init(self: *Self) !void {
     self.fallback.inflight.wm_stack.init();
 
     self.views.init();
+    self.all_outputs.init();
+    self.active_outputs.init();
 
     server.backend.events.new_output.add(&self.new_output);
     self.output_manager.events.apply.add(&self.manager_apply);
@@ -257,18 +261,17 @@ fn handleNewOutput(_: *wl.Listener(*wlr.Output), wlr_output: *wlr.Output) void {
 }
 
 /// Remove the output from root.active_outputs and evacuate views if it is a
-/// member of the list. The node is not freed
+/// member of the list.
 pub fn deactivateOutput(root: *Self, output: *Output) void {
     {
-        const node = @fieldParentPtr(std.TailQueue(Output).Node, "data", output);
-
-        // If the node has already been removed, do nothing
-        var output_it = root.active_outputs.first;
-        while (output_it) |n| : (output_it = n.next) {
-            if (n == node) break;
+        // If the output has already been removed, do nothing
+        var it = root.active_outputs.iterator(.forward);
+        while (it.next()) |o| {
+            if (o == output) break;
         } else return;
 
-        root.active_outputs.remove(node);
+        output.active_link.remove();
+        output.active_link.init();
     }
 
     if (output.inflight.layout_demand) |layout_demand| {
@@ -290,7 +293,12 @@ pub fn deactivateOutput(root: *Self, output: *Output) void {
     }
     // Use the first output in the list as fallback. If the last real output
     // is being removed, store the views in Root.fallback.
-    const fallback_output = if (root.active_outputs.first) |node| &node.data else null;
+    const fallback_output = blk: {
+        var it = root.active_outputs.iterator(.forward);
+        if (it.next()) |o| break :blk o;
+
+        break :blk null;
+    };
     if (fallback_output) |fallback| {
         var it = output.pending.focus_stack.safeIterator(.reverse);
         while (it.next()) |view| view.setPendingOutput(fallback);
@@ -332,13 +340,15 @@ pub fn deactivateOutput(root: *Self, output: *Output) void {
 /// Add the output to root.active_outputs and the output layout if it has not
 /// already been added.
 pub fn activateOutput(root: *Self, output: *Output) void {
-    const node = @fieldParentPtr(std.TailQueue(Output).Node, "data", output);
+    {
+        // If we have already added the output, do nothing and return
+        var it = root.active_outputs.iterator(.forward);
+        while (it.next()) |o| if (o == output) return;
+    }
 
-    // If we have already added the output, do nothing and return
-    var output_it = root.active_outputs.first;
-    while (output_it) |n| : (output_it = n.next) if (n == node) return;
+    const first = root.active_outputs.empty();
 
-    root.active_outputs.append(node);
+    root.active_outputs.append(output);
 
     // This arranges outputs from left-to-right in the order they appear. The
     // wlr-output-management protocol may be used to modify this arrangement.
@@ -350,7 +360,7 @@ pub fn activateOutput(root: *Self, output: *Output) void {
     output.tree.node.setPosition(layout_output.x, layout_output.y);
 
     // If we previously had no outputs, move all views to the new output and focus it.
-    if (root.active_outputs.len == 1) {
+    if (first) {
         output.pending.tags = root.fallback.tags;
         {
             var it = root.fallback.pending.focus_stack.safeIterator(.reverse);
@@ -411,10 +421,8 @@ pub fn applyPending(root: *Self) void {
     }
 
     {
-        var output_it = root.active_outputs.first;
-        while (output_it) |node| : (output_it = node.next) {
-            const output = &node.data;
-
+        var output_it = root.active_outputs.iterator(.forward);
+        while (output_it.next()) |output| {
             // Iterate the focus stack in order to ensure the currently focused/most
             // recently focused view that requests fullscreen is given fullscreen.
             output.inflight.fullscreen = null;
@@ -469,9 +477,8 @@ pub fn applyPending(root: *Self) void {
     {
         // Layout demands can't be sent until after the inflight stacks of
         // all outputs have been updated.
-        var output_it = root.active_outputs.first;
-        while (output_it) |node| : (output_it = node.next) {
-            const output = &node.data;
+        var output_it = root.active_outputs.iterator(.forward);
+        while (output_it.next()) |output| {
             assert(output.inflight.layout_demand == null);
             if (output.layout) |layout| {
                 var layout_count: u32 = 0;
@@ -538,10 +545,8 @@ fn sendConfigures(root: *Self) void {
     assert(root.inflight_configures == 0);
 
     // Iterate over all views of all outputs
-    var output_it = root.active_outputs.first;
-    while (output_it) |output_node| : (output_it = output_node.next) {
-        const output = &output_node.data;
-
+    var output_it = root.active_outputs.iterator(.forward);
+    while (output_it.next()) |output| {
         var focus_stack_it = output.inflight.focus_stack.iterator(.forward);
         while (focus_stack_it.next()) |view| {
             // This can happen if a view is unmapped while a layout demand including it is inflight
@@ -614,10 +619,8 @@ fn commitTransaction(root: *Self) void {
         }
     }
 
-    var output_it = root.active_outputs.first;
-    while (output_it) |output_node| : (output_it = output_node.next) {
-        const output = &output_node.data;
-
+    var output_it = root.active_outputs.iterator(.forward);
+    while (output_it.next()) |output| {
         if (output.inflight.tags != output.current.tags) {
             std.log.scoped(.output).debug(
                 "changing current focus: {b:0>10} to {b:0>10}",
@@ -798,9 +801,8 @@ fn currentOutputConfig(self: *Self) !*wlr.OutputConfigurationV1 {
     // this destroys all associated config heads as well
     errdefer config.destroy();
 
-    var it = self.all_outputs.first;
-    while (it) |node| : (it = node.next) {
-        const output = node.data;
+    var it = self.all_outputs.iterator(.forward);
+    while (it.next()) |output| {
         const head = try wlr.OutputConfigurationV1.Head.create(config, output.wlr_output);
 
         // If the output is not part of the layout (and thus disabled)
diff --git a/river/command/config.zig b/river/command/config.zig
index 1a5543a..15d7db0 100644
--- a/river/command/config.zig
+++ b/river/command/config.zig
@@ -45,9 +45,8 @@ pub fn backgroundColor(
     if (args.len > 2) return Error.TooManyArguments;
 
     server.config.background_color = try parseRgba(args[1]);
-    var it = server.root.all_outputs.first;
-    while (it) |node| : (it = node.next) {
-        const output = node.data;
+    var it = server.root.all_outputs.iterator(.forward);
+    while (it.next()) |output| {
         output.layers.background_color_rect.setColor(&server.config.background_color);
     }
 }
diff --git a/river/command/layout.zig b/river/command/layout.zig
index 133a332..1c6c217 100644
--- a/river/command/layout.zig
+++ b/river/command/layout.zig
@@ -51,9 +51,8 @@ pub fn defaultLayout(
     server.config.default_layout_namespace = try util.gpa.dupe(u8, args[1]);
     util.gpa.free(old_default_layout_namespace);
 
-    var it = server.root.all_outputs.first;
-    while (it) |node| : (it = node.next) {
-        const output = node.data;
+    var it = server.root.all_outputs.iterator(.forward);
+    while (it.next()) |output| {
         if (output.layout_namespace == null) output.handleLayoutNamespaceChange();
     }
 }
diff --git a/river/command/output.zig b/river/command/output.zig
index d9f3c33..c32316a 100644
--- a/river/command/output.zig
+++ b/river/command/output.zig
@@ -17,6 +17,7 @@
 const std = @import("std");
 const assert = std.debug.assert;
 const mem = std.mem;
+const wl = @import("wayland").server.wl;
 const wlr = @import("wlroots");
 const flags = @import("flags");
 
@@ -38,7 +39,7 @@ pub fn focusOutput(
 
     // If the fallback pseudo-output is focused, there are no other outputs to switch to
     if (seat.focused_output == null) {
-        assert(server.root.active_outputs.len == 0);
+        assert(server.root.active_outputs.empty());
         return;
     }
 
@@ -62,7 +63,7 @@ pub fn sendToOutput(
 
     // If the fallback pseudo-output is focused, there is nowhere to send the view
     if (seat.focused_output == null) {
-        assert(server.root.active_outputs.len == 0);
+        assert(server.root.active_outputs.empty());
         return;
     }
 
@@ -86,12 +87,20 @@ pub fn sendToOutput(
 /// spacial direction
 fn getOutput(seat: *Seat, str: []const u8) !?*Output {
     if (std.meta.stringToEnum(Direction, str)) |direction| { // Logical direction
-        // Return the next/prev output in the list if there is one, else wrap
-        const focused_node = @fieldParentPtr(std.TailQueue(Output).Node, "data", seat.focused_output.?);
-        return switch (direction) {
-            .next => if (focused_node.next) |node| &node.data else &server.root.active_outputs.first.?.data,
-            .previous => if (focused_node.prev) |node| &node.data else &server.root.active_outputs.last.?.data,
+        // Return the next/prev output in the list
+        var link = &seat.focused_output.?.active_link;
+        link = switch (direction) {
+            .next => link.next.?,
+            .previous => link.prev.?,
         };
+        // Wrap around list head
+        if (link == &server.root.active_outputs.link) {
+            link = switch (direction) {
+                .next => link.next.?,
+                .previous => link.prev.?,
+            };
+        }
+        return @fieldParentPtr(Output, "active_link", link);
     } else if (std.meta.stringToEnum(wlr.OutputLayout.Direction, str)) |direction| { // Spacial direction
         var focus_box: wlr.Box = undefined;
         server.root.output_layout.getBox(seat.focused_output.?.wlr_output, &focus_box);
@@ -106,10 +115,10 @@ fn getOutput(seat: *Seat, str: []const u8) !?*Output {
         return @intToPtr(*Output, wlr_output.data);
     } else {
         // Check if an output matches by name
-        var it = server.root.active_outputs.first;
-        while (it) |node| : (it = node.next) {
-            if (mem.eql(u8, mem.span(node.data.wlr_output.name), str)) {
-                return &node.data;
+        var it = server.root.active_outputs.iterator(.forward);
+        while (it.next()) |output| {
+            if (mem.eql(u8, mem.span(output.wlr_output.name), str)) {
+                return output;
             }
         }
         return Error.InvalidOutputIndicator;