# 2018q3 Homework3 (list)
contributed by < littlepee >

[你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf)

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

巨集 (Macro) 是拿空間換取時間，在編譯之前，前置處理器 (preprocessor) 就將該程式替換至各個呼叫區塊，所以相同的邏輯在會重複出現在各個地方，但是由於執行時間不需要在函式堆疊切換，減少時間的耗損。定義巨集之後，編譯器就可以使用語彙字元字串用來替代原始程式檔中出現的每個識別項

函式是拿時間換取空間的，透過執行時期在函式堆疊的切換，相同邏輯區塊只要抽出成為函式，則大家共用同一份程式即可(在記憶體中只有一份實體，較節省記憶體空間)。函式實務上還有另一個好處是可以取得函式位址，也就是說可以把函式當參數。

- [程式設計 微知識(二) 函式(function)與巨集(macro)](https://dotblogs.com.tw/ace_dream/2016/01/16/function_macro)
- [How to properly use macros in C](https://pmihaylov.com/macros-in-c/)

---
Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

---
GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？

`typeof` 可以獲得變數的型態，且可以拿來宣告變數。

`typeof (*x) y;` -> This declares y with the type of what x points to.

- [Using the GNU Compiler Collection (GCC): Typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)

---

解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

---

## doubly-linked list

### queue.h

- 增加 pre ，使每個 element 可以指向前一個(達到雙向)

typedef struct ELE {
    /* Pointer to array holding string.
       This array needs to be explicitly allocated and freed */
    char *value;
    struct ELE *pre;
    struct ELE *next;
} list_ele_t;

### q_insert_head

- 從頭加入，新加入的 element 變成最開頭，因此他的 pre 會指向 NULL
- 原本的開頭的 element ，他的 pre 會改成指向 新開的 element

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)  // Return false if q is NULL
        return false;

    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)  // could not allocate space
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    newh->pre = NULL;
    newh->value = strdup(s);
    if (q->q_size == 0) {
        q->q_tail = newh;
    } else {
        q->head->pre = newh;
    }

    q->head = newh;
    (q->q_size)++;

    return true;
}

### q_insert_tail

- 從尾巴加入，新開的 element 的 pre 要指向原本的尾巴

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL)  // Return false if q is NULL
        return false;

    list_ele_t *new;
    new = malloc(sizeof(list_ele_t));
    if (new == NULL)  //  could not allocate space
        return false;

    new->next = NULL;
    new->value = strdup(s);
    if (q->q_size == 0) {
        q->head = new;
        new->pre = NULL;
    } else {
        q->q_tail->next = new;
        new->pre = q->q_tail;
    }

    q->q_tail = new;
    q->q_size++;

    return true;
}

### q_remove_head

- 從頭移除，因此變成新的開頭的 element ，他的 pre 會指向 NULL
- 須增加判斷，確定 q 不是空的

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if ((q == NULL) ||
        (q->q_size == 0))  // Return false if queue is NULL or empty.
        return false;

    if (sp) {  // If sp is non-NULL
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        int string_size = strlen(tmp->value);
        string_size =
            (string_size > (bufsize - 1))
                ? (bufsize - 1)
                : string_size;  // up to a maximum of bufsize-1 characters
        strncpy(sp, tmp->value, string_size);  // copy the removed string to *sp
        sp[string_size] = '\0';                // plus a null terminator
        free(tmp);
        q->q_size--;
        if (q->q_size)
            q->head->pre = NULL;
        return true;
    }

    return false;
}

### q_reverse

- 修正 q_reverse ，使用 pre 來做反轉

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if ((q == NULL) || (q->q_size == 0))  // No effect if q is NULL or empty
        return;

    list_ele_t *next_element;
    list_ele_t *current = q->head;

    q->q_tail = q->head;
    
    while (current) {
        q->head = current;

        next_element = current->next;
        current->next = current->pre;
        current->pre = next_element;
        current = next_element;
    }
}

### 目前進度

- 增加 pre ，使每個 element 可以指向前一個(達到雙向)
- 在 q_insert_head 和 q_insert_tail 中加入 pre 的相關功能

TOTAL		100/100

- 在 q_remove_head 中加入 pre 的相關功能

TOTAL		69/100

- 修正 q_remove_head 中 pre 的判斷

TOTAL		100/100

- 修正 q_reverse ，使用 pre 來做反轉

TOTAL		100/100