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)) { // 找到keyflag = 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;
}