# 2020q3 Homework3 (dict)
###### tags: `embedded_master`
Contributed by < `huang-me` >
[toc]
# Principle
==解釋程式的運作原理==
## test_common.c
### 判斷應該使用 CPY 或者 REF
```c
if (!strcmp(argv[1], "CPY") || (argc > 2 && !strcmp(argv[2], "CPY"))) {
CPYmask = 0;
REF = DEL;
printf("CPY mechanism\n");
} else
printf("REF mechanism\n");
```
利用 strcmp 比較 argument 的內容，如果裡面包含 CPY 的話表示要使用 CPY mechanism，反之則使用 REF mechanism。
### 建立 memory pool
```c
if (CPYmask) {
/* memory pool */
pool = (char *) malloc(poolsize * sizeof(char));
Top = pool;
}
```
如果選用的是 REF 的話就需要建立 memory pool，利用 cast 使得 Top 的內容可以被修改。
### 讀入資料
```c
while (fgets(buf, WORDMAX, fp)) {
int offset = 0;
for (int i = 0, j = 0; buf[i + offset]; i++) {
Top[i] =
(buf[i + j] == ',' || buf[i + j] == '\n') ? '\0' : buf[i + j];
j += (buf[i + j] == ',');
}
while (*Top) {
if (!tst_ins_del(&root, Top, INS, REF)) { /* fail to insert */
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
bloom_add(bloom, Top);
idx++;
int len = strlen(Top);
offset += len + 1;
Top += len + 1;
}
Top -= offset & ~CPYmask;
memset(Top, '\0', WORDMAX);
}
```
1. 逐行讀入城市資料並且將所有的 "," 或者 "\n" 替換為 "\0"
2. `j += (buf[i + j] == ',');`
保留 "," 之後的第一個空格
3. `tst_ins_del(&root, Top, INS, REF)`
將新的資料存入 tst 中
4. `bloom_add(bloom, Top);`
將新資料放入 bloom 中
5. `Top -= offset & ~CPYmask;`
在使用 CPY 的時候，需要先將 Top 的位置指回起始位置，再進行 memset，否則會使用到沒有辦法使用的記憶體
而使用 REF 則可以直接把記憶體繼續放在 memory pool，前面已經先宣告好記憶體位置。
## tst.c
### 找尋 prefix
```c
while ((curr = *pcurr)) {
diff = *p - curr->key;
if (diff == 0) {
if (*p++ == 0) {
if (del) {
(curr->refcnt)--;
return tst_del_word(root, curr, &stk, cpy);
} else
curr->refcnt++;
return (void *) curr->eqkid;
}
pcurr = &(curr->eqkid);
} else if (diff < 0) {
pcurr = &(curr->lokid);
} else {
pcurr = &(curr->hikid);
}
if (del)
tst_stack_push(&stk, curr);
}
```
1. 計算輸入詞的每個字母以及 pcurr->key 的大小，並且更新新的 pcurr
2. 如果找到一樣的字母就增加或者減少 refcnt
3. `if (*p++ == 0)` 如果詞語已經在 dict 中，直接 return 當前的 pointer
### 刪除不存在於 dict 的詞
```c
if (del)
return (void *) -1;
```
如果已經搜尋完了還是沒有找到相對應的詞，代表詞語並不在 dict 中，因此 return -1。
### 補上後續的字母於 dict
```c
for (;;) {
if (!(*pcurr = calloc(1, sizeof **pcurr))) {
fprintf(stderr, "error: tst_insert(), memory exhausted.\n");
return NULL;
}
curr = *pcurr;
curr->key = *p;
curr->refcnt = 1;
curr->lokid = curr->hikid = curr->eqkid = NULL;
if (!*root) /* handle assignment to root if no root */
*root = *pcurr;
if (*p++ == 0) {
if (cpy) {
const char *eqdata = strdup(s);
if (!eqdata)
return NULL;
curr->eqkid = (tst_node *) eqdata;
return (void *) eqdata;
} else {
curr->eqkid = (tst_node *) s;
return (void *) s;
}
}
pcurr = &(curr->eqkid);
}
```
1. 用 calloc 初始化一個空間，準備存放 node
2. `curr->key = *p;` 將字母設定為 curr 的 key，並且將其他的內容都設定好
3. 如果已經將整個詞語的 prefix 都設定好
如果使用的是 CPY 的話，就需要 allocate 記憶體以存取新的詞語，並且將 curr->eqkid 指向此記憶體。
反之，使用 REF 的話就可以直接把 curr->eqkid 指向 memory pool 中的此字串。
# 修改利用 getopt 修改讀取 argument
```c
if (argc == 3 && strcmp(argv[1], "--bench") == 0) {
...
}
```
本來利用 if 判斷執行時給予的參數有沒有 "--bench"，不過如果輸入的 argument 不止三個或者 "--bench" 沒有放在第一個參數的時候就會有誤判的情形發生，因此改用 getopt 以確保應該執行 bench 時不會出錯，也有更好的擴充性。
```c
int c, stat;
while ((c = getopt(argc, argv, "b")) != -1) {
switch (c) {
case 'b':
...
}
}
```
# REF 以及 CPY 執行時間差異
|WITHOUT BLOOM| CPY | REF |
|:---:|:------------------------------------:|:------------------------------------:|
|PREFIX:3|  |  |
|WHOLE WORD|  |  |
- 經過視覺化，發現在沒有使用 bloom filter 的情況下，REF 以及 CPY 搜尋 cities.txt 中的字串時無論使用的 prefix 長度為何，REF 以及 CPY 的執行速度基本上沒有明顯的差異。
- 而如果輸入要搜尋的字串越短，符合的字串就越多因此也需要更多的執行時間才可以找到所有的可能性。
## 有無使用 bloom filter 的差異
| WITH BLOOM | CPY | REF |
| -------- | -------- | -------- |
| PREFIX:3 |  |  |
| WHOLE WORD |  |  |
- 如果使用 bloom filter 搜尋 cities.txt 中的城市，可以大幅度降低搜尋時間，就算是搜尋3個字的 prefix 也可以達到接近
Sign in with Wallet
Connect another wallet