编程实现简单的git版本管理系统

git在写作业，开发软件项目，特别是团队合作开发，迭代开发中有着很大的用处。为了更进一步理解git的原理，以及掌握git的用法，了解git的实现机制，这里根据git系统的功能，实现了下git的代码。

下面先实现一个简化版的git(名为GeetFS)

给他文件系统（GeetFS）

题目背景

自从被安利了版本控制软件Git，顿顿沉迷其中无法自拔。恰好最近学习了文件系统的一些知识，于是顿顿打算在办签证的途中实现一个类似于Git的特殊“文件系统”GeetFS。

基本布局

普通的文件系统使用存储设备保存用户文件，但是GeetFS不是一个普通的文件系统。
——顿顿

GeetFS是一个基于内存的文件系统，其使用内存中的结构来保存和管理用户的文件数据。图2展示了GeetFS的工作流程和GeetFS保存数据的基本方式。在使用GeetFS时，用户发送请求给GeetFS。GeetFS会解析用户的请求，在内存数据结构中进行操作，完成用户请求。

GeetFS中的一些基本概念

• 文件：与普通文件系统中的文件概念相同，GeetFS中的文件可以保存数据。GeetFS中的文件支持读取、写入、删除。写入一个不存在（或此前已被删除）的文件会自动创建该文件；
• 文件名：每个文件拥有一个文件名，为一个长度不超过128的字符串。文件名的内容仅包含大小写英文字母（A ~ Z和a ~ z）和数字（0 ~ 9）。顿顿认为GeetFS的用户都非常善良，所以他们能够保证每个GeetFS命令中的文件名均满足上述规定，GeetFS在实现的时候无需进行检查。如图2中的file1表示一个名为file1的文件。
• 暗文件：为了表示文件的删除，GeetFS中引入了暗文件的概念。对于一个名为filename的文件，其暗文件名称为‐filename（即在文件名前增加了一个负号‐）。由于在用户创建的文件名中不允许出现‐，暗文件的文件名与普通文件的文件名并不会混淆。暗文件的文件大小为0，其中不可保存数据。其仅表示名为filename的文件被删除。一个文件与其暗文件不应同时出现在同一个提交中，也不应同时出现在暂存区中（关于提交和暂存区的概念请看下面两条）。如图2中的‐file2为一个暗文件，表示对文件file2的删除。
• 暂存区：用户所有的修改，包括文件写入、删除等，在未提交时，均保存在暂存区（即图2中的uncommitted结构，包括虚线椭圆及其右侧的文件）。其中文件的写入（包括创建）以文件的形式保存，而文件的删除以暗文件的形式保存。
• 提交：与在Git中类似，一个提交表示GeetFS的一个历史状态。一般来说，提交由commit命令创建，GeetFS将当前暂存区中的所有修改保存下来，并赋予一个唯一的提交名，成为一个提交。提交名的命名要求与文件名相同，且无需进行格式检查。除了commit命令外，用户还可以通过merge命令创建一个提交。通过merge命令创建的提交将两个现有提交进行合并。提交的创建在后文中有具体描述。除了GeetFS中的第一个提交不存在父提交之外，其余每个提交拥有一个父提交（由commit命令创建）或者两个父提交（由merge命令创建）。如图2中的cmt1表示一个名为cmt1的提交。
• HEAD：与Git中类似，HEAD表示当前的头部，指向头部提交。用户当前能够访问哪些文件，以及文件的内容，取决于当前缓存区中的内容以及当前头部所指向的提交。
• GeetFS命令：用户使用GeetFS命令对GeetFS的内容进行操作。命令只能通过标准输入传递给GeetFS，除了write命令占据两行之外，其他GeetFS均只占一行（即以换行符结尾）。

GeetFS的存储结构

GeetFS中保存了一个头部，一个暂存区结构，和若干个提交结构。

• 头部（HEAD）：GeetFS中有且仅有一个头部，为指向当前头部提交的一个指针或者引用，当GeetFS中不存在任何提交时，头部为空。
• 暂存区结构（uncommitted）：GeetFS中有且仅有一个暂存区结构。暂存区结构中包含了所有还未提交的修改。在此结构中，应该保存所有被修改（包括创建）文件的名称、大小和内容。对于删除的文件，该结构中应当保存对应的暗文件的信息。注意暗文件的大小为0，不保存数据，因此只有暗文件的文件名是有意义的信息。
• 提交结构：GeetFS中可以有零个或者多个提交结构，保存在元数据结构之中。暂存区结构中的内容在提交后，变为提交结构。一旦生成，提交结构中的内容是不可修改的。

初始状态

一个刚刚被创建出来的GeetFS文件系统只包括一个空头部和一个空的暂存区结构（即其中没有任何文件或暗文件）。

基本操作

普通的文件系统使用目录组织文件，但是GeetFS不是一个普通的文件系统。
——顿顿

作为一个“与(zhu)众(yao)不(shi)同(lan)”的文件系统，GeetFS只支持对文件的操作，并不支持目录（文件夹），同时GeekFS支持的文件操作只有三个：写入、读取和删除。这三个操作均依赖于文件的查找。

文件的查找

查找一个文件X的流程如图所示，具体规则如下：1.如果暂存区中能够查找到X文件，则找到了该文件；2.如果暂存区中不存在X文件，但是存在其暗文件‐X，则表示目标文件被删除，返回文件已被删除；3.如果在暂存区中，既不存在X文件，也
不存在其暗文件，则在暂存区中无法确定是否存在该文件，需继续查找头部所指向的提交。如果头部为空，则文件不存在；4.在一个提交中查找文件的方法与在暂存区中查找的方法相同，即先后检查目标文件和其暗文件。如果该提交中依然无法确定是否存在该文件，则继续查找该提交的父提交，直至能够确定目标文件的存在性，或父提交不存在，则该文件不存在。对于具有两个父提交的提交，其查找方法在后文merge命令中给出。

写入命令

共包括两行输入，其中第一行格式为write <filename> <offset> <len>（其中尖括号表示参数，下同），表示向文件<filename>中写入数据，写入的数据长度为<len>个字节，写入的开始位置为文件的<offset>位置（注意，在文件的位置0写
入1个字符，写入的是文件的第1个字符）。如果<offset>的位置超出了该文件的大小，则从文件当前末尾到<offset>之间的区域使用ASCII字符点（.）进行填充。在此行命令之后的一行，用户会输入<len>个字节作为文件内容，（注意结尾会有
一个换行符\n，不算做文件内容）。用户输入的内容中不包含换行字符，但是可能包含空格。在执行写入命令时，GeetFS首先按照前述方法查找该文件，并根据不同情况进行不同操作：

• 如果在暂存区中该文件被找到，则直接进行写入操作；
• 如果在某个提交中找到了该文件，则先将找到的文件拷贝到暂存区中（即在暂存区中创建该文件，并将找到的文件的内容拷贝到新文件中），再在暂存区中的文件中进行写入操作；
• 如果查找结果为文件被删除，如果是在暂存区中被删除，则删除暂存区中对应的暗文件，并在暂存区中创建该文件后进行写入操作；
• 如果是在某个提交中被删除，则在暂存区中创建该文件后进行写入操作；
• 如果该文件不存在，则在暂存区中创建该文件，并进行写入操作。

写入命令不产生输出。

读取命令

共占一行，格式为read <filename> <offset> <len>，表示从文件<filename>的<offset>位置开始读取此后的<len>个字节。对于超出文件当前大小的部分，每个超出的字节以一个ASCII字符点（.）替代。在执行时，GeetFS首先按前述方法查找该文件，如果能找到文件，则输出文件中对应的内容；如果文件不存在或者文件被删除，则输出<len>个ASCII字符点（.）。文件读取命令的输出共占一行，因此在文件内容后应有换行（\n）字符，格式也可以参考样例。

删除命令

占一行，格式为unlink <filename>，表示删除名为<filename>的文件。如果GeetFS中无法找到该文件或该文件被删除，则什么都不做。如果能够找到该文件，则在暂存区中添加该文件的暗文件。如果目标文件是在暂存区中被找到的，则还需要从暂存区中删除目标文件，只保留其暗文件。删除命令不产生输出。注意，删除操作并不能抵消文件创建操作的效果。在文件X不存在的情况下，用户可以首先创建文件X，之后将文件X删除。在删除后，暂存区中会存有一个X的暗文件（‐X），与文件X被创建前的状态不同。

列举命令

占一行，格式为ls，输出在当前的暂存区和当前的头部状态下，用户能够读到的文件（即可以查找到的文件，不包括暗文件）个数，以及其中按字典序排列，名字最小的文件名和名字最大的文件名。文件个数和两个文件名之间以一个空格隔开，共占一行。如果用户能读到的文件数为0，则只需输出数字0，占一行，无需给出文件名。列举命令的输出共占一行，因此在列举内容之后应有换行（\n）字符，具体可以参考样例。

高级操作

普通的文件系统仅仅是一个文件系统，但是GeetFS不是一个普通的文件系统。
——顿顿

作为一个有Git情节的文件系统，GeetFS当然不仅仅支持标准的文件系统接口。其还支持一系列与Git操作相似的高级命令。

提交命令（commit）

占一行，格式为commit <cmtname>。
commit命令将暂存区中的修改进行提交，其接受一个字符串类型参数<cmtname>，为新提交的名称。在进行提交时，GeetFS将当前的暂存区uncommitted重命名为给定的提交名称，并更新元数据信息。新的提交（<cmtname>）的父提交为此时头部所指向的提交。如果此时头部为空，则新提交没有父提交。此后，GeetFS将更新头部，让其指向刚刚创建的新提交（<cmtname>）。最后，GeetFS还会创建一个新的空暂存区，用于保存此后的修改。
注意，如果在提交时暂存区为空，或名为<cmtname>的提交已经存在，则该命令执行失败，GeetFS中不产生任何修改。提交命令不产生任何输出。

切换命令（checkout）

占一行，格式为checkout <cmtname>。
checkout接受一个参数，为提交名<cmtname>。该命令将当前的头部指向<cmtname >。在支持该命令之后，提交之间的关系可能会“分叉”。checkout命令不一定会成功。若在进行checkout时，暂存区不为空，或者名为<cmtname>的提交不存在，则checkout命令执行失败，GeetFS中不应产生任何修改。

合并命令（merge）

占一行，格式为merge <mergee> <cmtname>。
merge命令接受两个参数，分别为需要合并的提交名<mergee>和新提交的名字<cmtname>。假设此时头部指向的提交为headcmt，该命令将<mergee>中的内容合并到提交headcmt之上。具体来说，GeetFS会创建一个新的提交，名为<cmtname>，其两个父提交为headcmt和mergee。由merge命令创建的提交中不包含任何文件和数据，只记录了两个父提交，表示这两个父提交的内容在逻辑上进行了合并。
注意，如果在进行merge时满足以下任何一个条件，则merge执行失败，GeetFS中不产生任何修改。

• 失败条件1：暂存区不为空；
• 失败条件2：<mergee>与headcmt为同一个提交；
• 失败条件3：名为<mergee>的提交不存在。

支持merge命令会影响文件查找的规则：在支持merge命令后，一个提交（cmt）可以有两个不同的父提交（cmt.parent1和cmt.parent2）。在进行文件查找时，若在cmt中无法确定目标文件是否存在，则GeetFS需要通过cmt.parent1和cmt.parent2两
个父提交分别进行文件查找。

• 若通过两个父提交均无法找到目标文件或其暗文件，则表示要查找的文件不存在；
• 若仅能通过其中一个父提交找到该目标文件或其暗文件，则以此找到的文件作为文件查找的结果；
• 若通过两个父提交均能找到该目标文件或其暗文件，则根据所找到的两个文件的所在提交的创建时间进行选择，取创建时间最近（最大）的文件作为文件查找的结果。如果所找到的两个文件为同一个文件（即在同一个提交中），则以此文件作为文件查找的结果。

输入格式

从标准输入读入数据。
输入的第一行为一个数字N，表示该测试中的命令总个数。从第二行开始，标准输入共包含N个命令。注意，每个写入命令write共占两行，其中第一行为写入命令以及其参数，第二行为需要写入的文件内容。文件内容中不会包含换行字符，但是可能会包含空格。其他每个命令占一行，具体格式在前文已经给出。命令均符合相应格式，文件名和提交名均符合规范，读写命令中的长度均大于0，因此无需对命令格式进行错误处理。

输出格式

输出到标准输出。
根据每个命令的要求进行相应输出。

样例

文本格式样例输入

样例输入1

10
write file1 5 2
78
write file2 7 4
abcd
read file1 0 10
ls
read file2 4 10
unlink file2
ls
read file2 3 4
write file2 1 2
12
read file2 0 4

样例输出1

.....78...
2 file1 file2
...abcd...
1 file1 file1
....
.12.

样例输入2

22
write file1 3 2
ab
commit cmt1
write file2 2 4
cdef
read file1 0 10
ls
unlink file1
commit cmt2
ls
checkout cmt1
read file1 0 10
write file1 6 2
gh
write file3 2 3
ijk
commit cmt3
ls
checkout cmt2
ls
merge cmt3 cmt4
ls
read file3 0 10
checkout cmt3
write file3 5 3
lmn
read file3 0 10

样例输出2

...ab.....
2 file1 file2
1 file2 file2
...ab.....
2 file1 file3
1 file2 file2
3 file1 file3
..ijk.....
..ijklmn..

样例输入3

43
write file1 5 2
aa
write file2 2 2
bb
read file2 0 3
ls
commit cmt1
write file2 0 1
c
write file3 3 1
d
unlink file2
commit cmt2
read file3 0 5
commit cmt3
write file3 3 1
e
write file4 0 2
ff
commit cmt3
read file4 0 5
checkout cmt2
ls
unlink file4
unlink file2
read file1 0 5
unlink file1
ls
write file4 2 2
gg
write file1 3 2
hh
read file1 0 5
checkout cmt3
write file2 4 2
ii
unlink file1
commit cmt4
merge cmt4 cmt5
merge cmt3 cmt5
ls
read file4 0 5
unlink file4
merge cmt4 cmt6
write file1 8 1
j
commit cmt6
read file1 0 10
checkout cmt5
write file3 1 1
k
write file4 2 1
l
read file1 0 10
ls

样例输出3

..b
2 file1 file2
...d.
ff...
2 file1 file3
.....
1 file3 file3
...hh
3 file2 file4
..gg.
........j.
..........
3 file2 file4

子任务

提示

完成代码

#include<stdio.h>
#include<map>
#include<string>
#include<string.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

map<string,int> ms,mc;
int vis[21000],clo,tot,wrt,cmds,offset,len,sid,myfileid,nowworkspace,filename,lc[21000],lct,meid;
char s[1100],wr[2100000],ch,mes[1100];
char *temps;
string str,tos[21000],mins,maxs,mestr;
struct myfile{
    int len;
    char* s;
}myfiles[21000];
struct workspace{
    map<int,int>  tofile;
    int head,head2;
}workspaces[21000];
void write_file(int fileid){
    if (offset+len>myfiles[fileid].len){
        temps=new char[offset+len];
        memset(temps,'.',offset+len);
        for(int i=0;i<myfiles[fileid].len;++i)
            temps[i]=myfiles[fileid].s[i];
        if (myfiles[fileid].len>0)
            delete  myfiles[fileid].s;
        myfiles[fileid].len=offset+len;
        myfiles[fileid].s=temps;
    }
    for(int i=0;i<len;++i)
        myfiles[fileid].s[offset+i]=wr[i];
}
void cpyfile(int fromfile,int tofile){
    myfiles[tofile].len=myfiles[fromfile].len;
    if (myfiles[fromfile].len>0){
        myfiles[tofile].s=new char[myfiles[fromfile].len];
        memcpy(myfiles[tofile].s,myfiles[fromfile].s,myfiles[fromfile].len);
    }
}
void read_file(int fileid){
    int i;
    for(i=offset;i<offset+len&&i<myfiles[fileid].len;++i)
        putchar(myfiles[fileid].s[i]);
    for(;i<offset+len;++i)
        putchar('.');
    putchar('\n');
}
void unlink_file(int fileid){
    if (myfiles[fileid].len>0)
        delete myfiles[fileid].s;
    myfiles[fileid].len=-1;
}
void handle_write(){
    scanf("%s%d%d",s,&offset,&len);
    str=string(s);
    if  (!ms.count(str)){
        ms[str]=++sid;
        tos[sid]=str;
    }
    filename=ms[str];

    getchar();
    wrt=0;
    while ((ch=getchar())>30) wr[wrt++]=ch;
    
    if (workspaces[nowworkspace].tofile.count(filename)){
        write_file(workspaces[nowworkspace].tofile[filename]);
    }else{
        // faworkspace=workspaces[nowworkspace].head;
        // while (faworkspace){
        //     if (workspaces[faworkspace].tofile.count(filename)){
        //         workspaces[nowworkspace].tofile[filename]=++myfileid;
        //         cpyfile(workspaces[faworkspace].tofile[filename],myfileid);
        //         write_file(myfileid);
        //         return;
        //     }
        //     faworkspace=workspaces[faworkspace].head;
        // }
        clo++;
        vis[workspaces[nowworkspace].head]=clo;
        vis[workspaces[nowworkspace].head2]=clo;
        fd(i,nowworkspace-1,1) if (vis[i]==clo){
            vis[workspaces[i].head]=clo;
            vis[workspaces[i].head2]=clo;
            if (workspaces[i].tofile.count(filename)){
                workspaces[nowworkspace].tofile[filename]=++myfileid;
                cpyfile(workspaces[i].tofile[filename],myfileid);
                write_file(myfileid);
                return;
            }
        }
        workspaces[nowworkspace].tofile[filename]=++myfileid;
        write_file(myfileid);
    }
}
void handle_read(){
    scanf("%s%d%d",s,&offset,&len);
    str=string(s);
    if  (!ms.count(str)){
        for(int i=0;i<len;++i) putchar('.');
        putchar('\n');
        return;
    }
    filename=ms[str];

    if (workspaces[nowworkspace].tofile.count(filename)){
       read_file(workspaces[nowworkspace].tofile[filename]);
    }else{
        // faworkspace=workspaces[nowworkspace].head;
        // while (faworkspace){
        //     if (workspaces[faworkspace].tofile.count(filename)){
        //         read_file(workspaces[faworkspace].tofile[filename]);
        //         return;
        //     }
        //     faworkspace=workspaces[faworkspace].head;
        // }
        clo++;
        vis[workspaces[nowworkspace].head]=clo;
        vis[workspaces[nowworkspace].head2]=clo;
        fd(i,nowworkspace-1,1) if (vis[i]==clo){
            vis[workspaces[i].head]=clo;
            vis[workspaces[i].head2]=clo;
            if (workspaces[i].tofile.count(filename)){
                read_file(workspaces[i].tofile[filename]);
                return;
            }
        }       
        read_file(0);
    }
}
void handle_unlink(){
    scanf("%s",s);
    str=string(s);
    if  (!ms.count(str)){
        return;
    }
    filename=ms[str];   

     if (workspaces[nowworkspace].tofile.count(filename)){
       unlink_file(workspaces[nowworkspace].tofile[filename]);
    }else{
        // faworkspace=workspaces[nowworkspace].head;
        // while (faworkspace){
        //     if (workspaces[faworkspace].tofile.count(filename)){
        //         if (myfiles[workspaces[faworkspace].tofile[filename]].len>0){
        //             workspaces[nowworkspace].tofile[filename]=++myfileid;
        //             myfiles[myfileid].len=-1;
        //         }
        //         return;
        //     }
        //     faworkspace=workspaces[faworkspace].head;
        // }
        clo++;
        vis[workspaces[nowworkspace].head]=clo;
        vis[workspaces[nowworkspace].head2]=clo;
        fd(i,nowworkspace-1,1) if (vis[i]==clo){
            vis[workspaces[i].head]=clo;
            vis[workspaces[i].head2]=clo;
            if (workspaces[i].tofile.count(filename)){
                if (myfiles[workspaces[i].tofile[filename]].len>0){
                    workspaces[nowworkspace].tofile[filename]=++myfileid;
                    myfiles[myfileid].len=-1;
                }
                return;
            }
        }       
    }   
}
void handle_ls(){
    map<int,int> tempms;
    lct=0;
    // faworkspace=nowworkspace;
    // while (faworkspace){
    //     lc[++lct]=faworkspace;
    //     faworkspace=workspaces[faworkspace].head;
    // }
    clo++;
    vis[nowworkspace]=clo;
    fd(i,nowworkspace,1) if (vis[i]==clo){
        vis[workspaces[i].head]=clo;
        vis[workspaces[i].head2]=clo;
        lc[++lct]=i;
    }       
    fd(i,lct,1){
        for(auto it=workspaces[lc[i]].tofile.begin();it!=workspaces[lc[i]].tofile.end();++it)
            tempms[it->first]=it->second;
    }

    tot=0;
    for(auto it=tempms.begin();it!=tempms.end();++it){
        if (myfiles[it->second].len>0){
            if (!tot||tos[it->first]<mins) mins=tos[it->first];
            if (!tot||tos[it->first]>maxs) maxs=tos[it->first];
            ++tot;
        }
    }
    if (tot) 
        printf("%d %s %s\n",tot,mins.c_str(),maxs.c_str());
    else
        printf("0\n");
}
void handle_commit(){
    scanf("%s",s);
    if (!workspaces[nowworkspace].tofile.size())
        return;
    str=string(s);
    if  (mc.count(str))
        return;
    mc[str]=nowworkspace;
    ++nowworkspace;
    workspaces[nowworkspace].head=nowworkspace-1;
    workspaces[nowworkspace].tofile.clear();
}
void handle_checkout(){
    scanf("%s",s);
    if (workspaces[nowworkspace].tofile.size())
        return;
    str=string(s);
    if  (!mc.count(str))
        return;
    // nowworkspace=mc[str];
    workspaces[nowworkspace].head=mc[str];
    workspaces[nowworkspace].tofile.clear();
}
void handle_merge(){
    scanf("%s%s",mes,s);
    if (workspaces[nowworkspace].tofile.size())
        return;
    mestr=string(mes);
    if (!mc.count(mestr))
        return;
    meid=mc[mestr];
    if (meid==workspaces[nowworkspace].head)
        return;
    
    str=string(s);
    if (mc.count(str)) return;//???
    workspaces[nowworkspace].head2=meid;
    mc[str]=nowworkspace;
    ++nowworkspace;
    workspaces[nowworkspace].head=nowworkspace-1;
    workspaces[nowworkspace].tofile.clear();
}
int main(){
    nowworkspace=1;

    scanf("%d",&cmds);
    while (cmds--){
        scanf("%s",s);
        if (s[0]=='w'&&s[1]=='r'){//&&s[2]=='i'&&s[3]=='t'&&s[4]=='e'
           handle_write();
           continue;
        }
        if (s[0]=='r'&&s[1]=='e'){//&&s[2]=='a'&&s[3]=='d'
            handle_read();
            continue;
        }
        if (s[0]=='u'&&s[1]=='n'){//&&s[2]=='l'&&s[3]=='i'&&s[4]=='n'&&s[5]=='k'
            handle_unlink();
            continue;
        }
        if (s[0]=='l'&&s[1]=='s'){
            handle_ls();
            continue;
        }
        if (s[0]=='c'&&s[1]=='o'){
            handle_commit();
            continue;
        }
        if (s[0]=='c'&&s[1]=='h'){
            handle_checkout();
            continue;
        }
        if (s[0]=='m'&&s[1]=='e'){
            handle_merge();
            continue;
        }
    }
    return 0;
}