# 2021q1 Homework3 (quiz3)
contributed by < `tigger12613` >
> [2021q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz3)
## 解釋程式碼運作原理
### 儲存結構
`xs` 是儲存字串的結構，長度小於等於15的短字串用陣列儲存在 steak ，大於的長字串儲存在 heap。不論長字串、中字串或短字串結構的大小都為 16 byte 。
`filler` 儲存字串內容，如果字串長度小於15則正常儲存，如果字串長度等於15則把結束字符放在第16個 byte 中，因為這時的 `space_left`, `is_large_string`, `is_ptr`, `flag2`, `flag3`全都會是零，剛好與結束字符相同。
`space_left` 字串剩下的空間。
`is_ptr` 是否是以指針的方式儲存。
`is_large_string` 是否是長字串。
`char *ptr` 字串指標。
`size_t size` 字串長度。
`capacity` 使用的記憶體大小，使用`2^capacity`大小的記憶體。
```cpp=
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, is_large_string : 1, flag2 : 1, flag3 : 1;
};
/* heap allocated */
struct {
char *ptr;
/* supports strings up to 2^MAX_STR_LEN_BITS - 1 bytes */
size_t size : MAX_STR_LEN_BITS,
/* capacity is always a power of 2 (unsigned)-1 */
capacity : 6;
/* the last 4 bits are important flags */
};
} xs;
```
### Functions
### xs_is_ptr
字串是否儲存在 heap。
```cpp=
static inline bool xs_is_ptr(const xs *x) { return x->is_ptr; }
```
### xs_is_large_string
字串是否大於等於`LARGE_STRING_LEN`。(`LARGE_STRING_LEN = 256`)
```cpp=
static inline bool xs_is_large_string(const xs *x)
{
return x->is_large_string;
}
```
### xs_size
字串長度。
```cpp=
static inline size_t xs_size(const xs *x)
{
return xs_is_ptr(x) ? x->size : 15 - x->space_left;
}
```
### xs_data
回傳資料位置。
如果是中字串或長字串回傳指標。如果是長字串，回傳字串的 `4 byte` 後的位置，那 `4 byte` 是用來儲存引用數量的，暫時不會用到。
`OFF` = 1 因為 large string 的前 `4 byte` 用來儲存引用數量，後面才是字串內容。
```cpp=
static inline char *xs_data(const xs *x)
{
if (!xs_is_ptr(x))
return (char *) x->data;
if (xs_is_large_string(x))
return (char *) (x->ptr + OFF);
return (char *) x->ptr;
}
```
### xs_capacity
獲得 `capacity` 的大小。
```cpp=
static inline size_t xs_capacity(const xs *x)
{
return xs_is_ptr(x) ? ((size_t) 1 << x->capacity) - 1 : 15;
}
```
### xs_set_refcnt
設定引用數量，只對長字串有意義。
```cpp=
static inline void xs_set_refcnt(const xs *x, int val)
{
*((int *) ((size_t) x->ptr)) = val;
}
```
### xs_inc_refcnt
引用數量加一，只對長字串有意義。
```cpp=
static inline void xs_inc_refcnt(const xs *x)
{
if (xs_is_large_string(x))
++(*(int *) ((size_t) x->ptr));
}
```
### xs_dec_refcnt
引用數量減一，只對長字串有意義。
```cpp=
static inline int xs_dec_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return --(*(int *) ((size_t) x->ptr));
}
```
### xs_get_refcnt
獲取引用數量。
```cpp=
static inline int xs_get_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return *(int *) ((size_t) x->ptr);
}
```
### ilog2
以二為底對 `uint32` 取 `log` 並且 round down 。
```cpp=
static inline int ilog2(uint32_t n) { return 32 - __builtin_clz(n) - 1; }
```
### xs_allocate_data
分配或重新分配記憶體，記憶體大小一定是二的次方或二的次方加四。
```cpp=
static void xs_allocate_data(xs *x, size_t len, bool reallocate)
{
/* Medium string */
if (len < LARGE_STRING_LEN) {
x->ptr = reallocate ? realloc(x->ptr, (size_t) 1 << x->capacity)
: malloc((size_t) 1 << x->capacity);
return;
}
/* Large string */
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_new
新增 `xs` ，短字串放在原位，中長字串額外新增一個記憶體存放。
```cpp=
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;
}
```
### xs_grow
加大分配的記憶體。第17行的 else 永遠不會發生，第 12 行保證 is_ptr = true。
如果把實際上 `is_ptr == false` 的字串重新分配記憶體會發生記憶體錯誤，因此刪去`x->is_ptr = true`，加在真的分配記憶體之後。
因為 `xs_capacity` 對 `is_ptr == false` 的字串會回傳 `15` 因此對增大後的長度小於 16 的字串將不額外分配記憶體。
```cpp=
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);
x->is_ptr = true;
}
return x;
}
```
### xs_newempty
新增一個空字串。
```cpp=
static inline xs *xs_newempty(xs *x)
{
*x = xs_literal_empty();
return x;
}
```
### xs_free
釋放使用的記憶體，回傳一個空字串。
```cpp=
static inline xs *xs_free(xs *x)
{
if (xs_is_ptr(x) && xs_dec_refcnt(x) <= 0)
free(x->ptr);
return xs_newempty(x);
}
```
### xs_cow_lazy_copy
如果不是長字串 xs_get_refcnt 為 0 ，回傳 false 。
如果是長字串而且被引用超過2個就必須分配一個新的記憶體並且把字串複製過去。
當字串面臨更改就必須使用此函式，去確認是否要分配一個新的記憶體。
因為現在沒有實作 `CoW` 因此現在只會回傳 false 。
```cpp=
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;
}
```
### xs_concat
給 `string` 字串加上頭尾字串。
因為 `string` 面臨更改所以呼叫 `xs_cow_lazy_copy`。
如果連接完的字串大小小於等於容量，就不用增大記憶體，反之則要增大記憶體。
```cpp=
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_trim
清除字串前後指定的字元。
```cpp=
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)
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;
/* 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
`uint8_t mask[32] = {0}`總共有 256 個 bit 因此把每個 `byte` 一一對應到這 256 個 bit 上，如果某個 `byte` 需要被標記就把 屬於它的 bit 設為 1 。
```cpp=
#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)
```
### check_bit
確認 `byte` 是不是被標記的 `byte` ，原理與 `set_bit` 相同。
```cpp=
#define check_bit(byte) (mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8)
```
Sign in with Wallet
Connect another wallet