---
# System prepended metadata

title: Skip list & Prefix Search 在 C 語言上的簡單實作
tags: [linux2021, C, skip list]

---

# 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 命中率，降低記憶體延遲對查詢與更新效能的影響。

