# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 14 週測驗題 ###### tags: `sysprog2020` :::info 目的: 引導學員挑戰 LeetCode 並掌握位元處理和記憶體管理 ::: ==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLScXGes1BJzdIXfWVneB3r4Vkxynuu7DlOB0eeSsA-r2U37nGg/viewform)== --- ### 測驗 `1` LeetCode [1409. Queries on a Permutation With Key](https://leetcode.com/problems/queries-on-a-permutation-with-key/) 題意為,給定一個待查陣列 `queries`,陣列中的元素為 1 到 m 之間的正整數。 請你根據以下規則處理所有待查項 $queries[i]$ (從 $i = 0$ 到 $i = queries.length-1$): 1. 起初排列 $P = [1,2,3,...,m]$ 2. 對於目前 $i$,請你找出待查項 $queries[i]$ 在排列 P 中的位置(索引自 0 開始),然後將其從原位置移動到排列 P 的起始位置 (即索引為 0 處)。注意 $queries[i]$ 在 P 中的位置就是 $queries[i]$ 的查詢結果。 請你以陣列形式返回待查陣列 `queries` 的查詢結果。 範例 1 * 輸入 > $queries = [3,1,2,1]$, $m = 5$ * 輸出 > $[2,1,2,1]$ * 解讀:待查陣列 `queries` 處理如下: * 對於 $i=0 \to queries[i]=3, P=[1,2,3,4,5] \to$ `3` 在 P 中的位置是 ==`2`==,接著我們把 `3` 移動到 P 的起始位置,得到 $P=[3,1,2,4,5]$ * 對於 $i=1 \to queries[i]=1, P=[3,1,2,4,5] \to$ `1` 在 P 中的位置是 ==`1`==,接著我們把 `1` 移動到 P 的起始位置,得到 $P=[1,3,2,4,5]$ * 對於 $i=2 \to queries[i]=2, P=[1,3,2,4,5] \to$ `2` 在 P 中的位置是 ==`2`==,接著我們把 `2` 移動到 P 的起始位置,得到 $P=[2,1,3,4,5]$ * 對於 $i=3 \to queries[i]=1, P=[2,1,3,4,5] \to$ `1` 在 P 中的位置是 ==`1`==,接著我們把 `1` 移動到 P 的起始位置,得到 $P=[1,2,3,4,5]$ * 因此,返回的結果陣列為 $[2,1,2,1]$ 範例 2 * 輸入 > $queries = [4,1,2,2]$, $m = 4$ * 輸出 > $[3,1,2,0]$ * 解讀:待查陣列 `queries` 處理如下: * 對於 $i=0 \to queries[i]=4, P=[1,2,3,4] \to$ `4` 在 P 中的位置是 ==`3`==,接著我們把 `4` 移動到 P 的起始位置,得到 $P=[4,1,2,3]$ * 對於 $i=1 \to queries[i]=1, P=[4,1,2,3] \to$ `1` 在 P 中的位置是 ==`1`==,接著我們把 `1` 移動到 P 的起始位置,得到 $P=[1,4,2,3]$ * 對於 $i=2 \to queries[i]=2, P=[1,4,2,3] \to$ `2` 在 P 中的位置是 ==`2`==,接著我們把 `2` 移動到 P 的起始位置,得到 $P=[2,1,4,3]$ * 對於 $i=3 \to queries[i]=2, P=[2,1,4,3] \to$ `2` 在 P 中的位置是 ==`0`==,接著我們把 `2` 移動到 P 的起始位置,得到 $P=[2,1,4,3]$ * 因此,返回的結果陣列為 $[3,1,2,0]$ 範例 3 * 輸入 > $queries = [7,5,5,8,3]$, $m = 8$ * 輸出 > $[6,5,0,7,5]$ * 解讀:待查陣列 `queries` 處理如下: * 對於 $i=0 \to queries[i]=7, P=[1,2,3,4,5,6,7,8] \to$ `7` 在 P 中的位置是 ==`6`==,接著我們把 `7` 移動到 P 的起始位置,得到 $P=[7,1,2,3,4,5,6,8]$ * 對於 $i=1 \to queries[i]=5, P=[7,1,2,3,4,5,6,8] \to$ `5` 在 P 中的位置是 ==`5`==,接著我們把 `5` 移動到 P 的起始位置,得到 $P=[5,7,1,2,3,4,6,8]$ * 對於 $i=2 \to queries[i]=5, P=[5,7,1,2,3,4,6,8] \to$ `5` 在 P 中的位置是 ==`0`==,接著我們把 `5` 移動到 P 的起始位置,得到 $P=[5,7,1,2,3,4,6,8]$ * 對於 $i=3 \to queries[i]=8, P=[5,7,1,2,3,4,6,8] \to$ `8` 在 P 中的位置是 ==`7`==,接著我們把 `8` 移動到 P 的起始位置,得到 $P=[8,5,7,1,2,3,4,6]$ * 對於 $i=4 \to queries[i]=3, P=[8,5,7,1,2,3,4,6] \to$ `3` 在 P 中的位置是 ==`5`==,接著我們把 `3` 移動到 P 的起始位置,得到 $P=[3,8,5,7,1,2,4,6]$ * 因此,返回的結果陣列為 $[6,5,0,7,5]$ 提示: * $1 \le m \le 10^3$ * $1 \le queries.length \le m$ * $1 \le queries[i] \le m$ 思路:我們可維護一個陣列 `pos[]`,記錄目前所有數字的位置,初始時數字的位置對應其本身的數值減 `1` (數字自 `1` 開始,而索引自 `0` 起),也就是: ```cpp pos[1] = 0; // 數字 1 在第 0 位 pos[2] = 1; // 數字 2 在第 1 位 pos[3] = 2; // 數字 3 在第 2 位 ... pos[n] = n - 1; // 數字 n 在第 n-1 位 ``` 接著我們循序走訪 `queries` 陣列中的每個數字,利用 pos 陣列查看目前數字所在的位置,並將該位置計入預計回傳的結果。由於數字會從目前位置移動到陣列的首位,因此,目前數字的位置變為 `0`,其他小於目前數字的位置都要加 `1`,位置大於目前數字的位置保持不變。重複此步驟,直到處理完所有 `queries` 中的數字。 為了縮減時間複雜度,我們可引入 [Fenwick tree](https://en.wikipedia.org/wiki/Fenwick_tree): > [Binary indexed tree](https://www.csie.ntu.edu.tw/~sprout/algo2016/homework/week11.pdf): Fenwick tree 是個處理前綴時很有效率的資料結構,也稱為 Binary indexed tree,或簡稱 BIT。以下簡稱它為 BIT。對於一個長度為 n 的陣列,BIT 可以在 $O(n)$ 的時間初始化,在 $O(\log n)$ 時間詢問一個前綴的訊息 (例如前綴和),以及在 $O(\log n)$ 的時間修改其中一個值。雖然複雜度和線段樹相同,但 BIT 的時間常數比線段樹小得多,空間也比較小 (只需要多開一個大小恰好為 n 的陣列即可),程式碼也非常精簡 。一般來說,如果問題的性質可以使用 BIT,效率會和使用線段樹有明顯的差別。 `lowbit`: 二進位最後一個 1 的位置所代表的數值 範例: * 13 = 1101~2~ $\to$ `lowbit(13)` = 0001~2~ = 1 * 12 = 1100~2~ $\to$ `lowbit(12)` = 0100~2~ = 4 ![](https://i.imgur.com/ufDJQwC.png) > 節點存 $[i - lowbit(i) + 1, 1]$ 的和。 > 父節點為 $i - lowbit(i)$ > 第一列為原陣列 (即 $1, 7, 3, 0, ...]$,第二到第四列依次填入數字 > 方便起見,此處的陣列的索引為自 `1` 開始 建構 BIT: * prefixSum(13) = prefixSum(00001101~2~) > = BIT[13] + BIT[12] + BIT[8] > = BIT[00001101~2~] + BIT[00001100~2~] + BIT[00001000~2~] ![](https://i.imgur.com/4eOe7EN.png) 樹的示意圖 ![](https://i.imgur.com/R67ePaR.png) > BIT 的 binary 並不是指二元樹,而是指「二進位」 更新操作: ![](https://i.imgur.com/xoS2xwl.png) > 原有位於索引 5 的數值 `5` 增加 `2` 而成為 `7` BIT 時間複雜度 * 修改: $O(\log n)$ * 查詢: $O(\log n)$ 考慮以下程式碼為 [1409. Queries on a Permutation With Key](https://leetcode.com/problems/queries-on-a-permutation-with-key/) 的可能解法: ```cpp /* Fenwick tree */ #define lowbit(x) (x & -x) static inline int sum(int *tree, int index) { int ret = 0; for (; index; index -= lowbit(index)) ret += tree[index]; return ret; } static inline void update(int *tree, int size, int index, int delta) { for (; index < size; index += lowbit(index)) tree[index] += delta; } int *processQueries(int *queries, int queries_size, int m, int *ret_size) { int map[m + 1]; for (int i = 1; i <= m; ++i) map[i] = i + queries_size; int tree_size = queries_size + m + 1; int tree[tree_size]; memset(tree, 0, sizeof(tree)); for (int i = m; i; i--) update(tree, tree_size, i + queries_size, 1); *ret_size = queries_size; int *ret = malloc(sizeof(int) * queries_size); for (int i = 0; i < queries_size; ++i) { ret[i] = sum(tree, map[queries[i]]) + PPP; update(tree, tree_size, map[queries[i]], -1); /* set to zero */ map[queries[i]] = QQQ; update(tree, tree_size, map[queries[i]], 1); /* move to front */ } return ret; } ``` 請補完上述程式碼,使其得以符合 LeetCode 題目的行為。 參考資料: * [花花醬 LeetCode 1409. Queries on a Permutation With Key](https://youtu.be/DwtijVbS3G0) ==作答區== PPP = ? * `(a)` `-1` * `(b)` `0` * `(c)` `1` QQQ = ? * `(a)` `i` * `(b)` `0` * `(c)` `queries_size` * `(d)` `queries_size - 1` * `(e)` `queries_size - i` :::success 延伸問題: 1. 解釋上述程式碼運作原理,並分析時間複雜度 2. Binary Indexed Tree 有哪些應用?請舉例並分析 3. 研讀 [Fenwick Treeの定数倍高速化](https://yosupo.hatenablog.com/entry/2016/12/04/121927),探究上述程式碼改進的機會 ::: --- ### 測驗 `2` CS:APP 第 9 章提到 garbage collector (以下簡稱 GC),其中 [Mark and Sweep](https://en.wikipedia.org/wiki/Tracing_garbage_collection) 是經典的演算法,後者分為 mark 和 Sweep 兩個階段: - Mark 階段: 從 root set(stack & globals list)遞迴地走訪可到達的記憶體區段,並將之標記 - Sweep 階段: 走訪所有記憶體區段(ptr_map 中所有節點),並將沒被標記到的從 heap 中釋放 示意如下: ![](https://i.imgur.com/phxlQhD.gif) 實作 `Mark`: 1. 建立存取清單 `todo` 將所有 root 中的物件加入。 2. 當 `todo` 中有物件時,執行以下3~4。 3. 從 `todo` 中選任一物件 `v` ,將其除外於 `todo`。 4. 如果 `v` 未被標記,標記 `v` ,將所有 `v` 包含的物件放到 `todo` 中。 實作 `Sweep`: 1. 物件 `p` 從 `heap` 的最底層物件開始。 2. 當 `p` 還不是 `top` 的時候,執行以下3~5。 3. 如果 `p` 已被標記,則將其改為未標記。 4. 反之,將 `p` 的記憶體區塊加到 `free list` 中,準備清除。 5. 將 `p` 改為在 heap 中上一層的物件。 (`using p <- p + sizeof(p)`) 問題點 `1` * 需要清除時,通常表示沒有記憶體空間。 * 但是, Mark 階段需要記憶體空間去創造訪問清單 。 * 存取清單無法預測大小,因此無法預先保留。 :::info 解決方法 * 應用 `pointer reversal`,用 `depth first search` 取代存取清單。 ::: 問題點 `2` * 有些物件沒有指標的空間。 :::info 解決方法 * 使用一個暫存器記憶其 `parent` 位置,就可不用 `pointer reversal` 也能執行 `depth firsth search` 。 ::: - [ ] Tri-Color 演算法與 Golang > Reference: [Golang realtime garbage collector](https://www.youtube.com/watch?v=n59VtiRx34s) 上述的 mark and sweep 演算法有個缺點。每次在執行 `mark` 時,都需要將程式的執行予以暫停。 * 標記時,需要讓所有 object 維持不變,才能保持不出錯。 舉例: 以下程式具備物件 obj~0~, obj~1~, obj~2~, obj~3~ 時間 t0:執行 ` mark ` 將 ` reachable ` 物件標記。 ![](https://i.imgur.com/M8rrw1w.png) 時間 t1:因為沒有暫停程式的執行,出現 obj4 指向 obj3 ![](https://i.imgur.com/8v6mkKy.png) 時間 t2: 執行 ` sweep `,刪除物件 obj3, obj4 產生錯誤。 ![](https://i.imgur.com/jBgwEzS.png) 因此,為了讓 mark and sweep 過程可不暫停程式的運作, 延伸出 Tri-colored 演算法,描述如下: * 使用 Breadth-first 的策略。 * 將物件用三種顏色來標記: * 白色:未標記,在 sweep 的階段被清掃 * 灰色:已標記,目前 Breadth-first 的進行前緣。 * 黑色:已標記。 * 將新增物件,標記為灰色。 以下是改寫自 [Baby's First Garbage Collector](http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/) 的虛擬機器和 GC 實作: ```cpp #include <assert.h> #include <stdio.h> #include <stdlib.h> #define GC_INITIAL_THRESHOLD 8 #define STACK_MAX 256 /* maximum stack size for the virtual machine */ typedef enum { OBJECT_TYPE_INT, OBJECT_TYPE_PAIR } ObjectType; typedef struct sObject { /* GC related */ unsigned char mark; /* zero: unreached, non-zero: retained */ struct sObject *next; /* the next object chained to it */ ObjectType type; union { int value; struct { struct sObject *head, *tail; }; }; } Object; typedef struct { /* GC related */ Object *first_object; size_t object_num, object_max; size_t stack_size; Object *stack[STACK_MAX]; } VM; VM *new_vm() { VM *vm = malloc(sizeof(VM)); assert("VM allocation failed" && vm); if (vm) { vm->stack_size = 0; vm->first_object = 0; vm->object_num = 0; vm->object_max = GC_INITIAL_THRESHOLD; } return vm; } void vm_push(VM *vm, Object *value) { assert("stack overflow" && vm->stack_size < STACK_MAX); vm->stack[vm->stack_size++] = value; } Object *vm_pop(VM *vm) { assert("stack underflow" && vm->stack_size > 0); return vm->stack[--vm->stack_size]; } void gc(VM *); Object *new_object(VM *vm, ObjectType type) { if (vm->object_num == vm->object_max) gc(vm); Object *obj = malloc(sizeof(Object)); assert("Object allocation failed" && obj); if (obj) { obj->mark = 0; obj->type = type; obj->next = vm->first_object; vm->first_object = obj; /* tri-color: gray objects */ AAA; } return obj; } Object *vm_push_int(VM *vm, int value) { Object *obj = new_object(vm, OBJECT_TYPE_INT); if (obj) { obj->value = value; vm_push(vm, obj); } return obj; } Object *vm_push_pair(VM *vm) { Object *obj = new_object(vm, OBJECT_TYPE_PAIR); if (obj) { obj->tail = vm_pop(vm); obj->head = vm_pop(vm); vm_push(vm, obj); } return obj; } void free_vm(VM *vm) { vm->stack_size = 0; gc(vm); free(vm); } static void gc_mark(Object *obj) { if (obj->mark) return; /* for recursive reference */ obj->mark = 1; /* tri-color: black objects */ if (obj->type == OBJECT_TYPE_PAIR) { gc_mark(obj->head); gc_mark(obj->tail); } } static void gc_mark_all(VM *vm) { for (size_t i = 0; i < vm->stack_size; ++i) gc_mark(vm->stack[i]); } static void gc_sweep(VM *vm) { Object **obj = &(vm->first_object); while (*obj) { if (!(*obj)->mark) { Object *unreached = *obj; /* tri-color: white objects */ /* first_object / previous->next = unreached->next */ *obj = unreached->next; free(unreached); BBB; } else { (*obj)->mark = 0; obj = &(*obj)->next; } } } void gc(VM *vm) { gc_mark_all(vm); gc_sweep(vm); /* adjust GC threshold */ vm->object_max = vm->object_num ? vm->object_num * 2 : GC_INITIAL_THRESHOLD; } void test1() { puts(__func__);; VM *vm = new_vm(); vm_push_int(vm, 1); vm_push_int(vm, 2); gc(vm); assert("GC should skip preserved objects" && vm->object_num == 2); free_vm(vm); } void test2() { puts(__func__); VM *vm = new_vm(); vm_push_int(vm, 1); vm_push_int(vm, 2); vm_pop(vm); vm_pop(vm); gc(vm); assert("GC should collect unreached objects" && vm->object_num == 0); free_vm(vm); } void test3() { puts(__func__); VM *vm = new_vm(); vm_push_int(vm, 1); vm_push_int(vm, 2); vm_push_pair(vm); vm_push_int(vm, 3); vm_push_int(vm, 4); vm_push_pair(vm); vm_push_pair(vm); gc(vm); assert("GC should reach nested objects" && vm->object_num == CCC); free_vm(vm); } void test4() { puts(__func__); VM *vm = new_vm(); vm_push_int(vm, 1); vm_push_int(vm, 2); Object *a = vm_push_pair(vm); vm_push_int(vm, 3); vm_push_int(vm, 4); Object *b = vm_push_pair(vm); a->tail = b; b->tail = a; gc(vm); assert("GC should deal with recursive reference" && vm->object_num == DDD); free_vm(vm); } int main() { test1(); test2(); test3(); test4(); return 0; } ``` 參考的程式執行輸出如下: (預期「不會」觸發 assertion) ``` test1 test2 test3 test4 ``` 請補完程式碼,使 GC 符合預期行為。 ==作答區== AAA = ? * `(a)` `++vm->object_num` * `(b)` `--vm->object_num` BBB = ? * `(a)` `++vm->object_num` * `(b)` `--vm->object_num` CCC = ? * `(a)` 2 * `(b)` 3 * `(c)` 4 * `(d)` 5 * `(e)` 6 * `(f)` 7 * `(g)` 8 DDD = ? * `(b)` 3 * `(c)` 4 * `(d)` 5 * `(e)` 6 * `(f)` 7 * `(g)` 8 :::success 延伸問題: 1. 解釋上述程式碼運作原理,並且指出其不足和實作錯誤之處 2. 針對 Tri-colored 演算法,改進上述程式碼,使得符合演算法設計 ::: --- ### 測驗 `3` [Gap Buffer](https://en.wikipedia.org/wiki/Gap_buffer) 是種動態陣列的實作方式,廣泛用於文字編輯器一類的程式。其手法是將「空白」(gap, 指字串沒有填滿緩衝區的部分) 移動到緩衝區中間,如下圖: ![](https://i.imgur.com/qPd8icC.png) 當我們執行插入或刪除動作時,緩衝區中的 gap 會隨之移動。例如,下面一句話中,初始情況下空白在緩衝區的最後: ``` This is a smple txt.[ ] ``` > 這裡我們使用中括號 (即 ==`[ ]`==) 表示空白 當我們想要在 `smple` 中插入 `a` 字元時,編輯器首先把空白移動到 `s` 後面: ``` This is a s[ ]mple txt. ``` 然後在 `s` 後面插入 `a`: ``` This is a sa[ ]mple txt. ``` 若我們想在 `txt` 中插入一個 `e`,則需要同樣的步驟: ``` This is a sample t[ ]xt. This is a sample te[ ]xt. ``` 這種方法所基於的假設是,編輯文本時通常為連續接受輸入,其他時間則較少更動。 部分 Emacs 變種使用 Gap Buffer,包括古老的 [Emacs on TECO](https://www.emacswiki.org/emacs/TecoEmacs)、現代的 [GNU/Emacs](https://www.gnu.org/software/emacs/) 及早期 [Gosling Emacs](https://en.wikipedia.org/wiki/Gosling_Emacs) (Java 之父 James Gosling 在 1981 年用 C 語言撰寫的 Emacs 編輯器,後來 Richard Stallman 取用部分程式碼打造出 GNU Emacs),和 [Scintilla](https://www.scintilla.org/) (包括 [Code::Blocks](http://www.codeblocks.org/) 許多整合開發環境裡頭使用的程式碼編輯器元件) 也使用 Gap Buffer。某些 Emacs 版本改用 [Linked Line](http://web.mit.edu/~yandros/doc/craft-text-editing/Chapter-6.html)。 一個實作案例:假設文字編輯器的編輯區已有 `Hi, world!` 字串,然後游標 (cursor) 在 `,` 前面,我們用下方表示法: ``` Hi<cursor>, world!。 ``` gap buffer 會先建立下方的陣列,在此我們假設 gap 的長度是 4 且僅有一個 (事實上可能有不少這種 gap),`\xx` 表示 ASCII 編碼為 16 進位 xx 的字元: ``` [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [a] [b] [c] [d] 'H' 'i' \00 \00 \00 \00 ',' ' ' 'w' 'o' 'r' 'l' 'd' '!' ``` 當使用者刪去一個字元後,變成這樣: ``` [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [a] [b] [c] [d] 'H' \00 \00 \00 \00 \00 ',' ' ' 'w' 'o' 'r' 'l' 'd' '!' ``` 使用者輸入 `ello`,變成這樣: ``` [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [a] [b] [c] [d] 'H' 'e' 'l' 'l' 'o' \00 ',' ' ' 'w' 'o' 'r' 'l' 'd' '!' ``` 然後使用者右移游標,變成這樣: ``` [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [a] [b] [c] [d] 'H' 'e' 'l' 'l' 'o' ',' \00 ' ' 'w' 'o' 'r' 'l' 'd' '!' ``` 需要注意的是,當遇到緩衝區填滿的情況,需要重新配置記憶體再複製資料內容,所以 gap buffer 對於大檔案的處理會有效率疑慮。 走訪上述的編輯過程: ``` Hi<cursor>[ ], world! H<cursor>[ ], world! Hello<cursor>[ ], world! Hello,<cursor>[ ] world! ``` 考慮以下 Gap Buffer 實作程式碼: ```cpp #include <stdlib.h> typedef struct { char *buf; size_t size; size_t lb, rb; } gapbuf_buffer_t; typedef enum { GAPBUF_SUCCESS = 0, GAPBUF_ENOMEM, /* Out of memory */ GAPBUF_ERANGE, /* Range error */ GAPBUF_EARG, /* Invalid argument */ GAPBUF_EMAX /* Max error number */ } gapbuf_error_t; gapbuf_error_t gapbuf_insert(gapbuf_buffer_t *gb, const char *buf, const size_t n); gapbuf_error_t gapbuf_delete(gapbuf_buffer_t *gap, size_t n); #include <limits.h> #include <stdio.h> #include <string.h> #include <unistd.h> /* Calculates the capacity of the gap buffer given a requested size. */ static size_t _gapbuf_calc_buf_capacity(const size_t n) { size_t v = n - 1; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; #if (__WORDSIZE == 64) v |= v >> 32; #endif v++; return v; } /** * Grows the buffer such that `n` more characters fit in the gap. * * The functions tests if adding `n` chars to the buffer would * overflow and then reallocates buffer capacity if necessary. * * @param gap Pointer to the gap buffer instance. * @param n The additional number of chars to provision for. * * @return Nonzero on any failure. Consult `errno`. */ static int _gapbuf_provision_buf_capacity(gapbuf_buffer_t *gap, const size_t n) { /* check if we need to extend the size of the buffer */ if (gap->lb + n >= gap->rb) { /* allocate new buffer */ size_t new_siz = _gapbuf_calc_buf_capacity(gap->size + n); char *new_buf; if (!(new_buf = malloc(new_siz))) return -1; /* ENOMEM */ /* copy contents */ size_t new_rb = K333 - gap->size; size_t rlen = gap->size - K444; if (gap->buf) { memcpy(new_buf, gap->buf, gap->lb); memcpy(new_buf + new_rb, gap->buf + gap->rb, rlen); } /* update gap buffer struct */ char *tmp = gap->buf; gap->buf = new_buf; gap->rb = new_rb; gap->size = new_siz; free(tmp); } return 0; } gapbuf_error_t gapbuf_alloc(gapbuf_buffer_t **gb, const char *content, const size_t len) { if (!(*gb = malloc(sizeof(gapbuf_buffer_t)))) return GAPBUF_ENOMEM; (*gb)->size = 0; (*gb)->lb = 0, (*gb)->rb = 0; (*gb)->buf = NULL; K111; return GAPBUF_SUCCESS; } gapbuf_error_t gapbuf_free(gapbuf_buffer_t *gb) { if (gb) { free(gb->buf); free(gb); } return GAPBUF_SUCCESS; } size_t gapbuf_read(const gapbuf_buffer_t *gb, char *buf, const size_t bufsiz) { if (!(gb && buf) || (buf && !bufsiz)) return GAPBUF_EARG; /* copy lhs */ size_t lsiz = gb->lb; size_t n = (bufsiz < lsiz) ? bufsiz : lsiz; memcpy(buf, gb->buf, n); /* copy rhs */ size_t rsiz = bufsiz > 0 ? K222 : 0; n = (n < rsiz) ? n : rsiz; memcpy(buf + gb->lb, gb->buf + gb->rb, n); /* terminate string */ size_t total_len = gb->lb + rsiz; size_t term_index = total_len < bufsiz ? total_len : bufsiz; buf[term_index] = '\0'; return term_index; } gapbuf_error_t gapbuf_insert(gapbuf_buffer_t *gb, const char *buf, const size_t n) { if (!(gb && buf)) return GAPBUF_EARG; if (_gapbuf_provision_buf_capacity(gb, n) != 0) return GAPBUF_ENOMEM; memcpy(gb->buf + gb->lb, buf, n); gb->lb += n; return GAPBUF_SUCCESS; } gapbuf_error_t gapbuf_delete(gapbuf_buffer_t *gb, size_t n) { if (n > gb->lb) /* cannot move beyond left boundary */ return GAPBUF_ERANGE; gb->lb -= n; return GAPBUF_SUCCESS; } gapbuf_error_t gapbuf_fwd(gapbuf_buffer_t *gb, size_t n) { if (n + gb->rb > gb->size) return GAPBUF_ERANGE; memmove(gb->buf + gb->lb, gb->buf + gb->rb, n); gb->lb += n; gb->rb += n; return GAPBUF_SUCCESS; } gapbuf_error_t gapbuf_rwd(gapbuf_buffer_t *gb, size_t n) { if (n > gb->lb) return GAPBUF_ERANGE; memmove(gb->buf + gb->rb - n, gb->buf + gb->lb - n, n); gb->lb -= n; gb->rb -= n; return GAPBUF_SUCCESS; } #define my_assert(test, message) \ do { \ if (!(test)) \ return message; \ } while (0) #define my_run_test(test) \ do { \ char *message = test(); \ tests_run++; \ if (message) \ return message; \ } while (0) int tests_run = 0; static char *test_gapbuf_alloc_happy_path() { printf("%s... ", __func__); char *expected = "0123456789"; gapbuf_buffer_t *gap; my_assert(gapbuf_alloc(&gap, expected, strlen(expected)) == GAPBUF_SUCCESS, "Could not allocate buffer"); my_assert(gap->size == 16, "Unexpected allocation size"); char data[32]; size_t n = gapbuf_read(gap, data, 32); data[n] = '\0'; gapbuf_free(gap); my_assert(strncmp(expected, data, n) == 0, "Initialization string is not consistent"); printf("OK\n"); return 0; } static char *test_gapbuf_alloc_zero_length() { printf("%s... ", __func__); gapbuf_buffer_t *gap; my_assert(gapbuf_alloc(&gap, "", 0) == GAPBUF_SUCCESS, "Could not allocate empty buffer"); my_assert(gap, "Empty buffer allocation failed"); my_assert(gap->size == 0, "Unexpected allocation size"); my_assert(gapbuf_insert(gap, "asdf", 4) == GAPBUF_SUCCESS, "Could not insert into empty buffer"); char data[8]; size_t n = gapbuf_read(gap, data, 8); my_assert(strncmp("asdf", data, n) == 0, "String inconsistency"); gapbuf_free(gap); printf("OK\n"); return 0; } static char *test_gapbuf_read_into_insufficient_buffer() { printf("%s... ", __func__); gapbuf_buffer_t *gap; my_assert(gapbuf_alloc(&gap, "0123456789", 10) == GAPBUF_SUCCESS, "Could not allocate buffer"); char too_short[4]; size_t n = gapbuf_read(gap, too_short, 4); my_assert(strncmp("0123456789", too_short, n) == 0, "String inconsistency for short buffer"); printf("OK\n"); return 0; } static char *test_suite() { my_run_test(test_gapbuf_alloc_happy_path); my_run_test(test_gapbuf_alloc_zero_length); my_run_test(test_gapbuf_read_into_insufficient_buffer); return 0; } int main() { char *result = test_suite(); if (result != 0) { printf("%s\n", result); } else { printf("ALL TESTS PASSED\n"); } printf("Tests run: %d\n", tests_run); return result != 0; } ``` 參考的執行輸出如下: ``` test_gapbuf_alloc_happy_path... OK test_gapbuf_alloc_zero_length... OK test_gapbuf_read_into_insufficient_buffer... OK ALL TESTS PASSED Tests run: 3 ``` 請參照程式碼註解,補完程式碼。 ==作答區== K111 = ? * `(a)` 空白即可 * `(b)` `if (content) return gapbuf_insert(*gb, content, len)` * `(c)` `if (len > 0) return gapbuf_insert(*gb, content, len)` * `(d)` `if (content && len) return gapbuf_insert(*gb, content, len)` K222 = ? * `(a)` `gb->size - gb->rb - 1` * `(b)` `gb->size - gb->rb` * `(c)` `gb->size - gb->lb` * `(d)` `gb->size - gb->lb - 1` * `(e)` `gb->rb` * `(f)` `gb->lb` K333 = ? * `(a)` `gap->lb` * `(b)` `gap->lb + gap->rb` * `(c)` `gap->lb + new_siz` * `(d)` `gap->rb + new_siz` K444 = ? * `(a)` `gap->lb` * `(b)` `gap->rb` * `(c)` `(gap->rb - 1)` * `(d)` `(gap->rb + 1)` * `(e)` `(gap->lb - 1)` * `(f)` `(gap->lb + 1)` :::success 延伸問題: 1. 解釋上述程式碼運作原理並指出實作的缺失; 2. 透過 gcc builtins 和硬體指令去改進 `_gapbuf_calc_buf_capacity` 的效能; 3. 以上述程式碼為基礎,開發簡易的文字編輯器; 4. 學習 [Mazu-Editor](https://github.com/jserv/mazu-editor) 實作手法,探究其原理; ::: ---