Zig 新的 LinkedList API (是时候学习 @fieldParentPtr 了)

Zig's new LinkedList API (it's time to learn fieldParentPtr)

Source | HN Comments

文章介绍了 Zig 语言中新的链表 API 的变化，从泛型链表转变为侵入式链表，以提高性能和减少内存分配。核心在于使用 `@fieldParentPtr` 内置函数，通过节点地址获取包含该节点的父结构体实例。虽然 `@fieldParentPtr` 看起来复杂，但它解决了链表实现中的难题，值得开发者学习和掌握。

home dark

Zig 新的 LinkedList API (是时候学习 @fieldParentPtr 了)

2025年4月10日

在最近一次的 Zig 0.14 之后的提交中，Zig 的 SinglyLinkedList 和 DoublyLinkedList 发生了重大变化。之前的版本是一个泛型，并且移除了所有方法，看起来像这样：

pub fn SinglyLinkedList(comptime T: type) type {
 return struct {
  first: ?*Node = null,
  pub const Node = struct {
   next: ?*Node = null,
   data: T,
  };
 };
}

新的版本不是泛型的。而是将链表节点嵌入到你的数据中。这被称为侵入式链表，往往性能更好，需要的内存分配更少。除了简单的例子，我们存储在链表中的数据通常存储在堆上。由于侵入式链表将链表节点嵌入到数据中，因此不需要自己的内存分配。在深入示例之前，这是新的结构的样子，同样，移除了所有方法：

pub const SinglyLinkedList = struct {
 first: ?*Node = null,
 pub const Node = struct {
  next: ?*Node = null,
 };
};

更简洁，并且注意到它没有任何链接或引用到我们的数据。这是一个工作示例，展示了如何使用它：

const std = @import("std");
const SinglyLinkedList = std.SinglyLinkedList;
pub fn main() !void {
  // GeneralPurposeAllocator 正在被重命名
  // 为 DebugAllocator。让我们习惯这个名字
  var gpa: std.heap.DebugAllocator(.{}) = .init;
  const allocator = gpa.allocator();
  var list: SinglyLinkedList = .{};
  const user1 = try allocator.create(User);
  defer allocator.destroy(user1);
  user1.* = .{
    .id = 1,
    .power = 9000,
    .node = .{},
  };
  list.prepend(&user1.node);
  const user2 = try allocator.create(User);
  defer allocator.destroy(user2);
  user2.* = .{
    .id = 2,
    .power = 9001,
    .node = .{},
  };
  list.prepend(&user2.node);
  var node = list.first;
  while (node) |n| {
    std.debug.print("{any}\n", .{n});
    node = n.next;
  }
}
const User = struct {
  id: i64,
  power: u32,
  node: SinglyLinkedList.Node,
};

要运行此代码，你需要最近一周内的 nightly release。你认为输出会是什么？你应该看到类似以下内容：

SinglyLinkedList.Node{ .next = SinglyLinkedList.Node{ .next = null } }
SinglyLinkedList.Node{ .next = null }

我们只得到了节点，正如我们在这里以及从上面新的 SinglyLinkedList 的骨架结构中看到的那样，没有任何关于我们用户的信息。用户有节点，但似乎没有任何东西将节点链接回其包含的用户。或者有吗？过去，我们描述了编译器如何使用类型信息来确定如何访问字段。例如，当我们执行 user1.power 时，编译器知道：

id 从结构的开头偏移 +0 字节，
power 从结构的开头偏移 +8 字节（因为 id 是 i64），并且
power 是一个 i32

有了这些信息，编译器就知道如何从 user1 访问 power (即向前跳 8 个字节，读取 4 个字节并将其视为 i32)。但如果你仔细想想，这种逻辑很容易反转。如果我们知道 power 的地址，那么 user 的地址一定是 address_of_power - 8。我们可以证明这一点：

const std = @import("std");
pub fn main() !void {
  var user = User{
    .id = 1,
    .power = 9000,
  };
  std.debug.print("address of user: {*}\n", .{&user});
  const address_of_power = &user.power;
  std.debug.print("address of power: {*}\n", .{address_of_power});
  const power_offset = 8;
  const also_user: *User = @ptrFromInt(@intFromPtr(address_of_power) - power_offset);
  std.debug.print("address of also_user: {*}\n", .{also_user});
  std.debug.print("also_user: {}\n", .{also_user});
}
const User = struct {
  id: i64,
  power: u32,
};

魔法发生在这里：

const power_offset = 8;
const also_user: *User = @ptrFromInt(@intFromPtr(address_of_power) - power_offset);

我们将用户 power 字段的地址 &user.power 转换为整数，减去 8（8 字节，64 位），并告诉编译器应该将该内存视为 *User。这段代码可能对你有效，但它并不安全。具体来说，除非我们使用 packed 或 extern struct，否则 Zig 不保证结构的布局。它可能会将 power 放在 id 之前，在这种情况下，我们的 power_offset 应该是 0。它可以在每个字段后添加填充。它可以做任何它想做的事情。为了使这段代码更安全，我们使用 @offsetOf 内置函数来获取字段相对于其结构的实际字节偏移量：

const power_offset = @offsetOf(User, "power");

回到我们的链表，鉴于我们有 node 的地址，并且我们知道它是 User 结构的一部分，我们_能够_从节点获取 User。但是，我们不会使用上面的代码，而是使用稍微更友好的 @fieldParentPtr 内置函数。我们的 while 循环变为：

while (node) |n| {
 const user: *User = @fieldParentPtr("node", n);
 std.debug.print("{any}\n", .{user});
 node = n.next;
}

我们给 @fieldParentPtr 字段的名称，指向该字段的指针以及返回类型（上面通过分配给 *User 变量来推断），它会返回给我们包含该字段的实例。抛开性能不谈，我对新的 API 感觉好坏参半。我的最初反应是不喜欢为了使用链表这样简单的事情而暴露像 @fieldParentPtr 这样复杂的内置函数。但是，虽然 @fieldParentPtr 看起来很深奥，但它非常有用，开发人员应该熟悉它，因为它可以帮助解决原本存在问题的难题。