C में type-safe generic data structures लिखने का तरीका

(danielchasehooper.com)

3 पॉइंट द्वारा GN⁺ 2025-07-01 | 2 टिप्पणियां | WhatsApp पर शेयर करें

C में भी macro, void *, flexible array member, और union को मिलाकर type-safe generic data structures बनाए जा सकते हैं, और उदाहरण में linked list को चरणबद्ध तरीके से implement करके दिखाया गया है
हर type के लिए header को कई बार include करने का तरीका सुरक्षित है, लेकिन macro-generated code की वजह से definition ढूँढना और code completion मुश्किल हो सकता है, और binary size व build time बढ़ सकते हैं
void * आधारित list लचीली होती है, लेकिन type errors को नहीं रोक पाती, और अगर node और data अलग-अलग allocate किए जाएँ तो हर node पर 2 allocations और cache misses हो सकते हैं
flexible array member से data को node के अंदर store किया जा सकता है, और List(type) को union से wrap करने पर बिना runtime cost के compile-time type information जोड़ी जा सकती है
list_prepend macro ternary operator से पास किए गए value और payload type को match कराकर compile error उत्पन्न करता है, और return pointer type के लिए __typeof__() का उपयोग किया जा सकता है

C generic implementation की शुरुआत

लक्ष्य यह है कि C में List(int), List(Foo) जैसी type-specific lists declare की जा सकें, और गलत type डालने पर वह compile ही न हो
उदाहरण में List(Foo) में Foo value डाली जा सकती है, लेकिन list_prepend(&foo_list, 7) की तरह किसी दूसरे type को डालने वाला code compile नहीं होगा
list_for(item, &foo_list) के अंदर item को Foo * type के रूप में handle किया जा सकता है

लेवल 0: generic header तरीका

एक तरीका यह है कि data structure को header में लिखा जाए, और type macro T बदलते हुए #include को कई बार चलाया जाए
list.h T के आधार पर FooListNode, Foo_list_prepend जैसे types और functions को macro से generate करता है
यह तरीका generic भी है और type-safe भी, लेकिन usability थोड़ी कठिन हो जाती है
- types और functions macro से बने होते हैं, इसलिए उनकी definition कहाँ है यह ढूँढना मुश्किल होता है
- code completion सही से काम नहीं कर सकती
- एक ही function की कॉपी हर type के लिए बनती है, जिससे binary size और build time बढ़ते हैं
- list_prepend() की जगह Foo_list_prepend(), int_list_prepend() जैसे type-prefixed functions इस्तेमाल करने पड़ते हैं
जिन generic functions में type-specific code generation चाहिए, उनके लिए यह तरीका ज्यादा उपयुक्त हो सकता है

लेवल 1: `void *` आधारित list

अगर ListNode में void *data हो, तो वह कई types का data रख सकता है
list_prepend(ListNode **head, void *data) data pointer को सीधे store कर देता है, इसलिए implementation सरल रहती है
समस्या यह है कि यह structure type-safe नहीं है
अगर node और data अलग-अलग allocate हों, तो memory और performance cost भी बढ़ती है
- एक node के लिए दो allocations चाहिए
- data pointer खुद अतिरिक्त memory लेता है
- list traverse करते समय next node access और data access, दोनों जगह cache miss हो सकती है
उदाहरण के code में परिचित होने की वजह से malloc का उपयोग किया गया है, लेकिन व्यवहार में Arena के उपयोग की सिफारिश की गई है, और संबंधित सामग्री के लिए वीडियो और लेख देखे जा सकते हैं

लेवल 2: node के अंदर data store करना

void *data की जगह Flexible Array Member का उपयोग करने पर data को node के अंदर रखा जा सकता है
struct ListNode में ListNode *next और char data[] होते हैं, और allocation के समय sizeof(* node) + data_size जितनी memory एक बार में ली जाती है
list_prepend दिए गए data और उसका size लेकर memcpy से उसे node->data में copy करता है
इस तरीके में next और असली data memory में पास-पास रहते हैं, जिससे void * तरीके वाली allocation और cache समस्याएँ कम हो जाती हैं
लेकिन caller को data_size देना पड़ता है, जो एक अतिरिक्त बोझ है
अगर memcpy से बचना हो, तो list_alloc_front node के data area का pointer return कर सकता है, और caller उस memory को सीधे initialize कर सकता है
data member की alignment, padding, और size calculation से जुड़ी समस्याएँ अलग विषय हैं, इसलिए उदाहरण में उन्हें विस्तार से नहीं लिया गया है

लेवल 3: `union` से type information जोड़ना

मुख्य तकनीक यह है कि List(type) को union के रूप में define किया जाए, और उसमें असली list head के साथ type information के लिए pointer भी रखा जाए

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

payload runtime में इस्तेमाल नहीं होता, बल्कि compile-time type information देता है
union उपयोग करने से payload अलग से memory consume नहीं करता
List(Foo) foo_list, List(int) int_list की तरह type-specific lists बनाई जा सकती हैं

ternary operator से type check करना

list_prepend macro अंदरूनी function _list_prepend को call करते समय ternary operator से item और (list)->payload के types को match कराता है

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

अगर ternary operator के दोनों candidate types match नहीं करते, तो compiler type mismatch error देता है
उदाहरण के लिए List(Foo) में Bar * पास करने पर Clang Foo * और Bar * के pointer type mismatch को error के रूप में दिखाता है
यही macro sizeof(*(list)->payload) के जरिए store होने वाले type का size भी अपने-आप पास कर देता है
असली काम _list_prepend(ListNode **head, void *data, size_t data_size) जैसे generic internal function द्वारा किया जाता है

return type के लिए `typeof()` का उपयोग

जब generic function को internal data pointer return करना हो, तब __typeof__() से void * return value को payload type में cast किया जा सकता है

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

__typeof__() को Clang, GCC, और MSVC 19.39 या उससे ऊपर support करते हैं
C23 में standard में शामिल होने से पहले __typeof__() एक optional extension था
MSVC 19.39 से पहले जैसे compilers में जहाँ __typeof__() नहीं है, वहाँ ternary operator आधारित type check का उपयोग किया जा सकता है
type-safe return भी payload के जरिए allocation तरीके से संभव है, लेकिन उसकी विस्तृत implementation यहाँ नहीं दी गई है

पुराने तरीके और definition से जुड़ी सावधानियाँ

पुराने तरीके में _list_prepend को __typeof__((list)->payload) वाले function pointer type में cast करके call किया जाता था
इस तरह cast किए गए function pointer को call करना तकनीकी रूप से undefined behavior है, लेकिन आधुनिक compilers और आधुनिक platforms पर व्यवहार में समस्या नहीं मानी जाती
मौजूदा तरीका function pointer cast की जगह ternary operator type matching से error उत्पन्न करता है

`List(Foo)` को argument के रूप में पास करने की समस्या

C compiler एक जैसी structure रखने वाली दो List(Foo) definitions को हमेशा एक ही type नहीं मानता

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

अगर function argument के रूप में void my_function(List(Foo) list) define किया जाए और my_function(a) call किया जाए, तब भी incompatible type error आ सकती है
इसका समाधान typedef से type name देना है

typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

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

local variables में List(Foo) local_foo_list जैसा रूप अब भी इस्तेमाल किया जा सकता है
GCC 15 और 2025 के अंत के Clang में rule change के कारण एक ही tag name वाले structurally identical types को same type माना जाएगा

list के बाहर के data structures पर भी लागू

यही तकनीक सिर्फ list नहीं, बल्कि map, array, binary tree जैसे कई data structures पर लागू की जा सकती है
जिन data structures में कई related types चाहिए, वहाँ भी इसे बढ़ाया जा सकता है
उदाहरण के लिए hash map में internal structure, key type, और value type को union के अंदर साथ रखा जा सकता है

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

stb_ds.h भी type-safe generic data structures का एक उदाहरण है, लेकिन उसमें arrays और maps C arrays का उपयोग करते हैं, इसलिए कुछ type errors value pass करते समय नहीं बल्कि array assignment के समय पकड़ी जाती हैं

2 टिप्पणियां

click 2025-07-01

क्या बस सरलता से Zig इस्तेमाल कर लें, ऐसा सवाल मन में आता है।

GN⁺ 2025-07-01

Hacker News की राय

लेवल 2 कोड में uint64_t data[]; उन types के लिए गलत है जिनकी alignment requirements uint64_t से बड़ी हैं, और छोटे types के लिए यह बेकार में जगह खर्च करता है। उदाहरण के लिए 64-bit architecture पर ilp32 ABI ऐसा ही मामला है
लेवल 3 कोड int main() { List(Foo) foo_list = {NULL}; होना चाहिए
typeof न होने पर workaround से कुछ भी return नहीं किया जा सकता, और == symmetric होने की वजह से यह workaround const से जुड़ी गलतियों को भी allow कर देता है
payload को भी सुरक्षित तरीके से हटाया नहीं जा सकता। सही size जानने के लिए यह जरूरी है। List(int64_t) में int32_t जोड़ने की कोशिश करना संभव होना चाहिए, लेकिन उस int32_t का sizeof पता नहीं चल सकता। इस code के सही से काम करने के लिए अभी काफी चीजें missing हैं
मौजूदा C generics में दो बड़ी सीमाएँ हैं। पहली, vtable को delegate करने वाले तरीके में struct macro नहीं रख सकता, केवल functions रख सकता है, इसलिए capability सीमित हो जाती है। दूसरी, overhead से बचना हो तो external vtable को delegate करना पड़ता है, और उसके लिए vtable इस्तेमाल करने वाले सभी types को forward declare करना पड़ता है
अब तक मुझे सबसे अच्छा तरीका यह मिला कि forward header में, जहाँ typedef declare होता है, static functions को सिर्फ declare कर दिया जाए और define न किया जाए। असल में जब किसी translation unit में किसी खास type का header include नहीं किया जाता, तो “undefined static” warning किस stage पर आती है, यह GCC और Clang में अलग है
उदाहरण के लिए, अलग-अलग headers से आए struct SizedBuffer {void *p; size_t len;}; या struct BoundedBuffer {void *begin; void *end;};, और इनके respective const versions, सभी को स्वीकार करने वाले function की कल्पना करें
- external vtable को delegate करने के लिए vtable इस्तेमाल करने वाले सभी types को forward declare करना पड़ता है—इसी समस्या के कारण, जिस Apache Clownfish project में मैंने पहले काम किया था, उसमें हमने इसके लिए compiler तक बना लिया था
  शुरुआत में .h files parse की थीं, लेकिन अंत में लगा कि .cfh “Clownfish Header” नाम की छोटी header language बनाना बेहतर है
  parent class Obj में defined Clone method का CharBuf version call करने के लिए ऐसा code generate किया था
  
  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);
  }
  
  इस्तेमाल इस तरह किया था
  
  cfish_CharBuf *charbuf = cfish_CharBuf_new();
  cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);
  
  Clownfish का उद्देश्य कई dynamic language bindings के लिए minimum common denominator object model देना था, और .cfh files binding languages के लिए types derive करने में भी इस्तेमाल होती थीं। फिर भी, बताई गई समस्या से बचने के लिए generate किए गए boilerplate code की मात्रा सचमुच बेतुकी रूप से ज्यादा थी
  इसलिए लगभग हर कोई type safety छोड़कर call target पर सीधे void* casting इस्तेमाल कर लेता है
  https://github.com/apache/lucy-clownfish
- C में int main() का मतलब यह नहीं है कि arguments नहीं लेते, बल्कि इसका मतलब है कि अज्ञात संख्या के arguments लेते हैं। arguments नहीं लेते, यह बताने के लिए int main(void) लिखना चाहिए। C++ इस्तेमाल करने वाले लोग यह बात अक्सर भूल जाते हैं
- अच्छा होता अगर union को associatively extend किया जा सकता। यानी किसी type को सभी possible types को पहले से एक जगह declare किए बिना, खुद को दूसरे types के साथ उसी union का हिस्सा घोषित करने का तरीका मिलता
- malloc(sizeof(*node) + data_size); भी padding की वजह से समस्या पैदा कर सकता है। calculated size बहुत छोटा निकल सकता है
असहमत हूँ
लेख में बताए trick#0 से मैंने कभी C dialect पूरा बनाया था। उदाहरण के लिए generic binary heap यहाँ है: https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h
syntax थोड़ा भारी है, लेकिन अंत में जो मिलता है वह plain, predictable और optimize करने में आसान सामान्य C struct होता है—यह ऐसा code है जिसे compiler डोनट की तरह आसानी से पचा लेगा
दूसरी approaches में आखिरकार void* और runtime memory size calculation चाहिए होता है, और macros तो वैसे भी define करने पड़ते हैं
- लेखक हूँ। binary heap और linked list के use cases अलग हैं। binary heap को सही से store करने के लिए डाले जा रहे data को पढ़ना पड़ता है, लेकिन linked list में इसकी जरूरत नहीं होती
  अगर generic binary heap इस्तेमाल कर रहा होता तो शायद options को अलग तरह से तौलता। footnote में भी इस बात का जिक्र किया था
- header implementation पसंद करने की सचमुच कई वजहें हैं। macro function के उलट, header code में debugger से step into किया जा सकता है, और debugger को दिखने वाली type information भी बेहतर होती है, इसलिए debugging बेहतर रहती है
  हर instance monomorphized होता है, इसलिए compiler optimization की गुंजाइश भी ज्यादा होती है, और variable size की वजह से runtime cost नहीं देनी पड़ती। fixed size होने से generic struct को stack पर भी रखा जा सकता है
  लेखक ने जिन समस्याओं का जिक्र किया है, उनमें कम से कम दो को workaround किया जा सकता है। नामों को simple name mangling macro से Bar_func(args…) से func(Bar)(args…) में बदला जा सकता है। binary bloat को weak symbols इस्तेमाल करके कुछ कम किया जा सकता है, ताकि link time पर translation units के बीच shared functions की duplication हट जाए
  pointer type के generic containers में अलग problems हैं, लेकिन typedef या type alias से workaround किया जा सकता है
  C में intrusive data structures अब भी ज्यादा सुविधाजनक हैं, लेकिन debugger में उनसे निपटना कष्टदायक है
फ़ंक्शन type casting यह मानकर चलती है कि item pointer type, जैसे Foo*, का representation void* जैसा ही होगा, लेकिन C standard इसकी गारंटी नहीं देता। Standard की भाषा में ये दोनों types “compatible” नहीं हैं
इसलिए बदले हुए type से फ़ंक्शन call करना undefined behavior है। Pointer representation संयोग से समान हो, तब भी यह compiler के alias analysis को प्रभावित करता है। इस बारे में [0] भी देखने लायक है
अलग-अलग argument types के साथ फ़ंक्शन को cast करना generic call की type safety का मूल लगता है, लेकिन पता नहीं यह ठीक की जा सकने वाली समस्या है या नहीं
https://news.ycombinator.com/item?id=44421185
- इसे footnote में cover किया गया है। Casting type safety का core नहीं है। पूरा लेख पढ़कर देखिए
अगर “generics वाला C” चाहिए, तो इतनी घुमावदार राह लेने के बजाय बस C++ इस्तेमाल कर लेना चाहिए, नहीं?
- क्योंकि मैं safety regulation और दूसरे quality assurance में बंधे legacy project पर काम करता हूँ। अगले release की बात छोड़िए, दसवें release में भी C++ में port किया हुआ solution यूँ ही ship नहीं कर सकते। इसलिए जब तक यह संभव न हो, किसी तरह चीज़ों को चलाते रहना पड़ सकता है
  हालांकि नए projects के लिए C++ इस्तेमाल करने के standards और expectations तय किए जा सकते हैं, और हम सच में ऐसा करते हैं और किसी खास std को target करने का निर्णय लेते हैं
  Hacker News पर ऐसा रवैया काफी बार दिखता है, जो “अपनी skill बढ़ाओ” जैसा लगता है। मुझे लगता है इसमें कहीं ज़्यादा context चाहिए
- क्योंकि C के कई use cases में C++ पर switch करना उलटे और ज़्यादा workaround मांगता है
- कुछ लोग C++ से हद तक नफ़रत करते हैं, इसलिए इस तरह का काम लगातार सामने आता रहता है
  Microsoft ने Linux और free/open source software के प्रति नया रुझान दिखाने के बाद भी “C++ ही भविष्य है” वाली स्थिति से पीछे हटना सच में निराशाजनक था
  https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
  https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
  आजकल government और cyber regulations की वजह से Microsoft में C और C++ को लेकर नई policy आ गई है, इसलिए अब यह बहुत मायने नहीं रखता
  https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
  https://blogs.windows.com/windowsexperience/2024/11/19/windo...
- असली जवाब यह है कि यह ज़्यादा मज़ेदार है
- अगर C में कुछ workarounds से वही नतीजा मिल सकता है, तो C++ क्यों इस्तेमाल करें
शानदार trick है। मैं इसे अपनी experimental library में भी पहले से इस्तेमाल कर रहा हूँ https://github.com/uecker/noplate/blob/main/src/list.h
- अगर कोई यह जान सकता है तो शायद आप ही होंगे: क्या यह तरीका intrusive data structures पर भी apply करने का कोई तरीका दिखता है?
  यानी अभी की तरह node के अंदर data रखने के बजाय data के अंदर node struct रखना, और साथ में एक object को कई containers में डाल पाने की सुविधा देना
“Structurally identical types को GCC 15 और 2025 के उत्तरार्ध वाले Clang में rule changes की वजह से same type माना जाता है” वाले हिस्से पर सावधानी चाहिए
नए rules में same type माने जाने वाले सिर्फ़ tagged unions हैं, और उनका structure भी समान और tag भी समान होना चाहिए
List(T) macro को हर अलग T के लिए अलग tag generate करने के लिए बदलना होगा। Simple one-word type के लिए ## से यह आसान है, लेकिन char pointer, यानी string जैसी थोड़ी भी complex चीज़ में यह असंभव हो जाता है
बेशक List में इस्तेमाल करने से पहले सभी types को typedef करने के लिए मजबूर किया जा सकता है, लेकिन इससे generic उपयोगिता काफी घट जाती है

typedef char *str;
List(str) my_list_of_str;
List(str) tokenize(str input) {...}
- “सिर्फ़ tagged union को same type माना जाता है” वाली बात समझ नहीं आई। Tagged union तो बस एक design pattern नहीं है क्या
“ऐसा member जो कुछ नहीं करता और सिर्फ़ type रखता है” के लिए आम term मुझे type witness लगती है। लेकिन हैरानी की बात है कि type witness से जुड़ा literature काफी कम है
- जब कोई type variable होता है जो actual variable के type में बिल्कुल इस्तेमाल नहीं होता, तो उसके लिए phantom type नाम का मिलता-जुलता term है
  मैंने इसे ज़्यादातर Haskell में देखा है, और Scala में भी actual type system में मौजूद न होने वाली type hierarchy की नकल करने के लिए इस्तेमाल किया है
  एक तरह से यह union trick भी phantom type जैसी है, क्योंकि helper type वास्तव में बिल्कुल इस्तेमाल नहीं होता
Linux kernel में इस्तेमाल होने वाला तरीका भी है। इसमें type-specific struct के अंदर list information वाला struct list_head embed किया जाता है
https://kernelnewbies.org/FAQ/LinkedLists
- LIST_HEAD_INIT और INIT_LIST_HEAD नाम confusing हैं
अगर ऐसा करना पड़े, तो मैं सीधे C++ templates ही इस्तेमाल करूँगा
D में इसे ऐसे किया जा सकता है

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

T!int node;

C preprocessor से क्यों जूझना पड़े? preprocessor macro इस्तेमाल करना फिनिश कारपेंट्री में nail gun की जगह हथौड़ा इस्तेमाल करने जैसा है। nail gun 10 गुना तेज़ होती है, हर बार कील को सटीक जगह ठोकती है, और काम पर आधे-चाँद जैसे निशान भी नहीं छोड़ती

यह लेख C के बारे में है। कुछ projects में C का इस्तेमाल करना ज़रूरी होता है
सिर्फ़ हथौड़ा ही नहीं, punch भी साथ में इस्तेमाल किया जा सकता है। molding nail को हथौड़े से लगभग 1/8 inch बाकी छोड़कर ठोकें, फिर punch से उसे पूरा अंदर कर दें