作业 3：有趣的堆#

本次作业既用于测试你对话题 3 的理解，也是对话题 2 的进一步探索。在动态内存的基础上，继续深入研究数组和指针，并通过以下几个方面的训练，培养你的技能：

  • 操作指针和数组

  • 管理栈和堆上的内存分配

  • 使用 C 标准库中的 I/O 函数

  • 使用 Valgrind 等工具辅助追踪内存错误和泄漏

为了帮助你评估学习进度，对于每个作业/实验，我们罗列了一些要点，并提供了一些思考问题。在完成作业后，可以使用这些问题进行自我检查。如果你不能很好地回答这些问题，那么还需要进一步努力。

  • 作业 2 中编写的 scan_token 函数要求用户提供内存，用于存储扫描的词元。而作业 3 中的 read_line 函数却为用户分配好了内存。这两种方法有何优缺点？

  • 据说，一个正确的程序，malloc 调用和 free 调用应该是一一对应的。如果添加了 realloc 调用，这将如何改变所需的 malloc 和 free 调用数量？

  • 内存错误和内存泄漏哪个问题更严重，为什么？如何区分 Valgrind 报告了哪种错误？

  • 对于运行时或内存分配的效率，如何衡量你的程序是否具有可接受的性能？

  • 什么时候适合使用 calloc 代替 malloc？

初始项目#

你的个人用户目录下应该已经有 cs102 这个文件夹了，通过下面的命令拷贝初始代码到该目录中：

cp -r /home/cs102-shared/assignments/assign3 ~/cs102

内存分配#

本次作业提供了许多内存管理的针对性训练。编程过程中，你将出于各种目的使用栈和堆，并且需要注意适当地分配和正确地释放。以下是关于内存的一些通用指南以及针对程序的一些建议：

  • 栈分配（stack allocation）就像声明变量一样简单。栈很方便（自动分配/释放）、具备类型安全并且非常高效。

  • 动态分配是通过 malloc/realloc/free 进行的。利用堆内存，程序员能够控制生命周期（显式分配/释放）并提高程序的灵活性（可以调整存储大小/重新调整用途），但会牺牲安全性和效率。

  • 注意理解栈分配与堆分配的正确使用以及两者适用的场景。根据一般的经验，除非必须使用动态分配的情况，首选栈分配。这两种技术通常会在程序中同时出现。在以下情况下，堆分配是必要的：

    • 需要一个非常大的内存分配，可能会耗尽栈空间

    • 需要控制内存的生命周期，或者内存必须在函数调用之外持续存在

    • 需要在初始分配后调整内存大小

始终使用 Valgrind 至关重要。查看 Valgrind 指南并回顾实验 2 和 3 中的练习，确保熟练使用 Valgrind。特别是：

  • 内存错误。这是迄今为止让 Valgrind 辅助我们编程的最重要原因。如果 Valgrind 报告错误，则需要立即处理。

  • 内存泄漏。如果 Valgrind 报告泄漏，则说明有一些堆内存分配后没有释放。内存泄漏通常不会立刻导致程序错误，但错误的释放反而可能会导致错误，因此我们建议在程序完成之前不要担心内存释放的问题。开发完成后，再单独处理内存释放，并确保每一步的正确性。

背景：过滤命令#

uniq 和 tail 是一类特殊的命令，称为“过滤器”。过滤器是这样一种程序，它从用户或文件中读取输入（通常是逐行读入），以某种方式转换输入，并生成一些输出。其他一些过滤器命令还有 cat、sort 和 grep 等。

cat 是所有过滤器中最简单的，直接将输入进行输出。调用 cat filename 将打印指定文件的内容。 文档 man cat 表明，如果没有给出文件名参数，该命令将从标准输入读取。这意味着程序将读取用户在终端上键入的行。几乎每个过滤器（例如 grep wc less head sort 等）都遵循相同的接口，要么从指定的文件读取，要么从标准输入读取。从标准输入读取可以方便地进行快速测试，无需提前创建文件。

自己尝试一下：

  • 调用 cat Makefile 来查看文件的内容。

  • 使用 -b 参数可以对非空白行进行编号：cat -b Makefile。

  • 现在调用不带文件名参数的 cat -b，此时程序将等待你键入输入。

  • 输入一行文本并按 Enter 键，观察该行及其行号的对应关系。再输入几行，也会进行输出并编号。

  • 完成输入后，在单独的一行上按 Control-d，这表示输入结束（EOF 表示“文件结束”），过滤程序将退出。

下面是一些其他可供探索的过滤器。对于每个命令，请浏览 man 文档以了解其选项。在现有文件上运行过滤器，然后在没有文件名的情况下再次运行过滤器并通过标准输入进行操作。请记住，Control-d 用于发出 EOF 信号。

  • head 打印输入的前几行

  • tail 打印输入的后几行

  • wc 打印输入中的行数、单词数和字符数

  • grep 从输入中打印与搜索模式匹配的行

  • uniq 从输入中过滤掉相邻的重复行

  • sort 按顺序重新排列输入并打印

在标准输入上运行时，你会注意到某些过滤器会立即响应输入的每一行，例如如果与模式匹配，grep 会立刻回显该行。其他的命令，例如 sort，在你发出 EOF 信号之前不会输出任何内容。这取决于过滤器操作是否需要查看所有输入才能确定输出内容。

过滤器的真正威力在于它们可以组合成“管道”。管道是一系列命令，其中一个命令的输出被传递到（或“通过管道传输到”）下一个命令的输入。管道字符 | 将一个命令的输出作为下一个命令的输入。过滤器在管道中特别有用，因为它们可以在开始、中间或末尾使用。

管道允许你通过组合基本的过滤器，构建出更强大的操作。以下是一些例子：

  • grep include util.c | wc -l 在 util.c 中查找包含“include”的行，并将它们提供给 wc，wc 输出其接收到的输入中的行数。因此，该管道将输出匹配的行数。

  • cat -b util.c | tail 输出 util.c 中标有行号的行，并将它们提供给 tail，后者仅输出最后 10 行和行号。

  • 标准 uniq 命令仅过滤掉输入中相邻的重复行，而你的版本将过滤掉输入中任何位置出现的重复行。因此，使用标准 uniq 命令时，如果你的数据中有分散的重复行，则需要先重新排序，以便让重复项保持相邻位置，然后 uniq 才会检测到它们。我们可以使用三阶管道来输出文件中不同行的计数：sort samples/names | uniq | wc -l。首先，sort 将 samples/names 排序并输出给 uniq，uniq 忽略相邻的重复项输出到 wc，最后 wc 统计接收到的输入的行数并打印。

  • 现在轮到你了！如何编写一个管道来打印 samples/names 中三个最常见的名称？

Unix/Linux 的哲学是放弃构建单一的万能程序，而是鼓励创建更小的命令。每个命令都只负责某个单一任务，并足够精简。这些小的、离散的工具，通过管道进行组合，从而完成更大的任务。在本次作业中，你将编写其中的两个工具：uniq 和 tail。

任务 1：阅读和注释#

程序 mycat、mytail 和 myuniq 依赖于文件读取操作。文件读取的工作原理大都类似，但在不同语言中具有不同的语法。你的第一个任务是研究作业初始代码以及 C 标准库指南，大致了解 C 语言文件读取的工作原理。我们为你提供了完整的测试程序 mycat.c。而 myuniq.c 和 mytail.c 的起始文件包含处理命令行参数和文件设置的代码，其余部分将由你来实现。你应该先阅读并理解给定的代码，弄清楚如何更改并扩展它以满足你的需求，最后记得添加注释来记录你的实现策略。

查看初始代码时，有一些需要考虑的问题：

  • fopen 的 mode 参数有哪些可能的选项？如果你尝试打开一个不存在的或没有权限的文件，会发生什么情况？

  • 未能正确关闭文件的后果是什么？

  • 当没有文件名参数时，程序如何切换到标准输入进行读取？

  • 从文件读取的操作是否也可以用于从标准输入读取，还是说这两种操作需要不同的代码？

  • 程序 mycat 的默认行为对应于调用标准 cat 时，使用哪个命令行标志？

  • mytail 支持命令行参数 -number 来控制打印的行数。初始代码如何处理该可选参数？

  • mytail -number 的参数范围是什么？

与往常一样，我们提供的代码已删除了注释，你的工作就是为 mytail.c、myuniq.c 和 util.c 文件编写缺失的文档。可以不用注释 mycat.c 文件。

任务 1：实现 read_line#

标准库函数 fgets 用于从文件中读取文本。

char* fgets(char* buf, int bufsize, FILE* stream);

与大多数库函数一样，fgets 不进行任何分配，而是由用户提供缓冲区用于写入。用户必须根据预期的大小预先分配“足够大的”内存来存储该行。如果用户提供的内存太小，则函数可能会发生缓冲区溢出（如果使用 gets）或截断读取操作（如果使用 fgets）。

一个对用户更友好的设计是由读取函数在内部处理内存分配并创建适当大小的行。你将实现一个以这种方式运行的 read_line 函数：

char* read_line(FILE* fp);

函数 read_line 从文件中读取下一行。返回值是一个动态分配的且以空字符结尾的字符串（如果读到 EOF，即“文件结尾”，则返回 NULL）。此函数的执行方式是类似于 fgets 的更时尚的版本（事实上，你应该使用 fgets 来实现它！），因为它不仅可以读取下一行，还可以为字符串分配内存，这将使用户的工作变得更轻松。

以下是该函数操作的一些具体细节：

  • 该函数应该从文件中读取下一行。所谓“一行”，就是遇到第一个换行符或 EOF（以先到者为准），然后结束读取。

  • 返回的字符串应该包含换行符前的所有字符，但不应包括换行符本身。如果下一行仅包含换行符，则返回空字符串。

  • 如果 read_line 到达 EOF，意味着没有更多字符可以读取，则该函数应返回 NULL。请注意，需要先调用 fgets，然后才能检查 EOF 条件，因为尝试读取超出文件末尾的过程会触发 EOF 条件。这种情况应该清理所有预先分配的不再需要的内存，并返回 NULL。

  • 如果调用 fgets 时发生错误，该函数应该返回该时刻已读取的所有内容，如果没有读取任何内容，则返回 NULL（提示：即便你没有考虑到这种情况，你的函数最终可能仍然能够按此逻辑执行）。在这种情况下，你可以假设如果在调用 fgets 期间发生错误，则该时刻不会读取任何字符。

  • 要为返回的字符串分配内存，该函数应该先进行初始分配，并在需要时对其扩容。更具体地说，函数应该首先 malloc 一个最小的缓冲区（32 字节），第一次调用 fgets 时，先将行的前一部分读入缓冲区。如果还有更多内容需要读取，函数应该重新分配缓冲区，并将当前大小翻倍（64 字节），并再次调用 fgets 读取该行的剩余部分。重复这样的过程，翻倍扩容并写入内容，直到最终到达该行的换行符或 EOF，此时表明一行读取完毕。

  • 如果无法分配足够的内存，read_line 应该触发致命断言。养成一种好习惯，你应该为每次分配请求的结果添加断言 assert。分配失败的情况虽然很少见，但却是致命的。

  • read_line 应该返回动态分配的内存块的地址，该位置存储下一行的内容。不再需要时，用户负责释放该内存。

  • 你应该只需要使用 fgets 文件 I/O 函数，不需要使用任何其他函数，例如 feof、fgetc 等。

在 util.c 文件中编写 read_line 的实现。你可以使用我们提供的 mycat.c 程序对其进行测试。 mycat 程序与 sanitycheck 集成。稍后你将使用 read_line 函数继续编写 mytail 和 myuniq 程序。

注意：你可以假设正在读取的不是二进制可执行文件。可执行文件可能包含“空字节”，或全零字节。在处理字符串时，这些可能被当作空字符 NUL 来处理，从而让实现更棘手，所以你不必担心这一点。

任务 2：实现 mytail#

注意 如何对管道中运行的程序使用 gdb/valgrind？

GDB 和 Valgrind 不能很好地与管道配合使用。一种简单的替代方法是，为待测试的输入编写一个文件，然后在该文件上运行 gdb/valgrind 程序。提供输入时，你可以使用重定向 > 来捕获命令的输出。

标准 tail 命令是一个过滤器命令，读取输入，并按顺序打印输入的最后 N 行。 N 的值默认为 10，但也可以设置为命令行标志，例如 tail -4。以下是 tail 的使用示例：

$ cat samples/colors
red
green
green
yellow
blue
blue
blue
blue
$ tail -3 samples/colors 
blue
blue
blue

如果输入包含的总行数少于 N，则打印输入中的所有行。

你要编写的 mytail 程序在操作上与标准 tail 类似，但存在以下差异：

  • mytail 仅支持一个命令行标志 -N，其中 N 是要输出的行数（标准 tail 有许多其他标志）

  • mytail 只读取一个文件：指定文件（如果指定）或标准输入（如果没有）（标准 tail 可以从任意数量的文件参数读取）

当 mytail 处理其输入时，它需要跟踪 N 个行。为此，你必须使用包含 N 个条目的数组。在任何时候，该数组都保存最近读取的 N 行。该数组是一个由 N 行组成的“滑动窗口”（slide window），它在输入过程中移动。当 mytail 到达输入末尾时，该窗口仅包含最后 N 行。

当 mytail 开始处理输入时，它将使用 read_line 函数将前 N 行读入数组。读取第 N+1 行时，不应扩大数组，而应丢弃输入的第一行（最初的行）并将该数组位置用于存储第 N+1 行。 N+2 行覆盖最初的第二行，依此类推。这样，数组就相当于一种循环队列，在任何时候最多存储最近读取的 N 行。

由于数组大小是预先已知的并且在其生命周期内不会改变，因此该数组是使用栈分配的好机会。实现该程序的挑战是理解循环队列的逻辑以及要小心分配和释放字符串。

重要提示：确保理解 Slide Window 方法，并按该方法实现你的 mytail 程序！有些地方也将该数组称作“环形缓冲区”。

任务 3：实现 myuniq#

标准 uniq 是一个过滤器，处理提供的输入，删除相邻的重复行，然后输出。当使用 -c 标志调用 uniq 时，它会计算每行出现的次数。以下是 uniq -c 的使用示例：

$ cat samples/colors
red
green
green
yellow
blue
blue
blue
blue
$ uniq -c samples/colors 
    1 red
    2 green
    1 yellow
    4 blue

你要编写的 myuniq 程序在操作上与标准 uniq 类似，但有一些差异：

  • myuniq 过滤掉所有重复行，无论它们出现在输入中的何处（标准 uniq 仅检测输入中彼此相邻的重复行）

  • 每个重复行仅打印一次，打印顺序与输入中出现的顺序相同。

  • myuniq 总是在输出的每一行前面加上前缀，表示该行在输入中出现次数的（这是使用 -c 标志调用标准 uniq 的行为）

  • myuniq 不支持任何命令行标志（标准 uniq 有许多标志）

为了检测输入中任意位置的重复行，myuniq 必须跟踪输入过程中看到的所有行。它还需要计算每行重复的次数。定义一个结构体数组，可以存储这些信息，帮助我们完成这项工作，但我们仍有一个难题。这个数组需要多少个条目？与 mytail 提前确定数组的分配大小不同，myuniq 的数组大小是不确定的。它可能需要一个包含 10 个条目的数组，或 10,0000 个条目的数组。如果尝试选择一个固定值，对于某些输入来说可能太大，而对于另一些输入来说则太小。听起来，似乎按需分配才是最合理的！

我们对 myuniq 要求是，先为数组分配 100 个条目作为初始大小，如果该数组填满时，调整数组大小用于添加另外 100 个条目。然后根据需要重复此操作，每次添加额外的 100 个条目。（注意这里的策略不是翻倍）

为了匹配示例程序的输出格式，在打印行的计数时，你应该使用 printf 标记 %7d 而不仅仅是 %d。这将打印宽度为 7 的数字，输出将类似于：

      1 red
   5000 blue
  12413 green
1253473 yellow

myuniq 程序中的大部分挑战都与能否正确处理内存有关。当完成本次作业时，你将成为堆内存管理大师！

测试与提交#

本次作业也会查看你的程序的内存和运行时效率。对于内存效率，Valgrind 可以提供巨大的帮助，因为 Valgrind 报告包含有关总堆使用情况的统计信息。在 Valgrind 报告末尾查找以下格式的行：

total heap usage: 10 allocs, 10 frees, 888 bytes allocated

这是程序生命周期内所有堆分配的总和。分配计数应始终等于释放计数。分配计数和分配的总大小是程序内存“占用空间”的衡量标准。

运行时效率（程序运行的速度）也很重要。在命令前面加上执行时间并报告完成该命令所用的时间。例如， time ./mytail 将测量程序的运行时间，而 time samples/mytail_soln 将测量示例程序的运行时间。标记为“用户”的时间是我们感兴趣的部分。

$ time ./mytail -1 samples/dictionary
zygote

real    0m0.010s
user    0m0.006s
sys     0m0.000s

$ time samples/mytail_soln -1 samples/dictionary
zygote

real    0m0.009s
user    0m0.007s
sys     0m0.000s

那么如何确保分配适当的内存，以及合理的运行时效率呢？最佳策略是使用给定输入测量示例程序，并用相同输入测量你的程序。如果你的程序和示例程序的结果大致相同（例如在 2 或 3 倍之内），那么你的实现就没什么大问题。当考虑空间与时间的权衡时，示例程序向你展示了我们正在寻找的平衡点。如果你的程序使用明显更多的内存或时间，则表明你的程序有一些不必要或多余的工作应该消除。请务必注意，非常小的输入对于有意义的测量来说太小；相反，你应该测量较大的输入，以查看程序的大规模运行情况。

作为作业的一部分，你应该尽可能完善 custom_tests 中的测试案例，至少添加 3 到 5 个。为了更好的可读性，也建议你为代码和测试用例编写注释或文档。这些注释用于说明每个测试的初衷，以及这些测试之间的相互关系。

遵循实验 3 中介绍的调试策略，一个关键原则是不要随意更改代码：

  • 观察漏洞行为。

  • 创建一个可复现输入。

  • 缩小检查范围。

  • 分析。

  • 设计实验并验证。

  • 修改代码消除错误。

作业提交方式参考作业 0，可以使用 submit 提交你的代码。为了追求完美，一些加分项值得你去注意：

  • 编译是否干净，有无警告等编译错误？

  • 默认测试是否全部通过？

  • 自定义测试案例是否全面？

对于代码实现部分：

  • 有没有其他地方，还可以使用位运算进行改写？

  • 算法是否高效？还记得如何分析算法复杂度吗？

  • 代码风格及可读性是否注意过？有没有进行函数拆分，提取出一些更通用的代码？

  • 有没有尝试编写文档？一份好的代码就如同一篇优美的散文，不多一字，也不少一字。加油！