C程序：复杂数据结构的快照问题

Question

问题描述：由于想保存数据结构在任意时刻的快照（由用户来触发），需要对当前的数据状态进行深度复制，但是，该结构较为复杂，还没有找到有效的方法来实现。

数据结构代码：

struct value {
value* prev;
value* next;
int value;
};
struct entry {
entry* prev;
entry* next;
value* values;
char key[MAX_KEY_LENGTH];
};
struct snapshot {
snapshot* prev;
snapshot* next;
entry* entries;
int id;
};

如下图描述的那样，1、2、3分别是三个时刻的快照，其保存的是三个时刻的current database state；current database state是当前用户编辑数据的环境。现在的问题就是，如何将current database state复制一份并保存。同时，快照1、2、3还可以被rollback到current database state。

Answer 1

一个方案是把数据存成c++里的vector, 然后serialize, 比如用boost::serialization.

Answer 2

将数据以二进制的形式保存到日志文件中，需要的时候再从这个日志文件中读取出来，一般思路应该都是这个样子的。

Answer 3

我目前的方法是，使用malloc在内存中逐一为current state分配空间，然后按照其原有连接一一复原。代码如下：

            entry* currentEntry = entry_head; // 当前状态
            entry* lastEntry = NULL;
            value* cpValue = NULL;
            value* lastValue = NULL;
            snapshot* newSnapshot = NULL; // 新建的快照
            newSnapshot = (snapshot*)malloc(sizeof(snapshot));
            snapIndex++;
            newSnapshot -> id = snapIndex; // 设置快照ID
            newSnapshot -> prev = NULL;
            newSnapshot -> next = NULL;
            // 开始复制当前状态
            if(currentEntry == NULL){
                newSnapshot -> entries = NULL;
                printf("no entries\n");
            }else{
                    // 由于前一个元素无法确定后一个元素的位置（还未创建），因此，只设置prev指针
                    while(currentEntry != NULL){
                    newEntry = (entry*)malloc(sizeof(entry));
                    newEntry -> next = NULL;
                    strcpy(newEntry -> key, currentEntry -> key);
                    newEntry -> prev = lastEntry;
                    valuePt = currentEntry -> values;
                    while(valuePt != NULL){
                        cpValue = (value*)malloc(sizeof(value));
                        cpValue -> next = NULL;
                        cpValue -> value = valuePt -> value;
                        cpValue -> prev = lastValue;
                        valuePt = valuePt -> next;
                        lastValue = cpValue;
                    }
                    // 反向设置next指针
                    while(lastValue != NULL){
                        if(lastValue -> prev != NULL){
                            lastValue -> prev -> next = lastValue;
                            lastValue = lastValue -> prev;
                        }else{
                            // first value
                            newEntry -> values = lastValue;
                            break;
                        }
                    }

                    currentEntry = currentEntry -> next;
                    lastEntry = newEntry;
                    lastValue = NULL;
                }
                // 反向设置next指针
                while(lastEntry != NULL){

                    if(lastEntry -> prev != NULL){
                        lastEntry -> prev -> next = lastEntry;
                        lastEntry = lastEntry -> prev;
                    }else{
                        newSnapshot -> entries = lastEntry; // 设置新快照的entries指针，此时lastEntry指向第一个value
                        break;
                    }
                }
            }

            // 将新snapshot加入链表中
            if(snapshot_head == NULL){
                snapshot_head = newSnapshot;
            }else{
                newSnapshot -> next = snapshot_head;
                snapshot_head -> prev = newSnapshot;
                snapshot_head = newSnapshot;
            }
            printf("save as snapshot %d\n", snapIndex);

        }