map and grep, foreach on C

Perlでリスト処理といえばmapとgrepにforeachだと思う。
たとえば、こんな感じで使える。実行すると"6 12 18 24 30"が標準出力に出力される。

#! /usr/bin/perl
use strict;
use warnings;

# 要素に1から10を持つリストを生成する。
my @list1 = (1..10);

# 各要素が3倍のリストを生成する。
my @list2 = map { $_ * 3 } @list1;

# 偶数の要素のリストを生成する。
my @list3 = grep { $_ % 2 == 0 } @list2;

# 各要素を表示する。
foreach (@list3) { print $_, " "; }
print "\n";

これを無性にC言語でやりたくなったので実装してみた。

#include <stdio.h>
#include <stdlib.h>

#include "list.h"
List_template(int)

int multi_3(int *in, int *out) {  /* 3倍する */
  *out = *in * 3;
  return TRUE;
}

int is_even(int *in, int *bool) { /* 偶数か？ */
  *bool = (*in % 2 == 0) ? TRUE : FALSE;
  return TRUE;
}

int main() {
  List list1 = NULL, list2 = NULL, list3 = NULL;
  int i, *n;

  /* 要素に1から10を持つリストを生成する。 */
  list1 = List_func(create, int)();
  if (list1 == NULL) goto END;
  for (i = 1; i <= 10; i++) {
    if (! List_func(push, int)(list1, &i)) goto END;
  }

  /* 各要素が3倍のリストを生成する。 */
  list2 = List_func(map, int)(list1, multi_3 );
  if (list2 == NULL) goto END;

  /* 偶数の要素のリストを生成する。 */
  list3 = List_func(grep, int)(list2, is_even );
  if (list3 == NULL) goto END;

  /* 各要素を表示する。 */
  List_foreach (n, list3) {
    printf("%d ", *n);
  }
  printf("\n");

END:
  List_func(delete, int)(list1);
  List_func(delete, int)(list2);
  List_func(delete, int)(list3);

  return 0;
}

それでは恐ろしいリストの中身を。
まず、list.hの定義内容はこう。

#ifndef __LIST_H__
#define __LIST_H__

#define TRUE  (1 == 1)
#define FALSE (1 != 1)

/* リスト型 */
typedef struct List_t *List;

/* リストの生成 */
List List_create(unsigned int);
/* リストの破棄 */
void List_delete(List);
/* リストの末尾に追加 */
int List_push(List, const void *);

/* リストの変換 */
typedef int (*List_map_func)(void *input, void *output);
List List_map(List, List_map_func);
/* リストのフィルタリング */
typedef int (*List_grep_func)(void *in, int *bool);
List List_grep(List, List_grep_func);

/* リストのイテレータが次の要素を保持しているか？ */
int List_has_next(List);
/* リストのイテレータをリセットし初めの要素を取得 */
void *List_begin(List);
/* リストのイテレータで次の要素を取得 */
void *List_next(List);

/* リストのイテレーション */
#define List_foreach(_V, _LIST) \
for (_V = List_begin(_LIST); List_has_next(_LIST); _V = List_next(_LIST) )

/* 型に応じた関数 */
#define List_func(name, type)  List_##name##type
#define List_template(type) \
List List_func(create, type)() { \
  return List_create(sizeof(type)); \
} \
void List_func(delete, type)(List list) { \
  List_delete(list); \
} \
int List_func(push, type)(List list, const type *v) { \
  return List_push(list, v); \
} \
List List_func(map, type)(List list, int (*f)(type *, type *)) { \
  return List_map(list, (List_map_func)f); \
} \
List List_func(grep, type)(List list, int (*f)(type *, int *)) { \
  return List_grep(list, (List_grep_func)f); \
}

#endif

単なる連結リスト。実装は結構長い。

#include <string.h>
#include <stdlib.h>
#include <stddef.h>

#include "list.h"

typedef struct Cell_t *Cell;  /* セル型 */
typedef struct Cell_t {
  Cell next;            /* 次のセル */
  char value;           /* 要素の開始 */
};

struct List_t {              /* リスト型 */
  size_t size;          /* 要素のサイズ */
  unsigned int count;   /* 要素の登録数 */
  Cell begin, end, now; /* 最初、最後、現在(イテレータ用) */
};

/* セルの要素のポインタを取得 */
#define CELL_VALUE(_CELL) \
((char *)_CELL + offsetof(struct Cell_t, value))

/* セルの生成 */
static Cell Cell_create(List list) {
  size_t size = offsetof(struct Cell_t, value) + list->size;
  Cell cell = malloc(size);
  if (cell != NULL) cell->next = NULL;
  return cell;
}

/* セルの破棄 */
static void Cell_delete(Cell cell) { free(cell); }

/* リストの生成 */
List List_create(size_t size) {
  List list = NULL;
  if (size == 0) return list;

  list = malloc(sizeof(struct List_t));
  if (list != NULL) {
    list->size    = size;
    list->count   = 0;
    list->now = list->end = list->begin = NULL;
  }
  return list;
}

/* リストの破棄 */
void List_delete(List list) {
  if (list == NULL) return;

  while (list->count > 0) {
    Cell cell   = list->begin;
    list->begin = cell->next;
    Cell_delete(cell);
    if (--list->count == 0) list->end = NULL;
  }
  free(list);
}

/* リストの末尾に追加 */
int List_push(List list,const void *value) {
  Cell cell = NULL;
  if (list == NULL) return FALSE;
  cell = Cell_create(list);
  if (cell == NULL) return FALSE;

  memcpy(CELL_VALUE(cell), value, list->size);
  if (list->end != NULL) {
    list->end->next = cell;
  }
  else {
    list->now = list->begin = cell;
  }
  list->end = cell;
  ++list->count;
  return TRUE;
}

/* リストの変換 */
List List_map(List list, List_map_func f) {
  List list2 = NULL;
  void *push_value = NULL;
  void *value;

  if (list == NULL) return NULL;
  list2 = List_create(list->size);
  if (list2 == NULL) return NULL;
  push_value = malloc(list->size);
  if (push_value == NULL) {
    List_delete(list2);
    return NULL;
  }

  /* List_map_func結果でリスト生成 */
  List_foreach (value, list) {
    if (! (*f)(value, push_value)) {
      List_delete(list2);
      free(push_value);
      return NULL;
    }
    if (! List_push(list2, push_value) ) {
      List_delete(list2);
      free(push_value);
      return NULL;
    }
  }
  return list2;
}

/* リストのフィルタリング */
List List_grep(List list, List_grep_func f) {
  List list2 = NULL;
  void *value;
  int bool;

  if (list == NULL) return NULL;
  list2 = List_create(list->size);
  if (list2 == NULL) return NULL;

  /* List_grep_func結果が真のリストを生成 */
  List_foreach (value, list) {
    if (! (*f)(value, &bool)) {
      List_delete(list2);
      return NULL;
    }
    if (bool) {
      if (! List_push(list2, value) ) {
        List_delete(list2);
        return NULL;
      }
    }
  }
  return list2;
}

/* リストのイテレータが次の要素を保持しているか？ */
int List_has_next(List list) {
  if (list == NULL) return FALSE;
  if (list->now == NULL) return FALSE;
  return TRUE;
}

/* リストのイテレータをリセットし初めの要素を取得 */
void *List_begin(List list) {
  if (list == NULL) return NULL;
  list->now = list->begin;
  return CELL_VALUE(list->now);
}

/* リストのイテレータで次の要素を取得 */
void *List_next(List list) {
  if (list == NULL) return NULL;
  list->now = (list->now == NULL) ? NULL : list->now->next;
  return CELL_VALUE(list->now);
}

感想。やれなくは無いけどめんどくさい。