# 2021q1 Homework2 (quiz2)
contributed by < `mahavishnuj` >
## 測驗一 include/linux/list.h 解讀與實作
### `struct` 的初始化與 ?
```cpp
struct list_head {
struct list_head *prev, *next;
};
/**
* LIST_HEAD - Declare list head and initialize it
* @head: name of the new object
*/
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
/**
* INIT_LIST_HEAD() - Initialize empty list head
* @head: pointer to list head
*/
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head; head->prev = head;
}
/**
```
除了上述的的內容可以看出 `struct` 本身是一個是一個 Doubly-linked list 裡面含了兩個 `Pointer`
:::warning
注意 doubly-linked list 連字號的擺放位置。
:notes: jserv
:::
``` graphviz
digraph struct {
rankdir=LR
node[shape=record]
head [label="{<prev>prev|<head>head|<next>next}"]
}
```
一開始新增第一個 `node` 之後把 `head->next` 跟 `head->prev` 都指向自己
``` graphviz
digraph struct {
rankdir=LR
node[shape=record]
head [label="{<prev>prev|<head>head|<next>next}"]
head:next:e -> head:prev:w[arrowhead=arrow]
}
```
### add_tail
這邊有個 `add_tail` 的部分就是在 `head` 的後面加入新的節點
```c=
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
/**
* list_del() - Remove a list node from the list
* @node: pointer to the node
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
/**
```
先新增一個一個 `Pointer` `Prev` 指向原本的點， `node` 就是即將新增的點
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
prev [label="prev"]
node[shape=record]
head [label="{<prev>prev|<listnode>head|<next>next}"]
tail [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:n -> head:n
head:prev:s -> head:s
prev-> head
}
```
把 `prev` 所指的點的 `next` 這個指標指向新的點
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
prev [label="prev"]
node[shape=record]
head [label="{<prev>prev|<listnode>head|<next>next}"]
tail [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> tail:s
head:prev:s -> head:s
prev-> head
}
```
再把 `tail` 的 `next` 指標指到 `Prev` 所指向的位置
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
prev [label="prev"]
node[shape=record]
head [label="{<prev>prev|<listnode>head|<next>next}"]
tail [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> tail:s
tail:next:n -> head:n
head:prev:s -> head:s
prev-> head
}
```
再把 `tail` 的 `prev` 指標也指到 `Prev` 所指向的位置
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
prev [label="prev"]
node[shape=record]
head [label="{<prev>prev|<listnode>head|<next>next}"]
tail [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> tail:s
tail:next:n -> head:n
tail:prev:s -> head:s
head:prev:s -> head:s
prev-> head
}
```
完整結束後的結構長這樣，指標都是指向都是指向該節點的位置
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
prev [label="prev"]
node[shape=record]
head [label="{<prev>prev|<listnode>head|<next>next}"]
tail [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> tail:prev:s
tail:next:s -> head:prev:s
tail:prev:n -> head:next:n
head:prev:n -> tail:next:n
prev-> head
}
```
### del_tail():
先新增兩個指標 `next` 跟 `prev` 分別指向 `node 的 next` 與 `node 的 prev`
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
prev [label="prev"]
next [label="next"]
node[shape=record]
head [label="{<prev>prev|<listnode>head|<next>next}"]
tail [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> tail:prev:s
tail:next:s -> head:prev:s
tail:prev:n -> head:next:n
head:prev:n -> tail:next:n
prev-> head
next-> head
}
```
再分別把 `next 的 prev 指標指到 prev 的位置`
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
prev [label="prev"]
next [label="next"]
node[shape=record]
head [label="{<prev>prev|<listnode>head|<next>next}"]
tail [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> tail:prev:s
tail:next:s -> head:prev:s
tail:prev:n -> head:next:n
head:prev:n -> head
prev-> head
next-> head
}
```
最後把 `prev 的 next 指標指到` next的位置
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
prev [label="prev"]
next [label="next"]
node[shape=record]
head [label="{<prev>prev|<listnode>head|<next>next}"]
tail [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:n -> head:prev:n
prev-> head
next-> head
}
```
### list_empty() and list_is_singular
顧名思義一個是檢查是否為空的 `list` 另一個則是檢查是否為單一 `node`
```c=
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
/**
* list_is_singular() - Check if list head has exactly one node attached
* @head: pointer to the head of the list
*/
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
### list_splice_tail
這裡的部分是哪兩條 `linked-list` 串接起來但需要注意的是從 `list->next開始串接`
```c=
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_cut_position
```c=
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;
}
```
假設一開始為三個點的狀態下，先新增一個 `Pointer : head_from_first` 指向 `head_from` 的 `next`
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
dummy [label="head_from_first"]
node[shape=record]
head [label="{<prev>prev|<listnode>head_to|<next>next}"]
first [label="{<prev>prev|<listnode>head_from|<next>next}"]
cutnode [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> first:prev:s
first:next:s -> cutnode:prev:s
cutnode:next:e ->head:s
dummy-> cutnode
}
```
接著開始操作`head_from` 的 `next` 所指向 `node->next` 還有 `head_from->next->prev` 指向 `head_from`
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
dummy [label="head_from_first"]
node[shape=record]
head [label="{<prev>prev|<listnode>head_to|<next>next}"]
first [label="{<prev>prev|<listnode>head_from|<next>next}"]
cutnode [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> first:prev:s
head:prev:w -> first:e
first:next:n -> head:prev:n
cutnode:next:e ->head:s
cutnode:prev:e ->head:s
dummy-> cutnode
}
```
最後調整
``` graphviz
digraph structs {
rankdir=LR
node[shape=plaintext]
dummy [label="head_from_first"]
node[shape=record]
head [label="{<prev>prev|<listnode>head_to|<next>next}"]
first [label="{<prev>prev|<listnode>head_from|<next>next}"]
cutnode [label="{<prev>prev|<listnode>node|<next>next}"]
head:next:s -> cutnode:prev:s
head:prev:w -> cutnode:e
first:next:n -> head:prev:n
cutnode:next:n ->cutnode:n
dummy-> cutnode
}
```
### MergeSort() 實作
COND1 = ?
(c) fast->next == list
COND2 = ?
(b) fast->next->next == list
MMM = ?
(e) &get_middle(&q->list)->list
TTT = ?
(a) slow
## 測驗 `2`
- 考慮函式 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 >> X;
N |= N >> Y;
N |= N >> Z;
return (N + 1) >> 1;
}
```
從 `f(21) = 16` 的結果來推斷，最後在 `return` 之前結果會是 `1111` 加上一之後變成 `10000` 之後在經過 `bitwise` 運算變成 `1000` 以十六位無號數來說以最糟糕的情況大概是只有最高位元是一，並且要在四次的運算把所有 `bit` 變成 `1`
```c=
N = 1000 0000 0000 0000
//N |= N >> 1;
N = 1100 0000 0000 0000
//N |= N >> 2;
N = 1111 0000 0000 0000
//N |= N >> 4;
N = 1111 1111 0000 0000
//N |= N >> 8;
N = 1111 1111 1111 1111
```
## 測驗 `3`
### bitcpy 實驗與相關議題
```c=
#include <stdint.h>
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t count)
{
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);
static const uint8_t read_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t write_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
while (count > 0) {
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
/* Cross multiple bytes */
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
mask |= write_mask[write_lhs + bitsize];
*dest++ = (original & mask) | (data >> write_lhs);
}
count -= bitsize;
}
}
```
一個 `byte` 有 8 個 `bits` ， 假設 `_read = 0 ` 的話， `read_lhs = 0` 再來 `read_rhs = 8` 因此 `lsh` 跟 `rhs` 分別表示了要寫或讀的範圍的 `offset'
```c=
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
```
## 測驗 `4`
- TO DO
Sign in with Wallet
Connect another wallet