C писать в середине двоичного файла без перезаписи любого существующего содержимого
Сегодняшняя проблема заключается в том, что мне нужно написать массив чисел в двоичном файле в начальной позиции. У меня есть позиция, с которой он должен начинаться, и я не хочу перезаписывать значения после этого, просто хочу вставить массив в начальную позицию в файле. Например:
12345
Давайте толкнем 456 в положение 2:
12456345
Я знаю, что, вероятно, мне придется реализовать это самостоятельно, но я хочу знать, что вы думаете о том, как реализовать это максимально эффективно.
4 ответа
Вот функция 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 КиБ; я использовал 32 байта, и, похоже, все в порядке). Я только оценил результаты, но шаблоны разработаны так, чтобы было легко увидеть, что они верны. Код не проверяет любой из lseek() звонки; это незначительный риск.
Во-первых, используйте ftruncate() чтобы увеличить файл до окончательного размера. Затем скопируйте все со старого конца на новый, вернувшись к точке вставки. Затем перезаписать среднее содержание данными, которые вы хотите вставить. Я думаю, что это настолько эффективно, насколько это возможно, потому что файловые системы обычно не предлагают истинную "вставку" в середине файлов.
Я согласен с остальными, но позвольте мне сформулировать решение немного иначе:
Получить временное имя файла (для этого существуют специфичные для ОС вызовы)
Скопируйте исходный файл во временный файл (теперь есть две копии одного и того же файла)
Откройте исходный файл для "добавления".
"Обрезать" его до точки вставки
Напишите ваши новые данные
Откройте временный файл для "чтения"
"Искать" в точке вставки (опять же, вызов зависит от ОС)
Чтение до конца файла во временном файле; вставка в исходный файл (по-прежнему открыт для "добавления").
Закройте оба файла
Удалить временный файл
Я собираюсь интерпретировать ваш вопрос так: "Как я могу эффективно реализовать постоянное хранилище объекта, которое поддерживает поиск с произвольным доступом по индексу и вставку с расширением". Как уже отмечалось, вы можете использовать простой линейный массив в файле, но это будет эффективно только для поиска (O(1)) и совершенно неэффективно для вставки (O(n)). Вы можете достичь O(log n) как для поиска, так и для вставки, используя вместо этого древовидную структуру данных. Сохраняйте один файл, который действует как индекс, а другой - как хранилище данных и представляет собой последовательность фрагментов. Каждый кусок может быть частично заполнен. Индексный файл содержит дерево (двоичное дерево или B-дерево), где каждый узел соответствует некоторому смежному фрагменту массива и содержит размер этого фрагмента (так что корневой узел содержит размер всего массива). Для двоичного дерева левый и правый дочерние узлы содержат размер левой и правой половин (приблизительно) массива. Наконец, конечные узлы содержат указатель на блок в файле хранилища данных, который содержит фактические данные. Теперь вставка включает изменение свойства "size" узлов "k", где "k" - высота дерева. Когда чанк хранилища данных становится слишком полным, разделите его (выделите новый, увеличив размер файла, или, если вы также поддерживаете удаление, возможно, из свободного списка пустых чанков), и перенастройте дерево (множество стандартных способов выполнения этот.)
Это звучит сложно? Определенно! Эффективная вставка в середине файла более сложна, чем добавление.