# 2019q1 Homework6 (gc)
contributed by < `F74021200` >

---

## 解說和程式碼分析：

### 1. 資料結構：

* **gc_ptr_t**
* 在 gc_alloc() 中呼叫的 malloc() 所配置的空間，會用 gc_ptr_t 紀錄起來以作管理
* 使用 start 紀錄 malloc() 所配置連續空間的第一個位址
* 使用 size 紀錄 malloc() 所配置連續空間的大小
* 使用 mark 紀錄是否仍被使用
* 會被包進 gc_list_t 中形成一個 list node

* **__gc_object**

* type:gc_t
* 一開始在 core.c 中會宣告一個 global 的變數— __gc_object ，利用這個變數，可以管理所有用 gc_alloc() 配置的記憶體空間。

* **ptr_map**

* type:gc_list_t**
* array of the pointer to gc_list_t
* 是 __gc_object 的一個 element
* array 大小： PTR_MAP_SIZE
* array 中，每個 element 連接一個 list ，此 list 中，每個 node 的 type 為 gc_list_t
* 使用 gc_alloc() 配置一個連續空間後，會用一個 type 為 gc_ptr_t 的變數 p 紀錄起來；將此連續空間的第一個位址除以 8 ，再除以 PTR_MAP_SIZE 取餘數 r 後，將 p 包進 gc_list_t 後，並串接到 ptr_map[r] 中。

* **limit**
* type:size_t
* 是 __gc_object 的一個 element
* ptr_map 下最多只能串接 limit 個 list node ，這些 node 的 type 為 gc_list_t

* **min**

* type:uintptr_t
* 由 [cplusplus](http://www.cplusplus.com/reference/cstdint/) ： Integer type capable of holding a value converted from a void pointer and then be converted back to that type with a value that compares equal to the original pointer.
* [why use uintptr_t](https://stackoverflow.com/questions/1845482/what-is-uintptr-t-data-type)
* 用來紀錄被 __gc_object 管理的記憶體中，位址最小的值

* **max**

* type:uintptr_t
* 用來紀錄被 __gc_object 管理的記憶體中，位址最大的值

### 2. mark and sweep:

* **mark**

* 使用 gc_mark_stack() 來 mark 仍被使用的空間
* __gc_object 中的 stack_start 紀錄目前使用的 stack 的開頭位址；在 gc_mark_stack() 中宣告一 local variable ，此 local variable 的位址為此 stack 的最尾端位址，因此，便可利用 gc_mark() 將 stack 中仍在被使用的空間標記起來；另外， __gc_object 的 globals 紀錄目前仍被使用的全域空間，利用此 globals 便可標記這些全域空間。
* 上述的標記動作為：
* 從 __gc_object 中的 ptr_map 下，找出紀錄著配置空間的 list node ，並將其 marked 改為 True 。

* **sweep**

* 使用 gc_sweep() 將目前未被使用的以配置空間釋放掉
* 從 __gc_object 中的 ptr_map 下，找出 marked 為 False 的 list node ，利用這些 list node 的 start 釋放配置空間，再從 ptr_map 中 delete 這些 list node 。

### 3. reference counting:

* ref_count 為 __gc_object 中的一 size_t 型別的 element ，在 __gc_object 被宣告時，會被賦值為 0 ，以此顯示未被其他 function 存取。
* ref_count 的值會被兩個 function 改變 - gc_init() 與 gc_destroy()
* gc_init()
* 增加 ref_count 的值
* 若已經有 function 正在存取 __gc_object 時 (ref_count 之值大於 0) ， gc_init() 會將 ref_count 之值加一 ，表示又有一個 function ( 呼叫 gc_init() 的 function) 會使用 __gc_object 。
* 若 ref_count 之值等於 0 ，表示目前未有 function 存取 __gc_object ，因此初始化 __gc_object ，並將 ref_count 賦值為 1 ，表示目前有一 function (呼叫 gc_init() 的 function) 會使用 __gc_object 。

* gc_destroy()
* 減少 ref_count 的值
* 當一個 function 不再使用 __gc_object 時，會利用 gc_destroy() 嘗試釋放掉 __gc_object 所能存取到的空間。
* 當 ref_count 大於 0 時，代表還有 function 正在使用 __gc_object ，因此將不釋放 __gc_object 所能存取到的空間。
* 當 ref_count 不大於 0 時，代表沒有 function 在使用 __gc_object ，因此會將連接其下的 gc_list_t 型別的 node 空間釋放掉。