2020q3 第 14 週測驗題

tags: sysprog2020

目的: 引導學員挑戰 LeetCode 並掌握位元處理和記憶體管理

作答表單

---

測驗 1

LeetCode 1409. 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:

Binary indexed tree: Fenwick tree 是個處理前綴時很有效率的資料結構，也稱為 Binary indexed tree，或簡稱 BIT。以下簡稱它為 BIT。對於一個長度為 n 的陣列，BIT 可以在

$O(n)$ 的時間初始化，在

$O(\log n)$ 時間詢問一個前綴的訊息 (例如前綴和)，以及在

$O(\log n)$ 的時間修改其中一個值。雖然複雜度和線段樹相同，但 BIT 的時間常數比線段樹小得多，空間也比較小 (只需要多開一個大小恰好為 n 的陣列即可)，程式碼也非常精簡 。一般來說，如果問題的性質可以使用 BIT，效率會和使用線段樹有明顯的差別。

lowbit: 二進位最後一個 1 的位置所代表的數值
範例:

• 13 = 1101₂
  $\to$ lowbit(13) = 0001₂ = 1
• 12 = 1100₂
  $\to$ lowbit(12) = 0100₂ = 4

節點存

$[i-lowbit(i)+1,1]$ 的和。
父節點為

$i-lowbit(i)$
第一列為原陣列 (即

$1,7,3,0,...]$，第二到第四列依次填入數字
方便起見，此處的陣列的索引為自 1 開始

建構 BIT:

• prefixSum(13) = prefixSum(00001101₂)

  = BIT[13] + BIT[12] + BIT[8]
  = BIT[00001101₂] + BIT[00001100₂] + BIT[00001000₂]

樹的示意圖

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

更新操作:

原有位於索引 5 的數值 5 增加 2 而成為 7

BIT 時間複雜度

• 修改:
  $O(\log n)$
• 查詢:
  $O(\log n)$

考慮以下程式碼為 1409. 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

作答區

PPP = ?

• (a) -1
• (b) 0
• (c) 1

QQQ = ?

• (a) i
• (b) 0
• (c) queries_size
• (d) queries_size - 1
• (e) queries_size - i

延伸問題:

1. 解釋上述程式碼運作原理，並分析時間複雜度
2. Binary Indexed Tree 有哪些應用？請舉例並分析
3. 研讀 Fenwick Treeの定数倍高速化，探究上述程式碼改進的機會

---

測驗 2

CS:APP 第 9 章提到 garbage collector (以下簡稱 GC)，其中 Mark and Sweep 是經典的演算法，後者分為 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 階段需要記憶體空間去創造訪問清單 。
• 存取清單無法預測大小，因此無法預先保留。

解決方法

• 應用 pointer reversal，用 depth first search 取代存取清單。

問題點 2

• 有些物件沒有指標的空間。

解決方法

• 使用一個暫存器記憶其 parent 位置，就可不用 pointer reversal 也能執行 depth firsth search 。

• Tri-Color 演算法與 Golang

  Reference: Golang realtime garbage collector

上述的 mark and sweep 演算法有個缺點。每次在執行 mark 時，都需要將程式的執行予以暫停。

• 標記時，需要讓所有 object 維持不變，才能保持不出錯。

舉例： 以下程式具備物件 obj₀, obj₁, obj₂, obj₃

時間 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 的虛擬機器和 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

延伸問題:

1. 解釋上述程式碼運作原理，並且指出其不足和實作錯誤之處
2. 針對 Tri-colored 演算法，改進上述程式碼，使得符合演算法設計

---

測驗 3

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、現代的 GNU/Emacs 及早期 Gosling Emacs (Java 之父 James Gosling 在 1981 年用 C 語言撰寫的 Emacs 編輯器，後來 Richard Stallman 取用部分程式碼打造出 GNU Emacs)，和 Scintilla (包括 Code::Blocks 許多整合開發環境裡頭使用的程式碼編輯器元件) 也使用 Gap Buffer。某些 Emacs 版本改用 Linked Line。

一個實作案例：假設文字編輯器的編輯區已有 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)

延伸問題:

1. 解釋上述程式碼運作原理並指出實作的缺失;
2. 透過 gcc builtins 和硬體指令去改進 _gapbuf_calc_buf_capacity 的效能;
3. 以上述程式碼為基礎，開發簡易的文字編輯器;
4. 學習 Mazu-Editor 實作手法，探究其原理;

---