Cara Menulis Struktur Data yang Type-Safe (Generic) di C

• Artikel ini menjelaskan metode baru untuk membuat struktur data generic yang type-safe di bahasa C
• Teknik ini mengaitkan informasi tipe ke struktur data dengan memanfaatkan union, dan dijelaskan menggunakan contoh implementasi linked list
• Artikel ini membandingkan perbedaan dari pola generic C yang sudah ada (makro, pointer void, Flexible Array Member) serta kelemahan masing-masing pendekatan
• Karena pemeriksaan tipe bisa dilakukan saat compile time, penggunaan tipe yang salah dapat dicegah lebih awal
• Teknik baru ini menyediakan antarmuka fungsi/struktur data yang jelas dan konsisten seperti foo_list

---

Pendahuluan

• Memperkenalkan cara membuat struktur data generic di bahasa C dengan tetap menjaga keamanan tipe
• Teknik ini menghubungkan informasi tipe ke struktur data pada saat compile time dengan menggunakan union
• Dapat diterapkan pada semua struktur data seperti map, array, binary tree, dan dijelaskan melalui implementasi linked list dasar sebagai contoh
• Karena banyak pengembang menganggap generic tidak mungkin di C, penjelasan disusun secara bertahap dan mudah diikuti

Generic tradisional berbasis makro

• Cara tradisional untuk mengimplementasikan struktur data generic di C adalah menggunakan makro untuk menghasilkan nama struct, fungsi, dan tipe
• Pendekatan ini diperluas dengan meng-include header struktur data beberapa kali untuk beberapa tipe

Contoh:

• Menggunakan makro (misalnya CONCAT, NODE_TYPE, PREPEND_FUNC) untuk menghasilkan nama struct dan fungsi yang sesuai tipe
• Untuk setiap tipe, fungsi dan struct dibuat secara terpisah, sehingga tipe seperti int dan Foo masing-masing memiliki definisi struktur data sendiri

Kekurangan:

• Sulit mengetahui lokasi definisi tipe dan fungsi karena dihasilkan oleh makro sehingga sulit dilacak
• Sulit memanfaatkan fitur code completion
• Fungsi yang sama dihasilkan berkali-kali, sehingga ukuran biner dan waktu build meningkat
• Nama fungsi memerlukan prefiks tipe (misalnya Foo_list_prepend)

Tahap generic 1: pendekatan pointer void

• Tipe data pada struktur data dibuat tidak bergantung pada tipe dengan menggunakan void *
• Field data pada linked list dideklarasikan sebagai void *
• Karena pemeriksaan tipe tidak dimungkinkan, kesalahan tipe bisa muncul saat runtime dan keamanan compile time rendah
• Tidak efisien dari sisi memori dan cache: node dan data dialokasikan secara terpisah sehingga menambah overhead yang tidak perlu dan meningkatkan cache miss

Tahap generic 2: inline storage (Flexible Array Member)

• Memanfaatkan Flexible Array Member untuk menyimpan data itu sendiri di dalam node, bukan hanya menyimpan pointer
• Satu kali alokasi per node sudah cukup, dan data ditempatkan berdekatan dengan pointer next di cache
• Pendekatan ini memerlukan informasi ukuran untuk diteruskan, seperti pada memcpy, tetapi performanya meningkat berkat tata letak memori yang konsisten
• Dengan fungsi list_alloc_front, struct dapat diinisialisasi langsung tanpa memcpy

Tahap generic 3: implementasi pemeriksaan tipe

• Menambahkan informasi tipe ke struktur data saat compile time dengan mendeklarasikan pointer tipe yang diparameterkan pada member payload di dalam union
• Contoh: #define List(type) union { ListNode *head; type *payload; }
• Dengan cara ini, tipe dari list tersebut dapat diperoleh melalui __typeof__(foo_list.payload)
• Pada makro (list_prepend), hanya kode dengan tipe yang benar yang bisa dikompilasi melalui type casting pada tipe fungsi
• Jika tipe yang digunakan salah, error akan muncul pada saat compile time

Contoh error:

• Saat menambahkan int ke foo_list, akan muncul pesan error kompilasi 'incompatible integer to pointer conversion'

Dukungan untuk compiler yang tidak mendukung typeof

• Hingga sebelum C23, __typeof__ belum menjadi standar, sehingga pada beberapa compiler (misalnya MSVC versi lama) fitur ini tidak berfungsi
• Efek yang mirip masih bisa dicapai dengan solusi alternatif seperti memanfaatkan member payload di dalam struct

Pengiriman parameter dan typedef

• Bahkan jika bentuk List(Foo) sama, compiler tetap menganggapnya sebagai tipe yang berbeda satu sama lain
• Dengan menggunakan typedef, pengiriman parameter dan assignment menjadi lebih lancar

Contoh:

• typedef List(Foo) ListFoo;
• Variabel ListFoo dapat dideklarasikan dan digunakan sebagai parameter fungsi

Penutup dan perluasan ke berbagai struktur data

• Teknik ini juga dapat digunakan pada struktur data yang membutuhkan beberapa parameter tipe (misalnya hash map)
• Melalui union, keamanan tipe untuk key dan value masing-masing dapat dijamin
• Untuk praktik yang lebih rinci dan implementasi makro, lihat tautan gist kode terkait

Kesimpulan

• Pendekatan baru ini mengatasi kelemahan pendekatan lama (keterbacaan, efisiensi build, kemudahan perawatan), sekaligus memberikan skema penamaan fungsi yang konsisten dan keamanan tipe
• Mudah diperluas ke berbagai struktur data dan mendukung banyak parameter tipe
• Melalui pemeriksaan tipe saat compile time, pendekatan ini memastikan keamanan dan efisiensi dalam penggunaan struktur data generic secara bersamaan

Ucapan terima kasih

• Artikel ini diselesaikan berkat masukan dan dorongan dari Martin Fouilleul

[click]

Bukankah lebih sederhana kalau langsung pakai Zig? Pertanyaan seperti itu memang terlintas.

[GN⁺]

Komentar Hacker News

• Menunjukkan bahwa penggunaan uint64_t data[]; pada kode tahap 2 tidak cocok untuk tipe yang membutuhkan alignment lebih besar dari uint64_t, dan sebaliknya boros untuk tipe yang lebih kecil; ini bahkan lebih bermasalah pada ABI ilp32 di arsitektur 64-bit. Disebutkan juga bahwa pada kode tahap 3 seharusnya ditulis int main() { List(Foo) foo_list = {NULL}; seperti ini. Dalam situasi tanpa typeof, nilai kembalian tidak bisa dikembalikan, dan pada kode pengganti bisa muncul error terkait const, yang makin terlihat karena sifat simetris operator ==. Jika payload dihilangkan, tidak ada informasi ukuran sehingga tidak aman; misalnya menambahkan int32_t ke List(int64_t) mungkin tampak aman, tetapi ukuran int32_t sebenarnya tidak bisa dipastikan. Katanya, perlu perbaikan tambahan agar lebih aman. Menurut komentar itu, ada dua keterbatasan besar saat memakai generic di C: pertama, pendekatan delegasi vtable membatasi fungsi karena struct tidak bisa memuat macro; kedua, jika mendelegasikan ke vtable eksternal, semua tipe yang akan dipakai harus dideklarasikan lebih dulu. Cara terbaik disebut sebagai hanya mendeklarasikan fungsi statis di header yang berisi deklarasi typedef, dengan tambahan bahwa GCC dan Clang berbeda dalam kapan mereka mengeluarkan peringatan undefined static. Di akhir, diberikan contoh desain fungsi yang menerima struct buffer berbeda-beda, sambil menekankan bahwa versi const juga harus dikelola semuanya

  • Terkait isu delegasi vtable eksternal, seseorang berbagi pengalaman pernah sampai membuat compiler sendiri untuk menyelesaikan ini di proyek lama. Saat memulai proyek Apache Clownfish, mereka sempat mem-parsing file .h lalu akhirnya membuat format sendiri bernama header Clownfish (.cfh). Mereka menunjukkan contoh kode yang benar-benar memanggil metode "Clone" pada obj, lalu menceritakan pengalaman harus menghasilkan banyak kode berlebihan seperti itu demi binding bahasa dinamis yang memerlukan fitur berorientasi objek. Tujuan Clownfish adalah menyediakan model objek common denominator terendah, dan tipe bahasa binding juga dibuat dari .cfh. Ditambahkan bahwa karena kerumitan seperti ini, kebanyakan orang akhirnya menyerah pada type safety dan memakai casting void*. https://github.com/apache/lucy-clownfish

  • Soal int main(), dijelaskan bahwa di C, int main() berarti jumlah argumen tidak ditentukan. Harus dideklarasikan sebagai int main(void) agar benar-benar berarti tanpa argumen. Ditekankan bahwa ini adalah hal yang sering dilupakan banyak penulis C++

  • Ada pendapat bahwa mereka berharap union bisa benar-benar “berunion”, yaitu satu tipe dapat mendeklarasikan dirinya sebagai bagian dari union tipe lain

  • Menunjukkan bahwa saat melakukan malloc, ukuran yang dihitung bisa lebih kecil dari ukuran sebenarnya karena masalah padding internal, misalnya saat menulis malloc(sizeof(*node) + data_size);, sehingga dianggap berisiko

• Membantah isi trik #0, dengan mengatakan bahwa ia memakai trik ini saat membuat seluruh dialek C. Sebagai contoh, dibagikan kode implementasi generic binary heap https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. Sintaksnya memang agak berat, tetapi hasil akhirnya menjadi struct C biasa sehingga memberi keuntungan besar dalam optimisasi dan prediktabilitas. Menurutnya, implementasi lain tak terhindarkan harus memakai void*, sizing memori runtime, dan definisi macro

  • Sebagai penulis artikel, ia menjelaskan bahwa binary heap dan linked list memiliki tujuan berbeda. Binary heap perlu membaca data saat penyimpanan sehingga pendekatan aksesnya berbeda, dan saat menulis generic binary heap pilihannya bisa berbeda. Ia menambahkan bahwa hal ini juga sudah disebutkan di catatan kaki artikel

  • Diberikan beberapa alasan mengapa implementasi di header lebih disukai. Saat debugging, lebih mudah melacak kode dan memanfaatkan informasi tipe dibanding fungsi macro. Compiler juga bisa melakukan optimisasi monomorphized untuk tiap instans tanpa biaya runtime atau beban ukuran variabel. Struct generic bisa diletakkan di stack. Dua masalah yang disebut penulis artikel dianggap bisa diakali: nama fungsi bisa dengan mudah diubah dengan macro nama fungsi, dan simbol ganda saat linking juga bisa digabung otomatis memakai weak symbol. Untuk container generic bertipe pointer ada masalah lain, tetapi bisa diatasi dengan typedef dan sebagainya. Menurutnya intrusive data structure di C tetap nyaman, hanya saja debugging-nya sulit

  • Ungkapan "compiler melahapnya seperti makan donat" membuat seseorang tertawa terbahak-bahak

• Saat melakukan konversi tipe fungsi, misalnya dengan mengasumsikan representasi internal Foo* dan void* sama, hal itu tidak dijamin dalam C standar. Bila tidak ada kompatibilitas tipe ("compatible") antartipe, casting seperti ini bisa berujung pada undefined behavior. Disebutkan juga bahwa compiler bisa terpengaruh dalam analisis alias dan sebagainya (dengan tautan referensi) https://news.ycombinator.com/item?id=44421185

  • Penulis artikel menjawab bahwa ini sudah disebut di catatan kaki, dan casting bukan inti dari type safety di sini. Ia menyarankan agar membaca keseluruhan artikelnya

• Muncul pertanyaan, "Kalau untuk memakai generics di C harus sampai melakukan akrobat seperti ini, kenapa tidak pakai C++ saja?"

  • Seseorang berbagi pengalaman bahwa karena standar keselamatan dan persyaratan lain, pada proyek legacy sering kali migrasi ke C++ belum memungkinkan untuk saat ini. Untuk proyek baru, mereka memang menetapkan standar dan mengadopsi C++, tetapi proyek lama dianggap masih harus bertahan dengan C untuk sementara. Ada pendapat bahwa sudut pandang "tinggal pakai C++ saja" sebaiknya sedikit lebih peka terhadap konteks

  • Dalam praktiknya juga, di banyak tempat yang memakai C, beralih ke C++ justru bisa lebih rumit dan menimbulkan lebih banyak masalah

  • Sebaliknya, ada pula yang berpendapat bahwa dengan sedikit usaha hasil yang sama bisa dicapai di C, jadi tidak perlu sampai beralih ke C++

• Diperkenalkan pola yang benar-benar dipakai di kernel Linux, yaitu menyertakan struct list_head yang memuat informasi list ke dalam struct per tipe. Tautan referensi terkait juga dibagikan https://kernelnewbies.org/FAQ/LinkedLists

  • Ada yang merasa nama macro LIST_HEAD_INIT dan INIT_LIST_HEAD di kernel Linux kurang intuitif

• Pada kode di bagian "typeof on old compilers", ditunjukkan bahwa (list)->payload = (item); sebenarnya bukan no-op, melainkan menimpa list head dengan item. Jika perilaku yang diinginkan memang no-op, disarankan membungkusnya dengan if(0)

  • Disebutkan juga bahwa pada contoh tersebut union diubah menjadi struct, dan ini pun tampak boros. Menurut komentar itu, menanganinya di dalam if(0) akan lebih baik

• Ditunjukkan bahwa dalam bahasa D, struktur generic list seperti ini jauh lebih sederhana, sambil menekankan ketidaknyamanan macro C dengan metafora bahwa preprocessor C terasa seperti memukul paku dengan palu ke kuku sendiri, sedangkan untuk memaku, nail gun jauh lebih cepat dan rapi

  • Dijelaskan bahwa posting tersebut memang tentang C, dan pada beberapa proyek memang wajib menggunakan C

• Ide memanfaatkan union dan typeof() dianggap menarik. Dalam pengalaman komentator, pada data structure intrusive mereka tetap merasa perlu wrapper yang dibungkus macro besar, dan mereka mempertanyakan apakah implementasi seperti itu juga bisa dilakukan dengan union dan typeof. Sebagai contoh, mereka membagikan kode wrapper hash table dan tautan dokumentasi https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

• Seseorang berbagi bahwa mereka sudah memakai teknik ini di library eksperimental https://github.com/uecker/noplate/blob/main/src/list.h

  • Mereka menanyakan ide untuk struct intrusive, yaitu cara memasukkan node structure ke dalam data agar sebuah objek bisa sekaligus berada di beberapa container

• Tampaknya inti konsepnya adalah memanfaatkan tipe function pointer untuk memperoleh type safety, alih-alih memakai handle type yang umum. Disebutkan bahwa pada standar C23, masalah kompatibilitas tipe telah diperbaiki, lalu dibagikan dokumen standar terkait serta status dukungan GCC/Clang terbaru https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

  • Sebagai penulis artikel, ia menekankan bahwa ide utamanya adalah memakai union untuk mengaitkan informasi tipe ke tipe data generic; casting fungsi bukan satu-satunya cara, dan berbagai alternatif juga sudah dibahas rinci di footnote serta bagian "typeof on old compilers"