Try   HackMD

2023q1 Homework1 (lab0)

contributed by < chiacyu >

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

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):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           60
Model name:                      Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
Stepping:                        3
CPU MHz:                         1700.000
CPU max MHz:                     3600.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5187.53
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

開發日誌

做作業前可以先研讀 你所不知道的 C 語言: linked list 和非連續記憶體對於實作過程大有幫助。

q_new

這邊需要注意的部份在根據 malloc 的說明:

On error, these functions return NULL.

若是失敗時會回傳 NULL 因此就算失敗也必須要使用 free 來釋放記憶體。

struct list_head *q_new()
{
    struct list_head *q_head = malloc(sizeof(struct list_head));
    if (!q_head) {
        free(q_head);
        return NULL;
    }
    INIT_LIST_HEAD(q_head);
    return q_head;
}

q_free()

釋放記憶體的部份則是透過 list_for_entry_safe 依序走訪過每一個 element 來釋放每個節點所佔用的記憶體。

void q_free(struct list_head *l)
{
    if (!l) {
        return;
    }
    if (list_empty(l)) {
        free(l);
    }
    element_t *entry, *safe;

    list_for_each_entry_safe (entry, safe, l, list) {
        if (entry->value) {
            free(entry->value);
        }
        free(entry);
    }
    free(l);
    return;
}

q_insert_head()

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *q = malloc(sizeof(element_t));
    if (!q) {
        free(q);
        return false;
    }
    q->value = strdup(s);
    list_add(&q->list, head);
    return true;
}

q_insert_tail()

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *q = malloc(sizeof(element_t));
    if (!q) {
        free(q);
        return false;
    }
    q->value = strdup(s);
    list_add_tail(&q->list, head);
    return true;
}

q_remove_head()

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)) {
        return NULL;
    }
    element_t *q_head = list_first_entry(head, element_t, list);
    list_del(&q_head->list);
    if (!q_head) {
        free(q_head);    
        return NULL;
    }
    strncpy(sp, q_head->value, bufsize);
    return q_head;
}

q_remove_tail()

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    element_t *q_tail;
    q_tail = list_last_entry(head, element_t, list);
    list_del(&q_tail->list);
    if (!q_tail){
        free(q_tail);
        return NULL;
    }
    strncpy(sp, q_tail->value, bufsize);
    return q_tail;
}

思考如何縮減程式碼。

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_size()

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

這邊用的方式是先計算出 queue 的長度，再取下高斯的方式來找出 mid 的位置

改進漢語描述，並描述對應的演算法。

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

bool q_delete_mid(struct list_head *head)
{
    if (!head){
        return false;
    }

    int q_num = q_size(head);
    q_num = q_num/2;
    struct list_head *mid = head;
    while (q_num--) {
        mid = mid->next;
    }
    element_t *mid_node = list_entry(mid, element_t, list);
    list_del(&mid_node->list);
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    return true;
}

q_delete_dup()

delete 的方式用兩個指標 先去若是遇到重複的字串 將第二個指標持續往 next 前進直到不同 再第一個指標往 next 走得過程刪除重複的節點

改進漢語表達。

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

bool q_delete_dup(struct list_head *head)
{
    if (head == NULL) {
        return false;
    }

    struct list_head *curr = head->next, *nextt;
    bool dup_flag = false;
    while (curr && curr->next) {
        if (curr == head || curr->next == head)
            break;
        nextt = curr->next;
        element_t *node_f = list_entry(curr, element_t, list);
        element_t *node_s = list_entry(nextt, element_t, list);
        while (strcmp(node_f->value, node_s->value) == 0) {
            nextt = nextt->next;
            if (nextt == head) {
                break;
            }
            node_s = list_entry(nextt, element_t, list);
            dup_flag = true;
        }
        if (dup_flag) {
            while (curr != nextt) {
                struct list_head *delete_node = curr;
                curr = curr->next;
                list_del(delete_node);
                free(list_entry(delete_node, element_t, list));
            }
            dup_flag = false;
        }
        curr = curr->next;
    }
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    return true;
}

q_swap()

swap 的實作方式則是用兩個指標分別指到，欲插入頭部的位置與欲移動節點之位置。由於後一個節點的 next 會指向 head 因此可以作為判斷之條件來檢視是否走遍所有節點。

void q_swap(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node = head->next;

    while (node && node->next) {
        struct list_head *next_n;
        if (node == head || node->next == head)
            break;
        next_n = node->next;
        list_del(node);
        list_add(node, next_n);
        node = node->next;
    }
    return;
    // https://leetcode.com/problems/swap-nodes-in-pairs/
}

q_reverse()

void q_reverse(struct list_head *head)
{
    if (list_empty(head)) {
        return;
    }
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        list_move(node, head);
    }
    return;
}

q_reverseK()

目前的實作方式是用兩個指標，第一個指標放在 前頭 ，第二個指標指向欲移動的點。但目前這種方式當遇到 queue 長度能被 k 整除時會有問題，需要再改進。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (list_empty(head) || k < 2) {
        return;
    }
    int reverse_count = q_size(head)/ k;
    int interval = k - 1;
    struct list_head *start = head->next, *end = head->next;
    while (reverse_count--) {
        while (interval--) {
            end = end->next;
        }
        while (end != start) {
            struct list_head *move_node = end;
            end = end->prev;
            list_del(move_node);
            list_add_tail(move_node, start);
        }
        start = start->next;
        end = start;
        if(start == head || start->next== head) break;
    }
    return;
}

q_sort()

目前是依照 你所不知道的 C 語言: linked list 和非連續記憶體 內文提供的遞迴版本去實作。 唯一的差別是在與這邊的實作是取 first entry 作為 pivot ，範例的版本則是取最後一個 entry 作為 pivot 。 原本在宣告 large_head 跟 small_head 的時候是使用 malloc 但發現在執行時期會發生 FATAL ERROR: Calls to malloc disallowed 後來才改為不需要 malloc 的版本。

void q_sort(struct list_head *head) {
    
    if (list_empty(head) || list_is_singular(head)){
        return;
    }

    struct list_head large_head;
    struct list_head small_head;
    element_t *pivot_node;
    element_t *current_node;
    element_t *safe;

    INIT_LIST_HEAD(&large_head);
    INIT_LIST_HEAD(&small_head);

    pivot_node = list_last_entry(head, element_t, list);
    list_del(&pivot_node->list);
    
    list_for_each_entry_safe(current_node, safe, head, list){
        if(strcmp(current_node->value, pivot_node->value) < 0){
            list_move_tail(&current_node->list, &small_head);
        }
        else if(strcmp(current_node->value, pivot_node->value) >= 0){
            list_move_tail(&current_node->list, &large_head);
        }
    }

    q_sort(&large_head);
    q_sort(&small_head);

    list_add(&pivot_node->list, head);
    list_splice(&small_head, head);
    list_splice_tail(&large_head, head);
}

q_descend

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head)) {
        return 0;
    }
    struct list_head *curr = head->prev;
    struct list_head *safe = head->prev;
    char *max_value = '\0';
    int count_size = 0;

    while (curr != head) {
        curr = safe;
        safe = curr->prev;
        count_size+=1;
        element_t *entry = list_entry(curr, element_t, list);
        if (strcmp(entry->value, max_value) > 0) {
            max_value = strdup(entry->value);
        } else {
            list_del(curr);
            free(entry);
            count_size+=1;
        }
    }
    return count_size;
}

q_merge()

這邊的作法是透過，list_for_each_entry_safe 的方式將每一個節點走遍。 假設總共有三個 queue [A,B,C] [D,E,F] [G,H,I], 先準備一個 sort_head 並將所有節點移動至此成 [A,B,C,D,E,F,G,H,I] 此時三個佇列變成 [] [] []，在將 sort_head 排序後串回第一個 queue, 變成 [A,B,C,D,E,F,G,H,I] [] [] 。

int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (list_empty(head)) {
        return 0;
    }
    int count = 0;
    struct list_head sort_head;
    INIT_LIST_HEAD(&sort_head);

    queue_contex_t *itr;
    queue_contex_t *itr_safe;
    list_for_each_entry_safe (itr, itr_safe, head, chain) {
        count += itr->size;
        list_splice_init(itr->q, &sort_head);
    }

    q_sort(&sort_head);
    list_splice_init(&sort_head, list_first_entry(head, queue_contex_t, chain)->q);
    printf("The count is %d\n", count);
    return count;
}

網頁伺服器

Shuffle 實作

Last changed by 
 
chiacyu
1
430

Read more

XDP firewall

contributed by &lt; chiacyu &gt;

Dec 2, 2023
2023q1 Homework7 (ktcp)

contributed by &lt; chiacyu &gt;

Nov 17, 2023
# linux2023 : chiacyu

β

Aug 18, 2023
2023q1 Homework6 (quiz5)

contributed by &lt; chiacyu &gt; 測驗 1 在 pool_init 的過程中，需要透過一個 meta data 的資料結構來記錄這個 block 裡面的資訊，因此若是 size 小於 header_size 就會返回失敗。 bool pool_init(void *addr, int size) { if (!addr) /* not a valid memory address */ return false;

Apr 17, 2023
Read more from chiacyu
Published on HackMD