単連結リストの整列 #15 要素の保持するデータ型が任意のものに対応した単連結リストの整列関数

lsort.hで宣言したインタフェイスに基づいた整列関数を実装する。

lsort.c

#include <stddef.h>
#include "lsort.h"

typedef struct tag_node node_t;
struct tag_node {
    node_t *next;
};

static void node_swap(node_t *n)
{
    node_t *p, *q;
    if (n == NULL || (p = n->next) == NULL || (q = p->next) == NULL) return;
    n->next = q;
    p->next = q->next;
    q->next = p;
}

void lsort(void *base_ptr, int (*issup)(const void *, const void *, void *), void *arg)
{
    node_t *b, *p, *q;
    if (base_ptr == NULL || (b = *(node_t **)base_ptr) == NULL || b->next == NULL) return;
    for (q = NULL; q != b->next; q = p->next) {
        for (p = (node_t *)&b; p->next->next != q; p = p->next) {
            if (issup(p->next, p->next->next, arg)) node_swap(p);
        }
    }
    *(node_t **)base_ptr = b;
}

整列関数lsortが想定する単連結リストの要素は、
lsort.c内で定義しているnode_t型のように、
最初のメンバが次の要素へのポインタであるような構造体で定義されている。
前に述べたように、単連結リストの先頭の要素へのポインタへのポインタをlsortの第一引数base_ptrとして渡す。
二つの要素の順位関係は関数として定義し、lsortの第二引数に関数ポインタとして渡す。
この関数issupは三つの引数を取り、始めの二つの引数は順位を比較すべき二つの要素へのポインタであり、
第一引数が第二引数より順位が上の時に非零、さもなければ零を返すことで順位関係を表す。
lsortは常に順位が下位のものから上位のものへと並ぶ昇順の整列を行う。
もし、降順の整列が必要ならissupの機能を逆転して、
第一引数が第二引数より順位が下の時に非零を返すようにすればよい。
どのような場合でも同順位の時は零を返すようにすれば安定整列になるはずである。
issupの第三引数には要素を比較する時に参照すべき任意のデータが渡される。
実際のデータはlsortの第三引数argとして与える。