C’de tip güvenli jenerik veri yapıları yazma yöntemi

(danielchasehooper.com)

3 puan yazan GN⁺ 2025-07-01 | 2 yorum | WhatsApp'ta paylaş

C’de de makrolar, void *, flexible array member ve union birleştirilerek tip güvenli jenerik veri yapıları oluşturulabilir; örnek, bağlı listeyi adım adım nasıl uygulayacağını gösteriyor
Tipe özel başlık dosyasını birden çok kez include etme yöntemi güvenli olsa da, makroyla üretilen kod nedeniyle tanım takibi ve kod tamamlama zorlaşır; ikili dosya boyutu ve derleme süresi de artabilir
void * tabanlı liste genel amaçlıdır ama tip hatalarını engelleyemez; düğüm ve veri ayrı ayrı ayrılırsa düğüm başına 2 ayırma ve cache miss oluşabilir
Flexible array member ile veriyi düğümün içinde saklayıp List(type)’ı union ile sararsanız, çalışma zamanı maliyeti olmadan derleme zamanı tip bilgisi ekleyebilirsiniz
list_prepend makrosu, üçlü operatörle aktarılan değer ile payload tipini eşleştirerek derleme hatası üretir; dönüş işaretçisi tipi için __typeof__() kullanılabilir

C jenerik uygulamasının başlangıç noktası

Amaç, C’de List(int), List(Foo) gibi tipe özel listeler tanımlamak ve yanlış tip eklendiğinde bunun derlenmemesini sağlamaktır
Örnekte List(Foo) içine Foo değeri konabilir, ancak list_prepend(&foo_list, 7) gibi farklı tip ekleyen kod derlenmez
list_for(item, &foo_list) içindeki item, Foo * tipi olarak ele alınabilir

Seviye 0: Jenerik başlık dosyası yöntemi

Bir yöntem, veri yapısını bir başlık dosyasına yazıp tip makrosu T’yi değiştirerek birden çok kez #include etmektir
list.h, T’ye dayanarak FooListNode, Foo_list_prepend gibi tipleri ve fonksiyonları makroyla üretir
Bu yöntem jenerik ve tip güvenlidir, ancak kullanım deneyimi pürüzlü hale gelir
- Tipler ve fonksiyonlar makrolarla oluşturulduğu için tanım konumunu bulmak zorlaşır
- Kod tamamlama iyi çalışmayabilir
- Her tip için aynı fonksiyonun bir kopyası oluştuğundan ikili dosya boyutu ve derleme süresi artar
- Tek bir list_prepend() yerine Foo_list_prepend(), int_list_prepend() gibi tip önekli fonksiyonlar kullanmak gerekir
Tipe özel kod üretimi gerektiren jenerik fonksiyonlarda bu yöntem daha uygun olabilir

Seviye 1: `void *` tabanlı liste

ListNode, void *data taşıyorsa birden fazla tipte veri barındırabilir
list_prepend(ListNode **head, void *data), veri işaretçisini olduğu gibi sakladığı için uygulaması basittir
Sorun, bu yapının tip güvenli olmamasıdır
Düğüm ve veri ayrı ayrı ayrılırsa bellek ve performans maliyeti de artar
- Tek bir düğüm için iki ayırma gerekir
- data işaretçisinin kendisi ek bellek kullanır
- Listeyi dolaşırken sonraki düğüme erişimde ve veriye erişimde ayrı ayrı cache miss yaşanabilir
Örnek kod, aşinalık nedeniyle malloc kullanıyor; ancak pratikte Arena kullanımı öneriliyor ve ilgili kaynak olarak video ile yazı incelenebilir

Seviye 2: Veriyi düğüm içinde saklama

void *data yerine Flexible Array Member kullanılırsa veri düğümün içine konabilir
struct ListNode, ListNode *next ve char data[] içerir; ayırma sırasında sizeof(* node) + data_size kadar alan tek seferde ayrılır
list_prepend, aktarılan veriyi ve boyutu alıp memcpy ile node->data içine kopyalar
Bu yöntem, next ile gerçek veriyi bellekte birbirine yakın yerleştirerek void * yöntemindeki ayırma ve cache sorunlarını azaltır
Buna karşılık çağıranın data_size geçirme yükü doğar
memcpy’den kaçınmak isterseniz list_alloc_front, düğümün veri alanı işaretçisini döndürebilir ve çağıran bu belleği doğrudan ilklendirebilir
data üyesinin hizalaması, padding’i ve boyut hesaplama sorunları ayrı bir konu olduğundan örnekte ayrıntılı ele alınmaz

Seviye 3: `union` ile tip bilgisi ekleme

Temel teknik, List(type)’ı union olarak tanımlayıp gerçek liste başını ve tip bilgisi için bir işaretçiyi birlikte tutmaktır

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

payload çalışma zamanında kullanılmaz, derleme zamanı tip bilgisi sağlar
union kullanıldığı için payload ayrı bellek tüketmez
List(Foo) foo_list, List(int) int_list gibi tipe özel listeler oluşturulabilir

Üçlü operatörle tip denetimi yapma

list_prepend makrosu, içerideki _list_prepend fonksiyonunu çağırırken üçlü operatörle item ve (list)->payload tiplerini eşleştirir

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

Üçlü operatörün iki aday tipi uyuşmazsa derleyici tip uyumsuzluğu hatası verir
Örneğin List(Foo)’ya Bar * geçirilirse Clang, Foo * ile Bar * arasındaki işaretçi tipi uyumsuzluğunu hata olarak gösterir
Aynı makro, sizeof(*(list)->payload) ile saklama tipinin boyutunu da otomatik geçirir
Asıl işi _list_prepend(ListNode **head, void *data, size_t data_size) gibi bir jenerik iç fonksiyon üstlenir

Dönüş tipi için `typeof()` kullanma

Jenerik fonksiyonun iç veri işaretçisini döndürmesi gerektiğinde, __typeof__() ile void * dönüş değeri payload tipine cast edilebilir

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

__typeof__() Clang, GCC ve MSVC 19.39 ve sonrasında desteklenir
__typeof__(), C23’te standarda dahil edilene kadar isteğe bağlı bir uzantıydı
MSVC 19.39 öncesi gibi __typeof__() bulunmayan derleyicilerde üçlü operatör tabanlı tip denetimi kullanılabilir
Tip güvenli dönüş, payload üzerinden ayırma yöntemiyle de mümkündür; ancak ayrıntılı uygulama atlanmıştır

Eski yöntem ve tanım gereği dikkat edilmesi gerekenler

Önceki yöntem, _list_prepend’i __typeof__((list)->payload) içeren bir fonksiyon işaretçisi tipine cast ederek çağıran bir yapıdaydı
Tipi cast edilmiş fonksiyon işaretçisi çağrısı teknik olarak tanımsız davranıştır; ancak modern derleyicilerde ve modern platformlarda pratikte sorun çıkarmadığı varsayılır
Mevcut yöntem, fonksiyon işaretçisi cast’i yerine üçlü operatör tip eşleşmesi ile hatayı tetikler

`List(Foo)`’yu argüman olarak geçirirken yaşanan sorun

C derleyicisi, aynı yapıya sahip iki List(Foo) tanımını aynı tip olarak görmeyebilir

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

Fonksiyon argümanı olarak void my_function(List(Foo) list) tanımlayıp my_function(a) çağırıldığında da uyumsuz tip hatası çıkabilir
Çözüm, typedef ile tipe ad vermektir

typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

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

Yerel değişkenlerde List(Foo) local_foo_list biçimi kullanılmaya devam edilebilir
GCC 15 ve 2025 sonundaki Clang’da kural değişikliği ile aynı etiket adına sahip yapısal olarak aynı tiplerin aynı tip olarak kabul edilmesi planlanıyor

Liste dışındaki veri yapılarına da uygulanabilir

Aynı teknik yalnızca listelere değil map, dizi ve ikili ağaç gibi pek çok veri yapısına da uygulanabilir
Birden fazla ilişkili tip gerektiren veri yapılarına da genişletilebilir
Örneğin hash map, iç yapıyı ve anahtar tipi ile değer tipini union içinde birlikte tutabilir

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

stb_ds.h da tip güvenli jenerik veri yapılarına bir örnektir; ancak diziler ve map’ler C dizilerini kullandığı için bazı tip hataları değer geçirme anında değil, dizi ataması anında yakalanır

2 yorum

click 2025-07-01

Basitçe Zig kullanmak yeterli olmaz mı? diye bir soru akla geliyor.

GN⁺ 2025-07-01

Hacker News yorumları

Seviye 2 kodundaki uint64_t data[];, hizalama gereksinimi uint64_t'den büyük olan türler için yanlış, daha küçük olan türler içinse israf olur. Örneğin 64 bit mimarideki ilp32 ABI böyle bir durumdur.
Seviye 3 kodu int main() { List(Foo) foo_list = {NULL}; olmalı.
typeof olmadığı için etrafından dolaşınca hiçbir şey döndüremezsiniz; ayrıca == simetrik olduğu için bu dolambaçlı yöntem const ile ilgili hatalara da izin verir.
payload da güvenle atlanamaz. Çünkü doğru boyutu bilmek için gereklidir. List(int64_t)'ye int32_t eklemek mümkün olmalıdır, ama o int32_t'nin sizeof değerini bilemezsiniz. Bu kodun düzgün çalışması için hâlâ epey eksik parça var.
Mevcut C jeneriklerinde iki büyük sınırlama var. Birincisi, vtable'a devreden yaklaşımda struct makro içeremez, yalnızca fonksiyon içerebilir; bu da işlevselliği sınırlar. İkincisi, ek yükten kaçınmak için harici bir vtable'a devretmek gerekir; bunun için de vtable'ı kullanacak tüm türleri önceden bildirmek gerekir.
Şimdiye kadar bulduğum en iyi yöntem, typedef'i bildiren ileri bildirim header'ında static fonksiyonları yalnızca bildirmek, tanımlamamaktı. Belirli bir türün header'ını bir çeviri birimine dahil etmediğinizde “undefined static” uyarısının hangi aşamada çıktığı GCC ile Clang'de farklı.
Örneğin farklı header'lardan gelen struct SizedBuffer {void *p; size_t len;}; veya struct BoundedBuffer {void *begin; void *end;}; ile bunların her birinin const sürümlerini alan bir fonksiyon düşünün.
- Harici vtable'a devretmek için vtable'ı kullanacak tüm türleri önceden bildirme zorunluluğu yüzünden, daha önce katkı verdiğim Apache Clownfish projesinde bunun için başlı başına bir derleyici bile yapmıştık.
  Başta .h dosyalarını parse ediyorduk, ama sonunda .cfh “Clownfish Header” denen küçük bir header dili yapmanın daha iyi olduğuna karar verdik.
  Üst sınıf Obj içinde tanımlı Clone metodunun CharBuf sürümünü çağırmak için şöyle kod üretiyorduk:
  
  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);
  }
  
  Kullanımı şöyleydi:
  
  cfish_CharBuf *charbuf = cfish_CharBuf_new();
  cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);
  
  Clownfish'in amacı, birden fazla dinamik dil bağlaması için en küçük ortak payda niteliğinde bir nesne modeli sağlamaktı; .cfh dosyaları bağlama dilleri için türleri türetmekte de kullanılıyordu. Yine de işaret edilen sorundan kaçınmak için üretilen boilerplate kod miktarı gerçekten akıl almazdı.
  Bu yüzden neredeyse herkes tür güvenliğinden vazgeçip çağrı hedefinde doğrudan void* cast'i kullanmayı tercih ediyor.
  https://github.com/apache/lucy-clownfish
- C'de int main() argüman almadığı anlamına gelmez; bilinmeyen sayıda argüman aldığı anlamına gelir. Argüman almadığını belirtmek için int main(void) yazmak gerekir. C++ kullananların sıkça unuttuğu bir gerçek.
- union'ların birleşimsel olarak genişletilebilmesi iyi olurdu. Yani bir tür, mümkün olan tüm türleri tek bir yerde önceden bildirmeden, başka türlerle aynı union'ın parçasıymış gibi kendini bildirebilse.
- malloc(sizeof(*node) + data_size); da padding yüzünden sorun çıkarabilir. Hesaplanan boyut fazla küçük kalabilir.
Katılmıyorum.
Yazıda bahsedilen trick#0 ile komple bir C lehçesi oluşturmuştum. Örneğin jenerik ikili heap https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h adresinde.
Sözdizimi biraz ağır, ama sonunda elde ettiğiniz şeyin sıradan, öngörülebilir ve optimize etmesi kolay normal C struct'ları olması büyük avantaj. Derleyicinin çörek gibi yiyip bitireceği kod.
Diğer yaklaşımlar sonunda void* ve çalışma zamanında bellek boyutu hesaplaması gerektiriyor; ayrıca zaten makro da tanımlamak zorundasınız.
- Yazarıyım. İkili heap ile bağlı liste farklı kullanım örnekleri. İkili heap doğru saklamak için içine konan veriyi okumak zorundadır, ama bağlı listenin buna ihtiyacı yoktur.
  Jenerik ikili heap kullansaydım seçenekleri farklı tartmış olabilirdim. Dipnotta da bu noktaya değindim.
- Header içinde implementasyon tercih etmek için gerçekten birkaç neden var. Makro fonksiyonların aksine header kodunun içine debugger'da adım adım girilebilir; debugger'ın görebildiği tür bilgisi de daha iyidir, bu yüzden debugging daha iyidir.
  Her örnek monomorfize edildiği için derleyici optimizasyonuna da daha çok alan kalır ve değişken boyut nedeniyle çalışma zamanı maliyeti ödemezsiniz. Sabit boyutlu olduğundan jenerik struct'ı stack'e de koyabilirsiniz.
  Yazarın bahsettiği sorunlardan en az ikisi aşılabilir. İsimler, basit bir name mangling makrosuyla Bar_func(args…) biçiminden func(Bar)(args…) biçimine çevrilebilir. Binary şişmesi ise weak symbol kullanılarak, link sırasında çeviri birimleri arasında paylaşılan fonksiyonların tekilleştirilmesiyle kısmen azaltılabilir.
  Pointer türlerinin jenerik container'larında başka bir sorun var, ama typedef veya tür alias'larıyla bunun etrafından dolaşılabilir.
  C'de intrusive veri yapıları hâlâ daha rahat, ama debugger'da uğraşması acı verici.
Fonksiyon tipi cast’i, öğe işaretçisi türünün, örneğin Foo*’ın void* ile aynı temsile sahip olduğunu varsayar; ancak C standardı bunu garanti etmez. Standart terminolojiyle bu iki tür “uyumlu” değildir.
Bu nedenle fonksiyonu dönüştürülmüş türle çağırmak tanımsız davranıştır. İşaretçi temsilleri tesadüfen aynı olsa bile bu, derleyicinin alias analizini de etkiler. Bununla ilgili [0] da bakmaya değer.
Fonksiyonları farklı argüman türleriyle cast etmek, jenerik çağrının tip güvenliğinin özü gibi görünüyor; bunun düzeltilebilir bir sorun olup olmadığını bilmiyorum.
https://news.ycombinator.com/item?id=44421185
- Bu, dipnotlarda ele alındı. Cast etmek tip güvenliğinin özü değil. Yazının tamamını okuyabilirsiniz.
“Jenerikleri olan C” istiyorsanız bu kadar dolambaçlı yollara girmeyip doğrudan C++ kullanmak gerekmez mi?
- Çünkü güvenlik regülasyonlarına ve başka kalite güvencesi süreçlerine bağlı legacy projelerde çalışıyoruz. Bırakın bir sonraki sürümü, onuncu sürümde bile C++’a port edilmiş bir çözümü öylece çıkaramayız. Bu yüzden mümkün olana kadar bir şekilde çalışır halde tutmak gerekebilir.
  Öte yandan yeni projeler için C++ kullanılacak şekilde standartları ve beklentileri belirleyebiliriz; gerçekten de bunu yapıyor ve belirli bir std hedeflenecek şekilde karar veriyoruz.
  Hacker News’te bu tavrı oldukça sık görüyorum; biraz “becerini artır” demeye benziyor. Bence burada çok daha fazla bağlama ihtiyaç var.
- Çünkü C’nin kullanıldığı birçok senaryoda C++’a geçmek aslında daha fazla dolambaçlı yol gerektiriyor.
- Bazı insanlar C++’tan iliklerine kadar nefret ediyor; bu tür çalışmaların sürekli ortaya çıkmasının nedeni bu.
  Microsoft’un Linux’a ve özgür/açık kaynak yazılıma yeni bir sempati göstermesinden sonra bile “C++ gelecek” tutumundan geri adım atması gerçekten hayal kırıklığıydı.
  https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
  https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
  Bugünlerde hükümet ve siber mevzuat nedeniyle Microsoft’ta C ve C++ için yeni bir politika var, dolayısıyla pek önemli değil.
  https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
  https://blogs.windows.com/windowsexperience/2024/11/19/windo...
- Asıl cevap: çünkü bu taraf daha eğlenceli.
- C’de birkaç dolambaçlı yolla aynı sonucu alabiliyorsak neden C++ kullanalım?
Güzel bir numara. Ben de deneysel kütüphanemde zaten kullanıyorum: https://github.com/uecker/noplate/blob/main/src/list.h
- Bunu bilecek biri varsa o da sizsiniz gibi geliyor: Bu yaklaşımı intrusive veri yapılarına uygulamanın bir yolunu görüyor musunuz?
  Mevcut durumda olduğu gibi veriyi düğümün içine koymak yerine, düğüm yapısını verinin içine koyan ve yan etki olarak bir nesnenin birden fazla container’a girebilmesini sağlayan yaklaşım.
“Yapısal olarak aynı türler, GCC 15 ve 2025’in ikinci yarısındaki Clang’da kural değişikliği sayesinde aynı tür olarak kabul edilir” kısmında dikkatli olmak gerekiyor.
Yeni kurallarda aynı tür olarak kabul edilenler yalnızca etiketli union’lardır; yapıları aynı olmalı ve etiketleri de aynı olmalıdır.
List(T) makrosunun, farklı her T için farklı bir etiket üretecek şekilde değiştirilmesi gerekir. Basit tek kelimelik türler için bu ## ile kolaydır; ancak char işaretçisi, yani string gibi biraz karmaşıklaştığında imkânsız hale gelir.
Elbette List içinde kullanmadan önce tüm türlerin typedef edilmesini zorunlu kılabilirsiniz, ama bu da genelliği ciddi biçimde azaltır.

typedef char *str;
List(str) my_list_of_str;
List(str) tokenize(str input) {...}
- “Yalnızca etiketli union’lar aynı tür olarak kabul edilir” ifadesini anlamıyorum. Tagged union sadece bir tasarım deseni değil mi?
“Hiçbir şey yapmayıp yalnızca türü taşıyan üye” için genel terimin type witness olduğunu düşünüyorum. Ama type witness ile ilgili literatür beklediğimden çok daha az.
- Gerçek bir değişkenin türü olarak hiç kullanılmayan bir tür değişkeni olduğunda buna benzer bir terim olan phantom type var.
  Bunu çoğunlukla Haskell’de gördüm; Scala’da da gerçek tip sisteminde olmayan bir tip hiyerarşisini taklit etmek için kullanmıştım.
  Bir bakıma bu union numarası da yardımcı tür gerçekte hiç kullanılmadığı için phantom type’a benziyor.
Linux çekirdeğinde kullanılan bir yöntem de var. Liste bilgisi olan struct list_head’i türe özgü struct’ın içine embed etme yöntemi.
https://kernelnewbies.org/FAQ/LinkedLists
- LIST_HEAD_INIT ve INIT_LIST_HEAD adları kafa karıştırıcı.
Böyle yapmak gerekiyorsa doğrudan C++ template kullanmayı tercih ederim.
D’de bunu şöyle yaparsınız:

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

T!int node;

C önişlemcisiyle neden uğraşalım ki? Önişlemci makroları kullanmak, ince marangozlukta çivi tabancası yerine çekiç kullanmaya benzer. Çivi tabancası 10 kat daha hızlıdır, çiviyi her seferinde tam yerine çakar ve iş parçasında yarım ay biçimli izler bırakmaz.

Bu yazı C hakkındadır. Bazı projelerde C kullanmak zorunludur.
Yalnızca çekiç kullanmak zorunda değilsiniz; yanında zımba da kullanabilirsiniz. Pervaz çivisini çekiçle yaklaşık 1/8 inç kalacak şekilde çakıp ardından zımbayla sonuna kadar gömebilirsiniz.