將 treesort 整合進 lab0-c

contributed by < willwillhi1 >

treesort.c

• 程式碼的理解在 willwillhi1 / quiz3 中

修改程式

node_t 結構體

參考作業一的 list_head 的實作，將原本的結構體中用來表示紅黑樹的地方抽離出來單獨使用。
原本的實作為以下，將 uintptr_t color, struct __node *left, *right 從 node_t 裡移出來。

typedef struct __node {
    uintptr_t color;
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t __attribute__((aligned(sizeof(long))));

使用一致的程式碼縮排方式，亦即 4 個空白 (而非 tab)。

jserv

已修正

抽離出來用來表示紅黑樹的結構體定義為 rb_node ：

struct rb_node {
    uintptr_t color;
    struct rb_node *right;
    struct rb_node *left;
} __attribute__((aligned(sizeof(long))));

而原本的 node_t 結構體會變成：

typedef struct __node {
    struct rb_node node;
    struct list_head *list;
} node_t;

其中裡面的 list_head 指標指向 element_t 結構體裡面的 list_head，element_t 用來表示佇列的資訊，詳細的教學可以參考 你所不知道的C 語言: linked list 和非連續記憶體。

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。

保留 cmap_iter_t 的風格，作為走訪節點的通用 iterator

jserv

使用 struct *rb_node 可以作為走訪節點的通用 iterator

• comparator 的部份，因為 element_t 的 value 的型別是字串，所以先改成以下作為替代，其中 _CMP_LESS, _CMP_GREATER, _CMP_EQUAL 分別代表 -1, 1, 0。

/* 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，顏色標成紅色)。

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 的方式來走訪所有節點並釋放記憶體。

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 層所有點。

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 開始一直往右找，反之最小則是往左。

/* 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。

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 來走訪整個佇列，同時建立紅黑樹的節點。

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 加入。

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;        
}

最後釋放記憶體

tree_free(map->head);
free(map);

qtest 修改

在 qtest 中新增 do_tree_sort 函式。

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 命令。

ADD_COMMAND(tree_sort, "Use red black tree to sort the queue", "");

TODO: 引入 option，讓 qtest 得以在執行時期切換不同的排序實作，有助於後續分析。

jserv

引入 option
首先在 q_test 中宣告全域變數 enable_rb_tree_sort

static int enable_rb_tree_sort = 0;

然後修改 do_sort 函式中的部份程式，用來判斷執行 sort 時要用什麼樣的方法排序

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 的參數

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 所提及的做一次排序就要重新建一次樹，也就是需要使用 malloc 配置額外的空間，相較之下原本實作的 merge sort 因為是 in-place，所以執行成本相對較低。

TODO: 引入 memory pool (課程測驗題已提過)，預先配置好記憶體，之後重用該空間，從而縮減動態記憶體配置的成本。

jserv

引入 memory pool

參考 rv32emu 的 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 中…。

可參考 rv32emu 的 mpool.c 中的 mpool_extend()，避免 free 掉原先已配置好的記憶體

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);
}

最後在釋放記憶體的時候不需要釋放紅黑樹節點的空間。

-   tree_free(map->head);
    free(map);

負責建立以及初始化節點的函式 list_make_node 做一些小修改，將紅黑樹節點的位址通過參數傳入使用。

-   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 的程式。

if (mp) {
    call_mem_pool_times = 0;
    mpool_destory(mp);
}

q_quit 函式同樣也要。

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 改為：

typedef struct mpool {
    size_t arena_count;
    size_t node_count;
    arena_t *first_arena;
    arena_t *last_arena;
} mpool_t;

其實 "arena" 會比 "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

jserv

了解！

arena 儲存每次新增的節點記憶體的起始 (first_mapped) 到最後 (last_mapped) 的位址，next 表示下一個 arena 的位址。

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 的位址。

#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 的部份為：

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 中。

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 大致相同，只是需要先判斷目前的空間是否夠用。

size_t new_size = q_size(head);
if (new_size <= mp->node_count)
    return;

如果不夠就宣告新的 arena 並且初始化。

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)。

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 結構體本身

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。

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。

#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 指標來取得下一個節點的位址。

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 函式改為對應的參數即可。

else if (enable_rb_tree_sort) {
    tree_sort(current->q, mp->first_arena->first_mapped);
}

因應 qtest 原本的 do_sort 函式規定在做排序時不能動態配置記憶體的需求。

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。

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 函式宣告區域變數來解決這個問題。

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 的寫法來改寫 mpool。
原本的 mpool 的結構體是直接定義的，所以也就只能給 node_t 使用。

typedef struct mem_node {
    node_t node;
    struct mem_node *next;
} mem_node_t;

利用巨集改寫後的 mpool.h，type 代表要儲存的結構體名稱，可以依照使用者的需求改變。

#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 生成。

#define mpool_gen(type, field) 

接下來各個函式的修改都是修改對應的結構體名稱而已

mpool_create

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

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

size_t mpool_size(mpool_t *mp)                                  \
{                                                               \
    if (!mp)                                                    \
        return 0;                                               \
                                                                \
    return mp->field##_count;                                   \
}                                                               \

mpool_free

void mpool_free(mpool_t *mp)                                    \
{                                                               \
    ...
    mp->field##_count = 0;                                      \
    ...
}                                                               \

qtest 的修改

在 qtest 呼叫 mpool_proto 來產生各個函式的 prototype，然後再用 mpool_gen 產生對應函式的實作。

#include "mpool.h"

mpool_proto(node_t, node);
mpool_gen(node_t, node);