2022q1 Homework1 (lab0)

contributed by < qwe661234 >

Implement queue.c

queue structure

Doubly-linked list and its value is string.

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

typedef struct {
    char *value;
    struct list_head list;
} element_t;

queue_new

struct list_head *q_new()
{
    struct list_head *newh =
        (struct list_head *) malloc(sizeof(struct list_head));
    if (!newh)
        return NULL;

    INIT_LIST_HEAD(newh);
    return newh;
}

q_insert_head

Add new queue node to the end of the list by list_add.

If malloc fails to allocate space for string that store in new node, you should free the memory of new node. Otherwise, it would cause memory leak.

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = (element_t *) malloc(sizeof(element_t));
    if (!ele)
        return false;
    size_t slen = strlen(s);
    char *str = (char *) malloc((slen + 1) * sizeof(char));
    if (!str) {
        free(ele);
        return false;
    }
    strncpy(str, s, slen);
    str[slen] = '\0';
    ele->value = str;
    list_add(&ele->list, head);
    return true;
}

Instead of char *str = (char *) malloc((slen + 1) * sizeof(char)), you can simply write as char *str = malloc((slen + 1) * sizeof(char)) which is a valid C statement.

jserv

q_insert_tail

Expect for adding new queue node to the end of the list by list_add_tail, other operations are the same as q_insert_head.

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = (element_t *) malloc(sizeof(element_t));
    if (!ele)
        return false;
    size_t slen = strlen(s);
    char *str = (char *) malloc((slen + 1) * sizeof(char));
    if (!str) {
        free(ele);
        return false;
    }
    strncpy(str, s, slen);
    str[slen] = '\0';
    ele->value = str;
    list_add_tail(&ele->list, head);
    return true;
}

q_remove_head

Get first node of queue by list_first_entry.

Check if the buffer size - 1 is larger than the length of copy string. Otherwise, it would overflow destination buffer.

Undefined behavior for strncpy

1. memory dest and memory src overlap
2. one of dest and src does not point to char
3. size of dest is less than bufsize
4. size of src is less than size of dest, but src is not terminate with '\0'

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target = list_first_entry(head, element_t, list);
    if (sp) {
        size_t slen = strlen(target->value);
        if (slen <= bufsize - 1) {
            strncpy(sp, target->value, slen);
            sp[slen] = '\0';
        } else {
            strncpy(sp, target->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
    }
    list_del(&target->list);
    return target;
}

q_remove_tail

Except for getting first node of queue by list_last_entry, other operations are the same as q_remove_head.

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target = list_last_entry(head, element_t, list);
    if (sp) {
        size_t slen = strlen(target->value);
        if (slen <= bufsize - 1) {
            strncpy(sp, target->value, slen);
            sp[slen] = '\0';
        } else {
            strncpy(sp, target->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
    }
    list_del(&target->list);
    return target;
}

q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    int len = 0;
    struct list_head *li;
    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

If queue is singular, delete the only node in queue.

If queue is non-singular, use two pointer to get middle node. The first pointer is point to the first node and the second pointer is point to the last node. The first pointer iterate from the first to the the last node and the last pointer iterate oppositely. When these two pointers point to the same node or the firat pointer cross the second pointer, the node pointed by the second pointer would be the middle node.

Becasue these two pointers meet the terminal condition in the beginning, we use do while.

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target;

    if (!list_is_singular(head)) {
        // More than one node in the queue
        struct list_head *front = head->next, *back = head->prev;
        do {
            front = front->next;
            back = back->prev;
        } while (front != back && front->prev != back);
        target = list_entry(front, element_t, list);
        list_del(front);
    } else {
        // Only one node in the queue
        target = list_entry(head->next, element_t, list);
        list_del(head->next);
    }
    free(target->value);
    free(target);
    return true;
}

q_delete_dup

A queue node would be delete in two condition:

1. node value is equal to next node value
2. node value is not equal to next node value, but it is equal to previous node value.

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    bool flag = false;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (&safe->list != head && !strcmp(entry->value, safe->value)) {
            flag = true;
            list_del(&entry->list);
            free(entry->value);
            free(entry);
        } else if (flag) {
            flag = false;
            list_del(&entry->list);
            free(entry->value);
            free(entry);
        }
    }
    return true;
}

q_swap

Iterate the queue and record the number of iterated node. If the number is even, move current node to the position which is previos to previous node.

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int count = 0;
    struct list_head *node, *prev = head;
    list_for_each (node, head) {
        count++;
        if (count % 2 == 0) {
            list_move(node, prev);
            node = node->next;
            prev = node;
        }
    }
}

q_reverse

Modified version:

Except for the last node, move node to the queue tail from node is previous to the last node to the first node.

This version is more concise.

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *cur = head->prev->prev, *next;
    while(cur != head) {
        next = cur->prev;
        list_move_tail(cur, head);
        cur = next;
    }
}

original version:

Change the value of pointer *prev and *next of all queue nodes and head

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    element_t *entry, *safe;
    struct list_head *tmp;
    list_for_each_entry_safe (entry, safe, head, list) {
        tmp = entry->list.prev;
        entry->list.prev = entry->list.next;
        entry->list.next = tmp;
    }
    tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

By means of Linux APIs, you can shorten the above code snip.

jserv

q_sort

Sort the queue by merge sort.

I want to create another head to maintain when I divide the queue, but malloc is disallowed in q_sort. Therefore, I remove queue head and pass the first node and the last node as parameters.

Because the mergeSort only return the first node of sorted queue, we should iterate sorted queue to find out the last node. Then, connect removed queue head to the first node and the last node of sorted queue.

struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
    struct list_head *return_head, *cur;
    if (strcmp(list_entry(l1, element_t, list)->value,
               list_entry(l2, element_t, list)->value) < 0) {
        return_head = l1;
        l1 = l1->next;
    } else {
        return_head = l2;
        l2 = l2->next;
    }
    cur = return_head;
    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) < 0) {
            cur->next = l1;
            l1->prev = cur;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2->prev = cur;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    if (l1) {
        cur->next = l1;
        l1->prev = cur;
    } else if (l2) {
        cur->next = l2;
        l2->prev = cur;
    }
    return return_head;
}

struct list_head *mergeSort(struct list_head *head, struct list_head *tail)
{
    if (head == tail)
        return head;
    struct list_head *front = head, *back = tail;
    do {
        front = front->next;
        back = back->prev;
    } while (front != back && front->prev != back);
    if (front != back) {
        back->next = NULL;
        front->prev = NULL;
    } else {
        front = front->next;
        back->next = NULL;
        front->prev = NULL;
    }
    struct list_head *l1 = mergeSort(head, back);
    struct list_head *l2 = mergeSort(front, tail);
    return merge(l1, l2);
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *front = head->next, *back = head->prev;
    front->prev = NULL;
    back->next = NULL;
    front = mergeSort(front, back);
    back = front;
    while (back->next)
        back = back->next;
    head->next = front;
    front->prev = head;
    head->prev = back;
    back->next = head;
}

Command list

All commands store in a command list, and it is a singly-linked list

Data Structure of command list

• name: command name
• operation: do_command function
• documentation: command information show in command help

typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

ADD_COMMAND Macro

ADD_COMMAD automatically link command xxx to its operation function do_xxx

#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)

You should explain why it works.

jserv

add_cmd

cmd_list is the head of command list

what while loop in funciton add_cmd does is sorting commands in alphabetical order. The operaion like insertion sort, find out the suit position from the head of list and insert new command element into command list.

void add_cmd(char *name, cmd_function operation, char *documentation)
{
    cmd_ptr next_cmd = cmd_list;
    cmd_ptr *last_loc = &cmd_list;
    while (next_cmd && strcmp(name, next_cmd->name) > 0) {
        last_loc = &next_cmd->next;
        next_cmd = next_cmd->next;
    }

    cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
    ele->name = name;
    ele->operation = operation;
    ele->documentation = documentation;
    ele->next = next_cmd;
    *last_loc = ele;
}

Add new command shuffle for qtest

q_shuffle

Follow the modern shuffle algorithm to shuffle queue.

• Each round:
  1. choose tail node and record node previous to it.
  2. remove tail node.
  3. generate random number, this number represent node number from 0 ~ n - 1
     • node number of the first node of queue is 0.
     • n means node number of tail node.
  4. find out the node that its number is equal to the random number and swap the node for tail node.
  5. set tail node to recorded node.
• Terminal:
  tail node is equal to the frist node

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    srand(time(NULL));
    int size = q_size(head);
    struct list_head *cur, *tail = head, *target = head->prev;
    for (int i = size - 1; i > 0; i--) {
        long random_num = rand() % i;
        cur = head->next;
        list_del(target);
        while (random_num) {
            cur = cur->next;
            random_num--;
        }
        list_move_tail(target, cur);
        list_move_tail(cur, tail);
        tail = tail->prev;
        target = tail->prev;
    }
}

do_shuffle

When user call command shuffle, funciton do_shuffle would be called.

static bool do_shuffle(int argc, char *argv[])
{
    if (!l_meta.l)
        report(3, "Warning: Calling sort on null queue");
    error_check();

    int cnt = q_size(l_meta.l);
    if (cnt < 2)
        report(3, "Warning: Calling sort on single node");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();
    set_noallocate_mode(false);

    bool ok = true;

    show_queue(3);
    return ok && !error_check();
}

Add command shuffle

Function ADD_COMAND connect command parameter1 to do_parameter1 automatically, so when user call command shuffle, then function do_shuffle would be called.

parameter2 is the information of command. When user call command help, the "| shuffle queue" will show in the information of the command shuffle.

ADD_COMMAND(shuffle, "                | shuffle queue");

TODO List

• read continer_of
  https://hackmd.io/@sysprog/linux-macro-containerof
• qtest 提供新的命令 shuffle
• read qtest
• 在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
• 以 Valgrind 分析記憶體問題
• 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
• 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示