# 2021q1 Homework2 (quiz2)
contributed by < `ccs100203` >
###### tags: `linux2021`
> [第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz2)
## 測驗 1
以下是針對 doubly-linked list 的 merge sort 實作:
```cpp
#include <string.h>
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;
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(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);
}
```
### 解釋程式原理
> 參考 [Merge sort](https://en.wikipedia.org/wiki/Merge_sort)
程式會藉由 `get_middle` 取得該 list 的中間點，再透過 `list_cut_position` 做切割，然後重複的遞迴呼叫。當所有節點都分開後會經由 `list_merge` 將其排序以及結合。
#### `get_middle`
此函式的目的是找出 list 的中間點
```cpp
/**
* list_for_each - iterate over list nodes
* @node: list_head pointer used as iterator
* @head: pointer to the head of the list
*/
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
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);
}
```
下面的圖表只繪製出 `next` 指標
- 首先，會分別用 `fast`、`slow` 指標指向 list 的前兩個 node
```graphviz
digraph graphname{
node[shape=box]
fast[shape=plaintext,fontcolor=red]
slow[shape=plaintext,fontcolor=red]
"*list"[shape=plaintext,fontcolor=red]
rankdir=LR
{
rank="same";
slow->A
"*list"->A
}
{
fast->B
}
A->B->C->D->E->F->G->A
}
```
- 再來進入了 `list_for_each` 所定義的迴圈內，一開始的賦值階段會先將 `slow` 指向下一個節點
```graphviz
digraph graphname{
node[shape=box]
fast[shape=plaintext,fontcolor=red]
slow[shape=plaintext,fontcolor=red]
"*list"[shape=plaintext,fontcolor=red]
rankdir=LR
{
rank="same"
"*list"->A
}
{
rank="same"
fast->B
slow->B
}
A->B->C->D->E->F->G->A
}
```
- 在 if 的判斷通過之前，迴圈會讓 `slow` 不斷指向下一個節點，而 `fast` 則會指向下下個節點
```graphviz
digraph graphname{
node[shape=box]
fast[shape=plaintext,fontcolor=red]
slow[shape=plaintext,fontcolor=red]
"*list"[shape=plaintext,fontcolor=red]
rankdir=LR
{
rank="same"
"*list"->A
}
{
rank="same";
slow->C
}
{
rank="same";
fast->D
}
A->B->C->D->E->F->G->A
}
```
- 此時，`fast->next->next == list` 的判斷式會成立
可以看出 `slow` 會位於 list 中間的節點，所以藉著 `slow` 就可以將 A、B、C 與 D、E、F、G 分開。
```graphviz
digraph graphname{
node[shape=box]
fast[shape=plaintext,fontcolor=red]
slow[shape=plaintext,fontcolor=red]
"*list"[shape=plaintext,fontcolor=red]
rankdir=LR
{
rank="same"
"*list"->A
}
{
rank="same";
slow->D
}
{
rank="same";
fast->F
}
A->B->C->D->E->F->G->A
}
```
#### `list_cut_position`
此函式用來將一條 list 從特定的點切分成兩條 list。
他會將 `head_from` 之後一直到 `node` 之間的節點接到 `head_to`。
舉例來說:
```
node
|
V
HEAD->N1->N2->N3->N4->N5->N6->N7->N8
LEFT
```
最終情況會變成下列兩條 list
```
HEAD->N5->N6->N7->N8
LEFT->N1->N2->N3->N4
```
- 下面是程式碼以及更詳盡的圖解
```cpp=
/**
* list_cut_position() - Move beginning of a list to another list
* @head_to: pointer to the head of the list which receives nodes
* @head_from: pointer to the head of the list
* @node: pointer to the node in which defines the cutting point
*/
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;
}
```
- 給定剛進入函式時的情況
```graphviz
digraph graphname{
node[shape=box]
head_to[shape=plaintext,fontcolor=red]
head_from[shape=plaintext,fontcolor=red]
"node"[shape=plaintext,fontcolor=red]
rankdir=LRBT
{
rank="same"
A->B->C->D [style=invis]
}
"node"->C
head_from->A
A->B->C->D
D->C->B->A
head_to->N->N:w
N->N:e
A->D:e
D->A:w
}
```
- 執行完 Line 21, 22
```cpp=21
head_from->next = node->next;
head_from->next->prev = head_from;
```
```graphviz
digraph graphname{
node[shape=box]
head_to[shape=plaintext,fontcolor=red]
head_from[shape=plaintext,fontcolor=red]
"node"[shape=plaintext,fontcolor=red]
rankdir=LRBT
{
rank="same"
A->B->C->D [style=invis]
}
"node"->C
head_from->A
A->D:e
B->C
C->B
B->A
C->D->A:w
A->D:e
D->A:w
head_to->N->N:w
N->N:e
}
```
- 執行完 Line 24, 25
```cpp=24
head_to->prev = node;
node->next = head_to;
```
```graphviz
digraph graphname{
node[shape=box]
head_to[shape=plaintext,fontcolor=red]
head_from[shape=plaintext,fontcolor=red]
"node"[shape=plaintext,fontcolor=red]
rankdir=LRBT
{
rank="same"
A->B->C->D [style=invis]
}
"node"->C
head_from->A
A->D
B->C
C->B
B->A
C->N
D->A
A->D
D->A
head_to->N->C
N->N:e
}
```
- 執行完 Line 26, 27
```cpp=26
head_to->next = head_from_first;
head_to->next->prev = head_to;
```
```graphviz
digraph graphname{
node[shape=box]
head_to[shape=plaintext,fontcolor=red]
head_from[shape=plaintext,fontcolor=red]
"node"[shape=plaintext,fontcolor=red]
rankdir=LRBT
{
rank="same"
A->B->C->D [style=invis]
}
"node"->C
head_from->A
A->D
B->C
C->B
B->N
C->N
D->A
A->D
D->A
head_to->N->C
N->B
}
```
---
## 測驗 2
考慮函式 func 接受一個 16 位元無號整數 $N$，並回傳小於或等於 $N$ 的 power-of-2 (漢字可寫作為 2 的冪)
```cpp=
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;
}
```
- 先考慮一個數字如何轉換為 power of 2，以一個隨意的 16 位元無號整數來說，只要保留最高位的 1 並將其他都轉換為 0 即可。
- 所以先將比最高位還低的位元全部轉換為 1，這樣就可以產生出 $00...0011...111$ 的數字，此時只需要將這個數字 + 1，再將他往右位移，就可以得到 power of 2。
- 以 1025 為例，可以看到透過前面的幾行會將較低位元的 bit 全數轉換為 1，再透過第八行將他轉換為 power of 2。
| after<br>execution | 15 <br>MSB | 14~11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 <br>LSB |
| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| Line 2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| Line 3 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| Line 4 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| Line 5 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Line 6 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Line 8 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
### 查閱 Linux 核心原始程式碼 power of 2
> 根據 [log2.h](https://elixir.bootlin.com/linux/latest/source/include/linux/log2.h#L36)
#### is_power_of_2
```cpp
/**
* is_power_of_2() - check if a value is a power of two
* @n: the value to check
*
* Determine whether some value is a power of two, where zero is
* *not* considered a power of two.
* Return: true if @n is a power of 2, otherwise false.
*/
static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) == 0));
}
```
- 已知如果一個數字只有任一且唯一一個 bit 為 1，其餘為 0，那麼他就屬於 power of 2。
- `(n & (n - 1)` 的操作，其實就是將最低位的 bit 設為 0。
假設 `n` 為 $11000$， `n - 1` 就是 $10111$，此時做 and 運算就可以將最底位的 bit 設為 0。
也藉由這個特性，跟上述已知道的條件，所以在做完 `(n & (n - 1)` 後，若數字變為 0，則代表其為 power of 2。
#### `__roundup_pow_of_two` 和 `__rounddown_pow_of_two` 解析
`__roundup_pow_of_two` 是為了將數字無條件進位到比較大的 power of 2，反之則為 `__rounddown_pow_of_two`。
- 以 $24$ 舉例:
- `__roundup_pow_of_two(24)` 應得到 32
- `__rounddown_pow_of_two(24)` 應得到 16
觀察以下程式碼，`fls_long` 的作用是 find leading set，也就是找出 bit 中最高位的 1。
- 已知 `fls_long(24)` 會得到 5
- `__roundup_pow_of_two`
只要再藉由 `1U << 5` 就能得到 32，那為什麼需要 `n-1` 呢?
假設今天不是 24，而是 32 這種屬於 power of 2 的數字時，程式是不需要做進位的，但是直接做 `fls_long(32)` 會得到 6，代表程式在不需要進位時還是會進位。所以需要藉由 `n-1` 去避免掉程式多做了進位的情況。
- `__rounddown_pow_of_two`
由於是要無條件捨去，所以可以很直觀的將 `fls_long(n)` 的結果 - 1，也就是只保留了原先數字中最高位為 1 的 bit。
```cpp
/**
* __roundup_pow_of_two() - round up to nearest power of two
* @n: value to round up
*/
static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
return 1UL << fls_long(n - 1);
}
/**
* __rounddown_pow_of_two() - round down to nearest power of two
* @n: value to round down
*/
static inline __attribute__((const))
unsigned long __rounddown_pow_of_two(unsigned long n)
{
return 1UL << (fls_long(n) - 1);
}
```
#### 如何 find leading set
由於上述的程式用到了 find leading set 的功能，所以來解釋他的做法。首先可以看到 `fls_long` 只是藉由不同的 type size 去呼叫不同的 fls。
##### fls_long
```cpp
static inline unsigned fls_long(unsigned long l)
{
if (sizeof(l) == 4)
return fls(l);
return fls64(l);
}
```
這邊只擷取了某一部分的情況，可以看到 find leading set 是藉由 number of bits 減 count leading zero 做出來的，而 `__kernel_ctlz` 又會藉 GCC Built in function 裡的 `__builtin_clzl` 去實作。
透過這些函式的串聯，就可以知道 `fls_long` 的功用與作法。
##### fls && fls64
```cpp
static inline int fls64(unsigned long word)
{
return 64 - __kernel_ctlz(word);
}
static inline int fls(unsigned int x)
{
return fls64(x);
}
```
##### `__kernel_ctlz(x)`
```cpp
# define __kernel_ctlz(x) __builtin_clzl(x)
```
:::info
- 參考 [fls_long](https://elixir.bootlin.com/linux/latest/source/include/linux/bitops.h#L185)
- 參考 [fls](https://elixir.bootlin.com/linux/latest/source/arch/alpha/include/asm/bitops.h#L366)
- 參考 [__kernel_ctlz](https://elixir.bootlin.com/linux/latest/source/arch/alpha/include/uapi/asm/compiler.h#L55)
- 參考 [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
:::
#### `__attribute__((const))` 用處
> 參考 [Declaring Attributes of Functions](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Function-Attributes.html)
Basically this is just slightly more strict class than the pure attribute below, since function is not allowed to read global memory.
Note that a function that has pointer arguments and examines the data pointed to must not be declared const. Likewise, a function that calls a non-const function usually must not be const. It does not make sense for a const function to return void.
規定 function 不能夠含有指標相關的參數以及調動到 global memory，同時也要求其必須有 void 以外的回傳值。
:::warning
換言之，`__attribute__((const))` 讓 C function (函式) 限縮到數學意義上的 function (函數)，這也是為何中文翻譯應該區分「函式」和「函數」
:notes: jserv
:::
---
## 測驗 3
以下是 `bitcpy` 實作，允許開發者對指定的記憶體區域，逐 bit 進行資料複製:
(避免篇幅過長故隱藏)
:::spoiler
```cpp=
#include <stdint.h>
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t count)
{
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);
static const uint8_t read_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t write_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
while (count > 0) {
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
/* Cross multiple bytes */
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
mask |= write_mask[write_lhs + bitsize];
*dest++ = (original & mask) | (data >> write_lhs);
}
count -= bitsize;
}
}
```
:::
透過 `read_lhs` 與 `read_rhs` 可以知道資料所需的偏移量。而 write 也是使用了相同的手段。
而 `_read / 8` 可以得知要從第幾個 byte 開始讀取。
```cpp=9
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);
```
限制每次最多處理 8 bits。
並且藉由 `bitsize` 與 `read_rhs` 的比較去判斷此次運算是否需要跨越到下一個 byte。
如果需要的話代表 `data` 需要加入下一個 byte 內最高位開始的 `read_rhs` 個 bit。
```cpp=42
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
```
而 `read_mask` 與 `write_mask` 的用處就在於保證程式只更改 / 更新到所需要的 bits。
- 先解釋程式如何進行寫入:
如果需要寫入最低位的 3 個 bit，則會產生下列的 mask:
```graphviz
digraph {
rankdir=LR
byte [shape="record", label="{1|1|1|1|1|0|0|0}"];
}
```
再來利用 `*dest = (*dest & mask) | (data >> write_lhs);`
`(*dest & mask)` 可以保留不須更改的高位 5 個 bits。
`(data >> write_lhs)` 則是用來取出需要寫入的 bits。
將兩者做 bitwise or 運算就可以完成預期中寫入的動作。
- 程式碼寫入實作說明
如果不需要跨位元組寫入，透過 `mask |= write_mask[write_lhs + bitsize];` 會將需要寫入的 bits 設為 0，而其餘設為 1，就可以透過下一行的操作在不更動其餘資料的狀況下將資料填入。
如果需要跨位元組寫入，第 60 行的會先寫入第一個 byte，利用 `mask` 將其操作限制在最右邊幾個所需的 bits。而下面兩行則是利用 `write_mask` 將需要寫入的幾個高位元的 bit 設為 0，其餘不變的則為 0，藉此完成寫入的操作。
```cpp=53
if (bitsize < 8)
data &= read_mask[bitsize];
uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
/* Cross multiple bytes */
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
mask |= write_mask[write_lhs + bitsize];
*dest++ = (original & mask) | (data >> write_lhs);
}
```
TODO 研究 linux kernel [bitmaps](https://github.com/torvalds/linux/blob/master/include/linux/types.h)
---
## 測驗 4
> 參考 [String interning](https://en.wikipedia.org/wiki/String_interning)
> In computer science, string interning is a method of storing only one copy of each distinct string value, which must be immutable. Interning strings makes some string processing tasks more time- or space-efficient at the cost of requiring more time when the string is created or interned.
> 以及 [Immutable object](https://en.wikipedia.org/wiki/Immutable_object)
> In object-oriented and functional programming, an immutable object (unchangeable object) is an object whose state cannot be modified after it is created.
String interning 是將出現多處的字串，只保存在單一的儲存空間，存取時直接讀取 reference，藉此節省運算與儲存成本。
以下是 string interning 在 C 語言中的簡易實作:
(避免篇幅過長故隱藏)
:::spoiler
- cstr.h
```cpp=
#pragma once
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
enum {
CSTR_PERMANENT = 1,
CSTR_INTERNING = 2,
CSTR_ONSTACK = 4,
};
#define CSTR_INTERNING_SIZE (32)
#define CSTR_STACK_SIZE (128)
typedef struct __cstr_data {
char *cstr;
uint32_t hash_size;
uint16_t type;
uint16_t ref;
} * cstring;
typedef struct __cstr_buffer {
cstring str;
} cstr_buffer[1];
#define CSTR_S(s) ((s)->str)
#define CSTR_BUFFER(var) \
char var##_cstring[CSTR_STACK_SIZE] = {0}; \
struct __cstr_data var##_cstr_data = {var##_cstring, 0, CSTR_ONSTACK, 0}; \
cstr_buffer var; \
var->str = &var##_cstr_data;
#define CSTR_LITERAL(var, cstr) \
static cstring var = NULL; \
if (!var) { \
cstring tmp = cstr_clone("" cstr, (sizeof(cstr) / sizeof(char)) - 1); \
if (tmp->type == 0) { \
tmp->type = CSTR_PERMANENT; \
tmp->ref = 0; \
} \
if (!__sync_bool_compare_and_swap(&var, NULL, tmp)) { \
if (tmp->type == CSTR_PERMANENT) \
free(tmp); \
} \
}
#define CSTR_CLOSE(var) \
do { \
if (!(var)->str->type) \
cstr_release((var)->str); \
} while (0)
/* Public API */
cstring cstr_grab(cstring s);
cstring cstr_clone(const char *cstr, size_t sz);
cstring cstr_cat(cstr_buffer sb, const char *str);
int cstr_equal(cstring a, cstring b);
void cstr_release(cstring s);
```
- cstr.c
```cpp=
#include <errno.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include "cstr.h"
#define INTERNING_POOL_SIZE 1024
#define HASH_START_SIZE 16 /* must be power of 2 */
struct __cstr_node {
char buffer[CSTR_INTERNING_SIZE];
struct __cstr_data str;
struct __cstr_node *next;
};
struct __cstr_pool {
struct __cstr_node node[INTERNING_POOL_SIZE];
};
struct __cstr_interning {
int lock;
int index;
unsigned size;
unsigned total;
struct __cstr_node **hash;
struct __cstr_pool *pool;
};
static struct __cstr_interning __cstr_ctx;
/* FIXME: use C11 atomics */
#define CSTR_LOCK() \
({ \
while (__sync_lock_test_and_set(&(__cstr_ctx.lock), 1)) { \
} \
})
#define CSTR_UNLOCK() ({ __sync_lock_release(&(__cstr_ctx.lock)); })
static void *xalloc(size_t n)
{
void *m = malloc(n);
if (!m)
exit(-1);
return m;
}
static inline void insert_node(struct __cstr_node **hash,
int sz,
struct __cstr_node *node)
{
uint32_t h = node->str.hash_size;
int index = h & (sz - 1);
node->next = hash[index];
hash[index] = node;
}
static void expand(struct __cstr_interning *si)
{
unsigned new_size = si->size * 2;
if (new_size < HASH_START_SIZE)
new_size = HASH_START_SIZE;
struct __cstr_node **new_hash =
xalloc(sizeof(struct __cstr_node *) * new_size);
memset(new_hash, 0, sizeof(struct __cstr_node *) * new_size);
for (unsigned i = 0; i < si->size; ++i) {
struct __cstr_node *node = si->hash[i];
while (node) {
struct __cstr_node *tmp = node->next;
insert_node(new_hash, new_size, node);
node = tmp;
}
}
free(si->hash);
si->hash = new_hash;
si->size = new_size;
}
static cstring interning(struct __cstr_interning *si,
const char *cstr,
size_t sz,
uint32_t hash)
{
if (!si->hash)
return NULL;
int index = (int) (hash & (si->size - 1));
struct __cstr_node *n = si->hash[index];
while (n) {
if (n->str.hash_size == hash) {
if (!strcmp(n->str.cstr, cstr))
return &n->str;
}
n = n->next;
}
// 80% (4/5) threshold
if (si->total * 5 >= si->size * 4)
return NULL;
if (!si->pool) {
si->pool = xalloc(sizeof(struct __cstr_pool));
si->index = 0;
}
n = &si->pool->node[si->index++];
memcpy(n->buffer, cstr, sz);
n->buffer[sz] = 0;
cstring cs = &n->str;
cs->cstr = n->buffer;
cs->hash_size = hash;
cs->type = CSTR_INTERNING;
cs->ref = 0;
n->next = si->hash[index];
si->hash[index] = n;
return cs;
}
static cstring cstr_interning(const char *cstr, size_t sz, uint32_t hash)
{
cstring ret;
CSTR_LOCK();
ret = interning(&__cstr_ctx, cstr, sz, hash);
if (!ret) {
expand(&__cstr_ctx);
ret = interning(&__cstr_ctx, cstr, sz, hash);
}
++__cstr_ctx.total;
CSTR_UNLOCK();
return ret;
}
static inline uint32_t hash_blob(const char *buffer, size_t len)
{
const uint8_t *ptr = (const uint8_t *) buffer;
size_t h = len;
size_t step = (len >> 5) + 1;
for (size_t i = len; i >= step; i -= step)
h = h ^ ((h << 5) + (h >> 2) + ptr[i - 1]);
return h == 0 ? 1 : h;
}
cstring cstr_clone(const char *cstr, size_t sz)
{
if (sz < CSTR_INTERNING_SIZE)
return cstr_interning(cstr, sz, hash_blob(cstr, sz));
cstring p = xalloc(sizeof(struct __cstr_data) + sz + 1);
if (!p)
return NULL;
void *ptr = (void *) (p + 1);
p->cstr = ptr;
p->type = 0;
p->ref = 1;
memcpy(ptr, cstr, sz);
((char *) ptr)[sz] = 0;
p->hash_size = 0;
return p;
}
cstring cstr_grab(cstring s)
{
if (s->type & (CSTR_PERMANENT | CSTR_INTERNING))
return s;
if (s->type == CSTR_ONSTACK)
return cstr_clone(s->cstr, s->hash_size);
if (s->ref == 0)
s->type = CSTR_PERMANENT;
else
__sync_add_and_fetch(&s->ref, 1);
return s;
}
void cstr_release(cstring s)
{
if (s->type || !s->ref)
return;
if (__sync_sub_and_fetch(&s->ref, 1) == 0)
free(s);
}
static size_t cstr_hash(cstring s)
{
if (s->type == CSTR_ONSTACK)
return hash_blob(s->cstr, s->hash_size);
if (s->hash_size == 0)
s->hash_size = hash_blob(s->cstr, strlen(s->cstr));
return s->hash_size;
}
int cstr_equal(cstring a, cstring b)
{
if (a == b)
return 1;
if ((a->type == CSTR_INTERNING) && (b->type == CSTR_INTERNING))
return 0;
if ((a->type == CSTR_ONSTACK) && (b->type == CSTR_ONSTACK)) {
if (a->hash_size != b->hash_size)
return 0;
return memcmp(a->cstr, b->cstr, a->hash_size) == 0;
}
uint32_t hasha = cstr_hash(a);
uint32_t hashb = cstr_hash(b);
if (hasha != hashb)
return 0;
return !strcmp(a->cstr, b->cstr);
}
static cstring cstr_cat2(const char *a, const char *b)
{
size_t sa = strlen(a), sb = strlen(b);
if (sa + sb < CSTR_INTERNING_SIZE) {
char tmp[CSTR_INTERNING_SIZE];
memcpy(tmp, a, sa);
memcpy(tmp + sa, b, sb);
tmp[sa + sb] = 0;
return cstr_interning(tmp, sa + sb, hash_blob(tmp, sa + sb));
}
cstring p = xalloc(sizeof(struct __cstr_data) + sa + sb + 1);
if (!p)
return NULL;
char *ptr = (char *) (p + 1);
p->cstr = ptr;
p->type = 0;
p->ref = 1;
memcpy(ptr, a, sa);
memcpy(ptr + sa, b, sb);
ptr[sa + sb] = 0;
p->hash_size = 0;
return p;
}
cstring cstr_cat(cstr_buffer sb, const char *str)
{
cstring s = sb->str;
if (s->type == CSTR_ONSTACK) {
int i = s->hash_size;
while (i < CSTR_STACK_SIZE - 1) {
s->cstr[i] = *str;
if (*str == 0)
return s;
++s->hash_size;
++str;
++i;
}
s->cstr[i] = 0;
}
cstring tmp = s;
sb->str = cstr_cat2(tmp->cstr, str);
cstr_release(tmp);
return sb->str;
}
```
:::
TODO
<!--
### 程式原理
如果兩個字串比對後的內容相同，那麼可以將其保存在相同的記憶體空間。
倘若字串長度過長，則比對過程會耗費大量成本，於是程式引入了 hash，藉此降低比對的成本。只要兩者的 hash 相同，即為相同的字串。
#### struct
```cpp
typedef struct __cstr_data {
char *cstr;
uint32_t hash_size;
uint16_t type;
uint16_t ref;
} * cstring;
typedef struct __cstr_buffer {
cstring str;
} cstr_buffer[1];
``` -->
Sign in with Wallet
Connect another wallet