C程序：复杂数据结构的快照问题
问题描述 ：由于想保存数据结构在任意时刻的快照（由用户来触发），需要对 当前 的数据状态进行 深度复制 ，但是，该结构较为复杂，还没有找到有效的方法来实现。
数据结构代码 ：
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。
荒耶丿宗蓮
9 years, 8 months ago
Answers
我目前的方法是，使用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);
}
不撸但不可
answered 9 years, 8 months ago
