2012-05-06 46 views
6

Vấn đề hôm nay là tôi cần viết một dãy số trong tệp nhị phân ở vị trí bắt đầu. Tôi có vị trí cần bắt đầu, và tôi không muốn ghi đè các giá trị sau đó, chỉ muốn chèn mảng vào vị trí bắt đầu trong tệp. Ví dụ:C ghi ở giữa tệp nhị phân mà không ghi đè bất kỳ nội dung hiện có nào

12345 

Hãy đẩy 456 ở vị trí thứ 2:

12456345 

Tôi biết rằng có lẽ tôi sẽ phải thực hiện nó bằng bản thân mình, nhưng tôi muốn biết ý kiến ​​của bạn về làm thế nào để thực hiện những gì mà hiệu quả nhất có thể.

+0

@ Câu trả lời của John có vẻ như đó là cách duy nhất nhưng nó sẽ liên quan đến rất nhiều việc sao chép các tệp lớn. Vì vậy, nếu có thể, tìm kiếm một cách tiếp cận khác để tuần tự hóa dữ liệu có thể là điều tốt nhất để làm. – gcbenison

+0

@gcbenison, có, tệp nhị phân của tôi có thể là 1GB và quá trình mở rộng sẽ được kích hoạt rất nhiều thời gian nên có thể đây là vấn đề –

+0

Sẽ tốt nhất nếu bạn có thể tránh phải chèn dữ liệu vào giữa tệp bởi vì nó quá tốn kém để làm, gấp đôi so với các tệp có kích thước gigabyte. –

Trả lời

9

Dưới đây là một chức năng extend_file_and_insert() rằng hiện công việc, nhiều hơn hoặc ít hơn.

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

(Lưu ý các dòng bổ sung thêm 2013/07/19; đó là một lỗi mà chỉ hiển thị khi kích thước bộ đệm là nhỏ hơn so với số lượng dữ liệu được sao chép lên các tập tin Nhờ malat cho trỏ. . ra lỗi mã tại thử nghiệm với BUFFERSIZE = 4)

Đây là một số mã kiểm tra quy mô nhỏ:.

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

Nó tạo ra kết quả:

12456345 
1245XxxxxxX6345 
1245XxxxxxX6ZzzzzzzzzzzzzzzzzzzzzzzzZ345 
1245XxxxxxX6ZzzzzzzzzzYyyyyyyyyyyyyyyYzzzzzzzzzzzzzzZ345 

Cần kiểm tra trên một số tệp lớn hơn (tệp lớn hơn BUFFERSIZE, nhưng sẽ rất hợp lý khi thử nghiệm với BUFFERSIZE nhỏ hơn 64 KiB; Tôi đã sử dụng 32 byte và nó có vẻ là OK). Tôi đã chỉ đánh bóng các kết quả nhưng các mẫu được thiết kế để dễ dàng thấy rằng chúng đúng. Mã không kiểm tra bất kỳ lệnh gọi nào trong số các cuộc gọi lseek(); đó là một rủi ro nhỏ.

+1

bạn cần cập nhật read_end_offset – malat

+0

@malat: Có, bạn nói đúng. Khi mã cần làm nhiều hơn một bộ đệm đầy đủ của dữ liệu di chuyển, giá trị của 'read_end_offset' cần phải được giảm đi bởi' bytes_this_time'. Tôi đã mã sửa chữa và thử nghiệm với 'BUFFERSIZE = 4' (cho thấy lỗi trên mã chưa được trộn). Cảm ơn bạn đã chỉ ra lỗi đó. –

5

Trước tiên, sử dụng ftruncate() để phóng to tệp thành kích thước cuối cùng. Sau đó sao chép tất cả mọi thứ từ đầu cuối sang đầu mới, làm việc theo cách của bạn trở lại điểm chèn. Sau đó ghi đè nội dung ở giữa bằng dữ liệu bạn muốn chèn. Điều này là hiệu quả như nó được, tôi nghĩ, bởi vì hệ thống tập tin nói chung không cung cấp đúng "chèn" ở giữa các tập tin.

+0

Đó là một giải pháp tốt đẹp. Tôi biết đó là một câu hỏi ngu ngốc nhưng bạn có thể vui lòng cung cấp một ví dụ hoặc một liên kết đến một câu hỏi hay không? Cảm ơn người đàn ông! –

+3

@FredericoSchardong: Chỉ cần viết nó. Tìm hiểu một hoặc hai điều. –

0

Tôi sẽ diễn giải rộng rãi câu hỏi của bạn là "làm cách nào tôi có thể triển khai hiệu quả lưu trữ liên tục của một đối tượng hỗ trợ tra cứu truy cập ngẫu nhiên bằng chỉ mục và chèn với mở rộng". Như đã lưu ý, bạn có thể sử dụng một mảng tuyến tính đơn giản trong tệp, nhưng điều này sẽ chỉ hiệu quả để tra cứu (O (1)) và không hiệu quả đối với việc chèn (O (n)). Bạn có thể đạt được O (log n) cho cả tra cứu và chèn bằng cách sử dụng cấu trúc dữ liệu cây thay thế. Duy trì một tệp hoạt động như một chỉ mục và một tệp khác hoạt động như kho dữ liệu và là một loạt các khối. Mỗi đoạn có thể một phần đầy. Tệp chỉ mục chứa một cây (cây nhị phân hoặc B-tree) trong đó mỗi nút tương ứng với một số đoạn liền kề của mảng và chứa kích thước của đoạn đó (để nút gốc chứa kích thước của toàn bộ mảng). Đối với cây nhị phân, các nút con trái và phải chứa kích thước của nửa trái và phải (xấp xỉ) của mảng. Cuối cùng các nút lá chứa một con trỏ đến một đoạn trong tệp lưu trữ dữ liệu có chứa dữ liệu thực tế. Chèn bây giờ liên quan đến việc thay đổi thuộc tính 'kích thước' của các nút 'k', trong đó 'k' là chiều cao của cây. Khi một kho lưu trữ dữ liệu bị quá đầy đủ, hãy phân chia nó (cấp phát một tệp mới bằng cách phát triển tệp, hoặc, nếu bạn hỗ trợ xóa, có lẽ từ danh sách trống khối trống) và cân bằng lại cây (nhiều cách tiêu chuẩn để làm) này.)

Âm thanh này có phức tạp không? Chắc chắn rồi! Chèn giữa tệp hiệu quả là phức tạp hơn để đạt được hơn là phụ thêm.

+0

Như đã đề cập trước khi các tệp của tôi có thể tăng lên 1GB, tôi mong đợi hàng nghìn lần chèn giữa. Tôi đã suy nghĩ về việc chia nhỏ tập tin rouge thành những tệp nhỏ trong đó tôi có thể nối thêm nội dung mới vào cuối chúng, sau đó khi tất cả được thực hiện chỉ cần tham gia các tệp nhỏ.Tôi tin rằng không có giải pháp nào hiệu quả hơn việc sử dụng các tệp nhỏ thông qua các hoạt động nối thêm. Bạn nghĩ gì về @gcbenison? –

+0

Bạn có thể giữ một loạt các tệp nhỏ thay vì các đoạn nhỏ trong một tệp lớn, nhưng bạn vẫn cần một số cách lập chỉ mục các khối. Nếu như vậy là chỉ cần dán một nhãn tuần tự trên mỗi một, sau đó chèn trở thành O (n) bởi vì bạn phải cập nhật nhãn của mỗi người. Do đó cách tiếp cận dựa trên cây. – gcbenison

+0

Cập nhật nhãn của từng người? Không cần phải làm thế. –

0

Tôi đồng ý với những người khác, nhưng hãy để tôi nêu rõ giải pháp một chút khác nhau:

  1. Nhận một tên tập tin tạm thời (có những cuộc gọi hệ điều hành cụ thể cho việc này)

  2. Sao chép của bạn tệp gốc vào tệp tạm thời (hiện có hai bản sao của cùng một tệp)

  3. Mở tệp gốc để "nối thêm".

  4. "Truncate" nó đến điểm chèn của bạn

  5. Viết dữ liệu mới của bạn

  6. Mở tập tin tạm thời của bạn cho "đọc"

  7. "Tìm kiếm" để điểm chèn (một lần nữa, cuộc gọi là hệ điều hành cụ thể)

  8. Đọc đến cuối tệp trong tệp tạm thời; chèn vào tệp gốc của bạn (vẫn mở để "nối thêm").

  9. Đóng tất cả các file

  10. Xóa tạm thời tập tin

+0

Cảm ơn bạn đã trả lời, trông cũng tuyệt vời. Tôi thực sự gắn liền với ý tưởng của các tập tin nhỏ vì nó seams là cách mà có số tiền ít hơn của I/O bởi vì sẽ có chỉ là một hoạt động nối thêm cho mỗi "chèn giữa" đề xuất ban đầu. Thay vì tất cả các bạn 10 bước tôi sẽ chỉ có một phụ thêm. Bạn có đồng ý với @ paulsm4? –

Các vấn đề liên quan