# Skip list & Prefix Search 在 C 語言上的簡單實作
## 為 Desktop Search 打造輕量級資料結構
在 2023 我還在念大學的時候，當時的專題指導老師 jserv 幫我想了一個非常有趣的題目。
題目是用 C 語言打造「桌面搜尋與平行化 PageRank 運算」，旨在應用 PageRank 平行化運算至本地端的桌面檔案監視與資料查詢的服務，類似 WinFS、Google Desktop，以及在 Linux 上的 Recoll、Tracker 等實作。
這個題目作為大學專題對於當時的我來說非常嚇人，光是研究各種 PageRank 演算法的平行化或許就可以獨立成為另一個專題了。還有有關於如何監視桌面下所有子目錄的事件，建立資料結構去儲存，進而生出 PageRank，再讓使用者透過 prefix/infix search 去得到想要的搜尋結果。這中間需要的思考設計、資料結構的選用、所需要了解的背景知識都遠超當時的我所預想。
當然，先求有再求好，但我一直很害怕寫出未來難以維護或擴充的資料結構，所以大學時的專題，儘管我非常喜歡這個題目，最終專題的實作較為簡陋，很多設計也因此停留於構想。
回顧完這段旅程，兩年後的我想再嘗試一次這個題目，在寫完有關於監視目錄下所有檔案的活動之後，接下來就需要一個資料結構來達到：
* 快速 prefix search
* 儲存檔案路徑與後續 PageRank 運算搭配使用
並期望這個資料結構能達到簡單、輕量。
## 為什麼用 skip list?
### 1. Prefix Search 更直覺好寫
如果要做到 prefix search，用 skip list 實作會相對直觀。skip list 的底層是一個排序的 linked list，只要找到 prefix 的起始節點後，向後線性掃描即可完成查詢。
相比之下，AVL / Red-Black Tree 屬於 binary search tree 結構，無法僅靠大小比較決定方向。實作 prefix search 時，往往還需要額外處理範圍搜尋、狀態遞迴等機制，不但複雜，還會讓整體程式的可讀性變差。
### 2. 有機會擴充為對 cache 較為友善的資料結構
雖然 skip list 的搜尋時間為期望 $O(\log n)$，不像 AVL / RB Tree 是最壞情況也能保證 $O(\log n)$，但 skip list 的記憶體存取模式（例如：連續掃描、較少指標跳躍）更符合 CPU cache 的特性。
這樣的性質使得 skip list 有機會在中小型規模資料下獲得實際效能優勢，未來甚至可以朝 cache-oblivious 的設計方向發展，保留在 high level 的 skip list 行為設計，改進底層資料結構，進一步改善效能。
### 3. 更容易擴充為多執行緒版本
因此若要設計 lock-based 的多執行緒版本，可以僅針對節點或某段區間加鎖，避免整個結構都上鎖造成效能瓶頸。
相比之下，AVL 與 RB Tree 每次插入或刪除都可能觸發旋轉、重新平衡（rotation 或 recoloring），牽動整棵樹的結構，因此不得不鎖住整個資料結構。
而若要實作 lock-free 的版本，skip list 的邏輯也比平衡樹簡單許多。
### 4. 其他原因
Skip list 資料結構在系統軟體開發時不時就會被提及一下，有時會出現在經典的 `struct list_head` 資料結構底下討論，亦或是在有些課程的課程討論區（例如：Linux 核心設計）。
網路上有很多人整理 skip list 的理論與應用，但是針對 skip list 去作出一個簡單的 C 語言實作相對比較少（至少在有公開在 HackMD 上的開發紀錄，看到的情況是這樣）。所以我就想要來試試看用 C 語言來寫一個簡單的 skip list。
## Linux 核心的 circular doubly linked list 與 skiplist
Linux kernel 中 `struct list_head` 資料結構非常經典，背後的設計思維可見：[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94)。
這個資料結構背後的設計思維可以給我們許多啟發，它的特點是:
* **環狀設計**：不需要特別處理 head/tail 特例。
* **雙向鏈結**：節點可以前後移動，方便刪除節點，增加後續實作其他功能的靈活性。
* **`container_of` 巨集**：讓資料結構本體與節點分離，不用自行維護一套 doubly-linked list。
然後再參考有關於 skip list 在 linux 核心的討論：[A kernel skiplist implementation (Part 1)](https://lwn.net/Articles/551896/), [Skiplists II: API and benchmarks](https://lwn.net/Articles/553047/)
裡面討論到的 skiplist 也用 circular doubly linked list 的概念實作，這樣在實作 skip list 資料結構的時候，將每一層 skip list 都設計成是個獨立的 circular doubly linked list。
## Skip list 資料結構
但是為了有跳表的 **精神**，也就是在不同層數下有相同 value 的節點應該都要被視為是同一個節點，只能有唯一地址。即使在不同的層數，只要該節點被 "跳" 到，所存取到的地址都該是同一個地址。
所以為了這個 **精神**，很彆扭的設計出一個如下的資料結構：
```c
struct sl_node;
typedef struct sl_node_ptr {
struct sl_node *next, *prev;
} sl_node_ptr;
typedef struct sl_node {
struct sl_node_ptr *list;
int lv;
} sl_node;
typedef struct sl_data {
char path[PATH_MAX];
double pgrk;
struct sl_node node;
} sl_data;
typedef struct skiplist {
struct sl_node head;
int lv;
} sl;
```
`sl_node_ptr` 是每一層用來連接節點的 forward / backward pointer，把它抽成一個獨立的小結構，這樣每一層都可以當成一個 doubly linked list 來操作。方便後續實作 circular doubly linked list 的實現。
`sl_node` 則是包住這些 pointer，再加上一個欄位紀錄這個節點的層數 (lv)。
真正的資料本體是放在 `sl_data` 裡面，這個結構和 `sl_node` 的相關操作是分開的。如果在操作 `sl_node` 的時候想要拿到資料內容，就需要靠 `container_of` 巨集來往外找到對應的 `sl_data` 結構。
```c
#ifndef container_of
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *)0)->member) *__pmember = (ptr); \
(type *)((char *)__pmember - offsetof(type, member)); \
})
#endif
```
然後我們可以再額外定義一個 `sl_entry` 巨集：
```c
#define sl_entry(ptr, type, member) container_of(ptr, type, member)
```
---
### 初始化巨集設計
在這份 skip list 的實作中，每層都是一個獨立的 circular doubly linked list，因此初始化的時候我們就讓每一層的 pointer 指向自己。讓每層都是 circular doubly linked list 之後，就可以避免之後插入/刪除時還要處理 head/tail 特例。
初始化一個節點的 pointer 結構：
```c
#define INIT_SL_NODE_CIRCULAR(node, level) \
do { \
(node)->lv = (level); \
(node)->list = calloc(level, sizeof(sl_node_ptr)); \
for (int i = 0; i < level; i++) { \
(node)->list[i].next = (node); \
(node)->list[i].prev = (node); \
} \
} while (0)
```
初始化整個 skip list 的 head node（每層都是獨立環狀 list）：
```c
#define INIT_SL_HEAD(sl, level) \
do { \
(sl)->lv = (level); \
INIT_SL_NODE_CIRCULAR(&(sl)->head, level); \
} while (0)
```
---
### 節點遍歷巨集 (Iteration Macros)
有了 circular doubly linked list 的結構後，我們就可以定義類似 Linux kernel 的 list 操作巨集。
基本的遍歷某一層可以寫成：
```c
#define sl_for_each_at_level(pos, head, level) \
for ((pos) = (head)->list[level].next; (pos) != (head); (pos) = (pos)->list[level].next)
```
可以以此類推其他像是 `sl_for_each_safe_at_level`, `sl_for_each_entry_at_level`, `sl_for_each_entry_continue_at_level` ... 等等巨集。
---
## Skip List 核心操作與對應實作
### `sl_lookup`：查找節點（同時記錄路徑）
```c
sl_node *sl_lookup(sl *skplist, const char *path, sl_node **update) {
sl_node *pos = &skplist->head;
for (int i = skplist->lv - 1; i >= 0; i--) {
while (pos->list[i].next != &skplist->head) {
sl_node *next = pos->list[i].next;
int cmp = strcmp(sl_entry(next, sl_data, node)->path, path);
if (!cmp)
return next;
if (cmp > 0)
break;
pos = next;
}
if (update) update[i] = pos;
}
return NULL;
}
```
從最上層往下層逐步搜尋節點，並找出 `path` 名稱剛好等於輸入字串的節點。這個搜尋原理其實類似於 Binary Search。
我們可以注意到：
* 走訪順序是從最上層（`list->lv - 1`）往下層（`0`）進行，每層都試圖「往後跳」直到下一個節點比目標大或是相同為止。
* 每層停下的位置（即每層中最後一個小於目標值的節點）會紀錄在 `update[i]`，方便後續實作 `sl_insert`。
* 走訪下一層開始的節點，就是上一層停下的位置。
這個函式其實還有支援兩種模式：
* 查找模式：傳入 `update = NULL`，只想知道這個節點存不存在。
* 插入前準備：傳入一個 `update[MAX_LEVEL]` 陣列，函式會順便記下每層的「插入點前一個節點」，節省後續 `sl_insert()` 時再找一次的成本。
比如在插入新節點時就會這樣用：
```c
sl_node *update[MAX_LEVEL];
if (sl_lookup(skplist, path, update)) {
// 建立新節點並使用 update[] 插入各層
}
```
這樣可以一邊查找，一邊記住每層的插入位置，避免之後還要再走一次路徑。
---
### `sl_insert`：插入新節點
```c
int sl_insert(sl *skplist, const char *path, double pgrk) {
sl_node *update[MAX_LEVEL];
for (int i = 0; i < MAX_LEVEL; i++)
update[i] = &skplist->head;
if (!path)
return -1;
if (sl_lookup(skplist, path, update))
return -1;
sl_data *entry = calloc(1, sizeof(sl_data));
if (!entry)
return -1;
snprintf(entry->path, PATH_MAX, "%s", path);
entry->pgrk = pgrk;
int new_lv = random_level();
INIT_SL_NODE_CIRCULAR(&entry->node, new_lv);
return _sl_insert(skplist, &entry->node, update);
}
```
這段程式碼主要分成幾個步驟：
* 先檢查有沒有重複
一開始會用 `sl_lookup()` 查找目標 `path`，順便把每一層未來的插入位置記在 `update[]` 裡。
如果發現已經有同名的節點，就直接回傳 `-1`，表示插入失敗。
* 準備新節點
如果沒重複，就先用 `calloc()` 分配一個新的 `sl_data` 節點，並將相關對應資料寫進去。
* 決定節點高度並初始化
接著用 `random_level()` 決定這個節點的層數（高度）。
再用 `INIT_SL_NODE_CIRCULAR()` 把每一層的 doubly linked list 初始化成 circular doubly linked list。
* 把新節點插入 skip list
最後呼叫 `_sl_insert()`，利用一開始 `sl_lookup()` 紀錄的 `update[]` 資訊，將新節點插入每一層對應的位置。
---
### `sl_delete`：刪除目標節點
```c
int sl_delete(sl *skplist, const char *path) {
if (!path)
return -1;
sl_node *target = sl_lookup(skplist, path, NULL);
if (!target)
return -1;
sl_node_remove(target);
sl_data *data = sl_entry(target, sl_data, node);
free(target->list);
free(data);
// Shrink list level if top levels are empty
while (skplist->lv > 1 && sl_empty_at_level(&skplist->head, skplist->lv - 1))
skplist->lv--;
return 0;
}
```
* 尋找目標節點
用 `sl_lookup` 找出目標節點 `target`。這裡沒有使用 `update[]`，因為刪除只需要找到該節點本身即可。
* 解除節點連結
呼叫 `sl_node_remove(target)`，透過節點內部指標逐層解除與前後節點的連結。
* 釋放記憶體
釋放該節點的指標陣列 `ptr` 和實際資料本體 `data`。
* 調整 skip list 高度(層數)
如果最高層已無節點，將 skip list 的高度 `list->lv` 往下縮減。
:::warning
**為何刪除不使用 `update[]` ？**
* 刪除時，只需知道目標節點本身，透過該節點的指標即可完成所有層級的連結解除。
* `sl_node_remove` 函式就是利用這點逐層解除連結。
```c
static inline void sl_node_remove(sl_node *n) {
for (int i = 0; i < n->lv; i++) {
sl_node_remove_at_level(n, i);
}
}
```
* 反而插入時必須事先知道每層的插入位置，因此需要用 `update[]` 紀錄查找過程中的節點位置。
:::
---
## Prefix search 實作
### `sl_lookup_prefix`：取得 prefix 開頭的多筆結果
```c
int sl_lookup_prefix(sl *skplist, const char *prefix, sl_data **results, int max) {
int prefix_len = strlen(prefix);
sl_node *head = &skplist->head;
sl_node *n = sl_lookup_prefix_lower_bound(skplist, prefix);
if (!n)
return 0;
sl_data *entry = sl_entry(n, sl_data, node);
int count = 0;
sl_for_each_entry_from_at_level(entry, head, 0, sl_data, node) {
if (strncmp(entry->path, prefix, prefix_len) || count >= max)
break;
results[count++] = entry;
}
return count;
}
```
這裡先呼叫 `sl_lookup_prefix_lower_bound`（類似 `sl_lookup` 的實作方式，只是不再找到目標之後立即 `return`），找到 prefix 在 skip list 最底層（level `0`）可能開始的位置，也就是第一個字串大於或等於 prefix 的節點。
接著從 skip list 底層（level `0`）開始遍歷整個 list，利用 `strncmp` 比較字串前綴是否相符，將所有符合的節點放入 `results` 中，直到超過 `max` 筆或遍歷結束。
---
## 資源釋放與記憶體管理
### `sl_free`
```c
void sl_free(sl *skplist) {
sl_node *pos, *tmp;
sl_for_each_safe_at_level(pos, tmp, &skplist->head, 0) {
sl_data *data = sl_entry(pos, sl_data, node);
free(data->node.list);
free(data);
}
free(skplist->head.list);
free(skplist);
}
```
在釋放整個 skip list 需要注意幾個點：
* 安全遍歷釋放節點
使用 `sl_for_each_safe_at_level` 巨集來遍歷節點，必須使用「safe」版本，避免在釋放節點時破壞遍歷鏈結，導致記憶體存取錯誤（segmentation fault）。
* 只遍歷 Level `0`
只需遍歷底層（Level `0`）的節點，因為所有層的節點指標均指向相同節點本體。當底層節點被釋放後，其它層的節點連結自然失效，無須重複釋放。
* 記憶體釋放順序
先釋放每個節點中存放不同層鏈結指標的 `ptr` 陣列，再釋放節點本體。最後釋放 skip list `head` 節點的 `ptr` 陣列，以及整個 skip list 結構本身。
---
## `main()` 簡單測試範例：插入、查詢與刪除
以下示範 Skip List 的插入、Prefix Search 與刪除功能，並展示對應的預期輸出：
```c
int main() {
init_random();
sl *list = sl_create();
sl_insert(list, "/doc/report.txt", 0.8);
sl_insert(list, "/doc/readme.md", 0.9);
sl_insert(list, "/doc/archive.zip", 0.7);
sl_insert(list, "/music/song.mp3", 0.5);
sl_insert(list, "/video/movie.mp4", 0.6);
sl_data *results[10];
int n = sl_lookup_prefix(list, "/doc", results, 10);
printf("Search prefix '/doc' found %d results:\n", n);
for (int i = 0; i < n; i++) {
printf(" %s (PageRank: %.2f)\n", results[i]->path, results[i]->pgrk);
}
sl_delete(list, "/doc/readme.md");
printf("After deleting '/doc/readme.md':\n");
n = sl_lookup_prefix(list, "/doc", results, 10);
for (int i = 0; i < n; i++) {
printf(" %s (PageRank: %.2f)\n", results[i]->path, results[i]->pgrk);
}
sl_free(list);
return 0;
}
```
預期輸出:
```
Search prefix '/doc' found 3 results:
/doc/archive.zip (PageRank: 0.70)
/doc/readme.md (PageRank: 0.90)
/doc/report.txt (PageRank: 0.80)
After deleting '/doc/readme.md':
/doc/archive.zip (PageRank: 0.70)
/doc/report.txt (PageRank: 0.80)
```
---
## 未來可以拓展的方向
* 更完善的亂數生成機制
目前使用標準 C 函式庫的 `random()` 作為隨機層數產生器，
```c
static inline uintptr_t _init_random(uintptr_t seed) {
uintptr_t x = (uintptr_t)(void *)&_init_random; // ASLR
x ^= seed;
x = (x << 13) | (x >> ((sizeof(uintptr_t) << 3) - 13));
x ^= (x >> 7);
x ^= (x << 17);
return x;
}
void init_random(void) {
struct timeval tm;
gettimeofday(&tm, NULL);
uintptr_t t = (uintptr_t)(tm.tv_sec ^ tm.tv_usec);
uintptr_t seed = _init_random(t ^ (uintptr_t)getpid());
srandom((unsigned int)(seed & 0xFFFFFFFFUL));
}
static inline int random_level() {
int lv = 1;
while (((double)random() / RAND_MAX) < P && lv < MAX_LEVEL) lv++;
return lv;
}
```
未來可引入品質更高的 PRNG 來進行實作。
> 延伸閱讀：[從模除偏差談亂數分布](https://hackmd.io/@sysprog/BkSydKkaJg)
* 引入 `sl_slot` 資料結構
讓每個節點存放多個 `key`。增加 cache 命中率，減少 `malloc/free` 次數，或可以減少 concurrency 寫入操作的開銷。
> 在 Desktop Search 中可以設計讓 skip list 節點只存目錄路徑，`sl_slot` 存目錄下所有檔案的資料。
* 多執行緒設計
將資料結構擴充為可在多執行緒環境下安全運行，甚至實現高並行。可能引入 Lazy list, Fine-grained locking, 甚至 lock-free 的設計。
> 延伸閱讀：[A Provably Correct Scalable Concurrent Skip List](https://people.csail.mit.edu/shanir/publications/OPODIS2006-BA.pdf),
[The Art of Multiprocessor Programming Chapter 14 - Skiplists and Balanced Search
](https://cs.ipm.ac.ir/asoc2016/Resources/Theartofmulticore.pdf), https://arxiv.org/html/2403.04582v2#S11
:::warning
可以思考 doubly linked list 的設計在多執行緒的環境中如何實作，因為 doubly linked list 在多執行緒下環境下，每次的插入、刪除，都要考慮到 `prev` 指標的操作，需要鎖住的節點會比 singly linked list 還要多。除了效能上的開銷比較大，在實作的難度也高許多。
:::
:::success
方案：
1. 研讀 [Userspace RCU](https://liburcu.org/) 並加入實作。
2. 不去使用 `prev`，只讓 `head` 保有 `prev` ，存取持有最大值的節點。
3. Insert 時仍然是 Doubly linked list 的 insert，remove 時只把 `next` 抹消，讓 `next` 指向 `NULL`，保留 `prev`，等到要 delete 的時候再利用 `prev` 指標往回遍歷，找到哪些節點的 `next` 值為 `NULL`，再去刪除。
:::
* Cache-Oblivious 的 skip list 設計
研究 Cache-Oblivious skip list 的資料結構，透過記憶體連續的存取模式增加 cache 命中率，降低記憶體延遲對查詢與更新效能的影響。
Sign in with Wallet
Connect another wallet