今天的问题是我需要在二进制文件的起始位置写入一个数字数组。我有它应该开始的位置，之后我不想覆盖值，只想在文件的起始位置插入数组。例如：
12345
让我们在位置 2 推 456：
12456345
我知道可能我必须自己实现它，但我想知道您对如何尽可能有效地实现它的看法。
问问题
8039 次
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 的文件，但使用比 64 KiB 小很多的 BUFFERSIZE 进行测试是明智的；我使用了 32 个字节，而且似乎还可以）。我只观察了结果，但这些模式的设计目的是让人们很容易看出它们是正确的。该代码不检查任何lseek()调用；这是一个小风险。
于 2012-05-06T05:07:40.727 回答
5
首先，使用ftruncate()将文件放大到最终大小。然后将所有内容从旧端复制到新端，然后返回插入点。然后用要插入的数据覆盖中间的内容。我认为这是尽可能高效的，因为文件系统通常不会在文件中间提供真正的“插入”。
于 2012-05-06T02:55:49.383 回答
1
我同意其他人的观点，但让我以不同的方式说明解决方案：
获取临时文件名（对此有特定于操作系统的调用）
将原始文件复制到临时文件（同一个文件现在有两个副本）
打开“追加”的原始文件。
将其“截断”到您的插入点
写入新数据
打开您的临时文件进行“读取”
“寻找”到插入点（同样，调用是特定于操作系统的）
读取到临时文件中的文件结尾；插入到您的原始文件中（仍然为“追加”打开）。
关闭两个文件
删除临时文件
于 2012-05-06T04:20:41.637 回答
0
我将把您的问题广义地解释为“如何有效地实现对象的持久存储，该对象支持通过索引进行随机访问查找和通过扩展插入。” 如前所述，您可以在文件中使用简单的线性数组，但这只会对查找（O（1））有效，而对于插入（O（n））效率很低。您可以通过使用树数据结构来实现查找和插入的 O(log n)。维护一个充当索引的文件，另一个充当数据存储并且是一系列块。每个块都可以部分满。索引文件包含一棵树（二叉树或 B 树），其中每个节点对应于数组的某个连续块并包含该块的大小（以便根节点包含整个数组的大小）。对于二叉树，左右子节点包含数组左右两半（大约）的大小。最后，叶节点包含指向数据存储文件中包含实际数据的块的指针。插入现在涉及更改“k”节点的“大小”属性，其中“k”是树的高度。当数据存储块太满时，将其拆分（通过增加文件分配一个新块，或者，如果您也支持删除，可能从空块的空闲列表中）并重新平衡树（许多标准的做这。）k' 是树的高度。当数据存储块太满时，将其拆分（通过增加文件分配一个新块，或者，如果您也支持删除，可能从空块的空闲列表中）并重新平衡树（许多标准的做这。）k' 是树的高度。当数据存储块太满时，将其拆分（通过增加文件分配一个新块，或者，如果您也支持删除，可能从空块的空闲列表中）并重新平衡树（许多标准的做这。）
这听起来很复杂吗？确实！高效的中间文件插入比追加更复杂。
于 2012-05-06T04:13:04.443 回答