C write in the middle of a binary file without overwriting any existing content

Question

Today's problem is that I need to write an array of numbers in a binary file at a starting position. I have the position where it should start, and I don't want to overwrite values after that, just want to insert the array at the starting position in the file. E.g:

12345

Let's push 456 at position 2:

12456345

I know that probably I'll have to implement it by myself, but I want to know what's your opinion on how to implement that as efficiently as possible.

Answer 1

Here's a function extend_file_and_insert() that does the job, more or less.

#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;
}

(Note the additional line added 2013-07-19; it was a bug that only shows when the buffer size is smaller than the amount of data to be copied up the file. Thanks to malat for pointing out the error. Code now tested with BUFFERSIZE = 4.)

This is some small-scale test code:

#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);
}

It produces the output:

12456345
1245XxxxxxX6345
1245XxxxxxX6ZzzzzzzzzzzzzzzzzzzzzzzzZ345
1245XxxxxxX6ZzzzzzzzzzYyyyyyyyyyyyyyyYzzzzzzzzzzzzzzZ345

It should be tested on some larger files (ones bigger than BUFFERSIZE, but it would be sensible to test with a BUFFERSIZE a lot smaller than 64 KiB; I used 32 bytes and it seemed to be OK). I've only eyeballed the results but the patterns are designed to make it easy to see that they are correct. The code does not check any of the lseek() calls; that's a minor risk.

Answer 2

First, use ftruncate() to enlarge the file to the final size. Then copy everything from the old end over to the new end, working your way back to the insertion point. Then overwrite the middle contents with the data you want to insert. This is as efficient as it gets, I think, because filesystems don't generally offer true "insertion" in the middle of files.

Answer 3

I'm agreeing with the others, but let me state the solution a bit differently:

1. Get a temp filename (there are OS-specific calls for this)

2. Copy your original file to the temp file (there are now two copies of the same file)

3. Open the original file for "append".

4. "Truncate" it to your insertion point

5. Write your new data

6. Open your temp file for "read"

7. "Seek" to the insertion point (again, the call is OS-specific)

8. Read to end-of-file in temp file; inserting into your original file (still open for "append").

9. Close both files

10. Delete temp file

Answer 4

I'm going to interpret your question broadly to be "how can I implement efficiently a persistent store of an object that supports random-access lookup by index and insertion with expansion." As noted, you could use a simple linear array in the file, but this would only be efficient for lookup (O(1)) and quite inefficient for insertion (O(n)). You could achieve O(log n) for both lookup and insertion by using a tree data structure instead. Maintain one file which acts as an index, and another which acts as the data store and is a series of chunks. Each chunk can be partially full. The index file contains a tree (binary tree or B-tree) where each node corresponds to some contiguous chunk of the array and contains the size of that chunk (so that the root node contains the size of the whole array). For a binary tree, the left and right child nodes contain the size of the left and right halves (approximately) of the array. Finally leaf nodes contain a pointer to a chunk in the data store file that contains the actual data. Insertion now involves changing the 'size' property of 'k' nodes, where 'k' is the height of the tree. When a data store chunk gets too full, split it (allocate a new one by growing the file, or, if you support deletion as well, perhaps from a free list of empty chunks) and rebalance the tree (lots of standard ways of doing this.)

Does this sound complicated? Definitely! Efficient mid-file insertion is more complicated to achieve than is appending.