ユーニックス総合研究所

  • home
  • archives
  • queue-parse

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

  • 作成日: 2023-09-18
  • 更新日: 2023-12-24
  • カテゴリ: C言語

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

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

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

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

ソースコード全文

ソースコードは以下になります。
ライセンスは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に保存しています。
キューに予約された文字は改行ではないことがわかっていますので、処理は簡便になっています。

おわりに

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

🦝 < キューは便利！

🦝 < エンキュー、デキュー！

カテゴリー

メニュー