OSTEP Projects：Reverse

本文将介绍操作系统导论（Operating Systems: Three Easy Pieces）作者所开源的操作系统相关课程项目 的 Reverse 部分，包含个人的代码实现和设计思路。

思路

题目的要求很简单：按行读取数据，读取完成后将所读取到的所有行反向输出（行间反向，行内不变）。但代码实现上却包含不少细节。

首先是核心问题：如何将读取到行反向输出？首先可以确定的一点是：在所有行读取完成之前，读取到的每一个行都需要进行保存。那么，利用什么数据结构进行保存呢？我们需要这个数据结构能够确定输入的不同行之间的前后相对关系，因此想到使用线性表。由于最终读取到的行数是不确定的，因此不能使用一个固定大小的数组，而应该使用可变长的线性表，如链表、动态数组。而又因为可变数组的扩容操作比较耗时，且我们并不需要对元素进行随机访问，只需要最后输出的时候进行顺序遍历，因此链表就成为了最佳选择。

反转的具体实现可以参考经典问题反转链表，设定一个前驱结点 pre 和当前结点 cur，每次读取到新的行，就动态申请存储该行数据的内存空间，并将 cur 指向这块内存空间，然后将 cur 的 next 域指向 pre，然后 pre 再指向 cur，以便进行下一行的操作。

根据 README 的说明，当输入文件和输出文件是同一个文件时，程序打印相关错误信息并退出。这里一个简单的想法是使用 strcmp(argv[1], argv[2]) 判断两个参数字符串是否相同，但文件路径的表示方式并不是唯一的，如 ./t1.txt 和 t1.txt 字符串不同，但表示的却是同一个文件。一个正确的做法是使用 stat() 函数，用以获取文件的状态信息，并对比输入与输出文件的状态信息是否相同。

最后，输入输出部分代码的实现可以封装为一个函数，并引入参数 FILE*，其中标准输入（stdin）和标准输出（stdout）可以看作是一个抽象的文件，并使用 fprintf() 进行文件写入。

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>

typedef struct LineNode {
	char* line_buf;
	struct LineNode* next;
} line_node;

// 判断两个路径是否表示同一个文件
int is_same_file(const char* file1, const char* file2) {
	struct stat sb1, sb2;
	stat(file1, &sb1);
	stat(file2, &sb2);
	return sb1.st_dev == sb2.st_dev && sb1.st_ino == sb2.st_ino; // 设备ID和inode号均相同
}

// 从文件fp中读取行数据
line_node* read_from_file(FILE* fp) {
	size_t sz = 0;
	line_node* cur = NULL; // 当前结点
	line_node* pre = NULL; // 前置结点
	while (1) {
		cur = (line_node*)malloc(sizeof(line_node*));
		if (cur == NULL) {
			fprintf(stderr, "malloc failed\n");
			exit(1);
		}
		if (getline(&(cur->line_buf), &sz, fp) == -1) { // 读到文件末尾，删去当前无效结点并结束循环
			line_node* temp = cur;
			cur = pre;
			free(temp);
			break;
		}
		cur->next = pre; // 链表反转
		pre = cur;
	}
	return cur;
}

// 写入反转后的数据到文件fp
void write_to_file(line_node* cur, FILE* fp) {
	while (cur != NULL) {
		fprintf(fp, "%s", cur->line_buf);
		line_node* temp = cur;
		cur = cur->next;
		free(temp);
	}
}

int main(int argc, char* argv[]) {
	line_node* cur = NULL;
	
	if (argc == 1) {
		cur = read_from_file(stdin);
		write_to_file(cur, stdout);
	}
	else if (argc >= 2 && argc <= 3) {
		FILE* fp = fopen(argv[1], "r");
		if (fp == NULL) {
			fprintf(stderr, "reverse: cannot open file '%s'\n", argv[1]);
			exit(1);
		}
		cur = read_from_file(fp);
		
		if (argc == 2) {
			write_to_file(cur, stdout);
		}
		else {
			FILE* fp2 = fopen(argv[2], "w");
			if (fp2 == NULL) {
				fprintf(stderr, "reverse: cannot open file '%s'\n", argv[2]);
				exit(1);
			}
			if (is_same_file(argv[1], argv[2])) {
				fprintf(stderr, "reverse: input and output file must differ\n");
				exit(1);
			}
			write_to_file(cur, fp2);
			fclose(fp2);
		}
		fclose(fp);
	}
	else {
		fprintf(stderr, "usage: reverse <input> <output>\n");
		exit(1);
	}
	return 0;
}