連結リストでキュー #3

示した片方向の連結リストによるこの実装では、
queue_dequeue()においてエントリが1個かそれ以上かで処理を場合分けしないといけない。

    if (p == queue->tail) queue->tail = p->next;

双方向の連結リストにすると構造が均一になり場合分けが不要になる。

queue.h

...snip
typedef struct {
    queue_entry_t *head;
} queue_t[1];
...snip

双方向リストで環状にエントリを持つので、
tailが無くても定数時間で先頭と末尾とにアクセスできる。

queue.c

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

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

#define HEAD    (queue->head)

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

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

void queue_enqueue(queue_t queue, mpz_t val)
{
    queue_entry_t *p = HEAD->prev;
    queue_entry_t *q = HEAD->prev = malloc(sizeof(queue_entry_t));
    mpz_init_set(q->val, val);
    q->prev = p;
    q->next = HEAD;
    p->next = q;
}

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

bool_t queue_isempty(queue_t queue)
{
    return HEAD == HEAD->next;
}

とはいえ、場合分けが不要になる効用は双方向リスト化による処理とメモリ使用の増大に勝るものなのだろうか？