Common Lisp風のLISPを作ってみる（４．コンスバッファ）

今回は、コンスバッファと私が呼んでいるモジュールを解説します。みなさんご承知のように、リスト'(1 2 3)の先頭に要素4を付け加えるのは容易ですが、末尾に付け加えるのは容易ではありません。また、リストは先頭から読むことはできますが末尾から読むことはできません。単方向リストだからです。だからLispの初心者はreverse関数を使っていい感じにまとめることを学びます。コンスバッファは、先頭と末尾の要素のアドレスを保持することでreverse関数を用いずにリストの末尾に要素を追加します。
ソースコード

cons_buffer.h

まずヘッダーファイルから見ていきます。

cons_buffer.h

/*
 * cons_buffer.h
 */

#ifndef CONS_BUFFER_H_
#define CONS_BUFFER_H_

typedef void * CONS_BUFFER;

CONS_BUFFER cons_buffer_allocate(void);
void cons_buffer_add(CONS_BUFFER buf, void *obj);
void *cons_buffer_get_list(CONS_BUFFER buf);
void cons_buffer_free(CONS_BUFFER buf);

#endif

文字列バッファの時と同じように、バッファの構造自体はソースファイルに記しています。

cons_buffer.c

ソースファイルを上から見ていきます。CBUF_HEADER構造体がリストの先頭と末尾のアドレスを保持します。

cons_buffer.c

/*
 * cons_buffer.c
 */

#include <stdlib.h>
#include "cons_buffer.h"
#include "../chapter02/type.h"
#include "helper.h"

typedef struct {
    CONS *top;
    CONS *last;
} CBUF_HEADER;

cons_buffer_allocate関数はコンスバッファを初期化します。

cons_buffer.c

CONS_BUFFER cons_buffer_allocate(void) {
    CBUF_HEADER *h = (CBUF_HEADER *)malloc(sizeof(CBUF_HEADER));
    h->top = NIL;
    h->last = NIL;
    return (void *)h;
}

cons_buffer_add関数はリストの末尾に要素を追加します。コンスバッファが何もデータを持っていない場合と持っている場合で処理が異なることに注意してください。

cons_buffer.c

void cons_buffer_add(CONS_BUFFER buf, void *obj) {
    CBUF_HEADER *h = (CBUF_HEADER *)buf;
    if (h->top == NIL) {
        h->top = (CONS *)cons(obj, NIL);
        h->last = h->top;
    } else {
        h->last->cdr = (CONS *)cons(obj, NIL);
        h->last = h->last->cdr;
    }
}

cons_buffer_get_list関数はコンスバッファが持っているリストを取得します。

cons_buffer.c

void *cons_buffer_get_list(CONS_BUFFER buf) {
    return (void *) ((CBUF_HEADER *)buf)->top;
}

cons_buffer_free関数はコンスバッファを解放します。

cons_buffer.c

void cons_buffer_free(CONS_BUFFER buf) {
    free(buf);
}

helper.h

ヘルパー関数をまとめたファイルである、helper.h, helper.cを見ていきましょう。これらのファイルは、必要に応じて関数が追加されていきます。

helper.h

/*
 * helper.h
 */

#ifndef HELPER_H_
#define HELPER_H_

void * cons(void *car1, void *cdr1);

#endif

helper.c

今回はcons関数を書きました。Lispのcons関数のようにコンスセルを返します。

helper.c

/*
 * helper.c
 */

#include <stdlib.h>
#include "helper.h"
#include "../chapter02/type.h"

void * cons(void *car1, void *cdr1) {
    CONS *c = malloc(sizeof(CONS));
    c->h.type = TYPE_CONS;
    c->car = car1;
    c->cdr = cdr1;
    return (void *)c;
}