# 2021q1 Homework3 (quiz3)
contributed by < `jhan1998` >
## 解釋程式碼運作
先從 union 看起：
```c
typedef union {
/* allow strings up to 15 bytes to stay on the stack
* use the last byte as a null terminator and to store flags
* much like fbstring:
* https://github.com/facebook/folly/blob/master/folly/docs/FBString.md
*/
char data[16];
struct {
uint8_t filler[15],
/* how many free bytes in this stack allocated string
* same idea as fbstring
*/
space_left : 4,
/* if it is on heap, set to 1 */
is_ptr : 1, flag1 : 1, flag2 : 1, flag3 : 1;
};
/* heap allocated */
struct {
char *ptr;
/* supports strings up to 2^54 - 1 bytes */
size_t size : 54,
/* capacity is always a power of 2 (unsigned)-1 */
capacity : 6;
/* the last 4 bits are important flags */
};
} xs;
```
> An implementation may allocate any addressable storage unit large enough to hold a bitfield. If enough space remains, a bit-field that immediately follows another bit-field in a structure shall be packed into adjacent bits of the same unit.
從 C 語言規格書上對於 bit-field 空間配置的描述來看我們可以知道，鄰近相同 type 的 bit-filed 會往前補，所以在這個 union 裡配置的空間就是 16 bytes。
另外由於空間是共用的，所以下面的 struct 最後會剩下 4 個 bits，因此 `is_ptr : 1, flag1 : 1, flag2 : 1, flag3 : 1` 這些變數不會被複寫，所以可以用來記錄字串資訊。
實際儲存狀況如下：
```c
xs *xs_new(xs *x, const void *p)
{
*x = xs_literal_empty();
size_t len = strlen(p) + 1;
if (len > 16) {
x->capacity = ilog2(len) + 1;
x->size = len - 1;
x->is_ptr = true;
xs_allocate_data(x, x->size, 0);
memcpy(xs_data(x), p, len);
} else {
memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);
}
return x;
}
```
* 小字串：長度小於等於 15 的情況下可以直接存在 stack 上，所以會把資料 copy 到 data 裡面，會有額外 4 個 bits 讓儲存剩下的長度。在 `*xs_new()` 裡的配置為：
```c
memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);
```
* 中字串：長度介於 16 到 LARGE_STRING_LEN 256 之間，這時候會在 heap 配置空間給字串，capacity 的計算為 ilog2(len) + 1 ，其中 `ilog2()` 為：
```c
/* lowerbound (floor log2) */
static inline int ilog2(uint32_t n) { return 32 - __builtin_clz(n) - 1; }
```
`__builtin_clz()` 我們可以知道 MSB 往右數遇到的第一個 1 之前所有 0 的數量，因此要計算 floor log2 的話，再減 1 就是我們要的值。
**e.g.**
$10_{10} = 00000000000000000000000000001010_2$
$32-28 - 1 = 3$
$2^3 = 9$
最後 capacity 再加 1，之後配置的空間就會是大於 len 的最小 2 的冪。
`is_ptr` 也會被設成 true，最後在 `xs_allocate_data()` 中會判斷，是否為大字串，不是的話會直接配置空間交給 `ptr` 儲存，另外由於是新字串，所以 reallocate 設為 0。
```c
if (len < LARGE_STRING_LEN) {
x->ptr = reallocate ? realloc(x->ptr, (size_t) 1 << x->capacity)
: malloc((size_t) 1 << x->capacity);
return;
}
```
* 大字串：基本上跟中字串一樣，唯一要注意的是在 `xs_allocate_data()` 裡，當被判斷為大字串時，會多配置一個 4 bytes (一個 int 大小)的空間當作 reference count 的儲存空間。
```c
x->is_large_string = 1;
/* The extra 4 bytes are used to store the reference count */
x->ptr = reallocate ? realloc(x->ptr, (size_t)(1 << x->capacity) + 4)
: malloc((size_t)(1 << x->capacity) + 4);
xs_set_refcnt(x, 1);
```
從 `xs_set_refcnt()` 來看可以知道 reference count 的是存在 `ptr` 開頭的前 4 bytes。
```c
static inline void xs_set_refcnt(const xs *x, int val)
{
*((int *) ((size_t) x->ptr)) = val;
}
```
在 `xs_tmp()` 裡：
```c
#define xs_tmp(x) \
((void) ((struct { \
_Static_assert(sizeof(x) <= MAX_STR_LEN, "it is too big"); \
int dummy; \
}){1}), \
xs_new(&xs_literal_empty(), x))
```
會先確保長度小於 MAX_STR_LEN 才會為字串建立一個物件，其中 `_Static_assert` 會在 compile time 就確認其中的式子是否為 0 ，如果是就會發生 compile time error 然後發出訊息，如果不等於 0 ，就不會有錯誤發生。
> The constant expression is evaluated at compile time and compared to zero. If it compares equal to zero, a compile-time error occurs and the compiler must display message (if provided) as part of the error message (except that characters not in basic source character set aren't required to be displayed).
Otherwise, if expression does not equal zero, nothing happens; no code is emitted.
`s_literal_empty()` 則是初始化剩餘長度讓 space_left 為 0。
```c
#define xs_literal_empty() \
(xs) { .space_left = 15 }
```
`xs_cow_lazy_copy` 這一段程式碼主要是把 data 指向的空間複製給 x 再把 data 指向 x 存資料的位置。
```c
static bool xs_cow_lazy_copy(xs *x, char **data)
{
if (xs_get_refcnt(x) <= 1)
return false;
/* Lazy copy */
xs_dec_refcnt(x);
xs_allocate_data(x, x->size, 0);
if (data) {
memcpy(xs_data(x), *data, x->size);
/* Update the newly allocated pointer */
*data = xs_data(x);
}
return true;
}
```
不過 lazy copy 應該是要先共用同一個空間，等偵測到改變，再變成兩個獨立的 copy ，上面這段程式碼，只是單純配置空間再指向那段空間，讓外面 data 的參數，之後可以更改輸入進來的物件，並不是 lazy copy。
`*xs_concat()` 的功能就是連接前後給定的字串，首先判斷，size 加起來會不會大於 capacity，如果沒有就可以直接做搬移，如果大於 capacity 那就要用 `xs_grow()` 來增加容量。
另外 `xs_cow_lazy_copy()` 在這邊是多餘的並沒有特別的作用。
```c
xs *xs_concat(xs *string, const xs *prefix, const xs *suffix)
{
size_t pres = xs_size(prefix), sufs = xs_size(suffix),
size = xs_size(string), capacity = xs_capacity(string);
char *pre = xs_data(prefix), *suf = xs_data(suffix),
*data = xs_data(string);
xs_cow_lazy_copy(string, &data);
if (size + pres + sufs <= capacity) {
memmove(data + pres, data, size);
memcpy(data, pre, pres);
memcpy(data + pres + size, suf, sufs + 1);
if (xs_is_ptr(string))
string->size = size + pres + sufs;
else
string->space_left = 15 - (size + pres + sufs);
} else {
xs tmps = xs_literal_empty();
xs_grow(&tmps, size + pres + sufs);
char *tmpdata = xs_data(&tmps);
memcpy(tmpdata + pres, data, size);
memcpy(tmpdata, pre, pres);
memcpy(tmpdata + pres + size, suf, sufs + 1);
xs_free(string);
*string = tmps;
string->size = size + pres + sufs;
}
return string;
}
```
`*xs_grow()`的部分會先偵測資料擺放在 heap 還是 stack 如果在 stack 會先備份，因為如果更改儲存空間的話，原本的 data 會被覆蓋掉。
```c
xs *xs_grow(xs *x, size_t len)
{
char buf[16];
if (len <= xs_capacity(x))
return x;
/* Backup first */
if (!xs_is_ptr(x))
memcpy(buf, x->data, 16);
x->is_ptr = true;
x->capacity = ilog2(len) + 1;
if (xs_is_ptr(x)) {
xs_allocate_data(x, len, 1);
} else {
xs_allocate_data(x, len, 0);
memcpy(xs_data(x), buf, 16);
}
return x;
}
```
這邊會先把 is_ptr 改成 true 再去偵測 `xs_is_ptr(x)` 這樣 else 永遠進不去，推測程式是想知道 grow 之前 data 是否放在 heap 上，才能把備份的資料放上去，所以把 is_ptr = true 移到 if-else 判斷式後面比較好。
```c
xs *xs_grow(xs *x, size_t len)
{
char buf[16];
if (len <= xs_capacity(x))
return x;
/* Backup first */
if (!xs_is_ptr(x))
memcpy(buf, x->data, 16);
x->capacity = ilog2(len) + 1;
if (xs_is_ptr(x)) {
xs_allocate_data(x, len, 1);
} else {
xs_allocate_data(x, len, 0);
memcpy(xs_data(x), buf, 16);
}
x->is_ptr = true;
return x;
}
```
`xs_trim()` 主要的重點在於 check_bit 和 set_bit 的功用，set_bit 的用意在把 8 bits 字元的資訊儲存在 mask 裡面，可以看到 `mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8` 之中 byte / 8 為字元的前 5 個 bits，這會拿來當 mask 的 index ，後 3 個 bits 的資訊會用做左移的量來記錄，由於 byte % 8 最大就是 7 因此最多就是 $10000000_2$ 並不會有 overflow 的問題。
```c
xs *xs_trim(xs *x, const char *trimset)
{
if (!trimset[0])
return x;
char *dataptr = xs_data(x), *orig = dataptr;
if (xs_cow_lazy_copy(x, &dataptr))
orig = dataptr;
/* similar to strspn/strpbrk but it operates on binary data */
uint8_t mask[32] = {0};
#define check_bit(byte) (mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8)
#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)
```
從一開始和最後面 check 就可以知道縮減後的字串。
```c
size_t i, slen = xs_size(x), trimlen = strlen(trimset);
for (i = 0; i < trimlen; i++)
set_bit(trimset[i]);
for (i = 0; i < slen; i++)
if (!check_bit(dataptr[i]))
break;
for (; slen > 0; slen--)
if (!check_bit(dataptr[slen - 1]))
break;
dataptr += i;
slen -= i;
```
由於只會比原字串小，所以不用額外分配空間，只要將修剪後的資料搬移到原本的位置就可以了。
```c
/* reserved space as a buffer on the heap.
* Do not reallocate immediately. Instead, reuse it as possible.
* Do not shrink to in place if < 16 bytes.
*/
memmove(orig, dataptr, slen);
/* do not dirty memory unless it is needed */
if (orig[slen])
orig[slen] = 0;
if (xs_is_ptr(x))
x->size = slen;
else
x->space_left = 15 - slen;
return x;
#undef check_bit
#undef set_bit
}
```
這邊我會把 set_bit 和 check_bit 改成：
```c
#define check_bit(byte) (mask[(uint8_t) byte >> 3] & 1 << (uint8_t) byte & 7)
#define set_bit(byte) (mask[(uint8_t) byte >> 3] |= 1 << (uint8_t) byte & 7)
```
利用 bit-wise 操作可以更優化效能。
## CoW & 優化
Sign in with Wallet
Connect another wallet