Try   HackMD

2022q1 Homework1 (lab0)

contributed by < naihsin >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           61
Model name:                      Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
Stepping:                        4
CPU MHz:                         3099.851
CPU max MHz:                     3100.0000
CPU min MHz:                     500.0000
BogoMIPS:                        5399.73
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        512 KiB
L3 cache:                        3 MiB
NUMA node0 CPU(s):               0-3

作業要求

依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
queue.c 僅提供介面 (interface) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:

  • q_new: 建立新的「空」佇列;
  • q_free: 釋放佇列所佔用的記憶體;
  • q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
  • q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
  • q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
  • q_release_element: 釋放特定節點的記憶體空間;
  • q_size: 計算目前佇列的節點總量;
  • q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
  • q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
  • q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
  • q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
  • q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

開發紀錄

q_new

  • 先 malloc 一塊記憶體空間給 head
  • 若 malloc 失敗則 return NULL
  • 接著把 head 的兩個指標 next, prev 初始化，兩個指標皆指向自己
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);

    return head;
}

q_free

  • 判斷 queue 的 head(也就是 l )是否為空
  • 若 l 為空，則代表「沒有」佇列
  • 若 l 不為空，此時佇列有兩種狀態，分別是「空」佇列與「不是空」佇列(也就是佇列裡面有 element )
  • 使用 list_for_each_entry_safe 走訪所有包含 list_head 結構的 element entry
  • 使用 q_release_element 把每一個 element free 掉
  • 最後別忘了還要把 l free 掉
void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *el, *safe;
    list_for_each_entry_safe (el, safe, l, list) {
        q_release_element(el);
    }
    free(l);
}

q_insert_head

  • 判斷 head 是否為空(也就是判斷有沒有佇列)
  • 若沒有佇列則 return false
  • malloc element_t 大小給 ptr 指標
  • 判斷 malloc 是否有成功
  • 若 malloc 失敗則 return false
  • 使用 list_add 把 ptr 指向 list 成員的位址加入到 list head
  • 接著 malloc strlen(s) + 1 大小給 ptr->value ，包含空字元
  • 判斷 malloc 是否成功
  • 把 s 複製到新的 element 中
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *ptr = (element_t *) malloc(sizeof(element_t));
    if (!ptr)
        return false;

    list_add(&ptr->list, head);

    ptr->value = (char *) malloc(strlen(s) + 1);
    if (!ptr->value)
        return false;

    strncpy(ptr->value, s, strlen(s) + 1);

    return true;
}

q_insert_tail

  • 判斷 head 是否為空(也就是判斷有沒有佇列)
  • 若沒有佇列則 return false
  • malloc element_t 大小給 ptr 指標
  • 判斷 malloc 是否有成功
  • 若 malloc 失敗則 return false
  • 使用 list_add 把 ptr 指向 list 成員的位址加入到 list tail
  • 接著 malloc strlen(s) + 1 大小給 ptr->value ，包含空字元
  • 判斷 malloc 是否成功
  • 把 s 複製到新的 element 中
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *ptr = (element_t *) malloc(sizeof(element_t));
    if (!ptr) {
        return false;
    }

    list_add_tail(&ptr->list, head);

    ptr->value = (char *) malloc(strlen(s) + 1);
    if (!ptr->value)
        return false;

    strncpy(ptr->value, s, strlen(s) + 1);

    return true;
}

q_remove_head

  • 判斷 head 是否為空(也就是判斷有沒有佇列)
  • 若沒有佇列則 return NULL
  • 判斷 list 是否為空
  • 若為空則 return NULL
  • 用 list_entry 找到從 head 數來的第一個 element entry 的位址
  • 判斷 sp 字串是否為空
  • 若為空，把 element 的字串複製到 sp 中
  • 記得要把 sp padding 一個空字元
  • 用 list_del_init 把剛剛找到的 element 的 list 成員 從 list 中移除
  • 把找到的 element return 回去
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ptr = list_entry(head->next, element_t, list);

    if (sp) {
        strncpy(sp, ptr->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del_init(&ptr->list);

    return ptr;
}

q_remove_tail

  • 判斷 head 是否為空(也就是判斷有沒有佇列)
  • 若沒有佇列則 return NULL
  • 判斷 list 是否為空
  • 若為空則 return NULL
  • 用 list_entry 找到從 tail 數來的第一個 element entry 的位址
  • 判斷 sp 字串是否為空
  • 若為空，把 element 的字串複製到 sp 中
  • 記得要把 sp padding 一個空字元
  • 用 list_del_init 把剛剛找到的 element 的 list 成員 從 list 中移除
  • 把找到的 element return 回去
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ptr = list_entry(head->prev, element_t, list);

    if (sp) {
        strncpy(sp, ptr->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del_init(&ptr->list);

    return ptr;
}

q_release_element

  • 在 q_insert_head, q_insert_tail 中，分別 malloc 整個 element 結構與 element->value ，使用到兩次 malloc ，在釋放 element 也必須把這兩個結構 free 掉
void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_size

  • 判斷 head 是否為空(也就是判斷有沒有佇列)
  • 若沒有佇列則 return 0
  • 用 list_for_each 走訪 list 所有的節點
  • list_for_each 是一個 macro ，展開為
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)
  • 設置 len 變數，算出總共有幾個節點
  • return len 回去
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

  • 判斷 head 是否為空(也就是判斷有沒有佇列)
  • 若沒有佇列則 return false
  • 判斷 queue 是否為空
  • 若 queue 為空則 return false
  • 接著設置快慢指針，找到中間的節點，快指針一次走兩步，慢指針一次走一步，當快指針到達終點時，慢指針才走完一半，所以可以利用這種特性來找到中間的節點
  • 使用 list_del_init 把慢指針從 list 中移除
  • 用 list_entry 找到慢指針被存放到 element 結構的位址
  • 用 q_release_element 把找到的 element release
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || !q_size(head))
        return false;

    struct list_head *slow = head->next, *fast = head->next;
    while (fast->next != head->next && fast->next->next != head->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    list_del_init(slow);
    q_release_element(list_entry(slow, element_t, list));

    return true;
}

q_delete_dup

  • 判斷 queue 是否為空
  • 若為空則 return false
  • 設置 cur 指針來走訪每個節點
  • 當 cur->next == head 則代表已經走訪完一圈
  • 設置 first, second 來紀錄相鄰兩個節點所處的 element 結構的位址
  • 當 first->value 跟 second->value 的值相等，則把 second 移除，且把 cur->next 從 list 中移除
  • 當 first->value 跟 second->value 的值不相等，把 cur 設置成 cur->next ，繼續下一對相鄰節點比較
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!q_size(head))
        return false;

    struct list_head *cur = head->next;
    while (cur->next != head) {
        element_t *first = list_entry(cur, element_t, list);
        element_t *second = list_entry(cur->next, element_t, list);
        if (!strcmp(first->value, second->value)) {
            list_del_init(cur->next);
            q_release_element(second);
        } else {
            cur = cur->next;
        }
    }
    return true;
}

q_swap

  • 設置 left, right 紀錄相鄰的兩個節點
  • 當 left == head || right == head 則代表已經走訪完一圈的所有節點
  • 使用 list_move 把 left 節點從 list 中移除，且再把 left 加入到 right 在 list 中的下一個位址，如此一來就可以達成 swap 兩個節點的操作
  • 更新 left = left->next, right = left->next，繼續下一輪的 swap 操作
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    struct list_head *left = head->next, *right = left->next;
    while (left != head && right != head) {
        list_move(left, right);
        left = left->next;
        right = left->next;
    }
}

q_reverse

  • 判斷 head 是否為空(也就是判斷有沒有佇列)
  • 若沒有佇列則 return
  • 使用 list_for_each_safe 走訪 list 中的所有節點
  • 用 list_move 刪除節點
void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *li, *safe;
    list_for_each_safe (li, safe, head) {
        list_move(li, head);
    }
}

若為 singular，不需要繼續處理。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

q_sort

  • 這邊我選擇用 divide and conquer 的方式來實做程式
  • 判斷 head 是否為空(也就是判斷有沒有佇列)
  • 若沒有佇列則 return
  • 判斷 list 是否為空
  • 若為空則 return
  • 先把 head->prev->next 設成 NULL ，讓最後一個節點的 next 指向 NULL，方便設置後續 q_merge 的結束條件
  • 呼叫 q_merge 來切割節點直到剩下一個節點
  • 接著 q_merge 會回傳已經排序好的節點
  • 此時的 queue 並不是完整的 doubly linked-list
  • while 是找到回傳 list 的最後一個節點
  • 復原 head 與 最後一個節點的關係
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    head->prev->next = NULL;
    struct list_head *ptr = q_merge(head->next);
    head->next = ptr;
    ptr->prev = head;

    while (ptr->next) {
        ptr = ptr->next;
    }
    ptr->next = head;
    head->prev = ptr;
}

q_merge

  • 判斷 ptr->next 是否為空
  • 若為空則代表已經切割至剩下一個節點，return ptr
  • 使用快慢指針來找到中間節點，詳細說明可參考 q_delete_mid
  • 從中間節點切割左右兩邊的 list
  • 使用 recursive ，再次把左邊的 list 切割，直到切割到剩下一個節點
  • 使用 recursive ，再次把右邊的 list 切割，直到切割到剩下一個節點
  • 使用 q_mergefinal 把左邊與右邊的 list 排序合併
struct list_head *q_merge(struct list_head *ptr)
{
    if (!ptr->next)
        return ptr;

    struct list_head *slow = ptr, *fast = ptr;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct list_head *left, *right;
    fast = slow->next;
    slow->next = NULL;
    left = q_merge(ptr);
    right = q_merge(fast);
    return q_mergefinal(left, right);
}

q_mergefinal

  • 這邊使用到 pointer to pointer 目的是為了減少記憶體的分配
  • 設置 head 指標紀錄排序好的第一個節點， head 先指向 left (也就是左邊節點)
  • 設置指標的指標 **ptr ，讓 ptr 紀錄 head 的記憶體位址，以便根據要修改當前節點的記憶體位址來變更 ptr
  • 設置 prev 指標紀錄前一個節點， 以便讓下一個節點的 prev 指回前一個節點
  • 設置指標的指標 **node ，讓 node 紀錄即將要加入 list 的節點的記憶體位址，一開始設成 NULL
  • 使用 for 迴圈直到 left 跟 right 皆不為 NULL
  • 使用 list_entry 找到 left 跟 right 所在的 element 結構的記憶體位址
  • 比較 el->value (左節點)跟 el2->value (右節點)的 element value
  • 若 el->value (左節點)比較小，則把 node 設成 &left 也就是 left 節點所處的記憶體位址
  • 反之，則把 node 設成 &right 也就是 right 節點所處的記憶體位址
  • 接著把 *node->prev = prev 也就是把 left->prev = prev 或 right->prev = prev ，把 node 與前一個節點的關係接上
  • 更新 prev ，把 prev 設成當前節點 *node
  • 更新 *ptr ，把當前要修改的記憶體位址的節點設成 *node
  • 前幾個步驟，已經順利把節點接上，接著要更新 ptr ，把紀錄當前節點的記憶體位址移到下一個節點
  • 更新 *node ，把當前指向 left 或 right 的節點更新為 left->next 或 right->next ， 等價於 left = left->next
struct list_head *q_mergefinal(struct list_head *left, struct list_head *right)
{
    struct list_head *head = left, *prev = NULL, **ptr = &head, **node;

    for (node = NULL; left && right; *node = (*node)->next) {
        element_t *el = list_entry(left, element_t, list);
        element_t *el2 = list_entry(right, element_t, list);
        node = (strcmp(el->value, el2->value) < 0) ? &left : &right;
        (*node)->prev = prev;
        prev = *node;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = left ? left : right;
    (*ptr)->prev = prev;
    return head;
}
Last changed by 
 
Hsin
0
442

Read more

D-link DIR-600 cmd injection vulnerability

Overview Vulnarable product: D-Link DIR-600 Manufacturer&apos;s website information: https://www.dlink.com/ Firmware download address: https://www.dlinktw.com.tw/techsupport/ProductInfo.aspx?m=DIR-600 Affected version Hardware version B5 Firmware version 2.18 Figure 1 shows the latest firmware of the router

Jun 10, 2023
D-link DIR-600 Stack overflow vulnerability

Overview Vulnarable product: D-Link DIR-600 Manufacturer&apos;s website information: https://www.dlink.com/ Firmware download address: https://www.dlinktw.com.tw/techsupport/ProductInfo.aspx?m=DIR-600 Affected version Hardware version: B5 Firmware version: 2.18 Figure 1 shows the latest firmware of the router

Jun 10, 2023
Proposal

Jan 18, 2020
Read more from Hsin
Published on HackMD