# 2020q1 Homework3 (quiz3)
contributed by < `Yu-Wei-Chang` >

> [2020q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz3?fbclid=IwAR39Qogo0gu5tBEayx31OePN8BNVoNnrAmD1g0RBn78ndrMo1cUoPUbqoV0)

### 1. 完成 XOR linked list 的排序程式，採用遞增順序:

#include <stdint.h>

typedef struct __list list;
struct __list {
    int data;
    struct __list *addr;
};

#define XOR(a, b) ((list *) ((uintptr_t) (a) ^ (uintptr_t) (b)))

list *sort(list *start)
{
    if (!start || !start->addr)
        return start;

    list *left = start, *right = start->addr;
    left->addr = NULL;
    right->addr = XOR(right->addr, left);

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right;) {
        if (!right || (left && left->data < right->data)) {
            list *next = left->addr;
            if (next)
                next->addr = XOR(left, next->addr);

            if (!merge) {
                start = merge = left;
                merge->addr = NULL;
            } else {
                merge->addr = XOR(merge->addr, left); /* LL1 */
                left->addr = merge; /* LL2 */
                merge = left;
            }
            left = next;
        } else {
            list *next = right->addr;
            if (next)
                next->addr = XOR(right, next->addr);

            if (!merge) {
                start = merge = right;
                merge->addr = NULL;
            } else {
                merge->addr = XOR(merge->addr, right); /* RR1 */
                right->addr = merge; /* RR2 */
                merge = right;
            }
            right = next;
        }
    }

    return start;
}

同 [Quiz1](https://hackmd.io/@sysprog/linux2020-quiz1)，這邊也採用合併排序法。
* **Line #13~#14** : Divide 直到剩一個節點或是沒有節點就直接返回。
* **Line #16~#18** : Divide 的方式是將傳入的鍊結串列的第一個節點拆開當成左半部(`list *left`，然後把節點的 address 清除掉)，剩下的部份當成右半部(`list *right`，然後消除掉頭節點 address 中的 left affress)。
* **Line #20~#21** : 兩部份的鍊結串列分別遞迴呼叫 sort() 繼續 Divide & Merge。
* **Line #24~#37** : Merge 左半部的節點 (左半部節點的資料數值小於右半部節點的資料，或是右半部節點都 Merge 完了)。
* **Line #25~#27** : 由於左半部鍊結串列的頭一個節點即將要 Merge 到終要返回的串列中，所以必須將該節點的位址從剩下的鍊結串列中消除掉 (left->addr->addr = XOR(left, left->addr->addr);)
* **Line #29~#31** : 第一個 Merge 的節點，addr 給 NULL 即可。
* **Line #32~#36** : 非第一個 Merge 的節點，因此要將自己的位址加入到 `merge->addr` 之中 (==LL1 : merge->addr = XOR(merge->addr, left);==)，然後因為是雙向的鍊結串列，所以要將前一個節點的位址加到自己的 addr。 (~~==LL2 : left->addr = XOR(left->addr, merge);==~~)
* **Line #38~#52** : Merge 右半部的節點。
* **Line #39~#41** : 由於右半部鍊結串列的頭一個節點即將要 Merge 到終要返回的串列中，所以必須將該節點的位址從剩下的鍊結串列中消除掉 (right->addr->addr = XOR(right, right->addr->addr);)
* **Line #43~#45** : 第一個 Merge 的節點，addr 給 NULL 即可。
* **Line #46~#49** : 非第一個 Merge 的節點，因此要將自己的位址加入到 `merge->addr` 之中 (==RR1 : merge->addr = XOR(merge->addr, right);==)，然後因為是雙向的鍊結串列，所以要將前一個節點的位址加到自己的 addr。 (~~==RR2 : right->addr = XOR(right->addr, merge);==~~)
* ==更正錯誤==：當 Merge 新節點時確實要更新節點的 `addr`，直接給值為前一個節點的位址就好 (也就是 `merge`)，因為新加入的節點目前後面沒有接其他節點。 `right->addr = XOR(right->addr, merge);` 是錯誤的，因為 `right->addr` 當中可能帶有其他節點的位址。

#### 延伸問題
* 解釋上述 XOR linked list 排序實作的原理，並指出其中可改進之處;
* 採用 [Merge Sort](https://en.wikipedia.org/wiki/Merge_sort) 來排序，其主要原理是將整個串列先拆分至剩一個節點，然後再一個一個合併，並且在合併的同時做排序。
* 可以看出上面程式碼是將一個串列由頭開始將**一個**節點拆分出來，然後對其和剩下的 **N - 1** 個節點的串列做遞迴處理，直到所有串列都被拆分成一個節點，再進行合併的動作。
在資料量過大的時候需要大量呼叫遞迴函式，會造成行程的 ==stack overflow==，改進處如同第一次作業的方法 [`lab0`](https://hackmd.io/GC88E_DvTs230mBhIICcBw?view#%E7%B5%90%E6%9E%9C%E9%A9%97%E8%AD%89%E6%AD%BB%E5%9C%A8%E7%AC%AC-15-%E5%92%8C-16-%E9%A0%85%E6%B8%AC%E8%A9%A6-%E5%8F%AA%E8%A6%81%E8%B3%87%E6%96%99%E5%8A%A0%E5%88%B0-8000-%E7%AD%86%E5%B7%A6%E5%8F%B3-sort-%E5%B0%B1%E6%9C%83%E7%99%BC%E7%94%9F-segmentation-fault)，將串列從中間切開分別去遞迴，如此可以減少遞迴次數。
* 除了 ==stack overflow== 的問題之外，原本拆分方式的排序耗時也較長，當資料數量越大時差異越明顯。

* 嘗試找出最佳化策略的 `Optimized S`
* 設定 S 的範圍 0~100，分別對長度為 1000 的 linked list 做排序，最後紀錄其各別的排序耗時，從耗時中找出 Optimized S。
* 在原本的排序函式中判斷輸入的串列長度，若長度 $<=$ S 的話就直接做 in-place 排序。

      list *sort(list *start)
    {
        if (!start || !start->addr)
            return start;
    
        /* New: Divide XOR list into two equivalent length list */
        list *l_prev = NULL;
        list *r_prev = NULL;
        list *left = start;
        list *right = XOR(r_prev, start->addr);
        int cnt = 1;
        r_prev = start;
    
        while (right && XOR(r_prev, right->addr)) {
          list *tmp;
    
          /* Move forward one step */
          tmp = left;
          left = XOR(l_prev, left->addr);
          l_prev = tmp;
    
          /* Move forward two stpes */
          tmp = right;
          right = XOR(r_prev, right->addr);
          r_prev = tmp;
          tmp = right;
          right = XOR(r_prev, right->addr);
          r_prev = tmp;
    
          /* Counting data numbers of sub linked list */
          cnt++;
        }
    
        /* We could get length of sub linked list after divide. (cnt * 2)
         * Bubble sorting it if its length less or equal than optimaied S. */
        if ((cnt * 2) <= opt_s) {
          return bubble_sort(start, (cnt * 2));
        }
    
        /* Assign right as right part of list (Next node of current left) */
        right = XOR(l_prev, left->addr);
        /* Cut from left part off */
        right->addr = XOR(left, right->addr);
        /* Cut from riht part off */
        left->addr = XOR(right, left->addr);
    
        left = sort(start);
        right = sort(right);
		
		...

* 目前選用氣泡排序法來當作 in-place 的排序法。

  list *bubble_sort(list *start, int cnt) {
  for (int i = 0; i < (cnt - 1); i++) {
    list *curr = start;
    list *prev = NULL;

    while (curr && XOR(prev, curr->addr)) {
      list *next = XOR(prev, curr->addr);

      /* Swap data */
      if (next->data < curr->data) {
        int tmp = curr->data;
        curr->data = next->data;
        next->data = tmp;
      }
      prev = curr;
      curr = next;
    }
  }
  return start;
  }

* 實驗結果 :
* 結論推斷
* 當 S == 0 時就是做原本的合併排序，排序耗時約 250 us。
* S 介於 1 ~ 15 時是直接做 in-place 的泡沫排序，排序耗時比原本的合併排序少一些。
* S 超過 16 後排序時間都超過原始的合併排序。
* ==推斷 Optimized S 大約在 1 ~ 15 之間。==

### 2. singly-linked list，可透過以下 pointer to pointer 改寫 insert 函式，功能等價但更簡潔

#include <stddef.h>
struct node {
    int data;
    struct node *next;
} *head;

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && (*list)->data < newt->data /* AA */)
        list = &(*list)->next; /* BB */
    newt->next = *link;
    *link = newt;
}

* **Line #10~#11** : 主要目的是遍歷整個鍊結串列找出資料數值比新節點還大的節點，以利後續的插入動作。
* AA : (*list)->data < newt->data
* BB : list = &(*list)->next;
* 原本的實作方式宣告了 `struct node *prev` 以及使用 `if(prev == NULL)` 條件判斷插入的節點位於開啟或中間，開頭的話就必須做 `head = newt`；而中間的話就做 `node->next = newt`。而 pointer to pointer 的實作把 head 和 node->next 看作相同的角色，使用 struct node ** 來代表它們，如此一來就不需要使用 prev 變數還條件判斷式。

###### tags: `Linux核心課程筆記 - 隨堂測驗`
###### tags: `Linux核心課程筆記 - Homework`