Sorting linked lists utility in C

"sort_linked_list": Sorting linked lists utility in C
Happy Hacking!

sort_linked_list: リンクト・リストの高速なソートを行うユーティリティ

この C 言語ユーティリティは、リング・バッファも含む単方向および双方向リンクト・リストを高速にソートします。高速ソートを実際に行うのはクイック・ソート・アルゴリズムを実装した C 言語標準ライブラリ "qsort()" です。ノードがデータ要素をポインタ参照している場合には、リスト中のノードのリンク順序は変えずにソートすることも出来ます (この利用方法のほうが高速に動作します)。

API を使用するためのヘッダは sort_linked_list.h で、API の実装は sort_linked_list.c です。API の説明は、この文書で後述しています。

テスト・プログラムとして unit_test.c も記述しました。このテスト・プログラムを Cygwin 上で実行し次の点について検証しました。

バブル・ソートとの処理時間の比較。もちろん、この API のほうが高速に処理します。
バブル・ソートでは 80000 件のノードを持つリストで処理時間が 511.632 秒かかるのに対して、Quick-sort では 0.134 乃至 0.071 秒でソートしています。

これらのソースコードをコンパイルするために Makefile を使用できます。ライセンスは GNU Public License とします。

リスト中のノードのリンク順序を変えずにソートする

ノードの構造体がデータ要素をポインタで指している場合は、ノードのリンク順序を変えずにそれぞれのノードが指すデータ要素だけを並べ変えることが出来ます。

このためには、API の第 5 引数 (get_datum_addr) にノード・ポインタからデータ要素アドレスを返す関数を、第 6 引数 (get_datum_fld_addr_on_node) にノード構造体のデータ要素ポインタ・メンバのアドレスを返す関数を渡し、第 8 引数 (set_next) には NULL を渡します。
リストが双方向リンクされている場合は、第 4 引数 (prev) にノードの前のノードのアドレスを返す関数を渡し、第 9 引数 (set_prev) にノードの前のノードのアドレスをセットする関数を渡してください。また、リスト構造体のアドレスをそのリンク順序でインデックスした配列を必要とするならば、第 10 引数にリスト構造体アドレス配列へのポインタを渡してください。

下の囲みの例では sort_datum_in_linked_list マクロを使用しています。

       #define KEY_LEN 10 /* キー文字列は 9 文字とする */
       struct datum_t { /* データ要素の定義 */
           char  key[KEY_LEN]; /* キー文字列 */
           long  value;        /* データ値 */
       };
       struct list_t { /* ノードの定義 */
           struct list_t  *prev, * next; /* 双方向リンク */
           struct datum_t *data; /* データ要素へのポインタ */
       } *list;
       #define MAX_NODES 10000 /* リストの挿入する最大ノード数 */
                  :
                  :
       void *next(const void *node)
       {
           return ((struct list_t *)node)->next;
       }
       void *prev(const void *node)
       {
           return ((struct list_t *)node)->prev;
       }
       void *set_prev(void *node. const void *prev)
       {
           ((struct list_t *)node)->prev = (struct list_t *)prev;
           return node;
       }
       void *get_datum_addr(const void *node)
       {
           return (void *)(((struct list_t *)node)->data);
       }
       void *get_datum_fld_addr_on_node(const void *node)
       {
           return (void *)(&(((struct list_t *)node)->data));
       }
       int cmp_datum(const void *data1, const void *data2)
       {
           return strncmp((*((struct datum_t **)data1))->key
                        , (*((struct datum_t **)data2))->key
                        , KEY_LEN
                        );
       }
                  :
                  :
       {
           ssize_t nodes_number; /* リストに挿入したノードの数 */
           struct list_t *list, **index = NULL;
                  :
           /* リスト構造 list にデータ要素を指しているノードを
            * 挿入する...
            */
                  :
           /* リスト構造の並び順を変えずにノードが指す
            * データ位置だけが変わる
            */
           sort_datum_in_linked_list(list
                                   , nodes_number
                                   , next
                                   , prev
                                   , get_datum_addr
                                   , get_datum_fld_addr_on_node
                                   , cmp_datum
                                   , set_prev
                                   , &index
                                   );
                  :
           free(index); index = NULL; /* リストが不要になった際、
                                       * インデックス配列に獲得した
                                       * 動的メモリを必ず解放する
                                       */
                  :
       }

一方、ノード構造体にデータ内容を展開するメンバも含めている場合は、上の方法は使用できません。ノードのリンク順序を並べ替えることでソートを実行することになります。

第 5, 6 引数に NULL を指定し、第 8 引数 (set_next) にノードの次のノードをリンク付ける関数を渡します。また、リンクト・リストが双方向リストの場合には、第 9 引数 (set_prev) にノードの前のノードをリンク付ける関数を渡します。下の囲みの例では sort_nodes_in_linked_list マクロを使用しています。

       #define KEY_LEN 10 /* キー文字列は 9 文字とする */
       struct list2_t { /* データ要素をノードの定義に含めた場合 */
           struct list_t  *prev, * next; /* 双方向リンク */
           /* ここから、データ要素を並べる... */
           char  key[KEY_LEN]; /* キー文字列 */
           long  value;        /* データ値 */
       } *list2;
       #define MAX_NODES 10000 /* リストの挿入する最大ノード数 */
                  :
                  :
       void *next(const void *node)
       {
           return ((struct list_t *)node)->next;
       }
       void *prev(const void *node)
       {
           return ((struct list_t *)node)->prev;
       }
       int cmp_nodes(const void *node1, const void *node2)
       {
           return strncmp((*(struct list2_t **)node1)->key
                        , (*(struct list2_t **)node2)->key
                        , KEY_LEN
                        );
       }
       void *set_next(void *node, const void *next)
       {
           ((struct list2_t *)node)->next =
                                       ((struct list2_t *)next;
       }
       void *set_prev(void *node, const void *prev)
       {
           ((struct list2_t *)node)->prev =
                                       ((struct list2_t *)prev;
       }
                  :
                  :
       {
           ssize_t nodes_number; /* リストに挿入したノードの数 */
           struct list_t *list, **index = NULL;
                  :
           /* リスト構造 list にノードを挿入する... */
                  :
           /* リスト構造の並び順を変えてソートを行う */
           sort_nodes_in_linked_list(list2
                                   , nodes_number
                                   , next
                                   , prev
                                   , cmp_nodes
                                   , set_next
                                   , set_prev
                                   , &index
                                   );
                  :
           free(index); index = NULL; /* リストが不要になった際、
                                       * インデックス配列に獲得した
                                       * 動的メモリを必ず解放する
                                       */
                  :
       }

性能測定の結果

i686 アーキテクチャ (1.1GHz) 上の CYGWIN_ME-4.90 l0n7r5 1.5.17 (0.129/4/2) 2005-05-25 19:38 で測定した性能結果は以下の表のようになりました。

ソート方式	ノード数ごとのソート処理時間 (sec.)
ソート方式	10000	20000	40000	80000
クイック・ソート (リンク順序を変えない)	0.005	0.013	0.032	0.071
クイック・ソート (リンク順序を変える)	0.006	0.021	0.053	0.134
バブル・ソート	3.052	19.772	114.589	511.632

API の説明

リンクト・リストをソートする sort_datum_in_linked_list(), sort_nodes_in_linked_list(), sort_linked_list()

void *sort_datum_in_linked_list(
                   void *list
                 , ssize_t nodes_n
                 , void *(*next)(const void *list)
                 , void *(*prev)(const void *list)
                 , void *(*get_datum_addr)(const void *node)
                 , void *(*get_datum_fld_addr_on_node)(
                                           const void *node)
                 , int (*cmp_nodes_via_ptr2ptr)(
                                         const void *node1
                                       , const void *node2
                                       )
                 , void *(*set_prev)(
                                     void *src_node
                                   , const void *prev_node)
                 , void ***index
                 )
void *sort_nodes_in_linked_list(
                   void *list
                 , ssize_t nodes_n
                 , void *(*next)(const void *list)
                 , void *(*prev)(const void *list)
                 , int (*cmp_nodes_via_ptr2ptr)(
                                         const void *node1
                                       , const void *node2
                                       )
                 , void *(*set_next)(
                                     void *src_node
                                   , const void *next_node)
                 , void *(*set_prev)(
                                     void *src_node
                                   , const void *prev_node)
                 , void ***index
                 )
void *sort_linked_list(
                   void *list
                 , ssize_t nodes_n
                 , void *(*next)(const void *list)
                 , void *(*prev)(const void *list)
                 , void *(*get_datum_addr)(const void *node)
                 , void *(*get_datum_fld_addr_on_node)(
                                           const void *node)
                 , int (*cmp_nodes_via_ptr2ptr)(
                                         const void *node1
                                       , const void *node2
                                       )
                 , void *(*set_next)(
                                     void *src_node
                                   , const void *next_node)
                 , void *(*set_prev)(
                                     void *src_node
                                   , const void *prev_node)
                 , void ***index
                 )

sort_datum_in_linked_list() はデータ要素をを参照するノードのリンク順序を変えずにデータ要素をソートするためのマクロで、sort_nodes_in_linked_list() はリスト・ノードのリンク順序を変えることでソートするためのマクロです。どちらのマクロも sort_linked_list() 関数を呼び出すことになります。

list にソートするリンクト・リストを渡します。nodes_n には list に挿入されているノードの数を渡します。ノード数が不明な場合には UNKNOWN_NUMBER_OF_SORTING_NODES を指定することで API がノード数の計数を行います。next にノードの次のノードのアドレスを返す関数を渡します。cmp_nodes_via_ptr2ptr は 2 つのノードをそのポインターのポインターを介して比較する関数を渡します。これらの引数は必須な引数です。

ソート対象のリンクト・リストが双方向リストの場合は prev にノードの前のノードのアドレスを返す関数を渡し、set_prev にノードの前のノードのアドレスをセットする関数を渡す必要があります。単方向リストの場合、これらの引数には NULL を渡します。

リスト中のノード構造体がデータ要素アドレスを指している場合にノードのリンク順序を変えずにソートを行うには、get_datum_addr にデータ要素アドレスを返す関数を渡し、get_datum_fld_addr_on_node にノード構造上のデータ要素ポインタ・メンバのアドレスを返す関数を渡します。また、set_next には NULL を渡します。

リスト上のノードのリンク順序を並べ替えることでソートする場合には、get_datum_addr と get_datum_fld_addr_on_node に NULL を渡し、set_next に次のノードのアドレスをセットする関数を渡します。

index に、ソートの済んだリストのリンク順序どおりに並んだノードアドレスの配列を出力します。出力する配列は、呼び出し側でノードのインデックスとして使用されることを想定しています。このインデックス配列が不要な場合は、この引数に NULL を渡します。index が指すポインタ配列アドレスを指定しない (index = NULL; としてから &index を渡した) 場合は、API 側で動的にメモリを獲得しますので呼び出し側でメモリ解放 free() を必ず行うようにしてください。

正常終了の場合、ソートされたリストの先頭ノードのアドレスを返します。不正な引数を渡されたりソート用の動的メモリ獲得に失敗した場合、NULL を返し errno にエラー内容を出力します。

エラーが起きた際の errno の値とその意味は以下のとおりです。

EINVAL (22) - 渡された引数が不正です
ENOMEM (12) - ソートを実行するための動的メモリが獲得できません (メモリ不足)

"sort_linked_list": Sorting linked lists utility in C Happy Hacking!

sort_linked_list: リンクト・リストの高速なソートを行うユーティリティ

リスト中のノードのリンク順序を変えずにソートする

性能測定の結果

API の説明

"sort_linked_list": Sorting linked lists utility in C
Happy Hacking!