1.20 queue.h

双方向リンクを持ったキューを扱う関数群で、 ヘッダ・ファイルは bsys / queue.h である。

キューの双方向リンクの先頭と終端もリンクされるため、リングを構成する。

キューの構造そのものはリンクのみであるため、 通常は他の構造体のメンバーとして使用する。

キューの要素の追加、削除、検索等の関数が用意されている。

□ キューの構造

/* ダブルリンクキュー(リング) */
typedef struct queue {
    struct  queue   *next;
    struct  queue   *prev;
} QUEUE;

【形式】

Bool    isQueEmpty(QUEUE *que)

【パラメータ】

QUEUE *que  キュー構造へのポインタ

【リターン値】

True        キューは空である。
False       キューは空ではない。

【解説】

キューに要素が含まれているかどうかをチェックする。
空であるキューとは、 que == que->next, que == que->prev であるキューを意味する。

【形式】

VOID    QueInit(QUEUE *que)

【パラメータ】

QUEUE *que  キュー構造へのポインタ

【リターン値】

なし

【解説】

キューを空の状態 ( que == que->next, que == que->prev) に初期化する。

【形式】

VOID    QueInsert(QUEUE *entry, QUEUE *que)

【パラメータ】

QUEUE *entry    挿入するエントリへのポインタ
QUEUE *que      キュー構造へのポインタ

【リターン値】

なし

【解説】

que の直前に entry を挿入する。

【形式】

VOID    QueRemove(QUEUE *entry)

【パラメータ】

QUEUE *entry    削除するエントリへのポインタ

【リターン値】

なし

【解説】

entry をキューから削除する。 entry の直前と直後のエントリがリンクされる。 キューがすでに空である場合には、なにもしない。

【形式】

QUEUE   *QueRemoveNext(QUEUE *que)

【パラメータ】

QUEUE *que  キューのポインタ

【リターン値】

QUEUE*      取り出したエントリへのポインタ

【解説】

キューの先頭の要素をキューから取り出し、関数値として戻す。
キューが空であった場合には NULL を戻す。

【形式】

QUEUE   *QueSearch(QUEUE *start, QUEUE *end, W val, W offset)
QUEUE   *QueSearchH(QUEUE *start, QUEUE *end, H val, W offset)

【パラメータ】

QUEUE   *start  検索開始エントリ
QUEUE   *end    検索終了エントリ
W or H  val     検索する値
W       offset  検索する値へのキュー構造の先頭アドレスからのオフセット

【リターン値】

QUEUE*  検索したエントリ

【解説】

start の次のエントリから end の直前のエントリまでを検索する ( start と end のエントリはサーチ対象に含まれない)。 キュー構造の先頭アドレス + offset バイトの領域に位置するデータの内容が val と同じ値であるエントリを検索し、関数値として戻す。 該当するエントリが存在しなかった場合は関数値として end を戻す。 検索対象データのサイズによって、 QueSearch(), QueSearchH() の 2 つの関数がある。

【形式】

Inline  QUEUE   *QueSearchNE(QUEUE *start, QUEUE *end, W val, W offset)
Inline  QUEUE   *QueSearchNEH(QUEUE *start, QUEUE *end, H val, W offset)

【パラメータ】

QUEUE   *start  検索開始エントリ
QUEUE   *end    検索終了エントリ
W or H  val     検索する値
W       offset  検索する値へのキュー構造の先頭アドレスからのオフセット

【リターン値】

QUEUE*  検索したエントリ

【解説】

start の次のエントリから end の直前のエントリまでを検索する ( start と end のエントリはサーチ対象に含まれない)。
キュー構造の先頭アドレス + offset バイトの領域に位置するデータの内容が val と異なる値であるエントリを検索し、関数値として戻す。 該当するエントリが存在しなかった場合は関数値として end を戻す。 検索対象データのサイズによって、 QueSearchNE(), QueSearchNEH() の2つの関数がある。

【形式】

QUEUE   *QueSearchGE(QUEUE *start, QUEUE *end, W val, W offset)

【パラメータ】

QUEUE   *start  検索開始エントリ
QUEUE   *end    検索終了エントリ
W       val     検索する値
W       offset  検索する値へのキュー構造の先頭アドレスからのオフセット

【リターン値】

QUEUE*  検索したエントリ

【解説】

start の次のエントリから end の直前のエントリまでを検索する ( start と end のエントリはサーチ対象に含まれない)。
キュー構造の先頭アドレス＋offsetバイトの領域に位置するデータの内容が val 以上の値であるエントリを検索し、関数値として戻す。
該当するエントリが存在しなかった場合は関数値として end を戻す。

【形式】

QUEUE   *QueSearchGEU(QUEUE *start, QUEUE *end, W val, W offset)

【パラメータ】

QUEUE   *start  検索開始エントリ
QUEUE   *end    検索終了エントリ
W       val     検索する値
W       offset  検索する値へのキュー構造の先頭アドレスからのオフセット

【リターン値】

QUEUE*  検索したエントリ

【解説】

start の次のエントリから end の直前のエントリまでを検索する ( start と end のエントリはサーチ対象に含まれない)。 キュー構造の先頭アドレス + offset バイトの領域に位置するデータの内容が val 以上の値であるエントリを検索し、 関数値として戻す。 データの内容と val の内容は符号無し整数 (32bit) の値として比較される。 該当するエントリが存在しなかった場合は関数値として end を戻す。

【形式】

QUEUE   *QueSearchRevLTU(QUEUE *start, QUEUE *end, W val, W offset)

【パラメータ】

QUEUE   *start  検索開始エントリ
QUEUE   *end    検索終了エントリ
W       val     検索する値
W       offset  検索する値へのキュー構造の先頭アドレスからのオフセット

【リターン値】

QUEUE*  検索したエントリ

【解説】

start の次のエントリから end の直前のエントリまでを検索する ( start と end のエントリはサーチ対象に含まれない)。
キュー構造の先頭アドレス + offset バイトの領域に位置するデータの内容が val よりも小さなエントリを検索し、関数値として戻す。 データの内容と val の内容は符号無し整数 ( 32bit ) の値として比較される。
該当するエントリが存在しなかった場合は関数値として end を戻す。