# Lab0 記錄
contributed by < `justapig9020` >
###### tags: `CSAPP`
## Link
[lab0](https://github.com/justapig9020/csapp-labs/tree/main/lab0/cprogramminglab-handout)
## Lab 說明
Lab0 主要目的為基於 single linked list 實作一 queue 。
架構以及測試環境由題目提供。我們需根據敘述完成 queue.c / queue.h 中對應的 linked list 操作。
其中包含：
- `queue_new`: 配置並初始化一個 queue
- `queue_insert_head`: 將一筆資料插入 queue 的最前端
- `queue_insert_tail`: 將一筆資料插入 queue 的最後端
- `queue_remove_head`: 將 queue 最前端的資料移除，並返回其值
- `queue_size`: 返回 queue 的大小(其中包含的數值數量)
- `queue_reverse`: 將 queue 中的數值順序反轉(例如： a, b, c 經過 reverse 後為 c, b, a)
在實作時需要注意記憶體的管理，以及對特定功能的複雜度要求。
- 記憶體配置可能失敗
- 可能要求對不存在( NULL ) 的 queue / element 做操作
- 所有功能需在 $O(n^2)$ 內完成
- `queue_insert_tail` , `queue_size` 的時間複雜度須為 $O(1)$
## Lab 實作
### queue_t
```c=
/**
* @brief Queue structure representing a list of elements
*/
typedef struct {
/**
* @brief Pointer to the first element in the queue, or NULL if the
* queue is empty.
*/
list_ele_t *head;
list_ele_t **tail;
size_t size;
} queue_t;
```
為了達成 `queue_size` , `queue_insert_tail` 在 $O(1)$ 內完成的目標，在 `queue_t` 中加入兩個新的成員。
- `tail`: 用以指向一個 pointer to `list_ele_t` ，該 pointer 會於下一個 `insert_tail` 時指向新加入的 `element` 。宣告為 pointer to pointer 的目的將會於 `queue_insert_tail` 解釋。
- `size`: 記錄當前 queue 中的 elements 數量。在 `insert` / `remove` 功能時對應的做加減。如此一來可以將計算個數的花費平攤至每個操作中，以此來達到 `queue_size` $O(1)$ 內完成。
### queue_new
```c=
/**
* @brief Allocates a new queue
* @return The new queue, or NULL if memory allocation failed
*/
queue_t *queue_new(void) {
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (!q)
return NULL;
q->head = NULL;
q->tail = &q->head;
q->size = 0;
return q;
}
```
配置一個記憶體並初始化，比較需要注意的是： `malloc` 有可能會失敗，根據 [man](https://man7.org/linux/man-pages/man3/free.3.html) 的描述
:::info
The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. ==On error, these functions return NULL.== NULL may also be returned by a successful call to malloc() with a size of zero, or by a successful call to calloc() with nmemb or size equal to zero.
:::
當記憶體配置失敗時，會返回 `NULL` ，因此在 `malloc` 後需要檢查返回的記憶體空間是否為合法的空間。若返回的值為 `NULL` 則代表記憶體配置失敗，根據敘述，需直接返回 `NULL` 。
### queue_free
```c=
/**
* @brief Frees all memory used by a element
* @param[in] e The element to free
* @return NULL if e is NULL, otherwise the value that the element holds
*/
static char *ele_free(list_ele_t *e) {
if (!e)
return NULL;
char *value = e->value;
free(e);
return value;
}
/**
* @brief Frees all memory used by a queue
* @param[in] q The queue to free
*/
void queue_free(queue_t *q) {
if (!q)
return;
list_ele_t *ptr = q->head;
while (ptr) {
list_ele_t *buf = ptr;
ptr = ptr->next;
char *value = ele_free(buf);
free(value);
}
free(q);
}
```
透過一個 `while loop` 施放 queue 中的所有 elements 。由於施放 element 的功能在其他地方也會用到，因此將其包裝成 `ele_free` 。
在 `ele_free` 時，會施放該 element 佔用的記憶體，並將其持有的 `value` 返回。由於 `value` 也是由我的手動配置的記憶體，因此在施放記憶體時，也須將其一併施放。
### queue_insert_head
```c=
/**
* @brief Allocates a new element
* @param[in] s The string to copied and hold by the new element
* @return The new element, or NULL if memory allocation failed
*/
static list_ele_t *ele_new(const char *s) {
// One addition byte for terminating NULL character
size_t n = strlen(s) + 1;
char *value = malloc(sizeof(char) * n);
if (!value)
return NULL;
list_ele_t *ele = malloc(sizeof(*ele));
if (!ele) {
free(value);
return NULL;
}
strncpy(value, s, n);
ele->next = NULL;
ele->value = value;
return ele;
}
/**
* @brief Attempts to insert an element at head of a queue
*
* This function explicitly allocates space to create a copy of `s`.
* The inserted element points to a copy of `s`, instead of `s` itself.
*
* @param[in] q The queue to insert into
* @param[in] s String to be copied and inserted into the queue
*
* @return true if insertion was successful
* @return false if q is NULL, or memory allocation failed
*/
bool queue_insert_head(queue_t *q, const char *s) {
if (!q)
return false;
list_ele_t *newh = ele_new(s);
if (!newh)
return false;
newh->next = q->head;
q->head = newh;
if (0 == q->size)
q->tail = &newh->next;
q->size += 1;
return true;
}
```
首先透過 `ele_new` 配置一個新的 element 。在 `ele_new` 中，首先計算傳入的字串長度，根據 [man](https://man7.org/linux/man-pages/man3/strlen.3.html) ：
:::info
The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').
:::
`strlen` 並不會計算到最後的 `\0` ，因此實際配置記憶體時，需額外多配置 1 byte 來存放 `\0` 。
需要注意的是，在配置 `ele` 時，若配置失敗，除了直接返回 `NULL` 外，也須將已經配置的 `value` 一併施放。
回到 `queue_insert_head` ，在配置完新的 element `newh` 後，將其插入當前 queue 的最前端。
插入後有一個特殊狀況需要考慮，若原本的 queue 為空 ( `q->size` 為 0 ) 時，需要將 `q->tail` 指向 `newh->next` 。
其原因為， `q->tail` 是一指標指向下一次 `insert_tail` 時會使用到的指標。在 queue 為空時， `q->tail` 需指向 `q->head` ，而當 queue 不為空時， `q->tail` 則需指向 queue 中最後一個 element 的 next 。因此，在插入 element 後需要檢查此一特殊狀況並解決。
### queue_insert_tail
```c=
/**
* @brief Attempts to insert an element at tail of a queue
*
* This function explicitly allocates space to create a copy of `s`.
* The inserted element points to a copy of `s`, instead of `s` itself.
*
* @param[in] q The queue to insert into
* @param[in] s String to be copied and inserted into the queue
*
* @return true if insertion was successful
* @return false if q is NULL, or memory allocation failed
*/
bool queue_insert_tail(queue_t *q, const char *s) {
if (!q)
return false;
list_ele_t *newt = ele_new(s);
if (!newt)
return false;
*q->tail = newt;
q->tail = &newt->next;
q->size += 1;
return true;
}
```
首先將傳入的資料包裝成 list_ele_t `newt` ，並將其插入整個 queue 的最尾端。
這邊要特別說明的是，為何要將 queue_t 的 `tail` 宣告成 pointer to pointer 而非單純的 pointer 。
若將 `tail` 宣告成 pointer 的話， queue_t 的 `head` 以及 `tail` 會分別指向 queue 的第一個以及最後一個 element 。在此狀況下，對空( empyt )的 queue 進行 `queue_insert_tail` 時也會遇到如 `queue_insert_head` 時的特殊狀況。
也就是在 queue 為空時， `head` , `tail` 皆指向 `NULL` 。因此在 `insert_tail` 時需要額外檢查 queue 是否為空，若為空時須將 `head` , `tail` 皆指向新插入的 element 。因爲此時新插入的 element 為 queue 中為一個 element ，換言之，該 element 既為第一個 element 又為最後一個 element 。
若是將 `tail` 宣告為 pointer to pointer 的話，只需固定將其指向接下來 `insert_tail` 時，用來指向新的 element 的指標即可。也就是在初始化 queue 時，將其指向 queue 的 `head` 。
在對空的 queue `insert_tail` 時，由於 `tail` 指向 `head` ，因此會將 `*tail` 也就是 `head` 指向新的 element 。此時將 `tail` 更新指向新的(也是當前 queue 中唯一的) element 的 next ，如此一來 `tail` 依舊滿足持續指向接下來將被更新的 pointer 。
在對非空 queue `insert_tail` 時，由於 `tail` 指向會後一個 element 的 `next` ，因此對 `*tail` 更新等同於將新的 element 接上。最後再將 `tail` 更新至新的 element 的 `next` 即可。
如此一來不僅能讓 `insert_tail` 在 $O(1)$ 內完成，更可讓整個 queue 的更新過程達成 branchless 。
### queue_remove_head
```c=
/**
* @brief Attempts to remove an element from head of a queue
*
* If removal succeeds, this function frees all memory used by the
* removed list element and its string value before returning.
*
* If removal succeeds and `buf` is non-NULL, this function copies up to
* `bufsize - 1` characters from the removed string into `buf`, and writes
* a null terminator '\0' after the copied string.
*
* @param[in] q The queue to remove from
* @param[out] buf Output buffer to write a string value into
* @param[in] bufsize Size of the buffer `buf` points to
*
* @return true if removal succeeded
* @return false if q is NULL or empty
*/
bool queue_remove_head(queue_t *q, char *buf, size_t bufsize) {
if (!q || q->size == 0)
return false;
list_ele_t *oldh = q->head;
q->head = q->head->next;
q->size -= 1;
if (0 == q->size)
q->tail = &q->head;
char *value = ele_free(oldh);
if (0 < bufsize && buf) {
strncpy(buf, value, bufsize - 1);
buf[bufsize - 1] = '\0';
}
free(value);
return true;
}
```
將 queue 中的第一個 element 刪除，並將其內容複製到 `buf` 中。需要別注意的是， buf 的大小由 `bufsize` 指定，且需要在最後一 byte 補上 `\0` 。
首先將第一個 element 從 queue 中取出變成 `oldh` ，並將 queu 的 `head` 指向原本的第二個 element ( oldh->next )。至此 linked list 的維護便完成了。
接著考慮 queue 的特殊狀況，也就是過去一直提到的，當 queue 為空時，需要將 queue 的 `tail` 重新指回其 `head` 。
接著，施放 `oldh` 並將其中的數值拷貝至 `buf` 。
這邊需要注意的是， `buf` 也許會為 `NULL` 。因此要對 `buf` 以及 `bufsize` 做檢查，唯有確定有空間讓我們寫入時，才對資料做拷貝。
在 `strncpy` 後別忘了在 `buf` 的最後一個 byte 填上 `\0` 來終止該字串。
最後記得將從 `oldh` 拿來的 `value` 施放。
### queue_size
```c=
/**
* @brief Returns the number of elements in a queue
*
* This function runs in O(1) time.
*
* @param[in] q The queue to examine
*
* @return the number of elements in the queue, or
* 0 if q is NULL or empty
*/
size_t queue_size(queue_t *q) {
if (!q)
return 0;
return q->size;
}
```
返回傳入的 queue 中具有幾個 elements 。若傳入的 queue 為 NULL 則返回 0 。
由於在 queue 中額外使用 `size` 來紀錄 elements 的個數，並將紀錄的成本均攤至每個 `insert` / `remove` 的功能中。因此此功能能在 $O(1)$ 的時間內完成。
### queue_reverse
```c=
/**
* @brief Reverse the elements in a queue
*
* This function does not allocate or free any list elements, i.e. it does
* not call malloc or free, including inside helper functions. Instead, it
* rearranges the existing elements of the queue.
*
* @param[in] q The queue to reverse
*/
void queue_reverse(queue_t *q) {
if (!q || 0 == q->size)
return;
list_ele_t *prev = NULL;
list_ele_t *curr = q->head;
list_ele_t *next;
q->tail = &curr->next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
q->head = prev;
}
```
將 queue 中的所有 elements 的順序反轉。
首先當 queue 為 NULL 或 empty 時，直接返回。
由於確保了 queue 不為 empty ，因此在一開始時 curr 必定指向一個存在的 element 。因此我們能將 queue 的 `tail` 更新成 curr 的 `next` ，因爲此時的 curr 指向當前 queue 中的第一個 element ，也就是 reverse 後的最後一個 element 。
接著我們透過三個指標 prev , curr , next 來完成 queue 的走訪以及反轉。
其原理為，若我們要將 curr 所指向的 element 反轉，則必須要將 `curr->next` 指向 curr 的上一個 element 。因此使用 prev 指標指向 curr 的上一個 element 。但是此時，由於 curr 的 next 指標指向了 prev ，因此我們無法得知原本的下一個 element 的位址。為了解決這個問題，額外宣告一個指標 next 用來保存 curr 的下一個 element 的位址。因此我們只要將 prev 更新為 curr 並將 curr 更新為 next 即可繼續完成對 queue 的走訪。
當 curr 指向 `NULL` 時，代表 curr 指向了原本 queue 的最後一個 element 的 next ，換言之 queue 走訪完畢。由於 prev 固定指向 curr 的上一位，因此 prev 此時指向原本 queue 的最後一個 element ，也就是 reverse 後的第一個 element 。因此我們只要將 queue 的 `head` 指向他，即可完成 queue 的 reverse 。
## Reference
[說明文件](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s22/www/labs/cprogramminglab.pdf)
[lab0 source code](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s22/www/labs/cprogramminglab-handout.tar)
Sign in with Wallet
Connect another wallet