引用: http://www.oschina.net/translate/coroutines-in-c 這里有一個(gè)簡(jiǎn)單的解壓過程的代碼片段和一個(gè)同樣簡(jiǎn)單的解析代碼片段:
|
![]()
繆斯的情人
|
每個(gè)代碼片段都很簡(jiǎn)單,通俗易懂。一個(gè)通過調(diào)用emit()方法每次產(chǎn)生一個(gè)字節(jié);另一個(gè)調(diào)用getchar()每次獲取一個(gè)字節(jié)。如果只通過調(diào)用emit()和getchar()就能彼此間提交數(shù)據(jù),那么就能簡(jiǎn)單的把兩個(gè)代碼片段連接到一起,因此也就能把解壓的輸出直接傳遞到解析部分。
在很多現(xiàn)在操作系統(tǒng)中,你可以使用管道在兩個(gè)進(jìn)程間通信或者兩個(gè)線程emit()——在解壓代碼中寫入管道,在解析代碼中使用getchar()從另一端相同的管道中讀取。簡(jiǎn)單強(qiáng)壯,但是也重量不可移植。通常你不想把你的一個(gè)簡(jiǎn)單程序分到線程中。 在這篇文章中我提供了一個(gè)創(chuàng)造性的解決方案來處理這個(gè)構(gòu)造的問題。 |
![]()
繆斯的情人
|
重寫常見的方式是重寫末端的通信管道,把它作為一個(gè)可調(diào)用的函數(shù)。這有個(gè)簡(jiǎn)單的例子。
當(dāng)然你不需要兩個(gè)都重寫;只修改一個(gè)就可以。如果把解壓片段重寫為以上形式,那么每次調(diào)用它都返回一個(gè)字符,原始的解析代碼片段中就可以把調(diào)用getchar()改為調(diào)用decompressor(),這樣程序看起來舒心多了。相反的,如果把解析代碼重寫為上面的形式,那么每次調(diào)用都會(huì)輸入一個(gè)字符,原始的解壓代碼中可以通過調(diào)用parser()替換掉了調(diào)用emit()。如果你是個(gè)貪婪的人你可以把兩個(gè)函數(shù)都重寫,都作為被調(diào)用者。 |
![]()
繆斯的情人
|
這就是我的真實(shí)觀點(diǎn)。和兩個(gè)重寫后的函數(shù)相比原始的代碼丑陋無比,在這里當(dāng)兩個(gè)進(jìn)程被寫為調(diào)用者而不是被調(diào)用者時(shí)更易讀了。如果你試圖通過解析器推斷出語(yǔ)法,或者通過解壓器了解解壓數(shù)據(jù)格式,只需閱讀下代碼就可以,同時(shí)你會(huì)發(fā)現(xiàn)原始的代碼清晰些,重寫后的代碼格式上不太清晰,如果沒有嵌入另外一者的代碼這會(huì)更好些。 |
![]()
繆斯的情人
|
Knuth協(xié)程在《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》中,Donald Knuth提供了一個(gè)解決這類問題的方法。他的方法是徹底丟掉堆棧的概念,不要再想一個(gè)進(jìn)程作為調(diào)用者,另一個(gè)作為被調(diào)用者,把他們當(dāng)做平等的協(xié)作者關(guān)系。 實(shí)際上就是:把傳統(tǒng)的“調(diào)用”稍微改為一個(gè)不同的方式。新的“調(diào)用”將在某個(gè)地方保存返回值而不是堆棧上,并且還能跳轉(zhuǎn)到另一個(gè)保存返回值的指定位置上。因此,解碼器每次生成一個(gè)字符,就保存它的程序計(jì)數(shù)器并且跳轉(zhuǎn)到上次解析器的位置-解析器每次都需要一個(gè)新的字符,它保存自己的程序計(jì)數(shù)器并且跳轉(zhuǎn)到上次解碼器的位置。程序可以在兩個(gè)函數(shù)之間來回自如的傳遞需要的數(shù)據(jù)了。 |
![]()
繆斯的情人
|
理論上看起來很美,但實(shí)際中你卻只能在匯編語(yǔ)言中使用,因?yàn)橥ㄓ玫母呒?jí)語(yǔ)言沒有一個(gè)支持調(diào)用原始的協(xié)程。像類似于C的都是依賴于基礎(chǔ)的堆棧結(jié)構(gòu),因此當(dāng)在函數(shù)間進(jìn)行數(shù)據(jù)傳遞時(shí),一個(gè)必須作為調(diào)用者,領(lǐng)一個(gè)必須作為被調(diào)用者。所以如果你想寫可移植的代碼,這種技術(shù)和Unix管道一樣不切實(shí)際。
|
![]()
繆斯的情人
|
基于棧的協(xié)程我們真正想要的是在C中模仿Knuth協(xié)程調(diào)用原語(yǔ)的能力。我們必須接受這個(gè)現(xiàn)實(shí),在C語(yǔ)言中,一個(gè)函數(shù)將作為調(diào)用者,另一個(gè)作為被調(diào)用者。對(duì)于調(diào)用者我們沒有任何問題;我們按照原始算法寫代碼就可以,無論什么時(shí)候,如果它生成一個(gè)字符那么它就需要調(diào)用另一個(gè)函數(shù)。 被調(diào)用者有很多問題。對(duì)于被調(diào)用者,我們想要一個(gè)函數(shù),該函數(shù)具有“返回并繼續(xù)”的操作:從函數(shù)返回后,當(dāng)再次調(diào)用它,只需要在上次位置繼續(xù)執(zhí)行就可以。比如,我們希望寫這樣一個(gè)函數(shù) int function(void) { int i; for (i = 0; i < 10; i++) return i; /* won't work, but wouldn't it be nice */ } 連續(xù)調(diào)用這個(gè)函數(shù)10次,返回0-9的數(shù)字。 |
![]()
繆斯的情人
|
我們?cè)趺茨軐?shí)現(xiàn)這個(gè)呢?好吧,我們可以用一個(gè)goto語(yǔ)句將控制跳轉(zhuǎn)到這個(gè)函數(shù)中的任何一點(diǎn)。所以如果我們有一個(gè)狀態(tài)變量,我們可以這樣做: int function(void) { static int i, state = 0; switch (state) { case 0: goto LABEL0; case 1: goto LABEL1; } LABEL0: /* start of function */ for (i = 0; i < 10; i++) { state = 1; /* so we will come back to LABEL1 */ return i; LABEL1:; /* resume control straight after the return */ } }這個(gè)方法可以奏效。在一些我們可能需要恢復(fù)控制的地方,我們擁有一組標(biāo)簽:一個(gè)在開始位置,其他的緊跟著每個(gè)返回語(yǔ)句。我們有一個(gè)保留在函數(shù)調(diào)用之間的狀態(tài)變量,它指明了下一步我們需要恢復(fù)控制那個(gè)標(biāo)簽。在任何返回之前,我們會(huì)更新狀態(tài)變量到正確的標(biāo)簽位;任何調(diào)用之后,我們會(huì)對(duì)這個(gè)變量的值做一個(gè)switch操作來查看它當(dāng)前進(jìn)行到哪里。 |
![]()
jimmyjmh
|
雖然這樣,它還是比較丑。最糟糕的的部分是,這一組標(biāo)簽必須手動(dòng)維護(hù),并且在函數(shù)體和初始的switch語(yǔ)句之間保持一致。每次新增一個(gè)返回語(yǔ)句,我們必須引進(jìn)一個(gè)新表簽名并把它加到switch列表中;而每次刪除一個(gè)返回語(yǔ)句,我們又必須移除相應(yīng)的標(biāo)簽。剛剛我們只是考慮一個(gè)因素增加的兩倍維護(hù)工作量。
|
![]()
jimmyjmh
|
達(dá)夫設(shè)備(Duff's Device)
C語(yǔ)言中著名的"達(dá)夫設(shè)備"利用case語(yǔ)句在其匹配switch語(yǔ)句子塊中也是合法的這一事實(shí)。Tom Duff利用這個(gè)方法優(yōu)化輸出回路: switch (count % 8) { case 0: do { *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; } while ((count -= 8) > 0); }我們可以稍加變動(dòng)將它應(yīng)用到協(xié)同程序技巧上。我們可以用switch語(yǔ)句本身執(zhí)行跳轉(zhuǎn),而不是用它來確定跳到哪里去執(zhí)行。 int function(void) { static int i, state = 0; switch (state) { case 0: /* start of function */ for (i = 0; i < 10; i++) { state = 1; /* so we will come back to "case 1" */ return i; case 1:; /* resume control straight after the return */ } } }現(xiàn)在這看起來更理想了。我們現(xiàn)在需要做的只是構(gòu)造一些精確宏,并且可以把細(xì)節(jié)隱藏到這些似是而非的定義里: #define crBegin static int state=0; switch(state) { case 0: #define crReturn(i,x) do { state=i; return x; case i:; } while (0) #define crFinish } int function(void) { static int i; crBegin; for (i = 0; i < 10; i++) crReturn(1, i); crFinish; } |
![]()
jimmyjmh
|
這差不多就是我們想要的了。我們可以通過這種一返回就控制下一個(gè)調(diào)用回復(fù)的方式,用crReturn從函數(shù)返回。當(dāng)然,我們必須遵守一些基本規(guī)則(用crBegin和crFinish包住函數(shù)體;聲明所需的所有保存在acrReturn中的靜態(tài)局部變量;絕不要在一個(gè)顯式switch語(yǔ)句中設(shè)置一個(gè)crReturn);但那些并不會(huì)限制我們太多。 剩下的唯一問題是傳給crReturn的第一個(gè)參數(shù)。就像在上一節(jié)引進(jìn)一個(gè)新標(biāo)簽一樣,我們必須避免與已存在的標(biāo)簽名沖突,確保所有給crReturn的狀態(tài)參數(shù)都是不同的。這影響是相當(dāng)小的 -- 編譯器會(huì)抓住它并并不讓它在運(yùn)行時(shí)出錯(cuò) -- 但我們還是要避免這樣做。 |
![]()
jimmyjmh
|
雖然這可以解決,ANSI C還是提供了擴(kuò)展到當(dāng)前行號(hào)的專門的宏名:__LINE__,因此我們可以把crReturn重寫成:
#define crReturn(x) do { state=__LINE__; return x; \ case __LINE__:; } while (0)而且只要遵守第四條基本規(guī)則,我們就不再需要擔(dān)心這些狀態(tài)參數(shù)了(決不在同一行寫兩個(gè)crReturn語(yǔ)句)。 |
![]()
jimmyjmh
|
評(píng)估現(xiàn)在我們有了這個(gè)畸形的東西,讓我們來重寫下原始的代碼片段吧。
我們已經(jīng)重寫了解碼器和解析器都作為了被調(diào)用者,不需要像最后一次那樣大規(guī)模的重寫。每個(gè)函數(shù)的結(jié)構(gòu)恰好是原始結(jié)構(gòu)的鏡像,讀者能夠通過解析器推斷出相應(yīng)的語(yǔ)法,或者通過解碼器了解到解壓數(shù)據(jù)格式,比起讀那些狀態(tài)機(jī)代碼簡(jiǎn)單多了。一旦你適應(yīng)了新的格式,你就會(huì)發(fā)現(xiàn)控制流程非常直觀:當(dāng)解壓器產(chǎn)生一個(gè)字符,它就調(diào)用crReturn將這個(gè)字符傳給調(diào)用函數(shù),并等待當(dāng)需要下一個(gè)字符時(shí)再次被調(diào)用。當(dāng)解析器需要一個(gè)新字符時(shí),它通過crReturn返回,并等待下一次被調(diào)用時(shí)通過參數(shù)c傳入新的字符。 |
![]()
繆斯的情人
|
這里代碼里還有一個(gè)小的結(jié)構(gòu)變化:parser()中g(shù)etchar()放在了循環(huán)的結(jié)尾而不是開頭了,這是因?yàn)楫?dāng)進(jìn)入函數(shù)時(shí),第一個(gè)字符已經(jīng)通過c傳進(jìn)來了。我們應(yīng)該可以接受這個(gè)小的結(jié)構(gòu)改變,或者如果我們真的對(duì)此抱有輕盈態(tài)度,我們可以認(rèn)為在parse()傳入數(shù)據(jù)前,需要一次“初始化”調(diào)用。 當(dāng)然像前面一樣,我們不必把兩個(gè)函數(shù)都使用協(xié)程的宏重寫,修改一個(gè)足矣;另一個(gè)可以作為他的被調(diào)用者。 我們已經(jīng)取得了我們想要達(dá)到的目標(biāo):一個(gè)可移植的ANSI C在生產(chǎn)者和消費(fèi)者之間傳遞數(shù)據(jù),而不用狀態(tài)機(jī)重寫代碼。我們已經(jīng)通過把一個(gè)switch語(yǔ)句的生僻的功能結(jié)合C的預(yù)處理創(chuàng)建一個(gè)隱式的狀態(tài)機(jī)。 |
![]()
繆斯的情人
|
編碼規(guī)范當(dāng)然,這種方式違背了書上的編碼規(guī)范,在公司代碼中嘗試這樣使用你會(huì)受到嚴(yán)厲的警告!在宏定義中,你的大括號(hào)沒有完全匹配,子區(qū)塊中使用了case,至于crReturn宏中內(nèi)容不完整···使用這種不負(fù)責(zé)任的編碼實(shí)踐你沒有被解雇真是一種奇跡。你應(yīng)該感到自行慚愧。 我需要聲明下編碼規(guī)范在這里不適用。在這篇文章里我展示的例子不是很長(zhǎng),也不復(fù)雜,即使使用狀態(tài)機(jī)重寫也能看懂。但是隨著函數(shù)變長(zhǎng),重寫的難度越來愈大,并且失去了代碼清晰度,越來越糟糕。 |
![]()
繆斯的情人
|
考慮下,如果一個(gè)函數(shù)有下面的代碼塊構(gòu)成 case STATE1: /* perform some activity */ if (condition) state = STATE2; else state = STATE3; 對(duì)于讀者來說從函數(shù)建立下面的小模塊也不是很難 LABEL1: /* perform some activity */ if (condition) goto LABEL2; else goto LABEL3; 一個(gè)調(diào)用者,一個(gè)被調(diào)用者。是的,這兩個(gè)函數(shù)在可視結(jié)構(gòu)上是一樣的,它們提供的底層算法都非常少。因?yàn)槭褂脜f(xié)程宏想要解雇你的人同樣會(huì)因?yàn)槟銓懙倪B接goto語(yǔ)句的小塊函數(shù)而怒斥你!這次它們做對(duì)了,因?yàn)檫@樣的函數(shù)布局破壞了算法的結(jié)構(gòu)。 |
![]()
繆斯的情人
|
編程規(guī)范目標(biāo)就是為了清晰。像switch,return和case語(yǔ)句把這些重要的東西隱藏到“不清晰”的宏中,從編程標(biāo)準(zhǔn)角度來看你已經(jīng)破壞了程序的語(yǔ)法結(jié)構(gòu),違背了代碼清晰的要求。但是我們這樣做是為了突出程序的算法結(jié)構(gòu),而算法結(jié)構(gòu)也正好是讀者想要了解的! 任何的編碼規(guī)范堅(jiān)持語(yǔ)法的清晰度而犧牲了算法的清晰度都應(yīng)該被重寫。如果你的老板因?yàn)槭褂眠@個(gè)技巧而解雇你,當(dāng)安保人員把你拖走時(shí)要不斷告訴他們。 |
![]()
繆斯的情人
|
風(fēng)騷般的編碼在正兒八經(jīng)的應(yīng)用程序中,協(xié)程很少使用,因?yàn)樗蕾囉陟o態(tài)變量,因此不能重入或者支持多線程。理想情況下,在真實(shí)應(yīng)用程序中,你可能想在多個(gè)不同的上下文中調(diào)用同一個(gè)函數(shù),并且在給定的一個(gè)上下文中每次調(diào)用時(shí),都能在這個(gè)上下文中上一次返回的位置繼續(xù)執(zhí)行。 這很容易做到,我們?cè)黾右粋€(gè)新的函數(shù)參數(shù)——一個(gè)上下文結(jié)構(gòu)的指針;我們將所有的局部變量和協(xié)程用到的狀態(tài)變量都聲明成結(jié)構(gòu)體中的元素. |
![]()
繆斯的情人
|
這樣寫丑了點(diǎn),因?yàn)橥蝗婚g你不得不使用ctx->i作為循環(huán)計(jì)數(shù)器而不是之前使用的i;事實(shí)上所有重要的變量都成了協(xié)程上下文結(jié)構(gòu)體中的元素。但是這消除了重入的問題,并且沒有影響到程序的結(jié)構(gòu)。 (當(dāng)然,要是C有Pascal語(yǔ)言的with語(yǔ)句,我們就可以將這個(gè)間接的引用隱藏掉,但是很遺憾沒有這些。對(duì)于C++語(yǔ)言,我們可以把協(xié)程的兩個(gè)函數(shù)設(shè)計(jì)成類的成員函數(shù),所有的局部變量設(shè)計(jì)成類的成員變量,從而將作用域的問題隱藏掉) |
![]()
繆斯的情人
|
這兒包含的C語(yǔ)言頭文件實(shí)現(xiàn)了一套預(yù)定義的協(xié)程使用的宏。在文件中定義了二套宏函數(shù),前綴分別是scr和ccr。scr宏是一套簡(jiǎn)單的實(shí)現(xiàn),用于可以使用靜態(tài)變量的情況;ccr宏更高級(jí)一些,能支持重入。在頭文件的注釋中有完整的說明。 需要注意的是,VC++ 6并不喜歡這種協(xié)程技巧,因?yàn)槠淠J(rèn)的debug狀態(tài)(Program Database for Edit and Continue)對(duì)__LINE__宏的支持有點(diǎn)兒怪。如果想用VC++ 6編譯一個(gè)使用了協(xié)程的宏,你就要關(guān)掉Edit and Continue。(在project settings中,選擇c/c++標(biāo)簽,在General中,將Debug info改為Program Database for Edit and Continue之外的其他值)。 (這個(gè)頭文件是MIT許可的,所以你可以任意使用,沒有任何限制。如果你發(fā)現(xiàn)MIT對(duì)你的使用方式有限制,可以給我發(fā)郵件,我會(huì)考慮給你授權(quán)。) 使用 這個(gè)鏈接 獲得coroutine.h。 感謝您的閱讀。分享才有快樂! |
![]()
繆斯的情人
|
參考文獻(xiàn)
|