リングバッファ(キュー)を使った文字列のパース処理
目次
リングバッファ(キュー)を使ったパース
パース処理を書いているとファイルなどのストリームをパースをすることもあります。
それで困るのがストリームの読み込み位置を前に戻せないケースです。
パースの都合上、ストリームの読み込み位置を前に戻したい時があるのですが、ストリームのオープンモードによってはシークが出来ない場合があります。
そういった時にどのようにパースをすればいいのでしょうか?
そういう時はキューを使ったパース処理が比較的に簡単に対処できます。
この記事ではキューを使った文字列のパース処理を解説します。
ソースコード全文
ソースコードは以下になります。
ライセンスは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 ・) | エンキュー、デキュー! |