Cara Menulis Struktur Data Generik yang Aman terhadap Tipe di C

(danielchasehooper.com)

3 poin oleh GN⁺ 2025-07-01 | 2 komentar | Bagikan ke WhatsApp

Bahkan di C, dengan menggabungkan makro, void *, flexible array member, dan union, kita bisa membuat struktur data generik yang aman terhadap tipe; contohnya menunjukkan implementasi bertahap menggunakan linked list
Pendekatan meng-include header per tipe berkali-kali itu aman, tetapi karena kode dihasilkan oleh makro, pelacakan definisi dan code completion bisa menjadi sulit, serta ukuran biner dan waktu build dapat meningkat
List berbasis void * bersifat umum, tetapi tidak bisa mencegah kesalahan tipe, dan jika node serta data dialokasikan terpisah maka dapat menimbulkan 2 kali alokasi per node dan cache miss
Dengan flexible array member, data bisa disimpan di dalam node, dan jika List(type) dibungkus dengan union, maka informasi tipe saat compile time bisa dilampirkan tanpa biaya runtime
Makro list_prepend mencocokkan nilai yang diberikan dengan tipe payload melalui operator ternary untuk memicu error kompilasi, dan tipe pointer hasil kembalian dapat memanfaatkan __typeof__()

Titik awal implementasi generik di C

Tujuannya adalah bisa mendeklarasikan list per tipe seperti List(int) dan List(Foo) di C, lalu membuat kode dengan tipe yang salah gagal dikompilasi
Dalam contoh, kita bisa memasukkan nilai Foo ke List(Foo), tetapi kode yang memasukkan tipe lain seperti list_prepend(&foo_list, 7) tidak akan bisa dikompilasi
item di dalam list_for(item, &foo_list) dapat diperlakukan sebagai tipe Foo *

Level 0: pendekatan header generik

Salah satu caranya adalah menulis struktur data di header, lalu menjalankan #include berkali-kali sambil mengganti makro tipe T
list.h menghasilkan tipe dan fungsi seperti FooListNode dan Foo_list_prepend berdasarkan T melalui makro
Pendekatan ini generik dan aman terhadap tipe, tetapi pengalaman penggunaannya terasa agak kasar
- Karena tipe dan fungsi dibentuk oleh makro, sulit menemukan lokasi definisinya
- Code completion mungkin tidak bekerja dengan baik
- Salinan fungsi yang sama dibuat untuk setiap tipe sehingga ukuran biner dan waktu build bertambah
- Kita tidak memakai satu list_prepend(), melainkan fungsi dengan prefiks tipe seperti Foo_list_prepend() dan int_list_prepend()
Untuk fungsi generik yang memang perlu menghasilkan kode per tipe, pendekatan ini bisa lebih cocok

Level 1: list berbasis `void *`

Jika ListNode memiliki void *data, maka ia bisa menampung data dari berbagai tipe
list_prepend(ListNode **head, void *data) hanya menyimpan pointer data apa adanya, sehingga implementasinya sederhana
Masalahnya, struktur ini tidak aman terhadap tipe
Jika node dan data dialokasikan secara terpisah, biaya memori dan performanya juga meningkat
- Satu node memerlukan dua kali alokasi
- Pointer data sendiri memakai memori tambahan
- Saat menelusuri list, akses ke node berikutnya dan akses ke data masing-masing bisa menimbulkan cache miss
Contoh kode memakai malloc karena sudah familiar, tetapi dalam praktiknya disarankan memakai Arena; bahan terkait bisa dilihat di video dan artikel

Level 2: menyimpan data di dalam node

Alih-alih void *data, kita bisa memakai Flexible Array Member untuk menaruh data di dalam node
struct ListNode memiliki ListNode *next dan char data[], lalu saat alokasi memori diambil sekaligus sebesar sizeof(* node) + data_size
list_prepend menerima data dan ukurannya, lalu menyalinnya ke node->data dengan memcpy
Dengan cara ini, next dan data aktual ditempatkan berdekatan di memori sehingga masalah alokasi dan cache pada pendekatan void * bisa dikurangi
Sebagai gantinya, pemanggil harus memberikan data_size
Jika ingin menghindari memcpy, list_alloc_front bisa dibuat untuk mengembalikan pointer ke area data node, sehingga pemanggil dapat menginisialisasi memori itu secara langsung
Masalah alignment, padding, dan perhitungan ukuran pada member data adalah topik terpisah, jadi tidak dibahas rinci dalam contoh

Level 3: menambahkan informasi tipe dengan `union`

Teknik intinya adalah mendefinisikan List(type) sebagai union, lalu meletakkan head list yang sebenarnya bersama pointer untuk informasi tipe

#define List(type) union { \
    ListNode *head; \
    type *payload; \
}

payload tidak dipakai saat runtime dan hanya menyediakan informasi tipe saat compile time
Karena menggunakan union, payload tidak mengonsumsi memori tambahan
Kita bisa membuat list per tipe seperti List(Foo) foo_list dan List(int) int_list

Memeriksa tipe dengan operator ternary

Makro list_prepend memanggil fungsi internal _list_prepend sambil mencocokkan tipe item dengan (list)->payload melalui operator ternary

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
                  (1 ? (item) : (list)->payload), \
                  sizeof(*(list)->payload))

Jika dua kandidat tipe pada operator ternary tidak cocok, compiler akan mengeluarkan error ketidakcocokan tipe
Misalnya, jika Bar * diberikan ke List(Foo), Clang akan menandai ketidakcocokan tipe pointer antara Foo * dan Bar *
Makro yang sama juga otomatis mengirimkan ukuran tipe yang akan disimpan melalui sizeof(*(list)->payload)
Pekerjaan sebenarnya ditangani oleh fungsi internal generik seperti _list_prepend(ListNode **head, void *data, size_t data_size)

Menggunakan `typeof()` untuk tipe hasil kembalian

Saat fungsi generik perlu mengembalikan pointer ke data internal, nilai balik void * bisa di-cast ke tipe payload dengan __typeof__()

#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))

__typeof__() didukung oleh Clang, GCC, dan MSVC 19.39 ke atas
Sebelum masuk ke standar di C23, __typeof__() adalah ekstensi opsional
Pada compiler yang tidak memiliki __typeof__(), seperti MSVC sebelum 19.39, pemeriksaan tipe berbasis operator ternary tetap bisa digunakan
Hasil kembalian yang aman terhadap tipe juga bisa dibuat melalui pola alokasi dengan payload, tetapi detail implementasinya tidak dibahas

Pendekatan lama dan catatan tentang definisi bahasa

Pendekatan sebelumnya memanggil _list_prepend dengan lebih dulu meng-cast-nya ke tipe function pointer yang mencakup __typeof__((list)->payload)
Pemanggilan function pointer yang sudah di-cast seperti itu secara teknis merupakan undefined behavior, tetapi pada compiler dan platform modern umumnya tidak menimbulkan masalah nyata
Pendekatan saat ini tidak lagi memakai cast function pointer, melainkan kecocokan tipe pada operator ternary untuk memicu error

Masalah saat mengoper `List(Foo)` sebagai argumen

Compiler C bisa saja tidak menganggap dua definisi List(Foo) yang memiliki struktur sama sebagai tipe yang sama

List(Foo) a;
List(Foo) b = a; // error

Bahkan jika kita mendefinisikan argumen fungsi sebagai void my_function(List(Foo) list) lalu memanggil my_function(a), bisa tetap muncul error tipe tidak kompatibel
Solusinya adalah memberi nama tipe tersebut dengan typedef

typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

void my_function(ListFoo list);
my_function(a); // ok

Untuk variabel lokal, bentuk seperti List(Foo) local_foo_list tetap bisa digunakan
Di GCC 15 dan Clang pada akhir 2025, perubahan aturan akan membuat tipe yang secara struktural sama dan memiliki nama tag yang sama diperlakukan sebagai tipe yang sama

Bisa diterapkan ke struktur data selain list

Teknik yang sama bisa diterapkan bukan hanya ke list, tetapi juga ke map, array, binary tree, dan berbagai struktur data lain
Ini juga bisa diperluas ke struktur data yang memerlukan beberapa tipe terkait sekaligus
Misalnya, hash map bisa menempatkan struktur internal, tipe key, dan tipe value bersama-sama di dalam union

#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}

stb_ds.h juga merupakan contoh struktur data generik yang aman terhadap tipe, tetapi karena array dan map-nya memakai C array, beberapa kesalahan tipe baru terdeteksi saat assignment array, bukan saat nilai diberikan

2 komentar

click 2025-07-01

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

GN⁺ 2025-07-01

Komentar Hacker News

Pada kode level 2, uint64_t data[]; keliru untuk tipe yang persyaratan alignment-nya lebih besar daripada uint64_t, dan boros untuk tipe yang lebih kecil. Contohnya ABI ilp32 pada arsitektur 64-bit
Kode level 3 seharusnya menjadi int main() { List(Foo) foo_list = {NULL};
Karena tidak ada typeof, jika memakai jalan memutar tidak ada apa pun yang bisa dikembalikan, dan karena == bersifat simetris, cara memutar ini juga membiarkan kesalahan terkait const lolos
payload juga tidak bisa dihilangkan dengan aman. Itu diperlukan untuk mengetahui ukuran yang benar. Kasus menambahkan int32_t ke List(int64_t) seharusnya dimungkinkan, tetapi sizeof dari int32_t itu tidak bisa diketahui. Agar kode ini berfungsi dengan benar, masih cukup banyak bagian yang belum ada
Saat ini ada dua keterbatasan besar pada generik di C. Pertama, pendekatan mendelegasikan ke vtable membatasi fungsionalitas karena struct tidak bisa memuat makro, hanya fungsi. Kedua, untuk menghindari overhead harus mendelegasikan ke vtable eksternal, tetapi untuk itu semua tipe yang akan memakai vtable harus dideklarasikan di muka
Cara terbaik yang sejauh ini saya temukan adalah hanya mendeklarasikan fungsi static, tanpa mendefinisikannya, di header depan yang mendeklarasikan typedef. Dalam praktiknya, tahap munculnya peringatan “undefined static” ketika header tipe tertentu tidak disertakan dalam suatu unit translasi berbeda antara GCC dan Clang
Misalnya, bayangkan fungsi yang menerima struct SizedBuffer {void *p; size_t len;}; atau struct BoundedBuffer {void *begin; void *end;}; dari header yang berbeda, serta versi const masing-masing
- Karena masalah bahwa untuk mendelegasikan ke vtable eksternal semua tipe yang akan memakai vtable harus dideklarasikan di muka, dalam proyek Apache Clownfish yang dulu saya ikuti, kami bahkan membuat compiler khusus untuk itu
  Awalnya kami mem-parse file .h, tetapi pada akhirnya kami menilai lebih baik membuat bahasa header kecil bernama .cfh “Clownfish Header”
  Untuk memanggil versi CharBuf dari metode Clone yang didefinisikan pada kelas induk Obj, kami menghasilkan kode seperti ini
  
  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);
  }
  
  Pemakaiannya seperti ini
  
  cfish_CharBuf *charbuf = cfish_CharBuf_new();
  cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);
  
  Tujuan Clownfish adalah menyediakan model objek penyebut persekutuan terkecil untuk binding beberapa bahasa dinamis, dan file .cfh juga dipakai untuk menurunkan tipe bagi bahasa binding. Meski begitu, jumlah kode boilerplate yang dihasilkan untuk menghindari masalah yang disebutkan benar-benar tidak masuk akal
  Karena itu hampir semua orang memilih mengorbankan type safety dan langsung memakai cast void* pada target pemanggilan
  https://github.com/apache/lucy-clownfish
- Di C, int main() bukan berarti tidak menerima argumen, melainkan menerima jumlah argumen yang tidak diketahui. Jika maksudnya tidak menerima argumen, harus ditulis int main(void). Ini fakta yang sering dilupakan orang yang memakai C++
- Akan bagus kalau union bisa diperluas secara union-like. Maksudnya, tanpa harus mendeklarasikan semua tipe yang mungkin di satu tempat terlebih dahulu, suatu tipe bisa mendeklarasikan dirinya sendiri seolah-olah merupakan bagian dari union yang sama dengan tipe lain
- malloc(sizeof(*node) + data_size); juga bisa bermasalah karena padding. Ukuran yang dihitung bisa menjadi terlalu kecil
Saya tidak setuju
Saya pernah membuat seluruh dialek C dengan trick#0 yang dibahas di tulisan itu. Misalnya heap biner generik ada di https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h
Sintaksnya memang agak berat, tetapi keuntungan besarnya adalah hasil akhirnya berupa struct C biasa yang wajar, dapat diprediksi, dan mudah dioptimalkan. Ini kode yang akan disantap compiler dengan lahap seperti donat
Pendekatan lain pada akhirnya membutuhkan void* dan perhitungan ukuran memori saat runtime, dan bagaimanapun tetap harus mendefinisikan makro
- Saya penulisnya. Heap biner dan linked list punya use case yang berbeda. Heap biner perlu membaca data yang dimasukkan agar bisa menyimpannya dengan benar, sedangkan linked list tidak perlu
  Jika saya memakai heap biner generik, mungkin saya akan menimbang pilihan dengan berbeda. Saya juga menyebutkan hal ini di catatan kaki
- Ada beberapa alasan nyata untuk lebih menyukai implementasi header. Berbeda dari fungsi makro, kode header bisa di-step into di debugger, dan informasi tipe yang bisa dilihat debugger juga lebih baik, sehingga debugging lebih baik
  Karena setiap instance dimonomorfisasi, compiler juga punya lebih banyak ruang untuk optimasi, dan tidak perlu membayar biaya runtime akibat ukuran variabel. Karena ukurannya tetap, struct generik juga bisa diletakkan di stack
  Setidaknya dua masalah yang disebut penulis bisa diakali. Nama dapat diubah dengan makro name mangling sederhana dari Bar_func(args…) menjadi func(Bar)(args…). Pembengkakan biner bisa dikurangi sebagian dengan memakai weak symbol, sehingga fungsi yang dibagikan antar-unit translasi dideduplikasi saat linking
  Kontainer generik untuk tipe pointer punya masalah lain, tetapi bisa diakali dengan typedef atau alias tipe
  Di C, struktur data intrusive masih lebih nyaman, tetapi menyakitkan untuk ditangani di debugger
Casting tipe fungsi mengasumsikan bahwa tipe pointer item, misalnya Foo*, memiliki representasi yang sama dengan void*, tetapi standar C tidak menjamin hal itu. Dalam istilah standar, kedua tipe itu tidak “kompatibel”
Karena itu, memanggil fungsi dengan tipe yang sudah dikonversi adalah perilaku tak terdefinisi. Sekalipun representasi pointernya kebetulan sama, ini juga memengaruhi analisis aliasing compiler. Terkait hal ini, [0] juga layak dibaca
Casting fungsi ke tipe argumen yang berbeda terlihat seperti inti dari type safety untuk pemanggilan generik, tetapi saya tidak tahu apakah ini masalah yang bisa diperbaiki
https://news.ycombinator.com/item?id=44421185
- Ini sudah dibahas di catatan kaki. Casting bukan inti dari type safety. Baca saja seluruh artikelnya
Kalau menginginkan “C dengan generics”, bukankah lebih baik tidak memutar sejauh ini dan langsung memakai C++ saja?
- Karena kami bekerja pada proyek legacy yang terikat regulasi keselamatan dan jaminan kualitas lainnya. Kami tidak bisa begitu saja mengirim solusi yang sudah di-port ke C++ pada rilis berikutnya, bahkan pada rilis kesepuluh sekalipun. Jadi, sampai itu memungkinkan, kami mungkin harus membuatnya tetap berjalan dengan cara apa pun
  Namun untuk proyek baru, kami bisa menetapkan standar dan ekspektasi agar memakai C++, dan memang begitu, dengan target std tertentu
  Saya cukup sering melihat sikap seperti ini di Hacker News, rasanya dekat dengan “tingkatkan kemampuanmu”. Menurut saya perlu jauh lebih banyak konteks di sini
- Karena dalam banyak use case tempat C dipakai, beralih ke C++ justru menuntut lebih banyak workaround
- Sebagian orang membenci C++ sampai ke tulang, sehingga pekerjaan semacam ini terus muncul
  Setelah Microsoft mulai menyukai Linux serta perangkat lunak bebas dan open source, sangat mengecewakan bahwa mereka mundur dari posisi “C++ adalah masa depan”
  https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
  https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
  Sekarang ini tidak terlalu penting, karena Microsoft punya kebijakan baru soal C dan C++ akibat pemerintah dan regulasi siber
  https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
  https://blogs.windows.com/windowsexperience/2024/11/19/windo...
- Jawaban sebenarnya: karena cara ini lebih menyenangkan
- Kalau bisa mendapat hasil yang sama di C hanya dengan beberapa workaround, kenapa memakai C++?
Trik yang keren. Saya juga sudah memakainya di library eksperimental saya https://github.com/uecker/noplate/blob/main/src/list.h
- Kalau ada yang mungkin tahu soal ini, sepertinya Anda orangnya: apakah Anda melihat cara menerapkan pendekatan ini juga pada struktur data intrusive?
  Maksudnya, alih-alih memasukkan data ke dalam node seperti sekarang, kita memasukkan struct node ke dalam data, dan sebagai efek samping memungkinkan satu objek masuk ke beberapa container
Bagian “tipe yang secara struktural identik dianggap sebagai tipe yang sama berkat perubahan aturan di GCC 15 dan Clang pada paruh akhir 2025” perlu diwaspadai
Dalam aturan baru, yang dianggap sebagai tipe yang sama hanyalah union yang memiliki tag, dan strukturnya harus sama serta tag-nya juga sama
Macro List(T) harus diubah agar menghasilkan tag berbeda untuk setiap T yang berbeda. Untuk tipe sederhana satu kata, ini mudah dengan ##, tetapi begitu sedikit lebih kompleks seperti pointer char, yaitu string, itu menjadi mustahil
Tentu saja, Anda bisa memaksa semua tipe di-typedef sebelum dipakai di List, tetapi itu sangat mengurangi kegenerikannya

typedef char *str;
List(str) my_list_of_str;
List(str) tokenize(str input) {...}
- Saya tidak paham maksud “hanya union yang memiliki tag yang dianggap sebagai tipe yang sama”. Bukankah tagged union itu sekadar pola desain?
Menurut saya istilah umum untuk “member yang tidak melakukan apa-apa dan hanya menyimpan tipe” adalah type witness. Namun ternyata literatur tentang type witness jauh lebih sedikit dari yang saya kira
- Ada istilah mirip, phantom type, ketika ada variabel tipe yang sama sekali tidak dipakai sebagai tipe variabel nyata
  Saya terutama melihatnya di Haskell, dan pernah memakainya juga di Scala untuk meniru hierarki tipe yang tidak ada di sistem tipe sebenarnya
  Dalam beberapa hal, trik union ini juga mirip phantom type karena tipe bantu itu sebenarnya sama sekali tidak dipakai
Ada juga cara yang dipakai di kernel Linux: meng-embed struct list_head, yaitu informasi list, ke dalam struct khusus tiap tipe
https://kernelnewbies.org/FAQ/LinkedLists
- Nama LIST_HEAD_INIT dan INIT_LIST_HEAD membingungkan
Kalau harus begini, saya lebih memilih langsung memakai template C++
Di D, caranya begini

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

T!int node;

Mengapa harus repot-repot dengan preprosesor C? Menggunakan makro preprosesor itu seperti memakai palu alih-alih nail gun untuk pekerjaan finishing kayu. Nail gun 10 kali lebih cepat, menancapkan paku dengan tepat setiap kali, dan tidak meninggalkan bekas cekungan berbentuk setengah bulan pada hasil kerja

Tulisan ini tentang C. Dalam beberapa proyek, C memang wajib digunakan
Bukan berarti hanya memakai palu; gunakan juga punch. Tancapkan paku molding dengan palu hingga tersisa sekitar 1/8 inci, lalu dorong sampai masuk sepenuhnya dengan punch