# [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` 起)，也就是:

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

> 節點存 $[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~]


樹的示意圖
> BIT 的 binary 並不是指二元樹，而是指「二進位」

更新操作:
> 原有位於索引 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/) 的可能解法:

/* 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 中釋放

示意如下:

實作 `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 ` 物件標記。

時間 t1：因為沒有暫停程式的執行，出現 obj4 指向 obj3

時間 t2: 執行 ` sweep `，刪除物件 obj3, obj4 產生錯誤。

因此，為了讓 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 實作:

#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, 指字串沒有填滿緩衝區的部分) 移動到緩衝區中間，如下圖：


當我們執行插入或刪除動作時，緩衝區中的 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 實作程式碼:

#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) 實作手法，探究其原理;
:::

---