単連結リストの整列 #64 処理の呼び出しカウント付きリストの実装

計数処理についてなんとかなりそうなのでintlistの全体をコーディングしてみる。

intlist.c

#include <stddef.h>
#include <stdlib.h>
#include <assert.h>
#include "listsort.h"
#include "intlist.h"

#define UNUSED_ARG(x) (void)(x)

struct tag_intlist {
    intelem_t head;
    unsigned long compare_counts;
    unsigned long swap_counts;
};

struct tag_intelem {
    int val;
    intelem_t next;
};

struct tag_intiter {
    intelem_t curr;
};

struct combined_arg {
    void *arg;
    int (*issup)(cintelem_t, cintelem_t, void *);
    intlist_t list;
};

static intelem_t intelem_new(int val)
{
    intelem_t elem = malloc(sizeof(struct tag_intelem));
    if (elem != NULL) {
        elem->val = val;
        elem->next = NULL;
    }
    return elem;
}

static void intelem_dispose(intelem_t elem)
{
    free(elem);
}

static void prev2(intlist_t list, intelem_t p1, intelem_t *pp1, intelem_t p2, intelem_t *pp2)
{
    int b1 = 1, b2 = 1;
    intelem_t q = list->head;
    *pp1 = *pp2 = NULL;
    for (;;) {
        if (b1 && q->next == p1) {
            *pp1 = q;
            b1 = 0;
        }
        if (b2 && q->next == p2) {
            *pp2 = q;
            b2 = 0;
        }
        if ((b1 | b2) == 0) break;
        q = q->next;
        if (q == NULL) break;
    }
}

static void *head(const void *list, void *listarg)
{
    UNUSED_ARG(listarg);
    return ((intlist_t)list)->head->next;
}

static void *next(const void *list, const void *p, void *listarg)
{
    UNUSED_ARG(list), UNUSED_ARG(listarg);
    return ((intelem_t)p)->next;
}

static int isvalid(const void *list, const void *p, void *listarg)
{
    UNUSED_ARG(list), UNUSED_ARG(listarg);
    return p != NULL;
}

static void swap(void *list, void *p, void *q, void *listarg)
{
    intelem_t t, pp, pq;
    UNUSED_ARG(listarg);
    (((intlist_t)list)->swap_counts)++;
    if (p == q) return;
    prev2(list, (intelem_t)p, &pp, (intelem_t)q, &pq);
    if (q == pp) {
        t = ((intelem_t)p)->next;
        ((intelem_t)p)->next = q;
        ((intelem_t)q)->next = t;
        ((intelem_t)pq)->next = p;
    } else {
        t = ((intelem_t)q)->next;
        if (p == pq) {
            ((intelem_t)q)->next = p;
            ((intelem_t)p)->next = t;
            ((intelem_t)pp)->next = q;
        } else {
            ((intelem_t)q)->next = ((intelem_t)p)->next;
            ((intelem_t)p)->next = t;
            ((intelem_t)pq)->next = p;
            ((intelem_t)pp)->next = q;
        }
    }
}

static int issuperior(const void *p, const void *q, void *args)
{
    (((struct combined_arg *)args)->list->compare_counts)++;
    return (((struct combined_arg *)args)->issup)(p, q, ((struct combined_arg *)args)->arg);
}

intlist_t intlist_new(void)
{
    intlist_t list = malloc(sizeof(struct tag_intlist));
    if (list != NULL) {
        list->head = intelem_new(0);
        if (list->head != NULL) {
            list->compare_counts = 0;
            list->swap_counts = 0;
        } else {
            free(list);
            list = NULL;
        }
    }
    return list;
}

void intlist_dispose(intlist_t list)
{
    intelem_t p, q;
    for (p = list->head; p != NULL; p = q) {
        q = p->next;
        intelem_dispose(p);
    }
    free(list);
}

int intlist_add_first(intlist_t list, int val)
{
    intelem_t p;
    if (list == NULL || (p = intelem_new(val)) == NULL) return 1;
    p->next = list->head->next;
    list->head->next = p;
    return 0;
}

intiter_t intlist_iterator(cintlist_t list)
{
    intiter_t iter;
    if (list == NULL) return NULL;
    iter = malloc(sizeof(struct tag_intiter));
    if (iter != NULL) iter->curr = list->head->next;
    return iter;
}

void intlist_sort(intlist_t list, int (*issup)(cintelem_t, cintelem_t, void *), void *arg)
{
    struct combined_arg args;
    if (list == NULL) return;
    args.arg = arg;
    args.issup = issup;
    args.list = list;
    listsort(list, head, next, isvalid, swap, NULL, issuperior, &args);
}

void intlist_reset_counts(intlist_t list)
{
    if (list == NULL) return;
    list->compare_counts = 0;
    list->swap_counts = 0;
}

unsigned long intlist_get_compare_counts(cintlist_t list)
{
    assert(list != NULL);
    return list->compare_counts;
}

unsigned long intlist_get_swap_counts(cintlist_t list)
{
    assert(list != NULL);
    return list->swap_counts;
}

int intelem_get_val(cintelem_t e)
{
    assert(e != NULL);
    return e->val;
}

int intiter_has_next(cintiter_t iter)
{
    return iter != NULL && iter->curr != NULL;
}

cintelem_t intiter_next(intiter_t iter)
{
    intelem_t p;
    if (! intiter_has_next(iter)) return NULL;
    p = iter->curr;
    iter->curr = p->next;
    return p;
}

void intiter_dispose(intiter_t iter)
{
    free(iter);
}

要素の交換関数swapが何回呼び出されたかについての計数処理は関数swap中に埋め込んだが、
交換処理と無関係の計数処理を一緒くたにするのはあまりよいことではないと思う。
比較処理の場合と同様にswapの外側に処理を付加した方が見通しと見栄えが良かったかもしれない。