Hatena::Groupcprogramming

Going My C Way このページをアンテナに追加 RSSフィード

2011年07月19日(火)

連結リストを扱うマクロ その2

15:54 | 連結リストを扱うマクロ その2 - Going My C Way を含むブックマーク はてなブックマーク - 連結リストを扱うマクロ その2 - Going My C Way 連結リストを扱うマクロ その2 - Going My C Way のブックマークコメント

前回のつづき。今度は 2way リストにします。

データの next、prev にはリストの流れごとの接尾詞をつけます。

typedef struct station_t {
    struct station_t *next_local;
    struct station_t *prev_local;
    struct station_t *next_rapid;
    struct station_t *prev_rapid;

    const char *name;
} STATION_t;

llist2.h

#ifndef INCLUDED_LLIST2_H
#define INCLUDED_LLIST2_H

#define next(postfix_)  next_ ## postfix_
#define prev(postfix_)  prev_ ## postfix_

#define llist_init(l_,t_)   ((l_)->next(t_) = (l_)->prev(t_) = (l_))

#define llist_next(l_,t_)   ((l_)->next(t_))
#define llist_prev(l_,t_)   ((l_)->prev(t_))

#define llist_ins_next(l_, t_, x_)              (\
    (x_)->next(t_)              = (l_)->next(t_),\
    (x_)->prev(t_)              = (l_)          ,\
    (l_)->next(t_)->prev(t_)    = (x_)          ,\
    (l_)->next(t_)              = (x_)          )

#define llist_ins_prev(l_, t_, x_)              (\
    (x_)->prev(t_)              = (l_)->prev(t_),\
    (x_)->next(t_)              = (l_)          ,\
    (l_)->prev(t_)->next(t_)    = (x_)          ,\
    (l_)->prev(t_)              = (x_)          )

#define llist_del_next(l_, t_)                                      (\
    (l_)->next(t_)->next(t_)->prev(t_)  = (l_)                      ,\
    (l_)->next(t_)                      = (l_)->next(t_)->next(t_)  )

#define llist_del_prev(l_, t_)                                      (\
    (l_)->prev(t_)->prev(t_)->next(t_)  = (l_)                      ,\
    (l_)->prev(t_)                      = (l_)->prev(t_)->prev(t_)  )

#define llist_del(l_, t_)                       (\
    (l_)->prev(t_)->next(t_) = (l_)->next(t_)   ,\
    (l_)->next(t_)->prev(t_) = (l_)->prev(t_)   )

#endif /* !INCLUDED_LLIST2_H */

使用例。try-llist2.c

#include <stdio.h>
#include <stdlib.h>
#include "llist2.h"

typedef struct station_t {
    struct station_t *next_local;
    struct station_t *prev_local;
    struct station_t *next_rapid;
    struct station_t *prev_rapid;

    const char *name;
} STATION_t;

int main(void)
{
    STATION_t stations[10], *station;
    STATION_t *chuo_line    = &stations[0]; /* ヘッド */
    STATION_t *shinjuku     = &stations[1];
    STATION_t *nakano       = &stations[2];
    STATION_t *mitaka       = &stations[3];
    STATION_t *koenji       = &stations[4];
    STATION_t *asagaya      = &stations[5];
    STATION_t *ogikubo      = &stations[6];
    STATION_t *nishiogikubo = &stations[7];
    STATION_t *kichijoji    = &stations[8];

    shinjuku->name      = "Shinjuku";
    nakano->name        = "Nakano";
    mitaka->name        = "Mitaka";
    koenji->name        = "Koenji";
    asagaya->name       = "Ayagaya";
    ogikubo->name       = "Ogikubo";
    nishiogikubo->name  = "Nishi-Ogikubo";
    kichijoji->name     = "Kichijoji";

    llist_init(chuo_line, local);
    llist_ins_next(chuo_line, local, mitaka);
    llist_ins_next(chuo_line, local, kichijoji);
    llist_ins_next(chuo_line, local, nishiogikubo);
    llist_ins_next(chuo_line, local, ogikubo);
    llist_ins_next(chuo_line, local, asagaya);
    llist_ins_next(chuo_line, local, koenji);
    llist_ins_next(chuo_line, local, nakano);
    llist_ins_next(chuo_line, local, shinjuku);

    llist_init(chuo_line, rapid);
    llist_ins_next(chuo_line, rapid, mitaka);
    llist_ins_next(chuo_line, rapid, nakano);
    llist_ins_next(chuo_line, rapid, shinjuku);

    puts("----- rapid -----");
    for (station = llist_next(chuo_line, rapid);
            station != chuo_line; station = llist_next(station, rapid)) {
        puts(station->name);
    }

    puts("----- local -----");
    for (station = llist_next(chuo_line, local);
            station != chuo_line; station = llist_next(station, local)) {
        puts(station->name);
    }

    /*
        nakano の次に ogikuno、その次に kichijoji を rapid に追加します
    */
    llist_ins_next(nakano,  rapid, ogikubo);
    llist_ins_next(ogikubo, rapid, kichijoji);

    puts("----- rapid -----");
    for (station = llist_next(chuo_line, rapid);
            station != chuo_line; station = llist_next(station, rapid)) {
        puts(station->name);
    }

    puts("----- local -----");
    for (station = llist_next(chuo_line, local);
            station != chuo_line; station = llist_next(station, local)) {
        puts(station->name);
    }

    return EXIT_SUCCESS;
}

実行結果。

$ ./try-llist2 
----- rapid -----
Shinjuku
Nakano
Mitaka
----- local -----
Shinjuku
Nakano
Koenji
Ayagaya
Ogikubo
Nishi-Ogikubo
Kichijoji
Mitaka
----- rapid -----
Shinjuku
Nakano
Ogikubo
Kichijoji
Mitaka
----- local -----
Shinjuku
Nakano
Koenji
Ayagaya
Ogikubo
Nishi-Ogikubo
Kichijoji
Mitaka