OSTEP Projects：Unix Utilities

本文将介绍操作系统导论（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。

算法的逻辑如下：

1. 先将 ch 初始化为一个文件中不会出现的字符（例如 '\0'），cnt 初始化为 0.
2. 遍历读取到的每次字符，若与 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;
}