contributed by < Chialiang86
>
list_cut_position
搭配 get_middle
函數藉由找出 list 中間點來將 list 切成左右兩部份,而從 list_cut_position 的參數 (parameter) 可看出 node
為 list_head
型態,而 get_middle
的回傳值型態為 list_ele_t *
,因此 MMM
代換為 &get_middle(&q->list)->list
。list_merge_sort
來分別將剛剛切出的左右兩 list 進行排序。list_cut_position
函數1. 先將 head_from_first
指派為 head_from->next
,而 node
為 head_from
此環狀 list 依據 get_middle
算出的中間點。
2. 將 head_from->next
指派為 node->next
;再把 head_from->next->prev
指派為 head_from
。
3. head_to->prev
指派為 node
,node->next
指派為 head_to
, 再把 head_to->next
指派為 head_from_first
,head_to->next->prev
指派為 head_to
。
get_middle
函數list_for_each
為一個 function-liked macro ,主要是簡化走訪整個 list 的過程。low
和 fast
兩變數,可看見 slow
每次執行完一輪會變為 slow->next
;但 fast
會變成 fast->next->next
,由其變數命名可知一個移動的較慢,另一個較快,主要目的是利用當 fast
到達起始點時, slow
到達 list 的中間位置,並將中間位置的指標藉由 list_entry
找出並回傳。list_entry
是由 container_of
這個 macro 來實現container_of
的定義:__extension__
typeof
關鍵字為 GNU C extension,並非 c 原始的標準。__typeof__
為 alternate keyword ,根據 gcc.gnu.org 中對 alternate keyword 的解釋 :-ansi and the various -std options disable certain keywords. This causes trouble when you want to use GNU C extensions, or a general-purpose header file that should be usable by all programs, including ISO C programs. The keywords asm, typeof and inline are not available in programs compiled with -ansi or -std
-ansi
或 -std
時,某些關鍵字如 typeof
, asm
, inline
是無法編譯的,解決辦法是在關鍵字頭尾加上 __
(用 __typeof__
代替 typeof
) ,即 alternate keyword-pedantic
會造成使用 GNU C extensions 產生 warning 的狀況,可以在 __typeof__
之前加上 __extension__
來避免。struct
中成員所在記憶體空間的起始位址(即 struct 的起始位址)container_of(slow, list_ele_t, list)
當作範例slow
為 list_head
型態的指標, list
為 list_ele_t
其中一個成員的名稱(可以想成 slow
即為 list_ele_t
中 list
成員的實體),結果回傳 slow
所在的 list_ele_t
記憶體起始位置。struct list_head
已經具有完整 circular doubly-linked list 的結構,只要加上一個存放字串 (value) 的欄位即可時做出 list merge sort 。list_ele_t
擴充了原有的 struct list_head
結構,主要是加上了可以存字串的 value
欄位list_ele_t
已經足夠去實做 list sort ),並且把 list_ele_t
中的 struct list_head list
放到第一個欄位,這樣有一個非常大的好處是,如果要進行走訪 list 的動作,只要直接把 list_ele_t *
強制轉型成 struct list_head *
即可,因為兩個指標指向的是同一塊記憶體位址,不需要用 contain_of
這個 macro
來計算 list
成員的相對記憶體位置,不但精簡了程式碼提高了可讀性,也省去了計算相對位置所使用的時間。q
的型態改變成 struct list_head *
,其實整個 q
的 list 只有 q
自己是真正屬於 struct list_head *
,其他的節點是有 value
成員的 list_ele_t *
,因此 q
本身可以算是一個 dummy node ,只有指向 list 功能。q_insert_head
函數,以下程式碼第 17 行可以看到,lsit_ele_t *
型態的新節點 newh
被強制轉形成 struct list_head *
加到 q->next
中,雖然兩者型態不同,但因為指向的是同一塊記憶體空間,因此省去許多計算相對位置,或額外設計 struct 來操作記憶體空間的成本。q_free
函數更改如下,傳進去的 type 雖然為 struct list_head *
,但走訪整條 list 要先轉型成 list_ele_t *
才能正確釋放記憶體。print
函數來印出完整的 listmain
修改gcc -o q1 q1.c
結果 (input 為 cities.txt)N
為 30(0b11110) 或 20(0b10100),為求小於等於 N
之二的冪,答案皆為 16(0b10000) ,觀察發現其實函數的輸出只跟 N
的二進制之 MSB(most signicant bit) 有關,輸入的值二進制最左邊的 1 才是關鍵。N
為 : 0b0010001110001101N |= N >> 1
: 0b0011001111001111N |= N >> 2
: 0b0011111111111111N |= N >> 4
: 0b0011111111001111N |= N >> 8
: 0b0011111111111111(N + 1)
: 0b01000000000000000(N + 1) >> 1
: 0b00100000000000000>>
和 |
運算子來將 MSB 以後的值都變成 1 ,再 +1 進位到產生"大於 N
之最大的二的冪"並右移一位來得到答案。N
之最小的二的冪。|
,&
,>>
,<<
,bitmask 或數字的二進制表示法等,並了解函數操作其中的意義。bitcpy
函數:count
為總共要複製的 bit 數,而 bitsize
為 while 迴圈進行一輪所複製的 bit 數 (bitsize <= 8),而 data
為一個從 _src
複製的 buffer ,經過偏移量的處理,要把正確的資料複製給 dest
, 大小為一個 byte。read_lhs
(write_lhs
) 和 read_rhs
(write_rhs
) 主要是操作從一個 byte 的角度處理 bit-offset 的變數,因為記憶體是以 byte 當作單位,因此 bit level 需要充分善用 c 中 bitwise 的特性,也是 bitcpy
最關鍵的變數之一。read_lhs
為 byte 中的左偏移量; read_rhs
為右偏移量,兩者相加為 8 (1 byte 為 8 bits)。
假設 source
指標所指的 byte 的值為 00101110, read_lhs=3
, read_rhs=5
上述程式碼執行之後的狀況
read_lhs
, read_rhs
對 data
的表示:read_lhs > 0
,則必須從 byte 由左往右數第 read_lhs + 1 個 bit 開始讀取,相當於是先把 data
左移 read_lhs
個 bit。read_rhs
代表 byte 中右邊的 bit 數,因此若 bitsize
> read_rhs
,則此回合會跨 byte 讀取資料至 data
,因此要借用剛剛 source++
後的位址,進行 data |= (*source >> read_rhs)
最後再依據 bitsize
和 read_mask
來將要複製的 bit 進行 &
運算
bitsize = 7
data
結果變為 01110100類似的原理,觀察 13 到 24 行
write_lhs=5
, write_rhs=3
, bitsize=7
, data=01101100
if
區塊的程式碼主要適用於要跨兩個 byte 把資料寫入 dest
中
(original & mask) | (data >> write_lhs)
這段程式碼是將 data
中的資料寫入 dest
(此時指向左半邊的 byte),例如 mask = 0b11111000 , original & mask
相當於先將 original
所指向的 byte 的右邊 3 個 bits 做清空的動作,因為會跨 byte 寫入,因此清空的 3 個 bit 之後會被寫入的資料取代。original = *dest & write_mask[bitsize - write_rhs]
為先將 dest
(此時指向右半邊的 byte) 左邊進行清空的動作。例如 write_rhs=3
; bitsize=7
代表 dest
左邊兩個 bit 會被寫入(因為左邊 byte 中右邊 3 個 bits 被寫入, 7 - 3 = 4 剩下 4 bit 給右邊 byte)。*dest = original | (data << write_rhs)
這行是將 data 複製到 dest
中,由於 data
的左邊 write_lhs
個 bit 已複製完成,故現在把剩下的 bit 資料複製給 dest
。else
區塊成處理是處理未跨 byte 資料寫入至 dest
mask |= write_mask[write_lhs + bitsize]
的目的為將 dest
左邊及右邊不需要被寫入的 bit 保留,如 wrtie_lhs = 5
,mask
原先為 0b11111000
, bitsize = 2
, 操作後 mask = 0b11111001
, 這個 mask
在下一行和 original
做 &
運算,代表 original 只有第 6, 7 兩個會被寫入的 bit 位置被 mask 清空,而把清空過的 original
和 (data >> write_lhs)
(即右移 write_lhs
個 bit 的資料)進行 |
運算,成功把資料複製進 dest
中。