# 2019q1W7下: 方鈺學

## 測驗 `1`
### 運作機制

:::info
延伸閱讀: [Precise Garbage Collection for C](https://www.cs.utah.edu/plt/publications/ismm09-rwrf.pdf) 有 Linux 核心的 GC 使用案例
:::

Contained two phases, `Mark` and `Sweep`.
#### `Mark` Phase
從 root 開始，找尋 `可到達` 的物件。 ( `Reachable Objects` )
標記 `可到達` 的物件。
#### `Sweep` Phase
從 heap 中，找尋未被標記的物件( `Unreachable Objects` )，即需要被清除的物件。
將未被標記的物件加入到 `free list` 中，準備清除。
將已被標記的物件重置為未被標記，以利下次的清掃。

### 如何實作
#### 簡單實作 `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 階段需要記憶體空間去創造訪問清單( `todo` ) 。
* 訪問清單( `todo` )無法預測大小，因此無法預先保留。
##### 解決方法
* 應用 `pointer reversal` ，用 `depth first search` 取代訪問清單。
#### 問題點 `2`
* 有些物件沒有指標的空間。
##### 解決方法
* 使用一個暫存器記憶其 `parent` 位置，就可以不用 `pointer reversal` 也能執行 `depth firsth search` 。

## 測驗 `2`
`string-separate.c` :

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "gc.h"

#define IS_DEL(c, d) (c == d)

static int count_words(char *s, char delimiter)
{
    int i = -1, words = 0;
    while (s[++i])
        if (((i != 0 && IS_DEL(s[i], delimiter) &&
              !IS_DEL(s[i - 1], delimiter)) ||
             (s[i + 1] == '\0' && !IS_DEL(s[i], delimiter))))
            words++;
    return words;
}

static char *get_word(char *s, char delimiter)
{
    int i = -1, size = 0;
    while (s[++i] && !IS_DEL(s[i], delimiter))
        size++;
    char *word = gc_alloc(sizeof(char) * (size + 1));
    word[size] = '\0';
    while (*s && !IS_DEL(*s, delimiter)) {
        *word++ = *s;
        s++;
    }
    return word - size;
}

char *my_strdup(char *s)
{
    if(!s)
        return NULL;
    int size = 0;
    int i = -1;
    while(s[++i])
        size++;
    char *word = gc_alloc(sizeof(char)*(size+1));
    word[size] = '\0';
    i = -1;
    while(s[++i]){
        word[i] = s[i];
    }
    return word;
}

char **my_strsep(char *s, char delimiter)
{
    if (!s)
        return NULL;

    char **tab;
    int size = count_words(s, delimiter);
    if (!(tab = gc_alloc((size + 1) * sizeof(char *))))
        return NULL;

    tab[size] = 0;
    char *str = s;
    while (*str) {
        if (!IS_DEL(*str, delimiter)) {
            *tab++ = get_word(str, delimiter);
            str += strlen(get_word(str, delimiter)) - 1;
        }
        str++;
    }
    return tab - size;
}

int main(int argc, char *argv[])
{
    gc_init(&argc, 1);

    char **sep = my_strsep("hello,world", ',');
    assert(sep);
    char *dup = my_strdup("hello,world");
    assert(dup);
    printf("%s\n", sep[0]);
    printf("%s\n", sep[1]);
    printf("%s\n", dup);
    gc_run();

    gc_dump_internals();
    gc_destroy();

    return 0;
}

`strdup()` :

char *my_strdup(char *s)
{
    if(!s)
        return NULL;
    int size = 0;
    int i = -1;
    while(s[++i])
        size++;
    char *word = gc_alloc(sizeof(char)*(size+1));
    word[size] = '\0';
    i = -1;
    while(s[++i]){
        word[i] = s[i];
    }
    return word;
}

###### tags: `Cprogramming` `LinuxKernel`