# 2016q3 Homework3 (mergesort-concurrent)
contributed by <`hugikun999`>

## mergesort-concurrent

### 流程圖

digraph{
輸入thread_data->pthread初始化->task放入queue->task_run
task_run->task_run
task_run->pthread_exit
task_run->cut_func;
cut_func->cut_func;
cut_func->merge_sort;
merge_sort->merge_list;
merge_sort->merge;
merge_list->merge;
merge->list_print;

}

### file
(1) list.c

node_t *node_new(val_t val, node_t *next)

新增一個node把資料放進去並且使該node指向next。

llist_t list_new()

新增一個list,將head設為NULL、size設為0。

list_add(llist_t *list, val_t val)

將所給的list新增一個node其data是val，且此node會被加在list的最前面。

list_nth(llist_t *list, uint32_t idx)

尋找第idx個node，若idx超過size回傳NULL。

list_print(llist_t *list)

印出list中所有node的data。

(2)threadpool.c

task_free(task_t *the_task)

將要傳入的工作釋放，包括arg和本身。

tqueue_init(tqueue_t *the_queue)

將目標工作佇列初始化，head、tail、mutex、cond、size都設為NULL。

*tqueue_pop(tqueue_t *the_queue)

先將lock鎖起來，檢查the_queue的tail有沒有東西，如果有就會將tail指向last。接下來檢查新的tail，如果有東西就將目前tail的next設為NULL;沒有就將the_queue的head設為NULL。size最後再減一，將鎖起來的lock解鎖，回傳ret。

tqueue_size(tqueue_t *the_queue)

取得the_queue中的工作數。

tqueue_push(tqueue_t *the_queue, task_t *task)

先將lock鎖起來，將task的last設為NULL，task的next接到the_queue。先檢查the_queue的head是否是空的，如果不是就將the_queue的last指向task，再將the_queue的head指向task。如果原本the_queue的size是0，則將the_queue的tail指向task順便將size+1。最後在解鎖。

tqueue_free(tqueue *the_queue)

一個一個將the_queue釋放掉，再將mutex摧毀。

tpool_init(tpool_t *the_pool, uint32_t tcount, void *(*func)(void *))

分配給threads、queue空間，將the_pool的count設為tcount且初始化queue，宣告一個pthread的屬性並初始化設定為JOINABLE。開始呼叫新的process並且新的thread開始執行func。最後將attr給摧毀。

tpool_free(tpool_t *the_pool)

用pthread_join()等待每個pthread終止，確定終止之後再將the_pool的threads給釋放，最後將queue也釋放。

### 更改
(1)
在```threadpool.c```中把已經釋放memory的the_pool這個指標設為NULL，以必免再次使用造成錯誤。在```main.c```中的最後也加了將pool設為NULL。

(2)
將```threadpool.c```中tpool_init()裡面有關的```pthread_create()```給碼掉。剛開始_task的func和arg根本就還沒有放東西，所以就算呼叫了```pthread_create()```進到```*task_run()```也會只會一直在while迴圈循環。另外在```threadpool.c```寫一個```threads_run()```的函式將碼掉的地方放進去。如此便可以等到_task放完東西再呼叫，不會浪費資源。
>> 可用 `diff -up` 的輸出來表示程式碼變更，而非只是貼出修改後、包含過時註解的程式碼 [name=jserv]
>> 了解[name=俊逸]

    the_pool->threads = (pthread_t *) malloc(sizeof(pthread_t) * tcount);
    the_pool->count = tcount;
    the_pool->queue = (tqueue_t *) malloc(sizeof(tqueue_t));
    tqueue_init(the_pool->queue);
/*    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
    for (uint32_t i = 0; i < tcount; ++i)
        pthread_create(&(the_pool->threads[i]), &attr, func, NULL);
    pthread_attr_destroy(&attr);*/
    return 0;

(3)
將`word.txt`亂數後的檔案先補齊16位，利用`mmap()`得出開頭指標在用`list_add()`建入list中，最後將lastname的字元做比大小(字元比大小會自動換為ASCII code)。

The whole program cost: 0.051664 sec

字元比大小

    while (a->size && b->size) {
        int count = 0, diff = 0;
        char *asize = a->head->data;
        char *bsize = b->head->data;
        llist_t *small;

        while((asize[count] != '\0') || (bsize[count] != '\0')) {
            diff = asize[count] - bsize[count];
            if(diff < 0) {
                small = a;
                break;
            } else if(diff > 0) {
                small = b;
                break;
            } else
                count++;
        }

### Problem
(1)

>> 取決於輸入 data set 的內容，目前實做只在意輸入的位址，至於每筆要取多少長度，是 mergesort 裡頭比較程式碼指定 [name=jserv]
>> 不太懂意思，所以我是要從mergrsort裡面更改嗎？[name=俊逸]

我有嘗試將`phonebook_concurrent`的size改成32且```file.c```的```MAX_BUFF_SIZE```也改為32，但是建立出來的數目是一樣多的，並沒有少一半。