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 */

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

M_PI は C の標準仕様ではない | M_PI Is Non-Standard in C

programming

GCC または Clang で M_PI を使う場合、 _XOPEN_SOURCE=500 またはより一般的な機能選択マクロが定義されていなければならない。 デフォルトでは定義されているので問題なく使える。

M_PI is defined by default with GCC or Clang, so you can use it without any problems.

M_PI

Pi, the ratio of a circle’s circumference to its diameter.

...

These constants come from the Unix98 standard and were also available in 4.4BSD; therefore they are only defined if _XOPEN_SOURCE=500, or a more general feature select macro, is defined. The default set of features includes these constants. See Feature Test Macros.

www.gnu.org

VC++ で M_PI を使うには、math.h をインクルードする前に _USE_MATH_DEFINES を定義する必要がある (ソースコードを引用する方法がわからない):

To use M_PI with VC++, you must define _USE_MATH_DEFINES before including math.h (I don't know how to quote source code):

#define _USE_MATH_DEFINES // for C++  
#include <cmath>  
  
#define _USE_MATH_DEFINES // for C  
#include <math.h>

...

Math Constants are not defined in Standard C/C++. To use them, you must first define _USE_MATH_DEFINES and then include cmath or math.h.

Math Constants

まあ、気になるのであれば、こんな感じにすればたぶん大丈夫:

If you are concerned about portability, you may want to define it like:

/*
#ifdef M_PI
#undef M_PI
#endif
*/
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif /* !M_PI */

宿題で間違ったのでメモ。

米語における関係代名詞主格の which と that の使い分け

english

関係代名詞主格制限用法で先行詞が人でない場合は which か that を使うことを学校で習うが、フォーマルな米語 (written English) ではつねに that を使うことが推奨されている (例: The Chicago Manual of Style)。

これで制限用法 (that) と非制限用法 (which) が見分けやすくなる。

English relative clauses - Wikipedia (permalink)

自分は無意識に使い分けていたが、米語限定とは知らなかった。

このまま米語でやって行っていこうか迷う。 正直スペルとか表現とか好きなところを自分で選びたいが、向こうの人からしたら変な奴に見えるかもしれない (すでに変な奴なので気にする必要はないのかもしれないが)。