# 2024q1 Homework2 (quiz1+2)
contributed by < [`wilson20010327`](https://github.com/wilson20010327) >
[repository](https://github.com/wilson20010327/M02-quiz1-2)
## 實驗環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  32
  On-line CPU(s) list:   0-31
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i9-14900HX
    CPU family:          6
    Model:               183
    Thread(s) per core:  2
    Core(s) per socket:  16
    Socket(s):           1
    Stepping:            1
    BogoMIPS:            4838.39
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss
                          ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_good nopl xtopology tsc_reliable nonstop_tsc cpuid
                          pni pclmulqdq vmx ssse3 fma cx16 sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx
                          f16c rdrand hypervisor lahf_lm abm 3dnowprefetch ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow vnmi
                          ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clw
                         b sha_ni xsaveopt xsavec xgetbv1 xsaves avx_vnni umip waitpkg gfni vaes vpclmulqdq rdpid movdiri mov
                         dir64b fsrm serialize flush_l1d arch_capabilities

## 使用快速排列排序陣列
為了熟悉快速排列的演算法，我先完成了對陣列進行排列。詳細程式碼於 `q-sort-array.c`
### Swap
在對陣列排序中其中一個重要的操作為 `swap` 使用 xor 不用使用額外記憶體，但使用時，演算法中會遇到 `swap` 同一個變數，在此狀況下會造成錯誤讓數值變為零，因此在交換時需要先做檢驗

void swap(int *a, int *b)
{
+    if (*a == *b)
+        return;
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

## 使用 Linux 核心風格的 List API 改寫 quiz1
詳細程式碼於 `quiz1_linux_list.c`
### 節點宣告
首先對 node_t 的宣告做改成 element_t，有了 `struct list_head list` 後， 數列的串接會變得方便，且可以使用 `Linux list API`。

-typedef struct __node {
-    struct __node *left, *right;
-    struct __node *next;
-    long value;
-} node_t;
+typedef struct {
+    int value;
+    struct list_head list;
+} element_t;

### 節點生成
在原先的程式碼中，須將原本串列的頭傳入函式，生成新的節點，將新的節點皆在原先的頭前面，再回傳新的節點位置作為串列的頭。而為了符合 `linux list` 風格，我將此函式改變為傳入指向串列的指標，並將新生成的節點加入串列的前面。

-node_t *list_construct(node_t *list, int n)
+void list_construct(struct list_head *head, int n)
{
-    node_t *node = malloc(sizeof(node_t));
+    element_t *node = malloc(sizeof(element_t));
     node->value = n;
-    node->next = list;
+    list_add(&node->list, head);
-    return node;
}

### 確認節點順序
用來檢驗串列是否照著數值大小由小到大做排列。原先作法需要用多餘的記憶體去暫存前一個節點的數值，使用list_for_each_entry_safe 取代使用 while 逐一走訪節點。

+static bool list_is_ordered(struct list_head *head)
-static bool list_is_ordered(node_t *list)
{
+    element_t *cur, *safe;
-    bool first = true;
-    int value;
+    list_for_each_entry_safe (cur, safe, head, list) {
+        if (&safe->list == head) {
+            break;
+        } else {
+            if (cur->value > safe->value)
+                return false;
+        }
+    }
-    while (list) {
-        if (first) {
-            value = list->value;
-            first = false;
-        } else {
-            if (list->value < value)
-                return false;
-            value = list->value;
-        }
-        list = list->next;
-    }
    return true;
}