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

 (danielchasehooper.com)
3 điểm bởi GN⁺ 2025-07-01 | 2 bình luận | Chia sẻ qua WhatsApp
  • Ngay cả trong C, bằng cách kết hợp macro, void *, flexible array member và union, ta có thể tạo cấu trúc dữ liệu generic an toàn kiểu; ví dụ minh họa cách triển khai từng bước bằng danh sách liên kết
  • Cách include header theo từng kiểu nhiều lần thì an toàn, nhưng do mã sinh ra bằng macro nên khó truy vết định nghĩa và hoàn thiện mã, đồng thời có thể làm tăng kích thước binary và thời gian build
  • Danh sách dựa trên void * có tính tổng quát, nhưng không ngăn được lỗi kiểu; nếu cấp phát node và dữ liệu riêng, có thể phát sinh 2 lần cấp phát cho mỗi node và cache miss
  • Nếu lưu dữ liệu bên trong node bằng flexible array member và bọc List(type) bằng union, có thể gắn thông tin kiểu tại thời điểm biên dịch mà không tốn chi phí runtime
  • Macro list_prepend dùng toán tử ba ngôi để khớp kiểu giữa giá trị truyền vào và payload, qua đó buộc lỗi biên dịch; với kiểu con trỏ trả về có thể tận dụng __typeof__()

Điểm xuất phát của triển khai generic trong C

  • Mục tiêu là khai báo danh sách theo từng kiểu như List(int), List(Foo) trong C, và khiến mã không biên dịch được nếu đưa vào sai kiểu
  • Trong ví dụ, có thể đưa giá trị Foo vào List(Foo), nhưng mã đưa kiểu khác như list_prepend(&foo_list, 7) sẽ không biên dịch
  • Bên trong list_for(item, &foo_list), item có thể được xử lý như kiểu Foo *

Cấp 0: Cách dùng header generic

  • Một cách là viết cấu trúc dữ liệu trong header, rồi thay đổi macro kiểu T và thực hiện #include nhiều lần
  • list.h dựa trên T để sinh ra bằng macro các kiểu và hàm như FooListNode, Foo_list_prepend
  • Cách này generic và an toàn kiểu, nhưng trải nghiệm sử dụng khá thô
    • Kiểu và hàm được cấu thành bằng macro nên khó tìm vị trí định nghĩa
    • Tính năng hoàn thiện mã có thể không hoạt động tốt
    • Các bản sao của cùng một hàm được tạo theo từng kiểu, làm tăng kích thước binary và thời gian build
    • Thay vì chỉ dùng một list_prepend(), phải dùng các hàm có tiền tố kiểu như Foo_list_prepend(), int_list_prepend()
  • Với các hàm generic cần sinh mã theo từng kiểu, cách này có thể phù hợp hơn

Cấp 1: Danh sách dựa trên void *

  • Nếu ListNode có void *data, nó có thể chứa dữ liệu thuộc nhiều kiểu
  • list_prepend(ListNode **head, void *data) lưu nguyên con trỏ dữ liệu, nên triển khai đơn giản
  • Vấn đề là cấu trúc này không an toàn kiểu
  • Nếu node và dữ liệu được cấp phát riêng, chi phí bộ nhớ và hiệu năng cũng tăng
    • Cần hai lần cấp phát cho một node
    • Bản thân con trỏ data dùng thêm bộ nhớ
    • Khi duyệt danh sách, có thể xảy ra cache miss ở cả lúc truy cập node kế tiếp và lúc truy cập dữ liệu
  • Mã ví dụ dùng malloc vì quen thuộc, nhưng trên thực tế nên dùng Arena; có thể tham khảo tài liệu liên quan là video và bài viết

Cấp 2: Lưu dữ liệu bên trong node

  • Thay vì void *data, có thể dùng Flexible Array Member để đặt dữ liệu bên trong node
  • struct ListNode có ListNode *next và char data[]; khi cấp phát, lấy một lần lượng bộ nhớ bằng sizeof(* node) + data_size
  • list_prepend nhận dữ liệu và kích thước được truyền vào, rồi sao chép vào node->data bằng memcpy
  • Cách này đặt next và dữ liệu thực tế gần nhau trong bộ nhớ, giảm vấn đề cấp phát và cache của cách dùng void *
  • Đổi lại, caller phải truyền data_size
  • Nếu muốn tránh memcpy, có thể để list_alloc_front trả về con trỏ tới vùng dữ liệu của node, rồi caller trực tiếp khởi tạo vùng nhớ đó
  • Các vấn đề về căn chỉnh, padding và tính toán kích thước của member data là chủ đề riêng nên không được đi sâu trong ví dụ

Cấp 3: Gắn thông tin kiểu bằng union

  • Kỹ thuật cốt lõi là định nghĩa List(type) dưới dạng union, đặt chung head thật của danh sách và con trỏ dùng cho thông tin kiểu
#define List(type) union { \
    ListNode *head; \
    type *payload; \
}
  • payload không được dùng ở runtime mà cung cấp thông tin kiểu tại thời điểm biên dịch
  • Vì dùng union, payload không tiêu tốn thêm bộ nhớ riêng
  • Có thể tạo danh sách theo từng kiểu như List(Foo) foo_list, List(int) int_list

Kiểm tra kiểu bằng toán tử ba ngôi

  • Macro list_prepend gọi hàm nội bộ _list_prepend, đồng thời dùng toán tử ba ngôi để khớp kiểu của item với (list)->payload
#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
                  (1 ? (item) : (list)->payload), \
                  sizeof(*(list)->payload))
  • Nếu hai kiểu ứng viên của toán tử ba ngôi không khớp, compiler sẽ báo lỗi không tương thích kiểu
  • Ví dụ, nếu truyền Bar * vào List(Foo), Clang sẽ hiển thị lỗi không khớp kiểu con trỏ giữa Foo * và Bar *
  • Cùng macro đó cũng tự động truyền kích thước của kiểu lưu trữ bằng sizeof(*(list)->payload)
  • Công việc thực sự do hàm nội bộ generic như _list_prepend(ListNode **head, void *data, size_t data_size) đảm nhiệm

Dùng __typeof__() cho kiểu trả về

  • Khi hàm generic cần trả về con trỏ dữ liệu bên trong, có thể dùng __typeof__() để ép kiểu giá trị trả về void * sang kiểu của payload
#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))
  • __typeof__() được hỗ trợ trong Clang, GCC và MSVC 19.39 trở lên
  • __typeof__() từng là extension tùy chọn trước khi được đưa vào tiêu chuẩn C23
  • Với các compiler không có __typeof__(), chẳng hạn MSVC trước 19.39, có thể dùng kiểm tra kiểu dựa trên toán tử ba ngôi
  • Việc trả về an toàn kiểu cũng có thể thực hiện bằng cách cấp phát thông qua payload, nhưng phần triển khai chi tiết được lược bỏ

Cách cũ và lưu ý về định nghĩa

  • Cách trước đây là ép _list_prepend sang kiểu con trỏ hàm có chứa __typeof__((list)->payload) rồi gọi
  • Việc gọi con trỏ hàm đã bị ép kiểu về mặt kỹ thuật là hành vi không xác định, nhưng bài viết xem là trên các compiler và nền tảng hiện đại thì thực tế không gây vấn đề
  • Cách hiện tại dùng khớp kiểu bằng toán tử ba ngôi để buộc phát sinh lỗi, thay vì ép kiểu con trỏ hàm

Vấn đề khi truyền List(Foo) làm đối số

  • Compiler C có thể không xem hai định nghĩa List(Foo) có cùng cấu trúc là cùng một kiểu
List(Foo) a;
List(Foo) b = a; // error
  • Ngay cả khi định nghĩa đối số hàm là void my_function(List(Foo) list) và gọi my_function(a), cũng có thể xảy ra lỗi kiểu không tương thích
  • Cách giải quyết là đặt tên kiểu bằng typedef
typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

void my_function(ListFoo list);
my_function(a); // ok
  • Với biến cục bộ, vẫn có thể tiếp tục dùng dạng List(Foo) local_foo_list
  • Trong GCC 15 và Clang vào cuối năm 2025, nhờ thay đổi quy tắc, các kiểu giống nhau về cấu trúc có cùng tên tag dự kiến sẽ được xử lý như cùng một kiểu

Có thể áp dụng cho các cấu trúc dữ liệu ngoài danh sách

  • Kỹ thuật tương tự có thể áp dụng không chỉ cho danh sách, mà còn cho nhiều cấu trúc dữ liệu như map, array, binary tree
  • Cũng có thể mở rộng cho các cấu trúc dữ liệu cần nhiều kiểu liên quan
  • Ví dụ, hash map có thể đặt chung cấu trúc nội bộ, kiểu khóa và kiểu giá trị trong union
#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}
  • stb_ds.h cũng là một ví dụ về cấu trúc dữ liệu generic an toàn kiểu, nhưng vì array và map dùng C array nên một số lỗi kiểu được bắt ở thời điểm gán array, chứ không phải ở thời điểm truyền giá trị

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
Các ý kiến trên Hacker News

  • Đoạn mã cấp 2 uint64_t data[]; là sai với các kiểu có yêu cầu căn chỉnh lớn hơn uint64_t, và gây lãng phí với các kiểu nhỏ hơn. Ví dụ như ABI ilp32 trên kiến trúc 64-bit
    Đoạn mã cấp 3 phải là int main() { List(Foo) foo_list = {NULL};
    Vì không có typeof, nếu đi đường vòng thì không thể trả về gì cả, và do == có tính đối xứng nên cách đi vòng này cũng cho phép cả lỗi liên quan đến const
    Cũng không thể bỏ qua payload một cách an toàn, vì nó cần để biết kích thước đúng. Trường hợp muốn thêm int32_t vào List(int64_t) phải được phép, nhưng không thể biết sizeof của int32_t đó. Để đoạn mã này hoạt động đúng, vẫn còn thiếu khá nhiều phần
    Generic trong C hiện nay có hai giới hạn lớn. Thứ nhất, cách ủy quyền cho vtable bị hạn chế tính năng vì struct không thể chứa macro mà chỉ có thể chứa hàm. Thứ hai, để tránh overhead thì phải ủy quyền cho vtable bên ngoài, nhưng để làm vậy phải khai báo tiến tất cả các kiểu sẽ dùng vtable
    Cách tốt nhất tôi tìm được đến nay là chỉ khai báo, nhưng không định nghĩa, các hàm static trong header khai báo tiến nơi khai báo typedef. Trên thực tế, khi không include header của một kiểu cụ thể vào một translation unit nào đó, thời điểm phát cảnh báo “undefined static” khác nhau giữa GCC và Clang
    Chẳng hạn hãy nghĩ đến một hàm nhận struct SizedBuffer {void *p; size_t len;}; hoặc struct BoundedBuffer {void *begin; void *end;}; đến từ các header khác nhau, cùng với các phiên bản const tương ứng của chúng

    • Vì vấn đề phải khai báo tiến tất cả các kiểu sẽ dùng vtable nếu muốn ủy quyền cho vtable bên ngoài, trong dự án Apache Clownfish mà tôi từng tham gia, chúng tôi thậm chí đã tạo hẳn một trình biên dịch cho việc này
      Ban đầu chúng tôi parse các file .h, nhưng cuối cùng thấy tốt hơn là tạo một ngôn ngữ header nhỏ gọi là .cfh “Clownfish Header”
      Để gọi phiên bản CharBuf của phương thức Clone được định nghĩa trong lớp cha Obj, chúng tôi sinh ra đoạn mã như sau

      typedef cfish_CharBuf*
      (*CFISH_CharBuf_Clone_t)(cfish_CharBuf* self);

      extern uint32_t CFISH_CharBuf_Clone_OFFSET;

      static inline cfish_CharBuf*
      CFISH_CharBuf_Clone(cfish_CharBuf* self) {
      const CFISH_CharBuf_Clone_t method
      = (CFISH_CharBuf_Clone_t)cfish_obj_method(
      self,
      CFISH_CharBuf_Clone_OFFSET
      );
      return method(self);
      }

      Cách dùng là như sau

      cfish_CharBuf *charbuf = cfish_CharBuf_new();
      cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);

      Mục tiêu của Clownfish là cung cấp một mô hình đối tượng mẫu số chung nhỏ nhất cho nhiều binding ngôn ngữ động, và các file .cfh cũng được dùng để suy ra kiểu cho ngôn ngữ binding. Dù vậy, lượng mã boilerplate được sinh ra để tránh vấn đề đã nêu thật sự vô lý
      Vì thế gần như mọi người đều từ bỏ type safety và cứ dùng ép kiểu void* cho đối tượng được gọi
      https://github.com/apache/lucy-clownfish

    • Trong C, int main() không có nghĩa là không nhận tham số, mà có nghĩa là nhận số lượng tham số không xác định. Nếu muốn nói không nhận tham số thì phải viết int main(void). Đây là điều những người dùng C++ thường hay quên

    • Sẽ thật tốt nếu union có thể được mở rộng theo kiểu hợp nhất. Tức là một kiểu có thể tự khai báo rằng nó là một phần của cùng union với kiểu khác, mà không cần khai báo trước tất cả các kiểu khả dĩ ở một nơi

    • malloc(sizeof(*node) + data_size); cũng có thể gặp vấn đề vì padding. Kích thước tính được có thể quá nhỏ

  • Tôi phản đối
    Tôi từng tạo cả một phương ngữ C bằng trick#0 được nói trong bài. Ví dụ heap nhị phân generic nằm ở https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h
    Cú pháp hơi nặng, nhưng lợi thế lớn là thứ thu được cuối cùng là struct C thông thường, dễ dự đoán và dễ tối ưu. Đó là loại mã mà trình biên dịch xử lý ngon lành như ăn bánh donut
    Các cách khác rốt cuộc đều cần void* và tính kích thước bộ nhớ lúc runtime, và dù sao cũng vẫn phải định nghĩa macro

    • Tôi là tác giả. Heap nhị phân và danh sách liên kết có use case khác nhau. Heap nhị phân cần đọc dữ liệu được đưa vào để lưu trữ đúng, còn danh sách liên kết thì không cần
      Nếu viết heap nhị phân generic thì có lẽ tôi đã cân nhắc các lựa chọn khác. Tôi cũng đã nhắc đến điểm này trong chú thích
    • Thực ra có nhiều lý do để ưu tiên triển khai trong header. Khác với hàm macro, mã trong header có thể step into trong debugger, và thông tin kiểu mà debugger nhìn thấy cũng tốt hơn, nên debug thuận lợi hơn
      Vì mỗi instance được đơn hình hóa, trình biên dịch cũng có nhiều cơ hội tối ưu hơn, và không phải trả chi phí runtime do kích thước biến đổi. Do kích thước cố định, cũng có thể đặt struct generic trên stack
      Ít nhất hai vấn đề mà tác giả nêu có thể đi đường vòng. Tên có thể được đổi từ Bar_func(args…) thành func(Bar)(args…) bằng một macro name mangling đơn giản. Binary bloat có thể giảm phần nào bằng cách dùng weak symbol để linker loại bỏ trùng lặp các hàm được chia sẻ giữa các translation unit khi link
      Container generic cho kiểu con trỏ có vấn đề khác, nhưng có thể đi đường vòng bằng typedef hoặc alias kiểu
      Trong C, cấu trúc dữ liệu intrusive vẫn tiện hơn, nhưng xử lý trong debugger thì rất khổ

  • Ép kiểu hàm giả định rằng kiểu con trỏ phần tử, chẳng hạn Foo*, có cùng biểu diễn với void*, nhưng chuẩn C không đảm bảo điều này. Theo thuật ngữ của chuẩn, hai kiểu này không “tương thích”
    Vì vậy việc gọi hàm bằng kiểu đã chuyển đổi là hành vi không xác định. Ngay cả khi biểu diễn con trỏ tình cờ giống nhau, nó cũng ảnh hưởng đến phân tích alias của trình biên dịch. Có thể tham khảo thêm [0] liên quan
    Việc cast hàm sang các kiểu tham số khác nhau có vẻ là trọng tâm của tính an toàn kiểu trong lời gọi generic, nhưng không rõ đây có phải vấn đề có thể sửa được hay không
    https://news.ycombinator.com/item?id=44421185

    • Phần này đã được nói trong chú thích. Việc cast không phải là trọng tâm của tính an toàn kiểu. Chỉ cần đọc toàn bộ bài là được

  • Nếu muốn “C có generic” thì sao không khỏi vòng vo như vậy và dùng luôn C++?

    • Vì đang làm việc trên dự án legacy bị ràng buộc bởi quy định an toàn và các bảo đảm chất lượng khác. Không thể đơn giản đưa ra một giải pháp đã port sang C++ cho bản phát hành tiếp theo, thậm chí cả bản phát hành thứ mười cũng không. Vì vậy có thể phải làm mọi cách để nó chạy được cho đến khi điều đó trở nên khả thi
      Tuy nhiên với dự án mới thì có thể đặt ra tiêu chuẩn và kỳ vọng là dùng C++, và thực tế là làm như vậy, đồng thời quy định nhắm đến một std cụ thể
      Trên Hacker News tôi khá thường thấy thái độ như thế này, cảm giác gần giống “hãy nâng trình đi”. Tôi nghĩ ở đây cần nhiều ngữ cảnh hơn rất nhiều
    • Vì trong nhiều use case mà C được dùng, chuyển sang C++ lại đòi hỏi nhiều đường vòng hơn
    • Có những người ghét C++ đến tận xương tủy nên những kiểu công việc như thế này cứ tiếp tục xuất hiện
      Sau khi Microsoft bắt đầu có thiện cảm mới với Linux và phần mềm tự do/mã nguồn mở, việc họ lùi khỏi lập trường “C++ là tương lai” thật sự đáng thất vọng
      https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
      https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
      Ngày nay, do chính phủ và các quy định an ninh mạng, Microsoft đã có chính sách mới về C và C++, nên điều đó không còn quá quan trọng
      https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
      https://blogs.windows.com/windowsexperience/2024/11/19/windo...
    • Câu trả lời thật sự là vì cách này thú vị hơn
    • Nếu trong C chỉ cần vài đường vòng là đạt cùng kết quả thì tại sao phải dùng C++

  • Một trick rất hay. Tôi cũng đã dùng trong thư viện thử nghiệm của mình rồi https://github.com/uecker/noplate/blob/main/src/list.h

    • Nếu có ai biết chuyện này thì có lẽ là bạn, bạn có thấy cách áp dụng phương pháp này cho cấu trúc dữ liệu intrusive không?
      Tức là thay vì đặt dữ liệu bên trong node như hiện nay, ta đặt struct node bên trong dữ liệu, và như hệ quả phụ, một object có thể nằm trong nhiều container

  • Cần cẩn thận với phần “các kiểu giống nhau về cấu trúc được xem là cùng một kiểu nhờ thay đổi quy tắc trong GCC 15 và Clang vào nửa cuối năm 2025”
    Trong quy tắc mới, thứ được xem là cùng kiểu chỉ là union có tag, và chúng phải có cùng cấu trúc lẫn cùng tag
    Macro List(T) sẽ phải được đổi để tạo tag khác nhau cho mỗi T khác nhau. Với kiểu đơn giản một từ thì dùng ## khá dễ, nhưng chỉ cần phức tạp hơn chút như con trỏ char, tức chuỗi, là không thể
    Tất nhiên có thể bắt buộc mọi kiểu phải được typedef trước khi dùng với List, nhưng như vậy tính tổng quát sẽ giảm mạnh

    typedef char *str;
    List(str) my_list_of_str;
    List(str) tokenize(str input) {...}

    • Tôi không hiểu câu “chỉ union có tag mới được xem là cùng kiểu”. Tagged union chẳng phải chỉ là một design pattern thôi sao

  • Tôi nghĩ thuật ngữ thông dụng cho “một member không làm gì ngoài việc giữ kiểu” là type witness. Nhưng tài liệu liên quan đến type witness ít hơn tôi tưởng nhiều

    • Khi có một biến kiểu hoàn toàn không được dùng làm kiểu của biến thực tế, có một thuật ngữ tương tự là phantom type
      Tôi chủ yếu thấy trong Haskell, và cũng từng dùng trong Scala để mô phỏng một phân cấp kiểu không có trong hệ thống kiểu thực tế
      Theo một nghĩa nào đó, trick union này cũng giống phantom type, vì kiểu phụ trợ thực ra hoàn toàn không được dùng

  • Cũng có cách mà Linux kernel dùng: embed struct list_head, tức thông tin danh sách, vào trong struct theo từng kiểu
    https://kernelnewbies.org/FAQ/LinkedLists

    • Các tên LIST_HEAD_INIT và INIT_LIST_HEAD dễ gây nhầm lẫn

  • Nếu phải làm như thế này thì thà tôi dùng trực tiếp template C++

  • Trong D thì làm như thế này là được

    struct ListNode(T) {
    ListNode* next;
    T data;
    }

    T!int node;

Tại sao phải khổ sở với bộ tiền xử lý C? Dùng macro tiền xử lý chẳng khác nào dùng búa thay vì súng bắn đinh khi làm mộc hoàn thiện. Súng bắn đinh nhanh hơn 10 lần, lần nào cũng đóng đinh chính xác, và không để lại vết lõm hình bán nguyệt trên sản phẩm

  • Bài viết này nói về C. Trong một số dự án, bắt buộc phải dùng C
  • Không phải chỉ dùng búa; có thể dùng kèm một cây đột. Đóng đinh hoàn thiện bằng búa sao cho còn nhô khoảng 1/8 inch, rồi dùng cây đột để đẩy vào hết