C'de tip güvenli (generic) veri yapıları yazma yöntemi

 (danielchasehooper.com)
3 puan yazan GN⁺ 2025-07-01 | 2 yorum | WhatsApp'ta paylaş
  • Bu yazı, C dilinde tip güvenli (generic) veri yapıları oluşturmanın yeni bir yöntemini açıklıyor
  • union kullanarak tip bilgisini veri yapısıyla ilişkilendiren bir tekniği, bağlantılı liste implementasyonunu örnek alarak anlatıyor
  • Mevcut C generic kalıplarıyla (makro, void pointer, Flexible Array Member) arasındaki farkları ve her yaklaşımın dezavantajlarını karşılaştırıyor
  • Derleme zamanı tip kontrolü mümkün olduğu için yanlış tip kullanımı önceden engellenebiliyor
  • Yeni teknik, foo_list gibi açık ve tutarlı işlev/veri yapısı arayüzleri sunuyor

Giriş

  • C dilinde generic veri yapılarını tip güvenli şekilde oluşturma yöntemini tanıtıyor
  • Bu teknik, union kullanarak tip bilgisini derleme zamanında veri yapısına bağlar
  • Map, dizi, ikili ağaç gibi tüm veri yapılarına uygulanabilir; örnek olarak temel bir bağlantılı liste implementasyonu üzerinden açıklanıyor
  • Birçok geliştirici C'de generic'in mümkün olmadığını düşündüğü için, adım adım ve kolay anlaşılır bir anlatım izleniyor

Geleneksel makro tabanlı generic yaklaşım

  • C'de generic veri yapıları implementasyonunun geleneksel yöntemi, makrolarla yapı ve fonksiyon adlarını ile tipleri üretmektir
  • Veri yapısı başlığını farklı tipler için birden çok kez include ederek genişletir

Örnek:

  • Tipe uygun yapı ve fonksiyon adlarını üretmek için makrolar (CONCAT, NODE_TYPE, PREPEND_FUNC gibi) kullanılır
  • Her tip için ayrı fonksiyonlar ve yapılar üretilir; böylece int ve Foo gibi her tip için ayrı veri yapısı tanımları ortaya çıkar

Dezavantajlar:

  • Tip ve fonksiyon tanımlarının nerede olduğunu anlamak zordur (makrolarla üretildiği için iz sürmek güçleşir)
  • Kod otomatik tamamlama özelliklerinden yararlanmak zordur
  • Aynı fonksiyonun birden çok kez üretilmesi, ikili dosya boyutunu ve derleme süresini artırır
  • Fonksiyon adlarında tip öneki gerekir (ör. Foo_list_prepend)

Generic aşama 1: void pointer yöntemi

  • Veri yapısının veri tipini void * yaparak tipten bağımsız hâle getirir
  • Bağlantılı listedeki data alanı void * olarak tanımlanır
  • Tip kontrolü yapılamadığı için çalışma zamanında tip hataları oluşabilir; derleme zamanı güvenliği düşüktür
  • Bellek ve önbellek kullanımı verimsizdir: düğüm ve veri ayrı ayrılır, bu da gereksiz ek yük ve daha fazla cache miss üretir

Generic aşama 2: satır içi depolama (Flexible Array Member)

  • Flexible Array Member (esnek dizi üyesi) kullanılarak pointer saklamak yerine verinin kendisi düğümle birlikte saklanır
  • Her düğüm için tek bir allocation yeterlidir; veri ile next pointer'ı önbellekte birbirine yakın konumlanır
  • Bu yaklaşımda memcpy gibi işlemler ve boyut bilgisinin aktarılması gerekir, ancak tutarlı bellek yerleşimi sayesinde performans iyileşir
  • list_alloc_front fonksiyonu kullanılırsa memcpy olmadan yapı doğrudan başlatılabilir

Generic aşama 3: tip kontrolünü uygulama

  • union içindeki payload üyesinde parametreli tip pointer'ı tanımlanarak derleme zamanında veri yapısına tip bilgisi eklenir
  • Örnek: #define List(type) union { ListNode *head; type *payload; }
  • Bu sayede __typeof__(foo_list.payload) ile ilgili listenin tipi elde edilebilir
  • Makro (list_prepend) içinde fonksiyon tip dönüşümü kullanılarak yalnızca doğru tipteyse derlenmesi sağlanır
  • Yanlış tip kullanılırsa derleme zamanında hata oluşur

Hata örneği:

  • foo_list içine int eklenmeye çalışıldığında, 'incompatible integer to pointer conversion' derleme hatası mesajı üretilir

typeof desteklemeyen derleyiciler için

  • C23 öncesine kadar __typeof__ standart olmadığından, bazı derleyicilerde (ör. eski MSVC sürümleri) çalışmaz
  • Yapı içindeki payload üyesini kullanmak gibi dolaylı yöntemlerle benzer bir etki elde etmek mümkündür

Parametre geçirme ve typedef

  • Aynı biçimdeki List(Foo) bile derleyici tarafından birbirinden farklı tipler olarak değerlendirilir
  • typedef kullanıldığında parametre geçirme ve atama işlemleri daha sorunsuz olur

Örnek:

  • typedef List(Foo) ListFoo;
  • ListFoo değişken bildirimi ve fonksiyon parametresi olarak kullanılabilir

Kapanış ve farklı veri yapılarına genişletme

  • Bu teknik, birden fazla tip parametresi gerektiren veri yapılarında da (ör. hash map) kullanılabilir
  • union sayesinde key ve value için ayrı ayrı tip güvenliği sağlanabilir
  • Daha ayrıntılı pratik örnekler ve makro implementasyonu için ilgili kod gist bağlantısına bakabilirsiniz

Sonuç

  • Yeni yaklaşım, mevcut yöntemlerin dezavantajlarını (okunabilirlik, derleme verimliliği, bakım kolaylığı) aşarak tutarlı fonksiyon adlandırması ve tip güvenliği sunar
  • Birden fazla veri yapısını ve çoklu tip parametrelerini desteklemek kolaydır
  • Derleme zamanı tip kontrolü sayesinde generic veri yapısı kullanımında güvenlik ve verimlilik birlikte sağlanır

Teşekkür

  • Bu yazı, Martin Fouilleul'un geri bildirimi ve teşvikiyle tamamlandı

İlgili okumalar

2 yorum

 
click 2025-07-01

Basitçe Zig kullanmak yeterli olmaz mı? diye bir soru akla geliyor.
 
GN⁺ 2025-07-01
Hacker News görüşleri
    1. aşamadaki kodda uint64_t data[]; kullanımının, hizalama gereksinimi uint64_t'den büyük olan türler için uygun olmadığı, daha küçük türlerde ise gereksiz israf yarattığı belirtiliyor; örneğin 64 bit mimarideki ilp32 ABI'de bu daha da sorunlu. 3. aşamadaki kodda int main() { List(Foo) foo_list = {NULL}; yerine böyle yazılması gerektiği söyleniyor. typeof olmayan durumda dönüş değerini geri veremediği, alternatif kodda ise const ile ilgili hatalar çıkabileceği ve == işleç simetrisi nedeniyle bu sorunun daha görünür olduğu ifade ediliyor. payload çıkarılırsa boyut bilgisi kalmadığı için güvenli olmaz; örneğin List(int64_t) içine int32_t eklemek ilk bakışta sorun yokmuş gibi görünse de gerçekte int32_t'nin boyutu saptanamaz. Daha güvenli hale getirmek için ek iyileştirme gerektiği söyleniyor. C'de generic kullanımında iki büyük sınırlama olduğu düşünülüyor: ilki, vtable delegasyonu yaklaşımında yapının makro içerememesi nedeniyle işlevselliğin kısıtlanması; ikincisi, dış vtable'a delege edildiğinde kullanılacak tüm türlerin önceden bildirilmesi zorunluluğu. En iyi yöntemin, typedef bildirimleri içeren başlıkta yalnızca statik fonksiyonlar tanımlamak olduğu, ancak GCC ile Clang'ın undefined static uyarılarını farklı zamanlarda verdiği de ekleniyor. Son olarak, farklı buffer struct'larını alan fonksiyon tasarımı örneği verilerek const sürümleri dahil hepsinin ayrıca yönetilmesi gerektiği vurgulanıyor

    • Dış vtable delegasyonu sorunuyla ilgili olarak, eski bir projede bunu çözmek için derleyici bile yazdığını anlatıyor. Apache Clownfish projesine başlarken .h dosyalarını parse ettiklerini, sonunda da Clownfish header (.cfh) adlı kendi formatlarını oluşturduklarını söylüyor. Gerçek bir objenin Clone metodunu çağıran örnek kod göstererek, nesne yönelimli özellikler gerektiren dinamik dil binding'leri için bu tür aşırı miktarda kod üretmek zorunda kaldıkları deneyimini paylaşıyor. Clownfish'in amacının en düşük ortak nesne modeli sunmak olduğu, binding dil türlerinin de .cfh üzerinden üretildiği belirtiliyor. Bu karmaşıklık yüzünden çoğu kişinin void* cast ederek tür güvenliğinden vazgeçtiğini de ekliyor. https://github.com/apache/lucy-clownfish

    • int main() konusunda, C'de int main() argüman sayısının belirsiz olduğu anlamına gelir. Argüman olmadığını belirtmek için int main(void) şeklinde tanımlanmalıdır. Birçok C++ yazarı bunu sık sık unutuyor diye vurgulanıyor

    • union'ın gerçekten birleşen bir yapı olması, yani bir türün kendisini başka bir türün union parçası olarak bildirebilmesinin güzel olacağı söyleniyor

    • malloc sırasında iç padding nedeniyle hesaplanan boyutun gerçekte gerekenden küçük kalabileceği belirtiliyor; örneğin malloc(sizeof(*node) + data_size); gibi kullanımın riskli olduğu söyleniyor

  • Trick#0 içeriğine itiraz ediliyor; kendi tam C lehçesini oluştururken bu tekniği kullandığını söylüyor. Örneğin generic binary heap uygulama örnek kodu paylaşıyor https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. Sözdiziminin biraz ağır olduğu, ama sonunda sıradan bir C struct'ına dönüştüğü için optimizasyon ve öngörülebilirlik açısından büyük avantaj sağladığı ifade ediliyor. Başka uygulamalarda void*, çalışma zamanında bellek boyutlandırma ve makro tanımlarının kaçınılmaz olduğu görüşünde

    • Yazı sahibi olarak, binary heap ile linked list'in amaçlarının farklı olduğunu açıklıyor. Binary heap'in depolama sırasında veriyi okuması gerektiği için yaklaşımın farklı olduğunu, generic binary heap yazarken seçimlerin de farklı olabileceğini belirtiyor. Bunun ana metindeki dipnotlarda da geçtiğini ekliyor

    • Header implementation tercih etmesinin çeşitli nedenleri sıralanıyor. Debug sırasında makro fonksiyonlara kıyasla kod takibi ve tür bilgisinden yararlanmak daha kolay. Derleyici her örnek için monomorphized optimizasyon yapabildiğinden çalışma zamanı maliyeti veya değişken boyut yükü olmuyor. Generic struct'lar stack üzerinde tutulabiliyor. Yazarın sözünü ettiği iki sorun da aşılabilir görülüyor: fonksiyon adları makrolarla kolayca değiştirilebilir, weak symbol kullanılarak link aşamasında çift tanımlar otomatik birleştirilebilir. Pointer type generic container'larda başka bir sorun daha olduğu, ama bunun da typedef vb. ile çözülebileceği söyleniyor. C'de intrusive data structure'ların hâlâ rahat olduğu, ancak debug etmenin zor olduğu düşünülüyor

    • "Derleyici bunu çörek yer gibi yiyor" ifadesi çok güldürmüş

  • Fonksiyon türü dönüşümünde, örneğin Foo* ile void*'ın iç gösteriminin aynı olduğu varsayılıyor, ancak standart C bunu garanti etmiyor. Türler arasında uyumluluk (compatible) yoksa bu tür cast'ler tanımsız davranışa yol açabilir. Derleyicinin alias analizi gibi alanlarda bundan etkilenebileceği söyleniyor (ilgili bağlantı eklenmiş) https://news.ycombinator.com/item?id=44421185

    • Bunun ana metin dipnotunda zaten geçtiği, cast'in tür güvenliğinin asıl özü olmadığı savunuluyor. Tüm yazının okunması tavsiye ediliyor

  • "C'de generics kullanmak için neden bu kadar zorlama yapılıyor, doğrudan C++ kullanılsa olmaz mı?" sorusu soruluyor

    • Güvenlik kriterleri ve başka gereksinimler nedeniyle legacy projelerde C++'a geçişin hemen mümkün olmadığı deneyimi paylaşılıyor. Yeni projelerde standart belirlenip C++ benimsenebildiği, ancak mevcut projelerin bir süre daha C ile devam etmek zorunda olduğu düşünülüyor. Basitçe "neden C++ kullanmıyorsunuz" bakışının biraz daha bağlam duyarlı olması gerektiği söyleniyor

    • Gerçekte de C kullanılan sahalarda C++'a geçiş daha karmaşık olabilir ve daha çok sorun çıkarabilir

    • Tersine, az bir ek çabayla aynı sonucun C'de alınabildiği, bu yüzden ille de C++'a gitmeye gerek olmadığı görüşü de savunuluyor

  • Linux kernel'de gerçekten kullanılan yöntem anlatılıyor: liste bilgisini taşıyan struct list_head yapısının türe özel struct'ların içine gömülmesi deseni. İlgili referans bağlantısı veriliyor https://kernelnewbies.org/FAQ/LinkedLists

    • Linux kernel'deki LIST_HEAD_INIT, INIT_LIST_HEAD makro adlarının çok sezgisel gelmediği söyleniyor

  • "typeof on old compilers" bölümündeki kodda (list)->payload = (item); satırının aslında no-op olmadığı, liste başlığının item ile üzerine yazıldığı belirtiliyor. Beklenen davranış buysa bunun if(0) içine alınması öneriliyor

    • Örnekte union'ın struct ile değiştirildiği, bunun da israf gibi göründüğü söyleniyor. if(0) içinde ele almanın daha iyi olacağı düşünülüyor

  • D dilinde bu tür generic list yapılarının çok daha basit olduğunu gösteriyor; C preprocessor'ını sanki tırnağa çekiç vurmak gibi, çivi çakmak için ise nail gun'ın çok daha hızlı ve temiz olması gibi bir benzetmeyle C makrolarının hantallığını vurguluyor

    • Söz konusu gönderinin C hakkında olduğu, bazı projelerde de mutlaka C kullanılması gerektiği belirtiliyor

  • union ve typeof() kullanma fikri ilginç bulunuyor. Kendi deneyiminde intrusive veri yapılarında sonunda büyük makrolara sarılmış wrapper'lara ihtiyaç duyduğunu, union ve typeof ile bunun da mümkün olup olmadığını merak ettiğini söylüyor. Örnek olarak hash table wrapper kodu ve doküman bağlantıları paylaşıyor https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

  • Kendi deneysel kütüphanesinde bu tekniği zaten kullandığını paylaşıyor https://github.com/uecker/noplate/blob/main/src/list.h

    • intrusive struct, yani node yapısını verinin içine dahil ederek bir nesnenin aynı anda birden çok container'a ait olabilmesine dair fikir soruyor

  • Tür güvenliğini sağlamak için fonksiyon pointer türlerinden yararlanma fikrinin asıl mesele olduğu düşünülüyor; yaygın handle type yaklaşımı yerine bunun kullanıldığı söyleniyor. C23 standardında tür uyumluluğu sorunlarının iyileştirildiği, ilgili standart dokümanı ile güncel GCC/Clang destek durumunun paylaşıldığı belirtiliyor https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

    • Yazı sahibi olarak, asıl fikrin union kullanarak generic veri türüne tür bilgisini bağlamak olduğunu vurguluyor; fonksiyon cast'inin tek yöntem olmadığını, çeşitli alternatiflerin tartışıldığını ve dipnotlarla "typeof on old compilers" bölümünde bunların ayrıntılı ele alındığını belirtiyor