contributed by < Hsuhaoxiang >
重新回答第 2 周測驗題
union
將不同類型的資料放在同一記憶體上,其大小為最大的成員所佔的空間xs
中每個成員皆小於等於 16 byte sizeof(xs) = 16
char *data
為存放短字串的地方struct
中記錄了 xs
是長短字串的相關資訊, filler[15]
佔用15 byte 是為了不讓後面存放資訊位置的地方改寫到短字串 data
的內容。space_left
用了 struct
中的 bit-field
佔 4 bit ,is_ptr
, flag
等共佔 1 bytespace_left
不紀錄長度,而是紀錄「最大短字串長度減去現在長度」,如此一來當短字串放滿 15 byte 後,最後的 space_left
、 is_ptr
、 flag
剛好會都是 0 也就是 \0
不影響短字串的 terminator,沒想到字串結尾的 1 個 byte 藉由 union
以及 bit-field
還能存下這些資訊!struct
就是存放長字串的地方了 char* ptr
佔 8 個 byte , size 放的是長字串所佔空間,扣掉 null character
就會都是 2 的指數次方減一,而 capacity
則是分配的記憶體大小裡面存的值為對數,所以還要再做指數運算才算得出大小,且保留最後 4-bit 讓 is_ptr
, flag
的值不會被動到。程式列表應該適度分段,從功能探討起,連帶提及答題思維
好的
xs_new
判斷要建立的字串是長字串還是短字串做出對應的操作xs_new
區分長短字串的判斷與題目 (len > AAA)
相同,其中 len = strlen(p) + 1
答案為
(c) 16
xs_trim
用來去除 x
的頭尾在 trimset
出現的字元set_bit(x)
與 check_bit(x)
這兩個 macro 對字串頭尾進行切割xs_trim
是負責去掉頭尾多餘的字串,如果本來是長字串,也就是使用 ptr
的字串如果變成小或等於 16 個字串還是會用 ptr
而不是 data[16]
, 並且進行 xs_concat
時會因為 capacity
讓串接後的字串大小讓串接後的字串大小有問題,必須要再修改!uint8_t mask[BBB] = {0}
中 mask 用於下兩行的 macro check_bit(byte)
與 set_bit(byte)
(uint8_t) byte / 8
最大為 31答案為
(a) 32
set_bit()
與 check_bit()
來找出需要被修剪的字元,因此 mask[index]
中放的是 trimset
字元的 ascii code % 8 之後的值,index 為 ascii code 除以 8。check_bit()
所要做的運算是 &
答案為
(b) &
xs_tmp
這個 macro
我其實我不知道為何需要特別去檢查 xs_new
中的 x
有沒有小或等於 16 個字元?這樣豈不是讓 xs
一開始只能初始為短字串再慢慢合併上去。16 這個數字可變更,但取決於結構體的規劃,請對照看 (https://github.com/facebook/folly/blob/master/folly/FBString.h),並參照 Cache 原理和實際影響,考慮到 cache line 空間。
prefix
, suffix
字串到 string 的前後, capacity
不夠就使用 xs_grow()
參考 folly::fbstring 中使用 CoW 的技巧
RefCounted
有兩個成員refCount
為多少 xs
長字串正在參考原本的字串,只有用 cow_copy()
時數字才會增加data_
為字串開頭的記憶體位置,也是存放長字串的地方宣告成長度為 1 的陣列讓 data_
表示為記憶體位置而不是資料,我有嘗試過把 data_[1]
換成 char *data
但最後會有問題,還沒找出原因,不過用這種宣告方式是更省記憶體的,比起我省下了一個指標的空間。refcounted
這名稱可縮減為 refcnt
,對應 typedef 後為 refcnt_t
。上方的 refCount_
可改為 val
或 cnt
,因為實質操作存取次數多,簡潔至上
已改
struct
中 data_
位元組偏移值refcnt_t
指標cnt
也就是他被參考的次數cnt
加 1cnt
減 1 , 如果沒有其他指標參考這個 struct
則釋放記憶體xs_new
, xs_grow
), 改寫長字串 ( xs_concat
) 時分配記憶體給 refcn_t
並將回傳 data_
這個存放字串的記憶體為cow_cpy
之後refcnt會加 1 , 將 copy 來的 string 跟 prefix
, suffix
進行串接表示發生改寫需要進行真正的「複製」,所以refcnt必須減 1直接對字串進行改動還沒考慮 cow