C既存の内容を上書きせずにバイナリファイルの途中に書き込む

Question

今日の問題は、開始位置のバイナリファイルに数値の配列を書く必要があることです。私はそれが始まるべき位置を持っており、それ以降の値を上書きしたくないだけで、ファイルの開始位置に配列を挿入したいだけです。例：

12345 

のは、2位に456をプッシュしてみましょう：

12456345 

私はおそらく私が自分でそれを実装する必要がありますことを知っているが、私はそれを実装する方法についてのあなたの意見だかを知りたいです可能な限り効率的に

Answer 1

ここでは、多かれ少なかれ、仕事をしていません機能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年7月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より大きいファイルでテストする必要がありますが、64KBよりはるかに小さいBUFFERSIZEでテストすることは賢明でしょう。私は32バイトを使用し、それはOKと思われた）。私は結果を目の当たりにしただけですが、パターンは正しいかどうかを簡単に確認できるように設計されています。コードはlseek()コールのいずれもチェックしません。それは軽微なリスクです。

Answer 2

最初にftruncate()を使用してファイルを最終サイズに拡大します。それから、古いものから新しいものまでのすべてをコピーして、挿入ポイントに戻ります。その後、挿入したいデータで途中の内容を上書きします。ファイルシステムはファイルの真中に真の "挿入"を提供しないので、これは効率的です。

Answer 3

"私は、インデックスによるランダムアクセス検索と拡張による挿入をサポートするオブジェクトの永続ストアを効率的に実装するにはどうすればよいですか？上記のように、ファイル内で単純な線形配列を使うこともできますが、これはルックアップ（O（1））と挿入（O（n））のためには効率が悪いだけです。代わりにツリーデータ構造を使用することで、検索と挿入の両方でO（log n）を達成することができます。索引として機能する1つのファイルと、データ・ストアとして機能し、一連のチャンクである別のファイルを維持します。各チャンクは部分的にいっぱいになることがあります。インデックスファイルにはツリー（バイナリツリーまたはBツリー）が含まれ、各ノードは配列の連続したチャンクに対応し、そのチャンクのサイズを含みます（ルートノードには配列全体のサイズが含まれます）。バイナリツリーの場合、左右の子ノードには、配列の左と右の半分（およそ）のサイズが含まれます。最後にリーフノードには、実際のデータを含むデータストアファイル内のチャンクへのポインタが含まれています。挿入には、kノードの 'size'プロパティを変更する必要があります。ここで、 'k'はツリーの高さです。データストアのチャンクがいっぱいになったら、ファイルを分割して分割します（空きチャンクの空きリストから削除をサポートしている場合はファイルを分割して割り当てます）、ツリーを再調整しますこれは）

この音は複雑ですか？絶対に！効果的な中間ファイルの挿入は、追加するよりも実現が複雑です。

Answer 4

私は他の人と同意、しかし、私は少し違った解決策を述べてみましょうよ：

1. は、一時ファイル名を取得します（このためにOS固有の呼び出しがある）

2. があなたをコピーします元のファイルを一時ファイルにコピーする（同じファイルのコピーが2つあります）

3. "append"の元のファイルを開きます。

5. が

6. を「読み」、再び（挿入ポイントに「シーク」のためのあなたの一時ファイルを開いて、新しいデータを書き込み、あなたの挿入ポイントに

7. それを「切り捨て」呼び出しはOS固有です）

8. 一時ファイル内のファイルの終わりまで読み取ります。元のファイルに挿入します（まだ「追加」するために開きます）。

9. 閉じる両方のファイル

10. 削除一時ファイル