Tuần Tự Hóa Dữ Liệu Trong Ngôn Ngữ Lập Trình C
Chuỗi hóa dữ liệu trong ngôn ngữ C
Chuỗi hóa cấu trúc dữ liệu luôn là một công cụ vô cùng hữu ích. Những ngày qua, khi sửa đổi lại mô-đun quản lý tài nguyên cũ, tôi đã gặp lại vài module con xử lý file dữ liệu được thiết kế từ trước. Việc chỉnh sửa chúng khiến tôi phát bực, từ đó thôi thúc tôi suy nghĩ lại toàn bộ phương án chuỗi hóa.
Các ngôn ngữ như Java hay .NET nhờ có hệ thống thông tin kiểu dữ liệu toàn diện nên được trang bị giải pháp chuỗi hóa hoàn chỉnh. Ngôn ngữ C++ lại có điểm yếu trong thiết kế khi thiếu hỗ trợ bản địa cho tính năng này, dẫn đến việc không có giải pháp nào được cộng đồng chấp nhận rộng rãi.
Hầu hết các thư viện serial hiện có cho C++ đều mang hơi hướng cách làm của MFC từ hai thập kỷ trước. Về sau, boost cung cấp một giải pháp nhìn có vẻ toàn diện hơn (boost.serialization). Tính “toàn diện” ở đây chủ yếu chỉ yếu tố phi xâm nhập (non-intrusive). Giải pháp của boost mang lại cảm giác hiện đại hơn, giao diện trực quan hơn. Nó tạo cho người dùng ảo giác rằng: “Chỉ cần vài thao tác đơn giản, những class vốn không hỗ trợ serial nay đã có thể sử dụng tính năng này!” Nói cách khác, việc “làm được” quan trọng hơn việc “giải quyết hậu quả phát sinh”.
Thực lòng mà nói, tôi không thích sử dụng những đoạn code được xây dựng từ hàng tá macro phức tạp (hay những viên ngọc trí tuệ cao độ nào đó?), dù đó là công sức của ai. Hơn nữa, tôi cần một giải pháp thuần C thay vì C++.
Từ hôm qua, tôi đã dành thời gian để giải quyết vấn đề này.
Vấn đề cốt lõi nằm ở chỗ C/C++ không cung cấp thông tin kiểu dữ liệu meta. Vậy tại sao không tự xây dựng meta thông tin từ gốc rễ?
Tôi từ chối dùng macro kỳ quái hay kỹ thuật template hiện đại (một lão lập trình viên C bảo thủ như tôi không cần đến những thứ đó!). Giải pháp đơn giản là tự định nghĩa một “ngôn ngữ nhỏ” để mô tả cấu trúc C, viết một chương trình nhỏ để phân tích cú pháp, rồi dùng nó sinh ra file .h chứa metadata phục vụ thư viện serial.
Nếu tạm thời chưa xét đến việc mở rộng cho các ngôn ngữ động phân tích dữ liệu serial, thực tế chỉ cần xử lý hai kiểu dữ liệu cơ bản:
- Kiểu giá trị nguyên thủy (primitive value)
- Kiểu tham chiếu đến các đối tượng khác
Với kiểu giá trị, ta chỉ cần sao chép vùng nhớ tương ứng với độ dài đã biết.
Còn tham chiếu trong bộ nhớ là con trỏ, khi serial sẽ chuyển thành độ lệch (offset) tương đối trong khối dữ liệu. Tôi dùng cơ số 1 (base 1) để cho phép giá trị 0 đại diện cho tham chiếu null.
Tôi chia tham chiếu thành hai loại: ngoại tham chiếu (external reference) và nội tham chiếu (internal
Ngoại tham chiếu trỏ đến các khối dữ liệu không cần serial. Thư viện sẽ chuyển chúng thành các “nguyên tử” (atoms) - thường là chuỗi duy nhất. Khi giải nén, các nguyên tử này sẽ được khôi phục thành tham chiếu gốc. Ví dụ: tệp tin hoặc handle cửa sổ có thể được ánh xạ thành nguyên tử chứa tên tệp hoặc tiêu đề cửa sổ tương ứng (tùy cách triển khai).
Nội tham chiếu trỏ đến các đối tượng cũng thuộc phạm vi serial. Dữ liệu được tham chiếu phải được đưa vào cùng khối serial. Nếu xử lý tốt quan hệ nội tham chiếu, các đối tượng sẽ độc lập với địa chỉ bộ nhớ.
Yêu cầu quan trọng của tôi là thư viện phải hợp nhất (merge) các khối dữ liệu giống nhau. Ví dụ: khi serial một cây, các nút lá có giá trị trùng nhau hoặc các cây con giống hệt nhau chỉ nên xuất hiện một lần duy nhất. Ngoài ra, thư viện phải xử lý được cấu trúc vòng (cyclic structures) như danh sách liên kết vòng hay đồ thị có hướng phức tạp.
Về độ phức tạp thời gian, tôi chấp nhận giới hạn đa thức. Việc hợp nhất đồ thị vòng có cấu trúc topo giống nhau sẽ bị bỏ qua dù về mặt lý thuyết có thể thực hiện được.
Với hai yêu cầu trên, các thư viện sẵn có như ProtoBuf không còn phù hợp.
Một yêu cầu nhỏ nữa: độ dài mảng có thể thay đổi, được xác định bởi một biến nguyên trong cùng cấu trúc.
Tôi đã hoàn thành phiên bản thử nghiệm trong vòng một ngày một đêm. Việc định nghĩa và xử lý meta thông tin không quá phức tạp. Giao diện thư viện rất đơn giản: chỉ cần truyền con trỏ dữ liệu, thông tin meta kiểu dữ liệu, thư viện sẽ tự động điền vào khối dữ liệu đầu ra. Về bản chất, đối tượng serial là một đồ thị có hướng có thể chứa vòng. Thách thức lớn nhất nằm ở việc hợp nhất các nút giống nhau.
Ban đầu, tôi dùng thuật toán “ngây thơ” nhất: không hợp nhất nút ngay từ đầu. Sau khi duyệt toàn bộ đồ thị, tính hash từng nút, sắp xếp và loại bỏ bản trùng, rồi sửa lại các th