Libx uthash ドキュメント

    このページの内容

    v2.4.0, June 2026

    GitHubのプロジェクトページはこちらです。

    はじめに

    Cの構造体向けの汎用的な連結リストマクロが、uthashの utlist.h に含まれています。自分のCプログラムで使うには、utlist.h をソースディレクトリにコピーし、プログラムで使用するだけです。

    #include "utlist.h"

    これらのマクロは、連結リストの基本操作である要素の追加と削除、ソート、反復処理をサポートします。

    ダウンロード

    ヘッダーファイル utlist.h をダウンロードするには、https://github.com/troydhanson/uthash のリンクからuthashをクローンするかZIPファイルを取得し、src/ サブディレクトリを確認してください。

    BSDライセンス

    このソフトウェアは修正版BSDライセンスで提供されています。自由に利用できるオープンソースソフトウェアです。

    プラットフォーム

    utlist マクロは、次の環境でテストされています。

    • Linux,

    • Mac OS X

    • Windows（Visual Studio 2008、Visual Studio 2010、またはCygwin/MinGWを使用）

    utlistの使い方

    リストの種類

    次の3種類の連結リストをサポートします。

    • 単方向連結リスト

    • 双方向連結リスト

    • 循環双方向連結リスト

    効率

    先頭への要素追加
    すべてのリスト形式で定数時間です。

    末尾への追加
    単方向連結リストではO(n)、双方向連結リストでは定数時間です（utlistの双方向連結リスト実装は head->prev に末尾へのポインターを保持するため、末尾への追加を定数時間で行えます）。

    要素の削除
    単方向連結リストではO(n)、双方向連結リストでは定数時間です。

    ソート
    すべてのリスト形式でO(n log(n)) です。

    順序を保った挿入（ソート済みリスト向け）
    すべてのリスト形式でO(n) です。

    反復処理、カウント、検索
    すべてのリスト形式でO(n) です。

    リストの要素

    next ポインターを含む構造体であれば、任意の構造体にこれらのマクロを使えます。双方向連結リストを作る場合は、要素に prev ポインターも必要です。

    typedef struct element {
    char *name;
    struct element *prev; /* needed for a doubly-linked list only */
    struct element *next; /* needed for singly- or doubly-linked lists */
} element;

    構造体の名前は自由に付けられます。上の例では element としています。1つのリスト内では、すべての要素が同じ型でなければなりません。

    prev/nextの名前を自由に指定する

    prev と next のポインターには別の名前を付けられます。その場合は、同じように動作し、これらの名前を追加の引数として受け取るマクロ群を使えます。

    リストの先頭ポインター

    リストの先頭ポインターは、単に要素の構造体へのポインターです。名前は自由に付けられます。必ず NULL で初期化してください。

    element *head = NULL;

    リストの操作

    リストは、要素の挿入と削除、ソート、反復処理をサポートします。

    単方向連結 双方向連結 循環双方向連結

    LL_PREPEND(head,add);

    DL_PREPEND(head,add);

    CDL_PREPEND(head,add);

    LL_PREPEND_ELEM(head,ref,add);

    DL_PREPEND_ELEM(head,ref,add);

    CDL_PREPEND_ELEM(head,ref,add);

    LL_APPEND_ELEM(head,ref,add);

    DL_APPEND_ELEM(head,ref,add);

    CDL_APPEND_ELEM(head,ref,add);

    LL_REPLACE_ELEM(head,del,add);

    DL_REPLACE_ELEM(head,del,add);

    CDL_REPLACE_ELEM(head,del,add);

    LL_APPEND(head,add);

    DL_APPEND(head,add);

    CDL_APPEND(head,add);

    LL_INSERT_INORDER(head,add,cmp);

    DL_INSERT_INORDER(head,add,cmp);

    CDL_INSERT_INORDER(head,add,cmp);

    LL_CONCAT(head1,head2);

    DL_CONCAT(head1,head2);

    CDL_CONCAT(head1,head2);

    LL_DELETE(head,del);

    DL_DELETE(head,del);

    CDL_DELETE(head,del);

    LL_REVERSE(head);

    DL_REVERSE(head);

    CDL_REVERSE(head);

    LL_SORT(head,cmp);

    DL_SORT(head,cmp);

    CDL_SORT(head,cmp);

    LL_FOREACH(head,elt) {…}

    DL_FOREACH(head,elt) {…}

    CDL_FOREACH(head,elt) {…}

    LL_FOREACH_SAFE(head,elt,tmp) {…}

    DL_FOREACH_SAFE(head,elt,tmp) {…}

    CDL_FOREACH_SAFE(head,elt,tmp1,tmp2) {…}

    LL_SEARCH_SCALAR(head,elt,mbr,val);

    DL_SEARCH_SCALAR(head,elt,mbr,val);

    CDL_SEARCH_SCALAR(head,elt,mbr,val);

    LL_SEARCH(head,elt,like,cmp);

    DL_SEARCH(head,elt,like,cmp);

    CDL_SEARCH(head,elt,like,cmp);

    LL_LOWER_BOUND(head,elt,like,cmp);

    DL_LOWER_BOUND(head,elt,like,cmp);

    CDL_LOWER_BOUND(head,elt,like,cmp);

    LL_COUNT(head,elt,count);

    DL_COUNT(head,elt,count);

    CDL_COUNT(head,elt,count);

    Prependは、既存のリスト先頭要素があればその前に要素を挿入し、新しい要素をリストの先頭にする操作です。Appendは、リストの末尾に要素を追加し、新しい末尾要素にする操作です。Concatenateは、正しく構築された2つのリストを受け取り、2つ目のリストを1つ目の末尾に連結します（Visual Studio 2008は LL_CONCAT と DL_CONCAT をサポートしませんが、VS2010では使えます）。先頭要素ではなく任意の要素の前に挿入するには、_PREPEND_ELEM マクロ群を使います。任意の要素の後ろに追加するには、_APPEND_ELEM マクロ群を使います。任意のリスト要素を別の要素で置き換えるには、_REPLACE_ELEM マクロ群を使います。

    sort操作は、メモリー内の要素を移動しません。各要素の prev と next ポインターを変更して、リストの順序だけを調整します。また、ソートによってリストの先頭が別の要素を指すように変わることがあります。

    foreach操作を使うと、リストの先頭から末尾まで簡単に反復処理できます。使い方の例を下に示します。もちろん、prev と next ポインターを直接使い、foreachマクロの代わりにすることもできます。反復処理中にリスト要素を削除する予定がある場合は、foreach_safe操作を使ってください。

    search操作は、特定の要素を探す反復処理を簡潔に書くためのものです。手動で反復し、各要素を調べる場合より速くなるわけではありません。2つの形式があり、「scalar」版は指定した構造体メンバーの単純な等値比較で要素を探します。汎用版は、cmp 関数でリスト内の他のすべての要素と比較する対象の要素を受け取ります。

    lower_bound操作は、指定した like 要素以下となるリストの最初の要素を、指定した cmp 関数に従って探します。lower_bound操作は、elt を、LL_APPEND_ELEM に渡すのに適した値に設定します。つまり、適切な挿入位置がリストの先頭なら elt=NULL、elt=p なら適切な挿入位置は p と p->next の間です。

    count操作は、リストを反復処理し、渡されたカウンターを増加させます。

    上の表に示したパラメーターは、次のとおりです。

    head
    リストの先頭ポインター（リスト要素の構造体へのポインター）。

    add
    リストに追加する要素の構造体へのポインター。

    del
    リストから置き換える、または削除する要素の構造体へのポインター。

    elt
    反復処理マクロでは、各リスト要素が順に代入されるポインター（使用例を参照）。検索マクロでは、結果を受け取るポインター。

    ref
    前への挿入や後ろへの追加の基準となる要素。ref がNULL値のポインターなら、_PREPEND_ELEM()では新しい要素をリストの末尾に追加し、_APPEND_ELEM()では先頭に挿入します。ref はポインター変数の名前でなければならず、NULLを直接指定することはできません。その場合は、代わりに_PREPEND()や_APPEND()のマクロ群を使ってください。

    like
    elt と同じ型の要素ポインターで、検索マクロが一致する要素を探す対象です（一致が見つかれば elt に格納します）。一致は、指定した cmp 関数で判定します。

    cmp
    比較する2つの要素の構造体へのポインターを引数として受け取る比較関数へのポインター。この比較関数は、負、ゼロ、正の int を返さなければなりません。それぞれ、1つ目の要素が2つ目より前、同じ順序、後に並ぶことを表します（つまり、strcmp と同じ規約です）。Visual Studio 2008では、2つの引数を void * として宣言してから実際の型にキャストし直す必要がある場合があります。

    tmp
    elt と同じ型のポインター。内部で使用されます。初期化は不要です。

    mbr
    スカラー検索マクロで、elt 構造体内のメンバー名を指定します。そのメンバーの値を、== で val と等しいか調べます。

    val
    スカラー検索マクロで、探す要素の構造体メンバー field の値を指定します。

    count
    リストの長さが代入される整数。

    使用例

    このサンプルプログラムは、テキストファイルから名前を読み取り（1行に1つの名前）、各名前を双方向連結リストの末尾に追加します。その後、ソートして表示します。

    双方向連結リスト

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "utlist.h"

#define BUFLEN 20

typedef struct el {
    char bname[BUFLEN];
    struct el *next, *prev;
} el;

int namecmp(el *a, el *b) {
    return strcmp(a->bname,b->bname);
}

el *head = NULL; /* important- initialize to NULL! */

int main(int argc, char *argv[]) {
    el *name, *elt, *tmp, etmp;

    char linebuf[BUFLEN];
    int count;
    FILE *file;

    if ( (file = fopen( "test11.dat", "r" )) == NULL ) {
        perror("can't open: ");
        exit(-1);
    }

    while (fgets(linebuf,BUFLEN,file) != NULL) {
        if ( (name = (el *)malloc(sizeof *name)) == NULL) exit(-1);
        strcpy(name->bname, linebuf);
        DL_APPEND(head, name);
    }
    DL_SORT(head, namecmp);
    DL_FOREACH(head,elt) printf("%s", elt->bname);
    DL_COUNT(head, elt, count);
    printf("%d number of elements in list\n", count);

    memcpy(&etmp.bname, "WES\n", 5);
    DL_SEARCH(head,elt,&etmp,namecmp);
    if (elt) printf("found %s\n", elt->bname);

    /* now delete each element, use the safe iterator */
    DL_FOREACH_SAFE(head,elt,tmp) {
      DL_DELETE(head,elt);
      free(elt);
    }

    fclose(file);

    return 0;
}

    prevとnext以外のフィールド名

    prev と next のフィールドに別の名前を付けている場合は、別のマクロ群を使う必要があります。これらは通常のマクロと同じように動作しますが、追加のパラメーターとしてフィールド名を受け取ります。

    この「フィールド名を自由に指定できる」マクロ群を下に示します。いずれも名前の末尾が 2 です。それぞれ末尾に 2 がない対応するマクロと同じように動作しますが、該当する prev と next のフィールド名を最後の引数として受け取ります。

    単方向連結 双方向連結 循環双方向連結

    LL_PREPEND2(head,add,next);

    DL_PREPEND2(head,add,prev,next);

    CDL_PREPEND2(head,add,prev,next);

    LL_PREPEND_ELEM2(head,ref,add,next);

    DL_PREPEND_ELEM2(head,ref,add,prev,next);

    CDL_PREPEND_ELEM2(head,ref,add,prev,next);

    LL_APPEND_ELEM2(head,ref,add,next);

    DL_APPEND_ELEM2(head,ref,add,prev,next);

    CDL_APPEND_ELEM2(head,ref,add,prev,next);

    LL_REPLACE_ELEM2(head,del,add,next);

    DL_REPLACE_ELEM2(head,del,add,prev,next);

    CDL_REPLACE_ELEM2(head,del,add,prev,next);

    LL_APPEND2(head,add,next);

    DL_APPEND2(head,add,prev,next);

    CDL_APPEND2(head,add,prev,next);

    LL_INSERT_INORDER2(head,add,cmp,next);

    DL_INSERT_INORDER2(head,add,cmp,prev,next);

    CDL_INSERT_INORDER2(head,add,cmp,prev,next);

    LL_CONCAT2(head1,head2,next);

    DL_CONCAT2(head1,head2,prev,next);

    CDL_CONCAT2(head1,head2,prev,next);

    LL_DELETE2(head,del,next);

    DL_DELETE2(head,del,prev,next);

    CDL_DELETE2(head,del,prev,next);

    LL_REVERSE2(head,next);

    DL_REVERSE2(head,prev,next);

    CDL_REVERSE2(head,prev,next);

    LL_SORT2(head,cmp,next);

    DL_SORT2(head,cmp,prev,next);

    CDL_SORT2(head,cmp,prev,next);

    LL_FOREACH2(head,elt,next) {…}

    DL_FOREACH2(head,elt,next) {…}

    CDL_FOREACH2(head,elt,next) {…}

    LL_FOREACH_SAFE2(head,elt,tmp,next) {…}

    DL_FOREACH_SAFE2(head,elt,tmp,next) {…}

    CDL_FOREACH_SAFE2(head,elt,tmp1,tmp2,prev,next) {…}

    LL_SEARCH_SCALAR2(head,elt,mbr,val,next);

    DL_SEARCH_SCALAR2(head,elt,mbr,val,next);

    CDL_SEARCH_SCALAR2(head,elt,mbr,val,next);

    LL_SEARCH2(head,elt,like,cmp,next);

    DL_SEARCH2(head,elt,like,cmp,next);

    CDL_SEARCH2(head,elt,like,cmp,next);

    LL_LOWER_BOUND2(head,elt,like,cmp,next);

    DL_LOWER_BOUND2(head,elt,like,cmp,next);

    CDL_LOWER_BOUND2(head,elt,like,cmp,next);

    LL_COUNT2(head,elt,count,next);

    DL_COUNT2(head,elt,count,next);

    CDL_COUNT2(head,elt,count,next);