# 2021q1 Homework2 (quiz2)
contributed by <`YingMuo` >
###### tags: `linux2021` `quiz2`
## 進度
- [ ] 測驗一
- [X] 解釋程式碼
- [ ] 解釋效能
- [ ] 效能評比
- [ ] 測驗二
- [X] 解釋程式碼
- [X] linux kernal 中的原始碼
- [ ] slab
- [ ] 測驗三
- [ ] 解釋程式碼並重寫
- [ ] linux kernal 中的原始碼
- [ ] 測驗四
- [X] 解釋程式碼
- [ ] 測試多執行緒
- [ ] chriso/intern
## 解釋程式運作原理
### 結構
用 `next` 串成 singly linked list 並用 `list_head` 串成 circular doubly linked list
```c
typedef struct __element {
char *value;
struct __element *next;
struct list_head list;
} list_ele_t;
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t size;
struct list_head list;
} queue_t;
```
使用 `q_insert_head` 串起來的 linked list 會長這樣
```graphviz
graph insert_head{
node [shape = record]
graph [rankdir = LR]
head
tail
ele1 [label = "{<value> ele1|<next> next|<list_head> list}"]
ele2 [label = "{<value> ele2|<next> next|<list_head> list}"]
ele3 [label = "{<value> ele3|<next> next|<list_head> list}"]
ele4 [label = "{<value> ele4|<next> next|<list_head> list}"]
ele1:next -- NULL
ele2:next -- ele1:value
ele3:next -- ele2:value
ele4:next -- ele3:value
head -- ele4:value
tail -- ele1:value
list -- ele1:list_head
ele1:list_head -- ele2:list_head
ele2:list_head -- ele3:list_head
ele3:list_head -- ele4:list_head
ele4:list_head -- list
}
```
將 singly linked list 和 circular doubly linked list 同時出現會導致 list 結構難以想像，並且 singly linked list 能夠做到的操作 circular doubly linked list 都能夠做到，導致 singly linked list 顯得很冗贅
:::warning
能夠正確輸出預期結果的程式碼，不該用「沒意義」來描述 (你那些碩博班的學長姐連「輸出符合預期結果」的程式碼都做不到，這樣的高等教育才是更「沒意義」)。工程講究持續反省和進步的歷程，你指出冗余程式碼很好，但不要用「沒意義」來誤導讀者的理解。
寫共筆的其中一個作用是，預先對未來的面試和工作溝通做準備。
:notes: jserv
:::
而 `queue_t` 結構在沒有 `next` 之後也顯得一樣多餘了，剩下有用的 size 也沒有被任何函式用到，可以直接拿掉
修改過後的版本：
```c
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
typedef struct __element {
char *value;
struct list_head list;
} list_ele_t;
static list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each(slow, list)
{
if (fast->next == list || fast->next->next == list)
break;
fast = fast->next->next;
}
return list_entry(slow, list_ele_t, list);
}
static void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
INIT_LIST_HEAD(head);
if (list_empty(lhs)) {
list_splice_tail(lhs, head);
return;
}
if (list_empty(rhs)) {
list_splice_tail(rhs, head);
return;
}
while (!list_empty(lhs) && !list_empty(rhs)) {
char *lv = list_entry(lhs->next, list_ele_t, list)->value;
char *rv = list_entry(rhs->next, list_ele_t, list)->value;
struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
list_del(tmp);
list_add_tail(tmp, head);
}
list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}
void list_merge_sort(struct list_head *q)
{
if (list_is_singular(q))
return;
struct list_head left;
struct list_head sorted;
INIT_LIST_HEAD(&left);
list_cut_position(&left, q, &get_middle(q)->list);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left, q, &sorted);
INIT_LIST_HEAD(q);
list_splice_tail(&sorted, q);
}
static bool validate(struct list_head *q)
{
struct list_head *node;
list_for_each(node, q)
{
if (node->next == q)
break;
if (strcmp(list_entry(node, list_ele_t, list)->value,
list_entry(node->next, list_ele_t, list)->value) > 0)
return false;
}
return true;
}
static void q_free(struct list_head *q)
{
if (!q)
return;
list_ele_t *tmp = NULL;
while (!list_empty(q)) {
tmp = list_first_entry(q, list_ele_t, list);
list_del(&tmp->list);
free(tmp->value);
free(tmp);
}
}
bool q_insert_head(struct list_head *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
char *new_value = strdup(s);
if (!new_value) {
free(newh);
return false;
}
newh->value = new_value;
list_add_tail(&newh->list, q);
return true;
}
int main(void)
{
FILE *fp = fopen("cities.txt", "r");
if (!fp) {
perror("failed to open cities.txt");
exit(EXIT_FAILURE);
}
struct list_head q;
INIT_LIST_HEAD(&q);
char buf[256];
while (fgets(buf, 256, fp))
q_insert_head(&q, buf);
fclose(fp);
list_merge_sort(&q);
assert(validate(&q));
q_free(&q);
return 0;
}
```
改完後的結構變成下圖，其實就是 `list_head` 的結構
```graphviz
graph insert_head{
node [shape = record]
graph [rankdir = LR]
q
ele1 [label = "{<value> ele1|<list_head> list}"]
ele2 [label = "{<value> ele2|<list_head> list}"]
ele3 [label = "{<value> ele3|<list_head> list}"]
ele4 [label = "{<value> ele4|<list_head> list}"]
q -- ele1:list_head
ele1:list_head -- ele2:list_head
ele2:list_head -- ele3:list_head
ele3:list_head -- ele4:list_head
ele4:list_head -- q
}
```
修改前後記憶體空間使用比較
```c
$ valgrind --tool=memcheck --track-origins=yes ./list
==13737== HEAP SUMMARY:
==13737== in use at exit: 0 bytes in 0 blocks
==13737== total heap usage: 187,657 allocs, 187,657 frees, 5,280,092 bytes allocated
==13737==
==13737== All heap blocks were freed -- no leaks are possible
==13737==
==13737== For lists of detected and suppressed errors, rerun with: -s
==13737== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
$ valgrind --tool=memcheck --track-origins=yes ./list_nonext
==13746== HEAP SUMMARY:
==13746== in use at exit: 0 bytes in 0 blocks
==13746== total heap usage: 187,656 allocs, 187,656 frees, 4,529,436 bytes allocated
==13746==
==13746== All heap blocks were freed -- no leaks are possible
==13746==
==13746== For lists of detected and suppressed errors, rerun with: -s
==13746== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
### get_middle
```c
static list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each(slow, list)
{
if (fast->next == list || fast->next->next == list)
break;
fast = fast->next->next;
}
return list_entry(slow, list_ele_t, list);
}
```
在這個函式中，`fast` 指標走訪串列的兩個節點，而 `slow` 指標則一次走訪串列的一個節點，所以當 `fast` 走到串列尾端時，`slow` 會在串列的中間部位，就可以拿到中間部位的節點。
### list_merge
```c
static void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
INIT_LIST_HEAD(head);
if (list_empty(lhs)) {
list_splice_tail(lhs, head);
return;
}
if (list_empty(rhs)) {
list_splice_tail(rhs, head);
return;
}
while (!list_empty(lhs) && !list_empty(rhs)) {
char *lv = list_entry(lhs->next, list_ele_t, list)->value;
char *rv = list_entry(rhs->next, list_ele_t, list)->value;
struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
list_del(tmp);
list_add_tail(tmp, head);
}
list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}
```
1. 如果其中一個 list 是空的，就直接把另一個 list 接在 head 後面
2. 兩條 list 的第一個 element 的值做比較，小於者會將第一個 element 從 list 中 remove 並加到 head 的尾端，直到其中一條 list 空的時候，就將另一條接在 head 後面
如果兩個 list 是 sorted，會得到一個也是 sorted 的 list
### list_cut_position
```c
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
會將 head_from 的第一個 element 到 node 都移到 head_to，剩下的都留在 head_from
### list_merge_sort
```c
void list_merge_sort(queue_t *q)
{
if (list_is_singular(&q->list))
return;
queue_t left;
struct list_head sorted;
INIT_LIST_HEAD(&left.list);
list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
INIT_LIST_HEAD(&q->list);
list_splice_tail(&sorted, &q->list);
}
```
1. list 的第一個 element 到 get_middle 得到的 element 移到 left，分別進行 list_merge_sort，在 merge 到 sort ，並重新放到 list
2. 如果 list_is_singular 就會 return ，所以最小切到剩一個 element
```graphviz
graph merge_sort {
node [shape = record]
subgraph cluster_00 {
subgraph cluster_0 {
"4" "3";
label = "";
color=blue;
}
subgraph cluster_1 {
"2" "1";
label = "";
color=blue;
}
}
subgraph cluster_01 {
subgraph cluster_3 {
"6" "5";
label = "";
color=blue;
}
subgraph cluster_2 {
"8" "7";
label = "";
color=blue;
}
}
}
```
## list_sort
### merge
```c
__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, cmp_func cmp,
struct list_head *a, struct list_head *b)
{
struct list_head *head, **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
* ```__artribute__((nonnull(args)))``` 為第 args 的 parameter 不能是 NULL
* 透過 cmp 去比較 a 和 b 的大小，比較小的會接在 head 的最後面 ( next )
1. a < b, return < 0
2. a = b, return = 0
3. a > b, return > 0
* 如果其中一個 list 為空，就把另一個 list 接在 head 最後面
* 沒有 prev ( singly linked list )，沒有 circle
### merge_final
```c
__attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, cmp_func cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
struct list_head *tail = head;
u8 count = 0;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
```
* 透過 cmp 去比較 a 和 b 的大小，比較小的會接在 head 的最後面 ( 雙向 )
* 如果其中一個 list 為空，就把另一個 list 接在 head 最後面，並將其 prev 都補齊
* 把頭尾聯起來，形成 doubly circular linked list
### list_sort
```c
__attribute__((nonnull(2, 3))) void list_sort(void *priv,
struct list_head *head,
int (*cmp)(void *priv,
struct list_head *a,
struct list_head *b))
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
/*
* Data structure invariants:
* - All lists are singly linked and null-terminated; prev
* pointers are not maintained.
* - pending is a prev-linked "list of lists" of sorted
* sublists awaiting further merging.
* - Each of the sorted sublists is power-of-two in size.
* - Sublists are sorted by size and age, smallest & newest at front.
* - There are zero to two sublists of each size.
* - A pair of pending sublists are merged as soon as the number
* of following pending elements equals their size (i.e.
* each time count reaches an odd multiple of that size).
* That ensures each later final merge will be at worst 2:1.
* - Each round consists of:
* - Merging the two sublists selected by the highest bit
* which flips when count is incremented, and
* - Adding an element from the input as a size-1 sublist.
*/
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, (cmp_func) cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, (cmp_func) cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, (cmp_func) cmp, head, pending, list);
}
```
* 將尾端的 next 指向 NULL ( 拆掉 circular )
* 將 list 的 prev 當作 pending 的空間來使用，每一個迴圈都會把 list 的頭放進 pending，形成前面是 pending 指向的 singly linked list 從後到前，後面是 list 指向的 singly linked list 從前到後，假設沒有進行 merge 的話會長的像下圖
```graphviz
digraph pending {
node [shape = record]
rankdir = LR
subgraph cluster_pending {
ele1 -> ele2 -> ele3 [dir=back]
label = "pending"
color = blue
}
head -> ele1
subgraph cluster_list {
ele4 -> ele5 -> ele6
ele4 -> ele5 -> ele6 [dir = back]
label = "list"
color = blue
}
ele3 -> ele4 [dir = back]
head -> ele6
pending -> ele3
list -> ele4
}
```
* count 的 least-significant 為 0 時會進行 merge，假設 ele4 < ele1 < ele5 < ele2 < ele6 < ele3
count = 3
```graphviz
digraph pending {
node [shape = record]
rankdir = LR
subgraph cluster_pending {
ele1 -> ele3 [dir=back]
ele1 -> ele2
NULL -> ele1 [dir=back]
label = "pending"
color = blue
}
head -> ele1
subgraph cluster_list {
ele4 -> ele5 -> ele6
ele4 -> ele5 -> ele6 [dir = back]
label = "list"
color = blue
}
ele3 -> ele4 [dir = back]
head -> ele6
pending -> ele3
list -> ele4
}
```
count = 4
```graphviz
digraph pending {
node [shape = record]
rankdir = LR
subgraph cluster_pending {
ele1 -> ele4 [dir=back]
ele1 -> ele2
ele4 -> ele3
NULL -> ele1 [dir=back]
label = "pending"
color = blue
}
head -> ele1
subgraph cluster_list {
ele5 -> ele6
ele5 -> ele6 [dir = back]
label = "list"
color = blue
}
ele4 -> ele5 [dir = back]
head -> ele6
pending -> ele4
list -> ele5
}
```
count = 5
```graphviz
digraph pending {
node [shape = record]
rankdir = LR
subgraph cluster_pending {
ele4 -> ele5 [dir=back]
ele4 -> ele1 -> ele2 -> ele3
NULL -> ele4 [dir=back]
label = "pending"
color = blue
}
head -> ele1
subgraph cluster_list {
ele6
label = "list"
color = blue
}
ele5 -> ele6 [dir = back]
head -> ele6
pending -> ele5
list -> ele6
}
```
count = 6，完美 2：1 ( ele4 有 4 個，ele6 有 2 個 )，bitwise 的奧秘
```graphviz
digraph pending {
node [shape = record]
rankdir = LR
subgraph cluster_pending {
ele4 -> ele6 [dir=back]
ele6 -> ele5
ele4 -> ele1 -> ele2 -> ele3
NULL -> ele4 [dir=back]
label = "pending"
color = blue
}
head -> ele1
subgraph cluster_list {
label = "list"
color = blue
}
head -> ele6
pending -> ele6
NULL2 [label = "NULL"]
list -> NULL2
}
```
* 如果在 pending 中的 linked list 大於 2 條會將其 merge 到只剩兩條
* 最後將剩下 2 條 list 進行 merge_final，除了會 merge 也會將 prev, circular 補回去，就完成了 merge sort
### 最佳化手法
TODO:
:::warning
不要只是貼出超連結，你需要摘要並且指出其中不足之處。任何人都可以複製貼上，或者用一句話讚揚，但只有具備專業的人，才能看出細節。
現在就要求自己深究！
:notes: jserv
:::
---
## power-of-2
### 解釋函式
```c
uint16_t func(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
return (N + 1) >> 1;
}
```
以 1000 0000 0000 0000 為例
N = 1000 0000 0000 0000
N = 1100 0000 0000 0000 ( N |= N >> 1 )
N = 1111 0000 0000 0000 ( N |= N >> 2 )
N = 1111 1111 0000 0000 ( N |= N >> 4 )
N = 1111 1111 1111 1111 ( N |= N >> 8 )
上述計算完後最高有效位將比他低位的 bit 都變成 1，因為他每次運算完都會將最高有效位及已經被他改變的位數都往後 shift，or 運算改到的範圍就會變大，所以能夠改變最高有效位後的所有 bit。
:::danger
改進上述漢語用法
:notes: jserv
:::
### round up/down power of in linux
* __builtin_constant_p 會判斷 n 是不是 constant
* ilog2 會得到 constant 的 log2 計算值
```c
#define roundup_pow_of_two(n) \
( \
__builtin_constant_p(n) ? ( \
((n) == 1) ? 1 : \
(1UL << (ilog2((n) - 1) + 1)) \
) : \
__roundup_pow_of_two(n) \
)
```
```c
static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
return 1UL << fls_long(n - 1);
}
```
```c
#define rounddown_pow_of_two(n) \
( \
__builtin_constant_p(n) ? ( \
(1UL << ilog2(n))) : \
__rounddown_pow_of_two(n) \
)
```
```c
static inline __attribute__((const))
unsigned long __rounddown_pow_of_two(unsigned long n)
{
return 1UL << (fls_long(n) - 1);
}
```
* \_\_roundup/down_pwo_of_two 都會呼叫 fls_long，而且從 roundup 為 fls_long(n-1) 與 rounddown 為 fls_long(n) - 1 可以猜測其就是將最高位以下的所以 bit 填成 1
```c
static inline unsigned fls_long(unsigned long l)
{
if (sizeof(l) == 4)
return fls(l);
return fls64(l);
}
```
* 這裡就先只看 fls() 的行為
```c
static __always_inline int fls(unsigned int x)
{
int r = 32;
if (!x)
return 0;
if (!(x & 0xffff0000u)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xff000000u)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xf0000000u)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xc0000000u)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x80000000u)) {
x <<= 1;
r -= 1;
}
return r;
}
```
* 這裡跟測驗中的 code 其實是一樣的概念，只是反過來把位數扣掉而已
## string intern
### 結構
#### cstring
```c
typedef struct __cstr_data {
char *cstr;
uint32_t hash_size;
uint16_t type;
uint16_t ref;
} * cstring;
```
string 結構的基本單位
* cstr - 字串
* hash_size - hash 值或是 string size
* 在 interning - hash_blob 的返回值 ( hash值 )
* 使用 buffer 建構 ( 在 stack ) - string size
* type - 不同的結構建構方式會有不同的 type
* CSTR_PERMANENT - 使用 CSTR_LITERAL 建構或 cstr_grab 沒有 type 的 cstring 會賦予該 cstring 此 type
* CSTR_INTERNING - 使用 cstr_interning 建構
* cstr_clone 在 sz < CSTR_INTERNING_SIZE 時使用
* cstr_cat 在 type 不為 CSTR_ONSTACK 且 sa + sb < CSTR_INTERNING_SIZE 時使用
* CSTR_ONSTACK - 使用 CSTR_BUFFER 建構
* 0 - 在 cstr_clone 或 cstr_cat 時沒有進到 interning 且不保持在 stack 上時
* ref - cstring 被多少東西依賴
* 在 hash table 或是在 stack 上的 cstring 為 0
* 在 cstr_clone 或 cstr_cat 時 size 超過 CSTR_INTERNING_SIZE 的 cstring 為 1
* 如果 type 不是有定義的 type 且 ref 不為 0 時 ( 方便稱呼這裡叫這情況為失去管理的 cstring )，cstr_grab 此 cstring 會讓 ref + 1 ( 監控失去管理的 cstring 被幾個東西依賴 )
總結一下不同情況下對應的 hash_size、type 和 ref 的值
* 在 interning - hash_size = hash_blob, type = CSTR_INTERNING, ref = 0
* 使用 buffer 建構 ( 在 stack ) - hash_size = string size, type = CSTR_ONSTACK, ref = 0
* 未進行初始話的 cstring 在被 cstr_grab 後 - hash_size = 0, type = CSTR_PERMANENT, ref = 0
* 在 cstr_clone 或 cstr_cat 因為 string 過長而未進入 interning ( 失去管理的 cstring ) - hash_size = 0, type = 0, ref > 0
#### cstr_buffer
```c
typedef struct __cstr_buffer {
cstring str;
} cstr_buffer[1];
```
將 cstring 包裝方便進行初始話
```c
struct __cstr_node {
char buffer[CSTR_INTERNING_SIZE];
struct __cstr_data str;
struct __cstr_node *next;
};
```
* hash table 的 node
* buffer 給 cstr_data 的 cstr 有一個空間可以放字串
* linked list 可以改成 list_head
#### cstr_pool
```c
struct __cstr_pool {
struct __cstr_node node[INTERNING_POOL_SIZE];
};
```
interning 存放 cstr_node 的空間
#### cstr_interning
```c
struct __cstr_interning {
int lock;
int index;
unsigned size;
unsigned total;
struct __cstr_node **hash;
struct __cstr_pool *pool;
};
```
整個 interning 結構
* lock - 為了 atomic 的 lock 操作
* index - 紀錄 pool 使用到哪個 node
* size - hash table 的 size
* total - 在 interning 的 node 總數
* hash - hash table
* pool - cstr_pool
### 函式
#### CSTR_LOCK/UNLOCK
使用 atomic 來做 lock 和 unlock
#### static inline void insert_node(struct __cstr_node **hash, int sz, struct __cstr_node *node)
* 在 hash table expand size 後把 node 重新放回 hash table 時使用
* 將 cstring 加到 ( hash_size % sz ) 那個 index 的 linked list 的 head
#### static void expand(struct __cstr_interning *si)
* 讓 hash table 的 size 變成原本的 2 倍 ( hash table 的 size 必須是 2 的 次方 )
* 重新開一個空間給 hash table
* 將在舊的 hash table 裡的 node 加到新的 hash table 並 free 舊的 hash table
#### static cstring interning(struct __cstr_interning *si, const char *cstr, size_t sz, uint32_t hash)
* cstr_interning 的底層操作
* 如果在 hash table 中找到一個 hash_size 與輸入的字串一樣但 cstr 卻不同的 cstring 就會將該 cstring 回傳
* 為了讓 hash table 不那容易碰撞，如果 si->total * 5 >= si->size * 4 就回傳 NULL ( 4/5 threshold )
* 在 pool 中取出一個 node，配置好 cstring，放到 hash[hash_size % table 的 size]
**threshold 的 4/5 是否為最佳值？**
#### static cstring cstr_interning(const char *cstr, size_t sz, uint32_t hash)
* 先上 lock
* 在 lock 期間會去執行 interning，如果回傳值是 NULL 代表 hash table 不夠大就去執行 expand 並在執行 interning
* 關閉 lock
#### static inline uint32_t hash_blob(const char *buffer, size_t len)
對應 hash table 的 hash 值
#### cstring cstr_clone(const char *cstr, size_t sz)
*
* 如果 string size < CSTR_INTERNING_SIZE 就使用 cstr_interning 在 interning 裡註冊一個 string 並回傳
* 否則 malloc 一個空間 maintain 一個 cstring 並回傳( 失去管理的 cstring )
#### cstring cstr_grab(cstring s)
* 依照 s 不同的 type 有不同操作
* type = CSTR_PERMANENT 或 CSTR_INTERNING 會直接回傳 s
* type = CSTR_ONSTACK 會執行 cstr_clone 並回傳 clone 出來的 cstring ( 用 buffer 建構的 cstring 會得到其 clone )
* 如果 type 不是以上三個且 ref = 0 則 type = CSTR_PERMANENT 並回傳 s ( 推測是為了未初始化的 cstring )
* 如果皆不是上述情況則 s 的 ref + 1 並回傳 s ( 讓失去管理的 cstring 的依賴數 + 1 )
#### void cstr_release(cstring s)
* 如果 s 的 type = 0 且 ref > 0 ( 失去管理的 cstring ) 就 s 的 ref - 1 ( 依賴數 - 1 )
* 如果剩下的依賴數是 0 就 free s
#### static size_t cstr_hash(cstring s)
* 為了不再重複計算 hash_blob
* 如果 s 在 interning 內就回傳其 hash_size
* 否則回傳 s 的 hash_blob 回傳值
#### int cstr_equal(cstring a, cstring b)
* 如果 a 跟 b 是同一個指標回傳 true
* 如果 a 跟 b 的 type 都是 CSTR_INTERNING 回傳 false
* 如果 a 跟 b 的 type 都是 CSTR_ONSTACK 且 hash_size 一樣回傳 cstr 的 strcmp，否則 false
* 不為上述情況的話會去比較 a 和 b 的 cstr_hash 值，如果一樣的話會回傳 cstr 的 strcmp
#### static cstring cstr_cat2(const char *a, const char *b)
* 如果 a + b 的 size ， CSTR_INTERNING_SIZE 就把 a 和 b 依序 memcpy 進一個 char \[\] 然後使用 cstr_interning 放進 interning
* 否則malloc 一個空間 maintain 一個 cstring 並回傳( 失去管理的 cstring )
#### cstring cstr_cat(cstr_buffer sb, const char *str)
* 如果 sb->str->type 為 CSTR_ONSTACK 就將 str 直接接在 sb->str->cstr 後面
* 如果 str 都放進去就結束並回傳 sb->str->cstr，否則在 size = CSTR_STACK_SIZE 後就會將 sb->str->cstr 和 str 丟進 cstr_cat2 再回傳 sb->str->cstr
Sign in with Wallet
Connect another wallet