本文将介绍操作系统导论（Operating Systems: Three Easy Pieces）作者所开源的操作系统相关课程项目 的 Unix Utilities 部分，包含个人的代码实现和设计思路。
wcat
思路
要实现一个 wcat 命令，打印从文件中读取到的所有字符。
编写一个 for 循环遍历所有的参数（需要读取的文件的路径），打开该文件，依照 README 中的提示使用 fgets() 每次读取一行，并将读取到的字符串打印到标准输出即可。
代码
#include <stdio.h>
#include <stdlib.h>
#define BUF_SIZE 1024
int main(int argc, char* argv[]) {
char buffer[BUF_SIZE];
for (int i = 1; i < argc; ++i) {
FILE* fp = fopen(argv[i], "r");
if (fp == NULL) {
printf("wcat: cannot open file\n");
exit(1);
}
while (fgets(buffer, sizeof(buffer), fp)) {
printf("%s", buffer);
}
fclose(fp);
}
return 0;
}
wgrep
思路
要实现一个 wgrep 命令，进行字符串匹配。
根据 README 中的提示，本题测试样例中一行的字符可能会很长，因此建议使用 getline() 这类动态分配内存的函数（无需预先指定缓冲区大小）。这里要求当只有一个参数 term 时，从标准输入中读取字符串，读取方式与从文件中读取一致，区别在于文件流参数的不同：从文件中读取为调用 fopen() 返回的指针，而从标准输入读取为 stdin。
每次读取一行字符串后，需要判断该字符串中是否存在指定的子串 term，这就回到了经典的字符串匹配的问题上。为了代码编写的方便，这里我使用的是最简单的朴素字符串匹配算法，当然也可以使用有限自动机、KMP 算法、Boyer-Moore 算法等更为高效的算法，值得注意的是，Unix 系统的 grep 命令使用的正是 Boyer-Moore 算法。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 朴素字符串匹配算法
int match(char term[], size_t m, char buffer[], size_t n) {
if (n < m) return 0;
for (int i = 0; i < n - m; ++i) {
int flag = 1;
for (int j = 0; j < m; ++j) {
if (term[j] != buffer[i + j]) {
flag = 0;
break;
}
}
if (flag) return 1;
}
return 0;
}
int main(int argc, char* argv[]) {
if (argc <= 1) {
printf("wgrep: searchterm [file ...]\n");
exit(1);
}
char* term = argv[1];
size_t m = strlen(term);
char* buffer = NULL;
size_t sz = 0;
ssize_t n = 0;
if (argc == 2) { // 从标准输入中读取
while ((n = getline(&buffer, &sz, stdin)) != -1) {
if (match(term, m, buffer, (size_t)n)) {
printf("%s", buffer);
}
}
}
else {
for (int i = 2; i < argc; ++i) {
FILE* fp = fopen(argv[i], "r");
if (fp == NULL) {
printf("wgrep: cannot open file\n");
exit(1);
}
while ((n = getline(&buffer, &sz, fp)) != -1) {
// 判断字符串是否匹配
if (match(term, m, buffer, (size_t)n)) {
printf("%s", buffer);
}
}
fclose(fp);
}
}
return 0;
}
wzip
思路
实现一个简单的压缩命令，将连续重复的字符压缩为 cnt + ch。
算法的逻辑如下：
- 先将 ch 初始化为一个文件中不会出现的字符（例如
'\0'），cnt 初始化为 0. - 遍历读取到的每次字符，若与 ch 相同，则将 cnt 加 1；若不同，则使用
fwrite()写入标准输出，并把 ch 更新为当前字符，cnt 置为 1. 最后，在所有文件遍历完成后，再判断 cnt 是否大于 0，若大于 0，则写入。
注意，这里的所有字符均要按照规则进行压缩，包括换行符（'\n'），我最开始写的时候还对换行符进行特判，以此来忽略对其进行处理，属实是多此一举了。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char* argv[]) {
if (argc <= 1) {
printf("wzip: file1 [file2 ...]\n");
exit(1);
}
char* buffer = NULL;
size_t sz = 0;
ssize_t n = 0;
char ch = '\0';
int cnt = 0;
for (int i = 1; i < argc; ++i) {
FILE* fp = fopen(argv[i], "r");
if (fp == NULL) {
printf("wzip: cannot open file\n");
exit(1);
}
while ((n = getline(&buffer, &sz, fp)) != -1) {
for (int j = 0; j < n; ++j) {
if (buffer[j] == ch) {
++cnt;
}
else {
if (cnt > 0) {
fwrite(&cnt, sizeof(int), 1, stdout);
fwrite(&ch, sizeof(char), 1, stdout);
}
ch = buffer[j];
cnt = 1;
}
}
}
fclose(fp);
}
if (cnt > 0) {
fwrite(&cnt, sizeof(int), 1, stdout);
fwrite(&ch, sizeof(char), 1, stdout);
}
return 0;
}
wunzip
思路
相较于编码，解码就简单很多了。使用 fread() 每次读取一个整数 cnt 和一个字符 ch，并使用 for 循环打印 cnt 个 ch 到标准输出即可。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char* argv[]) {
if (argc <= 1) {
printf("wunzip: file1 [file2 ...]\n");
exit(1);
}
int cnt = 0;
char ch = '\0';
size_t rc = 0;
for (int i = 1; i < argc; ++i) {
FILE* fp = fopen(argv[i], "rb");
if (fp == NULL) {
printf("wunzip: cannot open file\n");
exit(1);
}
while (1) {
if ((rc = fread(&cnt, sizeof(int), 1, fp)) < 1) {
break;
}
if ((rc = fread(&ch, sizeof(char), 1, fp)) < 1) {
break;
}
for (int j = 0; j < cnt; ++j) {
printf("%c", ch);
}
}
fclose(fp);
}
return 0;
}