C言語入門(54) 実際にプログラムを読んで理解を深めよう tail編(9)

Posted: 2013年08月22日

前回は、逆読みモードのファイル読み込み処理です。
今回は、逆読みモードの行読み込み処理について記載します。

reverse.c r_buf関数

プログラムプログラム:

typedef struct bf {
    struct bf *next;
    struct bf *prev;
    int len;
    char *l;
} BF;

/*
 * r_buf -- display a non-regular file in reverse order by line.
 *
 * This is the function that saves the entire input, storing the data in a
 * doubly linked list of buffers and then displays them in reverse order.
 * It has the usual nastiness of trying to find the newlines, as there's no
 * guarantee that a newline occurs anywhere in the file, let alone in any
 * particular buffer.  If we run out of memory, input is discarded (and the
 * user warned).
 */
static void
r_buf(FILE *fp, const char *fn)
{
    BF *mark, *tl, *tr;
    int ch, len, llen;
    char *p;
    off_t enomem;

    tl = NULL;
#define BSZ (128 * 1024)
    for (mark = NULL, enomem = 0;;) {
        /*
         * Allocate a new block and link it into place in a doubly
         * linked list.  If out of memory, toss the LRU block and
         * keep going.
         */
        if (enomem || (tl = malloc(sizeof(BF))) == NULL ||
            (tl->l = malloc(BSZ)) == NULL) {
            if (!mark)
                err(1, "malloc");
            tl = enomem ? tl->next : mark;
            enomem += tl->len;
        } else if (mark) {
            tl->next = mark;
            tl->prev = mark->prev;
            mark->prev->next = tl;
            mark->prev = tl;
        } else {
            mark = tl;
            mark->next = mark->prev = mark;
        }

        /* Fill the block with input data. */
        for (p = tl->l, len = 0;
            len < BSZ && (ch = getc(fp)) != EOF; ++len)
            *p++ = ch;

        if (ferror(fp)) {
            ierr(fn);
            return;
        }

        /*
         * If no input data for this block and we tossed some data,
         * recover it.
         */
        if (!len && enomem) {
            enomem -= tl->len;
            tl = tl->prev;
            break;
        }

        tl->len = len;
        if (ch == EOF)
            break;
    }

    if (enomem) {
        warnx("warning: %jd bytes discarded", (intmax_t)enomem);
        rval = 1;
    }

解説解説:

データを読み込みますが
リンクリスト(BF)にて管理します。

markは、はじめに読み込みを行ったBFをしまします。
読み込んだ順で処理が行われます。

リンクリストの設定はif文で構成されていますが
わかりづらい構造になっています。

  • 初回は、tlの領域を確保後にelseの処理を行います。
  • 次以降は、tlの領域を確保後に else ifの処理を行います。
    ※ メモリーの確保が出来ない倍は、ifの処理を行います。

無限ループで構成されていますが
以下の条件で終了します。
– 最後まで読みきった場合
– メモリーの確保に失敗して且つ、ファイルからデータが読み込める場合

また、メモリーの確保に失敗した場合は、
この関数を中断します。

プログラムプログラム:

    /*
     * Step through the blocks in the reverse order read.  The last char
     * is special, ignore whether newline or not.
     */
    for (mark = tl;;) {
        for (p = tl->l + (len = tl->len) - 1, llen = 0; len--;
            --p, ++llen)
            if (*p == 'n') {
                if (llen) {
                    WR(p + 1, llen);
                    llen = 0;
                }
                if (tl == mark)
                    continue;
                for (tr = tl->next; tr->len; tr = tr->next) {
                    WR(tr->l, tr->len);
                    tr->len = 0;
                    if (tr == mark)
                        break;
                }
            }
        tl->len = llen;
        if ((tl = tl->prev) == mark)
            break;
    }
    tl = tl->next;
    if (tl->len) {
        WR(tl->l, tl->len);
        tl->len = 0;
    }
    while ((tl = tl->next)->len) {
        WR(tl->l, tl->len);
        tl->len = 0;
    }
}

解説解説:

markを最後に読み込んだBFを設定し
最後のデータからループして表示処理を行います。

改行文字が見つかった場合は、その位置まで表示し
以前のバッファーに表示していない文字があれば表示を行います。

リンクリストが一周したら処理を終了し
残りの情報を表示します。

この処理では、mallocを行う割にfreeをおこなっていないため
メモリーリークしています。

カテゴリー: プログラム, 入門 | タグ: , , | コメント無し »

コメント