Serendip

Web Studio

8.7 記憶割当て

malloc, free の簡単な実装を学ぶ。

malloc 時に要求サイズが空きブロックより小さい場合に、後側からブロックを使用していくことに気がつかず、理解するのに時間がかかった。
後側からブロックを使用していくのは、空きリストのポインタを変更しなくてもよいからだろうか。

演習8-7

malloc での妥当なサイズの条件がいまいちわからない。
負の値が渡された場合、unsigned に変換されて大きなサイズが要求されるので、そのチェックを入れてみた。

free での正しいサイズ・フィールドというのもわからない。
解放ブロックのヘッダ位置と次のポインタの差が解放ブロックのサイズの場合が正しいサイズということだろうか。

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

typedef long Align;     /* long の境界に整合させる */

union header {          /* ブロックのヘッダ */
    struct {
        union header *ptr;  /* 空きリストの上なら次のブロック */
        unsigned size;      /* このブロックの大きさ */
    } s;
    Align x;            /* ブロックの整合を強制 */
};

typedef union header Header;

void *my_malloc(unsigned);
static Header *morecore(unsigned);
void my_free(void *);

int main(void)
{
    char *s, *p;

    if ((s = my_malloc(10)) == NULL) {
        fprintf(stderr, "can't allocate memory\n");
        exit(EXIT_FAILURE);
    }
    if ((p = my_malloc(10)) == NULL) {
        fprintf(stderr, "can't allocate memory\n");
        exit(EXIT_FAILURE);
    }

    s[0] = 'h';
    s[1] = 'e';
    s[2] = 'l';
    s[3] = 'l';
    s[4] = 'o';
    s[5] = '!';
    s[6] = '\0';

    p[0] = 'H';
    p[1] = 'E';
    p[2] = 'L';
    p[3] = 'L';
    p[4] = 'O';
    p[5] = '!';
    p[6] = '\0';

    printf("%s\n", s);
    printf("%s\n", p);
    my_free(s);
    my_free(p);

    return 0;
}

static Header base;     /* 開始時の空きリスト */
static Header *freep = NULL;    /* 空きリストの先頭 */

/* my_malloc : 汎用の記憶割当てプログラム */
void *my_malloc(unsigned nbytes)
{
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned nunits;

    if ((long) nbytes <= 0) { /* 引数が正の整数かをチェック */
        fprintf(stderr, "my_malloc : wrong memory size %d\n", nbytes);
        exit(EXIT_FAILURE);
    }

    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
    if ((prevp = freep) == NULL) {  /* 空きリストはまだない */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {  /* 十分大きい */
            if (p->s.size == nunits) {  /* 正確に */
                prevp->s.ptr = p->s.ptr;
            } else {    /* 後尾の部分を割り当て */
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p+1);
        }
        if (p == freep) {   /* 空きリストをリング状につなぐ */
            if ((p = morecore(nunits)) == NULL) {
                return NULL;    /* 残りなし */
            }
        }
    }
}

#define NALLOC 1024     /* 要求する最小の単位数 */

/* morecore : システムにもっとメモリを要求する */
static Header *morecore(unsigned nu)
{
    char *cp, *sbrk(int);
    Header *up;

    if (nu < NALLOC) {
        nu = NALLOC;
    }
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) - 1) {   /* スペースが全然ない */
        return NULL;
    }
    up = (Header *) cp;
    up->s.size = nu;
    my_free((void *) (up + 1));
    return freep;
}

/* my_free :  ブロック ap を空きリストに入れる */
void my_free(void *ap)
{
    Header *bp, *p;

    bp = (Header *) ap - 1;     /* ブロック・ヘッダを指す */
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) {
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) {
            break;  /* 領域の始めあるいは終りの解放ブロック */
        }
    }
    if ((bp < p->s.ptr) &&  /* 次の領域が後方にある場合 */
            ((p->s.ptr - bp - bp->s.size) != 0)) { /* ブロックサイズのチェック */
        fprintf(stderr, "my_free : wrong block size %d\n", bp->s.size);
    }
    if (bp + bp->s.size == p->s.ptr) {  /* 上の nbr へ結合 */
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {  /* 下の nbr へ結合 */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else {
        p->s.ptr = bp;
    }
    freep = p;
}

プログラミング言語C 第2版 ANSI規格準拠

posted with amazlet at 09.11.27

B.W. カーニハン D.M. リッチー
共立出版
売り上げランキング: 9726

Amazon.co.jp で詳細を見る