単連結リストの整列 #24 名前とスコアが要素のリストを実装する

前掲のインタフェイスを実装してみる。

sclist.c

#include <stdlib.h>
#include <string.h>
#include "sclist.h"
#include "lsort.h"

struct tag_sclist {
    scdata_t head;
    scdata_t tail;
};

struct tag_scdata {
    scdata_t next;
    char *name;
    int score;
};

struct tag_sciter {
    scdata_t curr;
};

static sciter_t sciter_new(sclist_t list)
{
    sciter_t i;
    if (list == NULL) return NULL;
    i = malloc(sizeof(sciter_t));
    if (i == NULL) return NULL;
    i->curr = list->head;
    return i;
}

int sciter_has_next(const sciter_t iter)
{
    return iter != NULL && iter->curr != NULL;
}

scdata_t sciter_next(const sciter_t iter)
{
    scdata_t p;
    if (! sciter_has_next(iter)) return NULL;
    p = iter->curr;
    iter->curr = p->next;
    return p;
}

static scdata_t scdata_new(const char *name, int score)
{
    scdata_t p;
    if (name == NULL) return NULL;
    p = malloc(sizeof(struct tag_scdata));
    if (p == NULL) return NULL;
    p->name = malloc(strlen(name) + 1);
    if (p->name == NULL) {
        free(p);
        return NULL;
    }
    p->next = NULL;
    strcpy(p->name, name);
    p->score = score;
    return p;
}

static void scdata_dispose(scdata_t data)
{
    free(data->name);
    free(data);
}

const char *scdata_get_name(const scdata_t data)
{
    return data->name;
}

int scdata_get_score(const scdata_t data)
{
    return data->score;
}

sclist_t sclist_new(void)
{
    sclist_t p = malloc(sizeof(struct tag_sclist));
    if (p != NULL) p->tail = p->head = NULL;
    return p;
}

void sclist_dispose(sclist_t list)
{
    scdata_t p = list->head;
    while (p != NULL) {
        scdata_t q = p->next;
        scdata_dispose(p);
        p = q;
    }
    free(list);
}

int sclist_add(sclist_t list, const char *name, int score)
{
    scdata_t p;
    if (name == NULL) return 0;
    p = scdata_new(name, score);
    if (p == NULL) return 0;
    if (list->tail == NULL) {
        list->tail = list->head = p;
    } else {
        list->tail->next =p;
        list->tail = p;
    }
    return 1;
}

sciter_t sclist_iterator(sclist_t list)
{
    return list != NULL ? sciter_new(list) : NULL;
}

void sclist_sort(sclist_t list, int (*issup)(const scdata_t, const scdata_t, void *), void *arg)
{
    scdata_t p;
    if (list == NULL || list->head == NULL) return;
    lsort(&list->head, (int (*)(const void *, const void *, void *))issup, arg);
    for (p = list->head; p->next != NULL; p = p->next) ;
    list->tail = p;
}

sclist_t型が指す実体struct tag_sclistは先頭の要素と末尾の要素へのポインタを管理している。
末尾要素の場所を知っているのでsclist_addでデータを追加する時にリストを先頭から辿る必要がない。
リストの整列は先頭要素のポインタへのポインタを与えてlsort関数を呼び出しているだけである。
ただ、リストは末尾要素も管理しているので整列後に末尾要素を改めて再設定している。
とはいえ改めて整列プログラムを書くよりもかなり楽だ。