汎用queueの開発

Javaなどのオブジェクト指向の言語での開発に慣れてくると、C言語で プログラムを書こうとしても、あれもない、これもない、でコードを書くのが いやになる事があります。というか、最近なりました。 たとえばqueueなんかはJavaだとList(ArrayListとか)を使うだけですが、 Cでは一々コードを書かなければなりません。生産性が下がるだけでなく、 コードの品質を保つのもなかなか面倒です。

そこで、JavaやC++のクラスライブラリのノリで使えるライブラリを志向して、 まずは汎用のqueueを作ってみました。

queueというのは説明するまでも無く、FIFO(First In, First Out)を実現する データ構造です。チューブの右からデータを入れ、左から取り出すような イメージですね。チューブは空かもしれませんし、既に沢山データが入っている かもしれません。左から取り出す毎にチューブの中のデータは少しずつ左に 移動してゆきます。データを入れるタイミングと取り出すタイミングは同期して いるとは限らないので、チューブ内のデータの量は増減します。queueのデータ 構造はシステムのあらゆる局面でしばしば登場するものです。

queueを実現する典型的な方法は二重リンクリストを使うものです。queue内の 個々のデータの構造を、

typedef struct general_queue_item {
	struct general_queue_item *prev;
	struct general_queue_item *next;
	void *data;
} general_queue_item_t;

これで作るqueueの先頭と末尾を管理するデータ構造を定義します。 queueの先頭からnextをたどってゆくと末尾に、末尾からprevをたどって ゆくと先頭に達するようになればよいわけです。

typedef struct general_queue_info {
	general_queue_item_t *head;
	general_queue_item_t *tail;
} general_queue_info_t;

では関数はどうなるでしょう。queueにデータを入れる方は、

void push_item(general_queue_info_t *info, void *data)
{
	general_queue_item_t *q;

	/* ここでqにgeneral_queue_item_t型のデータを一つ用意 */

	// queueの末尾につける
	q->data = data;
	q->next = NULL;
	q->prev = info->tail;
	if (info->tail != NULL) {
		info->tail->next = q;
	}
	info->tail = q;

	// queueが空だったら、先頭にも設定してあげる
	if (info->head == NULL) {
		info->head = q;
	}
}

取り出すほうはどうすればよいでしょうか。

void *get_item(general_queue_info_t *info)
{
	general_queue_item_t *q;
	void *data;

	// 先頭がNULL(==queueが空)ならNULLを返す
	if (info->head == NULL) {
		return NULL;
	}

	// リンクの付け直しをする
	q = info->head;
	data = q->data;
	info->head = q->next;
	if (info->tail == q) {
		info->tail = NULL;
	}

	return data;
}

queueの各要素のデータ領域をどこから持ってくるのか、複数のqueueを扱う場合 の考慮などを行うと、次のプログラムができました。どうでしょうか

• general_queue.h
• general_queue.c
• sample_queue.c