Try   HackMD

2022q1 Homework1 (lab0)

contributed by < AxotZero >

> My UBUNTU haven't install Chinese Input Tool. - Because of personal reasons, I was late to join the course. I started watching youtube videos on 02/19 and finish the basic implementation of queue.c on 02/21. Still have a long journey to completely finish HW1.

Show me the code rather than murmur!

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

實驗環境

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

$ lscpu
架構：                           x86_64
CPU 作業模式：                   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
每核心執行緒數：                 2
每通訊端核心數：                 4
Socket(s):                       1
NUMA 節點：                      1
供應商識別號：                   GenuineIntel
CPU 家族：                       6
型號：                           158
Model name:                      Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
製程：                           9
CPU MHz：                        3600.000
CPU max MHz:                     4200.0000
CPU min MHz:                     800.0000
BogoMIPS:                        7200.00
虛擬：                           VT-x
L1d 快取：                       128 KiB
L1i 快取：                       128 KiB
L2 快取：                        1 MiB
L3 快取：                        8 MiB
NUMA node0 CPU(s)：              0-7

針對佇列的操作

q_new








struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (q)
        INIT_LIST_HEAD(q);
    return q;
}

q_free












void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *safe = NULL;
    element_t *prev = NULL;
    list_for_each_entry_safe (prev, safe, l, list)
        q_release_element(prev);
    free(l);
}

q_insert_head, q_insert_tail

Due to the same behavior of q_insert_head and q_insert_tail that both of them need to new an element, I create a function new_element.



















































element_t *new_element(char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (!q)
        return NULL;

    size_t s_len = strlen(s);
    q->value = malloc(s_len + 1);

    if (!q->value) {
        free(q);
        return NULL;
    }
    strncpy(q->value, s, strlen(s));
    q->value[s_len] = '\0';
    return q;
}

bool q_insert_head(struct list_head *head, char *s)
{
    // check if it is null
    if (!head)
        return false;

    // initialize the new node
    element_t *q = new_element(s);
    if (!q)
        return false;

    // add new node to head;
    list_add(&q->list, head);
    return true;
}


bool q_insert_tail(struct list_head *head, char *s)
{
    // check if it is null
    if (!head)
        return false;

    // initialize the new node
    element_t *q = new_element(s);
    if (!q)
        return false;

    // add new node to tail;
    list_add_tail(&q->list, head);
    return true;
}

Thanks for laneser 開發紀錄 (lab0). I improve function new_element with strdup.














element_t *new_element(char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (!q)
        return NULL;

    q->value = strdup(s);
    if (!q->value) {
        free(q);
        return NULL;
    }
    return q;
}

q_remove_head, q_remove_tail

Due to the same behaviour of these two, I create a function q_remove wich remove the target node and copy the value of removed node to sp.






































element_t *q_remove(struct list_head *target, char *sp, size_t bufsize)
{
    // remove target
    list_del_init(target);

    // get target element
    element_t *ret = container_of(target, element_t, list);

    // copy removed element value to sp
    if (sp && ret->value) {
        strncpy(sp, ret->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return ret;
}

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    // check queue is null of empty;
    if (!head || list_empty(head))
        return NULL;

    // remove head
    element_t *ret = q_remove(head->next, sp, bufsize);
    return ret;
}

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    // check queue is null of empty;
    if (!head || list_empty(head))
        return NULL;

    // remove tail
    element_t *ret = q_remove(head->prev, sp, bufsize);
    return ret;
}

q_size














int q_size(struct list_head *head)
{
    // check null or empty
    if (!head || list_empty(head))
        return 0;

    // compute len
    int len = 0;
    struct list_head *node = NULL;
    list_for_each (node, head)
        ++len;
    return len;
}

q_delete_mid

slow, fast pointer version.





















bool q_delete_mid(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return false;

    // search middle node
    struct list_head **slow = &head->next;
    for (struct list_head *fast = head->next->next;
         fast != head && fast->next != head; fast = fast->next->next)
        slow = &(*slow)->next;

    // get target element
    element_t *target = container_of(*slow, element_t, list);

    // remove node and release element
    list_del_init(*slow);
    q_release_element(target);
    return true;
}

Utilize prev pointer version

search by both sides.

















bool q_delete_mid(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return false;

    // search middle node
    struct list_head *r = head->next, *l = head->prev;
    for(; r != l && r->next != l; r = r->next)
        l = l->prev;

    // remove node and release element
    list_del_init(l);
    q_release_element(container_of(l, element_t, list));
    return true;
}

q_delete_dup

Searches the start node and end node of duplicate string list, removed duplicate list and concat to remove_head. At the end of the algorithm, q_free(remove_head). In the future improvement, this operation may can be executed when the system is not busy.


































bool q_delete_dup(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return false;

    // check if it's singular
    if (list_is_singular(head))
        return true;

    struct list_head *first_node = head->next, *end_node = head->next;
    struct list_head *remove_head = q_new(), *tmp = q_new();
    while (end_node != head) {
        // search the start and end of duplicates string node
        element_t *first_element = container_of(first_node, element_t, list);
        element_t *end_element = NULL;
        do {
            end_node = end_node->next;
            end_element = container_of(end_node, element_t, list);
        } while (end_node != head &&
                 !strcmp(first_element->value, end_element->value));

        // concat duplicates node to remove_head
        if (first_node->next != end_node) {
            list_cut_position(tmp, first_node->prev, end_node->prev);
            list_splice_init(tmp, remove_head);
        }
        first_node = end_node;
    }
    q_free(remove_head);
    q_free(tmp);
    return true;
}

q_swap























void q_swap(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return;

    // q_swap
    struct list_head *node = head->next, *curr = NULL, *next = NULL;
    while (node != head && node->next != head) {
        next = node->next;
        curr = node;
        node = node->next->next;

        // swap adjacent nodes.
        curr->next = next->next;
        next->prev = curr->prev;
        curr->prev->next = next;
        curr->prev = next;
        next->next->prev = curr;
        next->next = curr;
    }
}

q_reverse




















void swap_list_head(struct list_head **a, struct list_head **b)
{
    struct list_head *tmp = *a;
    *a = *b;
    *b = tmp;
}

void q_reverse(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head))
        return;

    struct list_head *safe = NULL, *curr = NULL;

    list_for_each_safe (curr, safe, head)
        swap_list_head(&curr->prev, &curr->next);
    swap_list_head(&curr->prev, &curr->next);
}

q_sort






















































struct list_head *merge_two_list(struct list_head *a, struct list_head *b)
{
    struct list_head *head = NULL, **ptr = &head;
    for (struct list_head **node = NULL; a && b; *node = (*node)->next) {
        node = strcmp(container_of(a, element_t, list)->value,
                      container_of(b, element_t, list)->value) < 0
                   ? &a
                   : &b;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
    return head;
}

struct list_head *merge_sort(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    // search middle node
    struct list_head *slow = head, *fast = head->next;
    for (; fast && fast->next; fast = fast->next->next)
        slow = slow->next;

    struct list_head *middle = slow->next;
    slow->next = NULL;

    return merge_two_list(merge_sort(head), merge_sort(middle));
}

void q_sort(struct list_head *head)
{
    // check if it's NULL or empty
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    // remove the link of tail and head to create stop condition for merge_sort
    head->prev->next = NULL;

    // merge_sort
    head->next = merge_sort(head->next);

    // assign prev to each node
    struct list_head *tmp = head;
    while (tmp->next) {
        tmp->next->prev = tmp;
        tmp = tmp->next;
    }
    // concat head and tail
    tmp->next = head;
    head->prev = tmp;
}

Add "shuffle" command to qtest

  • I create extra_func.h and extra_func.c to write the code for shuffle
  • There are two version of shuffle
    1. q_shuffle: need to for-loop to search the node we want to swap
      • Time Complexity: O(n^2)
      • Space Complexity: O(1)
    2. q_shuffle_dp: store all the address to a list then we can avoid the for-loop to search the node
      • Time Complexity: O(n)
      • Space Complexity: O(N)
  • Hence, I add two commands. 
    


    ​​​​ADD_COMMAND(shuffle,"| shuffle the queue with O(n^2) time "
​​​​            "complexity and constant space complexity");
​​​​ADD_COMMAND(shuffle_dp,"| shuffle the queue with O(n) time and space "

shuffle_dp will also be used to compare merge_sort.





































































































void swap_ptr(struct list_head **a, struct list_head **b)
{
    struct list_head *tmp = *a;
    *a = *b;
    *b = tmp;
}
/*
 * Swap nodes in doubly linked list
 */
void swap_node(struct list_head *a, struct list_head *b)
{
    if (a == b)
        return;
    else if (a->next == b || b->next == a)  // if they are neighbors
    {
        // decide who is left and who is right
        struct list_head *l = a, *r = b;
        if (b->next == a) {
            r = a;
            l = b;
        }

        // swap
        l->next = r->next;
        r->prev = l->prev;
        l->prev->next = r;
        l->prev = r;
        r->next->prev = l;
        r->next = l;
        
    } else {
        a->next->prev = b;
        b->next->prev = a;
        a->prev->next = b;
        b->prev->next = a;
        swap_ptr(&a->next, &b->next);
        swap_ptr(&a->prev, &b->prev);
    }
}

/*
 * Get list node by given index
 */
struct list_head *get_node_by_idx(struct list_head *head, int idx)
{
    for (; idx > 0; --idx)
        head = head->next;
    return head;
}

/*
 * Shuffle the list with Fisher–Yates shuffle algorithm
 * Time Complexity: O(N^2)
 * Space Complexity: O(1)
 */
void q_shuffle(struct list_head *head)
{
    srand(time(NULL));
    struct list_head *curr = head->prev;
    struct list_head *curr_next = NULL;
    for (int i = q_size(head); i > 1; --i) {
        curr_next = curr->prev;
        swap_node(curr, get_node_by_idx(head, rand() % i));
        curr = curr_next;
    }
}

/*
 * Utilize extra space to shuffle with Fisher–Yates shuffle
 * Time Complexity: O(N)
 * Space Complexity: O(N)
 */
void q_shuffle_dp(struct list_head *head)
{
    srand(time(NULL));
    int len = q_size(head);

    // list space to store all addressed of the queue.
    struct list_head **dp = malloc(sizeof(struct list_head **) * len);
    struct list_head *curr = head->next;
    for (int i = 0; i < len; ++i, curr = curr->next)
        dp[i] = curr;

    // shuffle
    curr = head->prev;
    struct list_head *curr_prev = NULL, *tmp = NULL;
    for (int i = len; i > 1; --i) {
        curr_prev = curr->prev;
        // swap nodes
        tmp = dp[rand() % i];
        swap_node(curr, tmp);

        // swap addresses in the list space
        swap_ptr(&dp[i], &tmp);

        // move to next
        curr = curr_prev;
    }
    free(dp);
}

Compare my merge_sort and linux/list_sort.c

  1. I write a new trace-19-compare_sort.cmd which generate 750,000 elements to sort and contains three kinds of string aaaa, cccc, eeee

    



















    ​​​​new
​​​​ih eeee 250000
​​​​ih cccc 250000
​​​​ih aaaa 250000    

​​​​# sort sorted array
​​​​time sort
​​​​time linux_sort

​​​​# sort reversed sorted array
​​​​reverse
​​​​time sort
​​​​reverse
​​​​time linux_sort

​​​​# sort shuffled array
​​​​shuffle_dp
​​​​time sort
​​​​shuffle_dp
​​​​time linux_sort

  2. comparison of my_sort and linux_sort in three cases.

    Cases my_sort linux_sort
    sorted array 0.278s 0.15s
    reversed sorted 0.273s 0.154s
    shuffled 1.236s 0.744s 
    ​​​​$ ./qtest  -f traces/trace-19-compare_sort.cmd 
​​​​cmd> option fail 0
​​​​cmd> option malloc 0
​​​​cmd> 
​​​​cmd> new
​​​​l = []
​​​​cmd> ih eeee 250000
​​​​l = [eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee ... ]
​​​​cmd> ih cccc 250000
​​​​l = [cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc ... ]
​​​​cmd> ih aaaa 250000
​​​​l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
​​​​cmd> 
​​​​cmd> # sort sorted array
​​​​cmd> time sort
​​​​l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
​​​​Delta time = 0.287
​​​​cmd> time linux_sort
​​​​l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
​​​​Delta time = 0.150
​​​​cmd> 
​​​​cmd> # sort reversed sorted array
​​​​cmd> reverse
​​​​l = [eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee ... ]
​​​​cmd> time sort
​​​​l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
​​​​Delta time = 0.273
​​​​cmd> reverse
​​​​l = [eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee ... ]
​​​​cmd> time linux_sort
​​​​l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
​​​​Delta time = 0.154
​​​​cmd> 
​​​​cmd> # sort shuffled array
​​​​cmd> shuffle_dp
​​​​l = [cccc cccc aaaa aaaa eeee aaaa aaaa eeee aaaa aaaa aaaa cccc cccc aaaa aaaa eeee aaaa eeee aaaa eeee cccc aaaa aaaa eeee eeee eeee eeee aaaa eeee eeee ... ]
​​​​cmd> time sort
​​​​l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
​​​​Delta time = 1.242
​​​​cmd> shuffle_dp
​​​​l = [eeee aaaa aaaa eeee aaaa cccc aaaa eeee aaaa aaaa aaaa cccc aaaa aaaa cccc aaaa eeee eeee cccc cccc eeee aaaa aaaa eeee eeee aaaa eeee aaaa cccc eeee ... ]
​​​​cmd> time linux_sort
​​​​l = [aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ... ]
​​​​Delta time = 0.744
​​​​Freeing queue

Tiny Web server

First Development process - git commit

  1. Copy most of the code of tiny web server to my extra_func.c.
  2. Add following code to extra_func.h 
    




    ​​​​extern int listenfd;
​​​​extern bool noise;

​​​​char *process(int fd, struct sockaddr_in *clientaddr);
​​​​int open_listenfd();
  3. Add command to qtest.c and overwrite function run_console, cmd_select to console.c from lab01-tiny-web-server.
  4. remove all cppcheck warning and errors.
    • Still try to figuring out whether there is a better way to avoid
      • warning: sscanf() without field width limits can crash with huge input data. [invalidscanf].
    • The following is my current solution. 
      ​​​​​​sscanf(buf, "%1023s %1023s", method, uri);
    • The solution of LJP-TW 
      ​​​​​​​​sscanf(buf, "%" xstr(MAXLINE) "s %" xstr(MAXLINE) "s", method, uri);
  5. The web server now can work, but met two error:
    • Diffirent behaviour between curl and browser
      • If I send a command from through curl, the program will execute correctly 
        

        ​​​​​​​​​​​​curl -v localhost:9999/new
​​​​​​​​​​​​curl -v localhost:9999/it/1
        reference link
      • If I send a command from the chrome browser, the program will execute the command at most three times. I think this is because of the auto-retry of chrome browser.
    • If I run web server, any command from the console will get into infinite for-loop

Bug Fix

  1. Infinite for-loop
    • In function cmd_select, I forgot to delete the condition if(has_infile) while we have user input. It leads cmdline = readline() will never be executed which makes the buffer never be clear. Hence, the select() always detect user input and leads to infinite for loop.
Last changed by 
 
JohnCena
0
261
Published on HackMD