連結リストでキュー #1

多倍長精度演算ライブラリGMPの整数型mpz_tを格納できるキューを連結リストでかなり適当に実装。

queue.h

#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

#include <gmp.h>

typedef enum  { FALSE = 0 } bool_t;

typedef struct queue_entry queue_entry_t;

typedef struct {
    queue_entry_t *head, *tail;
} queue_t[1];

void queue_init(queue_t queue);
void queue_fin(queue_t queue);
void queue_enqueue(queue_t queue, mpz_t val);
void queue_dequeue(queue_t queue, mpz_t val);
bool_t queue_isempty(queue_t queue);

#endif /* QUEUE_H_INCLUDED */

queue_entry_t型がそうであるように、
queue_t型もqueue.hにおいては不完全型の構造体で定義しておくとその実装を隠すことができ、
さらにその実装で使用しているがゆえに表に出しているqueue_entry_t型自体を隠すことができるようになる。
しかし配列は不完全型を要素として持てないためこれは叶わない。
が、とりあえず配列として定義している。

queue.c

#include <stdlib.h>
#include "queue.h"

struct queue_entry {
    mpz_t val;
    queue_entry_t *next;
};

void queue_init(queue_t queue)
{
    queue->tail = queue->head = malloc(sizeof(queue_entry_t));
    queue->tail->next = queue->head;
    mpz_init(queue->tail->val);
}

void queue_fin(queue_t queue)
{
    queue_entry_t *p = queue->head->next;
    while (1) {
        queue_entry_t *q = p->next;
        mpz_clear(p->val);
        free(p);
        if (p == queue->head) return;
        p = q;
    }
}

void queue_enqueue(queue_t queue, mpz_t val)
{
    queue->tail = queue->tail->next = malloc(sizeof(queue_entry_t));
    queue->tail->next = queue->head;
    mpz_init_set(queue->tail->val, val);
}

/* must not call this function when queue is empty */
void queue_dequeue(queue_t queue, mpz_t val)
{
    queue_entry_t *p = queue->head->next;
    queue->head->next = p->next;
    if (p == queue->tail) queue->tail = p->next;
    mpz_set(val, p->val);
    mpz_clear(p->val);
    free(p);
}

bool_t queue_isempty(queue_t queue)
{
    return queue->head == queue->tail;
}

簡単な使い方。

#include <gmp.h>
#include "queue.h"
...snip
    queue_t queue;
    mpz_t x;
...snip
    /* initialize queue */
    queue_init(queue);
...snip
    /* enqueue x */
    queue_enqueue(queue, x);
...snip
    /* dequeue and assign dequeued value to x */
    queue_dequeue(queue, x);
    gmp_printf("%Zd ", x);
...snip
    /* dequeue all queued data */
    while (! queue_isempty(queue)) {
        queue_dequeue(queue, x);
        gmp_printf("%Zd ", x);
    }
    gmp_printf("\n");
...snip
    /* finalize queue */
    queue_fin(queue);