owned this note
owned this note
Published
Linked with GitHub
# 2020q1 Homework2 (quiz2)
contributed by < `sherisea` >
## 重新回答測驗題並解釋程式碼運作原理
1. AAA=?
```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;
x->ptr = malloc((size_t) 1 << x->capacity);
memcpy(x->ptr, p, len);
} else {
memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);
}
return x;
}
```
此段程式用於字串為短字串或長字串,而初始化 x 的 space_left 為 `15`,考慮到要涵蓋結束字元,因此可知 **AAA 應為 15 + 1 = 16。**
:::danger
注意共筆書寫慣例:中英文間以一個半形空白字元區隔
:notes: jserv
:::
若字串長度大於15:
```cpp
x->capacity = ilog2(len) + 1;
x->size = len - 1;
x->is_ptr = true;
x->ptr = malloc((size_t) 1 << x->capacity);
memcpy(x->ptr, p, len);
```
* 字串將儲存於heap中(因 stack 上可存放的字串長度的最大值為 15),is_ptr 為1
* size用來儲存字串長度
若字串長度小於等於15(else段落):
```cpp
memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);
```
* 字串將儲存於 stack 中
* 字串長度可由15-space_left求得
2. BBB=? CCC=?
```cpp
xs *xs_trim(xs *x, const char *trimset)
{
if (!trimset[0])
return x;
char *dataptr = xs_data(x), *orig = dataptr;
/* similar to strspn/strpbrk but it operates on binary data */
uint8_t mask[BBB] = {0};
#define check_bit(byte) (mask[(uint8_t) byte / 8] CCC 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
}
```
此段程式用於去除掉 x 內前後包含於 trimset 的字元。
根據 check_bit 和 set_bit 中 `mask[(uint8) byte / 8]` 以及 uint_8 最大可達 255,255 / 8 為 31.8,因此 **BBB 應為 32。**
* set_bit
1. 將要刪除的字元所對應到的 mask bit 更新為 1
2. 每個字元都能與 mask 對應
* check_bit
1. 檢查字串頭尾是否出現 trimset 的成員
2. 為了檢查是否出現要刪除的字元,可判斷出應該使用 & 來比較,因此 **CCC 應為 `&`**
#### 其他部分
* xs_tmp
```cpp
#define xs_tmp(x) \
((void) ((struct { \
_Static_assert(sizeof(x) <= 16, "it is too big"); \
int dummy; \
}){1}), \
xs_new(&xs_literal_empty(), "" x))
```
檢查 x 是否小於或等於 16 字元
* xs_grow
```cpp
xs *xs_grow(xs *x, size_t len)
{
if (len <= xs_capacity(x))
return x;
len = ilog2(len) + 1;
if (xs_is_ptr(x))
x->ptr = realloc(x->ptr, (size_t) 1 << len);
else {
char buf[16];
memcpy(buf, x->data, 16);
x->ptr = malloc((size_t) 1 << len);
memcpy(x->ptr, buf, 16);
}
x->is_ptr = true;
x->capacity = len;
return x;
}
```
若x的記憶體空間不夠,則重新配置 ${\log_2 len} + 1$ 大小的記憶體空間 (ilog2(len) + 1)
* xs_concat
```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);
if (size + pres + sufs <= capacity) {
memmove(data + pres, data, size);
memcpy(data, pre, pres);
memcpy(data + pres + size, suf, sufs + 1);
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;
}
```
將 prefix 與 suffix 串接到字串的前後
:::danger
列於 [Homework2 作業區](https://hackmd.io/@sysprog/linux2020-homework2) 的網址應為透過 HackMD 選取「公開發表」後所得的超連結,請更正。
:notes: jserv
:::