# 2019q1 Homework1 (lab0)
contributed by < [`chenIshi`](https://github.com/chenIshi/lab0-c) >

## 實驗環境
:::info
OS: `Ubuntu 16.04.5 LTS`
Kernel: `4.15.0-36-generic`
CPU: `Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz`
Byte-order: `Little Endian`
:::

:::danger
是不是該升級 Ubuntu Linux 系統呢？
:notes: jserv
:::

:::info
不過 Autoware 官方好像是建議用 16.04 的 Ubuntu 加上 ROS kinetic
為此裝兩個版本的 Ubuntu 或開虛擬機跑 autoware 好像都有點不適合
:cry: 陳奕熹
:::
## `C Programming Lab` 第一份作業要求
1. 整份程式目標在1~2小時內完成
2. 需要處理不合法的操作，像是`嘗試對 NULL/ Empty List 作 remove`
3. 部份操作要求在常數時間內完成，像 `q_size()`

## `free()`對不同資料結構實做狀況
1. 起因：`q_free()` 需要把 link list 全部記憶體釋放（不能只釋放`queue_t`）
2. 實驗：資料儲存型態以及`free()`後記憶體狀態

## struct offset 操作

#include <stdlib.h>
#include <string.h>

typedef struct ELE {
    struct ELE *next;
    char *value;
} list_t;

int main()
{
    /* set queue head */
    list_t *queue;
    queue = malloc(sizeof(list_t));

    queue->value = strdup("hello world");

    /* call next by in-struct pointer */
    list_t *to_be_insert;
    to_be_insert = malloc(sizeof(list_t));

    queue->next = to_be_insert;
    to_be_insert->value = strdup("bye world");

    /* call next by memory offset */
    (queue + 1)->value = strdup("weird world");
    (queue + 1)->next = NULL;

    return 0;
}

:::info
為了減少`queue_t`裡面 metadata 的數量，我試著看能不能用 `queue size` 推出指向`tail`的記憶體位址
:::


一開始因為不熟悉 pointer 的加減法，所以誤用 `*(queue + 1)` 去存取結構
後來才發現到的確是可以用 `queue + sizeof(list_t) / sizeof(queue) * size` 的方法拿到 `tail` 的，不過有一個很重要的前提在於 **struct 結構間不能有其他的動態分配記憶體**，不然這樣取記憶體位移就會錯誤，所以最後也沒有採取這樣的方法

:::warning
有個變形的 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 就利用指標之間的數值落差，做出節省記憶體開銷的資料結構
:notes: jserv
:::

:::info
但是在用 gdb 檢查記憶體狀況的時候，發現了部份應該屬於 `你所不知道的C語言` 範疇的問題

1. 結構元素在記憶體對應的順序先後是怎麼決定的？
> `list_t` 元素宣告時，是 `struct ELE *next` 先於 `char *value`
> 但是記憶體對應位址先後卻是相反 ?
2. 結構元素間的記憶體位移大小為什麼都是0x20(也就是十進位的16)，明明每個元素大小應該都只有 `pointer` 大小，也就是 0x10?
:::

## 神奇的 git hook

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    char *val;
    val = strdup(s);
    if (val == NULL)
        free(newh);
        return false;

以上是 `q_insert_tail()` 一開始初始化記憶體部份，一開始 commit 的時候
我忘記在 line 60 可以把 newh 記憶體空間釋放，很神奇的是 git hook 有抓到這個 memory leak
而且 debug 訊息非常明確，不是在 line 55 需要我去釋放 NULL 的記憶體配置
這讓我不禁開始懷疑背後要怎麼實做，畢竟編譯器最佳化印象中沒提到這個部份
正如老師說的，`工程師說出「似乎」「印象中」這種話是相當不負責任的`，

:::warning
看懂 cppcheck 如何做程式靜態分析嗎？
:notes: jserv
:::

## q_free()

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    /* Free queue head first */
    if (q == NULL)
        return;

    list_ele_t *free_ptr;
    list_ele_t *temp;
    free_ptr = q->head;
    while (free_ptr != NULL) {
        temp = free_ptr;
        free_ptr = free_ptr->next;
        free(temp);
    }
    free(q);
}

原本在 line 13 ~ 15 有嘗試釋放 value 的記憶體位址，不過就從錯誤訊息來看
該位址並沒有被 `malloc()` 過，因此嘗試釋放它可能會導致失敗或甚至 `core dump`
因為一直不清楚 `qtest` 會怎麼呼叫 `q_insert_head/tail()`
畢竟執行 `qtest` 時只會顯示插入的值