本文将介绍操作系统导论(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;
}