リングバッファ（キュー）を使った文字列のパース処理

731, 2023-09-18

リングバッファ（キュー）を使ったパース

パース処理を書いているとファイルなどのストリームをパースをすることもあります。
それで困るのがストリームの読み込み位置を前に戻せないケースです。

パースの都合上、ストリームの読み込み位置を前に戻したい時があるのですが、ストリームのオープンモードによってはシークが出来ない場合があります。
そういった時にどのようにパースをすればいいのでしょうか？

そういう時はキューを使ったパース処理が比較的に簡単に対処できます。
この記事ではキューを使った文字列のパース処理を解説します。

ソースコード全文

ソースコードは以下になります。
ライセンスはMITです。

/* 2023/09/18
 *
 * リングバッファ（キュー）を使った文字列のパース処理。
 * ポインタを前に戻せない縛りでパースを行う。
 */
#include <stdio.h>
#include <stdbool.h>

enum {
    QUEUE_SIZE = 4,
};

char queue[QUEUE_SIZE];
int queue_head;
int queue_tail;

void queue_enqueue(char val) {
    if ((queue_tail + 1) % QUEUE_SIZE == queue_head) {
        fprintf(stderr, "queue is full\n");
        return;
    }

    queue[queue_tail] = val;
    queue_tail = (queue_tail + 1) % QUEUE_SIZE;
}

char queue_dequeue(void) {
    if (queue_head == queue_tail) {
        fprintf(stderr, "queue is empty\n");
        return -1;
    }

    char val = queue[queue_head];
    queue_head = (queue_head + 1)  % QUEUE_SIZE;
    return val;
}

bool queue_is_empty(void) {
    return queue_head == queue_tail;
}

int main(void) {
    // 改行をカンマに置き換えるパース処理
    // ただしポインタを前に戻せない縛り
    const char *data = "abc\ndef\r\nghi\r\n123\r223";
    char dst[100] = {0};
    int dst_index = 0;

    for (const char *p = data; *p; p++) {
        // キューに予約された文字を処理する
        while (!queue_is_empty()) {
            char c = queue_dequeue();
            dst[dst_index++] = c;
        }

        char c1 = *p;
        if (c1 == '\n') {
            dst[dst_index++] = ',';
        } else if (c1 == '\r') {
            char c2 = *++p;
            if (c2 == '\n') {
                dst[dst_index++] = ',';
            } else {
                dst[dst_index++] = ',';
                queue_enqueue(c2);  // この文字の処理を予約する
            }
        } else {
            dst[dst_index++] = c1;
        }
    }

    dst[dst_index] = '\0';

    printf("dst[%s]\n", dst);

    return 0;
}

キューとは？

キューとは後入れ先出し（Last In, First Out ... LIFO）と呼ばれるデータ構造です。
配列などにデータを入れるときは後ろから入れます。データを取り出すときは先頭から取り出します。
つまり

[1][ ][ ][ ] <- In 1
[1][2][ ][ ] <- In 2
[1][2][3][ ] <- In 3

Out 1 <- [ ][2][3][ ]
Out 2 <- [ ][ ][3][ ]
Out 3 <- [ ][ ][ ][ ]

という感じでデータを出し入れします。
配列の後ろにデータを詰めていってデータを取り出すときは配列の先頭から取り出すわけですね。
もちろん実装は配列じゃなくリストの場合もあります。

いわゆる待ち行列というやつで、プリンタのジョブキューなどが有名です。
仕事をキューに予約しておくと、あとでその仕事を予約した順番に処理できるという感じです。

このキューを使ってパース処理を行います。

キューの実装

キューの実装は以下になります。

enum {
    QUEUE_SIZE = 4,
};

char queue[QUEUE_SIZE];
int queue_head;
int queue_tail;

void queue_enqueue(char val) {
    if ((queue_tail + 1) % QUEUE_SIZE == queue_head) {
        fprintf(stderr, "queue is full\n");
        return;
    }

    queue[queue_tail] = val;
    queue_tail = (queue_tail + 1) % QUEUE_SIZE;
}

char queue_dequeue(void) {
    if (queue_head == queue_tail) {
        fprintf(stderr, "queue is empty\n");
        return -1;
    }

    char val = queue[queue_head];
    queue_head = (queue_head + 1)  % QUEUE_SIZE;
    return val;
}

bool queue_is_empty(void) {
    return queue_head == queue_tail;
}

queueというのがキューの配列です。
queue_headはキューの先頭添え字、queue_tailはキューの末尾添え字になります。
配列のキューではこのように添え字を2つ使います。

キューにデータを詰めるときはqueue_tailを増加させます。
キューからデータを取り出すときはqueue_headを増加させます。
添え字がキューのサイズに達したときは添え字を0にリセットします。

queue_tailを1増加させたときにその値がqueue_headだった時は、キューが満杯です。
queue_headとqueue_tailが同じだったときは、キューは空です。

キューにデータを入れることをエンキュー（enqueue）、データを取り出すことをデキュー（dequeue）と言います。

文字列のパース処理

文字列のパースは以下になります。

int main(void) {
    // 改行をカンマに置き換えるパース処理
    // ただしポインタを前に戻せない縛り
    const char *data = "abc\ndef\r\nghi\r\n123\r223";
    char dst[100] = {0};
    int dst_index = 0;

    for (const char *p = data; *p; p++) {
        // キューに予約された文字を処理する
        while (!queue_is_empty()) {
            char c = queue_dequeue();
            dst[dst_index++] = c;
        }

        char c1 = *p;
        if (c1 == '\n') {
            dst[dst_index++] = ',';
        } else if (c1 == '\r') {
            char c2 = *++p;
            if (c2 == '\n') {
                dst[dst_index++] = ',';
            } else {
                dst[dst_index++] = ',';
                queue_enqueue(c2);  // この文字の処理を予約する
            }
        } else {
            dst[dst_index++] = c1;
        }
    }

    dst[dst_index] = '\0';

    printf("dst[%s]\n", dst);

    return 0;
}

今回のパースは改行をカンマに置き換える処理を行っています。
改行は

CRLF ... "\r\n"（Windows）
CR ... "\r"（古いMac）
LF ... "\n"（UNIX系）

の種類があり、これらに対応しないといけません。
この時、CRLFを処理するときに、ポインタを1つ先読みしないといけません。
しかし先読みした後は、ポインタを前に戻せない「縛り」があります。
ですので、先読みしたときに改行じゃなかった文字はキューに入れて、パースを予約します。

    // キューに予約された文字を処理する
    while (!queue_is_empty()) {
        char c = queue_dequeue();
        dst[dst_index++] = c;
    }

ループの中で上記のようにキューを処理しています。
キューに予約された文字をdstに保存しています。
キューに予約された文字は改行ではないことがわかっていますので、処理は簡便になっています。

おわりに

今回はキューを使ったパース処理を解説しました。
なにか参考になれば幸いです。

（^ _ ^）

キューは便利！

（・ v ・）

エンキュー、デキュー！