Cで再発明せずにデータ構造を使う

programming

たとえば C で単方向連結リストを実装する場合、ふつう入門書では

struct slist {
    int n;
    struct slist *next;
};

のように実装するが、使いたいデータの型が複数ある場合、

struct slist_int {
    int n;
    struct slist_int *next;
};

struct slist_double {
    double n;
    struct slist_double *next;
};

のように型の数と同じだけリストの型も用意する必要がある。

void * を使って

struct slist_generic {
    void *p;
    struct slist_generic *next;
};

のようにすれば汎用的に用いることもできるが、扱いづらい。

どこが元ネタか知らないのだが、Linux kernel の struct list_head や Windows の LIST_ENTRY などでは少し変わった方法でこれを解決している。

次のような構造体を用いる。

struct slist_head {
    struct slist_head *next;
};

これをリストにしたい構造体に突っ込む。たとえば、

struct slist_int {
    int n;
    struct slist_head list;
};

サンプルコード:

/* slist.h for C99 or later */

#ifndef SLIST_H
#define SLIST_H

#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>

struct slist_head {
    struct slist_head *next;
};

static inline void slist_init_head(struct slist_head *head)
{
    head->next = head;
}

static inline bool slist_empty(struct slist_head *head)
{
    return head->next == head;
}

static inline void slist_insert_front(struct slist_head *entry, struct slist_head *head)
{
    entry->next = head->next;
    head->next = entry;
}

#define slist_entry(ptr, type, member) ((type *)((uintptr_t)ptr - offsetof(type, member)))

#define slist_for_each(iter, head)     \
   for (iter = (head)->next;      \
        iter != (head);            \
        iter = iter->next)

#define slist_for_each_safe(iter, tmp, head)       \
   for (iter = (head)->next, tmp = iter->next; \
        iter != (head);                \
        iter = tmp, tmp = iter->next)

#endif /* !SLIST_H */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "slist.h"

struct slist_int {
    int n;
    struct slist_head list;
};

int main(void)
{
    struct slist_head head;
    struct slist_head *iter, *tmp;
    struct slist_int *entry;
    int i;

    slist_init_head(&head);

    for (i = 0; i < 10; i++) {
        struct slist_int *new = malloc(sizeof(*new));
        new->n = i;
        slist_insert_front(&new->list, &head);
    }

    if (slist_empty(&head))
        puts("never reached");

    slist_for_each(iter, &head) {
        entry = slist_entry(iter, struct slist_int, list);
        printf("%d -> ", entry->n);
    }
    puts("NULL");

    slist_for_each_safe(iter, tmp, &head) {
        entry = slist_entry(iter, struct slist_int, list);
        free(entry);
    }

    return 0;
}

解説が必要なのは slist_entry だと思うのでこれを解説するが、container_of か CONTAINING_RECORD でググったほうがわかりやすいかもしれない。

#define slist_entry(ptr, type, member) ((type *)((uintptr_t)ptr - offsetof(type, member)))
struct slist_int *ptr_slist_int = slist_entry(ptr_slist_head, struct slist_int, list);

はこんな感じに展開される(括弧は省略):

struct slist_int *ptr_slist_int = (struct slist_int *)((uintptr_t)ptr_slist_head - (size_t)&((struct slist_int *)0)->list);

ptr_slist_head から struct slist_int のメンバ struct list_head のオフセットを引いている。

よって、ptr_slist_head が struct slist_int に組み込まれた struct slist_head へのポインタならば、*ptr_slist_head をメンバに含む struct slist_int のアドレスを得ることができる(日本語不自由)。

頭いい。

C++ では std::forward_list があるらしい。

以上。以下、C89 以前用:

/* slist.h for C89 and earlier */

#ifndef SLIST_H
#define SLIST_H

#include <stddef.h>

struct slist_head {
    struct slist_head *next;
};

#define slist_init_head(head)          \
   ((head)->next = (head))

#define slist_empty(head)          \
   ((head)->next == (head))

#define slist_insert_front(entry, head)        \
   do {                  \
       (entry)->next = (head)->next; \
       (head)->next = (entry);      \
   } while (0)

#define slist_entry(ptr, type, member) ((type *)((char *)ptr - offsetof(type, member)))

#define slist_for_each(iter, head)     \
   for (iter = (head)->next;      \
        iter != (head);            \
        iter = iter->next)

#define slist_for_each_safe(iter, tmp, head)       \
   for (iter = (head)->next, tmp = iter->next; \
        iter != (head);                \
        iter = tmp, tmp = iter->next)

#endif /* !SLIST_H */

もう少しいい感じにマクロが使える言語がほしい(いい感じ とは)。