# Functional Programming 風格的 C 語言實作 contributed by < `jserv`, `JEFF1216`, `brian208579`, `happyincent` > ## 何謂 Functional Programming? [Functional Programming](https://en.wikipedia.org/wiki/Functional_programming) (以下簡稱 FP) 是種 programming paradigm (開發典範),不是 design pattern 也不是 framework,更不是 language。簡單來說,FP 是種以數學函數為中心的「思考方式」與「程式風格」。 [Why Functional Programming Matters](http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf) 是篇 1984 年的論文,在 1990 年做小幅度修改,主要凸顯出 FP 的優點與重要特質。 * 中文翻譯:[函數式程式設計為什麼至關重要](https://www.byvoid.com/zhs/blog/why-functional-programming) 一般來說,FP 的幾個特點如下: * 運算用的 function 大多只包含條件式及遞迴呼叫; * [higher-order functions](https://en.wikipedia.org/wiki/Higher-order_function) 主要有兩個特點: * function 可當作參數傳入 function 之中 * function 可以回傳 function * 沒有隱含 (implicit) 的 [Side Effect](https://en.wikipedia.org/wiki/Side_effect_(computer_science)) (副作用) * 將程式語言的函式視作看作是數學上的函數,乍看似乎沒問題,但副作用的存在不能保證每次呼叫的時候,傳回來的東西都會一樣,也就是程式本身,並非獨立於程式語言其他的部份。所以當程式出錯的時候,開發者需要走訪所有觸及的程式碼,方可確立問題的來源; * 在 [Haskell](https://www.haskell.org/) 等純函數語言,副作用是必須「明確」地用型別標示出來,而不是隱含的。副作用本身不必然是 primitive 的操作,可以是由語言的其他構件組成。而如 OCaml 這樣的 FP 語言,甚至提供 (explicit) reference 這樣的型別。所以每次呼叫函數,總可以保證傳回的數值不會變,也因此要寫對程式,也變得比較容易,或者說,較難寫程式但可確保容易寫出對的程式; * [lazy evaluation](https://en.wikipedia.org/wiki/Lazy_evaluation) * 當變數被定義時,不會立即 evaluate,而是等待要使用時才 evaluate 並儲存已計算的結果,所以不會重複 evaluate 同一個定義 * 因為沒有副作用,所以可以把計算過的值記起來,以便下次再呼叫的時候直接拿來用,也就是 lazy evaluation 的精神。 延伸閱讀: [Functional Programming: Concept & Example](https://hackmd.io/p/rJV1zI6jX/) 程式語言引入函式傳遞是縮減複雜度的手法之一,然而,很多時候很難阻止開發者傳遞幾百或幾千行的函式內容。於是,程式語言的設計者則轉向焦點,思索如何規範開發者撰寫出意圖單一、實作單純的簡明函式,這即是不可變(immutable) 特性。當開發者無法任意更動變數內含值或物件狀態,便只能從既有變數值或物件狀態,來產生新的數值或物件狀態,這不啻貫徹數學上的數學函數嗎?換言之,開發者會將大任務切割為若干小任務,於是可察覺小任務的流程重複性,一旦開發者封裝重複的小任務,隨後即可在呼叫它們時,只專注在真正該關心的運算,並以函式傳遞運算。 若函式實作時貫徹不可變特性,該函式就會被稱為純函式 (pure function),相對地,就會是具有副作用的函式。值得留意的是,即便在 [Haskell](https://www.haskell.org/) 一類純函數式語言中,也是有副作用的部份,不然就無法接受外界輸入,也不能進行程式對外的輸出。純函數式程式設計規範的是,副作用函式與純函式有個明確的界線,一邊是完全純粹的世界,不純的世界是另一邊;副作用本身對電腦上執行的程式是必要的特徵,它並非萬惡,真正令開發者畏懼的是,開發者搞不清楚這函式是否有副作用,進一步導致他們在不知道的地方改變什麼。 近年 FP 被重新提出且廣泛應用,是基於以下考量: 1. 硬體單核心時脈出現瓶頸,中央處理器的運作時脈已經很難超過 5GHz,因此單執行緒程式速度也面臨瓶頸,但隨著半導體製程進步,單位面積可以塞入更多電晶體,因此處理器可納入更多核 (即 multi-core)。典型 imperative 寫法依賴 [side effect](https://en.wikipedia.org/wiki/Side_effect_(computer_science)),使得多核很難發揮效益,但 FP 沒有 side effect,很容易藉由平行運算,充分運用硬體能力; 2. side effect 寫法很難單元測試,因為不保證每次的結果都ㄧ樣,但 FP 的 pure function 很適合單元測試 3. OOP 的 object composition 需依賴 interface,容易造成 interface 混亂與 over design,但 FP 的 function compostion 不需要額外 interface,只要求你使用 Dataflow 思考,並使用 pure function 避免 side effect 即可 ## 用 C 語言實作 FP 風格 在 FP 中,以下三種常見操作,搭配下圖食物對應: * map(): 配合給定行為,回傳一個陣列或鏈結串列 * filter(): 用以檢索和篩選 * reduce(): 將素材混合在一塊,得到最終結果 ![](https://i.imgur.com/jiZVpDx.png) 考慮 [test-functional.c](https://github.com/jserv/Functional-Programming-in-C/blob/master/test-functional.c) 的用法: ```cpp void print_int(void *v, void *args) { printf("[ op:%s ] %d\n", (char *) args, (int) (*(int *) v)); } void print_char(void *v, void *args) { static int count = 0; printf("%c ", (char) (*(char *) v)); if (++count > 10) { printf("\n"); count = 0; } } bool isOdd(void *v, void *args) { return (bool) (*((int *) v) & 1); } void *twice(void *v, void *args) { int *o = malloc(sizeof(int)); *o = *((int *) v) * 2; return o; } int main(int argc, char **argv) { gc_init(); // initialize the garbage collector iter(map(range(0, 10), twice, NULL), print_int, "twice"); /* 0, 2, 4, .., 20 */ iter(filter(range(0, 10), isOdd, NULL), print_int, "odd"); /* 1, 3, 5, 7, 9 */ iter(rangeChar('a', 'z'), print_char, NULL); /* a, b, c, ..., z */ iter(rangeChar(' ', 'z'), print_char, NULL); // won't get printed iter(rangeChar('1', 'z'), print_char, NULL); gc_collect(); exit(0); } ``` 執行輸出為: ``` [ op:twice ] 0 [ op:twice ] 2 [ op:twice ] 4 [ op:twice ] 6 [ op:twice ] 8 [ op:twice ] 10 [ op:twice ] 12 [ op:twice ] 14 [ op:twice ] 16 [ op:twice ] 18 [ op:twice ] 20 [ op:odd ] 1 [ op:odd ] 3 [ op:odd ] 5 [ op:odd ] 7 [ op:odd ] 9 a b c d e f g h i j k l m n o p q r s t u v w x y z 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z ``` 第 25 行的 `map` 操作,將給定 [0, 10] 區間的整數都透過 `twice` 函式乘上 `2`,再透過 `print_int` 個別輸出產生的數值。 第 27 行的 `filter` 操作,依據 `isOdd` 函式的判斷,自 [0, 10] 區間篩選出奇數, 再透過 `print_int` 個別輸出篩選出來的數值。 第 29 行到 31 行則展示 map 搭配 filter,列舉出給定 ASCII 字元集的範圍,並透過 `print_char` 函式輸出。 參見其他實作: * [Functional Programming](https://www.lucabol.com/tags/functional-programming/) * [Functional Style Programming Using C](https://www.pluralsight.com/guides/functional-style-programming-using-c) * [The GObject messaging system](https://developer.gnome.org/gobject/stable/chapter-signal.html) ## 案例: 反轉 linked list 元素 以下展示採用 [Functional Programming](https://en.wikipedia.org/wiki/Functional_programming) 風格開發的 singly-linked list 程式: [reverse.c](https://github.com/jserv/Functional-Programming-in-C/blob/master/reverse.c) ```cpp #include <stdint.h> #include <stdio.h> #include <stdlib.h> /* integer linked list type */ typedef struct __int_list const *const int_list_t; static int_list_t const Nil = NULL; /* empty list */ /* singly linked list element */ typedef struct __int_list { int_list_t next; int32_t const val; } node_t; /* A pointer to where we are about to store the result of computation */ typedef void *const CPS_Result; /* prototypes for the continuations */ typedef void (*MakeListCallback)(int_list_t list, CPS_Result res); void make_list(uint32_t const arr_size, int32_t const array[], int_list_t lst, MakeListCallback const cb, CPS_Result res); typedef void (*ReversedListCallback)(int_list_t rlist, CPS_Result res); void reverse(int_list_t list, int_list_t rlist, ReversedListCallback const cb, CPS_Result res); typedef void (*VoidMappable)(int32_t const val); void void_map_array(VoidMappable const cb, uint32_t const size, int32_t const *const arr); void list2array(int_list_t list, CPS_Result res); /* reverse a list and then store it in an array */ void reverse_toarray(int_list_t list, CPS_Result res) { reverse(list, Nil, list2array, res); } static void print_val(int32_t const val) { printf("%d ", val); } #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0])) int main(int argc, char *argv[]) { int32_t arr[] = {99, 95, 90, 85, 80, 20, 75, 15, 10, 5}; uint32_t const arr_size = ARRAY_SIZE(arr); int32_t res[arr_size]; /* call make_list and pass reverse_toarray as the "continuation" */ make_list(arr_size, arr, Nil, reverse_toarray, res); /* print out the reversed array */ void_map_array(print_val, arr_size, res); printf("\n"); return 0; } /* construct a linked list from an array */ void make_list(uint32_t const arr_size, int32_t const arr[], int_list_t lst, MakeListCallback const cb, CPS_Result res) { if (!arr_size) { cb(lst, res); return; } make_list(arr_size - 1, arr, &(node_t){.val = arr[arr_size - 1], .next = lst}, cb, res); } /* transform a linked list into an array */ void list2array(int_list_t list, CPS_Result res) { if (Nil == list) return; int32_t *array = res; array[0] = list->val; list2array(list->next, array + 1); } void reverse(int_list_t list, int_list_t rlist, /* reversed list */ ReversedListCallback const cb, CPS_Result res) { if (Nil == list) { cb(rlist, res); return; } reverse(list->next, &(node_t){.val = list->val, .next = rlist}, cb, res); } /* iterate over an array and performs action cb on each element */ void void_map_array(VoidMappable const cb, uint32_t const size, int32_t const *const arr) { if (!size) return; cb(arr[0]); void_map_array(cb, size - 1, arr + 1); } ``` 精髓在於以下: ```cpp /* integer linked list type */ typedef struct __int_list const *const int_list_t; static int_list_t const Nil = NULL; /* empty list */ ``` 這是個 const 結構指標且該指標的記憶體地址和內含值無法透過區域變數去改變,正如上述所及的 FP 精神。 再來,是關於 callback 的函式指標的理解,這是個函式指標,而 `MakeListCallback` 就是拿來接收 reverse_toarray 的這個函式,並且將 `lst` 和 `res` 傳給 reverse 做下一個動作,打個比方:`make_list(arr_size, arr, Nil, reverse_toarray, res);` 會在這行程式碼去呼叫 `make_list` 副函式直到執行完透過 `cb(lst,res)` 將做好的 linked list 開頭的記憶體地址回傳給 reverse,所以整體的函式執行順序是: ``` main --> make_list --> reverse_toarray --> reverse --> list2array --> void_map_array ``` 再來是建立 linked list 的部分: 這個是從陣列中的尾端建立起,亦即 `5` 是尾巴而 `99` 是頭,而在建立 linked list 過程中,lst 會將下一個結構的 next 儲存起來,並且將記憶體地址和數值複寫進下一個結構中,所以在 make_list 的順序是: - [ ] lst ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 99 | <ref> }", width=1.2, color=red] b [label="{ <data> 95 | <ref> }"]; c [label="{ <data> 90 | <ref> }"]; d [label="..." shape=box]; e [label="{ <data> 5 | <ref> }",width=1.2]; a:ref:c -> b:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false]; c:ref:c -> d:ref[arrowhead=dot, arrowtail=vee, dir=both, tailclip=false]; d->e:ref[arrowhead=dot, arrowtail=vee, dir=both, tailclip=false]; } ``` - [ ] list ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 99 | <ref> }", width=1.2, color=red] b [label="{ <data> 95 | <ref> }"]; c [label="..." shape=box]; d [label="{ <data> 5 | <ref> }"]; e [label="{ NULL }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; c:ref:c -> d:data [arrowsize=1.2]; d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; } ``` reverse 將開頭 (99) 的 next 指向一開始的 rlist (Null),再透過 rlist 儲存新的 (99) 的記憶體地址,再依序將 新的 (95) 的 next 指向新的 (99),如圖: - [ ] rlist: ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 99 | <ref> }", width=1.2, color=red] b [label="{ NULL }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; } ``` ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 95 | <ref> }", width=1.2, color=red] b [label="{ <data> 99 | <ref> }"]; c [label="{ NULL }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; } ``` 直到將全部的 linked list 做完反轉後才結束,如圖: - [ ] rlist ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 5 | <ref> }", width=1.2, color=red] b [label="{ <data> 10 | <ref> }"]; c [label="..." shape=box]; d [label="{ <data> 99 | <ref> }"]; e [label="{ NULL }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; c:ref:c -> d:data [arrowsize=1.2]; d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; } ``` 最後的 linked list 再傳回 `list2array` 並輸出最終結果。本程式的技巧除了透過陣列來建立一個 linked list,過程中也利用 `if` 的判斷式來進行遞迴並且傳給下一個副函式,例如在 `reverse` 副函式中,其終止的條件是,當 list 的記憶體地址為 NULL (也就是到最後一個 5 時) 會停止遞迴並將其中的值傳給下一個副函式: ```cpp void reverse(int_list_t list, int_list_t rlist, /* reversed list */ ReversedListCallback const cb, CPS_Result res) { if (Nil == list) { cb(rlist, res); return; } reverse(list->next, &(node_t) K1, cb, res); } ``` 注意到這裡的 CPS: > Continuation Passing Style (CPS): Programming style characterized by functions with an additional continuation argument, which call their continuation instead of returning to their caller. ## 案例: 對 Linked List 元素進行合併排序 利用 merge sort 我們減少了程式碼中的 side effect 並且將每個副函式幾乎變成了 pure function。也就是說,每個函式我們都只用了區域變數,並讓其中的值只受到該區域的副函式影響,直到結束後傳遞結果為止。 - [ ] merge sort merge sort 簡單來說就是將一個 linked list 拆成一個又一個獨立的結構再去作排列和重組。如圖: ![](https://i.imgur.com/mZWAlpF.png) [mergesort.c](https://github.com/jserv/Functional-Programming-in-C/blob/master/mergesort.c) 我們運用兩指標 fast 和 slow,當 fast 不為 `NULL` 時,fast 往前讀取記憶體地址,若下個 fast 依舊不為 NULL,則 slow 和 fast 兩個指標繼續往前,直到 fast 指向 NULL 為止。如下圖: - [ ] list ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 99 | <ref> }", width=1.2, color=red] b [label="{ <data> 95 | <ref> }", width=1.2, color=red]; c [label="{ <data> 85 | <ref> }", width=1.2, color=red]; d [label="{ <data> 80 | <ref> }", width=1.2, color=red]; e [label="{ <data>. .. | <ref> }", width=1.2, color=red]; f [label="{ NULL }", width=1.2, color=red]; g [label="{ <data> slow }", width=1.2, color=black]; h [label="{ <data> fast }", width=1.2, color=black]; a:ref:c -> b:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; c:ref:c -> d:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; d:ref:c -> e:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; e:ref:c -> f [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; a:ref:c -> g:data [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> h:data [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; } ``` 若 fast 不為 NULL 則變成: ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 99 | <ref> }", width=1.2, color=red] b [label="{ <data> 95 | <ref> }", width=1.2, color=red]; c [label="{ <data> 85 | <ref> }", width=1.2, color=red]; d [label="{ <data> 80 | <ref> }", width=1.2, color=red]; e [label="{ <data>. .. | <ref> }", width=1.2, color=red]; f [label="{ NULL }", width=1.2, color=red]; g [label="{ <data> slow }", width=1.2, color=black]; h [label="{ <data> fast }", width=1.2, color=black]; a:ref:c -> b:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; c:ref:c -> d:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; d:ref:c -> e:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; e:ref:c -> f [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; a:ref:c -> g:data [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; c:ref:c -> h:data [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; } ``` 若 fast 仍不為 NULL 的話則 fast 和 slow 各前進一格。 ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 99 | <ref> }", width=1.2, color=red] b [label="{ <data> 95 | <ref> }", width=1.2, color=red]; c [label="{ <data> 85 | <ref> }", width=1.2, color=red]; d [label="{ <data> 80 | <ref> }", width=1.2, color=red]; e [label="{ <data>. .. | <ref> }", width=1.2, color=red]; f [label="{ NULL }", width=1.2, color=red]; g [label="{ <data> slow }", width=1.2, color=black]; h [label="{ <data> fast }", width=1.2, color=black]; a:ref:c -> b:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; c:ref:c -> d:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; d:ref:c -> e:ref [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; e:ref:c -> f [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> g:data [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; d:ref:c -> h:data [arrowhead=dot, arrowtail=vee, dir=both, tailclip=false, arrowsize=1.2]; } ``` 直到 fast 碰到 `NULL` 為止,則該 list 就會被分為兩個和其他,以「案例: 反轉 linked list 元素」的輸入來說,就是 (99, 90, 95, 6, 85, 20, 75, 15) 一群,(10, 5) 為另一群這樣分下去。直到變成一個獨立的 linked list 後再去連接起來。 本次的程式執行順序為: > main --> make_list --> mergesort --> partition --> partition --> ........ --> mergesort --> mergelist --> mergesort --> list2array --> void_map_array 採用 non-intrusive 的 linked list 來實現,從程式碼中 ```cpp typedef struct __list * list_t; typedef struct __list { list_t next; } node_t; typedef struct __ele { int32_t const val; list_t const list; } ele_t; ``` 我們將 `val` 和 `list` 的值宣告為 `const`,亦即無法對其值進行改變,然後將`next `宣告為一個指標的指標,圖示如下: ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> val | <ref> list }", width=1.2, color=red] b [label="{ <data> val | <ref> list }", width=1.2, color=red]; g [label="{ <data> next }", width=1.2, color=black]; g:ref:c -> b:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=true arrowsize=0.5]; a:ref:c -> g:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=true, arrowsize=0.5]; } ``` - [ ] Nil 而在程式實現中,我們必須設計一個 Nil 結構參數,其目的是為了在各個函式之間呼叫,我們是以`ele_t `或是`list_t `的結構型態進行回傳資料和遞迴,所以我們無法直接利用 NULL 來作為函式中斷遞迴的判斷,因此我們令`Nil `為`static const ele_t Nil = {.val = 0, .list = &(node_t){ .next = NULL }}; ` 意思是當我們指向 Nil 時候就表示該記憶體地址指向 Null。如圖: ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> val | <ref> list }", width=1.2, color=red] b [label="{ <data> Nil(0) | <ref> list }", width=1.2, color=red]; c [label="{ <data> NULL }", width=1.2, color=black]; g [label="{ <data> next }", width=1.2, color=black]; g:ref:c -> b:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=true, arrowsize=0.5]; a:ref:c -> g:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=true, arrowsize=0.5]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=true, arrowsize=0.5]; } ``` - [ ] container_of (ptr, type, member) `container_of` 這樣的巨集用於 Linux 核心和一些專案中,作用是根據給定的結構體變數其中的一個成員變數的指標,來獲取指向整個結構體變數的指標。舉例來說,給定以下結構體: ```cpp struct demo_struct { type1 member1; type2 member2; type3 member3; type4 member4; }; ``` 假設結構體變數 `demo` 在執行時期的記憶體位置呈現如下圖: ``` demo +-------------+ 0xA000 | member1 | +-------------+ 0xA004 | member2 | +-------------+ 0xA010 | member3 | +-------------+ 0xA018 | member4 | +-------------+ ``` 一旦執行程式碼 `container_of(memp, struct demo_struct, type3)`,會使取得的記憶體地址為該結構的初始地址,亦即 `0xA000`,而在作 merge sort 時,前述 fast 和 slow 指標必須是指向該 linked list 結構的初始記憶體地址,才可以對它作 dereference ,否則就會出現記憶體操作的錯誤,因次我們可定義`list_entry` 如下: ```cpp #define list_entry(node, type, member) \ container_of(node, type, member) ``` 例如在 `partition` 中,我們要對將其拆開時,便會使用到: ```cpp fast = list_entry(head->list->next, ele_t, list); ``` - [ ] mergeLists 最後是關於 `mergeLists` 的實作,類似之前的程式碼,只是在於進行遞迴呼叫時,要用到 `tmp` 來當作暫存器儲存結構的記憶體地址。 ```cpp= if (a->list->next == NULL) { return b; } else if (b->list->next == NULL) { return a; } if (a->val <= b->val) { mergedList = a; ele_t *tmp = mergeLists(list_entry(a->list->next, ele_t, list), b); mergedList->list->next = (list_t)(&(tmp->list)); } else { mergedList = b; ele_t *tmp = mergeLists(a, list_entry(b->list->next, ele_t, list)); mergedList->list->next = (list_t)(&(tmp->list)); } ``` 其中第 13 行將回傳 `(a, Nil)` 給 `mergeLists`。 我們假設 a 是上述示意圖 `95` 的結構體,b 是 `90` 的結構體,在比較完大小後,在 `tmp = mergeLists(a, list_entry(b->list->next, ele_t, list));` 中會進行遞迴呼叫,隨即將 a 結構體指標和 Nil 回傳給 mergeLists 函式,經由 if 判斷式後回傳 a 結構體指標給 tmp 最後將 `90` 的 next ,也就是 b->list->next 由原本的指向 Nil 改成指向 `95` 的結構體,以此遞迴下去完成 non-intrusive linked-list 的重組。最後再輸出該 linked list,完成此次 FP 風格的實作。 gdb下的觀察結果: ```shell breakpoint 4, partition (head=0x7ffffffedee0, front=0x7ffffffedde0, back=0x7ffffffedde8) at mergesort.c:124 124 if (head == NULL || head->list->next == (list_t)(&(Nil.list))) { (gdb) 129 slow = head; (gdb) 130 fast = list_entry(head->list->next, ele_t, list); (gdb) 132 while(fast->list->next != NULL) { (gdb) p *head $1 = {val = 99, list = 0x7ffffffeded8} (gdb) p *fast $2 = {val = 95, list = 0x7ffffffedf48} (gdb) p *(head->list->next) $3 = {next = 0x7ffffffedf48} (gdb) p *(head->list) $4 = {next = 0x7ffffffedf58} (gdb) p &(head->list>next) No symbol "next" in current context. (gdb) p &(head->list->next) $5 = (list_t *) 0x7ffffffeded8 (gdb) p (head->list) $6 = (const list_t) 0x7ffffffeded8 (gdb) p (head->list->next) $7 = (list_t) 0x7ffffffedf58 (gdb) p &(fast->list) $8 = (const list_t *) 0x7ffffffedf58 ```