c - 与版本化字符串数据一起工作的数据结构？

Question

CS 中正确调用的“版本化数据结构”是什么？

有没有 我可以自行浏览、比较和选择的现有“版本化数据结构”列表？我只找到一篇关于“多版本哈希表”(标题 Hash Tables in Logic Programming，大约 1987 年)的论文，这就是我能找到的全部内容。

示例数据(在下面的讨论中要求):

"a b" c "d e" {
    f {
        "g h" "i j" {
            "k l m" n "o p q" {
                r;
            }
        }
    }
}
"a b" x {
     y {
         "z z z";
     }
}
"foo bar" baz;
"foo baz" bar;

如果出现多个类似的“树”，那么它们将留在原地，例如:

foo {
    bar;
    oof;
    bar {
       "a b c";
    }
    bar;
}

永远不会排序，但始终保持与写入相同的顺序。

数据将被一些“提交/版本”工具“编译”成二进制形式，然后“回滚”回文本形式或由其他工具查询。

为了更清楚地说明，让我们看一些 Unix shell 中的用法示例:

sh> $EDITOR file.txt
File saved.

sh> commit file.txt                      # create/commit file.txt.db (we assume 9 commits before this one)
Commited as version 10.

sh> show file.txt.db 'a b'               # Trailing '*' is implicit
"a b" c "d e" {
    f {
        "g h" "i j" {
            "k l m" n "o p q" {
                r;
            }
        }
    }
}
"a b" x {
     y {
         "z z z";
     }
}

sh> show file.txt.db 'a b' '*' y
"a b" x {
     y {
         "z z z";
     }
}

sh> show file.txt.db 'foo *'
"foo bar" baz;
"foo baz" bar;

sh> show file.txt.db -rollback=2 'a b'  # "historical" query, say that 'a b" c "d e" ...' was not there the time
"a b" x {
     y {
         "z z z";
     }
}

sh> rollback file.txt.db 2
Rolled back to version 2.

sh> $EDITOR file.txt
File saved.

sh> commit file.txt                      # new "branch" commit (because of the rollback above)!
Commited as version 2.1.

注意:始终保存所有历史记录!什么都不会被删除(如果其他工具没有明确要求的话)。

等等。也许需要一些“日志”或“日志”？？

Answer 1

如果您处理的是纯文本数据，则基本的版本化数据结构可以像数组或结构链表一样简单，如下所示:

struct versioned_string {
    int   version;
    char* data;
};

“提交”一个新条目只涉及分配一个新字符串来存储数据。检索特定版本将涉及遍历列表以查找特定的 version 值(对于链表)或索引到数组(对于数组)。 “回滚”将涉及从列表末尾清除一个条目并释放关联的字符串。

您还可以使用数据库(例如 sqlite)，将信息存储在表中，然后让数据库引擎处理添加、删除和搜索。然而，这可能有点矫枉过正。

不过，我并没有真正效仿你的例子。我假设您发布的第一个代码块表示单个输入字符串(即特定版本的文本数据的快照)？如果是这样，那么多个“树”应该不是问题，因为输入是作为原始文本存储的，没有以任何方式处理或解释。我当然不明白你的“Unix shell”例子。你能更详细地分解一下吗？具体来说，对于每一行，清楚地列出输入是什么、输出是什么以及您期望数据的“当前版本”在该点看起来像什么。

更新: 忽略我之前关于回滚的评论；我在考虑这个网站如何使用该术语(意思是恢复到以前的状态)，而你使用该术语的方式不同(意思是检索旧版本)。

整个数据集的每个快照都可以由单个 C 字符串表示，因为元素由非空字符(空格和/或大括号)分隔。一个简单的数据结构，如我上面概述的那样，应该可以为您提供创建它们的链接列表时所需的功能。由于数据存储在它的字符串表示中，提交和回滚操作就像向列表添加新元素(用于提交)或向后遍历列表并将字符串传递给 printf(用于回滚)。 “显示”命令是另一种动物，因为它与您对数据进行版本化的方式并没有太大关系。就版本控制系统而言，您要做的就是从列表中获取最后一个条目。那里的实际工作是由您创建的用于在内部解析字符串和操作数据的任何库函数完成的。