単連結リストの整列 #58 既に整列状態のものはそれ以上整列しない

前回の方針に従ってlistsortを変更する。
インタフェイスは変えないのでヘッダファイルに変更はない。

listsort.c

#include "listsort.h"

void listsort(
    void *list,
    void *(*head)(const void *, void *),
    void *(*next)(const void *, const void *, void *),
    int (*isvalid)(const void *, const void *, void *),
    void (*swap)(void *, void *, void *, void *),
    void *listarg,
    int (*issup)(const void *, const void *, void *),
    void *arg
) {
    void *p, *q, *r, *s;
    int b = 1;
    q = head(list, listarg);
    if (! isvalid(list, q, listarg)) return;
    r = next(list, q, listarg);
    if (! isvalid(list, r, listarg)) return;
    for (;;) {
        if (issup(q, r, arg)) {
            swap(list, q, r, listarg);
            s = next(list, q, listarg);
            b = 0;
        } else {
            s = next(list, r, listarg);
            q = r;
        }
        if (! isvalid(list, s, listarg)) break;
        r = s;
    }
    for (; b == 0 && q != next(list, head(list, listarg), listarg); q = s) {
        b = 1;
        p = head(list, listarg);
        while (p != q) {
            s = next(list, p, listarg);
            if (issup(p, s, arg)) {
                swap(list, p, s, listarg);
                b = 0;
            } else {
                r = p;
                p = s;
                s = r;
            }
        }
    }
}

一回リストを走査するたびにその過程で交換操作が行われたかどうかを記憶して、
一度も交換が行われなかった時にはそれ以降の処理を打ち切る。
走査の開始前に変数bを1に初期化し、交換を行った時にこれを0にする。
したがって、走査終了時にこれが0でなければそれ以上の整列処理は不要ということになる。