HackMD
2025q1 Homework2 (quiz1+2)
< Urbaner3 >
連結與參少材料
week1
quiz 1
先說明題目，包含一個單向的鏈結串列原型，程式碼，稱作 list.h 和 quiz1a.c 。把 list_t, list_item_t 定義放在 list.h 裡面。仔細看有兩個函式， list_size 和 list_insert_before 。再跟據 macro 拆解程式碼， main 進行文字互動函式 test_suite 會配合 macro 進行一連串的測試 就是 test_list 代表的內容。用 gcc 生成 quiz1a.i 程式碼
參考雙倍指標，linked lisr 下方約八個段落 void append(int value, list_entry_t **head) 類似 list_insert_before ，後者的 p 相當於前者的 direct 變量，找到 before 停下來。注意迴圈用法，對應相反邏輯的條件。l 是指向 head 的開頭物件， item 是 new。可推算 AAAA, BBBB, CCCC。
雙倍指標，打包再打包的概念，包起 dereference 的內容。不管哪種都會讓串列變成樹。一個追趕的演算法，只是追和被追有沒有用 next 連在一起而已。下方有示意圖。[1]; [2]。或說，讓 *p 指標用來存取所有的 next，另外，prev 也可以用類似的操作。雙指標不是物件的指標，是走遍指標的指標變數。
for (p = &l->head; *p != before; p = &(*p)->next);
l->1 2 3 4 5 6 7 8
be->
*p->
*p->it
l->1 2 3 4 5 6 7 8
.->it
it->4
l->1 2 3 it 4 5 6 7 8
reset: *p := 3->next = it
reset: it := item->next = before
AAAA = &l->head
BBBB = before
CCCC = &(*p)->next
DDDD = item->next
都和教材 append 的程式碼相對應，只有 DDDD 是新增的。
解釋上方程式碼運作原理
善用 gcc -E quiz1a.c > quiz1a.i, gcc -g -o quiz1a quiz1a.c 處理錯誤。因為有兩個巨集，影響預編譯的結果。而且是合成影響。
main -> test_suite -> [my_run_test(test_list);] = do-while(0) -> [test()] = test_list()
說真的，一步到位我還是有點暈，但預處理器成功了。test_list 函式有三步驟。
測試開頭插入
像堆疊一樣，倒數插入 items[i] ，從 i=0 到 999，但都插入在開頭，所以從開頭會是 999 數回 0。在 list_insert_before 函式執行之前， list_reset 只是建立節點，沒有串聯成串列，所有節點都是孤單的節點。注意 do-while(0) 是假迴圈，因為不會重複執行，只剩下名字。理頭都是預留給可能的錯誤，去判斷並回傳錯誤。如果 test_list 結束，測試成功回傳 NULL。
其他兩段測試
其實仔細看，只有一個測試，最後一段是類似測試但實作。一次說明，這次插入尾端，從 0 到 9999 。檢察長度，和各節點數值。就結束了。輸出 測試成功， run 次數 1，一次成功，一杆進洞。那個巨集是模仿 assert 和 printf 實作的。最後的 return !!result; 注意是字串對布林變數的 1, 0 真假反轉。用 felo search 有詳細說明，容易邏輯死亡，小心服用。摘錄一段：
In C, the expression return !!NULL; involves the use of the logical NOT operator (!) applied twice to the NULL macro.
在現有的程式碼基礎上，撰寫合併排序操作
嘗試運用 macro 測試在 static list_t *list_setup 函式中，但 macro 會被預處理的 return 影響，就算另外新增變數儲存也沒辦法。這是設計的問題。我發現我函式呼叫，即使不傳回串列頭的指標，初始構建和測試仍然可行。於是修改回傳型別配合 macro ，也算是發現 macro 的一大缺點。
test point chosen
context:
#0 list_size (mylist=0x55555555bee0 <l>) at quiz1a.c:90
#1 0x000055555555532b in test_list () at quiz1a.c:55
#2 0x0000555555555422 in test_suite () at quiz1a.c:78
#3 0x00005555555554f5 in main () at quiz1a.c:107
當有錯務時，回報機制在位址的錯誤，沒有辦法存取到。應該說是分頁錯誤的問題， gdb 可以讀取錯誤訊息，但是被 printf 的錯誤訊息中斷了。也就是兩個都要回傳，但不能同時回傳。
517 ./stdio-common/vfprintf-internal.c: No such file or directory.
(gdb) frame 3
#3 0x000055555555569e in main () at merge.c:137
137 printf("ERROR: %s\n", result);
(gdb) p result
$7 = 0x5 <error: Cannot access memory at address 0x5>
(gdb) type result
Undefined command: "type". Try "help".
(gdb) ptype result
type = char *
(gdb) p *result
Cannot access memory at address 0x5
# second test
(gdb) where
#0 list_size (mylist=0x55555555bfb8 <lsa>) at merge.c:90
#1 0x000055555555526a in list_setup (l=0x55555555bfb8 <lsa>,
l_items=0x55555555bf00 <a_items>, length=5, array=0x7fffffffd7e0)
at merge.c:24
#2 0x0000555555555678 in main () at merge.c:135
(gdb) l
85 list_item_t *curr;
86 curr = mylist->head;
87 int count = 0;
88 while (curr) {
89 count++;
90 curr = curr->next;
91 }
92 return count;
93 }
94
(gdb) p count
$1 = 1
(gdb) p curr
$2 = (list_item_t *) 0x55555555bf00 <a_items>
(gdb) p curr->next
$3 = (struct list_item *) 0x55555555bf10 <a_items+16>
(gdb) p curr->next->next
$4 = (struct list_item *) 0x55555555bf20 <a_items+32>
(gdb) p *curr->next->next
$5 = {value = 5, next = 0x55555555bf30 <a_items+48>}
修改程式碼，前置處理器部分：
#define setup_run_test(test, l, l_items, length, array) \
do { \
char *message = test(l, l_items, length, array); \
tests_run++; \
if (message) \
return message; \
} while (0)
並對 list_setup 加上 return NULL，完成回傳值，如果通過測試的話。原來直接輸入參數就可以但一定要注意資料的層數，結構都必須是全域的。
_GI__IO_puts (str=0x5555555560ac "ALL TESTS of List PASSED") at ./libio/ioputs.c:33
33 ./libio/ioputs.c: No such file or directory.
(gdb)
35 in ./libio/ioputs.c
(gdb)
__strlen_avx2 () at ../sysdeps/x86_64/multiarch/strlen-avx2.S:50
50 ../sysdeps/x86_64/multiarch/strlen-avx2.S: No such file or directory.
如果 printf 正常的話，用 cont, step, until N, 跳過迴圈和一些步驟。完成偵錯程序。
quiz 2
The provided code snippet outlines a structure and function prototypes for managing memory allocation using a binary search tree (BST) approach. This method is often utilized in memory allocators to efficiently manage free memory blocks. Below is a detailed explanation of the code structure and its relevance to Linux memory management.
Code Structure Explanation
Structure Definition:
The block structure represents a memory block in the allocator. It contains:
size: The size of the memory block.
l and r: Pointers to the left and right children in the binary search tree, respectively. This allows the blocks to be organized in a way that facilitates efficient searching, insertion, and deletion.
Function Prototypes:
find_free_tree(block_t **root, block_t *target): This function is likely intended to locate a specific free block in the tree based on the target block.
find_predecessor_free_tree(block_t **root, block_t *node): This function may be designed to find the predecessor of a given node in the tree, which is useful for operations like deletion or rebalancing.
Memory Management:
The remove_free_tree(block_t **root, block_t *target) function is intended to remove a specified block from the free tree. The implementation details are not provided, but typically, this would involve finding the target block in the tree and adjusting pointers to maintain the BST properties.
This code implements a simple binary tree data structure specifically designed for managing "free" blocks of memory. Here's a higher-level overview of its functionality:
Tree Structure: The block_t structure represents a node in the binary tree. Each node contains the size of the block and pointers to its left and right children.
Finding Nodes: The find_free_tree function (not fully provided) is supposed to locate a node in the tree that matches a given target block.
Removing Nodes: The main function, remove_free_tree, is responsible for removing a specified block from the tree. It handles three cases:
If the node has both children, it finds its in-order predecessor (the largest node in the left subtree) to replace it.
If the node has only one child, it directly replaces the node with its child.
If the node is a leaf (no children), it sets the pointer to NULL, effectively removing it from the tree.
Assertions: Throughout the code, assertions are used to ensure that operations maintain the tree's integrity, checking that nodes are not incorrectly linked after removals.
Memory Management: After a block is removed from the tree, its left and right pointers are set to NULL to prevent dangling pointers.
Overall, this code is designed to efficiently manage dynamic memory blocks by maintaining a structured representation of free memory in a binary tree format.
Just BST remove
block_t **node_ptr = find_free_tree(root, target);
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
quiz 3
optimized quick sort; related to w2 quiz1
24q1a zone vax-r
week2
quiz 1
quick sort
linux
class_text
AAAA= list_first_entry
BBBB=list_del
CCCC=list_move
DDDD=list_move(
EEEE=list_splice_tail_init
FFFF=list_splice_init
ana_Mickey
Shan
quiz 2
開平方根運算 clz2()
試看
次重要 想想，clz fib kernel hw
#include <stdio.h>
#include <stdint.h>
#define clz32(x) clz2(x, 0) // Macro to start the count
// Filled in constants to get the desired output
static const int mask[] = {0, 8, 12, 16}; // GGGG = 16
static const int magic[] = {0, 1, 0, 5}; // HHHH = 0, IIII = 5
unsigned clz2(uint32_t x, int c) {
if (!x && !c)
return 32; // If both x and c are zero, return 32 (all bits are zero)
uint32_t upper = (x >> (16 >> c)); // Shift x to get upper bits
uint32_t lower = (x & (0xFFFF >> mask[c])); // Get lower bits using mask
if (c == 3) // JJJJ = 3
return upper ? magic[upper] : 4 + magic[lower]; // KKKK = 4
return upper ? clz2(upper, c + 1) : (16 >> c) + clz2(lower, c + 1); // LLLL = 1
}
int main() {
printf("clz32(0x00000F00) = %u\n", clz32(0x00000F00)); // Expected output: 20
printf("clz32(0x00000001) = %u\n", clz32(0x00000001)); // Expected output: 31
return 0;
}
Summary of Changes:
GGGG: Changed to 16 to allow the upper bits to shift correctly.
HHHH: Changed to 0 to handle cases appropriately in the magic array.
JJJJ: Changed to 3 for the branching logic.
KKKK: Set to 4 in the return statement calculation.
LLLL: Set to 1 to properly manage recursion depth handling.
With these constants, your function should now produce the expected output. Compile and run the code to see the results!
idea:
MMMM: ~1 (bitwise NOT of 1). This mask ensures that you keep everything but the least significant bit.
NNNN: Since we're shifting y right by one bit each iteration of the loop, this should be 1, which will effectively divide y by 2 on each iteration.
PPPP: For m in the loop, since you're halving it each time, you can set this to 1 as well, meaning you will also right shift m by one bit.
我重新回去看，<bitwise> ，比如題目註解有 set bit 我沒有注意是增加位元的意思。邏輯和直覺沒有連結，這樣子會不順，不行。有三種 mask ，再想想 magic 是什麼？ 並且實測發現 cond ? A : B 如果 cond 是一個變數，那變數為零的時候，判斷為真，執行A選項，注意是零為真，跟邏輯的判斷不一樣。
與朋友<jouae>討論後半開根號計算之後，結論是，這個來源於 linux_kernel ，他提到多次的減法和右移，模擬減法，我無法理解所以先測試結果。
Initial: x=25, y=0, m=16
Iteration 1: b=16, y=0, x≥b so x=9, y=16, m=4
Iteration 2: b=20, y=8, x<b so no change to x, m=1
Iteration 3: b=9, y=4, x=b so x=0, y=5, m=0
Result: 5
63 in binary is 111111, so clz64(63) = 64 - 6 = 58
shift = (64 - 1 - 58) & ~1 = 5 & ~1 = 4 (this ensures shift is even)
m = 1ULL << 4 = 16
Iteration 1: b=0+16=16, y=0>>1=0, 63≥16 so x=63-16=47, y=0+16=16, m=16>>2=4
Iteration 2: b=16+4=20, y=16>>1=8, 47≥20 so x=47-20=27, y=8+4=12, m=4>>2=1
Iteration 3: b=12+1=13, y=12>>1=6, 27≥13 so x=27-13=14, y=6+1=7, m=1>>2=0
Loop exits, return y=7
1048576 = 2^20, so clz64(1048576) = 64 - 21 = 43
shift = (64 - 1 - 43) & ~1 = 20 & ~1 = 20 (already even)
m = 1ULL << 20 = 1048576
Following through the algorithm, we should get 1024
但實測結果是 3和 1023 而不是 7和 1024 這說明這個演算法是 floor 不是 ceiling 。我又打 sqrti(65) = 8 確認了。
Commit 30493cc 說這個奇怪的算法是費曼流傳下來的，還留了一個維基的連結，嗯，這下有意思了。我用 blame 看到的。
quiz 3
two sum, Hash table. 22q1 w1qz1 freshLiver, Risheng, qwe661234, Destiny0504
AAAA = map->bits
AAA = n->next = first;
BBBB = map->bits
CCCC = first->pprev
BBB : n->pprev= &h->first;
DDDD = n->pprev next or pprev
EEEE = n->pprev;
