Cách viết cấu trúc dữ liệu an toàn kiểu (generic) trong C

 (danielchasehooper.com)
3 điểm bởi GN⁺ 2025-07-01 | 2 bình luận | Chia sẻ qua WhatsApp
  • Bài viết này giải thích một phương pháp mới để tạo cấu trúc dữ liệu an toàn kiểu (generic) trong ngôn ngữ C
  • Bài viết minh họa bằng cách triển khai linked list, với kỹ thuật liên kết thông tin kiểu với cấu trúc dữ liệu bằng union
  • So sánh điểm khác biệt và nhược điểm của từng cách tiếp cận hiện có trong các mẫu generic của C (macro, con trỏ void, Flexible Array Member)
  • Có thể kiểm tra kiểu tại thời điểm biên dịch, giúp ngăn chặn việc dùng sai kiểu từ sớm
  • Kỹ thuật mới cung cấp giao diện hàm/cấu trúc dữ liệu rõ ràng và nhất quán như foo_list

Giới thiệu

  • Giới thiệu cách tạo cấu trúc dữ liệu generic trong C với tính an toàn kiểu
  • Kỹ thuật này dùng union để gắn thông tin kiểu với cấu trúc dữ liệu tại thời điểm biên dịch
  • Có thể áp dụng cho mọi cấu trúc dữ liệu như map, mảng, cây nhị phân..., và bài viết giải thích thông qua ví dụ triển khai linked list cơ bản
  • Vì nhiều lập trình viên nghĩ rằng generic là bất khả thi trong C, bài viết trình bày dễ hiểu theo từng bước

Generic truyền thống dựa trên macro

  • Cách triển khai cấu trúc dữ liệu generic truyền thống trong C là dùng macro để sinh tên struct, hàm và kiểu
  • Có thể mở rộng bằng cách include cùng một header cấu trúc dữ liệu nhiều lần cho nhiều kiểu khác nhau

Ví dụ:

  • Dùng macro (ví dụ: CONCAT, NODE_TYPE, PREPEND_FUNC) để tạo tên struct và tên hàm phù hợp với từng kiểu
  • Hàm và struct được tạo riêng cho từng kiểu, nên với mỗi kiểu như int hay Foo sẽ có định nghĩa cấu trúc dữ liệu riêng

Nhược điểm:

  • Khó xác định vị trí định nghĩa kiểu và hàm (vì được tạo ra bằng macro nên khó lần theo)
  • Khó tận dụng tính năng tự động hoàn thành mã
  • Việc tạo nhiều phiên bản của cùng một hàm làm tăng kích thước binary và thời gian build
  • Tên hàm cần tiền tố kiểu (ví dụ: Foo_list_prepend)

Generic bước 1: cách dùng con trỏ void

  • Đặt kiểu dữ liệu của cấu trúc dữ liệu là void * để tách khỏi kiểu cụ thể
  • Khai báo trường data của linked list là void *
  • Không thể kiểm tra kiểu, nên lỗi kiểu có thể phát sinh lúc runtime; độ an toàn tại thời điểm biên dịch thấp
  • Kém hiệu quả về bộ nhớ và cache: node và dữ liệu được cấp phát riêng, làm tăng overhead không cần thiết và số lần cache miss

Generic bước 2: lưu trữ inline (Flexible Array Member)

  • Dùng Flexible Array Member (thành viên mảng linh hoạt) để lưu trực tiếp dữ liệu trong node thay vì lưu con trỏ
  • Mỗi node chỉ cần một lần cấp phát, đồng thời dữ liệu và con trỏ next nằm gần nhau trong cache
  • Cách này cần truyền thông tin kích thước và dùng memcpy, nhưng cải thiện hiệu năng nhờ bố cục bộ nhớ nhất quán
  • Nếu dùng hàm list_alloc_front thì có thể khởi tạo trực tiếp struct mà không cần memcpy

Generic bước 3: triển khai kiểm tra kiểu

  • Khai báo con trỏ kiểu được tham số hóa trong thành viên payload của union để thêm thông tin kiểu vào cấu trúc dữ liệu tại thời điểm biên dịch
  • Ví dụ: #define List(type) union { ListNode *head; type *payload; }
  • Cách này cho phép lấy kiểu của list tương ứng bằng __typeof__(foo_list.payload)
  • Trong macro (list_prepend), có thể ép kiểu hàm để chỉ biên dịch được khi kiểu là hợp lệ
  • Nếu dùng sai kiểu, lỗi sẽ xuất hiện ngay lúc biên dịch

Ví dụ lỗi:

  • Khi thêm int vào foo_list, trình biên dịch sẽ báo lỗi 'incompatible integer to pointer conversion'

Hỗ trợ cho trình biên dịch không có typeof

  • Trước C23, __typeof__ chưa phải chuẩn, nên một số trình biên dịch (ví dụ: MSVC cũ) sẽ không hỗ trợ
  • Có thể đạt hiệu quả tương tự bằng các cách обход, chẳng hạn tận dụng thành viên payload trong struct

Truyền tham số và typedef

  • Ngay cả khi cùng có dạng List(Foo), trình biên dịch vẫn xem chúng là các kiểu khác nhau
  • Khi dùng typedef, việc truyền tham số và gán giá trị sẽ trơn tru hơn

Ví dụ:

  • typedef List(Foo) ListFoo;
  • Có thể khai báo biến ListFoo và dùng nó làm tham số hàm

Kết thúc và mở rộng sang nhiều cấu trúc dữ liệu

  • Kỹ thuật này cũng có thể áp dụng cho các cấu trúc dữ liệu cần nhiều tham số kiểu (ví dụ: hash map)
  • Có thể dùng union để đảm bảo an toàn kiểu riêng cho key và value
  • Để xem thêm phần thực hành chi tiết và phần cài đặt macro, tham khảo liên kết gist mã nguồn liên quan

Kết luận

  • Cách tiếp cận mới khắc phục các nhược điểm của phương pháp cũ (khả năng đọc, hiệu quả build, khả năng bảo trì), đồng thời mang lại quy ước đặt tên hàm nhất quán và tính an toàn kiểu
  • Dễ hỗ trợ nhiều cấu trúc dữ liệu và nhiều tham số kiểu
  • Thông qua kiểm tra kiểu tại thời điểm biên dịch, có thể đồng thời đảm bảo tính an toàn và hiệu quả khi dùng cấu trúc dữ liệu generic

Lời cảm ơn

  • Bài viết này được hoàn thiện nhờ phản hồi và sự động viên từ Martin Fouilleul

Bài viết liên quan

2 bình luận

 
click 2025-07-01

Tôi cũng có chút thắc mắc là chẳng phải chỉ cần dùng Zig một cách đơn giản là được sao?
 
GN⁺ 2025-07-01
Ý kiến trên Hacker News

  • Có ý kiến chỉ ra rằng ở mã bước 2, cách dùng uint64_t data[]; không phù hợp với các kiểu có yêu cầu căn chỉnh lớn hơn uint64_t, và ngược lại lại lãng phí không cần thiết với các kiểu nhỏ hơn; ví dụ trên ABI ilp32 của kiến trúc 64-bit thì còn rắc rối hơn. Với mã bước 3, có ý kiến cho rằng nên viết int main() { List(Foo) foo_list = {NULL}; như vậy. Khi không có typeof thì không thể trả về giá trị, còn với mã thay thế thì có thể phát sinh lỗi liên quan đến const, và do tính đối xứng của toán tử == nên vấn đề này càng lộ rõ. Nếu bỏ payload thì sẽ không còn thông tin kích thước nên không an toàn; ví dụ thêm int32_t vào List(int64_t) thoạt nhìn có vẻ ổn nhưng thực tế không thể xác định kích thước của int32_t. Muốn an toàn hơn thì cần bổ sung thêm. Người này cho rằng có hai giới hạn lớn khi dùng generic trong C: thứ nhất là cách ủy quyền qua vtable bị hạn chế chức năng vì struct không thể chứa macro; thứ hai là khi ủy quyền qua vtable bên ngoài thì phải khai báo trước toàn bộ các kiểu sẽ dùng. Cách tốt nhất là chỉ khai báo các hàm tĩnh trong header có chứa khai báo typedef, nhưng GCC và Clang lại khác nhau ở thời điểm đưa ra cảnh báo undefined static. Cuối cùng họ nêu ví dụ thiết kế hàm nhận các struct buffer khác nhau để nhấn mạnh rằng cần quản lý đầy đủ cả các phiên bản const

    • Về vấn đề ủy quyền qua vtable bên ngoài, có người chia sẻ rằng trong một dự án cũ họ đã phải tự làm cả compiler để giải quyết chuyện này. Khi bắt đầu dự án Apache Clownfish, họ parse file .h rồi cuối cùng tạo ra luôn một định dạng riêng là header Clownfish (.cfh). Họ đưa ví dụ mã thật gọi phương thức "Clone" của obj, và kể lại trải nghiệm phải sinh hàng loạt đoạn mã quá tay như vậy để phục vụ binding cho ngôn ngữ động cần tính năng hướng đối tượng. Mục tiêu của Clownfish là cung cấp mô hình đối tượng mẫu số chung thấp nhất, và cả kiểu của ngôn ngữ binding cũng được sinh từ .cfh. Họ nói thêm rằng chính vì sự phức tạp này mà đa số cuối cùng đành từ bỏ tính an toàn kiểu bằng cách cast void*. https://github.com/apache/lucy-clownfish

    • Về int main(), có người nhấn mạnh rằng trong C, int main() có nghĩa là số lượng đối số chưa xác định. Phải khai báo int main(void) thì mới có nghĩa là không có đối số. Đây là điều nhiều người viết C++ hay quên

    • Có ý kiến mong rằng union thực sự có thể được “hợp nhất”, tức là một kiểu có thể tự khai báo mình là một phần trong union của kiểu khác

    • Có người chỉ ra rằng khi malloc, do vấn đề padding nội bộ nên kích thước tính ra có thể nhỏ hơn thực tế; ví dụ khi làm malloc(sizeof(*node) + data_size); thì có thể nguy hiểm

  • Có người phản bác nội dung mẹo #0, nói rằng khi tự xây cả một phương ngữ C họ đã dùng chính mẹo này. Họ chia sẻ ví dụ mã hiện thực generic binary heap https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. Cú pháp hơi nặng, nhưng kết quả cuối cùng vẫn là một struct C thông thường nên rất có lợi về tối ưu hóa và tính dễ dự đoán. Theo họ, ở các cách hiện thực khác thì void*, định cỡ bộ nhớ lúc chạy và định nghĩa macro là điều khó tránh

    • Với tư cách tác giả, người viết giải thích rằng binary heap và linked list phục vụ mục đích khác nhau. Binary heap cần đọc dữ liệu khi lưu nên cách tiếp cận khác đi, và khi viết generic binary heap thì lựa chọn cũng có thể khác. Họ nói thêm là phần chú thích cuối bài cũng đã nhắc đến điều này

    • Có người nêu nhiều lý do thích cách hiện thực trong header. Khi debug thì dễ lần theo mã và tận dụng thông tin kiểu hơn so với hàm macro. Compiler có thể tối ưu monomorphized cho từng instance nên không có chi phí runtime hay gánh nặng kích thước biến đổi. Có thể đặt struct generic trên stack. Hai vấn đề mà tác giả nêu cũng có thể lách được: có thể dễ dàng đổi tên bằng macro tên hàm, và cũng có thể dùng weak symbol để khi liên kết thì các định nghĩa trùng tự động được gộp lại. Với container generic cho kiểu con trỏ thì lại có vấn đề khác, nhưng vẫn có thể xử lý bằng typedef v.v. Người này cho rằng intrusive data structure trong C vẫn tiện, dù debug thì khó hơn

    • Câu "compiler ngấu nghiến nó như ăn donut" khiến họ cười lớn

  • Có ý kiến nói rằng khi chuyển đổi kiểu hàm, ví dụ giả định biểu diễn nội bộ của Foo* và void* là giống nhau, thì chuẩn C không hề bảo đảm điều đó. Trong tình huống không có tính tương thích kiểu ("compatible"), kiểu cast như vậy có thể dẫn đến hành vi không xác định. Compiler cũng có thể bị ảnh hưởng trong các phân tích như alias analysis, v.v. (kèm liên kết tham khảo) https://news.ycombinator.com/item?id=44421185

    • Tác giả trả lời rằng điều này đã được nhắc trong chú thích cuối bài, và việc cast không phải là cốt lõi của tính an toàn kiểu. Họ khuyên nên đọc toàn bộ bài viết

  • Có người hỏi: "Nếu phải làm đủ trò như vậy để có generics trong C, sao không dùng luôn C++?"

    • Có người chia sẻ kinh nghiệm rằng vì tiêu chuẩn an toàn và các yêu cầu khác nên nhiều dự án legacy không thể lập tức chuyển sang C++. Với dự án mới thì họ đặt chuẩn và đưa C++ vào, nhưng với dự án cũ thì trong một thời gian vẫn phải giữ C. Họ cho rằng góc nhìn kiểu "cứ dùng C++ đi" nên cảm thông hơn với bối cảnh thực tế

    • Trên thực tế, ở nơi đang dùng C, việc chuyển sang C++ có thể còn phức tạp hơn và gây ra nhiều vấn đề hơn

    • Ngược lại, cũng có quan điểm cho rằng chỉ cần bỏ ra chút công là có thể đạt cùng kết quả ngay trong C, nên không nhất thiết phải đi tới C++

  • Có người giới thiệu cách làm đang được dùng thực tế trong nhân Linux: nhúng struct list_head chứa thông tin danh sách vào trong struct riêng của từng kiểu. Họ kèm liên kết tham khảo https://kernelnewbies.org/FAQ/LinkedLists

    • Có người thấy tên macro LIST_HEAD_INIT và INIT_LIST_HEAD trong nhân Linux không thật sự trực quan

  • Có người chỉ ra rằng trong mã ở phần "typeof on old compilers", dòng (list)->payload = (item); thực ra không phải no-op mà sẽ khiến head của list bị ghi đè bằng item. Nếu muốn đúng hành vi dự kiến thì nên bọc trong if(0)

    • Có người nói rằng trong ví dụ, union đã bị đổi thành struct, và điều này cũng có vẻ lãng phí. Xử lý trong if(0) có vẻ tốt hơn

  • Có người cho thấy trong ngôn ngữ D, kiểu generic list như vậy đơn giản hơn nhiều, và ví preprocessor của C như đóng đinh bằng búa vào móng tay, còn dùng nail gun thì vừa nhanh vừa gọn hơn, để nhấn mạnh sự bất tiện của macro C

    • Có người đáp lại rằng bài đăng này nói về C, và trong một số dự án thì bắt buộc phải dùng C

  • Có người thấy ý tưởng dùng union và typeof() rất thú vị. Với trường hợp của họ, khi làm data structure intrusive thì cuối cùng vẫn cần wrapper bọc trong các macro lớn; họ đặt câu hỏi liệu union và typeof có thể dùng để hiện thực kiểu này không. Họ chia sẻ ví dụ mã wrapper cho hash table cùng tài liệu https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

  • Có người chia sẻ rằng cá nhân họ đã dùng kỹ thuật này trong một thư viện thử nghiệm https://github.com/uecker/noplate/blob/main/src/list.h

    • Có người hỏi xin ý tưởng về struct intrusive, tức là cách nhúng cấu trúc node vào dữ liệu để một đối tượng có thể đồng thời thuộc nhiều container

  • Có ý kiến cho rằng cốt lõi là tận dụng kiểu của con trỏ hàm để đảm bảo an toàn kiểu, thay vì dùng kiểu handle như cách thường thấy. Trong chuẩn C23, vấn đề tương thích kiểu đã được cải thiện, và họ chia sẻ tài liệu chuẩn cùng tình hình hỗ trợ trên GCC/Clang mới nhất https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

    • Tác giả trả lời rằng ý tưởng cốt lõi là dùng union để gắn thông tin kiểu vào kiểu dữ liệu generic; ép kiểu hàm không phải là con đường duy nhất, và họ đã bàn đến nhiều phương án khác, kể cả trong footnote và phần "typeof on old compilers"