# 2021q1 Homework2 (quiz2)
contributed by < `chiehen` >
###### tags:`linux2021`
## 測驗一
### 解釋程式碼
根據 q_insert_head 程式碼, 一個 queue 的架構大約如下:
```graphviz
digraph structs {
node[shape=record]
rankdir="LR"
queue [label="<h> head|<t> tail|<f2> size|{<list> list|{<p> prev|<n> next}}"];
subgraph subs{
struct1 [label="<v> value1|<next> next|<l> list|{<p> prev|<n> next}"];
struct2 [label="<v> value2|<next> next|<l> list|{<p> prev|<n> next}"];
struct3 [label="<v> value3|<next> next|<l> list|{<p> prev|<n> next}"];
struct3:next -> struct2:next;
struct2:next -> struct1:next;
struct3:p -> struct2:n[dir="both", constraint=false]
struct2:p -> struct1:n[dir="both", constraint=false]
}
queue:t -> struct1:v;
queue:h -> struct3:v;
queue:n -> struct1:p[dir="both" constraint=false];
queue:p -> struct3:n[dir="both" constraint=false];
}
```
:::danger
改用 Graphviz 製圖
:notes: jserv
:::
* list_cut_position()
```c=
/**
* list_cut_position() - Move beginning of a list to another list
* @head_to: pointer to the head of the list which receives nodes
* @head_from: pointer to the head of the list
* @node: pointer to the node in which defines the cutting point
*/
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
假設 list_from 是 head 為 head_from 的 list;
list_to 是 head 為 head_to 的 list;
將原本在 list_from 的 node 從 第一個 list_ele_t 到 node 搬至 list_to, 因此 head_from 留下 node->next 到最後
因為操作上只有使用到 其中的list node 因此圖片只展示 list node
```graphviz
digraph structs{
node[shape=record]
rankdir ="LR";
head1 [label="head from|<p> prev|<n> next"]
head1:n -> node1:p [dir="both"]
head1:p -> node4:n [dir="both"]
subgraph subs{
node1 [label="1|{<p> prev|<n> next}"];
node2 [label="2|{<p> prev|<n> next}"];
node3 [label="3|{<p> prev|<n> next}"];
node4 [label="4|{<p> prev|<n> next}"];
node1:n -> node2:p [dir="both"]
node2:n -> node3:p [dir="both"]
node3:n -> node4:p [dir="both"]}
}
```
結束函式後:
```graphviz
digraph structs{
node[shape=record]
rankdir ="LR";
head1 [label="head from|<p> prev|<n> next"]
head2 [label="head to|<p> prev|<n> next"]
head2:n -> node1:p [dir="both"]
head2:p -> node2:n [dir="both"]
head1:n -> node3:p [dir="both"]
head1:p -> node4:n [dir="both"]
node1 [label="1|{<p> prev|<n> next}"];
node2 [label="2|{<p> prev|<n> next}"];
node3 [label="3|{<p> prev|<n> next}"];
node4 [label="4|{<p> prev|<n> next}"];
node1:n -> node2:p[dir="both"];
node3:n -> node4:p [dir="both"]
}
```
* list_splice_tail()
```c=
/**
* list_splice_tail() - Add list nodes from a list to end of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*/
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next, *list_last = list->prev;
if (list_empty(list))
return;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
```
將 list 所連接的 node 接在 head 所串起的這個 list 的後面
看到這裡時覺得很奇怪, 為什麼不用處理 list 的記憶體, 仔細看才發現在宣告的時候並沒有使用到 malloc
[When and why to use malloc?](https://stackoverflow.com/questions/8800482/when-and-why-to-use-malloc)
> You use malloc when you need to allocate objects that must exist beyond the lifetime of execution of the current block (where a copy-on-return would be expensive as well), or if you need to allocate memory greater than the size of that stack (ie: a 3mb local stack array is a bad idea).
C99 7.20.3 Memory management functions
> The lifetime of an allocated object extends from the allocation until the deallocation.
依照這個可發現 `queue_t left;` 在 `list_merge` 後已不需要, `struct list_head sorted;` 則是在執行 `list_splice_tail(&sorted, &q->list);` 後完成任務
* container of 的 macro 可以從 member 推出 struct 的記憶體起始位置
```c=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
除了在[題目](https://hackmd.io/@sysprog/linux2021-quiz2)中所說到的外,將 `__pmember` 轉型成 char* 是因為指標在進行加減時，是以 dereference 後的型態的大小作為單位, 而因為 offsetof 回傳的單位是 bytes, 因此在進行運算時先轉型成 deference 後單位同為 1 byte 的char*
pointer to zero??
---
## 測驗二
### 解釋程式碼
func 接受一個 16 位元無號整數 N 並回傳小於或等於 N 的 power-of-2
```c=
uint16_t func(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
return (N + 1) >> 1;
}
```
直觀上想找到符合題目要求的值，便會想到從 MSB 開始找第一個不是零的位元(以下稱目標位元)，他的數值便是所求，舉例來說:
N = 10101~2~ = 21~10~ , func(N) = 16~10~ = 10000~2~
N = 100000~2~ = 32~10~, func(N) = 32~10~ = 100000~2~
而配合註解可以發現，此程式透過將目標位元以下的位元都賦值為 1 , 再將此數字 +1 變可得到(目標位元+1個位元)的數值, 因此只要再又一個 bit 就是所求，舉例:
N = 10101~2~ = 21~10~
1. 11111~2~
2. 100000~2~
3. 10000~2~ = 16~10~
而如何將目標位元以下的位元都賦值為 1, 便是測驗的部分。而以看似最難以達成的 N = 8000~16~ (最多 0 需要被設為 1)舉例
1. 因為目標位元保證為 1 ，在第三行後能保證目標位元及下一個位元都為 1, (N=C000~16~)
2. 基於上一點, 第四行則能保證目標位元及比他小的三個位元都為 1, (N = F000~16~)
3. 基於上一點, 第五行則能保證目標位元及比他小的7個位元都為 1, (N = FF00~16~)
4. 基於上一點, 第六行則能保證目標位元及比他小的15個位元都為 1, (N = FFFF~16~)
因此能保證此方法對 16 位元能達到預期的效果
P.S. 事實上，如果最初值為 N = 8000~16~, 會在最後 N + 1 時發生 overflow, 所以應另外做處理
---
## 測驗三
Sign in with Wallet
Connect another wallet