GitHubのプロジェクトページはこちらです。
はじめに
Cの構造体向けの非常に簡単なスタックマクロが、uthashの utstack.h に含まれています。自分のCプログラムでこれらのマクロを使うには、utstack.h をソースディレクトリにコピーし、プログラムで使用するだけです。
#include "utstack.h"これらのマクロは、侵入型の連結リストで実装されたスタックの基本操作を提供します。スタックは「push」「pop」「count」の操作に加え、スタックの先頭要素を取得する単純な操作をサポートします。
ダウンロード
ヘッダーファイル utstack.h をダウンロードするには、https://github.com/troydhanson/uthash のリンクからuthashをクローンするかZIPファイルを取得し、src/ サブディレクトリを確認してください。
BSDライセンス
このソフトウェアは修正版BSDライセンスで提供されています。自由に利用できるオープンソースソフトウェアです。
プラットフォーム
utstack マクロは、次の環境でテストされています。
-
Linux,
-
Mac OS X,
-
Windows（Visual Studio 2008およびVisual Studio 2010を使用）
使い方
スタック（リスト）の先頭ポインター
スタックの先頭ポインターは、単に要素の構造体へのポインターです。名前は自由に付けられます。必ず NULL で初期化してください。これはスタックの先頭要素へのポインターでもあります。
element *stack = NULL;スタックの操作
スタックの操作は、O(1)のpush、O(1)のpop、およびO(n)の要素数のカウントだけです。提供されているマクロでは、先頭要素以外のスタック要素に直接アクセスすることはできません。
コードを読みやすくするため、マクロ STACK_EMPTY(head) を head == NULL の代わりに、STACK_TOP(head) を head の代わりに使うことができます。
|
|
|
|
|
要素数を |
|
|
|
|
上の表に示したパラメーターは、次のとおりです。
stack
スタックの先頭ポインター（要素の構造体へのポインター）。
add
スタックに追加する要素の構造体へのポインター。
elt
popされた要素のアドレスが代入されるポインター。初期化は不要です。
tmp
elt と同じ型のポインター。内部で使用されます。初期化は不要です。
count
スタックの要素数が代入される整数。初期化は不要です。
使用例
このサンプルプログラムは、テキストファイルから名前を読み取り（1行に1つの名前）、各名前をスタックにpushします。その後、popして逆順に表示します。
名前のスタック
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "utstack.h"
#define BUFLEN 20
typedef struct el {
char bname[BUFLEN];
struct el *next;
} el;
el *head = NULL; /* important- initialize to NULL! */
int main(int argc, char *argv[]) {
el *elt, *tmp;
char linebuf[sizeof el->bname];
int count;
FILE *file = fopen("test11.dat", "r");
if (file == NULL) {
perror("can't open: ");
exit(-1);
}
while (fgets(linebuf, sizeof linebuf, file) != NULL) {
el *name = malloc(sizeof *name);
if (name == NULL) exit(-1);
strcpy(name->bname, linebuf);
STACK_PUSH(head, name);
}
fclose(file);
STACK_COUNT(head, elt, count);
printf("%d elements were read into the stack\n", count);
/* now pop, print, and delete each element */
while (!STACK_EMPTY(head)) {
printf("%s\n", STACK_TOP(head)->bname);
STACK_POP(head, elt);
free(elt);
}
return 0;
}next以外のフィールド名
要素の構造体の next フィールドに別の名前を付けている場合は、別のマクロ群を使う必要があります。これらは通常のマクロと同じように動作しますが、追加のパラメーターとしてフィールド名を受け取ります。
この「フィールド名を自由に指定できる」マクロ群を下に示します。いずれも名前の末尾が 2 です。それぞれ末尾に 2 がない対応するマクロと同じように動作しますが、最後の引数として next フィールドの名前を受け取ります。
|
|
|
|
|
要素数を |