---
tags: linux kernel class
---
# 將 treesort 整合進 `lab0-c`
contributed by < `willwillhi1` >
> [treesort.c](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-1)
* 程式碼的理解在 [willwillhi1 / quiz3](https://hackmd.io/@willwillhi/linux2023q1-quiz3) 中
### 修改程式
#### `node_t` 結構體
參考作業一的 `list_head` 的實作，將原本的結構體中用來表示紅黑樹的地方抽離出來單獨使用。
原本的實作為以下，將 `uintptr_t color`, `struct __node *left, *right` 從 `node_t` 裡移出來。
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
:::warning
使用一致的程式碼縮排方式，亦即 4 個空白 (而非 tab)。
:notes: jserv
> 已修正
:::
抽離出來用來表示紅黑樹的結構體定義為 `rb_node` ：
```c
struct rb_node {
uintptr_t color;
struct rb_node *right;
struct rb_node *left;
} __attribute__((aligned(sizeof(long))));
```
而原本的 `node_t` 結構體會變成：
```c
typedef struct __node {
struct rb_node node;
struct list_head *list;
} node_t;
```
其中裡面的 `list_head` 指標指向 `element_t` 結構體裡面的 `list_head`，`element_t` 用來表示佇列的資訊，詳細的教學可以參考 [你所不知道的C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)。
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
最後對用來表示整個 `map` 資訊的 `cmap_internal` 做一些小修改 :
* `node_t *head` 改成 `struct rb_node *head`，表示整顆紅黑樹的 `root`。
* `cmap_iter_t it_end, it_most, it_least` 這個部份還在思考要改成 `element_t` 或是 `list_head` 或 `struct rb_node`。
:::warning
保留 `cmap_iter_t` 的風格，作為走訪節點的通用 iterator
:notes: jserv
> 使用 `struct *rb_node` 可以作為走訪節點的通用 iterator
:::
* `comparator` 的部份，因為 `element_t` 的 `value` 的型別是字串，所以先改成以下作為替代，其中 `_CMP_LESS`, `_CMP_GREATER`, `_CMP_EQUAL` 分別代表 -1, 1, 0。
```c
/* string comparison */
static inline int cmap_cmp_str(void *arg0, void *arg1)
{
char *a = (char *) arg0, *b = (char *) arg1;
int result = strcmp(a, b);
return result < 0 ? _CMP_LESS : result > 0 ? _CMP_GREATER : _CMP_EQUAL;
}
```
建立節點的部份修改為以下，傳入的參數為 `element_t` 結構體裡的 `list_head` 的位址，然後 `cmap_create_node` 將紅黑樹節點初始化(將節點的左、右，及親子節點初始化為 `NULL`，顏色標成紅色)。
```c
static inline node_t *list_make_node(struct list_head *list)
{
node_t *node = malloc(sizeof(node_t));
node->list = list;
cmap_create_node(node);
return node;
}
```
#### free
在 `tree_sort` 最後執行，負責釋放整顆樹所用到的空間，目前的想法是用 `DFS` 的方式來走訪所有節點並釋放記憶體。
```c
static void tree_free(struct rb_node* node)
{
if (!node)
return;
tree_free(node->left);
tree_free(node->right);
free(container_of(node, node_t, node));
}
```
#### 印出 level order
用來在開發時查看整個樹的架構，方便除錯
目前是採用時間複雜度 $O(N^2)$ 的方法
邏輯是依照樹高來印出該層的所有點，並用遞迴的方式來走訪所有的階層。
`print_current_level` 負責印出第 `i` 層所有點。
```c
void print_level_order(struct rb_node* root)
{
int h = height(root);
for (int i = 1; i <= h; i++)
print_current_level(root, i);
printf("\n");
}
```
#### 紅黑樹的旋轉操作
基本的 `cmap_rotate_left`, `cmap_rotate_right` 和 平衡 `LL`, `LR`, `RR`, `RL` 情況對應的操作 `cmap_l_l`, `cmap_l_r`, `cmap_r_r`, `cmap_r_l`
做的修改只有把結構體 `node_t` 改成新定義的 `rb_node`。
#### cmap_calibrate
透過走訪整棵紅黑樹來重新計算整個佇列中的最大與最小值
最大就是從 `root` 開始一直往右找，反之最小則是往左。
```c
/* Recompute it_least and it_most */
obj->it_least = obj->it_most = obj->head;
while (obj->it_least->left)
obj->it_least = obj->it_least->left;
while (obj->it_most->right)
obj->it_most = obj->it_most->right;
```
測試結果
```
cmd> shuffle
l = [6 4 2 5 3 1]
cmd> tree_sort
least: 1
most: 6
l = [1 2 3 4 5 6]
```
#### cmap_insert
在原本的實作中有三個參數：
* `cmap_t obj`: 代表整個 `map` 的資訊。
* `node_t *node`: 改為要插入的 `element_t` 的 `list_head` 位址。
* `void *value`: 這裡在原本實作中是可以改進的，目前不會處理碰撞發生的情況，如果發生就會跳錯 `not support repetitive value`。
* 取值： 先用 `container_of` 取得 `node_t` 的位址再用它的 `list_head *list` 成員去存取 `element_t` 中的 `value`。
```c
char *node_value = container_of(container_of(rbnode, node_t, node)->list, element_t, list)->value;
char *cur_value = container_of(container_of(cur, node_t, node)->list, element_t, list)->value;
```
#### `tree_sort`
`tree sort` 分成兩個部份，分別是建立紅黑樹然後在透過走訪樹來將佇列排序。
* 建立紅黑樹，利用 `list.h` 裡的 `list_for_each` 來走訪整個佇列，同時建立紅黑樹的節點。
```c
list_for_each(list, head) {
cmap_insert(map, list, NULL);
// print_level_order(map->head);
}
```
* 對整個佇列排序
`cmap_first` 會回傳紅黑樹中位置最左的節點，也就是佇列中 `value` 最小的點。
`cmap_next` 會找到該點在樹中的下一個順位的點，會分成兩個情況：
* 如果該點有右子點，就往右走然後一直往左
* 如果沒有右子點，那麼就往親代節點找，這時候如果對於親代節點來說該點是右節點就繼續往上(親代節點)找，直到變成左節點或到 `root` 為止。
下面程式中的 `for` 迴圈用 `cmap_next` 依序走訪整棵樹，然後用 `list_del` 將該點從佇列中移除後再用 `list_add` 加入。
```c
node_t *node = cmap_first(map);
if (!node) {
free(map);
return;
}
for (node_t *next = cmap_next(&node->node); next; next = cmap_next(&node->node)) {
list_del(next->list);
list_add(next->list, node->list);
node = next;
}
```
最後釋放記憶體
```c
tree_free(map->head);
free(map);
```
#### `qtest` 修改
在 `qtest` 中新增 `do_tree_sort` 函式。
```c
static bool do_tree_sort(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
int cnt = 0;
if (!current || !current->q)
report(3, "Warning: Calling sort on null queue");
else
cnt = q_size(current->q);
error_check();
if (cnt < 2)
report(3, "Warning: Calling sort on single node");
error_check();
if (current && exception_setup(true)) {
tree_sort(current->q);
}
exception_cancel();
bool ok = true;
if (current && current->size) {
for (struct list_head *cur_l = current->q->next;
cur_l != current->q && --cnt; cur_l = cur_l->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
element_t *item, *next_item;
item = list_entry(cur_l, element_t, list);
next_item = list_entry(cur_l->next, element_t, list);
if (strcmp(item->value, next_item->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
q_show(3);
return ok && !error_check();
}
```
最後在 `console_init` 函式中加入 `tree_sort` 命令。
```c
ADD_COMMAND(tree_sort, "Use red black tree to sort the queue", "");
```
:::warning
TODO: 引入 option，讓 `qtest` 得以在執行時期切換不同的排序實作，有助於後續分析。
:notes: jserv
:::
引入 `option`
首先在 `q_test` 中宣告全域變數 `enable_rb_tree_sort`
```c
static int enable_rb_tree_sort = 0;
```
然後修改 `do_sort` 函式中的部份程式，用來判斷執行 `sort` 時要用什麼樣的方法排序
```c
if (current && exception_setup(true)) {
if (enable_linux_list_sort)
list_sort(NULL, current->q, compare);
else if (enable_rb_tree_sort)
tree_sort(current->q);
else
q_sort(current->q);
}
```
最後在 `console_init` 函式中加入對應的 `option` 的參數
```c
add_param("tree_sort",
&enable_rb_tree_sort,
"Enable red black tree sort",
NULL);
```
執行時期可以任意變更排序方法
```
cmd> shuffle
l = [2 0 7 6 9 4 8 1 3 5]
cmd> option tree_sort 1
cmd> sort
4 2 7 0 3 6 9 nil 1 nil nil 5 nil 8 nil
l = [0 1 2 3 4 5 6 7 8 9]
cmd> option tree_sort 0
cmd> option linux_sort 1
cmd> shuffle
l = [3 8 2 0 7 5 4 9 6 1]
cmd> sort
l = [0 1 2 3 4 5 6 7 8 9]
```
#### 測試
* 對 0 ~ 9 排序
第五行輸出為整棵樹的 `level order`
```=
cmd> show
Current queue ID: 0
l = [3 1 2 7 0 6 8 4 9 5]
cmd> tree_sort
2 1 6 0 nil 4 8 nil nil 3 5 7 9
l = [0 1 2 3 4 5 6 7 8 9]
```
* 隨機產生 100 筆
```
cmd> it RAND 100
l = [xrfwhz ftmlgo kfmwkdbdx whoaexr wiodk quvcx upgbawu pbndrtv omcotnew uofep umzkndty lmygmppbh nkbgeb tcemua kjchcyprt rhnuum xznxygkj ukxtcx atvavkle vpqgw wigsrvdrs jpyufzd ikkrnmpju uvwxlxdm pjpelvwn odhqkyb fsphoizy hrcmsed ayrgizmb jyudxef ... ]
cmd> tree_sort
pbndrtv ftmlgo upgbawu dgmqlzvhz kfmwkdbdx rhnuum whoaexr cvpicnbua eeyjxo hrcmsed nkbgeb pqgnvkpop txbhwduxr vbtcamvuw xznxygkj ayrgizmb cwenxpta drqlz fbgjlviv grwyjlzb jjeqv lmygmppbh omcotnew pednu quvcx tcemua umzkndty uvwxlxdm vpqgw wiodk yodrltlqh atvavkle bpweopbs cwbhlv cxyxciq dpwmfyt edaiq etusjryv fsphoizy fwalkzr hnxfnc ikkrnmpju jtkdd ktmyocr mhvspe odhqkyb ooxubo pcsckfemz pkbuhejjw nil nil smpifvvbo tqiwnssmj ukxtcx uofep nil uwjxnupts nil walpjtma wigsrvdrs xkjap yjeub znrrp adavrgqa nil blvvycwcm csxkd nil nil nil nil nil nil nil eehba nil nil fjfteu nil fuckt nil hmech nil icesjd jgkhxm jpyufzd jzqpmw kjchcyprt kylup lovrbun mosxqbhc nil okkmhm omnydkf oqlqrxq pbvsmd nil pjpelvwn pltyjd roszmz tbuduss nil trwudfze nil nil nil nil nil nil nil nil nil nil wpwdbju xrfwhz nil nil yxnvklfe zttgrhcxm nil nil nil nil nil nil nil nil nil nil nil nil nil nil hsornbnp nil nil nil jlumjan nil jyudxef kecwozis kfodbg kqvgoi kwfknhxng lgwau nil nil mnippyie nil nil nil nil nil nil oykzxcdg nil nil nil nil nil nil nil rzlkelkm snaeobods nil nil nil nil xddkwa nil nil nil nil nil nil
l = [adavrgqa atvavkle ayrgizmb blvvycwcm bpweopbs csxkd cvpicnbua cwbhlv cwenxpta cxyxciq dgmqlzvhz dpwmfyt drqlz edaiq eehba eeyjxo etusjryv fbgjlviv fjfteu fsphoizy ftmlgo fuckt fwalkzr grwyjlzb hmech hnxfnc hrcmsed hsornbnp icesjd ikkrnmpju ... ]
```
* 用 `time` 命令測試 `10000` 筆資料的執行時間
```
cmd> it RAND 10000
l = [deyjlwbu oipohcuj seosytsv emsfjz ofgqfee okqmdz pqxff cvtdeukif zevbevho fbxasn sufgjqfgn tzmyxwoxd ujernnrai sityjiep yzvugyv aluvqsw qumzfv szcuckck wxxdeh nhmocbw esfztdus veevab itpctn vbrtxzf ifjad homjxeqf kxaki jebzqhyyg rewzk bimrdugr ... ]
cmd> time sort
l = [aaacjup aaapjnrdx aabivxsx aafjaxr aagkwem aaira aaiubccca aamrcxns aapnkal aapvd aararb aarksrhi aarpwbgv aastvghzq aawvw aaxjvlz aaxxm aayyjy aazddg aazwqbym abbwj abcaotlpm abdukla abeadfln abevtxr abhactu abjprlq ablyw abmksjwnk abnpiw ... ]
Delta time = 0.277
```
`tree_sort` 平均五次下來為 `0.269 s`，
對比原本實作的 `merge sort` 平均五次的執行時間為 `0.0086 s` 有很大的差距。
想了一下會有這樣的結果第一個可能是我的實作的效率可能不好，還有改進的空間。
另一個可能是 [Wikipedia](https://en.wikipedia.org/wiki/Tree_sort) 所提及的做一次排序就要重新建一次樹，也就是需要使用 `malloc` 配置額外的空間，相較之下原本實作的 `merge sort` 因為是 in-place，所以執行成本相對較低。
:::warning
TODO: 引入 memory pool (課程測驗題已提過)，預先配置好記憶體，之後重用該空間，從而縮減動態記憶體配置的成本。
:notes: jserv
:::
### 引入 memory pool
參考 [rv32emu](https://github.com/sysprog21/rv32emu/blob/master/src/mpool.c) 的 `memory pool` 後實作一個醜醜的簡易版本。
新增 `mpool.h` 和 `mpool.c`
在 `mpool.h` 定義一個結構體 `mpool_t`，用來事先配置記憶體給紅黑樹，從而簡少 `tree sort` 配置記憶體的成本。
`node_count` 代表 `memory pool` 目前的節點個數。
`mapped` 代表配置的記憶體的起始位置。
```
typedef struct mpool {
size_t node_count;
node_t *mapped;
} mpool_t;
```
接下來 `mpool` 提供的函式依序有:
#### `mpool_create`
用來建立 `memory pool`，然後依照輸入的佇列的長度初始化。
```
mpool_t *mpool_create(struct list_head *head)
{
mpool_t *new_mp = malloc(sizeof(mpool_t));
if (!new_mp)
return NULL;
size_t size = q_size(head);
new_mp->node_count = size;
node_t *n = malloc(sizeof(node_t) * size);
if (!n)
return NULL;
new_mp->mapped = n;
return new_mp;
}
```
#### `mpool_alloc`
在已經建立 `memory pool` 的情況下，判斷是否需要配置更多的記憶體，若是則 `free` 掉目前的空間後再重新配置一次，反之則什麼都不做返回。
```
void mpool_alloc(mpool_t *mp, struct list_head *head)
{
if (!mp)
return;
size_t new_size = q_size(head);
if (new_size <= mp->node_count)
return;
mpool_free(mp);
mp->node_count = new_size;
mp->mapped = malloc(sizeof(node_t) * new_size);
}
```
重新配置記憶體的部份一開始是用 `realloc`，不過目前會遇到以下的問題，還在 `debug` 中...。
:::info
可參考 rv32emu 的 `mpool.c` 中的 `mpool_extend()`，避免 free 掉原先已配置好的記憶體
:notes: qwe661234
:::
```
mremap_chunk(): invalid pointer
```
#### `mpool_size`
回傳目前 `memory pool` 的節點個數。
```
size_t mpool_size(mpool_t *mp)
{
if (!mp)
return 0;
return mp->node_count;
}
```
#### `mpool_free`
負責釋放 `memory pool` 動態配置出來的空間，然後把 `node_count` 歸零。
```
void mpool_free(mpool_t *mp)
{
if (!mp || !mp->mapped)
return;
free(mp->mapped);
mp->node_count = 0;
}
```
#### `mpool_destory`
釋放掉整個 `mpool_t` 結構體所用到的空間。
```
void mpool_destory(mpool_t *mp)
{
mpool_free(mp);
free(mp);
}
```
#### 對 `tree_sort` 的修改
`tree_sort` 的參數新增一個 `node_t *node_t_pool` 代表事先分配好的節點空間。
建立紅黑樹的部份改成以下程式，`index` 從零開始累加，`node_t_pool + (index++)` 表示該次分配的節點的位址。
```
size_t index = 0;
list_for_each (list, head) {
cmap_insert(map, node_t_pool + (index++), list, NULL);
}
```
最後在釋放記憶體的時候不需要釋放紅黑樹節點的空間。
```diff
- tree_free(map->head);
free(map);
```
負責建立以及初始化節點的函式 `list_make_node` 做一些小修改，將紅黑樹節點的位址通過參數傳入使用。
```diff
- static inline node_t *list_make_node(struct list_head *list)
+ static inline node_t *list_make_node(node_t *node, struct list_head *list)
{
- node_t *node = malloc(sizeof(node_t));
node->list = list;
cmap_create_node(node);
return node;
}
```
#### `qtest` 的修改
整體的想法是要在 `qtest` 準備好 `memory pool`，讓 `treesort` 使用。
所以新增了一個命令 `mem_pool` 負責做這件事。
首先是全域變數的宣告
`mpool_t` 結構體的指標 `mp`
以及 `call_mem_pool_times` 代表呼叫 `mem_pool` 的次數。
```
static mpool_t *mp = NULL;
static size_t call_mem_pool_times = 0;
```
`do_mem_pool` 函式會先判斷輸入是否正確和佇列是否為空
```
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q) {
report(3, "Warning: Queue is null");
return false;
}
```
然後依照 `call_mem_pool_times` 來判斷要呼叫什麼函式
如果是 `call_mem_pool_times` 等於零就建立及初始化 `memory pool`，大於零則判斷目前空間是否夠用，不夠則重新配置。
```
if (current && exception_setup(true)) {
if (!call_mem_pool_times++) {
mp = mpool_create(current->q);
} else {
mpool_alloc(mp, current->q);
}
}
```
最後會輸出目前的 `memory pool` 大小。
```
printf("Current mpool size: %ld\n", mpool_size(mp));
```
`do_free` 函式要多加入釋放 `memory pool` 的程式。
```diff
if (mp) {
call_mem_pool_times = 0;
mpool_destory(mp);
}
```
`q_quit` 函式同樣也要。
```diff
if (exception_setup(true)) {
struct list_head *cur = chain.head.next;
while (chain.size > 0) {
queue_contex_t *qctx, *tmp;
tmp = qctx = list_entry(cur, queue_contex_t, chain);
cur = cur->next;
q_free(qctx->q);
free(tmp);
chain.size--;
}
+ if (call_mem_pool_times)
+ mpool_destory(mp);
}
```
#### 測試
建立一個佇列 [1, 3, 0, 2]
然後用 `mem_pool` 命令建立對應大小紅黑樹節點空間
最後再用 `sort` 命令測試是否可以正常執行排序
```
cmd> option tree_sort 1
cmd> show
Current queue ID: 0
l = [1 3 0 2]
cmd> mem_pool
Current mpool size: 4
cmd> sort
1 0 3 nil nil 2 nil
l = [0 1 2 3]
```
如果對佇列插入 `4` 後再次使用 `mem_pool` 命令
則會擴增 `memory pool` 的空間
```
cmd> it 4
l = [0 1 2 3 4]
cmd> shuffle
l = [1 4 2 3 0]
cmd> mem_pool
Current mpool size: 5
cmd> sort
2 1 4 0 nil 3 nil
l = [0 1 2 3 4]
```
最後可以用 `free` 或直接 `quit` 都可以釋放掉 `memory pool` 的空間。
```
cmd> free
l = NULL
cmd> quit
Freeing queue
```
初步測試效能，以 `10000` 為基準:
```
cmd> it RAND 10000
l = [bwerm cvvstr kqicwynl eokhsrmkq xoatiswcw tdreu fbgdwse wmqmficd mknbur yodgls clzwrmh pigrtg cbohm hnuaq lixdteju pcfst buuej cghejy ftcpbw vvuos wtrmfkl jrlgxno fqvvkuct vasvap flikam njcmzswu hcekpmhe upuutur uxtncna ekcxluc ... ]
cmd> mem_pool
Current mpool size: 10000
cmd> option tree_sort 1
cmd> time sort
l = [aacmeyfu aadsegl aahglkdhf aalfkmsn aambzf aaocofkko aapek aaqaub aatekwcl aatqgnzr aavazsc aaznjysds aazoedri abasotz abdal abhpwsmnm abipv abivfhc abjcq abjdkn abjhq abjthieyo abkkuhapg ablqosi abpuqa abrhymj abudbhjtp abuueh abvlzfybw acbparwji ... ]
Delta time = 0.011
```
平均五次下來為 `0.0122 s`，與先前的實作的執行時間 `0.269 s` 相比大幅的下降。
不過與原實作的 `merge sort` 的 `0.0086 s` 相比還是較差。
TODO: 更詳細的效能比較或畫圖
### 修改實作後的 `memory pool`
為了避免每次擴大 `pool` 都需要 `free`，所以做進一步的修改，`mpool` 改為：
```c
typedef struct mpool {
size_t arena_count;
size_t node_count;
arena_t *first_arena;
arena_t *last_arena;
} mpool_t;
```
:::warning
其實 "[arena](https://www.dictionary.com/browse/arena)" 會比 "[area](https://www.dictionary.com/browse/area)" 用字更精準
* area: any section reserved for a specific function
* arena: a central stage, ring, area, or the like, used for sports or other forms of entertainment, surrounded by seats for spectators
:notes: jserv
> 了解！
:::
`arena` 儲存每次新增的節點記憶體的起始 (`first_mapped`) 到最後 (`last_mapped`) 的位址，`next` 表示下一個 `arena` 的位址。
```c
typedef struct arena {
mem_node_t *first_mapped;
mem_node_t *last_mapped;
struct arena *next;
} arena_t;
```
最後的 `mem_node_t` 結構體為了避免在 `qtest` 會有重複宣告的情況發生，所以會先檢查是否有定義過。
`mem_node_t` 所儲存的資訊就是紅黑樹的節點以及下一個 `mem_node_t` 的位址。
```c
#ifndef MEM_NODE
#define MEM_NODE
typedef struct mem_node {
node_t node;
struct mem_node *next;
} mem_node_t;
#endif
```
`mpool_create` 也要做對應的修改，初始化 `mpool_t *new_mp` 的部份為：
```c
mpool_t *new_mp = malloc(sizeof(mpool_t));
if (!new_mp)
return NULL;
size_t size = q_size(head);
new_mp->node_count = size;
new_mp->arena_count = 1;
arena_t *arena = malloc(sizeof(arena_t));
new_mp->first_arena = arena;
new_mp->last_arena = arena;
```
配置與輸入佇列相同長度的 `mem_node_t` 空間後再將其連結起來，最後分別將其開頭與尾端位址存到 `arena` 的 `first_mapped` 和 `last_mapped` 中。
```c
mem_node_t *n = malloc(sizeof(mem_node_t) * size);
if (!n)
return NULL;
mem_node_t *cur = n;
for (int i = 0; i < size - 1; ++i) {
cur[i].next = cur + i + 1;
}
cur[size - 1].next = NULL;
arena->first_mapped = cur;
arena->last_mapped = cur + size - 1;
arena->next = NULL;
```
`mpool_alloc` 修改邏輯與 `mpool_create` 大致相同，只是需要先判斷目前的空間是否夠用。
```c
size_t new_size = q_size(head);
if (new_size <= mp->node_count)
return;
```
如果不夠就宣告新的 `arena` 並且初始化。
```c
size_t size = new_size - mp->node_count;
mp->node_count = new_size;
mp->arena_count = mp->arena_count + 1;
arena_t *arena = malloc(sizeof(arena_t));
mem_node_t *n = malloc(sizeof(mem_node_t) * size);
if (!n)
return;
mem_node_t *cur = n;
for (int i = 0; i < size - 1; ++i) {
cur[i].next = cur + i + 1;
}
cur[size - 1].next = NULL;
arena->first_mapped = cur;
arena->last_mapped = cur + size - 1;
```
最後把初始化後的 `arena` 接到 `mpool_t` 的最尾端 (`last_arena`)。
```c
mp->last_arena->next = arena;
mp->last_arena->last_mapped->next = arena->first_mapped;
mp->last_arena = arena;
arena->next = NULL;
```
`mpool_free` 負責釋放所有 `arena` 裡頭的 `mem_node_t` 空間以及 `arena` 結構體本身
```c
arena_t *cur = mp->first_arena;
while (cur) {
arena_t *tmp = cur;
cur = cur->next;
free(tmp->first_mapped);
free(tmp);
}
```
然後把 `arena_count`, `node_count` 歸零，`first_arena`, `last_arena` 重新指向 `NULL`。
```c
mp->arena_count = 0;
mp->node_count = 0;
mp->first_arena = NULL;
mp->last_arena = NULL;
```
`queue.h` 的修改
因為 `treesort` 函式需要用到 `mem_node_t` 結構體，所以再宣告一次 `mem_node_t`。
```c
#ifndef MEM_NODE
#define MEM_NODE
typedef struct mem_node {
node_t node;
struct mem_node *next;
} mem_node_t;
#endif
```
修改 `treesort` 函式
透過 `mem_node_t` 的 `next` 指標來取得下一個節點的位址。
```c
void tree_sort(struct list_head *head, struct mem_node *pool)
{
...
struct mem_node *cur = pool;
list_for_each (list, head) {
cmap_insert(map, &cur->node, list, NULL);
cur = cur->next;
// print_level_order(map->head);
}
...
}
```
最後 `qtest` 的修改只需要將 `tree_sort` 函式改為對應的參數即可。
```c
else if (enable_rb_tree_sort) {
tree_sort(current->q, mp->first_arena->first_mapped);
}
```
因應 `qtest` 原本的 `do_sort` 函式規定在做排序時不能動態配置記憶體的需求。
```c
set_noallocate_mode(true);
if (current && exception_setup(true)) {
if (enable_linux_list_sort)
list_sort(NULL, current->q, compare);
else if (enable_rb_tree_sort) {
tree_sort(current->q, mp->first_arena->first_mapped);
} else
q_sort(current->q);
}
exception_cancel();
set_noallocate_mode(false);
```
之前已經透過 `memory pool` 的方式事先配置節點的記憶體了，不過 `tree sort` 在建立 `struct cmap_internal` 時會用到 `malloc`。
```c
void cmap_new(size_t s1, size_t s2, int (*cmp)(void *, void *), cmap_t obj)
{
cmap_t obj = malloc(sizeof(struct cmap_internal));
...
}
```
所以在 `treesort` 函式宣告區域變數來解決這個問題。
```c
void tree_sort(struct list_head *head, struct mem_node *pool)
{
struct cmap_internal map;
cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_str, &map);
...
}
```
最後做個小測試：
```
cmd> option tree_sort 1
cmd> new
l = []
cmd> it RAND 1000
l = [ewleir tgwmqxbx otdcamq qkkcaecki linxjp wzjix hwicrg phoxt wgalcghlx bdahadxz kggobz bufum jwhqjm pkflj vqgepbrft itihaq iodzjvwmz juawqptmu wjtajmeqn jxhkmaakr luoeyqfe nydcckxtf vtvgy caffaifv yxbhyrj zyhuevhc kfgkcmoz vrefz ftmwg ikpyo ... ]
cmd> mem_pool
Current mpool size: 1000
cmd> sort
l = [abdgomey acydelyfy adiybmu adltemlk adxuzomi agbwobfz ageru agkldlqgb ahocaz aivrqeat ajlxdwypy ajxkcjom akcmv akylew alcnytf anqmljcuh aodbbkr aokiefbc arjrxsmu ascxqkmyl asskxzud asuemv atgmdmr ausmclo auvfhlab avadi avhxqueoq bdahadxz bdjdmorsj bdryoeelp ... ]
cmd> new
l = []
cmd> it RAND 1000
l = [svbvmxrdb uadotsp xaczycfx kdlpibck ccocro nqcnqe otamkn altumyt jxlpi cipckae rbtgnhoe evoeza oluke lphgjua oogvrdynd npzpffss ucvunct nwzmapyln ioivyeuaa ddixnzql jndlvckg ndccovg odwmlbzj xgdzez ppvhqt ffxcchdsz rdppy cxqrohntb csfkodtu zanihui ... ]
cmd> mem_pool
Current mpool size: 1000
cmd> sort
l = [aapdssaf abjkxhs abniq abwkmpknf abzwmhwa aelhfgap aercjoitb aeuutwfl afgbhf afqywl afvnaibfk ahbmqf aicfrdjfk ajemztar akjvnfy alimboy alixmh almxr alnsvsh altumyt aosxsc aplxmc appiqeb aptmktltz aqgrxybzj aqwbo arxyeqap auokjofq avbbu awfurl ... ]
cmd> merge
l = [aapdssaf abdgomey abjkxhs abniq abwkmpknf abzwmhwa acydelyfy adiybmu adltemlk adxuzomi aelhfgap aercjoitb aeuutwfl afgbhf afqywl afvnaibfk agbwobfz ageru agkldlqgb ahbmqf ahocaz aicfrdjfk aivrqeat ajemztar ajlxdwypy ajxkcjom akcmv akjvnfy akylew alcnytf ... ]
cmd> size
Queue size = 2000
l = [aapdssaf abdgomey abjkxhs abniq abwkmpknf abzwmhwa acydelyfy adiybmu adltemlk adxuzomi aelhfgap aercjoitb aeuutwfl afgbhf afqywl afvnaibfk agbwobfz ageru agkldlqgb ahbmqf ahocaz aicfrdjfk aivrqeat ajemztar ajlxdwypy ajxkcjom akcmv akjvnfy akylew alcnytf ... ]
cmd> shuffle
l = [pyauaocrs nkopuzrve jhracfaua phiyuy kpmdi vknxotac xqwnis vvaiskoq uzatka upbspjs tqdgp pstvn cksirn uunkt pdioxl abjkxhs trzgs xmmxy jbrsoq xxjdy pjwwdmzfo tetiokboe ftyxo vafhqlsm zgxqooin letmclonb nrutrme sqvss pultrdg bfvaacrai ... ]
cmd> mem_pool
Current mpool size: 2000
cmd> sort
l = [aapdssaf abdgomey abjkxhs abniq abwkmpknf abzwmhwa acydelyfy adiybmu adltemlk adxuzomi aelhfgap aercjoitb aeuutwfl afgbhf afqywl afvnaibfk agbwobfz ageru agkldlqgb ahbmqf ahocaz aicfrdjfk aivrqeat ajemztar ajlxdwypy ajxkcjom akcmv akjvnfy akylew alcnytf ... ]
```
### 用巨集改寫 `mpool`
為了能讓使用者可以自行定義 `mpool` 的結構體，參考 [第 4 週測驗 1 的 rb.h](https://hackmd.io/@sysprog/linux2023-quiz4#%E6%B8%AC%E9%A9%97-1) 的寫法來改寫 `mpool`。
原本的 `mpool` 的結構體是直接定義的，所以也就只能給 `node_t` 使用。
```c
typedef struct mem_node {
node_t node;
struct mem_node *next;
} mem_node_t;
```
利用巨集改寫後的 `mpool.h`，`type` 代表要儲存的結構體名稱，可以依照使用者的需求改變。
```c
#define mpool_proto(type, field) \
typedef struct mem_##type { \
type field; \
struct mem_##type *next; \
} mem_##type##_t; \
typedef struct arena { \
mem_##type##_t *first_mapped; \
mem_##type##_t *last_mapped; \
struct arena *next; \
} arena_t; \
typedef struct mpool { \
size_t arena_count; \
size_t field##_count; \
arena_t *first_arena; \
arena_t *last_arena; \
} mpool_t; \
/** \
* mpool_create - create and initialize a new memory pool \
*/ \
mpool_t *mpool_create(size_t size); \
/** \
* mpool_alloc - allocate a memory to the memory pool \
*/ \
void mpool_alloc(mpool_t *mp, size_t new_size); \
/** \
* mpool_size - return size of mpool \
*/ \
size_t mpool_size(mpool_t *mp); \
/** \
* mpool_free - free the mpool \
*/ \
void mpool_free(mpool_t *mp); \
/** \
* mpool_destory - destory the mpool \
*/ \
void mpool_destory(mpool_t *mp)
```
接著 `mpool` 的各個函式的實作由 `mpool_gen` 生成。
```c
#define mpool_gen(type, field)
```
接下來各個函式的修改都是修改對應的結構體名稱而已
#### mpool_create
```c
mpool_t *mpool_create(size_t size) \
{ \
...
new_mp->field##_count = size; \
...
mem_##type *n = malloc(sizeof(mem_##type) * size); \
if (!n) \
return NULL; \
\
mem_##type *cur = n; \
...
} \
```
#### mpool_alloc
```c
void mpool_alloc(mpool_t *mp, size_t new_size) \
{ \
...
size_t size = new_size - mp->field##_count; \
mp->field##_count = new_size; \
...
mem_##type *n = malloc(sizeof(mem_##type) * size); \
if (!n) \
return; \
\
mem_##type *cur = n; \
...
} \
```
#### mpool_size
```c
size_t mpool_size(mpool_t *mp) \
{ \
if (!mp) \
return 0; \
\
return mp->field##_count; \
} \
```
#### mpool_free
```c
void mpool_free(mpool_t *mp) \
{ \
...
mp->field##_count = 0; \
...
} \
```
#### qtest 的修改
在 `qtest` 呼叫 `mpool_proto` 來產生各個函式的 `prototype`，然後再用 `mpool_gen` 產生對應函式的實作。
```c
#include "mpool.h"
mpool_proto(node_t, node);
mpool_gen(node_t, node);
```
Sign in with Wallet
Connect another wallet