sysprog
      • Sharing URL Link copied
      • /edit
      • View mode
        • Edit mode
        • View mode
        • Book mode
        • Slide mode
        Edit mode View mode Book mode Slide mode
      • Customize slides
      • Note Permission
      • Read
        • Owners
        • Signed-in users
        • Everyone
        Owners Signed-in users Everyone
      • Write
        • Owners
        • Signed-in users
        • Everyone
        Owners Signed-in users Everyone
      • Engagement control Commenting, Suggest edit, Emoji Reply
      • Invitee
      • No invitee
    • Publish Note

      Publish Note

      Everyone on the web can find and read all notes of this public team.
      Once published, notes can be searched and viewed by anyone online.
      See published notes
      Please check the box to agree to the Community Guidelines.
    • Commenting
      Permission
      Disabled Forbidden Owners Signed-in users Everyone
    • Enable
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
      • Everyone
    • Suggest edit
      Permission
      Disabled Forbidden Owners Signed-in users Everyone
    • Enable
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
    • Emoji Reply
    • Enable
    • Versions and GitHub Sync
    • Note settings
    • Engagement control
    • Transfer ownership
    • Delete this note
    • Insert from template
    • Import from
      • Dropbox
      • Google Drive
      • Gist
      • Clipboard
    • Export to
      • Dropbox
      • Google Drive
      • Gist
    • Download
      • Markdown
      • HTML
      • Raw HTML
Menu Note settings Sharing URL Help
Menu
Options
Versions and GitHub Sync Engagement control Transfer ownership Delete this note
Import from
Dropbox Google Drive Gist Clipboard
Export to
Dropbox Google Drive Gist
Download
Markdown HTML Raw HTML
Back
Sharing URL Link copied
/edit
View mode
  • Edit mode
  • View mode
  • Book mode
  • Slide mode
Edit mode View mode Book mode Slide mode
Customize slides
Note Permission
Read
Owners
  • Owners
  • Signed-in users
  • Everyone
Owners Signed-in users Everyone
Write
Owners
  • Owners
  • Signed-in users
  • Everyone
Owners Signed-in users Everyone
Engagement control Commenting, Suggest edit, Emoji Reply
Invitee
No invitee
Publish Note

Publish Note

Everyone on the web can find and read all notes of this public team.
Once published, notes can be searched and viewed by anyone online.
See published notes
Please check the box to agree to the Community Guidelines.
Engagement control
Commenting
Permission
Disabled Forbidden Owners Signed-in users Everyone
Enable
Permission
  • Forbidden
  • Owners
  • Signed-in users
  • Everyone
Suggest edit
Permission
Disabled Forbidden Owners Signed-in users Everyone
Enable
Permission
  • Forbidden
  • Owners
  • Signed-in users
Emoji Reply
Enable
Import from Dropbox Google Drive Gist Clipboard
   owned this note    owned this note      
Published Linked with GitHub
1
Subscribed
  • Any changes
    Be notified of any changes
  • Mention me
    Be notified of mention me
  • Unsubscribe
Subscribe
# 2024-02-{20,27} 問答簡記 ## 不同長度的 linked list 是否可以合併? > [jouae](https://github.com/jouae) 從 [案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 延伸,我們將討論文中程式碼對不同長度的單向鏈結串列可否做合併?可以的話怎麼做到的? ### 回顧 [C99 規格書(ISO/IEC 9899:TC3)](https://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf) * 6.5.13 Logical AND operator >The && operator shall yield 1 if both of its operands compare unequal to 0; otherwise, it yields 0. The result has type *int*. 這邊要注意的是經由 && 邏輯運算子後,得到的型態是 *int* * 6.8.5 Iteration statements >$while$ $($ $expression$ $)$ statement $do$ statement $while$ $($ $expression$ $)$ ; $for$ $($ $expression_{opt}$ ; $expression_{opt}$ ; $expression_{opt}$ $)$ statement $for$ $($ $declaration$ $expression_{opt}$ ; $expression_{opt}$ $)$ statement C99規格書中描述 controlling expression 的限制為 >The controlling expression of an iteration statement shall have *scalar type*. 這邊 *scalar type* 根據 C99 6.2.5 Type 第 21 項 (page 36) 定義為 >Arithmetic types and pointer types are collectively called *scalar types*. Array and structure types are collectively called *aggregate types*. 而 Arithmetic types 在同個 section 下,第 18 項定義為 >Integer and floating types are collectively called arithmetic types. * 有意思的是在[C++11規格書](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf)中, 5.14 Logical AND operator 下的規定是 `bool` 型態 >The && operator groups left-to-right. The operands are both contextually converted to type bool. 可以看到文中 `mergeTwoLists(*L1, *L2)` 輸入只有兩個 `ListNode` 結構體的指標。而內部實作的部分則由 `while(L1 && L2)` 實踐,所以當兩者皆非 null pointer 時,比較完大小順序就可以將兩者合併。 考慮其控制表達式的否命題即為: ``` L1 or L2 is a null pointer ``` 說明停止條件為 L1 或是 L2 指向 null。兩者同時指向 null 的情形只會發生在傳入函式的 L1 和 L2 皆是 null pointer 。 以下圖例簡易說明兩不同長度的單向串列是如何合併的,`L1=[4, 5]` , `L2=[1, 6, 7]`, `ptr` 就像針線的針,會依據節點數值大小把針頭(指標)穿過比較後的節點: ```graphviz digraph structs { node[shape=record] rankdir=LR ptr [label="<data> ptr"] L2_a [label="<data> 1|<header> L2"]; L2_b [label="<data> 6"]; L2_c [label="<data> 7"]; L1_a [label="<data> 4|<header> L1"]; L1_b [label="<data> 5"]; L1_a -> L1_b -> null1; L2_a -> L2_b -> L2_c -> null2; } ``` 比較 L1 和 L2 大小。 `ptr->next` 指向 4 , `ptr` 串接後的數列為 `[4]` ```graphviz digraph structs { node[shape=record] rankdir=LR ptr [label="<data> ptr"] L2_a [label="<data> 1|<header> L2"]; L2_b [label="<data> 6"]; L2_c [label="<data> 7"]; L1_a [label="<data> 4"]; L1_b [label="<data> 5|<header> L1"]; ptr->L1_a -> L1_b -> null1; L2_a -> L2_b -> L2_c -> null2; } ``` 比較 L1 和 L2 大小。 `ptr->next` 指向 5 , `ptr` 串接後的數列為 `[4, 5]` ```graphviz digraph structs { node[shape=record] rankdir=LR ptr [label="<data> ptr"] L2_a [label="<data> 1|<header> L2"]; L2_b [label="<data> 6"]; L2_c [label="<data> 7"]; L1_a [label="<data> 4"]; L1_b [label="<data> 5"]; null1 [label="<data> null1|<header> L1"] L1_a -> L1_b -> null1; L2_a -> L2_b -> L2_c -> null2; ptr -> L1_a } ``` 跳出迴圈,判斷 `ptr->next` 該接到哪裡。由於 L1 目前為 null , `ptr->next` 指向 L2 串接後的數列為 `[4, 5, 1, 6, 7]` 合併完成。 ## 能否使用 linked list 去實作 quicksort > joec1368 針對 Linux 核心的場景,強調是否可以達成 [in-place algorithm](https://en.wikipedia.org/wiki/In-place_algorithm) ## 何時用到 bubble sort 或 insertion sort? > wilicw * 已經接近排序好的 list。 * 任務優先權沒有顯著變化 ## Linus 提到的 bad taste [The mind behind Linux | Linus Torvalds | TED](https://youtu.be/o8NPllzkFhE?feature=shared&t=870) 中的程式碼為何是 bad taste? * 避免 `head` 為 `null`。 * 使用 indirect pointer 來減少特殊案例的處理 ## 排序程式碼練習 > c24094031@gs.ncku.edu.tw 考慮以下程式碼,使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) ```c #include <stddef.h> #include <stdint.h> #include "list.h" struct listitem { uint16_t i; struct list_head list; }; static inline int cmpint(const void *p1, const void *p2) { const uint16_t *i1 = (const uint16_t *) p1; const uint16_t *i2 = (const uint16_t *) p2; return *i1 - *i2; } static void list_insert_sorted(struct listitem *entry, struct list_head *head) { struct listitem *item = NULL; if (list_empty(head)) { list_add(&entry->list, head); return; } list_for_each_entry (item, head, list) { if (cmpint(&entry->i, &item->i) < 0) { list_add_tail(&entry->list, &item->list); return; } } list_add_tail(&entry->list, head); } static void list_insertsort(struct list_head *head) { struct list_head list_unsorted; struct listitem *item = NULL, *is = NULL; INIT_LIST_HEAD(&list_unsorted); list_splice_init(head, &list_unsorted); /* Put your code here */ } ``` > :warning: 上方程式碼不完整 ## 為什麼不用在環狀鏈結串列中使用 swap 就可以做到交換? > [jouae](https://github.com/jouae) 最簡單實作的 swap 如下: ```c void swap(int *a, int *b) { int tmp; tmp = *a; *a = *b; *a = tmp; } ``` 可以看到上述的部分需要額外一個變數 `tmp` 來暫存交換的值。 而在單向鏈結串列中,不用做到額外變數,只要使用間接指標( indirect pointer )。參見[你所不知道的 C 語言: linked list 和非連續記憶體——Merge Sort 的實作](https://hackmd.io/@owlfox/BJkrdnExL/https%3A%2F%2Fhackmd.io%2Fs%2FSkE33UTHf#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C): ```c struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) { struct ListNode *head = NULL, **ptr = &head, **node; for (node = NULL; L1 && L2; *node = (*node)->next) { node = (L1->val < L2->val) ? &L1: &L2; *ptr = *node; ptr = &(*ptr)->next; } *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2); return head; } ``` ## merge sort 實作何處可用 `list_splice`? > [a1157857220](https://github.com/a1157857220) ## Timsort 什麼時候用到 `list_splice`? > [jouae](https://github.com/jouae) 在 Python 官方文件中 listsort.txt 紀錄這個由 Peters, Tim 開發的 Timsort 跟實驗內容,以下摘入自開頭片段: > This describes an adaptive, stable, natural mergesort, modestly called timsort. 在 Timsort 中,討論的基本單位稱作為 run ,為一非遞減或是嚴格遞減的數列。例如: ```cpp [60, 50, 40, 1, 2, 3] ``` 可以拆解成兩個 run: ```cpp run 1: [60, 50, 40] run 2: [1, 2, 3] ``` 而向上述原始數列就已經有排序的子數列,這些子數列稱作為 natural run ,而其餘沒有排序過的元素,會先蒐集起來至一定數量後,藉由插入排序( insert sort )來排序成為一個 run 。同時為避免比較次數過多, Tim 在實作的過程中有限制每個 run 的上限為 64。 在過往學員 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-timsort#Timsort-%E9%81%8B%E4%BD%9C%E6%96%B9%E5%BC%8F) 紀錄中,詳述 Timsort 流程。 回頭來看 `list_splice(*list, *head)`,由兩個輸入組成 `*list` 跟 `*head` ,兩者皆是 `list_head` 結構體的指標,作用為將 `list` 這個節點包含其後續節點,繫( splice )於 `head` 之後。所以在進行合併各個 run 的過程中, `list_splice` 就在此時上場。 在 Linux list_sort.c 中合併的實踐是由 `*merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)` 達成。由於並非環狀鏈結串列的合併,跟我們預期 `list_splice` 的運作不一樣, `list_splice` 針對環狀結構操作。 **注意**:在此的 `*a` 和 `*b` 為 null-terminated singly-linked list 。詳見原始碼中 `list_sort()` 的部分。 在 `merge_final()` 部分中,則還原了原本串列的環狀結構。 在函數的一開始先把單向串列改成雙向串列 ```c // 將 a 鏈結在 tail 之後 // 並將 a 的前一個節點指向 tail 形成 doubly linked tail->next = a; a->prev = tail; // 更新 tail 位置為 a tail = a; a = a->next; ``` 函式的最後將雙向串列頭尾相連形成環狀結構 ```c /* And the final links to make a circular doubly-linked list */ tail->next = head; head->prev = tail; ``` 整個過程簡化的話,就是 `list_splice` 的功能。 * [Jserv. 你所不知道的 C 語言: linked list 和非連續記憶體——Linux 核心的 list_sort 實作](https://hackmd.io/@sysprog/c-linked-list#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-list_sort-%E5%AF%A6%E4%BD%9C) * [visitorckw. Linux 核心專題: 改進 `lib/list_sort.c`](https://hackmd.io/@sysprog/Hy5hmaKBh) * [yanjiew1. Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort) * [yanjiew1. linux23q1-timsort](https://github.com/yanjiew1/linux23q1-timsort/blob/main/timsort.c) * [Peters, Tim. listsort.txt](https://svn.python.org/projects/python/trunk/Objects/listsort.txt) * [Peters, Tim. [Python-Dev] Sorting. Python Developers Mailinglist.](https://mail.python.org/pipermail/python-dev/2002-July/026837.html) ## 為何 `list.h` 選定 0x00100100 與 0x00200200 作為無效的地址? > [Jimmy01240397](https://github.com/Jimmy01240397) 我在做 `git log | grep <address>` 之類的操作後依然沒有詳細說明。只知道該 address 第一次出現是在 commit `9a69abf80edf2ea0dac058cab156879d29362788` "menuconfig: Add "breadcrumbs" navigation aid" 的位置 ```c static inline void list_del(struct list_head *node) { struct list_head *next = node->next; struct list_head *prev = node->prev; next->prev = prev; prev->next = next; #ifdef LIST_POISONING node->prev = (struct list_head *) (0x00100100); node->next = (struct list_head *) (0x00200200); #endif } ``` [linux/poison.h](https://github.com/torvalds/linux/blob/master/include/linux/poison.h) 的註解: > These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries. 當 `list_del` 執行時,會將節點的的 prev 和 next 指向一個特定的地址,當存取到該地址時,會觸發 [page fault](https://en.wikipedia.org/wiki/Page_fault)。 在《[Linux Device Drivers 3/e](https://lwn.net/Kernel/LDD3/)》第四章 Debugging Techniques 的引言提到,Linux 核心的程式碼不易在除錯器中運作、錯誤也不易重現,不過一旦引發錯誤時,可能會讓整個系統崩潰,而造成錯誤的證據則隨之消失。 除錯的的其一手法就是將這種有毒 (poison) 的值設在使用前後,當該數值變更時,我們就會知道非預期的狀況發生。 > 諺語: One man's meat is another man's poison 有了這樣的設計,我們便可在除錯時知道 : 若 `node->next` 與 `node->prev` 分別指向 `LIST_POISON1` 與 `LIST_POISON2` 的話,就代表發生 use-after-free 的情況,像是 [lib/list_debug.c](https://github.com/torvalds/linux/blob/master/lib/list_debug.c) 便是 Linux 核心中對應的除錯程式碼。 若無 `LIST_POISONING` 的設計,在 `list_del()` 時將 `node->next` 和 `node->prev` 都指向 NULL,除錯階段就無法得知此時的 NULL 代表的是 uninitialized 抑或被釋放後才指派的。 至於不直接釋放節點的原因,可參閱 [Kernel Self-Protection](https://www.kernel.org/doc/html/latest/security/self-protection.html) 中 Memory poisoning 的部份得知: > When releasing memory, it is best to poison the contents, to **<font color="#000">avoid reuse attacks that rely on the old contents of memory</font>**. E.g., clear stack on a syscall return (`CONFIG_GCC_PLUGIN_STACKLEAK`), wipe heap memory on a free. This frustrates many uninitialized variable attacks, stack content exposures, heap content exposures, and use-after-free attacks. ## [2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)第 1 題 > [weihsinyeh](https://github.com/weihsinyeh) 建立二元樹需要有透過得知中序(in-order)與前序 (pre-order) 或是後序 (post-order)才能具體說明一個獨一無二的二元樹的原因說明舉例如下。 前序是 `[A B C]` 透過前序知道 `A` 是 中間的那個點,但卻無法透過前序知道 `B` `C` 相對於A的左邊還是右邊。 因此產生的二元樹可能如下中序分別是 `[B C A]`, `[B A C]` , `[A B C]` ``` A A A / / \ \ B B C B \ \ C C (1) (2) (3) ``` 第一個樹:由中序知道 `A` 是 中間的那個點,`B` `C` 相對於`A`在左邊。所以都在 `A` 的左子樹中。 第二個樹:由中序知道 `A` 是 中間的那個點,`B` 相對於 `A` 在左邊,所以在 `A` 的左子樹中。`C` 相對於`A`在右邊,所以在 `A` 的右子樹中。 第三個樹:由中序知道 `A` 是 中間的那個點,`B` `C` 相對於`A`在右邊。所以都在 `A` 的右子樹中。 所以 DFS 中的實作是透過 preorder 會藉由 `find` 找到`preorder[pre_low]` 在`inorder`中的位置 `idx`。 由圖得知在 `idx` 左邊的都會被放到左子樹,在`idx`右邊的都會被放到右子樹。 因此對應到左子樹的在中序涵蓋的範圍 : `[in_low,idx-1]`,右子樹在中序涵蓋的範圍 : `[idx+1,in_high]` ```c tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size); tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size); ``` 而觀察剛剛的前序可以知道他的分佈的規則就是 `[中點 左子樹 右子樹]`,從這裡就可以看到只要知道左子樹有多少個,右子樹有多少個,就可以知道在前序的範圍了。 而因為 `pre_low` 是中點 左子樹在前序的涵蓋範圍 : `[pre_low + 1, pre_low + (idx - in_low)]` 其實就是`pre_low`往後左子樹的在中序涵蓋的範圍 : `[in_low,idx-1]` 右子樹在前序的涵蓋範圍 : `[pre_high - (in_high - idx - 1), pre_high]` 其實就是`pre_high`往前右子樹的在中序涵蓋的範圍 : `[idx+1,in_high]` 也因此從這樣的分析其實知道如果題目提供的只有後序與中序,我只要從後序的最後一個往前讀。 改變範圍即可因為後序的分佈是 `[左子樹 右子樹 中點]`,`post_high`是中點。 所以左子樹在後序的涵蓋範圍:`[post_low, post_low + (idx - 1 - in_low)]` 右子樹在後序的涵蓋範圍:`[post_high - 1 - (in_high - (idx+1)) , post_high-1]` 所以這樣也就明白中序在建立二元樹中缺一不可的角色,而前序與後序則是可以只挑其中一個。 而 `find` 函式則是用 hash table 去紀錄`in-order`的位置而已,可換成其他資料結構來實作。

Import from clipboard

Advanced permission required

Your current role can only read. Ask the system administrator to acquire write and comment permission.

This team is disabled

Sorry, this team is disabled. You can't edit this note.

This note is locked

Sorry, only owner can edit this note.

Reach the limit

Sorry, you've reached the max length this note can be.
Please reduce the content or divide it to more notes, thank you!

Import from Gist

Import from Snippet

or

Export to Snippet

Are you sure?

Do you really want to delete this note?
All users will lose their connection.

Create a note from template

Create a note from template

Oops...
This template is not available.
Upgrade
All
  • All
  • Team
No template found.

Create custom template

Upgrade

Delete template

Do you really want to delete this template?
Turn this template into a regular note and keep its content, versions, and comments.

This page need refresh

You have an incompatible client version.
Refresh to update.
New version available!
See releases notes here
Refresh to enjoy new features.
Your user state has changed.
Refresh to load new user state.

Sign in

Forgot password

or

By clicking below, you agree to our terms of service.

Sign in via Facebook Sign in via Twitter Sign in via GitHub Sign in via Dropbox Sign in with Wallet
Wallet ( )
Connect another wallet

New to HackMD? Sign up

Help

  • English
  • 中文
  • Français
  • Deutsch
  • 日本語
  • Español
  • Català
  • Ελληνικά
  • Português
  • italiano
  • Türkçe
  • Русский
  • Nederlands
  • hrvatski jezik
  • język polski
  • Українська
  • हिन्दी
  • svenska
  • Esperanto
  • dansk

Documents

Help & Tutorial

How to use Book mode

How to use Slide mode

API Docs

Edit in VSCode

Install browser extension

Get in Touch

Feedback

Discord

Send us email

Resources

Releases

Pricing

Blog

Policy

Terms

Privacy

Cheatsheet

Syntax Example Reference
# Header Header 基本排版
- Unordered List
  • Unordered List
1. Ordered List
  1. Ordered List
- [ ] Todo List
  • Todo List
> Blockquote
Blockquote
**Bold font** Bold font
*Italics font* Italics font
~~Strikethrough~~ Strikethrough
19^th^ 19th
H~2~O H2O
++Inserted text++ Inserted text
==Marked text== Marked text
[link text](https:// "title") Link
![image alt](https:// "title") Image
`Code` Code 在筆記中貼入程式碼
```javascript
var i = 0;
```
var i = 0;
:smile: :smile: Emoji list
{%youtube youtube_id %} Externals
$L^aT_eX$ LaTeX
:::info
This is a alert area.
:::

This is a alert area.

Versions and GitHub Sync
Upgrade to Prime Plan

  • Edit version name
  • Delete

revision author avatar     named on  

More Less

No updates to save
Compare
    Choose a version
    No search result
    Version not found
Sign in to link this note to GitHub
Learn more
This note is not linked with GitHub
 

Feedback

Submission failed, please try again

Thanks for your support.

On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?

Please give us some advice and help us improve HackMD.

 

Thanks for your feedback

Remove version name

Do you want to remove this version name and description?

Transfer ownership

Transfer to
    Warning: is a public team. If you transfer note to this team, everyone on the web can find and read this note.

      Link with GitHub

      Please authorize HackMD on GitHub
      • Please sign in to GitHub and install the HackMD app on your GitHub repo.
      • HackMD links with GitHub through a GitHub App. You can choose which repo to install our App.
      Learn more  Sign in to GitHub

      Push the note to GitHub Push to GitHub Pull a file from GitHub

        Authorize again
       

      Choose which file to push to

      Select repo
      Refresh Authorize more repos
      Select branch
      Select file
      Select branch
      Choose version(s) to push
      • Save a new version and push
      • Choose from existing versions
      Include title and tags
      Available push count

      Upgrade

      Pull from GitHub

       
      File from GitHub
      File from HackMD

      GitHub Link Settings

      File linked

      Linked by
      File path
      Last synced branch
      Available push count

      Upgrade

      Danger Zone

      Unlink
      You will no longer receive notification when GitHub file changes after unlink.

      Syncing

      Push failed

      Push successfully