# 2025q1 Homework2 (quiz1+2)
contributed by < `Brianpan` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
Repo: [Link](https://github.com/Brianpan/kernel-hw2)
# Quiz 1
## Q1
題目要寫一個list_insert_before函式, p是指到next指標的地址,所以終止條件是
*p 代表指到的那個元素
```cpp!
static inline void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before || *p != NULL; p = &(*p)->next)
;
*p = item;
item->next = before;
}
```
延伸問題: 撰寫合併排序
[commit](https://github.com/Brianpan/kernel-hw2/blob/03707a9fbd2a362b18c931f4b73742429d0971f1/list.c#L44)
## Q2
#### 演算法精神
演算法主要是在做移除符合適當大小的節點,這個設計沒有考慮樹的再平衡
移除的情況有三種
1. 左右子節點皆存在
2. 只有一個左右子節點
3. 沒有左右子節點
情況2,3比較直觀
情況2直接把那個子節點拉上來
```cpp!
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
```
情況3就直接把目標節點從樹中移除
```cpp!
*node_ptr = NULL
```
情況1的狀況是要思考這個刪除的節點要怎麼取代
有兩種方法
1. 左子樹最大值的節點
2. 右子樹最小值的節點
本題實作採取1.的做法
接下來找最右節點又有兩種情況
1. 直接是刪除節點的左節點
2. 不是左節點
是情況1.好解決,我們直接把刪除的節點的指標指給左節點
```cpp!
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /
```
情況2.以這個子樹為例我們要刪除9, 我們找到最大右節點5
做以下步驟
- 紀錄9的左右子節點
- 把5節點從樹中移除,這個動作代表5的左節點會取代5的位置
- 把5節點取代9節點的位置
```graphviz
digraph BST {
node [shape=circle];
9 -> 3;
9 -> 10;
3 -> 2;
5 [style=filled fillcolor=red];
3 -> 5;
5 -> 4;
}
```
實作中透過指標的指標去間接更新刪除節點的母節點指標
#### 實作
找左子樹最右邊的節點
```cpp!
/*
* Structure representing a free memory block in the memory allocator.
* The free tree is a binary search tree that organizes free blocks (of type block_t)
* to efficiently locate a block of appropriate size during memory allocation.
*/
void remove_free_tree(block_t **root, block_t *target)
{
/* Locate the pointer to the target node in the tree. */
block_t **node_ptr = find_free_tree(root, target);
/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while (*pred_ptr && (*pred_ptr)->right)
pred_ptr = &(*pred_ptr)->r;
/* Verify the found predecessor using a helper function (for debugging).
*/
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);
/* If the predecessor is the immediate left child. */
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /* Replace target with its left child. */
(*node_ptr)->r = old_right; /* Attach the original right subtree. */
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
} else {
/* The predecessor is deeper in the left subtree. */
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* Remove the predecessor from its original location. */
remove_free_tree(&old_left, *pred_ptr);
/* Replace the target node with the predecessor. */
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
}
}
/* If the target node has one child (or none), simply splice it out. */
else if ((*node_ptr)->l || (*node_ptr)->r) {
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
} else {
/* No children: remove the node. */
*node_ptr = NULL;
}
/* Clear the removed node's child pointers to avoid dangling references. */
target->l = NULL;
target->r = NULL;
}
```
### 補完程式碼
https://github.com/Brianpan/kernel-hw2/blob/master/q2.c
### 閱讀筆記
TBD
## Q3
### QuickSort精神
1. 找一個pivot值,將整個陣列或串列分成兩個部分,左半邊都小於等於pivot,右半邊都大於pivot
2. 向下分成左右兩個子問題,繼續做步驟1的操作,直到只剩下一個元素
3. 合併左右兩邊和pivot成為一個排序的陣列或串列
#### 非遞迴版本實作
##### 概念
想像一個虛擬的堆疊用迴圈迭代確認是否為空
這個例子是用begin,end陣列指到的值
初始狀態是
```cpp!
begin[0] = *list;
end[0] = list_tail(list);
```
每一輪結束後的更新狀態是
```cpp!
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
```
收斂是當L==R, 像是pivot那一點就是確認已排序
每個回合結束後會i+2,換句話說我們先排右邊的序列
##### 圖解
初始狀態
```graphviz
digraph g1 {
node[shape=plaintext];
"begin[0]" [fontcolor="brown"];
"end[0]" [fontcolor="brown"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n3 -> n1 -> n0 -> n2 -> n4 -> l0
}
"begin[0]" -> n3;
"end[0]" -> n4;
pivot -> n3;
L -> n3;
R -> n4;
p -> n1;
}
```
把pivot節點從串列移除
```graphviz
digraph g2 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n1 -> n0 -> n2 -> n4 -> l0
}
pivot -> n3 -> l1;
left -> l2;
right -> l3;
L -> n3;
R -> n4;
p -> n1;
}
```
p處理完節點1
```graphviz
digraph g3 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n0 -> n2 -> n4 -> l0
}
pivot -> n3 -> l1;
left -> n1 -> l2;
right -> l3;
L -> n3;
R -> n4;
p -> n0;
}
```
p處理完節點0
```graphviz
digraph g4 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n2 -> n4 -> l0
}
pivot -> n3 -> l1;
left -> n1 -> n0 -> l2;
right -> l3;
L -> n3;
R -> n4;
p -> n2;
}
```
p處理完所有節點
```graphviz
digraph g5 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
}
left -> n1 -> n0 -> n2 -> l0;
pivot -> n3 -> l1;
right -> l2;
L -> n3;
R -> n4;
p -> n4;
}
```
更新begin[i], end[i]指標
意義就是下一輪的左右邊界
```graphviz
digraph g6 {
node[shape=plaintext];
"begin[0]" [fontcolor="brown"];
"end[0]" [fontcolor="brown"];
"begin[1]" [fontcolor="brown"];
"end[1]" [fontcolor="brown"];
"begin[2]" [fontcolor="brown"];
"end[2]" [fontcolor="brown"];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
}
"begin[0]" -> n1;
"end[0]" -> n2;
"begin[1]" -> n3;
"end[1]" -> n3;
"begin[2]" -> n4;
"end[2]" -> n4;
pivot -> n3 -> l1;
left -> n1 -> n0 -> n2 -> l3;
right -> n4 -> l2;
L -> n3;
R -> n4;
}
```
### 實作
#### 單向串列版本
[連結](https://github.com/Brianpan/kernel-hw2/blob/master/q3.c)
```cpp!
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list);
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
#### 雙向串列版本
[連結](https://github.com/Brianpan/kernel-hw2/blob/master/q3_2.c)
此版本和單向串列的主要差別
- 只使用一個begin陣列去模擬堆疊
- 每次分割左右兩個串列前要把環狀串列最後指標給移除
- 這個實作最後要把雙向串列的prev指標更新回正確的地址
# Quiz2
## Q1
### 題目精神
- [x] 利用list API實作quicksort
- [ ] 實作有效亂數
### 補完程式碼
[程式碼](https://github.com/brianpan/kernel-hw2/blob/master/q4.c)
#### 實作quicksort
```cpp!
static void list_quicksort(struct list_head *head)
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
// get the pivot and remove it from the circular list
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
// move item to either list_less or list_greater list
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
// divide part
// recusively sort left, right sublist
list_quicksort(&list_less);
list_quicksort(&list_greater);
// merge phase
list_add(&pivot->list, head);
// list_less to the beginning of the list_head
list_splice(&list_less, head);
// list_greater to the end of the list_head
list_splice_tail(&list_greater, head);
}
```
#### 測試程式碼
更改原本的實作,使用比較前後元素確認排序是否成功
```cpp!
i = 0;
list_for_each_entry_safe (item, is, &testlist, list) {
if (is)
assert(cmpint(&item->i, &is->i) < 0);
list_del(&item->list);
free(item);
i++;
}
```
#### 延伸問題
##### list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting?
**stable sorting**
假設排序中有兩個元素在比較下是相同的 cmp(a, b) == 0, stable sorting會保證排序後相同排序大小的元素有按照原本的出現順序
$[1_1, 2, 1_2]$ -> $[1_1, 1_2, 2]$
回到原本的問題為什麼無法滿足stable sorting, 那是因為使用list_move就讓原本的順序相反,因為是往前插入
##### 實作整合至lab0c
[commit](https://github.com/Brianpan/lab0-c/commit/e94a5ef0ac32b62766c06587e5b75a688cc801ed)
使用quicksort實作有兩個perf test沒有跑過
##### 分析
TBD
## Q2
### 題目精神
- [x] 認識位元操作API: clz, ctz
- [x] 位元操作
- [ ] 計算平方根
### clz實作
#### 演算法精神
從長度32開始每次遞迴都把長度減半
終止條件:剩下兩位元時查表
magic number代表在2bit時候的快速查表
- clz(0) : 2
- clz(1) : 1
- clz(2) : 0
- clz(3) : 0
```cpp!
// divide and conquer width
static const int mask[] = {0, 8, 12, 14};
// magic numbers for 2 bits
// 0 -> 2
// 1 -> 1
// 2 -> 0
// 3 -> 0
static const int magic[] = {2, 1, 0, 0};
unsigned clz2(uint32_t x, int c)
{
if (!x && !c)
return 32;
uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));
// 2 bits left which implies c == 3
// c = 0 => 16 bits
// c = 1 => 8 bits
// c = 2 => 4 bits
// c = 3 => 2 bits
if (c == 3)
return upper ? magic[upper] : 2 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}
```
64位元是32位元延伸, 先判斷前32位元clz32是否是0, 是則判斷下32位元的clz32值
```cpp!
static inline int clz64(uint64_t x)
{
return clz32(x >> 32) ? clz32(x >> 32) :
clz32(x & 0xFFFFFFFF) + 32;
}
```
### 計算sqrt
```cpp!
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
/* clz64(x) returns the count of leading zeros in x.
* (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
* Rounding that index down to an even number ensures our starting m is a
* power of 4.
*/
int shift = (total_bits - 1 - clz64(x)) & 0xFFFFFFFE;
m = 1ULL << shift;
while(m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
#### 演算法精神
TBD
理解中, 要用自己的話說一次
[reference](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg?view)
## Q3
### 目標
- [x] 理解hash table實作
- [x] 應用在2sum
這裡是使用linked list方式實作map,這個方式好處是不用碰撞後還要挪元素
(probing)
### hlist
linux 用於hash table實作的資料結構[include/linux/types.h](https://github.com/torvalds/linux/blob/master/include/linux/types.h)
```cpp!
struct hlist_head {
struct hlist_node *first;
}
struct hlist_node {
struct hlist_node *next, **pprev;
}
```
### map實作
資料結構和巨集
```cpp!
#define MAP_HASH_SIZE(bits) (1 << (bits))
#define GOLDEN_RATION_32 0x61C88647
// definition of the map structs
typedef struct {
int bits;
struct hlist_head *ht;
} map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
初始化map
```cpp!
map_t *map_init(int bits)
{
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(bits));
if (map->ht) {
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
湊雜函式
```cpp!
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
return (val * GOLDEN_RATION_32) >> (32 - bits);
}
```
取得函式
這裡的處理比較直觀
- 先找到湊雜值所在的串列
- 使用線性搜尋找到鍵值相同的元素
```cpp!
static struct hash_key *find_key(map_t *map, int key)
{
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
// find exact mach of the key from the hash table's hlist
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
return NULL;
}
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
新增函式
比較值得注意的是從頭插入
需要更新**pprev, *next指標
```cpp!
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
// key exists
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
if (!kn)
return;
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
// renew pprev of old first node
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
```
刪除map
每個map串列逐個刪除
這邊pprev的更新是把它更新成&head, 下一輪再做刪除
```cpp!
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
// next's pprev to cur's pperv
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
Sign in with Wallet
Connect another wallet