• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            S.l.e!ep.¢%

            像打了激速一樣,以四倍的速度運(yùn)轉(zhuǎn),開心的工作
            簡單、開放、平等的公司文化;尊重個性、自由與個人價值;
            posts - 1098, comments - 335, trackbacks - 0, articles - 1
              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            Coroutines in C

            Posted on 2013-05-19 16:07 S.l.e!ep.¢% 閱讀(886) 評論(1)  編輯 收藏 引用 所屬分類: C++

            引用: http://www.oschina.net/translate/coroutines-in-c

            我們都知道構(gòu)建一個大型的程序是一件非常困難的工作。一個經(jīng)常面臨的問題來自于此:如果你有一個代碼片段用來生產(chǎn)數(shù)據(jù),另一個代碼片段來調(diào)用它,哪一個是調(diào)用者,哪一個是被調(diào)用者呢?

            這里有一個簡單的解壓過程的代碼片段和一個同樣簡單的解析代碼片段:

            /* Decompression code */
                while (1) {
                    c = getchar();
                    if (c == EOF)
                        break;
                    if (c == 0xFF) {
                        len = getchar();
                        c = getchar();
                        while (len--)
                            emit(c);
                    } else
                        emit(c);
                }
                emit(EOF);
            /* Parser code */
                while (1) {
                    c = getchar();
                    if (c == EOF)
                        break;
                    if (isalpha(c)) {
                        do {
                            add_to_token(c);
                            c = getchar();
                        } while (isalpha(c));
                        got_token(WORD);
                    }
                    add_to_token(c);
                    got_token(PUNCT);
                }


            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            每個代碼片段都很簡單,通俗易懂。一個通過調(diào)用emit()方法每次產(chǎn)生一個字節(jié);另一個調(diào)用getchar()每次獲取一個字節(jié)。如果只通過調(diào)用emit()和getchar()就能彼此間提交數(shù)據(jù),那么就能簡單的把兩個代碼片段連接到一起,因此也就能把解壓的輸出直接傳遞到解析部分。

            在很多現(xiàn)在操作系統(tǒng)中,你可以使用管道在兩個進(jìn)程間通信或者兩個線程emit()——在解壓代碼中寫入管道,在解析代碼中使用getchar()從另一端相同的管道中讀取。簡單強(qiáng)壯,但是也重量不可移植。通常你不想把你的一個簡單程序分到線程中。

            在這篇文章中我提供了一個創(chuàng)造性的解決方案來處理這個構(gòu)造的問題。
            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            重寫

            常見的方式是重寫末端的通信管道,把它作為一個可調(diào)用的函數(shù)。這有個簡單的例子。

            int decompressor(void) {
                static int repchar;
                static int replen;
                if (replen > 0) {
                    replen--;
                    return repchar;
                }
                c = getchar();
                if (c == EOF)
                    return EOF;
                if (c == 0xFF) {
                    replen = getchar();
                    repchar = getchar();
                    replen--;
                    return repchar;
                } else
                    return c;
            }
            void parser(int c) {
                static enum {
                    START, IN_WORD
                } state;
                switch (state) {
                    case IN_WORD:
                    if (isalpha(c)) {
                        add_to_token(c);
                        return;
                    }
                    got_token(WORD);
                    state = START;
                    /* fall through */
            
                    case START:
                    add_to_token(c);
                    if (isalpha(c))
                        state = IN_WORD;
                    else
                        got_token(PUNCT);
                    break;
                }
            }

            當(dāng)然你不需要兩個都重寫;只修改一個就可以。如果把解壓片段重寫為以上形式,那么每次調(diào)用它都返回一個字符,原始的解析代碼片段中就可以把調(diào)用getchar()改為調(diào)用decompressor(),這樣程序看起來舒心多了。相反的,如果把解析代碼重寫為上面的形式,那么每次調(diào)用都會輸入一個字符,原始的解壓代碼中可以通過調(diào)用parser()替換掉了調(diào)用emit()。如果你是個貪婪的人你可以把兩個函數(shù)都重寫,都作為被調(diào)用者。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            這就是我的真實(shí)觀點(diǎn)。和兩個重寫后的函數(shù)相比原始的代碼丑陋無比,在這里當(dāng)兩個進(jìn)程被寫為調(diào)用者而不是被調(diào)用者時更易讀了。如果你試圖通過解析器推斷出語法,或者通過解壓器了解解壓數(shù)據(jù)格式,只需閱讀下代碼就可以,同時你會發(fā)現(xiàn)原始的代碼清晰些,重寫后的代碼格式上不太清晰,如果沒有嵌入另外一者的代碼這會更好些。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            Knuth協(xié)程

            在《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》中,Donald Knuth提供了一個解決這類問題的方法。他的方法是徹底丟掉堆棧的概念,不要再想一個進(jìn)程作為調(diào)用者,另一個作為被調(diào)用者,把他們當(dāng)做平等的協(xié)作者關(guān)系。

            實(shí)際上就是:把傳統(tǒng)的“調(diào)用”稍微改為一個不同的方式。新的“調(diào)用”將在某個地方保存返回值而不是堆棧上,并且還能跳轉(zhuǎn)到另一個保存返回值的指定位置上。因此,解碼器每次生成一個字符,就保存它的程序計(jì)數(shù)器并且跳轉(zhuǎn)到上次解析器的位置-解析器每次都需要一個新的字符,它保存自己的程序計(jì)數(shù)器并且跳轉(zhuǎn)到上次解碼器的位置。程序可以在兩個函數(shù)之間來回自如的傳遞需要的數(shù)據(jù)了。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            理論上看起來很美,但實(shí)際中你卻只能在匯編語言中使用,因?yàn)橥ㄓ玫母呒壵Z言沒有一個支持調(diào)用原始的協(xié)程。像類似于C的都是依賴于基礎(chǔ)的堆棧結(jié)構(gòu),因此當(dāng)在函數(shù)間進(jìn)行數(shù)據(jù)傳遞時,一個必須作為調(diào)用者,領(lǐng)一個必須作為被調(diào)用者。所以如果你想寫可移植的代碼,這種技術(shù)和Unix管道一樣不切實(shí)際。
            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            基于棧的協(xié)程

            我們真正想要的是在C中模仿Knuth協(xié)程調(diào)用原語的能力。我們必須接受這個現(xiàn)實(shí),在C語言中,一個函數(shù)將作為調(diào)用者,另一個作為被調(diào)用者。對于調(diào)用者我們沒有任何問題;我們按照原始算法寫代碼就可以,無論什么時候,如果它生成一個字符那么它就需要調(diào)用另一個函數(shù)。

            被調(diào)用者有很多問題。對于被調(diào)用者,我們想要一個函數(shù),該函數(shù)具有“返回并繼續(xù)”的操作:從函數(shù)返回后,當(dāng)再次調(diào)用它,只需要在上次位置繼續(xù)執(zhí)行就可以。比如,我們希望寫這樣一個函數(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)用這個函數(shù)10次,返回0-9的數(shù)字。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            我們怎么能實(shí)現(xiàn)這個呢?好吧,我們可以用一個goto語句將控制跳轉(zhuǎn)到這個函數(shù)中的任何一點(diǎn)。所以如果我們有一個狀態(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 */
                }
            }
            這個方法可以奏效。在一些我們可能需要恢復(fù)控制的地方,我們擁有一組標(biāo)簽:一個在開始位置,其他的緊跟著每個返回語句。我們有一個保留在函數(shù)調(diào)用之間的狀態(tài)變量,它指明了下一步我們需要恢復(fù)控制那個標(biāo)簽。在任何返回之前,我們會更新狀態(tài)變量到正確的標(biāo)簽位;任何調(diào)用之后,我們會對這個變量的值做一個switch操作來查看它當(dāng)前進(jìn)行到哪里。
            jimmyjmh
            jimmyjmh
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            雖然這樣,它還是比較丑。最糟糕的的部分是,這一組標(biāo)簽必須手動維護(hù),并且在函數(shù)體和初始的switch語句之間保持一致。每次新增一個返回語句,我們必須引進(jìn)一個新表簽名并把它加到switch列表中;而每次刪除一個返回語句,我們又必須移除相應(yīng)的標(biāo)簽。剛剛我們只是考慮一個因素增加的兩倍維護(hù)工作量。
            jimmyjmh
            jimmyjmh
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            達(dá)夫設(shè)備(Duff's Device)

            C語言中著名的"達(dá)夫設(shè)備"利用case語句在其匹配switch語句子塊中也是合法的這一事實(shí)。Tom Duff利用這個方法優(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);
                }
            我們可以稍加變動將它應(yīng)用到協(xié)同程序技巧上。我們可以用switch語句本身執(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
            jimmyjmh
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            這差不多就是我們想要的了。我們可以通過這種一返回就控制下一個調(diào)用回復(fù)的方式,用crReturn從函數(shù)返回。當(dāng)然,我們必須遵守一些基本規(guī)則(用crBegin和crFinish包住函數(shù)體;聲明所需的所有保存在acrReturn中的靜態(tài)局部變量;絕不要在一個顯式switch語句中設(shè)置一個crReturn);但那些并不會限制我們太多。

            剩下的唯一問題是傳給crReturn的第一個參數(shù)。就像在上一節(jié)引進(jìn)一個新標(biāo)簽一樣,我們必須避免與已存在的標(biāo)簽名沖突,確保所有給crReturn的狀態(tài)參數(shù)都是不同的。這影響是相當(dāng)小的 -- 編譯器會抓住它并并不讓它在運(yùn)行時出錯 -- 但我們還是要避免這樣做。

            jimmyjmh
            jimmyjmh
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            雖然這可以解決,ANSI C還是提供了擴(kuò)展到當(dāng)前行號的專門的宏名:__LINE__,因此我們可以把crReturn重寫成:

            #define crReturn(x) do { state=__LINE__; return x; \
                                     case __LINE__:; } while (0)
            而且只要遵守第四條基本規(guī)則,我們就不再需要擔(dān)心這些狀態(tài)參數(shù)了(決不在同一行寫兩個crReturn語句)。
            jimmyjmh
            jimmyjmh
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            評估

            現(xiàn)在我們有了這個畸形的東西,讓我們來重寫下原始的代碼片段吧。

            int decompressor(void) {
                static int c, len;
                crBegin;
                while (1) {
                    c = getchar();
                    if (c == EOF)
                        break;
                    if (c == 0xFF) {
                        len = getchar();
                        c = getchar();
                        while (len--)
            	        crReturn(c);
                    } else
            	    crReturn(c);
                }
                crReturn(EOF);
                crFinish;
            }
            void parser(int c) {
                crBegin;
                while (1) {
                    /* first char already in c */
                    if (c == EOF)
                        break;
                    if (isalpha(c)) {
                        do {
                            add_to_token(c);
            		crReturn( );
                        } while (isalpha(c));
                        got_token(WORD);
                    }
                    add_to_token(c);
                    got_token(PUNCT);
            	crReturn( );
                }
                crFinish;
            }

            我們已經(jīng)重寫了解碼器和解析器都作為了被調(diào)用者,不需要像最后一次那樣大規(guī)模的重寫。每個函數(shù)的結(jié)構(gòu)恰好是原始結(jié)構(gòu)的鏡像,讀者能夠通過解析器推斷出相應(yīng)的語法,或者通過解碼器了解到解壓數(shù)據(jù)格式,比起讀那些狀態(tài)機(jī)代碼簡單多了。一旦你適應(yīng)了新的格式,你就會發(fā)現(xiàn)控制流程非常直觀:當(dāng)解壓器產(chǎn)生一個字符,它就調(diào)用crReturn將這個字符傳給調(diào)用函數(shù),并等待當(dāng)需要下一個字符時再次被調(diào)用。當(dāng)解析器需要一個新字符時,它通過crReturn返回,并等待下一次被調(diào)用時通過參數(shù)c傳入新的字符。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            這里代碼里還有一個小的結(jié)構(gòu)變化:parser()中g(shù)etchar()放在了循環(huán)的結(jié)尾而不是開頭了,這是因?yàn)楫?dāng)進(jìn)入函數(shù)時,第一個字符已經(jīng)通過c傳進(jìn)來了。我們應(yīng)該可以接受這個小的結(jié)構(gòu)改變,或者如果我們真的對此抱有輕盈態(tài)度,我們可以認(rèn)為在parse()傳入數(shù)據(jù)前,需要一次“初始化”調(diào)用。

            當(dāng)然像前面一樣,我們不必把兩個函數(shù)都使用協(xié)程的宏重寫,修改一個足矣;另一個可以作為他的被調(diào)用者。

            我們已經(jīng)取得了我們想要達(dá)到的目標(biāo):一個可移植的ANSI C在生產(chǎn)者和消費(fèi)者之間傳遞數(shù)據(jù),而不用狀態(tài)機(jī)重寫代碼。我們已經(jīng)通過把一個switch語句的生僻的功能結(jié)合C的預(yù)處理創(chuàng)建一個隱式的狀態(tài)機(jī)。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            編碼規(guī)范

            當(dāng)然,這種方式違背了書上的編碼規(guī)范,在公司代碼中嘗試這樣使用你會受到嚴(yán)厲的警告!在宏定義中,你的大括號沒有完全匹配,子區(qū)塊中使用了case,至于crReturn宏中內(nèi)容不完整···使用這種不負(fù)責(zé)任的編碼實(shí)踐你沒有被解雇真是一種奇跡。你應(yīng)該感到自行慚愧。

            我需要聲明下編碼規(guī)范在這里不適用。在這篇文章里我展示的例子不是很長,也不復(fù)雜,即使使用狀態(tài)機(jī)重寫也能看懂。但是隨著函數(shù)變長,重寫的難度越來愈大,并且失去了代碼清晰度,越來越糟糕。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            考慮下,如果一個函數(shù)有下面的代碼塊構(gòu)成

            case STATE1:
                /* perform some activity */
                if (condition) state = STATE2; else state = STATE3;

            對于讀者來說從函數(shù)建立下面的小模塊也不是很難

            LABEL1:
                /* perform some activity */
                if (condition) goto LABEL2; else goto LABEL3;

            一個調(diào)用者,一個被調(diào)用者。是的,這兩個函數(shù)在可視結(jié)構(gòu)上是一樣的,它們提供的底層算法都非常少。因?yàn)槭褂脜f(xié)程宏想要解雇你的人同樣會因?yàn)槟銓懙倪B接goto語句的小塊函數(shù)而怒斥你!這次它們做對了,因?yàn)檫@樣的函數(shù)布局破壞了算法的結(jié)構(gòu)。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            編程規(guī)范目標(biāo)就是為了清晰。像switch,return和case語句把這些重要的東西隱藏到“不清晰”的宏中,從編程標(biāo)準(zhǔn)角度來看你已經(jīng)破壞了程序的語法結(jié)構(gòu),違背了代碼清晰的要求。但是我們這樣做是為了突出程序的算法結(jié)構(gòu),而算法結(jié)構(gòu)也正好是讀者想要了解的!

            任何的編碼規(guī)范堅(jiān)持語法的清晰度而犧牲了算法的清晰度都應(yīng)該被重寫。如果你的老板因?yàn)槭褂眠@個技巧而解雇你,當(dāng)安保人員把你拖走時要不斷告訴他們。

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            風(fēng)騷般的編碼

            在正兒八經(jīng)的應(yīng)用程序中,協(xié)程很少使用,因?yàn)樗蕾囉陟o態(tài)變量,因此不能重入或者支持多線程。理想情況下,在真實(shí)應(yīng)用程序中,你可能想在多個不同的上下文中調(diào)用同一個函數(shù),并且在給定的一個上下文中每次調(diào)用時,都能在這個上下文中上一次返回的位置繼續(xù)執(zhí)行。

            這很容易做到,我們增加一個新的函數(shù)參數(shù)——一個上下文結(jié)構(gòu)的指針;我們將所有的局部變量和協(xié)程用到的狀態(tài)變量都聲明成結(jié)構(gòu)體中的元素.

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            這樣寫丑了點(diǎn),因?yàn)橥蝗婚g你不得不使用ctx->i作為循環(huán)計(jì)數(shù)器而不是之前使用的i;事實(shí)上所有重要的變量都成了協(xié)程上下文結(jié)構(gòu)體中的元素。但是這消除了重入的問題,并且沒有影響到程序的結(jié)構(gòu)。

            (當(dāng)然,要是C有Pascal語言的with語句,我們就可以將這個間接的引用隱藏掉,但是很遺憾沒有這些。對于C++語言,我們可以把協(xié)程的兩個函數(shù)設(shè)計(jì)成類的成員函數(shù),所有的局部變量設(shè)計(jì)成類的成員變量,從而將作用域的問題隱藏掉)

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            這兒包含的C語言頭文件實(shí)現(xiàn)了一套預(yù)定義的協(xié)程使用的宏。在文件中定義了二套宏函數(shù),前綴分別是scr和ccr。scr宏是一套簡單的實(shí)現(xiàn),用于可以使用靜態(tài)變量的情況;ccr宏更高級一些,能支持重入。在頭文件的注釋中有完整的說明。

            需要注意的是,VC++ 6并不喜歡這種協(xié)程技巧,因?yàn)槠淠J(rèn)的debug狀態(tài)(Program Database for Edit and Continue)對__LINE__宏的支持有點(diǎn)兒怪。如果想用VC++ 6編譯一個使用了協(xié)程的宏,你就要關(guān)掉Edit and Continue。(在project settings中,選擇c/c++標(biāo)簽,在General中,將Debug info改為Program Database for Edit and Continue之外的其他值)。

            (這個頭文件是MIT許可的,所以你可以任意使用,沒有任何限制。如果你發(fā)現(xiàn)MIT對你的使用方式有限制,可以給我發(fā)郵件,我會考慮給你授權(quán)。)

            使用 這個鏈接 獲得coroutine.h。

            感謝您的閱讀。分享才有快樂!

            繆斯的情人
            繆斯的情人
            翻譯于 1個月前

            0人頂

            翻譯的不錯哦!

            參考文獻(xiàn)

            • Donald Knuth,計(jì)算機(jī)編程藝術(shù), 卷 1. Addison-Wesley, ISBN 0-201-89683-4. Section 1.4.2 describes coroutines in the "pure" form.
            • http://www.lysator.liu.se/c/duffs-device.html 是 Tom Duff's自己關(guān)于Duff策略的討論。注意,右下角,暗示著Duff有可能獨(dú)立的完成這樣的協(xié)程技巧或者其他類似的東西。

              更新與, 2005-03-07: Tom Duff 在一篇博客評論中證實(shí)了這一點(diǎn)。“revolting way to use switches to implement interrupt driven state machines”這篇文章中和他最初在郵件中說的確實(shí)一樣.

            • PuTTY是一個 Win32 Telnet 和 SSH 客戶端。SSH協(xié)議其中一部分使用了協(xié)程技巧.,據(jù)我所知,這是一個在生產(chǎn)代碼中最糟糕的C代碼片段的輪子。

            Feedback

            # re: Coroutines in C  回復(fù)  更多評論   

            2013-05-20 13:04 by zgpxgame
            mark
            亚洲国产精品无码久久久久久曰| 久久精品国产秦先生| 亚洲国产视频久久| 国产成人精品久久| 人妻精品久久久久中文字幕一冢本| 热re99久久精品国99热| 久久99精品国产一区二区三区| 国产福利电影一区二区三区久久久久成人精品综合 | 亚洲精品乱码久久久久久不卡| 午夜精品久久久久久| 日韩久久久久久中文人妻| 久久久精品免费国产四虎| 久久伊人影视| 久久久老熟女一区二区三区| 国产L精品国产亚洲区久久| 一级做a爰片久久毛片毛片| 久久精品国产99久久无毒不卡| 亚洲国产精品久久久久久| 日本久久久久久久久久| 久久精品国产亚洲av高清漫画 | 91精品无码久久久久久五月天| 久久久久亚洲?V成人无码| 无遮挡粉嫩小泬久久久久久久 | 久久国产精品成人影院| 精品久久久久久久中文字幕 | 久久这里有精品视频| 久久精品国产亚洲AV大全| 日韩十八禁一区二区久久 | 国内高清久久久久久| 国产精品99久久久久久董美香| 久久精品国产亚洲av麻豆图片| 久久国产精品-久久精品| 久久精品成人欧美大片| 激情久久久久久久久久| 久久婷婷成人综合色综合| 亚洲国产成人精品91久久久| 欧美一区二区精品久久| 色婷婷综合久久久久中文| 久久笫一福利免费导航| 国产精品一区二区久久精品无码 | 久久人妻少妇嫩草AV无码蜜桃|