POSIX Tree Container (tsearch) 避坑指南

August 30, 2024

最近因故發現原來 POSIX 竟然也有提供鍵值容器的函式集(tsearch)，乍看有點意思，於是就打算順手拿來用用。結果不用不知道，一用踩坑踩翻天！花費不少時間的追蹤除錯和閱讀相關說明文件(是的，我最初想說看著挺簡單就沒看了)之後，終於理清相關的用法和避坑指南。

其實 POSIX 容器的使用者應該算是小眾，也不知道留著筆記能幫到誰？也或許幫是過了 N 年之後的我自己吧！另一方面也是意識到這個容器函式庫能夠被設計的坑爹滿滿，因此探討這個程式庫的使用方法，可能在作為程式庫介面設計上的反面教材意義更大！

為什麼要使用 POSIX 容器？

首先我們得先釐清混淆，本文討論的容器，是指資料結構上的 container，就是在程式設計中用來放資料的那個容器，而不是這幾年很流行的那個作業系統虛擬化的那個 Contianer。如果你要關注的是後者的話，那麼可以直接離開了，因為本文與之完全無關！

擺在為何要使用 POSIX 容器的這個問題之前的問題，可能得先問問為何需要呼叫額外的容器程式庫？

這些資料容器就是在資料結構課程上學過的那些：陣列、串列、堆疊、貯列、和鍵值容器。這些極其基本的基礎容器，在現代的幾乎所有高階程式語言中都已經原生的提供了，所以除非有極為特別的考量，否則完全沒有需要捨簡就繁去另外使用一個容器程式庫。因此會產生使用容器程式庫需求的前提，首先就是你所使用的程式語言沒有原生提供容器相關功能，其實大概除了純 C 語言的用戶之外也沒有別人了，這就是為什麼我說這種東西是小眾用途的原因！

好的，現在我們把用戶群體限縮到了 C 語言的使用者。那麼 C 語言用戶為什麼需要一個容器程式庫呢？其實就兩個原因：簡單、方便。

作為 C 語言用戶，想必軟體工程底子是足夠堅實的。雖然資料容器的需求非常常見，但是對於簡單的資料容器，往往程式設計師能夠自己快速造一個出來。舉個最簡單的例子：陣列，訓練有素的設計師不都已經練到閉著眼睛盲打就能完成日常所需的操作了？但是對於複雜一點的容器，比方說雙向串列，難道也是每次用到的時候就重新造一個出來嗎？雖然每次手搓一個串列容器也不是辦不到的事，並且確實有不少工程師平常就是這麼做的，但是你不累嗎？如果再複雜一點，比方說鍵值容器，雖然說以大家的底子也不是造不出來，但想必這個時候已經確實萌生了「找一個現成的來用」的想法了吧！如果你還需要為不同類型的資料都造一個鍵值容器，或者如果你在許多不同的開發案中都有使用這樣容器的需求，那麼我想在你的腦海裡肯定會深深烙下一個想法：「有沒有現成的、可以容納通用格式的容器程式庫可以讓我直接調用？最好前置作業愈簡單愈好！」這，就是通用容器程式庫存在的需求和目的。

那麼除了自己造一個之外，有哪些現成可選的容器函式庫呢？我想這類的東西鐵定不少，而且各庫的特性和適用場合都不太一樣，比方有的很單純且不涉及記憶體配置、有的使用親切容易上手等等。這裡只提及我自己最喜歡也最常使用的幾個現成的程式庫： C++ STL Container、BSD Kernel Container、和本文描述的 POSIX Tree Container。首先 C++ STL Container 確實是來亂的，因為 C 語言根本無法呼叫使用這個東西！不過提出它的用意其實在於：當你有了想要找個容器程式庫的想法的時候，也許該先想的問題是能不能換個程式語言？是否現在這件事情非得用 C 語言來實現不可？

先簡單討論一下一般常用的幾種基本容器類型：陣列、串列、堆疊、貯列、鍵值容器。其中陣列太過簡單單純，用程式語言原生的功能就能直接操作，另外造一個程式庫的話能著墨的地方並不多，產生的效益也很有限，因此一般都還是自己土法煉鋼。串列開始具有一定程度的複雜性，雖然自己也能手搓串列，但能有現成工具可以使用的話也確實能省不少事。堆疊和貯列其實都可視為是加上了一些操作限制的串列，所以它的實現其實完全被串列所覆蓋了；甚至如果對於效能有所苛刻，並且不介意容納資料有限的話，也能完全使用陣列來替代堆疊和貯列的功能。因此堆疊和貯列其實就是串列或陣列的限縮特化版本，其底層實現其實是通用的，可以直接比照。最後，鍵值容器才是全部裡面最複雜也最重要的重點。鍵值容器的底層實現可能是各種二元樹、跳躍串列、雜湊容器、或其他邏輯容器，但上層總歸而言就是提供了「鍵」與「值」(或資料)的對應關係和收納容器，因此在這裡等同視之。其實在大部份的容器程式庫裡，也少有明確區別鍵與值的，而是將其二者視為一個整體進行操作，用 C++ STL 的概念來說的話，就是其實 std::map 的功能完全可以由 std::set 來實現，兩者等同視之的意思。

BSD Kernel Container 顧名思義，是 BSD 核心空間能夠取用的容器程式庫，提供了雙向串列、和紅黑樹的使用介面。雖然說這是在核心程式碼裡面的程式，但因為其本身就是個只有兩個標頭檔實現了全部功能的程式庫，加上也沒用到什麼必須得在核心空間才能取用的特殊功能，因此單獨抽取出來用在使用者空間上也是挺簡單的，這也是我平常所用的 BSD 容器的取得來源。其實 Linux Kernel 也提供了同樣功能的程式庫，也是雙向串列和紅黑樹，也是只需要兩個標頭檔。但是實際使用過後我覺得 Linux Kernel Container 的介面缺乏人性化使用體驗，加上 BSD 的許可證是比較友好有利的，因此成為我當前最愛用也是綜合評價最好用的容器工具。不過畢竟本篇的重點不在於此，所以不會更深入討論 BSD 實現的容器工具。

POSIX 也定義了使用者空間的容器相關介面，提供了二元樹容器(tsearch)、和雜湊容器(hsearch)；不過我嫌棄它的雜湊容器介面設計太垃圾，缺少使用價值，因此這裡只關注二元樹容器。 (關於 POSIX 的雜湊容器為什麼垃圾？改天有心情的話也許再寫一篇去探討吧！) 既然我前面已經給了 BSD 容器這麼高的評價，那麼 POSIX 容器顯然得有些特別的優點，否則就完全沒有介紹它的必要了。 POSIX 容器相比於其他容器程式庫(其實主要對標的是 BSD 容器)，有如下幾個優點：

已內建於支援 POSIX 規格的 C 標準程式庫，包括 Glibc。因此無需特別做什麼設定就可以直接呼叫取用，連將相關標頭檔放置到專案程式碼的合適位置這個動作都不需要；當然，除非你用的 C 程式庫不支援 POSIX，那就另當別論！ (^_^)
使用單純簡便。整個容器有關的操作函式就只有 tsearch()、tfind()、tdelete()、twalk()/twalk_r()、和 tdestroy()，相當單純，使用上也無需要另外定義資料結構、在結構內包含納入它的節點結構等等在使用之前要先完成的動作，輕量使用的話其實相當簡便。

總結 POSIX 容器就是在你有輕量使用需求，不太講究效能、記憶體等計算資源，需要托管的資料也不需要太複雜處理機制的時候，這個接近於原生的容器程式庫或許能成為你考量使用的名單之一；當然它有缺點，簡單而言就是使用邏輯與現代容器介面有差異，不注意之下容易踩坑，而這正是整篇文要論述的重點之一。

前置作業

雖然 POSIX 容器已內建在支援的 C 標準函式庫中，但是在使用前還是有少許事情需要做的：

引用標頭檔 #include <search.h>
定義 _GNU_SOURCE 巨集。

其實 twalk_r() 和 tdestroy() 不是 POSIX 定義的功能，而是 GNU 擴展；但若缺少了這兩函式的話，個人認為會讓容器的實用性大大降低，基本沒法好好正常使用。因此啟用 GNU 擴展在我認為是必須的前置作業。啟用 GNU 擴展只需要定義 _GNU_SOURCE 巨集即可，你可以直接寫在程式碼裡，在引用標頭檔前定義：
```
 #define _GNU_SOURCE
 #include <search.h>
```
當然也可以在整個專案的全局空間裡加入此項定義，以 GCC 為例，需要加入編譯選項：-D_GNU_SOURCE。

函式說明

tsearch()

void* tsearch(
    const void *key, void **rootp, int(*compar)(const void*, const void*));

集搜尋、插入、與建立一個二元樹結構於一身的函式。

使用者應管理維護一個指標變數，這個變數將指向二元樹的根節點；而函式參數 rootp 便是這個指標變數的指標。由於根節點可能在樹的操作過程中產生變更，因此這個指標的值也會處在變化狀態；然而使用者除了判斷其是否為 NULL 之外，基本無需關心該變數的值，因其具體數值是由函式庫來進行管理指派，使用者只需要確保這個指標變數本身在整個樹的生命週期為可用即可：

void *root = NULL;

這個變數的初值應設為 NULL，表示該容器為空；同樣在容器的所有元素都已被移除後，這個指標的值也會變回 NULL (用 tdestroy() 清空的例外)。由於部份函式可能會變更這個指標的數值，因此在呼叫此類函式時便會要求傳入此指標變數的指標。

key 為一個指向使用者自訂資料的指標，為本次操作所要搜尋或插入的目標。注意雖然這個變數使用了 const 修飾，但實際上函式有可能在操作完成後將此變數插入到容器內，因此在記憶體管理等事務上需要注意這件事；至於該變數是否被插入到容器內，可藉由函式返回值來進行判斷。

compar() 為使用者定義資料的比較函式，其規格與 qsort() 相同：函式傳入兩個使用者定義物件的指標，當左物件應排在右物件前面時傳回負值，當左物件應排在右物件後面時傳回正值，當兩物件相等時傳回零。

函式傳回值的型態為 void*，但其並非為使用者定義資料的指標，而是搜尋結果的資訊，這點要注意別被誤導！其傳回的值實際上是一個指向使用者定義資料的指標變數的位址，聽起來饒口，但其實就是指標的指標；也就是說假設使用者定義的資料型態為 UserData 的話，那麼傳回型態應等效為 UserData**。函式傳回值其實理解為容器疊代器(iterator)會更加合適貼切！因此後面說明都將以疊代器稱呼之。

當函式搜尋到與傳入之 key 匹配的節點時，便傳回該節點的疊代器；若容器內無匹配的節點，則函式將會新增節點，並存入 key 變數；若發生其它問題，例如無法配置記憶體，則返回 NULL。因此在函式呼叫後，建議可以比對傳回的疊代器指向之資料指標使否與 key 相同，來判斷其是否已被加入於容器內，並決定是否需要將原輸入的參數 key 銷毀等管理工作。

tfind()

void* tfind(
    const void *key, void *const *rootp, int(*compar)(const void*, const void*));

函式作用為在容器內搜尋節點。所有規格與 tsearch() 相同，除了在搜尋不到符合的節點時，本函式不會插入節點，而是傳回 NULL。

tdelete()

void* tdelete(
    const void *restrict key,
    void **restrict rootp,
    int(*compar)(const void*, const void*));

函式作用為移除容器內的一個節點。 key 為一個指向使用者定義格式資料的指標，用來作為函式比對並找出符合節點的依據； rootp 為容器根節點指標的指標； compar() 為使用者定義資料的比較函式，其規格與 tsearch() 相同。

當在容器內找到與 key 符合的節點，該節點即會被移除容器並釋放資源。返回值為被移除節點的父節點疊代器(沒錯，這個函式不會傳回被移除節點本身的資訊)、或根節點疊代器；若容器內未有與 key 符合的節點，則會返回 NULL。

此函式會自動處理並釋放被移除節點的資源，但是無法處理其內的使用者資料，再加上此函式並不能傳回被移除節點的相關資訊，因此無法像其他的容器那樣先移除節點、再銷毀使用者資料。在使用此函式移除一個節點時，正確的做法應是先搜尋容器內欲將移除的節點，然後釋放該節點內的使用者資料，然後才是呼叫此函式移除該節點。

twalk()

void twalk(
    const void *root,
    void(*action)(const void *nodep, VISIT which, int depth));

函式作用為遍歷容器內所有節點。 root 為容器根節點，action() 為當每走訪一個節點時會呼叫的通知函式。

走訪通知函式 action() 的參數 nodep 為該節點的疊代器，亦及指向該節點使用者結構的指標的指標； which 為一個列舉參數，列舉值參考下面的 VISIT 定義，其作用為指出目前走訪該節點是採用哪一種走訪方式； depth 則指出該節點之於樹結構上的深度，其中根節點為 0，並往下層遞增。

typedef enum
{
    preorder,
    postorder,
    endorder,
    leaf
} VISIT;

其中要特別注意，VISIT 所定義的走訪類型和一般在資料結構教科書上學到的類型並不相合，初使用者可能會因而被誤導！

leaf: 即指出該節點為樹的葉節點，這部份沒什麼爭議。
preorder: 同教科書上的 preorder (前序)，即先走訪中間，然後左邊，然後右邊。
postorder: 其實為教科書上的 inorder (中序)，即先走訪左邊，然後中間，然後右邊。
endorder: 其實為教科書上的 postorder (後序)，即先走訪左邊，然後右邊，然後中間。

因為 twalk() 會採用不同的方式都走訪一遍，所以實際上一個節點可能會被訪問多次，這點在使用上也需要注意！詳細來說，葉節點只會被走訪一次，但除了葉節點以外的其它節點則會被走訪三次。因此在使用此走訪函式時，應先檢查 which 參數，並略過那些你不關心的型式的重複走訪呼叫。例如若我希望使用中序走訪，則應檢查當 which 為 postorder 或 leaf 的時候才進行處理，並忽略其他類型的走訪呼叫。

最後要提醒的是在 action() 裡、以及在 twalk() 的呼叫過程中，不要去改變節點的搜索鍵屬性，亦不應對容器進行插入、刪除等操作，以避免容器內部狀態邏輯錯亂。

twalk_r()

(此功能為 GNU 擴展)

void twalk_r(
    const void *root,
    void(*action)(const void *nodep, VISIT which, void *closure),
    void *closure);

此函式功能與 twalk() 相同，函式參數和回呼函式的參數定義基本都相同，請直接參考 twalk() 相關說明；不同的部份是本函式增加了物件導向的相容性。

action() 函式取消了 depth 參數，並以 closure 參數取代之，其即為呼叫 twalk_r() 時所傳入的 closure 參數，其值和意義由使用者定義。

tdestroy()

(此功能為 GNU 擴展)

void tdestroy(void *root, void(*free_node)(void *nodep));

函式作用為一次性銷毀一個容器。

root 為容器根節點，函式即會釋放所有該根節點所指向的容器資源。至於使用者定義的資料則需透過使用者定義的 free_node() 函式進行處理，注意其中 nodep 參數即為指向使用者資料的指標，而不是疊代器(指向資料的指標的指標)！呼叫 tdestroy() 必須指派 free_node() 函式(不能為 NULL)，如果使用者的資料並不需要進行額外的處理，也應傳入一個實際上沒做任何事的函式供呼叫。

此功能為 GNU 擴展函式，若不使用或無法使用此函式，則按照 POSIX 的定義只能不斷呼叫 tdelete() 不斷刪除節點直到容器為空為止！

範例

#define _GNU_SOURCE
#include <stdio.h>
#include <search.h>

typedef int UserData;

static
int compare_user_data(const void *l, const void *r)
{
    return *(const UserData*)l - *(const UserData*)r;
}

static
const char* get_visit_label(VISIT which)
{
    switch(which)
    {
    case preorder:
        return "preorder";

    case postorder:
        return "postorder";

    case endorder:
        return "endorder";

    case leaf:
        return "leaf";

    default:
        return "unknown";
    }
}

static
void on_posix_node(const void *nodep, VISIT which, int depth)
{
    const UserData* const* iter = nodep;
    printf("Walk on node: which=%s,\tdepth=%d,\tvalue=%d\n",
        get_visit_label(which), depth, **iter);
}

static
void on_gnu_node(const void *nodep, VISIT which, void *closure)
{
    const UserData* const* iter = nodep;
    printf("Walk on node: which=%s,\tuser-arg=\"%s\",\tvalue=%d\n",
        get_visit_label(which), (char*) closure, **iter);
}

static
void on_free_node(void *nodep)
{
    const UserData *node = nodep;
    printf("Free on node: value=%d\n", *node);
}

int main(void)
{
    UserData elements[] = { 2, 8, 3, 9, 4, 6, 1, 7, 11, 5, 0, 10 };
    int element_num = sizeof(elements)/sizeof(elements[0]);
    void *root = NULL;

    printf("Build tree\n");
    for(int i = 0; i < element_num; ++i)
    {
        UserData **iter = tsearch(&elements[i], &root, compare_user_data);
        printf("Insert: new-node=%d, value=%d\n",
            *iter == &elements[i], **(UserData**)iter);
    }
    printf("\n");

    printf("Find nodes\n");
    {
        UserData key = 7;
        UserData **iter = tfind(&key, &root, compare_user_data);
        printf("Find key=%d, ret-iter=%p, value=%d\n",
            key, iter, iter ? **iter : -1);
    }
    {
        UserData key = 28;
        UserData **iter = tfind(&key, &root, compare_user_data);
        printf("Find key=%d, ret-iter=%p, value=%d\n",
            key, iter, iter ? **iter : -1);
    }
    printf("\n");

    printf("Erase nodes\n");
    {
        UserData key = 6;
        UserData **iter = tdelete(&key, &root, compare_user_data);
        printf("Erase key=%d, ret-iter=%p, ret-value=%d\n",
            key, iter, iter ? **iter : -1);
    }
    {
        UserData key = 24;
        UserData **iter = tdelete(&key, &root, compare_user_data);
        printf("Erase key=%d, ret-iter=%p, ret-value=%d\n",
            key, iter, iter ? **iter : -1);
    }
    printf("\n");

    printf("Walk through (POSIX)\n");
    twalk(root, on_posix_node);
    printf("\n");

    printf("Walk through (GNU)\n");
    twalk_r(root, on_gnu_node, "Hallo!");
    printf("\n");

    printf("Release tree\n");
    tdestroy(root, on_free_node);
    printf("\n");

    return 0;
}

執行結果：

Build tree
Insert: new-node=1, value=2
Insert: new-node=1, value=8
Insert: new-node=1, value=3
Insert: new-node=1, value=9
Insert: new-node=1, value=4
Insert: new-node=1, value=6
Insert: new-node=1, value=1
Insert: new-node=1, value=7
Insert: new-node=1, value=11
Insert: new-node=1, value=5
Insert: new-node=1, value=0
Insert: new-node=1, value=10

Find nodes
Find key=7, ret-iter=0x555c42174790, value=7
Find key=28, ret-iter=(nil), value=-1

Erase nodes
Erase key=6, ret-iter=0x555c42174750, ret-value=7
Erase key=24, ret-iter=(nil), ret-value=-1

Walk through (POSIX)
Walk on node: which=preorder,	depth=0,	value=7
Walk on node: which=preorder,	depth=1,	value=3
Walk on node: which=preorder,	depth=2,	value=1
Walk on node: which=leaf,	depth=3,	value=0
Walk on node: which=postorder,	depth=2,	value=1
Walk on node: which=leaf,	depth=3,	value=2
Walk on node: which=endorder,	depth=2,	value=1
Walk on node: which=postorder,	depth=1,	value=3
Walk on node: which=preorder,	depth=2,	value=4
Walk on node: which=postorder,	depth=2,	value=4
Walk on node: which=leaf,	depth=3,	value=5
Walk on node: which=endorder,	depth=2,	value=4
Walk on node: which=endorder,	depth=1,	value=3
Walk on node: which=postorder,	depth=0,	value=7
Walk on node: which=preorder,	depth=1,	value=10
Walk on node: which=preorder,	depth=2,	value=8
Walk on node: which=postorder,	depth=2,	value=8
Walk on node: which=leaf,	depth=3,	value=9
Walk on node: which=endorder,	depth=2,	value=8
Walk on node: which=postorder,	depth=1,	value=10
Walk on node: which=leaf,	depth=2,	value=11
Walk on node: which=endorder,	depth=1,	value=10
Walk on node: which=endorder,	depth=0,	value=7

Walk through (GNU)
Walk on node: which=preorder,	user-arg="Hallo!",	value=7
Walk on node: which=preorder,	user-arg="Hallo!",	value=3
Walk on node: which=preorder,	user-arg="Hallo!",	value=1
Walk on node: which=leaf,	user-arg="Hallo!",	value=0
Walk on node: which=postorder,	user-arg="Hallo!",	value=1
Walk on node: which=leaf,	user-arg="Hallo!",	value=2
Walk on node: which=endorder,	user-arg="Hallo!",	value=1
Walk on node: which=postorder,	user-arg="Hallo!",	value=3
Walk on node: which=preorder,	user-arg="Hallo!",	value=4
Walk on node: which=postorder,	user-arg="Hallo!",	value=4
Walk on node: which=leaf,	user-arg="Hallo!",	value=5
Walk on node: which=endorder,	user-arg="Hallo!",	value=4
Walk on node: which=endorder,	user-arg="Hallo!",	value=3
Walk on node: which=postorder,	user-arg="Hallo!",	value=7
Walk on node: which=preorder,	user-arg="Hallo!",	value=10
Walk on node: which=preorder,	user-arg="Hallo!",	value=8
Walk on node: which=postorder,	user-arg="Hallo!",	value=8
Walk on node: which=leaf,	user-arg="Hallo!",	value=9
Walk on node: which=endorder,	user-arg="Hallo!",	value=8
Walk on node: which=postorder,	user-arg="Hallo!",	value=10
Walk on node: which=leaf,	user-arg="Hallo!",	value=11
Walk on node: which=endorder,	user-arg="Hallo!",	value=10
Walk on node: which=endorder,	user-arg="Hallo!",	value=7

Release tree
Free on node: value=0
Free on node: value=2
Free on node: value=1
Free on node: value=5
Free on node: value=4
Free on node: value=3
Free on node: value=9
Free on node: value=8
Free on node: value=11
Free on node: value=10
Free on node: value=7

檢討與改善方案

依據我的使用經驗，POSIX 容器最大的問題在於介面設計上不符合人性直覺，且處處存在誤導效果。首先就是那一堆的 void* 讓我以為是我的自訂資料的指標，在引發了大量的 segmentation fault 和花費大量時間的追蹤除錯後，我才發現了問題之所在。

然後它的訪問方式也是一大嘈點，不是提供疊代器讓使用者可以用個 for 迴圈逐步訪問，能夠自由操作其它資源，並能自己決定什麼時候終止。它需要透過一個全部走訪呼叫一次走訪所有的節點，非葉節點還重複走訪了多次，而這個坑也讓我給踩了！因為要一次走訪全部節點，不只使用者不能控制走訪流程，還必須透過回呼函式進行相關處理；回呼函式也不是完全不行，在 GNU 擴展的加持下，我仍能夠完成各種需要的操作而不發生衝突，但是不方便！為了在回呼函式裡面可以取用其它相關資源，我需要定義、建立、並傳遞一個結構，雖然說這是在 C 語言底下常見的物件導向操作方式，但如果是採用了疊代器訪問的方案，完全可以避免掉冗餘的複雜度，也不用在 C 程式碼的函式外全域空間去定義可能就使用了一次的結構。

此外它關於走訪方式的定義與一般的理解認知不同這點絕對是個坑！我不清楚 twalk() 對於走訪定義和資料教科書不同是存在什麼歷史遺留因素，但是它產生的影響副作用絕對足夠忽悠第一次嘗試它的現代人。在 twalk() 的回呼函式中還存在無用的參數。雖然重複走訪同一個節點的設計很讓人出乎意料，但在此行為前提之下，which 至少還提供了使用者是否要忽略本次回呼的依據；那麼另一個參數 depth 就真的不知道意義何在了！站在一個容器使用者的角度，其實通常壓根不在意我的資料現在到底放在第幾層節點？這讓容器內部的實現自己去處理就好了！甚至我也不在乎你到底是用紅黑樹、AVL 樹、還是什麼樹來實做的？程式庫需要提供的就只是為使用者建立鍵與值的對應關係，提供以鍵查詢、以及循序訪問的方式即可！還好在 GNU 的擴展中把這個無用的參數給取消了，替換成了更加有用的 closure 參數。

綜合我在使用這些函式時所踩的坑，的確你可以歸咎於我在使用它之前沒有先仔細閱讀它的說明文件，並且事實上這些詳細的內容、定義、和規範都已經登載在它的說明文件裡；所以這裡總結出來的第一個檢討就是：在使用一個功能前，要先閱讀過它的相關說明文件！ 但是遇到的這些問題確實也指出了它的設計不符合操作直覺，是為介面設計不良的示範教案！

那麼如果讓我來定義操作介面的話，我會如何定義呢？下面就來給出相同的函式集在我修改之後的介面長相。這裡我只簡單的修改了函式介面的宣告方式，不涉及函式行為的變更、或整體程式庫結構的更動；因為如果能夠更動的話，我會想要直接設計全新的程式庫介面。同時也是順道展現一下文字的威力，看看同樣的東西改個介面表現型式就能夠產生多大的改善效果！ (相反的，光是亂命名也可以產生很強的破壞力，願所有程式設計行業的設計師都能謹記妥善命名)

typedef void* troot_t;

/*
 * 如果考量到相容性的話，其實 VISIT 不能更動！
 * 雖然原先的定義不符合當下的直覺，但若擅自「修正」定義的話，
 * 反會造成許多已存在的程式碼出現異常行為的相容性問題；
 * 但如果我們假設這個問題不存在的話，那麼就能更改成下列的名稱和順序。
 */
typedef enum
{
    preorder,
    indorder,
    postorder,
    leaf
} VISIT;

void** tsearch(
    void *key,
    troot_t *root,
    int(*compar)(const void*, const void*));

void** tfind(
    const void *key,
    troot_t const* root,
    int(*compar)(const void*, const void*));

void** tdelete(
    const void *restrict key,
    troot_t *root,
    int(*compar)(const void*, const void*));

void twalk(
    const troot_t root,
    void(*action)(const void **node, VISIT which, int depth));

void twalk_r(
    const troot_t root,
    void(*action)(const void **node, VISIT which, void *closure),
    void *closure);

void tdestroy(troot_t root, void(*free_node)(void *node));

參考資料

https://man7.org/linux/man-pages/man3/twalk_r.3.html

上一篇：「在 Windows 上架設 SSH 服務(使用 Git Bash)」
下一篇：「這時代的 C 語言還有什麼用處呢？」