OSTEP Projects：KV

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

思路

题目要求实现一个最简单的数据库，以支持数据的持久化。

每个操作由格式为 op,[arg1],[arg2] 的命令给出，那么首先要解决的问题就是参数的分离，再根据操作符 op 来对不同的操作进行特殊处理。字符串划分这里采用的是 strsep() 函数：该函数接收两个参数 char** stringp 和 const char* delim，stringp 是指向待分割字符串 string 的指针，delim 则是指定的分隔符，该函数的操作是查找 string 中第一个 delim 的位置 it，并将 stringp 指向 string 中 it + 1 的位置，同时返回string 开头到 it 所有字符所构成的子串（加上 '\0' 终结符）。

插入操作没什么好说的，直接使用 fprintf() 写入文件即可。对于查找和删除，则需要将数据从文件（数据库）中读取到内存，存储在特定的数据结构中，例如哈希表、红黑树等，但为了代码实现的简单，我使用的是最简单的链表。对于查找，先将所有数据读取到一个链表中，然后按顺序逐个进行查找；对于删除，将所有数据读取到一个链表中，然后逐个遍历链表，如果当前结点的键（key）与参数不同，则写入文件中，否则，不写入（相当于删除）。最后，为了防止内存的泄露，需要在每次结束查找和删除操作之后，将存储数据内容的链表结点的内存空间释放。

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DATA_BASE "./database.txt"

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

// 从文件fp中读取数据
line_node* read_from_file(FILE* fp) {
	line_node* dummy = (line_node*)malloc(sizeof(line_node)); // 哨兵结点
	line_node* p = dummy;
	size_t sz = 0;
	while (1) {
		p->next = (line_node*)malloc(sizeof(line_node));
		p = p->next;
		if (getline(&(p->line_buf), &sz, fp) == -1) {
			p->next = NULL;
			break;
		}
	}
	return dummy->next;
}

// 释放链表内存空间
void free_list_mem(line_node* data) {
	while (data != NULL) {
		line_node* temp = data;
		data = data->next;
		free(temp);
	}
}

int main(int argc, char* argv[]) {
	for (int i = 1; i < argc; ++i) {
		char* op = strsep(&argv[i], ","); // 操作符
		if (!strcmp(op, "p")) {
			char* key = strsep(&argv[i], ",");
			char* value = strsep(&argv[i], ",");
			if (argv[i] != NULL) {
				printf("bad command\n");
				continue;
			}
			
			FILE* fp = fopen(DATA_BASE, "a");
			if (fp == NULL) {
				fprintf(stderr, "cannot open file %s\n", DATA_BASE);
				exit(1);
			}
			fprintf(fp, "%s,%s\n", key, value);
			fclose(fp);
		}
		else if (!strcmp(op, "g")) {
			char* key = strsep(&argv[i], ",");
			if (argv[i] != NULL) {
				printf("bad command\n");
				continue;
			}
			FILE* fp = fopen(DATA_BASE, "r");
			if (fp == NULL) {
				fprintf(stderr, "cannot open file %s\n", DATA_BASE);
				exit(1);
			}
			
			line_node* data = read_from_file(fp);
			line_node* p = data;
			int flag = 0;
			
			while (p != NULL) {
				char* entry = strdup(p->line_buf); // 条目备份（line_buf会被strsep()修改）
				char* token = strsep(&(p->line_buf), ",");
				if (!strcmp(token, key)) { // 找到key
					flag = 1;
					printf("%s", entry);
					break;
				}
				p = p->next;
			}
			if (!flag) {
				printf("%s not found\n", key);
			}
			
			free_list_mem(data);
			fclose(fp);
		}
		else if (!strcmp(op, "d")) {
			char* key = strsep(&argv[i], ",");
			if (argv[i] != NULL) {
				printf("bad command\n");
				continue;
			}
			
			FILE* fp = fopen(DATA_BASE, "r");
			if (fp == NULL) {
				fprintf(stderr, "cannot open file %s\n", DATA_BASE);
				exit(1);
			}
			line_node* data = read_from_file(fp);
			fclose(fp);
			
			// 清空文件
			fp = fopen(DATA_BASE, "w");
			if (fp == NULL) {
				fprintf(stderr, "cannot open file %s\n", DATA_BASE);
				exit(1);
			}
			fclose(fp);
			
			fp = fopen(DATA_BASE, "a");
			if (fp == NULL) {
				fprintf(stderr, "cannot open file %s\n", DATA_BASE);
				exit(1);
			}
			line_node* p = data;
			while (p != NULL) {
				char* entry = strdup(p->line_buf); // 条目备份
				char* token = strsep(&(p->line_buf), ",");
				if (strcmp(token, key)) { // 当前条目键值为key，不写入（相当于删除）
					fprintf(fp, "%s", entry);
				}
				p = p->next;
			}
			
			free_list_mem(data);
			fclose(fp);
		}
		else if (!strcmp(op, "c")) {
			if (argv[i] != NULL) {
				printf("bad command\n");
				continue;
			}
			FILE* fp = fopen(DATA_BASE, "w");
			if (fp == NULL) {
				fprintf(stderr, "cannot open file %s\n", DATA_BASE);
				exit(1);
			}
			fclose(fp);
		}
		else if (!strcmp(op, "a")) {
			if (argv[i] != NULL) {
				printf("bad command\n");
				continue;
			}
			FILE* fp = fopen(DATA_BASE, "r");
			line_node* data = read_from_file(fp);
			line_node* p = data;
			while (p != NULL) {
				printf("%s", p->line_buf);
				p = p->next;
			}
			free_list_mem(data);
			fclose(fp);
		}
		else {
			printf("bad command\n");
			continue;
		}
	}
	return 0;
}