今天遇到的问题是，我需要在一个二进制文件中写入一个数字数组，并指定一个起始位置。我知道它应该从哪里开始，但我不希望覆盖在此之后的任何值，只想将数组插入到文件的起始位置。例如：
12345
让我们将456推到位置2：
12456345
我知道可能需要自己实现，但我想知道你对如何尽可能高效地实现它的意见。
在二进制文件中间写入内容，且不覆盖任何现有内容的C语言实现方式。
10
- Frederico Schardong
5
@John的回答似乎是唯一的方法，但对于大文件来说，这将涉及大量复制。因此，如果有可能，寻找另一种数据序列化方法可能是最好的选择。 - gcbenison
@gcbenison，是的，我的二进制文件可能会有1GB大小，而且扩展过程会被多次触发，所以这可能会成为一个问题。 - Frederico Schardong
最好避免在文件中间插入数据，因为这样做非常昂贵，特别是在千兆字节大小的文件中更是如此。 - Jonathan Leffler
@JonathanLeffler 是的，你说得对。也许最好先将它们存储在小文件中，当我不再需要扩大它时，再将它们连接起来。 - Frederico Schardong
2一定要为这个插入代码编写良好的测试。覆盖小偏移量和大小、边缘情况以及大偏移量和大小。后者尤其重要，因为当处理大文件时，您不能承受算术溢出。这些会导致程序卡死、崩溃、文件长度过短或过长，与应有的文件数据不符合。32位整数在 ~2GB 处开始溢出。 - Alexey Frunze
4个回答
13
这是一个名为extend_file_and_insert()的函数，大体上可以完成工作。
#include <sys/stat.h>
#include <unistd.h>
enum { BUFFERSIZE = 64 * 1024 };
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
/*
off_t is signed
ssize_t is signed
size_t is unsigned
off_t for lseek() offset and return
size_t for read()/write() length
ssize_t for read()/write() return
off_t for st_size
*/
static int extend_file_and_insert(int fd, off_t offset, char const *insert, size_t inslen)
{
char buffer[BUFFERSIZE];
struct stat sb;
int rc = -1;
if (fstat(fd, &sb) == 0)
{
if (sb.st_size > offset)
{
/* Move data after offset up by inslen bytes */
size_t bytes_to_move = sb.st_size - offset;
off_t read_end_offset = sb.st_size;
while (bytes_to_move != 0)
{
ssize_t bytes_this_time = MIN(BUFFERSIZE, bytes_to_move);
ssize_t rd_off = read_end_offset - bytes_this_time;
ssize_t wr_off = rd_off + inslen;
lseek(fd, rd_off, SEEK_SET);
if (read(fd, buffer, bytes_this_time) != bytes_this_time)
return -1;
lseek(fd, wr_off, SEEK_SET);
if (write(fd, buffer, bytes_this_time) != bytes_this_time)
return -1;
bytes_to_move -= bytes_this_time;
read_end_offset -= bytes_this_time; /* Added 2013-07-19 */
}
}
lseek(fd, offset, SEEK_SET);
write(fd, insert, inslen);
rc = 0;
}
return rc;
}
(请注意于2013-07-19添加的额外行；这是一个错误，只有当缓冲区大小小于要复制到文件上的数据时才会显示出来。感谢malat指出了这个错误。现在使用BUFFERSIZE = 4进行测试。)
这是一些小规模的测试代码：
#include <fcntl.h>
#include <string.h>
static const char base_data[] = "12345";
typedef struct Data
{
off_t posn;
const char *data;
} Data;
static const Data insert[] =
{
{ 2, "456" },
{ 4, "XxxxxxX" },
{ 12, "ZzzzzzzzzzzzzzzzzzzzzzzzX" },
{ 22, "YyyyyyyyyyyyyyyY" },
};
enum { NUM_INSERT = sizeof(insert) / sizeof(insert[0]) };
int main(void)
{
int fd = open("test.dat", O_RDWR | O_TRUNC | O_CREAT, 0644);
if (fd > 0)
{
ssize_t base_len = sizeof(base_data) - 1;
if (write(fd, base_data, base_len) == base_len)
{
for (int i = 0; i < NUM_INSERT; i++)
{
off_t length = strlen(insert[i].data);
if (extend_file_and_insert(fd, insert[i].posn, insert[i].data, length) != 0)
break;
lseek(fd, 0, SEEK_SET);
char buffer[BUFFERSIZE];
ssize_t nbytes;
while ((nbytes = read(fd, buffer, sizeof(buffer))) > 0)
write(1, buffer, nbytes);
write(1, "\n", 1);
}
}
close(fd);
}
return(0);
}
它产生以下输出：
12456345
1245XxxxxxX6345
1245XxxxxxX6ZzzzzzzzzzzzzzzzzzzzzzzzZ345
1245XxxxxxX6ZzzzzzzzzzYyyyyyyyyyyyyyyYzzzzzzzzzzzzzzZ345
应该在一些更大的文件上进行测试（比BUFFERSIZE大的文件），但是测试时使用的BUFFERSIZE应该远小于64 KiB，我使用了32个字节，结果看起来还不错。我只是用肉眼检查了结果，但这些模式都是为了方便查看它们是否正确而设计的。代码没有检查任何lseek()调用，这是一个较小的风险。
- Jonathan Leffler
1
@malat：是的，你说得对。当代码需要移动多个缓冲区的数据时，
read_end_offset 的值需要减去 bytes_this_time。我已经编写了修复程序，并使用 BUFFERSIZE=4 进行了测试（这在未修复的代码中显示了错误）。感谢你指出这个错误。 - Jonathan Leffler5
首先使用ftruncate()来扩大文件到最终大小。然后将旧结尾的所有内容复制到新结尾，一直回溯到插入点。然后用要插入的数据覆盖中间内容。我认为这是效率最高的方法，因为文件系统通常不会真正提供在文件中间进行“插入”。
- John Zwinck
2
这是一个不错的解决方案。我知道这可能是个愚蠢的问题，但你能否提供一个例子或一个好的链接？谢谢！ - Frederico Schardong
4只需动笔写下来，学习一两件事情。 - Alexey Frunze
1
我同意其他人的观点，但是让我稍微以不同的方式陈述解决方案：
获取一个临时文件名（有特定于操作系统的调用）
将原始文件复制到临时文件中（现在有两个相同文件的副本）
打开原始文件进行“追加”。
将其“截断”到您要插入的位置
编写新数据
打开您的临时文件进行“读取”
“寻找”插入点（再次调用是特定于操作系统的）
在临时文件中读取到文件末尾；插入到您仍然打开的原始文件中进行“追加”。
关闭两个文件
删除临时文件
- paulsm4
1
谢谢你的答案，看起来也很棒。我对小文件的想法非常赞同，因为它似乎是最少 I/O 量的方式，因为每个“中间插入”最初提出的操作只有一次追加操作。与你提到的十个步骤不同，我只需要一个追加操作。@paulsm4 你同意吗？ - Frederico Schardong
0
我将广泛解释您的问题为“如何高效实现一个支持随机访问索引和插入扩展的对象的持久存储”。如前所述，您可以在文件中使用简单的线性数组，但这只对查找（O（1））有效，并且对于插入非常低效（O（n））。而使用树数据结构，则可同时实现 O(log n) 的查找和插入。维护一个充当索引的文件和另一个作为数据存储的文件，后者是一系列块，每个块都可以部分填充。索引文件包含树（二叉树或B树），其中每个节点对应于一些连续的数组块，并包含该块的大小（因此根节点包含整个数组的大小）。对于二叉树，左右子节点包含左右半边（大致上）数组的大小。最后，叶子节点包含指向数据存储文件中包含实际数据的块的指针。现在，插入涉及更改树的“大小”属性的“k”个节点，其中“k”是树的高度。当数据存储块变得太满时，分割它（通过增长文件来分配新块，或者如果您还支持删除，则可能来自空块的空闲列表），并重新平衡树（有许多标准方法可实现此操作）。
这听起来很复杂吗？绝对是的！实现高效的中间文件插入比追加更加复杂。
- gcbenison
5
如之前所述，我的文件可能会增长到1GB，我预计会有数千个中间插入。我正在考虑将大文件拆分为小文件，以便能够在其末尾附加新内容，然后在所有操作完成后再将这些小文件合并。我相信，使用追加操作的小文件没有比这更有效的解决方案了。您认为呢，@gcbenison？ - Frederico Schardong
你可以保留一堆小文件，而不是将小块存储在一个大文件中，但你仍然需要某种索引块的方式。如果这种方式只是在每个块上贴上顺序标签，那么插入操作的时间复杂度将为O(n)，因为你必须更新每个块的标签。因此采用基于树的方法。 - gcbenison
需要更新每个标签吗？没有必要这样做。 - Frederico Schardong
如果许多插入操作都落在同一个块中，那么在某个时候你需要对其进行拆分，否则你最终只会将数据插入到一个大文件的中间位置，而这正是分块方法试图避免的。当你拆分块时，索引方案也需要更新以便能够找到新的块。 - gcbenison
是的，但无论如何，您的树数据结构提议将不得不执行截断以进行每个新的中间插入，因此需要像其他回答我的帖子所建议的那样进行复制操作，对吗？ - Frederico Schardong
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接