C में type-safe (Generic) data structure लिखने का तरीका

 (danielchasehooper.com)
3 पॉइंट द्वारा GN⁺ 2025-07-01 | 2 टिप्पणियां | WhatsApp पर शेयर करें
  • यह लेख C भाषा में type-safe (Generic) data structure बनाने का एक नया तरीका समझाता है
  • union का उपयोग करके type information को data structure से जोड़ने की तकनीक को linked list implementation के उदाहरण से समझाया गया है
  • मौजूदा C generic patterns (macro, void pointer, Flexible Array Member) के साथ अंतर और हर तरीके की कमियां की तुलना की गई है
  • compile-time type check संभव है, इसलिए गलत type usage को पहले ही रोका जा सकता है
  • नई तकनीक foo_list की तरह स्पष्ट और एकसमान function/data structure interface प्रदान करती है

परिचय

  • C भाषा में generic data structure को type safety के साथ बनाने का तरीका प्रस्तुत किया गया है
  • यह तकनीक union का उपयोग करके type information को compile time पर data structure से जोड़ती है
  • इसे map, array, binary tree जैसे सभी data structure पर लागू किया जा सकता है, और उदाहरण के लिए एक basic linked list implementation से समझाया गया है
  • क्योंकि बहुत से developers मानते हैं कि C में generics संभव नहीं हैं, इसलिए इसे step-by-step आसान तरीके से समझाया गया है

पारंपरिक macro-आधारित generics

  • C में generic data structure implementation का पारंपरिक तरीका macro का उपयोग करके struct और function के नाम तथा type बनाना है
  • data structure header को अलग-अलग types के लिए कई बार include करके इसे विस्तारित किया जाता है

उदाहरण:

  • type के अनुसार struct और function name बनाने के लिए macro (जैसे CONCAT, NODE_TYPE, PREPEND_FUNC) का उपयोग
  • हर type के लिए अलग function और struct बनते हैं, इसलिए int और Foo जैसे types के लिए अलग-अलग data structure definitions निकलती हैं

कमियां:

  • type और function definition कहां बनी है यह समझना कठिन होता है, क्योंकि वे macro से generate होती हैं
  • code auto-completion का फायदा लेना मुश्किल होता है
  • एक ही function की कई copies generate होने से binary size और build time बढ़ता है
  • function name में type prefix चाहिए होता है (उदाहरण: Foo_list_prepend)

generic चरण 1: void pointer तरीका

  • data structure के data type को void * रखकर उसे type-independent बनाया जाता है
  • linked list के data field को void * घोषित किया जाता है
  • type check संभव नहीं होता, इसलिए runtime पर type error हो सकता है और compile-time safety कम रहती है
  • memory और cache उपयोग अक्षम हो जाता है: node और data अलग-अलग allocate होते हैं, जिससे अनावश्यक overhead और cache miss बढ़ते हैं

generic चरण 2: inline storage (Flexible Array Member)

  • Flexible Array Member का उपयोग करके pointer store करने के बजाय data को node के साथ ही store किया जाता है
  • हर node के लिए केवल एक allocation काफी होता है, और cache में data तथा next pointer पास-पास रहते हैं
  • इस तरीके में memcpy जैसी size information पास करनी पड़ती है, लेकिन consistent memory layout के कारण performance बेहतर होती है
  • list_alloc_front function का उपयोग करने पर memcpy के बिना भी struct को सीधे initialize किया जा सकता है

generic चरण 3: type check लागू करना

  • union के payload member में parameterized type pointer घोषित करके compile time पर data structure में type information जोड़ी जाती है
  • उदाहरण: #define List(type) union { ListNode *head; type *payload; }
  • ऐसा करने पर __typeof__(foo_list.payload) से उस list का type प्राप्त किया जा सकता है
  • macro (list_prepend) में function type cast के जरिए केवल सही type होने पर ही compilation संभव होता है
  • गलत type इस्तेमाल करने पर compile time पर error होता है

error उदाहरण:

  • foo_list में int जोड़ने पर 'incompatible integer to pointer conversion' compile error message दिखाई देता है

typeof को support न करने वाले compilers के लिए

  • C23 से पहले __typeof__ standard का हिस्सा नहीं था, इसलिए कुछ compilers (जैसे पुराने MSVC) में यह काम नहीं करता
  • struct के भीतर payload member का उपयोग जैसी workaround तकनीकों से मिलता-जुलता प्रभाव हासिल किया जा सकता है

parameter passing और typedef

  • एक ही रूप वाला List(Foo) भी compiler की नज़र में अलग type माना जाता है
  • typedef का उपयोग करने पर parameter passing और assignment आसान हो जाते हैं

उदाहरण:

  • typedef List(Foo) ListFoo;
  • ListFoo variable declaration और function parameter के रूप में इस्तेमाल किया जा सकता है

समापन और अन्य data structure तक विस्तार

  • यह तकनीक कई type parameters वाले data structure (जैसे hash map) पर भी लागू की जा सकती है
  • union के माध्यम से key, value दोनों की type safety सुनिश्चित की जा सकती है
  • अधिक विस्तृत अभ्यास और macro implementation के लिए संबंधित code gist लिंक देखें

निष्कर्ष

  • यह नया तरीका पुराने तरीकों की कमियों (readability, build efficiency, maintainability) को दूर करते हुए एकसमान function naming scheme और type safety प्रदान करता है
  • अलग-अलग data structure और multiple type parameters को support करना आसान है
  • compile-time type check के जरिए generic data structure के उपयोग में safety और efficiency दोनों हासिल की जा सकती हैं

आभार

  • यह लेख Martin Fouilleul के feedback और प्रोत्साहन से पूरा हुआ

संबंधित पढ़ाई

2 टिप्पणियां

 
click 2025-07-01

क्या बस सरलता से Zig इस्तेमाल कर लें, ऐसा सवाल मन में आता है।
 
GN⁺ 2025-07-01
Hacker News राय

  • चरण 2 के कोड में uint64_t data[]; इस्तेमाल करने के तरीके पर यह आपत्ति उठाई गई कि जिन types की alignment requirement uint64_t से बड़ी है, उनके लिए यह उपयुक्त नहीं है, और छोटे types के लिए यह अनावश्यक बर्बादी है. उदाहरण के लिए 64-bit architecture के ilp32 ABI में यह और भी समस्या पैदा करता है. चरण 3 के कोड में int main() { List(Foo) foo_list = {NULL}; की जगह ऐसा लिखना चाहिए, यह राय दी गई. typeof न होने की स्थिति में return value वापस नहीं दी जा सकती, और वैकल्पिक कोड में const से जुड़ी errors आ सकती हैं, साथ ही == operator की symmetry की वजह से यह समस्या और उभरती है. payload हटा देने पर size की जानकारी नहीं रहती, इसलिए यह सुरक्षित नहीं है; उदाहरण के लिए List(int64_t) में int32_t जोड़ना ठीक लगता है, लेकिन वास्तव में int32_t का size तय नहीं किया जा सकता. इसे और सुरक्षित बनाने के लिए अतिरिक्त सुधार की ज़रूरत है. C में generics इस्तेमाल करने की दो बड़ी सीमाएँ बताई गईं: पहली, vtable delegation approach में struct के अंदर macro नहीं डाले जा सकते, इसलिए functionality सीमित हो जाती है; दूसरी, external vtable को delegate करने पर इस्तेमाल होने वाले सभी types पहले से declare करने पड़ते हैं. सबसे अच्छा तरीका यह बताया गया कि typedef declarations वाले header में केवल static functions declare की जाएँ, लेकिन GCC और Clang undefined static warning अलग-अलग timing पर देते हैं, यह भी जोड़ा गया. अंत में अलग-अलग buffer structs लेने वाले function design का उदाहरण देकर कहा गया कि const versions सहित सब कुछ manage करना पड़ता है

    • external vtable delegation issue पर किसी ने साझा किया कि पुराने project में इसे हल करने के लिए उन्होंने compiler तक बना लिया था. Apache Clownfish project की शुरुआत में .h files parse करते-करते अंत में Clownfish header (.cfh) नाम का अपना format बनाना पड़ा. असली obj के "Clone" method को call करने वाला code उदाहरण के तौर पर दिखाया गया, और बताया गया कि object-oriented features चाहिए थे dynamic language bindings के लिए, इसलिए ऐसी भारी मात्रा में code generation करनी पड़ी. Clownfish का उद्देश्य lowest common object model देना था, और binding language types भी .cfh से generate किए जाते थे. इस जटिलता की वजह से ज़्यादातर लोग void* casting के साथ type safety छोड़ देते हैं, यह भी जोड़ा गया. https://github.com/apache/lucy-clownfish

    • int main() के बारे में कहा गया कि C में int main() का मतलब है arguments की संख्या unspecified है. अगर यह बताना हो कि कोई argument नहीं है, तो int main(void) लिखना चाहिए. कई C++ लिखने वाले लोग यह बात अक्सर भूल जाते हैं, इस पर ज़ोर दिया गया

    • यह राय आई कि union से सचमुच एक संयुक्त संरचना जैसी उम्मीद होती है, यानी काश एक type खुद को किसी दूसरे type के union के हिस्से के रूप में declare कर पाता

    • malloc करते समय internal padding की वजह से calculated size वास्तविक size से छोटा हो सकता है, यह आपत्ति उठाई गई; जैसे malloc(sizeof(*node) + data_size); लिखने पर जोखिम हो सकता है

  • ट्रिक #0 का विरोध करते हुए किसी ने कहा कि उन्होंने C की पूरी dialect बनाते समय यही ट्रिक इस्तेमाल की थी. उदाहरण के तौर पर generic binary heap implementation का code साझा किया गया https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. syntax थोड़ी भारी है, लेकिन आखिर में यह एक सामान्य C struct बन जाती है, जिससे optimization और predictability में बड़ा फायदा मिलता है. उनके अनुसार दूसरी implementations में void*, runtime memory sizing, और macro definitions से बचना मुश्किल है

    • लेखक ने जवाब में कहा कि binary heap और linked list का उद्देश्य अलग है. binary heap में store करते समय data पढ़ना पड़ता है, इसलिए approach अलग होती है, और generic binary heap लिखते समय अलग चुनाव हो सकते हैं. यह भी जोड़ा कि main text के footnote में इसका ज़िक्र है

    • header-based implementation पसंद करने के कई कारण दिए गए. debugging के समय macro functions की तुलना में code trace करना और type information का उपयोग करना आसान होता है. compiler हर instance के लिए monomorphized optimization कर सकता है, इसलिए runtime cost या variable-size burden नहीं रहता. generic structs को stack पर रखा जा सकता है. लेखक द्वारा बताई गई दो समस्याओं को भी avoid किया जा सकता है: function-name macros से नाम आसानी से बदले जा सकते हैं, और weak symbols का उपयोग करके linking के समय duplicate definitions अपने-आप merge की जा सकती हैं. pointer-type generic containers में एक और समस्या है, लेकिन उसे typedef वगैरह से हल किया जा सकता है. यह भी राय दी गई कि C में intrusive data structures अब भी सुविधाजनक हैं, हालांकि debugging कठिन रहती है

    • "compiler इसे डोनट की तरह खा जाता है" वाली अभिव्यक्ति पर किसी की ज़ोरदार हँसी छूट गई

  • function type conversion में, जैसे Foo* और void* की internal representation एक जैसी मान ली जाती है, लेकिन standard C में इसकी guarantee नहीं है. types के बीच compatibility ("compatible") न होने पर ऐसा casting undefined behavior तक ले जा सकता है. compiler की alias analysis जैसी चीज़ों पर भी इसका असर पड़ सकता है, यह कहा गया (संदर्भ लिंक सहित) https://news.ycombinator.com/item?id=44421185

    • जवाब में कहा गया कि main text के footnote में इसका ज़िक्र है, और casting type safety का मुख्य बिंदु नहीं है. पूरी पोस्ट पढ़ने की सलाह दी गई

  • यह सवाल उठा: "अगर C में generics के लिए इतनी मशक्कत करनी पड़ रही है, तो सीधे C++ क्यों नहीं इस्तेमाल करते?"

    • जवाब में किसी ने अपना अनुभव साझा किया कि safety standards और अन्य requirements की वजह से legacy projects में C++ में migration तुरंत संभव नहीं होता. नए projects में standards तय करके C++ अपनाया जा सकता है, लेकिन मौजूदा projects को कुछ समय तक C में ही रहना पड़ता है. सिर्फ "C++ ही इस्तेमाल कर लो" जैसी बातों में थोड़ा ज़्यादा संदर्भ और संवेदनशीलता होनी चाहिए, यह राय दी गई

    • एक और प्रतिक्रिया में कहा गया कि व्यवहार में C इस्तेमाल करने वाली जगहों पर C++ में जाना ज़्यादा जटिल हो सकता है और अधिक समस्याएँ पैदा कर सकता है

    • इसके उलट यह तर्क भी दिया गया कि थोड़ी-सी अतिरिक्त मेहनत से C में वही परिणाम मिल सकता है, तो फिर बेवजह C++ तक जाने की ज़रूरत नहीं

  • Linux kernel में वास्तव में इस्तेमाल होने वाला एक तरीका बताया गया, जिसमें list information रखने वाला struct list_head हर type-specific struct के अंदर शामिल किया जाता है. संबंधित संदर्भ लिंक दिया गया https://kernelnewbies.org/FAQ/LinkedLists

    • किसी ने कहा कि Linux kernel के LIST_HEAD_INIT, INIT_LIST_HEAD जैसे macro names बहुत intuitive नहीं लगते

  • "typeof on old compilers" section के code में (list)->payload = (item); वास्तव में no-op नहीं है, बल्कि list head ही item से overwrite हो जाता है, यह आपत्ति उठाई गई. अगर यही इरादा था, तो इसे if(0) में लपेटना चाहिए, ऐसा सुझाव दिया गया

    • इसके साथ यह भी कहा गया कि उदाहरण में union को struct में बदला गया है, जो अपने-आप में बर्बादी लगता है. if(0) के अंदर रखना अधिक बेहतर लगता है

  • D language में ऐसी generic list structure कहीं ज़्यादा सरल है, यह दिखाया गया, और C के preprocessor की तुलना ऐसे की गई मानो नाखून पर हथौड़ा मारना हो, जबकि कील ठोकने के लिए Nail gun कहीं तेज़ और साफ़ है — इस रूपक से C macros की असुविधा पर ज़ोर दिया गया

    • जवाब में कहा गया कि वह पोस्ट C के बारे में है, और कुछ projects में C का इस्तेमाल करना अनिवार्य होता है

  • union और typeof() का इस्तेमाल करने वाला विचार दिलचस्प लगा. किसी ने कहा कि intrusive data structures में उन्हें आखिरकार बड़े macros में लिपटे wrappers की ज़रूरत पड़ती है, और पूछा कि क्या union और typeof से भी ऐसी implementation संभव है. उदाहरण के तौर पर hash table wrapper implementation का code और documentation link साझा किए गए https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

  • किसी ने साझा किया कि वे व्यक्तिगत रूप से यह technique पहले से एक experimental library में इस्तेमाल कर रहे हैं https://github.com/uecker/noplate/blob/main/src/list.h

    • उन्होंने intrusive struct, यानी data में node structure शामिल करके, किसी object को एक साथ कई containers का हिस्सा बनाने के तरीके पर विचार पूछा

  • ऐसा लगा कि function pointer के type का उपयोग करके type safety हासिल करना ही मुख्य विचार है, यानी आम तौर पर इस्तेमाल होने वाले handle type की जगह यह implementation है. C23 standard में type compatibility की समस्या बेहतर हुई है, यह बताते हुए standard document और latest GCC/Clang support status साझा किया गया https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

    • लेखक ने जवाब में ज़ोर देकर कहा कि मुख्य विचार union का उपयोग करके generic data type के साथ type information को जोड़ना है. function casting ही एकमात्र तरीका नहीं है; कई विकल्पों पर चर्चा की गई थी, और footnote तथा "typeof on old compilers" section में भी इसे विस्तार से समझाया गया है