第七章·第二节链表 (Linked Lists)

⚠️ 注意

如果您发现了错误，欢迎参与贡献。

📖 本节目录

设计概述

BIRD 实现了一套高效、通用的双向循环链表，是代码中使用最广泛的数据结构之一。

核心类型

typedef struct node {
  struct node *next, *prev;
} node;

typedef struct list {
  node *head, *tail;
} list;

💡 译者注

BIRD 的链表设计遵循 Linux 内核链表风格——node 结构嵌入到用户自定义结构中，而非存储数据指针。这种"侵入式链表"（Intrusive Linked List）的优势在于零内存分配：添加/删除节点不需要任何 malloc/free 调用，仅操作指针。对于路由协议这种高频增删路由条目的场景，避免每次操作都涉及堆分配是性能关键。

核心操作

函数/宏	说明
`add_head(l, n)`	在链表头部插入节点
`add_tail(l, n)`	在链表尾部插入节点
`rem_node(n)`	从链表中移除节点（不需要知道所属链表）
`WALK_LIST(n, l)`	遍历链表中所有节点

零开销原则

链表操作不涉及内存分配/释放
节点内存由调用方管理（通常是资源池的一部分）
遍历通过指针运算实现，无额外开销

本文译者及原文信息

Hat

译者

展开原文属性

原文作者： <Ondrej Filip>, <Martin Mares>, <Maria Matejka>, <Ondrej Zajicek> 原文链接： https://bird.network.cz/?get_doc&v=20&f=prog-7.html#ss7.2 原文标题： 7.2 Linked lists

展开译文属性

遵循协议： CC BY-NC-SA 4.0 / 译者： hat / 翻译时间： 2026-05-01 / 本文链接： https://bird.xmsl.dev/docs/developer-guide/7-2-linked-lists.html

第七章·第二节 链表 (Linked Lists) ​

设计概述 ​

核心类型 ​

核心操作 ​

零开销原则 ​

本文译者及原文信息 ​

Hat