Chillward的博客

发表于 更新于

👋 你好，我是Chillward

欢迎来到我的博客，这里主要是我平时学习编程的笔记和踩坑记录还有一些别的碎碎念。

🧑‍💻 关于我

  • 目前正在学习：C/C++、Rust、RT-Thread嵌入式、Linux相关知识
  • 兴趣方向：嵌入式开发、底层原理、编程语言特性
  • 状态：入门水平，慢慢摸索中，在这里记录学习过程

📚 博客内容

主要就是记录自己学习过程中的笔记，方便自己回头看，也希望能帮到有需要的人：

  • Rust学习笔记：从入门开始的学习过程记录
  • RT-Thread开发笔记：实时操作系统学习和使用的记录
  • C语言相关笔记：一些C语言特性的学习和使用总结
  • 其他杂项：遇到的问题、解决方案、零散知识点记录
  • 一些碎碎念

📬 联系方式

  • GitHub: Chillward
  • 博客就是当前站点，随缘更新

西郊有密林，祝君出重围。

发表于

Reference Counting in C

事情是这样的，Tsoding在他的频道发布了这样一期视频，是关于在C语言中实现一个简易的Rc，并且使用它来实现了一个微型的Lisp解释器。我跟着他的视频敲完了所有代码。但老实说我并没有理解多少，所以在这里写一个博客并且盼望着能够从中学到一些什么

一、Lisp 是什么

1.1 Lisp 概述

Lisp的全称是List Processor（列表处理机），由John McCarthy在1958年创立，是目前仍在使用的第二古老高级编程语言，仅次于Fortran。和我们熟悉的C、Java、Python等语言相比，Lisp的核心差异在于 “程序即数据”（同像性） 这一独特特质，这也是它区别于其他主流语言的核心标志。

1.2 Lisp 核心特征

  • 语法高度统一：一切皆为S-表达式（列表），摒弃传统中缀表示法。例如加法运算不会写成1 + 2，而是采用前缀表示法的(+ 1 2)。

  • 函数式编程为核心：递归是核心编程方式，函数在Lisp中是“一等公民”，可作为参数、返回值或变量存储，灵活性极高。

  • 早期特性奠基：是最早引入动态类型和自动内存管理的语言之一，这两大特性也成为后续编程语言内存管理方案的核心动因。

二、Lisp 底层数据结构

2.1 核心结构：Cons Cell（点对单元）

理解Lisp的关键，在于认清其列表的本质——它并非连续数组，而是由Cons Cell（点对单元） 构成的链表，这是Lisp数据结构的底层基石。每个Cons Cell分为两部分：CAR指向当前节点的数据（如整数、符号），CDR指向列表的“剩余部分”。

一个标准的Lisp列表，本质是“嵌套的Cons Cell链条”，且必须以NIL（空列表） 结尾。例如列表(1 2 3)在内存中，就是三个Cons Cell串联而成：

  1. 第一个Cons Cell：CAR为1、CDR指向第二个Cons Cell；

  2. 第二个Cons Cell：CAR为2、CDR指向第三个Cons Cell；

  3. 第三个Cons Cell：CAR为3、CDR指向NIL。

2.2 易混淆概念区分

  • Cons Cell：底层物理结构，类似一个有两个格子的“盒子”，是构成所有Lisp数据结构的基础单元。

  • 点对（Dotted Pair）：当Cons Cell的CDR指向非列表（也非NIL）时，称为点对，格式如(420 . 69)，常用来表示坐标、键值对等二元关系。

  • 标准列表：只有当Cons Cell链条以NIL结尾时，才是我们常说的“标准列表”，也是Lisp中最常用的数据形式。

这种链表结构赋予Lisp一个重要优势——结构共享：创建新列表时无需复制已有数据，只需新建Cons Cell并指向已有链表即可，这让数据操作更高效，但也给内存管理带来了一定挑战。

所以说Lisp的列表本质上就是链表

三、Lisp 解释器解析

3.1 Lisp 解释器核心：REPL循环

Lisp解释器的核心是REPL循环，简单来说就是四个步骤的循环执行：

  • 读取（Read）：输入字符串并解析为Lisp内部的链表结构；

  • 求值（Eval）：递归判断表达式类型（常量、变量、函数调用），若为函数调用则递归求值参数并执行逻辑（Eval是核心部分）；

  • 打印（Print）：输出求值结果；

  • 循环（Loop）：等待下一次输入。

3.2 内存管理的必要性

由于Lisp的递归链表操作、结构共享特性，多个列表可能共用同一个Cons Cell节点。若手动调用free()，既无法判断谁该负责释放，也容易出现内存泄漏或重复释放的问题，因此自动内存管理就成了Lisp解释器的必选项。

首先，在一切开始之前，我们为什么需要用到Rc来管理这一切？

四、Lisp 解释器的核心内存管理方式

引用计数（RC）的核心逻辑很简单：给每个对象（如Lisp的Expr结构体）维护一个计数器，具体操作如下：

  • 新指针指向对象时，计数器+1（对应rc_acquire操作）；

  • 指针失效时，计数器-1（对应rc_release操作）；

  • 计数器归零时，立即释放该对象占用的内存。

优点：实时性高，内存无人使用时立即回收，无不可预测停顿；实现简单，无需扫描整个内存堆。

缺点：每次指针赋值都要更新计数器，存在分散性能开销；无法处理循环引用（两个对象互相指向时，计数器永远无法归零，导致内存泄漏）。

所谓弱引用好像就是拿来解决这个问题的

Tsoding并没有完整的实现整个Lisp解释器，而是只简单实现了

  • 求值（Eval）：递归判断表达式类型（常量、变量、函数调用），若为函数调用则递归求值参数并执行逻辑（Eval是核心部分）；

  • 打印（Print）：输出求值结果；

这两个部分。

我觉得从Rc的实现来开始切入是相当合适的

1
2
3
4
5
6
7
8
9
10
typedef struct
{
    ptrdiff_t count;
    void (*destroy)(void *data);
} Rc;

void *rc_alloc(size_t size, void (*destroy)(void *data));
void *rc_acquire(void *data);
void rc_release(void *data);
ptrdiff_t rc_count(void *data);

这是我们rc.h中的所有的函数声明。

观察Rc类型，我们可以发现其中只简单的包含两个元素，一个类型为pirtdiff_t的count，以及一个void (*)(void *)的函数指针，指向被Rc管理的类型自定义的析构函数。

那么我们是如何通过Rc来管理自定义的的呢，这里我们就用到了C语言的一个特性：内存偏移

在 C 语言中，我们通常认为指针指向的是一块内存的“起点”。但 rc.h 利用了一个空间上的错位：用户看到的起点，其实是数据的中点。

1
2
3
+------------+-----------+
|    Rc      |   struct  |
+------------+-----------+

我们可以观察rc_aclloc函数的实现:

1
2
3
4
5
6
7
8
9
void *rc_alloc(size_t size, void (*destroy)(void *data))
{
    Rc *rc = malloc(sizeof(Rc) + size);
    assert(rc);
    rc->count = 0;
    rc->destroy = destroy;
    printf("[RC] %p allocated\n", rc);
    return rc + 1;
}

我们分配的连续内存中内嵌了 Rc 元数据头，用于存储引用计数和对应的析构函数指针。接口返回的指针直接指向自定义数据类型，调用 rc_alloc 后即可直接操作目标对象，Rc 元数据头作为底层实现细节被完全隐藏，无需显式访问。

然后我们可以来观察rc_release函数的实现

1
2
3
4
5
6
7
8
9
10
11
void rc_release(void *data)
{
    Rc *rc = (Rc *)data - 1;
    rc->count -= 1;
    if (rc->count <= 0)
    {
        rc->destroy(rc + 1);
        printf("[RC] %p released\n", rc);
        free(rc);
    }
}

这个函数的功能分三步：

  1. 通过指针运算取回我们需要的header

  2. 减少引用次数

  3. 当引用次数<=0时，调用析构函数，最后进行内存释放

我们为什么要这么设计？

这种模式是高度泛用的（Generic），它是 C 语言中模拟“多态析构”的标准工程实践。

这段代码本质上是解耦了内存管理逻辑（Rc）与具体的业务清理逻辑（Lisp）。

  • Rc 库的视角（通用性）：rc.h 并不关心它管理的是 Lisp 的表达式、一个复杂的网络缓冲区，还是一个文件描述符。它只知道：“当没人用这块地时，我就通过这个预留的‘电话号码’（函数指针）通知物主来搬家。”

  • 业务层的视角（定制性）：不同的数据类型可以注册不同的 destroy 函数。

    • 如果是 Lisp PAIR：destroy 会递归释放左右子节点。

    • 如果是 文件对象：destroy 可能会负责 fclose(fp)。

    • 如果是 线程池：destroy 可能会负责销毁互斥锁（Mutex）。

大概就是“我的引用用完了，剩下的内部资源清理，交给你专属的析构函数处理“这个逻辑

而在rc_acquire函数中，我们所做的工作仅仅只取回头部之后将count+1,随后返回原地址

1
2
3
4
5
6
void *rc_acquire(void *data)
{
    Rc *rc = ((Rc *)data - 1);
    rc->count += 1;
    return data;
}

可以发现 rc_alloc 并不进行“计数 +1”这个行为，它将初始计数设置为 0。真正的“计数 +1”是由 rc_acquire 负责的。

这种设计背后有一套严密的逻辑配合：

1. rc_alloc 的职责：初始化

rc_alloc 的任务是分配内存并设置好“元数据”。

  • 它将 rc->count 初始化为 0。

  • 这意味着：刚分配出来的对象，在逻辑上还没有被任何人“持有”所有权。

  • 这是一种“预分配”状态，等待被第一个使用者接管。

2. rc_acquire 的职责：增加引用

这是真正执行 rc->count += 1 的地方。

  • 当我们希望一个指针正式指向这个对象并共享其所有权时，你必须显式调用 rc_acquire。
3. 为什么要分两步？（配合构造函数）

观察我们的构造函数（如 make_pair），可以发现这种设计的精妙之处：

1
2
3
4
5
6
7
Expr *make_pair(Expr *left, Expr *right)
{
    Expr *expr = alloc_expr(EXPR_PAIR); // 1. 分配，count = 0
    expr->pair.left = rc_acquire(left); // 2. 这里的 left 被新对象持有了，count + 1
    expr->pair.right = rc_acquire(right); // 3. 这里的 right 被新对象持有了，count + 1
    return expr; // 返回 count = 0 的新对象
}

关于这个，我们一会会提到的(确信)

  • 内部成员的持有：make_pair 作为父节点，通过 rc_acquire 明确表示它“拥有”了子节点 left 和 right。

  • 新对象的返回：make_pair 返回的新对象计数仍为 0。直到 main 函数或另一个父节点决定接管它时，才会调用 rc_acquire 将其变为 1。

总结

  • rc_alloc：负责 “生”，但不负责“养”，计数设为 0。

  • rc_acquire：负责 “养”（增加所有权），计数 +1。

  • rc_release：负责 “弃”（放弃所有权），计数 -1，并在无人领养（计数归零）时销毁。

这种“由调用者决定何时加 1”的模式，能有效避免在构造复杂树状结构（如 Lisp 列表）时出现计数混乱。

Rc_count函数实际上是不太重要的，它仅仅只是返回当前对象的count而已。

我们刚才花了不少时间，把 rc.h 这个头文件的功能都梳理了一遍。

整体的思路是这样的：

我要做一个 Lisp 解析器 → 可 Lisp 里的列表结构，靠手动管理内存根本不现实 → 所以必须自己搞一套自动内存管理机制 → 于是就实现了 rc.h 这套引用计数库 → 最后再用它来支撑整个解析器的运行。

当然，Tsoding 本人是把这些内容混在一起开发的，中间甚至还重构了两次。他是一边写解析器的功能，一边慢慢完善 rc.h 的逻辑。rc_alloc 最开始甚至还自带 count++ 的逻辑，一直迭代到最后，才变成现在这种谁调用谁释放的样子。

虽说这种边做边改的方式，确实更贴近真实开发的流程。但我必须说实话，看完他那两个小时十八分钟的视频，我人是蒙的。当然这也就是这篇博客诞生的原因

想要实现一个lisp解析器，我们需要些什么？

首先我们应该需要一个数据结构来存储lisp的对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef enum
{
    EXPR_NIL,
    EXPR_SYMBOL,
    EXPR_INTEGER,
    EXPR_PAIR,
    __count_expr_kind,
} Expr_Kind;

typedef struct Expr Expr;

struct Expr
{
    Expr_Kind kind;
    static_assert(__count_expr_kind == 4, "Amount of expression kinds has changed");
    union
    {
        const char *symbol;
        int integer;
        struct
        {
            Expr *left;
            Expr *right;
        } pair;
    };
};

我并没有学习过Lisp，所以关于这种数据类型，以下是Ai的回答:

在 C 语言这种静态强类型的语言中，变量的类型在编译时就固定了。但 Lisp 是一种动态类型语言，一个变量既可以是数字，也可以是字符串，甚至可以是一个列表。

为了用 C 语言模拟出 Lisp 的灵活性，这段代码使用了 标签联合体（Tagged Union，也叫有别联合） 的设计模式。下面我们逐一拆解这段代码的精妙之处，并解释它如何完美映射 Lisp 中的四大核心概念。

一、 Lisp 四大概念在代码中的映射

1. 表达式 (Expression)

在 Lisp 中，“万物皆为表达式”。代码、数据、数字、函数，全都是表达式。

  • 代码体现：整个 struct Expr 就是一个通用的“表达式”容器。

  • 设计逻辑：无论你手里的 Lisp 数据是一个单独的数字，还是一个包含几万个元素的列表，在 C 语言的函数签名里，它们统一都表现为 Expr *。这实现了高级语言中的多态性。

2. 原子 (Atom)

原子是不可分割的最小单元，对应代码中占位单一、不含有子表达式的类型。

  • 代码体现：

    • EXPR_INTEGER：对应 union 中的 int integer;。

    • EXPR_SYMBOL：对应 union 中的 const char *symbol;。

  • 设计逻辑：它们是“实心”的。当你拿到一个 Expr 且它的 kind 是这两者之一时，你直接读取里面的数值或字符串即可，不需要再做深层的递归解析。

3. 列表 (List)

列表是 Lisp 的灵魂，由点对（Cons Cell）链式拼接而成。

  • 代码体现：EXPR_PAIR 对应 union 中的 struct { Expr *left; Expr *right; } pair;。

  • 设计逻辑：这是典型的递归数据结构。一个 pair 有两个指针 left（通常叫 CAR）和 right（通常叫 CDR）。

    • left 指向当前列表的元素（它本身可以是一个原子，也可以是另一个列表）。

    • right 指向列表的“剩余部分”。

      通过这种嵌套，C 语言成功在堆内存中还原了 Lisp 链表。

4. NIL (空列表)

NIL 代表“无”，是列表的终点，也是空列表 '() 的化身。

  • 代码体现：EXPR_NIL。

  • 设计逻辑：注意看，union 里面根本没有为 EXPR_NIL 准备任何数据字段！因为 NIL 不需要存储任何额外信息。当 Expr 的 kind == EXPR_NIL 时，程序只要知道“到头了”或者“这里为空”即可，既省内存又非常安全。

二、 为什么要这样设计？

除了完美契合 Lisp 哲学，这段代码在 C 语言的工程实践上拉满了细节：

1. enum + union：打造安全的动态类型

C 语言的 union（联合体）允许不同的变量共享同一块内存。但 union 有一个致命缺点：它不知道自己当前存的到底是哪种类型。 如果你存入了一个指针，却按整数去读取，程序就会引发段错误。

  • 解决方案：在 union 前面强行塞入一个 Expr_Kind kind;。

  • 工作流：每次你要用这个 Expr 时，先用 switch(expr->kind) 判断它是什么。如果是 EXPR_INT，你才去读 expr->integer。这个 kind 就是那块内存的**“身份证”**。

2. 匿名联合体 (Anonymous Union)

观察代码，union 后面并没有变量名（没有写 union { ... } data;）。

  • 好处：在访问数据时，你可以直接写 expr->integer 或 expr->pair.left，而不需要写成冗长的 expr->data.integer。这让代码极其干净。

3. 极致的内存优化

因为使用了 union，struct Expr 的总大小只取决于它内部占用空间最大的那个成员。

  • 在 64 位系统上，pair 包含两个指针（$8 + 8 = 16$ 字节），这是最大的。

  • 所以，无论这个 Expr 存的是 NIL、一个整数，还是一个复杂的列表节点，它在内存中都只占固定的（16 字节的数据 + 4 字节的枚举 + 内存对齐填充）。这对于需要频繁分配小对象的 Lisp 解释器来说，内存碎片极小，性能极高。

4. 惊艳的编译时防御：__count_expr_kind 与断言

这是最体现作者 C 语言功底的地方：

1
2
3
4
5
6
7
8
9
typedef enum {
    EXPR_NIL,        // 0
    EXPR_SYMBOL,     // 1
    EXPR_INTEGER,    // 2
    EXPR_PAIR,       // 3
    __count_expr_kind, // 4 （利用枚举递增特性，自动算出前面有4个元素）
} Expr_Kind;

static_assert(__count_expr_kind == 4, "Amount of expression kinds has changed");

  • 设计痛点：在后续开发中，如果你想给 Lisp 增加一个“浮点数”类型（EXPR_FLOAT），你会在 enum 里插上一行。但很多程序员会忘记去修改 eval 里的 switch-case，或者忘记修改对应的分配函数，导致难以排查的 Bug。

  • 解决方案：作者在 struct Expr 的定义里直接写了 static_assert。如果你敢在 enum 里多加一个类型，__count_expr_kind 就会变成 5。此时编译器会直接拒绝编译并报错。它强迫你在增加新类型时，必须顺便把这个断言改成 5。而当你去改这个 5 的时候，你就会猛然醒悟：“哦！我还得去其他地方适配这个新类型！”

有了数据类型之后，我们就可以构造这一切了

在main.c中，我们有四个构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Expr *alloc_expr(Expr_Kind kind)
{
    Expr *expr = rc_alloc(sizeof(Expr), destroy_expr);
    expr->kind = kind;
    return expr;
}

static_assert(__count_expr_kind == 4, "Amount of expression kinds has changed.Change the ctors");

Expr *make_nil(void)
{
    return alloc_expr(EXPR_NIL);
}

Expr *make_integer(int integer)
{
    Expr *expr = alloc_expr(EXPR_INTEGER);
    expr->integer = integer;
    return expr;
}

Expr *make_symbol(const char *symbol)
{
    Expr *expr = alloc_expr(EXPR_SYMBOL);
    expr->symbol = symbol;
    return expr;
}

Expr *make_pair(Expr *left, Expr *right)
{
    Expr *expr = alloc_expr(EXPR_PAIR);
    expr->pair.left = rc_acquire(left);
    expr->pair.right = rc_acquire(right);
    return expr;
}

这些函数负责将 rc_alloc 申请的原始内存“格式化”为具体的 Lisp 表达式。

  • make_nil()：创建一个空列表。

  • make_symbol(const char *name)：创建一个符号。

  • make_integer(int value)：创建一个整数。

  • make_pair(Expr *left, Expr *right)：创建一个点对（Cons Cell）。这是唯一一个递归的构造函数，它会调用 rc_acquire 来接管子节点的所有权。

正是通过对rc_alloc的调用，让rc.h拥有了对于expr类型的管理能力

为什么在make_pair的时候需要接管子节点的所有权？

这是一个非常深刻的问题，触及了 生命周期管理 与 数据结构完整性 的核心。

简单直接的回答是：为了防止“过河拆桥”。

在 C 语言中，如果你创建了一个父节点（Pair），但它不“接管”子节点的所有权，那么子节点随时可能被外界释放，导致父节点手里握着两个指向荒原的野指针。

我们可以从以下三个逻辑维度来深度拆解这个设计：

1. 逻辑上的“从属关系”

在 Lisp 的列表结构中，一个 Pair 节点是由 left 和 right 组成的复合体。

  • 从逻辑上看，left 和 right 现在是这个 Pair 的组成部分。

  • 如果父节点不接管所有权，它就无法保证自己生命周期内的完整性。

如果不接管会发生什么？

假设你写了这样一段代码：

1
2
3
4
Expr *a = make_integer(10);
Expr *p = make_pair(a, make_nil());
rc_release(a); // 如果 make_pair 没调 rc_acquire
// 此时 a 被销毁了，p->pair.left 变成了一个野指针！

正是因为 make_pair 内部调用了 rc_acquire(left)，使得 a 指向的内存计数变为 2（一份在变量 a 手里，一份在父节点 p 手里）。即便外界释放了 a，计数依然为 1，内存安全无恙。

2. 支撑“递归释放”的连锁反应

你之前在研究 rc_release 时看到了它会调用 rc->destroy(rc + 1)。这个递归清理机制之所以能跑通，全赖 make_pair 当初接管了所有权。

  • 构建时：make_pair 通过 rc_acquire 建立了“父子契约”。

  • 销毁时：当父节点 p 被 rc_release 且计数归零时，它的析构函数 destroy_expr 也会被触发。

  • 权力交接：destroy_expr 内部会对 left 和 right 调用 rc_release。

核心逻辑： 如果你当初没有 acquire（计数没加），现在的 release（计数减一）就会导致子节点被提前错误释放。只有**“生时接管，死时交出”**，才能保证整棵树的内存管理是闭环的。

3. 应对“多重引用”的复杂场景

Lisp 最强大的地方在于数据共享。

想象一下：一个复杂的表达式 A，既是列表 B 的头部，又是列表 C 的尾部。

  • 场景：A 被 B 和 C 同时持有。

  • 机制：

    1. make_pair(A, ...) 给 B 用，A 计数 $+1$。

    2. make_pair(..., A) 给 C 用，A 计数再 $+1$。

  • 结果：此时 A 的计数器精确地记录了它被两个父节点共享。无论 B 还是 C 谁先死，只要另一个还活着，A 就不会被销毁。

这种 “去中心化” 的内存管理，必须依靠每一个 make_pair 在创建时自觉地通过 rc_acquire 宣示主权。

“make_pair 就像是一个领养机构。当你把两个子节点 left 和 right 交给它组成一个新的家庭（Pair）时，它不能只是简单地‘看着’它们，而是必须通过 rc_acquire 正式办理领养手续（接管所有权）。

这样一来，即便原本的亲生父母（创建子节点的函数）撒手不管了，只要这个家庭还存在，孩子们就是安全的。而当这个家庭最终解散时，它也会负责任地通过析构函数，帮孩子们寻找下一条出路（递归释放）。”

make_pair 接管所有权，是为了实现 “数据结构的自完备性”。它让每一个 Expr 节点都变成了一个能自感知、自负责的独立生命体，从而构建出 Lisp 那样复杂而稳固的语法树。

有构造，就会有析构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void destroy_expr(void *data)
{
    Expr *expr = data;
    switch (expr->kind)
    {
    case EXPR_NIL:
    case EXPR_SYMBOL:
    case EXPR_INTEGER:
        break;
    case EXPR_PAIR:
        rc_release(expr->pair.left);
        rc_release(expr->pair.right);
        break;
    case __count_expr_kind:
        break;
    default:
    {
        UNREACHABLE("Expr_Kind");
    }
    }
}

这个函数与rc.h进行配合使用，在rc_release中进行对应结构的资源清理，正如前文提到的，我们正式通过这层解耦，实现了对于EXPR_PAIR类型的递归资源释放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define dump_expr(expr) dump_expr_opt(expr, 0)
void dump_expr_opt(Expr *expr, int level)
{
    for (int i = 0; i < level; ++i)
    {
        printf("  ");
    }
    switch (expr->kind)
    {
    case EXPR_NIL:
    {
        printf("NIL(%td)\n", rc_count(expr));
    }
    break;

    case EXPR_SYMBOL:
    {
        printf("SYMBOL(%td): %s\n", rc_count(expr), expr->symbol);
    }
    break;
    case EXPR_INTEGER:
    {
        printf("INTEGER(%td): %d\n", rc_count(expr), expr->integer);
    }
    break;
    case EXPR_PAIR:
    {
        printf("PAIR(%td):\n", rc_count(expr));
        dump_expr_opt(expr->pair.left, level + 1);
        dump_expr_opt(expr->pair.right, level + 1);
    }
    break;
    case __count_expr_kind:
        break;
    default:
        UNREACHABLE("EXPR_Kind");
        break;
    }
}

这是一个打印信息的调试函数，这个函数倒是没什么，就仅仅是在类型为EXPR_PAIR时会循环调用他自己而已。并且我们通过宏来模拟了默认参数这个东西

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Expr *args_to_list(va_list args)
{
    Expr *arg = va_arg(args, Expr *);
    if (arg->kind == EXPR_NIL)
        return arg;
    return make_pair(arg, args_to_list(args));
}

#define make_list(...) make_list_impl(NULL, __VA_ARGS__, make_nil())

Expr *make_list_impl(void *first, ...)
{
    va_list args;
    va_start(args, first);
    Expr *list = args_to_list(args);
    va_end(args);
    return list;
}

这一块其实是很有意思的。

我们为什么需要一个make_list呢？make_pair(make_integer(1),make_pair(make_integer(2),make_pair(make_integer(3), make_nil())));

我相信没有人会想看到这一串破玩意儿的。所以我们构造了args_to_list和make_list_impl这两个函数，以及make_list宏

一、 宏的“预处理陷阱”：强制哨兵机制

在 C 语言中，处理变长参数（va_list）最头疼的问题是：函数不知道参数什么时候结束。 通常做法是要求调用者手动传一个 NULL，但这极易被遗忘。

作者通过宏 make_list 巧妙地解决了这个问题：

  1. 它在用户传入的参数 __VA_ARGS__ 后面自动追加了一个 make_nil()。

  2. 无论你写 make_list(a, b) 还是 make_list(a)，预处理器都会在末尾补上一个 NIL。

  3. 这个补上的 NIL 充当了哨兵（Sentinel），告诉后面的解析逻辑：“到这里就结束了”。

二、 为什么非要用递归？防止列表“反过来”

你可能会好奇，为什么要专门写一个递归的 args_to_list，而不是直接用 for 循环遍历参数？

这里涉及到栈与链表的结构冲突：

如果用简单的循环去构造列表，代码逻辑通常是“每拿到一个新元素，就把它插在当前列表的最前面”。

  • 输入：1, 2, 3

  • 循环过程：

    1. NIL

    2. make_pair(1, NIL) -> (1)

    3. make_pair(2, (1)) -> (2 1)

    4. make_pair(3, (2 1)) -> (3 2 1)

  • 结果：顺序完全反了。

而 args_to_list 通过 递归的回溯（Backtracking） 完美保持了顺序：

1
return make_pair(arg, args_to_list(args));

在这个调用中，make_pair 必须等待递归底部的 args_to_list 返回结果后才能执行。

执行逻辑（“先深入，后构造”）：

  1. 递进阶段：拿到 1（等着） -> 拿到 2（等着） -> 拿到 3（等着） -> 撞到哨兵 NIL。

  2. 回溯阶段：从 NIL 开始，倒序往回“焊接”：

    • make_pair(3, NIL)

    • make_pair(2, (3))

    • make_pair(1, (2 3))

  3. 最终输出：(1 2 3)。

那么现在我们就剩下main以及eval函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Expr *eval(Expr *expr)
{
    if (expr->kind == EXPR_PAIR)
    {
        assert(expr->pair.left->kind == EXPR_SYMBOL);
        if (strcmp(expr->pair.left->symbol, "+") == 0)
        {
            int result = 0;
            Expr *args = expr->pair.right;
            while (args->kind != EXPR_NIL)
            {
                assert(args->kind == EXPR_PAIR);
                assert(args->pair.left->kind == EXPR_INTEGER);
                result += args->pair.left->integer;
                args = args->pair.right;
            }
            return make_integer(result);
        }
        else if (strcmp(expr->pair.left->symbol, "swap") == 0)
        {
            Expr *args = expr->pair.right;
            assert(args->kind == EXPR_PAIR);
            assert(args->pair.left->kind == EXPR_PAIR);
            assert(args->pair.right->kind == EXPR_NIL);
            Expr *arg = args->pair.left;
            return make_pair(arg->pair.right, arg->pair.left);
        }
        else
        {
            TODO("Report unknow function error");
        }
    }
    else
    {
        return expr;
    }
}

eval 函数是解释器的求值入口，它根据表达式的 kind 标签进行逻辑分发：如果是整数等原子类型则直接原样返回；如果是列表（Pair），则默认将第一个元素视为符号指令，后续部分视为参数。在执行 + 指令时，它通过 while 循环遍历参数链表，将内部的整数逐个累加，最后返回一个新的整数对象；在执行 swap 指令时，它则通过重新解构和组合指针，将传入的点对进行左右对调并返回。这种设计通过大量的 assert 确保了输入结构的合法性，并利用底层的 make_ 系列函数在计算过程中生成新的结果对象，是整个解释器从“静态数据”转向“动态计算”的核心环节。

这个其实跟Rc的关系已经不大了，Rc更接近于管理这一切的底层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int main()
{
    printf("========== Lisp 解释器功能与内存测试 ==========\n\n");

    // --- 测试 1: 加法功能 (+ 10 20 30) ---
    printf("【测试 1: 加法运算 (+ 10 20 30)】\n");
    Expr *add_expr = rc_acquire(make_list(
        make_symbol("+"),
        make_integer(10),
        make_integer(20),
        make_integer(30)));

    printf("构造表达式: ");
    dump_expr(add_expr);
    printf("当前引用计数: %td\n", rc_count(add_expr));

    printf("--- 执行 Eval ---\n");
    Expr *add_result = rc_acquire(eval(add_expr));
    printf("计算结果: ");
    dump_expr(add_result);

    printf("--- 释放内存 ---\n");
    rc_release(add_expr);
    rc_release(add_result);
    printf("加法测试内存已安全释放\n\n");

    // --- 测试 2: 结构交换 (swap (69 . 420)) ---
    printf("【测试 2: 结构交换 (swap (69 . 420))】\n");
    // 构造 (swap (69 . 420))
    Expr *swap_expr = rc_acquire(make_list(
        make_symbol("swap"),
        make_pair(make_integer(69), make_integer(420))));

    printf("原始表达式: ");
    dump_expr(swap_expr);

    printf("--- 执行 Eval ---\n");
    Expr *swap_result = rc_acquire(eval(swap_expr));

    printf("交换后结果: ");
    dump_expr(swap_result);
    printf("结果引用计数: %td\n", rc_count(swap_result));

    printf("--- 验证：释放原始表达式 ---\n");
    rc_release(swap_expr);
    // 此时 swap_expr 已销毁，但 swap_result 应该依然有效
    printf("原始表达式已释放，结果依然存活: ");
    dump_expr(swap_result);

    printf("--- 最终清理 ---\n");
    rc_release(swap_result);
    printf("所有内存已归还系统\n");

    printf("\n================ 测试结束 ================\n");
    return 0;
}

这里放一段ai生成的main以及运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
========== Lisp 解释器功能与内存测试 ==========

【测试 1: 加法运算 (+ 10 20 30)】
[RC] 000001F17C372460 allocated
[RC] 000001F17C372400 allocated
[RC] 000001F17C372490 allocated
[RC] 000001F17C372760 allocated
[RC] 000001F17C3722E0 allocated
[RC] 000001F17C372310 allocated
[RC] 000001F17C372670 allocated
[RC] 000001F17C372220 allocated
[RC] 000001F17C3727F0 allocated
构造表达式: PAIR(1):
  SYMBOL(1): +
  PAIR(1):
    INTEGER(1): 10
    PAIR(1):
      INTEGER(1): 20
      PAIR(1):
        INTEGER(1): 30
        NIL(1)
当前引用计数: 1
--- 执行 Eval ---
[RC] 000001F17C372340 allocated
计算结果: INTEGER(1): 60
--- 释放内存 ---
[RC] 000001F17C372460 released
[RC] 000001F17C372400 released
[RC] 000001F17C372490 released
[RC] 000001F17C372760 released
[RC] 000001F17C3722E0 released
[RC] 000001F17C372310 released
[RC] 000001F17C372670 released
[RC] 000001F17C372220 released
[RC] 000001F17C3727F0 released
[RC] 000001F17C372340 released
加法测试内存已安全释放

【测试 2: 结构交换 (swap (69 . 420))】
[RC] 000001F17C372490 allocated
[RC] 000001F17C372250 allocated
[RC] 000001F17C372640 allocated
[RC] 000001F17C372730 allocated
[RC] 000001F17C372580 allocated
[RC] 000001F17C372790 allocated
[RC] 000001F17C372550 allocated
原始表达式: PAIR(1):
  SYMBOL(1): swap
  PAIR(1):
    PAIR(1):
      INTEGER(1): 69
      INTEGER(1): 420
    NIL(1)
--- 执行 Eval ---
[RC] 000001F17C372610 allocated
交换后结果: PAIR(1):
  INTEGER(2): 420
  INTEGER(2): 69
结果引用计数: 1
--- 验证：释放原始表达式 ---
[RC] 000001F17C372490 released
[RC] 000001F17C372730 released
[RC] 000001F17C372580 released
[RC] 000001F17C372790 released
[RC] 000001F17C372550 released
原始表达式已释放，结果依然存活: PAIR(1):
  INTEGER(1): 420
  INTEGER(1): 69
--- 最终清理 ---
[RC] 000001F17C372640 released
[RC] 000001F17C372250 released
[RC] 000001F17C372610 released
所有内存已归还系统

================ 测试结束 ================

这个Lisp解释器对于一个没有接触过函数式编程的我来说还是太难理解了，燃尽了。。。。

不过我其实还是很好奇这套gc还可以用在哪些地方上面

发表于 更新于

我们在上篇博客中通过提取状态转移这个步骤为函数，实现了状态进入/退出动作的自动执行，在这篇博客中，我们将加入层次状态这个内容

顺带一提，这个层次状态真是看的我头痛，因为C语言并不是一门面向对象语言，所以我们在这里发生了一些并不令人愉快的抽象泄露

一、父状态的实现机制拆解

1. 数据结构的基石：parent_state 数组

1
State parent_state[STATE_COUNT];

初始化：

1
2
3
4
fsm->parent_state[STATE_IDLE]    = -1;          // 根状态
fsm->parent_state[STATE_ACTIVE]  = -1;          // 容器状态，本身无父
fsm->parent_state[STATE_PLAYING] = STATE_ACTIVE;
fsm->parent_state[STATE_PAUSED]  = STATE_ACTIVE;

这个数组构建了一棵单父树，每个状态最多有一个直接父状态。-1 表示该状态是顶层节点。

2. 事件冒泡：从子到父的查找链

1
2
3
4
5
6
7
8
9
10
void fsm_dispatch(StateMachine *fsm, Event evt) {
    State current = fsm->current_state;
    while (current != -1) {
        fsm->state_table[current](fsm, evt);   // 尝试让当前状态处理
        if (fsm->current_state != current) {    // 状态变了？
            break;   // 事件被处理，停止冒泡
        }
        current = fsm->parent_state[current];   // 未处理，向父状态回溯
    }
}

核心逻辑：

  • 事件首先交给叶子状态（如 Playing）处理。
  • 如果该状态函数不改变 current_state（即忽略事件），则循环继续，将 current 更新为其父状态（Active）。
  • 父状态的处理函数被调用，若它执行了转移（改变了 current_state），循环终止。
  • 若一直回溯到 -1 仍无状态处理，事件被丢弃。

这相当于在运行时动态查找当前状态下针对该事件的有效转移，优先子状态，后父状态。

3. 转移时的层次进入/退出顺序

版本3中采用了硬编码判断，因为已知层次结构只有一层：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static void fsm_transition_to(StateMachine *fsm, State target) {
    if (fsm->current_state == target) {
        return;
    }
    // 1. 找出从当前状态到目标状态需要退出的状态路径
    //    原理：从当前叶子向上找父状态，直到找到与目标状态的公共祖先。
    //    为简化，本例硬编码处理，完整通用算法将在博客中说明。
    State old = fsm->current_state;
    State new = target;
    printf("[Transition] %d -> %d\n", old, new);
    // ---------- 执行退出动作（自底向上） ----------
    // 退出当前叶子
    if (fsm->exit_actions[old])
        fsm->exit_actions[old]();
    // 如果当前叶子有父状态且与目标的祖先不同，则继续退出父状态
    if ((old == STATE_PLAYING || old == STATE_PAUSED) && (new == STATE_IDLE)) {
        if (fsm->exit_actions[STATE_ACTIVE])
            fsm->exit_actions[STATE_ACTIVE]();
    }
    // ---------- 更新当前状态 ----------
    fsm->current_state = new;

    if ((new == STATE_PLAYING || new == STATE_PAUSED) &&
        (old != STATE_PLAYING && old != STATE_PAUSED)) {
        if (fsm->entry_actions[STATE_ACTIVE])
            fsm->entry_actions[STATE_ACTIVE]();
    }
    if (fsm->entry_actions[target]) {
        fsm->entry_actions[target]();
    }
}

设计思想：

  • 利用 parent_state 的隐含知识：Playing 和 Paused 同属一个父状态 Active。
  • 通过判断目标状态是否在 Active 的“子状态集合”内，来决定是否执行父状态的进入/退出动作。
  • 顺序上：先处理子状态自己的退出动作，再判断是否需要退出父状态；进入时相反。

二、为什么要这么实现？

1. 为什么不用嵌套 switch-case？

嵌套 switch 的层次实现：

1
2
3
4
5
6
switch (current_state) {
    case STATE_PLAYING:
    case STATE_PAUSED:
        // 共享代码？
        break;
}
  • 无法优雅地复用进入/退出动作（Active 的 entry/exit 需要在每个子状态转移时手动插入）。
  • 事件处理代码会急剧膨胀，难以维护。

2. 为什么不用函数递归模拟继承？

递归方案（每个状态函数返回一个布尔值表示是否处理）确实更“优雅”，但：

  • 每次事件都需要多层函数调用，在资源紧张的MCU上可能造成栈溢出。
  • 状态处理函数需要额外返回值，接口复杂化。

3. 为什么使用 parent_state 数组 + 循环？

  • 内存效率：每个状态只需一个字节（或枚举大小）的存储。
  • 速度：while 循环比递归调用开销小，且无栈风险。
  • 确定性：适合硬实时系统，行为完全可预测。

三、更好的实现方案？

方案A：状态嵌套结构体（显式层次）

1
2
3
4
5
6
7
8
9
10
11
typedef struct State {
    StateID id;
    struct State *parent;          // 指向父状态
    void (*entry)(void);
    void (*exit)(void);
    void (*handle)(struct State *self, Event e);
} State;

State active = { .parent = NULL, ... };
State playing = { .parent = &active, ... };
State paused  = { .parent = &active, ... };

优点：层次关系通过指针直接可见，parent 指针就是天然的冒泡路径。
缺点：占用内存更大（每个状态需存储多个指针），且需额外处理状态ID到结构体指针的映射。

这个其实就是之前提到过的面向对象模拟法

方案B：状态处理函数返回处理标志

1
2
3
4
5
6
7
8
9
10
11
typedef bool (*StateHandler)(StateMachine *fsm, Event evt);

void fsm_dispatch(StateMachine *fsm, Event evt) {
    State current = fsm->current_state;
    while (current != -1) {
        if (fsm->state_table[current](fsm, evt)) {
            break;   // 返回 true 表示事件已处理
        }
        current = fsm->parent_state[current];
    }
}

优点：语义清晰，不需要通过检查 current_state 是否改变来判断处理与否。
缺点：状态函数必须返回布尔值，且如果转移发生在更深层调用的函数中，返回值传递会复杂化。

这个其实会更直观

方案C：真正的LCA算法（通用层次引擎）

1
2
3
4
5
6
7
8
9
10
11
// 伪代码
void transition_to(StateMachine *fsm, State target) {
    // 1. 计算LCA（最小公共祖先）
    State lca = find_lca(fsm->current_state, target);
    // 2. 从当前状态退出到LCA（自底向上）
    exit_to_lca(fsm->current_state, lca);
    // 3. 从LCA进入目标状态（自顶向下）
    enter_from_lca(lca, target);
    // 4. 更新当前状态
    fsm->current_state = target;
}

这是完全符合UML规范的实现，可以处理任意深度的嵌套、正交区域等。但需要：

  • 为每个状态存储完整的祖先路径，或维护状态深度和父链。
  • 复杂的路径比较算法。

QP/C框架就是采用这种方案，其核心引擎约800行C代码。

或许在遥远的未来，我会去研究这个QP/C(最好是)

方案D：状态表 + 编译期层次展开（宏魔法）

利用X宏或C预处理器技巧，在编译期生成扁平的状态转移表，同时将层次语义转换为索引计算。例如：

1
2
3
4
5
#define STATES \
    X(IDLE)    \
    X(ACTIVE)  \
    X(PLAYING, ACTIVE) \
    X(PAUSED, ACTIVE)

通过宏生成 parent_state 数组和转移表。这种方法在大型项目中能减少手动维护错误，但代码可读性下降。

可读性真的下降的很多了

这里插一嘴关于这个宏方法的实现

1
2
3
4
5
6
7
8
9
10
// states.def —— 状态定义文件（无头文件保护，可被多次包含）

// 格式：X(状态枚举名, 父状态枚举名或-1, 进入动作函数名, 退出动作函数名)
// 父状态为 -1 表示顶层状态

X(STATE_IDLE,    -1,            entry_idle,    NULL)
X(STATE_ACTIVE,  -1,            entry_active,  exit_active)
X(STATE_PLAYING, STATE_ACTIVE,  entry_playing, exit_playing)
X(STATE_PAUSED,  STATE_ACTIVE,  entry_paused,  exit_paused)
X(STATE_MENU,    -1,            entry_menu,    exit_menu)

基本上来说就是一个X宏，记录了多种元素，在需要的地方用不同的宏进行二次展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
typedef struct {
    State current_state;
    
    // 指向外部生成的静态表
    const State *parent_state; 
    void (*const *entry_actions)(void); 
    void (*const *exit_actions)(void);
    
    // ... 其他成员
} StateMachine;

// 1. 生成状态枚举
typedef enum {
#define X(name, parent, entry_func, exit_func) name,
#include "states.def"
#undef X
    STATE_COUNT
} State;

// 2. 生成父状态数组
static const State parent_state[STATE_COUNT] = {
#define X(name, parent, entry_func, exit_func) parent,
#include "states.def"
#undef X
};

// 3. 生成进入动作函数指针表
static void (*const entry_actions[STATE_COUNT])(void) = {
#define X(name, parent, entry_func, exit_func) entry_func,
#include "states.def"
#undef X
};

// 4. 生成退出动作函数指针表
static void (*const exit_actions[STATE_COUNT])(void) = {
#define X(name, parent, entry_func, exit_func) exit_func,
#include "states.def"
#undef X
};

// 5. 生成状态名称字符串表（便于调试）
static const char *state_names[STATE_COUNT] = {
#define X(name, parent, entry_func, exit_func) #name,
#include "states.def"
#undef X
};

void fsm_init(StateMachine *fsm) {
    fsm->current_state = STATE_IDLE;
    fsm->history_active = -1;
    // 将生成的静态表赋值给状态机实例
    fsm->parent_state  = parent_state;
    fsm->entry_actions = entry_actions;
    fsm->exit_actions  = exit_actions;
    fsm->state_table   = state_table;

    // 执行初始状态进入动作
    if (fsm->entry_actions[fsm->current_state]) {
        fsm->entry_actions[fsm->current_state]();
    }
}

当然，在这种将状态机成员置于全局数据段的写法下，我们在结构体内部很明显更适合存储指针而不是完整的数组成员

当前方案采用树形结构的扁平化存储，通过维护一个 parent_state 数组，显式记录每个状态节点的父节点索引。

数组中元素取值规则为：

  • 若值为 -1，表示该状态为根节点，无父节点；
  • 若为非 -1 数值，则该数值直接对应其父节点的索引，以此建立节点间的层级关联。

整体思路是用线性数组结构模拟树形层级关系，通过索引映射替代显式的树形指针或嵌套结构。

发表于

我们在上篇博客中简单探索了一下表函数法实现的FSM，我们通过函数指针跟结构体的配合来消除了巨大的 switch(current_state)，每个状态独立成函数，易于扩展。状态处理函数 = δ 函数的分段实现。 state_table[s](fsm, e) 执行 δ(s, e)。

局限：

  • 没有“动作”的概念。转移时无法自动执行硬件初始化/清理。

  • 没有“层次”。多个状态共享行为时，代码重复。

我们在这篇博客中，我们要给它实现”动作”这个概念

1
2
3
4
5
6
7
struct StateMachine {
    State        current_state;
    StateHandler state_table[STATE_COUNT];
    // 进入和退出动作表
    void (*entry_actions[STATE_COUNT])(void); // 函数指针数组
    void (*exit_actions[STATE_COUNT])(void);
};

观察我们全新的StateMachine结构体的声明，可以发现它的内部多了两个新的成员，这两个成员其实也是指针数组。存储的数据类型为void ()(void)

顺便一提，C语言有时候这个语法真的是有些逆天，就算我们有所谓的右左法则，但是我觉得用typedef简化复杂类型的声明也是合理的

函数如其名，我们为每一个状态新增了对应的进入函数跟退出函数。

1
2
3
static void entry_closed(void) {
    printf("  [Action] entry Closed: motor off\n");
}

当然，在这个简单的demo中，它们也仅仅就只是打印了一些我们需要的文本而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void fsm_init(StateMachine *fsm) {
    fsm->current_state             = STATE_CLOSED; // 初始状态
    fsm->state_table[STATE_CLOSED] = state_closed;
    fsm->state_table[STATE_OPENED] = state_opened;

    // 注册进入/退出动作
    fsm->entry_actions[STATE_CLOSED] = entry_closed;
    fsm->exit_actions[STATE_CLOSED]  = exit_closed;
    fsm->entry_actions[STATE_OPENED] = entry_opened;
    fsm->exit_actions[STATE_OPENED]  = exit_opened;

    // 手动执行初始状态的进入动作（因为初始状态没有“转移进入”）
    if (fsm->entry_actions[fsm->current_state]) {
        fsm->entry_actions[fsm->current_state]();
    }
}

上篇博客好像没有讲解这个fsm_init函数，这个函数基本上就是初始化了一下我们所要用到的状态机结构体，我们在这个版本的代码中，仅仅只是增加了对于每个状态进入/退出动作的注册。以及对于初始状态的进入动作的手动执行。

我们在这个版本中最重要的变动就是新增了一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void fsm_transition_to(StateMachine *fsm, State next_state) {
    if (fsm->current_state == next_state) {
        // do someting here,自转移通常也需要执行exit/entry，但是按需决定
        return;
    }

    // 1.执行当前状态的退出动作
    if (fsm->exit_actions[fsm->current_state]) {
        fsm->exit_actions[fsm->current_state]();
    }
    // 2.更新状态
    fsm->current_state = next_state;
    // 3.执行新状态的进入动作
    if (fsm->entry_actions[fsm->current_state]) {
        fsm->entry_actions[fsm->current_state]();
    }
}

这个函数专门负责状态机的状态切换，把原本放在状态处理函数里的状态跳转逻辑抽离出来，统一由它管理。

它会自动执行旧状态的退出动作、更新当前状态、再执行新状态的进入动作。

和 fsm_dispatch 思想类似，把进入 / 退出动作封装成函数指针调用，大幅减少新增状态时的重复代码。

透过这种改动，我们现在拥有了转移时自动执行硬件初始化/清理的功能，并且将硬件操作与状态绑定，而非与事件绑定。

我们在下一篇博客中，将会给这个框架新增层次状态的功能。

发表于 更新于

最近在学习关于有限状态机的知识，感觉有点麻头，写个博客输出一下

一、有限状态机的数学本质

有限状态机（Finite State Machine, FSM）是一个五元组：

text

( Σ, S, s0, δ, F )

  • Σ：有限的事件集合（输入字母表）

  • S：有限的状态集合

  • s0：初始状态（s0 ∈ S）

  • δ：状态转移函数 δ: S × Σ → S

  • F：终止状态集合（可空，嵌入式系统通常无终止状态）

用一句话概括：
给定当前状态和输入事件，状态转移函数 δ 唯一地确定下一个状态。

一个简单的demo是这样的

1
2
3
4
5
6
7
8
9
10
11
12
State current = CLOSED;

void handle_event(Event e) {
    switch (current) {
        case CLOSED:
            if (e == OPEN) current = OPENED;
            break;
        case OPENED:
            if (e == CLOSE) current = CLOSED;
            break;
    }
}

在这个handel_event内，我们用一个switch实现了根据当前状态和传入的事件，进行状态·切换的功能。

毫无疑问它是可用的，但当你面对以下现实需求时，switch-case 会迅速变成灾难：

  1. 状态数量增加（例如播放器有 10+ 状态）→ switch 嵌套太深。

  2. 需要进入/退出动作（控制硬件）→ 每个 case 里都要重复写硬件操作。

  3. 多个状态共享行为（例如“停止”在多个状态下都要回到 Idle）→ 代码重复。

  4. 需要记住离开时的子状态（历史状态）→ 无法用纯 δ 函数表达。

在C语言中实现有限状态机（FSM）的方法主要有以下5种常见方式，如果考虑变体或组合可扩展至更多，但核心典型方法如下：

  1. switch 语句法
    最经典的方法，用 switch(state) 分支处理每个状态下的事件和转移。代码直观，适合状态数不多的FSM。

  2. 函数指针表法
    为每个状态定义一个处理函数，用函数指针数组或结构体数组存储，当前状态对应函数被调用，函数内执行动作并返回下一状态。适合状态多、逻辑复杂的FSM。

  3. 状态转移表法
    构建二维表（或结构体数组），行表示当前状态，列表示输入事件，表项为目标状态和/或动作函数指针。通过查表驱动转移，易于维护和动态修改。

  4. goto 标签法（Duff风格或状态机模式）
    利用 goto 和标签实现类似协程的FSM，常见于嵌入式或解析器（如Protothreads）。不推荐用于大型系统，但可手动模拟可抢占状态机。

  5. 面向对象模拟法
    用结构体封装状态变量和函数指针（类似虚表），模拟C++的多态行为。每个状态是一个“类”，通过统一接口调用。适合需要状态复用或继承的场景。

此外，还有枚举+宏封装、消息队列+状态机等变体，但本质是上述方法的组合。因此，公认的核心实现方式通常为 3～5种。若按不同编程范式划分，可认为是 4～6种。实际应用中，switch和函数指针表最为常见。

我使用的方法是函数指针表法。

我们可以先来修改最上面那个简单的例子，本质上就是利用函数指针把耦合的代码给拆开来了，方便后期新增/修改状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 事件枚举
typedef enum {
    EVENT_OPEN,
    EVENT_CLOSE,
    EVENT_NONE
} Event;

// 状态枚举
typedef enum {
    STATE_CLOSED,
    STATE_OPENED,
} State;

#define STATE_COUNT = (sizeof(State)/sizeof(STATE_CLOSED))
typedef struct StateMachine StateMachine;
typedef void (*StateHandler)(StateMachine *fsm, Event evt);

struct StateMachine {
    State        current_state;
    StateHandler state_table[STATE_COUNT];
};

观察StateMachine结构体，我们可以发现，其中包含当前状态，以及一个指针数组，数组的元素类型为void (StateHandler)(StateMachine fsm, Event evt); 的数组，也就是上面所说的为每个状态定义一个处理函数，用函数指针数组或结构体数组存储，当前状态对应函数被调用，函数内执行动作并返回下一状态。适合状态多、逻辑复杂的FSM。** 该函数指针指向对应状态的处理函数。

我自认为FSM的核心在于

收到事件–>找到对应状态的处理函数–>执行状态转移

在之前的Switch的方法中，我们找到对应状态的处理函数这一步是在一个函数内由Switch语句完成的，但是在函数表法中，我们会有这样一个函数

1
2
3
4
5
void fsm_dispatch(StateMachine *fsm, Event evt) {
    if (evt == EVENT_NONE)
        return;
    fsm->state_table[fsm->current_state](fsm, evt);
}

该函数根据状态机当前状态，调用对应处理函数，参数为状态机自身与触发事件。

而接下来的执行状态转移这一步，在这个最为简单的demo中，我们直接在每个单独状态的处理函数中处理当前状态的切换，我们可以选一个状态的处理函数出来看一下。

1
2
3
4
5
6
7
8
9
10
11
static void state_closed(StateMachine *fsm, Event evt) {
    switch (evt) {
        case EVENT_OPEN:
            printf("[Closed]-> Opened (tigger:OPEN)\n");
            fsm->current_state = STATE_OPENED;
            break;
        default:
            printf("[Closed] Event ignored : %s\n", event_name(evt));
            break;
    }
}

其中fsm->current_state = STATE_OPENED; 这一句完成的功能就是实现当前状态的切换。

这就是我们这个最简单FSM demo 的核心代码部分，在接下来的博客中，我们会为其新增一些新的功能进去，代码的复杂度也会进一步提升。

我把完整的代码贴在下面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

// 事件枚举
typedef enum {
    EVENT_OPEN,
    EVENT_CLOSE,
    EVENT_NONE
} Event;

// 状态枚举
typedef enum {
    STATE_CLOSED,
    STATE_OPENED,
    STATE_COUNT // 仅用于标记状态个数
} State;

typedef struct StateMachine StateMachine;
typedef void (*StateHandler)(StateMachine *fsm, Event evt);

struct StateMachine {
    State        current_state;
    StateHandler state_table[STATE_COUNT];
};

const char *event_name(Event evt);
static void state_closed(StateMachine *fsm, Event evt);
static void state_opened(StateMachine *fsm, Event evt);

void fsm_init(StateMachine *fsm) {
    fsm->current_state             = STATE_CLOSED; // 初始状态
    fsm->state_table[STATE_CLOSED] = state_closed;
    fsm->state_table[STATE_OPENED] = state_opened;
}

void fsm_dispatch(StateMachine *fsm, Event evt) {
    if (evt == EVENT_NONE)
        return;
    fsm->state_table[fsm->current_state](fsm, evt);
}

static void state_closed(StateMachine *fsm, Event evt) {
    switch (evt) {
        case EVENT_OPEN:
            printf("[Closed]-> Opened (tigger:OPEN)\n");
            fsm->current_state = STATE_OPENED;
            break;
        default:
            printf("[Closed] Event ignored : %s\n", event_name(evt));
            break;
    }
}

static void state_opened(StateMachine *fsm, Event evt) {
    switch (evt) {
        case EVENT_CLOSE:
            printf("[Opened]-> Closed (tigger:CLOSE)\n");
            fsm->current_state = STATE_CLOSED;
            break;
        default:
            printf("[Opened] Event ignored: %s\n", event_name(evt));
            break;
    }
}

const char *event_name(Event evt) {
    switch (evt) {
        case EVENT_OPEN:
            return "OPEN";
        case EVENT_CLOSE:
            return "CLOSE";
        case EVENT_NONE:
            return "NONE";
    }
}

int main(void) {
    StateMachine fsm;
    fsm_init(&fsm);

    // 模拟事件序列
    Event test_events[] = {EVENT_OPEN,
        EVENT_OPEN, // 重复开门（应被忽略）
        EVENT_CLOSE,
        EVENT_CLOSE, // 重复关门（应被忽略）
        EVENT_OPEN};

    for (size_t i = 0; i < sizeof(test_events) / sizeof(test_events[0]); i++) {
        printf("\n[Event] %s\n", event_name(test_events[i]));
        fsm_dispatch(&fsm, test_events[i]);
        printf("[Current State] %s\n", fsm.current_state == STATE_CLOSED ? "Closed" : "Opened");
    }

    return 0;
}

发表于

我知道这个标题不太像人类，但是这不重要

我们可以先来看两段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main(int, char **)
{
    DynamicArray *arr = arr_init(3);
    arr_push(arr, 10);
    arr_push(arr, 20);
    arr_push(arr, 30);
    arr_print(arr);
    arr_free(arr);
    return 0;
}

int main(int, char **)
{
    int *numbers = NULL;
    arr_push(numbers, 69);
    arr_push(numbers, 420);
    arr_push(numbers, 1337);
    arr_push(numbers, 80085);
    for (size_t i = 0; i < arr_len(numbers); ++i)
    {
        printf("%d\n", numbers[i]);
    }
    arr_free(numbers);
}

第一个 main 函数中，我们初始化的是 DynamicArray * 类型的自定义动态数组结构体指针，后续所有操作函数均基于该指针类型实现；第二个 main 函数中，我们仅初始化了单纯的 int * 类型原生整型指针，配套的操作函数(宏)也仅针对这个明确数据类型的指针进行操作。

在 C 语言及绝大多数编程语言中，一个完整可用的动态数组，必须包含以下三个关键要素：

  1. 数据块 存储数组元素的连续内存空间，是动态数组的数据存储载体。

  2. 当前使用量 (count) 标记数组中有效元素的实际个数，用于控制遍历、访问边界。

  3. 容量 (capacity) 标记当前内存最大可容纳的元素总数，用于判断动态扩容的时机。

这个数据块部分，在C语言这边的话，一般来说都是由一个指向要存储元素类型的指针跟一套内存分配机制一起组成的(比如glib实现的malloc)。

在我们常见的实现方法中，这三部分通常会被存放在一个结构体中，大概像这样

1
2
3
4
5
typedef struct{
    int *items;      // 数组元素
    size_t count;    // 当前元素数量
    size_t capacity; // 数组容量
} DynamicArray;

我们通常会先初始化一个动态数组结构体变量(malloc或者栈分配)，再通过结构体内部的指针，操作存储数据的内存块；当容量 capacity 不足时执行的 realloc 重分配操作，就是这类内存操作的典型例子。

而我们今天提到的 Header_Array（头部数组），其典型的 Header 结构体声明如下：

1
2
3
4
typedef struct{
    size_t count;
    size_t capacity;
} Header;

我们可以发现，这个结构体中并没有存储数组元素的成员。基于此，我们可以提出两个关键问题：

  • 如果仅观察 main 函数的代码：管理数组所需的头部信息究竟存放在哪里？

  • 如果仅分析这个 Header 结构体：数组的实际数据又存储在什么地方？

在标准实现中，头部信息会存储在显式定义的结构体变量中，我们通过变量内部的指针对数据进行操作；此时，存储头部信息与存储实际数据的内存可能是相互分离、不连续的。

而在Header_Array（头部数组）中，整个动态数组占用一整块连续的内存，头部信息会隐式地存储在数据段的前方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
┌──────────────────────────────────────────────────────┐
│  DynamicArray 结构体 (栈上或堆上，此处假设堆上)           │
├──────────────────────────────────────────────────────┤
│  count     │  capacity   │  items 指针                │
│  (size_t)  │  (size_t)   │  (int*)                   │
│     4      │     6       │  ────────┐                │
└────────────┴─────────────┴──────────┼────────────────┘
                                      │
                                      ↓
                         ┌─────────────────────────────┐
                         │  数据区（另一个独立堆块）       │
                         ├─────────────────────────────┤
                         │  10 │ 20 │ 30 │ 40 │  ? │ ? │
                         └─────────────────────────────┘

┌───────────────────────────────────────────────┐
│  Header           │  数据区（用户可访问）       │
│  (count, capacity)│  [0] [1] [2] [3] ...     │
└───────────────────────────────────────────────┘
▲                  ▲
│                  │
header指针         arr 指针（用户持有）
(Header*)(arr)-1

这种 Header_Array 还有一个显著优势：借助宏展开，可以很方便地实现泛型动态数组。

当然，这本身也是侵入式数据结构的一大特性，这部分内容我们可以放在最后再展开说明。

实现该操作依赖的核心语法特性是：对指针进行加减运算时，地址偏移量由指针指向的数据类型大小决定。

借助这一特性，我们可以通过强制转换指针类型、执行指针运算并对结果解引用，精准获取隐藏在内存块最前端的头部信息（Header），以及其中存储的元数据。

我们可以先从一个 int 类型的侵入式动态数组入手，实现逻辑其实非常简洁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int *arr_init(int *ptr, int size){
    if (ptr == NULL)
    {
        Header *header = malloc(sizeof(*ptr) * size + sizeof(Header));
        header->capacity = size;
        header->count = 0;
        ptr = (int *)(header + 1);
    }
    return ptr;
}
void arr_push(int **arr_ptr, int data){
    int *arr = *arr_ptr;
    Header *header = ((Header *)arr - 1);
    if (header->count >= header->capacity)
    {
        header->capacity *= 2;
        header = realloc(header, sizeof(*arr) * header->capacity +
                                     sizeof(Header));
        arr = (int *)(header + 1);
        *arr_ptr = arr;
    }
    arr[header->count++] = data;
}
void arr_free(int *arr){
    free((Header *)(arr)-1);
}

其实只要理解了前面提到的指针运算特性—— 对指针进行加减操作时，偏移量由指针指向类型的大小决定，这段代码就很好理解、也很好写了。

这里有一个细节需要重点注意：结合 realloc 的核心特性可知，当原内存地址后无足够连续空间时，realloc() 会将内存块整体迁移至新的内存位置。

若迁移成功，函数会返回新的内存地址，原指针将失效，必须用新地址覆盖旧指针，否则会引发野指针、内存访问异常等问题。

正是由于这一特性，我们在 arr_push 函数的参数列表中特意使用二级指针，核心目的就是：当 realloc 触发内存迁移时，能够直接修改并更新原数组指针的地址，保证指针始终有效。

但这种实现方式只能处理 int 类型的动态数组，如果想支持其他数据类型，就必须为每一种类型单独编写一套操作函数。

这时我们就可以用上 C 语言的宏，借助它来实现泛型动态数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define arr_push(arr, x)                                                   \
    do {                                                                   \
        if (arr == NULL) {                                                 \
            Header *header =                                               \
                malloc(sizeof(*arr) * ARR_INIT_CAPACITY + sizeof(Header)); \
            header->count = 0;                                             \
            header->capacity = ARR_INIT_CAPACITY;                          \
            arr = (void *)(header + 1);                                    \
        }                                                                  \
        Header *header = (Header *)(arr) - 1;                              \
        if (header->count >= header->capacity) {                           \
            header->capacity *= 2;                                         \
            header = realloc(header, sizeof(*arr) * header->capacity +     \
                                         sizeof(Header));                  \
            arr = (void *)(header + 1);                                    \
        }                                                                  \
        (arr)[header->count++] = (x);                                      \
    } while (0)

可以看到，使用宏时，参数类型从二级指针简化成了一级指针。这是因为 C 语言的宏本质比较原始，仅仅是做单纯的文本替换。

这段宏会在调用处直接展开，并且 arr 会在宏内部完成更新。而不需要考虑局部变量的问题

当然，这段宏不太健壮，仍然可能出现野指针之类的问题，但只是作为一个demo来说，倒也够用

发表于 更新于

时隔不知道多久的颓废之后，正在尝试恢复人类形态（并非

在面向对象编程中，设计模式是解决常见问题的经典方案。然而，在C语言这种非面向对象的语言中实现设计模式需要一些技巧。本文将探讨如何在C语言中实现简单工厂模式，这是一种创建型设计模式，用于封装对象的创建过程。

项目结构

首先，让我们看一下这个简单示例的目录结构：

1
2
3
4
5
6
7
8
├── include/
│   ├── shape.h
│   ├── circle.h
│   └── rectangle.h
├── src/
│   ├── shape.c
│   ├── circle.c
│   └── rectangle.c

挑战与思路

拿C语言写设计模式真是一整个牢住了，没有继承，没有多态，什么都没有。突然有点想念强面向对象语言。

用C语言实现设计模式确实有一定挑战，因为C语言本身不支持继承、多态等面向对象特性。但通过一些技巧，我们仍然可以模拟出类似的效果。

在这个简单工厂模式的实现中，我们使用了一些模拟面向对象编程的技术，包括不透明指针模式。这些技术可以帮助我们在C语言中实现类似面向对象的行为。

顺带一提，在这个简单工厂模式的实现里，有涉及到一些模拟oop跟不透明模式的东西，或许大概可能也许以后会写一下这些东西（逃

Shape句柄的实现

让我们先来看看shape_t这个句柄是如何定义的：

1
2
3
4
5
6
7
8
9
typedef const struct shape_api **shape_t;
struct shape_api {
    void (*draw)(shape_t shape);
    void (*destroy)(shape_t shape);
};

struct shape {
    const struct shape_api *api;
};

shape_t 是一个指向 shape_api 结构体指针的指针。通过这种设计，我们可以使用 (*shape_t)->成员函数 的方式来访问不同形状类实现的成员函数。

工厂函数

在简单工厂模式中，工厂的主要职责是创建对象。我们实现了以下两个工厂函数：

1
2
shape_t shape_create(enum shape_type type);
shape_t shape_create_with_param(const shape_config_t *config);

其中 shape_create 是 shape_create_with_param 的简化版本，使用预定义的默认参数。让我们重点分析 shape_create_with_param 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
shape_t shape_create_with_param(const shape_config_t *config) {
    if (!config)
        return NULL;
    switch (config->type) {
        case SHAPE_CIRCLE: {
            struct shape_circle *circle =
                (struct shape_circle *)malloc(sizeof(struct shape_circle));
            if (!circle)
                return NULL;
            shape_circle_init_with_radius(circle, config->params.circle.radius);
            return &circle->shape.api;
        }
        case SHAPE_RECTANGLE: {
            struct shape_rectangle *rectangle =
                (struct shape_rectangle *)malloc(
                    sizeof(struct shape_rectangle));
            if (!rectangle)
                return NULL;
            shape_rectangle_init_with_size(rectangle,
                                           config->params.rectangle.width,
                                           config->params.rectangle.height);
            return &rectangle->shape.api;
        }
        default:
            return NULL;
    }
}

这里没有什么错误处理，毕竟它只是一个简易的demo而已。

这个函数的主要逻辑是：

  1. 检查配置参数是否有效
  2. 根据配置中的类型创建相应的对象
  3. 调用对应类的初始化函数
  4. 返回对象的句柄

由于我没有实现自己的内存分配函数，所以我们这里就使用 malloc()。

配置结构体

工厂函数需要一个配置结构体来指定要创建的对象类型和参数：

1
2
3
4
5
6
7
8
9
10
11
typedef struct shape_config {
    enum shape_type type;
    union {
        struct {
            float radius;
        } circle;
        struct {
            float width, height;
        } rectangle;
    } params;
} shape_config_t;

shape_config_t 结构体使用联合体（union）来存储不同类型形状的参数。这种设计使得我们可以用一个结构体来表示所有可能形状的配置。

基本上来说，shape_config_t基本上就只是一个单纯的结构体，包含了需要构建对象的类别跟所需要的参数

设计考虑

需要注意的是，当前的实现存在一个设计上的局限性：每次添加新的形状类型时，都需要修改 shape_config_t 结构体和 shape_create_with_param 函数。这违反了开闭原则（对扩展开放，对修改封闭）。

当然，这个配置结构体跟刚才提到的create函数都是不符合开闭原则的。每添加一个类都需要对他俩进行修改，这很不优雅。

在实际项目中，可以考虑更灵活的解决方案，比如使用注册机制或配置表来避免直接修改核心代码。不过，对于这个简单的演示来说，当前的实现已经足够清晰。

在拷打了一会AI之后，AI给了我一种新的解决方案，待我有空了去研究研究。

初始化函数

回归正题，我们发现这个工厂要求被它管理的类需要有”shape_rectangle_init_with_size”这样一个暴露出来的初始化函数

工厂要求每个被管理的类都提供一个公开的初始化函数。以矩形为例：

1
2
3
4
5
6
void shape_rectangle_init_with_size(struct shape_rectangle *self, float width,float height) {
    memset(self, 0, sizeof(*self));
    self->shape.api = &_rectangle_api;
    self->width = width;
    self->height = height;
}

随便掏一个出来，可以发现它所做的工作也并不复杂，只是很单纯的置0了对象，然后把传进来的参数填进去了而已。

初始化函数主要完成以下工作：

  1. 使用 memset 将对象内存清零
  2. 将虚函数表指针绑定到对象的 api 成员
  3. 设置对象的特定参数（如矩形的宽度和高度）

“self->shape.api = &_rectangle_api;”这一句可以稍微注意一下，这个初始化函数将对应子类的（基类为shape）虚函数表绑定到了self->shape.api，这是我们之后实现运行时多态的必要条件

虚函数表

每个形状类都有自己的虚函数表，定义了该类实现的特定行为：

1
const struct shape_api _rectangle_api = {.draw = _shape_rectangle_draw, .destroy = _shape_rectangle_destroy};

虚函数表大概长这样，我们实现了draw跟destroy函数并且绑定到了这个结构体上

这个虚函数表包含了指向实际实现函数的指针。对于矩形类，我们实现了 _shape_rectangle_draw 和 _shape_rectangle_destroy 函数。

成员函数实现

让我们看看 _shape_rectangle_destroy 函数的实现：

1
2
3
4
5
static void _shape_rectangle_destroy(shape_t shape) {
    struct shape_rectangle *self =
        container_of(shape, struct shape_rectangle, shape.api);
    free(self);
}

这里把destroy掏出来看看，基本上来说它就只是单纯的用container_of宏，通过在rectangle子类中包含的shape*的地址和一些别的信息反推出了rectangle本身的地址，然后执行了free。其实draw也是差不多的，也是反推出来本身地址之后，取出结构体中的内容物进行使用，你甚至可以再次进行一个分层，这没什么问题。

这个函数使用 container_of 宏从 shape_t 句柄反推出完整的矩形对象地址，然后释放内存。draw 函数的实现原理类似，也是通过反推地址来访问对象的特定数据。

container_of 宏是一个常用的C语言技巧，它通过结构体成员的地址计算出整个结构体的地址。

通用接口函数

虽然严格来说，以下两个函数不属于工厂模式的核心部分，但它们提供了统一的接口来操作所有形状对象：

1
2
void shape_draw(shape_t shape);
void shape_destroy(shape_t shape);

虽然强行归类一切没什么意义，C语言甚至都不是面向对象的，更不是强面向对象。但是没法把他俩归类还是让我有点烦。

这些函数提供了类型安全的操作接口，隐藏了具体的实现细节。

shape_draw 函数的实现展示了如何通过虚函数表调用具体的实现：

1
2
3
4
5
void shape_draw(shape_t shape) {
    if (shape && *shape && (*shape)->draw) {
        (*shape)->draw(shape);
    }
}

他俩其实也挺简单的，就是进行一个简单的判空之后，解引用出*shape_api，然后再通过结构体首个成员的地址是整个结构体的地址这个机制套娃两次就可以对子类绑定好的成员函数进行一个调用了。

这个函数首先进行空指针检查，然后通过双重解引用访问虚函数表中的 draw 函数指针，最后调用具体的实现。这种设计允许我们在不知道具体类型的情况下调用正确的方法。

示例代码

下面是一个完整的使用示例，展示了如何创建和使用不同形状：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
int main(int argc, char **argv) {
    printf("=== Simple Factory Pattern Demo ===\n\n");

    // 测试1: 使用默认参数创建形状
    printf("Test 1: Creating shapes with default parameters\n");

    shape_t circle1 = shape_create(SHAPE_CIRCLE);
    if (circle1) {
        printf("Created default circle\n");
        shape_draw(circle1);
        shape_destroy(circle1);
    }

    shape_t rectangle1 = shape_create(SHAPE_RECTANGLE);
    if (rectangle1) {
        printf("Created default rectangle\n");
        shape_draw(rectangle1);
        shape_destroy(rectangle1);
    }

    printf("\n");

    // 测试2: 使用带参数的工厂函数创建自定义形状
    printf("Test 2: Creating shapes with custom parameters\n");

    shape_config_t circle_config = {.type = SHAPE_CIRCLE,
                                    .params.circle.radius = 2.5f};

    shape_t circle2 = shape_create_with_param(&circle_config);
    if (circle2) {
        printf("Created custom circle with radius 2.5\n");
        shape_draw(circle2);
        shape_destroy(circle2);
    }

    shape_config_t rectangle_config = {.type = SHAPE_RECTANGLE,
                                       .params.rectangle.width = 3.0f,
                                       .params.rectangle.height = 4.0f};

    shape_t rectangle2 = shape_create_with_param(&rectangle_config);
    if (rectangle2) {
        printf("Created custom rectangle with width 3.0 and height 4.0\n");
        shape_draw(rectangle2);
        shape_destroy(rectangle2);
    }

    printf("\n");

    // 测试3: 错误处理 - 无效类型
    printf("Test 3: Error handling - invalid shape type\n");
    shape_t unknown_shape = shape_create(999); // 无效类型
    if (!unknown_shape) {
        printf("Correctly rejected unknown shape type\n");
    }

    printf("\n=== Demo Completed ===\n");

    return 0;
}

当然，最后在这里赋上一个main.c

总结

通过这个简单的示例，我们可以看到如何在C语言中实现简单工厂模式。虽然C语言本身不支持面向对象特性，但通过一些技巧，我们仍然可以模拟出类似的效果：

  1. 不透明指针：使用 shape_t 作为不透明句柄，隐藏实现细节
  2. 虚函数表：通过结构体指针模拟虚函数表，实现运行时多态
  3. 工厂函数：封装对象的创建过程，提供统一的创建接口
  4. 配置结构体：使用联合体存储不同类型对象的参数

感觉这种设计模式，复杂的已经不是单个成员函数了，复杂的是这些函数之间的关系了感觉。

这种设计模式的复杂性主要来自于函数之间的关系和交互，而不是单个函数的实现。通过合理的抽象和封装，我们可以在C语言中构建出灵活、可扩展的系统。

在实际项目中，可以根据需要进一步优化这个实现，比如添加更完善的错误处理、支持动态注册新类型、或者实现更复杂的设计模式。

发表于 更新于 分类于

在C语言中，原生并没有像C++或JavaScript那样内置的**箭头函数（lambda）**支持。但是，我们可以通过一些技巧和模式来模拟实现类似的功能。

下面介绍两种常见的实现方式：

1. 使用宏和typeof关键字

这种方法是利用C语言的宏预处理器和GCC/Clang编译器特有的typeof扩展。这种方式的优点是代码简洁，看起来最接近真正的lambda表达式，但缺点是它依赖于特定的编译器，可移植性较差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>

// 定义一个宏，用于创建类似lambda的函数
// 参数：
// type: 函数的返回类型
// args: 函数的参数列表，用括号括起来
// body: 函数体
#define LAMBDA(type, args, body) \
({ \
    type __fn__ args body \
    __fn__; \
})

int main() {
    // 定义一个lambda，求两个数的和
    int (*sum_lambda)(int, int) = LAMBDA(int, (int a, int b), {
        return a + b;
    });

    printf("Sum: %d\n", sum_lambda(5, 3)); // 输出 Sum: 8

    // 定义一个lambda，判断一个数是否为偶数
    int (*is_even_lambda)(int) = LAMBDA(int, (int num), {
        return num % 2 == 0;
    });

    printf("Is 10 even? %d\n", is_even_lambda(10)); // 输出 Is 10 even? 1
    printf("Is 7 even? %d\n", is_even_lambda(7));   // 输出 Is 7 even? 0

    return 0;
}

工作原理：

  • LAMBDA宏创建了一个匿名函数，并立即返回这个函数的地址。
  • ({}) 这种语法是GCC的**语句表达式（Statement Expressions）**扩展，它允许在一个表达式中使用代码块。代码块的最后一条语句的值就是整个表达式的值。
  • typeof在这里没有直接使用，但这个模式的核心是利用了GCC/Clang对局部函数（nested functions）的支持，并在宏中返回了其地址。上述代码中的typeof是隐藏在宏的实现细节中，用来自动推断函数指针类型的。

2. 使用结构体和函数指针

这是一种更通用、更具可移植性的方法，可以在任何遵循C标准的编译器上使用。它的核心思想是将函数指针和捕获的变量（被lambda引用的外部变量）封装在一个结构体中。

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>

// 定义一个结构体，用于表示lambda
typedef struct {
    void *context; // 用于存储捕获的变量
    int (*function)(void *context, int arg); // 函数指针
} Lambda;

// 实际执行的函数，它接收一个上下文和一个参数
int adder_function(void *context, int arg) {
    int *base = (int *)context;
    return (*base) + arg;
}

// 创建一个lambda
Lambda create_adder(int base) {
    // 分配内存来存储捕获的变量
    int *context = (int *)malloc(sizeof(int));
    *context = base;

    Lambda l = {
        .context = context,
        .function = adder_function
    };
    return l;
}

int main() {
    // 创建一个lambda，它会捕获外部变量 'x'
    int x = 10;
    Lambda add_x = create_adder(x);

    // 调用lambda
    int result = add_x.function(add_x.context, 5); // 10 + 5
    printf("Result: %d\n", result); // 输出 Result: 15

    // 释放捕获变量的内存
    free(add_x.context);

    return 0;
}

工作原理：

  • 我们定义了一个Lambda结构体，它包含两个成员：
    • context：一个**void*指针**，用于存储lambda需要访问的外部变量（即“捕获的变量”）。
    • function：一个函数指针，它接收context指针和实际的参数。
  • 当我们创建一个lambda时，我们会分配内存来存储外部变量，并将其地址赋给context。
  • 在调用时，我们将Lambda结构体的context和实际参数一起传递给function指针指向的函数。
  • 这种方式更复杂，但非常灵活，并且是C语言中实现闭包（closure）的经典模式。它也是很多库（例如：libdispatch）在C语言中实现异步回调和闭包的基础。

发表于

事件集

事件集也是线程间同步的机制之一，一个事件集可以包含多个事件，利用事件集可以完成一对多，多对多的线程间同步。下面以坐公交为例说明事件，在公交站等公交时可能有以下几种情况：

①P1 坐公交去某地，只有一种公交可以到达目的地，等到此公交即可出发。

②P1 坐公交去某地，有 3 种公交都可以到达目的地，等到其中任意一辆即可出发。

③P1 约另一人 P2 一起去某地，则 P1 必须要等到 “同伴 P2 到达公交站” 与“公交到达公交站”两个条件都满足后，才能出发。

这里，可以将 P1 去某地视为线程，将 “公交到达公交站”、“同伴 P2 到达公交站” 视为事件的发生，情况①是特定事件唤醒线程；情况②是任意单个事件唤醒线程；情况③是多个事件同时发生才唤醒线程。

事件集工作机制

事件集主要用于线程间的同步，与信号量不同，它的特点是可以实现一对多，多对多的同步。即一个线程与多个事件的关系可设置为：其中任意一个事件唤醒线程，或几个事件都到达后才唤醒线程进行后续的处理；同样，事件也可以是多个线程同步多个事件。这种多个事件的集合可以用一个 32 位无符号整型变量来表示，变量的每一位代表一个事件，线程通过 “逻辑与” 或“逻辑或”将一个或多个事件关联起来，形成事件组合。事件的 “逻辑或” 也称为是独立型同步，指的是线程与任何事件之一发生同步；事件 “逻辑与” 也称为是关联型同步，指的是线程与若干事件都发生同步。

RT-Thread 定义的事件集有以下特点：

1）事件只与线程相关，事件间相互独立：每个线程可拥有 32 个事件标志，采用一个 32 bit 无符号整型数进行记录，每一个 bit 代表一个事件；

2）事件仅用于同步，不提供数据传输功能；

3）事件无排队性，即多次向线程发送同一事件 (如果线程还未来得及读走)，其效果等同于只发送一次。

在 RT-Thread 中，每个线程都拥有一个事件信息标记，它有三个属性，分别是 RT_EVENT_FLAG_AND(逻辑与)，RT_EVENT_FLAG_OR(逻辑或）以及 RT_EVENT_FLAG_CLEAR(清除标记）。当线程等待事件同步时，可以通过 32 个事件标志和这个事件信息标记来判断当前接收的事件是否满足同步条件。

事件集工作示意图

如上图所示，线程 #1 的事件标志中第 1 位和第 30 位被置位，如果事件信息标记位设为逻辑与，则表示线程 #1 只有在事件 1 和事件 30 都发生以后才会被触发唤醒，如果事件信息标记位设为逻辑或，则事件 1 或事件 30 中的任意一个发生都会触发唤醒线程 #1。如果信息标记同时设置了清除标记位，则当线程 #1 唤醒后将主动把事件 1 和事件 30 清为零，否则事件标志将依然存在（即置 1）。

事件集控制块

在 RT-Thread 中，事件集控制块是操作系统用于管理事件的一个数据结构，由结构体 struct rt_event 表示。另外一种 C 表达方式 rt_event_t，表示的是事件集的句柄，在 C 语言中的实现是事件集控制块的指针。事件集控制块结构的详细定义请见以下代码：

1
2
3
4
5
6
7
8
9
struct rt_event
{
    struct rt_ipc_object parent;    /* 继承自 ipc_object 类 */

    /* 事件集合，每一 bit 表示 1 个事件，bit 位的值可以标记某事件是否发生 */
    rt_uint32_t set;
};
/* rt_event_t 是指向事件结构体的指针类型  */
typedef struct rt_event* rt_event_t;

rt_event 对象从 rt_ipc_object 中派生，由 IPC 容器所管理。

事件集的管理方式

事件集控制块中含有与事件集相关的重要参数，在事件集功能的实现中起重要的作用。事件集相关接口如下图所示，对一个事件集的操作包含：创建 / 初始化事件集、发送事件、接收事件、删除 / 脱离事件集。

事件相关接口

创建和删除事件集

当创建一个事件集时，内核首先创建一个事件集控制块，然后对该事件集控制块进行基本的初始化，创建事件集使用下面的函数接口：

1
rt_event_t rt_event_create(const char* name, rt_uint8_t flag);

调用该函数接口时，系统会从对象管理器中分配事件集对象，并初始化这个对象，然后初始化父类 IPC 对象。下表描述了该函数的输入参数与返回值：

参数 描述
name 事件集的名称
flag 事件集的标志，它可以取如下数值： RT_IPC_FLAG_FIFO 或 RT_IPC_FLAG_PRIO
返回 ——
RT_NULL 创建失败
事件对象的句柄 创建成功

Note

注：RT_IPC_FLAG_FIFO 属于非实时调度方式，除非应用程序非常在意先来后到，并且你清楚地明白所有涉及到该事件集的线程都将会变为非实时线程，方可使用 RT_IPC_FLAG_FIFO，否则建议采用 RT_IPC_FLAG_PRIO，即确保线程的实时性。

系统不再使用 rt_event_create() 创建的事件集对象时，通过删除事件集对象控制块来释放系统资源。删除事件集可以使用下面的函数接口：

1
rt_err_t rt_event_delete(rt_event_t event);

在调用 rt_event_delete 函数删除一个事件集对象时，应该确保该事件集不再被使用。在删除前会唤醒所有挂起在该事件集上的线程（线程的返回值是 - RT_ERROR），然后释放事件集对象占用的内存块。下表描述了该函数的输入参数与返回值：

参数 描述
event 事件集对象的句柄
返回 ——
RT_EOK 成功

初始化和脱离事件集

静态事件集对象的内存是在系统编译时由编译器分配的，一般放于读写数据段或未初始化数据段中。在使用静态事件集对象前，需要先行对它进行初始化操作。初始化事件集使用下面的函数接口：

1
rt_err_t rt_event_init(rt_event_t event, const char* name, rt_uint8_t flag);

调用该接口时，需指定静态事件集对象的句柄（即指向事件集控制块的指针），然后系统会初始化事件集对象，并加入到系统对象容器中进行管理。下表描述了该函数的输入参数与返回值：

参数 描述
event 事件集对象的句柄
name 事件集的名称
flag 事件集的标志，它可以取如下数值： RT_IPC_FLAG_FIFO 或 RT_IPC_FLAG_PRIO
返回 ——
RT_EOK 成功

系统不再使用 rt_event_init() 初始化的事件集对象时，通过脱离事件集对象控制块来释放系统资源。脱离事件集是将事件集对象从内核对象管理器中脱离。脱离事件集使用下面的函数接口：

1
rt_err_t rt_event_detach(rt_event_t event);

用户调用这个函数时，系统首先唤醒所有挂在该事件集等待队列上的线程（线程的返回值是 - RT_ERROR），然后将该事件集从内核对象管理器中脱离。下表描述了该函数的输入参数与返回值：

参数 描述
event 事件集对象的句柄
返回 ——
RT_EOK 成功

发送事件

发送事件函数可以发送事件集中的一个或多个事件，如下：

1
rt_err_t rt_event_send(rt_event_t event, rt_uint32_t set);

使用该函数接口时，通过参数 set 指定的事件标志来设定 event 事件集对象的事件标志值，然后遍历等待在 event 事件集对象上的等待线程链表，判断是否有线程的事件激活要求与当前 event 对象事件标志值匹配，如果有，则唤醒该线程。下表描述了该函数的输入参数与返回值：

参数 描述
event 事件集对象的句柄
set 发送的一个或多个事件的标志值
返回 ——
RT_EOK 成功

接收事件

内核使用 32 位的无符号整数来标识事件集，它的每一位代表一个事件，因此一个事件集对象可同时等待接收 32 个事件，内核可以通过指定选择参数 “逻辑与” 或“逻辑或”来选择如何激活线程，使用 “逻辑与” 参数表示只有当所有等待的事件都发生时才激活线程，而使用 “逻辑或” 参数则表示只要有一个等待的事件发生就激活线程。接收事件使用下面的函数接口：

1
2
3
4
5
rt_err_t rt_event_recv(rt_event_t event,
                           rt_uint32_t set,
                           rt_uint8_t option,
                           rt_int32_t timeout,
                           rt_uint32_t* recved);

当用户调用这个接口时，系统首先根据 set 参数和接收选项 option 来判断它要接收的事件是否发生，如果已经发生，则根据参数 option 上是否设置有 RT_EVENT_FLAG_CLEAR 来决定是否重置事件的相应标志位，然后返回（其中 recved 参数返回接收到的事件）；如果没有发生，则把等待的 set 和 option 参数填入线程本身的结构中，然后把线程挂起在此事件上，直到其等待的事件满足条件或等待时间超过指定的超时时间。如果超时时间设置为零，则表示当线程要接受的事件没有满足其要求时就不等待，而直接返回 - RT_ETIMEOUT。下表描述了该函数的输入参数与返回值：

参数 描述
event 事件集对象的句柄
set 接收线程感兴趣的事件
option 接收选项
timeout 指定超时时间
recved 指向接收到的事件
返回 ——
RT_EOK 成功
-RT_ETIMEOUT 超时
-RT_ERROR 错误

option 的值可取：

1
2
3
4
5
6
/* 选择 逻辑与 或 逻辑或 的方式接收事件 */
RT_EVENT_FLAG_OR
RT_EVENT_FLAG_AND

/* 选择清除重置事件标志位 */
RT_EVENT_FLAG_CLEAR

事件集应用示例

这是事件集的应用例程，例子中初始化了一个事件集，两个线程。一个线程等待自己关心的事件发生，另外一个线程发送事件，如以下代码所示：

事件集的使用例程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <rtthread.h>

#define THREAD_PRIORITY      9
#define THREAD_TIMESLICE     5

#define EVENT_FLAG3 (1 << 3)
#define EVENT_FLAG5 (1 << 5)

/* 事件控制块 */
static struct rt_event event;

ALIGN(RT_ALIGN_SIZE)
static char thread1_stack[1024];
static struct rt_thread thread1;

/* 线程 1 入口函数 */
static void thread1_recv_event(void *param)
{
    rt_uint32_t e;

    /* 第一次接收事件，事件 3 或事件 5 任意一个可以触发线程 1，接收完后清除事件标志 */
    if (rt_event_recv(&event, (EVENT_FLAG3 | EVENT_FLAG5),
                      RT_EVENT_FLAG_OR | RT_EVENT_FLAG_CLEAR,
                      RT_WAITING_FOREVER, &e) == RT_EOK)
    {
        rt_kprintf("thread1: OR recv event 0x%x\n", e);
    }

    rt_kprintf("thread1: delay 1s to prepare the second event\n");
    rt_thread_mdelay(1000);

    /* 第二次接收事件，事件 3 和事件 5 均发生时才可以触发线程 1，接收完后清除事件标志 */
    if (rt_event_recv(&event, (EVENT_FLAG3 | EVENT_FLAG5),
                      RT_EVENT_FLAG_AND | RT_EVENT_FLAG_CLEAR,
                      RT_WAITING_FOREVER, &e) == RT_EOK)
    {
        rt_kprintf("thread1: AND recv event 0x%x\n", e);
    }
    /* 执行完该事件集后进行事件集的脱离，事件集重复初始化会导致再次运行时，出现重复初始化的问题 */
    rt_event_detach(&event);
    rt_kprintf("thread1 leave.\n");
}


ALIGN(RT_ALIGN_SIZE)
static char thread2_stack[1024];
static struct rt_thread thread2;

/* 线程 2 入口 */
static void thread2_send_event(void *param)
{
    rt_kprintf("thread2: send event3\n");
    rt_event_send(&event, EVENT_FLAG3);
    rt_thread_mdelay(200);

    rt_kprintf("thread2: send event5\n");
    rt_event_send(&event, EVENT_FLAG5);
    rt_thread_mdelay(200);

    rt_kprintf("thread2: send event3\n");
    rt_event_send(&event, EVENT_FLAG3);
    rt_kprintf("thread2 leave.\n");
}

int event_sample(void)
{
    rt_err_t result;

    /* 初始化事件对象 */
    result = rt_event_init(&event, "event", RT_IPC_FLAG_PRIO);
    if (result != RT_EOK)
    {
        rt_kprintf("init event failed.\n");
        return -1;
    }

    rt_thread_init(&thread1,
                   "thread1",
                   thread1_recv_event,
                   RT_NULL,
                   &thread1_stack[0],
                   sizeof(thread1_stack),
                   THREAD_PRIORITY - 1, THREAD_TIMESLICE);
    rt_thread_startup(&thread1);

    rt_thread_init(&thread2,
                   "thread2",
                   thread2_send_event,
                   RT_NULL,
                   &thread2_stack[0],
                   sizeof(thread2_stack),
                   THREAD_PRIORITY, THREAD_TIMESLICE);
    rt_thread_startup(&thread2);

    return 0;
}

/* 导出到 msh 命令列表中 */
MSH_CMD_EXPORT(event_sample, event sample);

仿真运行结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 \ | /
- RT -     Thread Operating System
 / | \     4.1.1 build Sep  5 2024 15:53:21
 2006 - 2022 Copyright by RT-Thread team
msh >event_sample
thread2: send event3
thread1: OR recv event 0x8
thread1: delay 1s to prepare the second event
msh >thread2: send event5
thread2: send event3
thread2 leave.
thread1: AND recv event 0x28
thread1 leave.

msh >event_sample
thread2: send event3
thread1: OR recv event 0x8
thread1: delay 1s to prepare the second event
msh >thread2: send event5
thread2: send event3
thread2 leave.
thread1: AND recv event 0x28
thread1 leave.

例程演示了事件集的使用方法。线程 1 前后两次接收事件，分别使用了 “逻辑或” 与“逻辑与”的方法。

事件集的使用场合

事件集可使用于多种场合，它能够在一定程度上替代信号量，用于线程间同步。一个线程或中断服务例程发送一个事件给事件集对象，而后等待的线程被唤醒并对相应的事件进行处理。但是它与信号量不同的是，事件的发送操作在事件未清除前，是不可累计的，而信号量的释放动作是累计的。事件的另一个特性是，接收线程可等待多种事件，即多个事件对应一个线程或多个线程。同时按照线程等待的参数，可选择是 “逻辑或” 触发还是 “逻辑与” 触发。这个特性也是信号量等所不具备的，信号量只能识别单一的释放动作，而不能同时等待多种类型的释放。如下图所示为多事件接收示意图：

多事件接收示意图

一个事件集中包含 32 个事件，特定线程只等待、接收它关注的事件。可以是一个线程等待多个事件的到来（线程 1、2 均等待多个事件，事件间可以使用 “与” 或者 “或” 逻辑触发线程），也可以是多个线程等待一个事件的到来（事件 25）。当有它们关注的事件发生时，线程将被唤醒并进行后续的处理动作。

这写的还是挺像人话的，就是暂时不知道有什么用