名前

insque, remque - キューにアイテムを挿入/削除する

書式

#include <search.h>

void insque(void *elem, void *prev);
void remque(void *elem);

glibc 向けの機能検査マクロの要件 (feature_test_macros(7) 参照):

insque(), remque():

_SVID_SOURCE || _XOPEN_SOURCE >= 500 || _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED

説明

関数 insque() と remque() は双方向連結リスト (doubly-linked list) を操作する。リスト中のそれぞれの要素は、最初の二つの要素がそれぞれ次と前へのポインターであるような構造体である。リンクリストは、線形 (linear) か環状 (circular) のどちらかになる (線形の場合には、リストの末尾では次へのポインターが NULL になり、リストの先頭では前へのポインターが NULL になる)。

insque() 関数は elem で示される要素を prev で示される要素の直後に挿入する。

リストが線形の場合、insque(elem, NULL) を呼び出すと、リストの最初の要素を挿入することができる。この呼び出しを行うと elem の次へのポインターと前へのポインターに共に NULL が設定される。

リストが環状の場合、呼び出す側が、最初の要素の次へのポインターと前へのポインターが自分自身を指し、また insque() の呼び出しで prev 引き数が最初の要素を指すように保証しなければならない。

remque() 関数は elem で示される要素を双方向連結リストから取り除く。

準拠

POSIX.1-2001.

注意

伝統的に (SunOS, Linux libc 4,5 では) これらの関数の引き数は struct qelem *型であり、これは以下のように定義されている。

struct qelem {


    struct qelem *q_forw;


    struct qelem *q_back;


    char          q_data[1];
};

この定義は <search.h> をインクルードする前に _GNU_SOURCE を定義することで得られる。

これらの関数のプロトタイプの置かれる場所は、UNIX の種類により異なる。上記は POSIX 版である。 <string.h> にあるシステムもある。

バグ

glibc 2.4 以前では prev に NULL を指定することができなかった。その結果、線形のリストを作成するためには、呼び出し側は、最初の呼び出しで、リストの最初の 2 つの要素を持ち、各要素の次へのポインターと前へのポインターを適切に初期化したリストを作成しなければならなかった。

例

次のプログラムは insque() の使用法を示したものである。下記はプログラムの実行例である。

$ ./a.out -c a b c
Traversing completed list:


    a


    b


    c
That was a circular list

プログラムのソース

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <search.h>
struct element {


    struct element *forward;


    struct element *backward;


    char *name;
};
static struct element *
new_element(void)
{


    struct element *e;


    e = malloc(sizeof(struct element));


    if (e == NULL) {


        fprintf(stderr, "malloc() failed\n");


        exit(EXIT_FAILURE);


    }


    return e;
}
int
main(int argc, char *argv[])
{


    struct element *first, *elem, *prev;


    int circular, opt, errfnd;


    /* The "-c" command-line option can be used to specify that the


       list is circular */


    errfnd = 0;


    circular = 0;


    while ((opt = getopt(argc, argv, "c")) != -1) {


        switch (opt) {


        case 'c':


            circular = 1;


            break;


        default:


            errfnd = 1;


            break;


        }


    }


    if (errfnd || optind >= argc) {


        fprintf(stderr,  "Usage: %s [-c] string...\n", argv[0]);


        exit(EXIT_FAILURE);


    }


    /* Create first element and place it in the linked list */


    elem = new_element();


    first = elem;


    elem->name = argv[optind];


    if (circular) {


        elem->forward = elem;


        elem->backward = elem;


        insque(elem, elem);


    } else {


        insque(elem, NULL);


    }


    /* Add remaining command-line arguments as list elements */


    while (++optind < argc) {


        prev = elem;


        elem = new_element();


        elem->name = argv[optind];


        insque(elem, prev);


    }


    /* Traverse the list from the start, printing element names */


    printf("Traversing completed list:\n");


    elem = first;


    do {


        printf("    %s\n", elem->name);


        elem = elem->forward;


    } while (elem != NULL && elem != first);


    if (elem == first)


        printf("That was a circular list\n");


    exit(EXIT_SUCCESS);
}

この文書について

この man ページは Linux man-pages プロジェクトのリリース 3.79 の一部である。プロジェクトの説明とバグ報告に関する情報は http://www.kernel.org/doc/man-pages/ に書かれている。

2014-08-19