9

今日の問題は、数値の配列をバイナリ ファイルの開始位置に書き込む必要があることです。開始位置があり、その後値を上書きしたくありません。ファイルの開始位置に配列を挿入したいだけです。例えば：

12345

位置 2 で 456 をプッシュしましょう:

12456345

おそらく自分で実装する必要があることはわかっていますが、できるだけ効率的に実装する方法についての意見を知りたいです。

4

4 に答える 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 に追加された追加の行に注意してください。これは、ファイルにコピーされるデータの量よりもバッファー サイズが小さい場合にのみ表示されるバグでした。エラーを指摘してくれたmalatBUFFERSIZE = 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

私は他の人に同意しますが、解決策を少し違った方法で述べさせてください。

  1. 一時ファイル名を取得します (これには OS 固有の呼び出しがあります)

  2. 元のファイルを一時ファイルにコピーします (現在、同じファイルの 2 つのコピーがあります)。

  3. 「追加」の元のファイルを開きます。

  4. 挿入ポイントまで「切り捨てる」

  5. 新しいデータを書き込む

  6. 「読み取り」用に一時ファイルを開きます

  7. 挿入ポイントへの「シーク」 (繰り返しますが、呼び出しは OS 固有です)

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

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

  10. 一時ファイルを削除

于 2012-05-06T04:20:41.637 に答える
0

あなたの質問を広く解釈して、「インデックスによるランダム アクセス ルックアップと展開による挿入をサポートするオブジェクトの永続ストアを効率的に実装するにはどうすればよいか」ということになります。前述のように、ファイルで単純な線形配列を使用できますが、これはルックアップ (O(1)) に対してのみ効率的であり、挿入 (O(n)) に対しては非常に非効率的です。代わりにツリー データ構造を使用することで、ルックアップと挿入の両方で O(log n) を実現できます。インデックスとして機能する 1 つのファイルと、データ ストアとして機能し、一連のチャンクである別のファイルを維持します。各チャンクは部分的にいっぱいになる可能性があります。インデックス ファイルには、各ノードが配列の連続したチャンクに対応するツリー (バイナリ ツリーまたは B ツリー) が含まれ、そのチャンクのサイズが含まれます (ルート ノードに配列全体のサイズが含まれるように)。二分木の場合、左と右の子ノードには、配列の左半分と右半分のサイズ (概算) が含まれます。最後に、リーフ ノードには、実際のデータを含むデータ ストア ファイル内のチャンクへのポインターが含まれます。挿入には、'k' ノードの 'size' プロパティの変更が必要になりました。ここで、'k' はツリーの高さです。データ ストア チャンクがいっぱいになった場合は、それを分割し (ファイルを大きくして新しいチャンクを割り当てるか、削除をサポートしている場合は、おそらく空のチャンクの空きリストから)、ツリーのバランスを取り直します (多くの標準的な方法で行います)。これ。）k' は木の高さです。データ ストア チャンクがいっぱいになった場合は、それを分割し (ファイルを大きくして新しいチャンクを割り当てるか、削除をサポートしている場合は、おそらく空のチャンクの空きリストから)、ツリーのバランスを取り直します (多くの標準的な方法で行います)。これ。）k' は木の高さです。データ ストア チャンクがいっぱいになった場合は、それを分割し (ファイルを大きくして新しいチャンクを割り当てるか、削除をサポートしている場合は、おそらく空のチャンクの空きリストから)、ツリーのバランスを取り直します (多くの標準的な方法で行います)。これ。）

これは複雑に聞こえますか？絶対！効率的な中間ファイル挿入は、追加よりも達成が複雑です。

于 2012-05-06T04:13:04.443 に答える