Cấu trúc dữ liệu generic an toàn kiểu trong ngôn ngữ C

Lập trình viên C thường phải đối mặt với một bài toán nan giải: làm sao để viết các cấu trúc dữ liệu tổng quát (generic) mà vẫn đảm bảo an toàn kiểu dữ liệu (type safety)? Trong một bài viết kỹ thuật gần đây được chia sẻ rộng rãi trên Hacker News, tác giả Daniel Chase Hooper đã trình bày một kỹ thuật thú vị sử dụng union để giải quyết vấn đề này — một cách tiếp cận mà theo ông là chưa từng thấy ở nơi khác.

Vấn đề với các phương pháp truyền thống

C có hai cách phổ biến để xây dựng cấu trúc dữ liệu generic, nhưng cả hai đều có nhược điểm đáng kể.

Cách thứ nhất là viết cấu trúc dữ liệu trong file header bằng macro, sau đó #include file đó nhiều lần — mỗi lần cho một kiểu dữ liệu khác nhau. Phương pháp này đảm bảo an toàn kiểu nhưng tỏ ra cồng kềnh và khó bảo trì khi số lượng kiểu tăng lên.

Cách thứ hai là sử dụng con trỏ void *. Cách này linh hoạt hơn nhưng hoàn toàn không an toàn về kiểu — trình biên dịch sẽ không phát hiện nếu bạn vô tình truyền sai kiểu dữ liệu, dẫn đến lỗi runtime khó truy vết.

Cải thiện bộ nhớ với Flexible Array Member

Một trong những vấn đề của cách tiếp cận void * là mỗi node trong danh sách liên kết cần hai lần cấp phát bộ nhớ (một cho bản thân node, một cho dữ liệu trỏ tới), gây lãng phí và làm tăng khả năng cache miss khi duyệt danh sách.

Tác giả giải quyết bằng cách sử dụng Flexible Array Member — một tính năng của C cho phép lưu trữ dữ liệu trực tiếp bên trong node:

typedef struct ListNode {
    struct ListNode *next;
    unsigned char data[];
} ListNode;

Nhờ đó, con trỏ next và dữ liệu thực tế nằm cạnh nhau trong bộ nhớ, giảm số lần cấp phát xuống còn một và cải thiện đáng kể hiệu năng truy cập.

Điểm cốt lõi: Union để kiểm tra kiểu

Phần thú vị nhất của bài viết là kỹ thuật dùng union với thành viên payload có kiểu tham số hóa. Ý tưởng là tạo ra một union chứa thông tin kiểu chỉ tồn tại ở thời điểm biên dịch:

#define List(T) union { \
    struct { ListNode *head; } list; \
    T *payload; \
}

Điểm mấu chốt là payload không bao giờ được dùng ở runtime — nó chỉ tồn tại để mang thông tin kiểu cho trình biên dịch. Vì là union, payload không tiêu tốn thêm bộ nhớ nào.

Tiếp theo, tác giả sử dụng toán tử ba ngôi (ternary operator) để buộc trình biên dịch kiểm tra rằng phần tử được thêm vào phải cùng kiểu với payload của danh sách. Nếu không khớp, Clang sẽ báo lỗi ngay tại thời điểm biên dịch.

Sử dụng typeof để trả về đúng kiểu

Đối với các hàm generic cần trả về con trỏ tới dữ liệu bên trong, tác giả sử dụng __typeof__() để ép kiểu từ void * sang kiểu payload của cấu trúc dữ liệu:

#define list_prepend(list, item) \
    _list_prepend(&(list), (void*)(__typeof__((list).payload))(item))

Đáng chú ý, __typeof__() từng là phần mở rộng tùy chọn nhưng đã trở thành một phần của tiêu chuẩn C23. Trong khi Clang và GCC đã hỗ trợ từ lâu, MSVC chỉ bắt đầu hỗ trợ từ phiên bản 19.39.

Một lưu ý về typedef

Tác giả cũng chỉ ra một điểm thú vị: trình biên dịch C không coi hai biến có định nghĩa kiểu giống hệt nhau là cùng kiểu, nếu chúng được định nghĩa riêng biệt. Giải pháp là dùng typedef:

typedef struct { int a; int b; } MyType;

MyType x;
MyType y; // Cùng kiểu nhờ typedef

Điều này đặc biệt quan trọng với các cấu trúc dữ liệu phức tạp như hash map, nơi có nhiều kiểu liên kết với nhau.

So sánh với các thư viện hiện có

Tác giả cũng so sánh kỹ thuật của mình với stb_ds.h — một thư viện cấu trúc dữ liệu generic phổ biến. Theo ông, stb_ds.h tuy an toàn kiểu nhưng chỉ hoạt động được vì mảng và map của nó được triển khai dựa trên mảng C thuần. Trình biên dịch chỉ bắt lỗi kiểu khi gán vào mảng C đó, không phải tại thời điểm truyền giá trị vào các hàm generic — nghĩa là một số lỗi kiểu vẫn có thể lọt qua.

Kỹ thuật union được trình bày trong bài viết có phạm vi áp dụng tổng quát hơn, hoạt động với mọi loại cấu trúc dữ liệu: mảng, danh sách liên kết, cây nhị phân, hash map...

Ý nghĩa với lập trình viên Việt Nam

Với cộng đồng lập trình viên C tại Việt Nam — đặc biệt những người làm việc trong lĩnh vực nhúng, hệ thống nhúng, IoT và phát triển firmware — kỹ thuật này mở ra hướng tiếp cận mới để viết code an toàn hơn mà không phải chuyển sang C++ hay Rust. Việc tận dụng sức mạnh của trình biên dịch để bắt lỗi sớm luôn là thực hành tốt, giúp giảm thiểu bug trong các dự án lớn và tăng độ tin cậy của sản phẩm.

Tác giả cũng đề cập đến một bài viết tiếp theo về "Mảng mở rộng nhanh với con trỏ ổn định trong C" — hứa hẹn tiếp tục khai thác sâu hơn các kỹ thuật lập trình C hiện đại.