|
C MAGAZINE Linux programming Tips
第10回 GLib プログラミング 後半
■はじめに
GLibは、アプリケーションの開発を行う際に便利な機能をまとめたC言語用のライブラリーです。もともと GLibはLinux上で開発され 、 GTK+やGNOME関連のアプリケーションなどが利用しています。GLibは、既に数多くのシステムに移植されておりUNIX互換システムやWindows上でも利用可能です。 GLibが提供している機能を２つに分別することができます。一つは、前回のGLib プログラミング前半で説明した、 (標準Cライブラリーの)glibcが提供している関数には類似しているがより利便性や移植性を向上させた機能です。もう一方は、配列、リスト、 ハッシュやバイナリーツリーなのどデータ構造、字句解析(Lexical Scanner)機能やイベントドリブン機構などです。これらはglibcでは提供されていません。後半の今回は、 プログラミングの際に頻繁に使われるであろうデータ構造の配列、ハッシュ、を解説します。
■プログラミング/ハックを始める前に
今回は、GLibの機能を全て紹介できないためGLibが持つ関数のリファレンスが載っているURLを示しておきます。このリファレンスには、 サンプルプログラムや使用例はあまり載っていませんが、GLibが提供する関数の情報を得ることができますので、 今回紹介することができなかった機能を使用したい場合は参考になると思います。
http://developer.gnome.org/doc/API/glib/index.html
ここで簡単なサンプルプログラムとそれのMakefileを紹介します。コンパイラーオプションに関しては、このMakefileを参考にしてください。
リスト1 : Makefile
PROGS=hello
ifeq (on,$(DEBUG))
CFLAGS=-Wall `/usr/local/bin/glib-config --cflags` -g
LDLIBS=`/usr/local/bin/glib-config --libs` -static
else
CFLAGS=-Wall `glib-config --cflags`
LDLIBS=`glib-config --libs`
endif
all: $(PROGS)
clean:
rm -f $(PROGS) |
リスト2: hello.c
#include <glib.h>
int main(int argc, char* argv[])
{
g_print("Hello GLib World!\n");
g_mem_profile(); /* configureで--enable-mem-profile指定時のみ有効 */
return 0;
} |
■GLibのデータ構造
GLibは、データ構造として以下のリストのような機能を提供します。
このようなデータ構造は、ある程度のプログラムを記述する際に避けては通れないものだと思います。 最近の言語処理系においてはこのような機能は言語仕様として始めから利用できるようになっておりますが、 効率を優先したC言語は不幸にも言語仕様としては持っておりません。皆さんも、プログラムを書く毎に、 このようなデータ構造を書いた経験があるのではないかと思います。GLibは、(中にはマイナーなものも含まれますが、) 一般的によく利用されるデータ構造を提供します。汎用的ではありますが、ほとんどの状況で利用できます。この中でも特にメジャーな配列、 ハッシュテーブルのGLibによる定義とそのプログラミングについて説明します。
| |
配列( GArray, GByteArray, GPtrArray )
通常、C言語では、malloc()関数などによってメモリー領域を確保し使用しますが、それは固定長のメモリー確保のため、 サイズ変更が必要になるたびに realloc() 関数を呼び出す必要があります。 realloc() 関数を呼ぶのが面倒なので絶対に使いきらないぐらいの大きなメモリー領域を確保しておくのもナンセンスかもしれません。GLibは、 データの追加、削除に応じて必要なデータ格納領域のメモリーの確保、開放を自動的に行う配列を提供してくれます。
配列の型としては、GArray, GByteArray, GPtrArray の３種類があります。 GArrayは、サイズNバイトの大きさの要素の配列を提供します。GByteArrayは、 GArrayの実装とほぼ同じですが、guint8型で定義されているtype-safeな配列です。GPtrArrayは、ポインター配列に特化した配列で、 オペレーションも上記の２つとは異なります。
まずGLibによる配列の宣言を見てみましょう。以下は、ヘッダー glib.h で定義されているものです。 プログラム側からデータ配列へのポインターとその長さを参照できることが分かります。
typedef struct _GArray GArray;
typedef struct _GByteArray GByteArray;
typedef struct _GPtrArray GPtrArray;
struct _GArray
{
gchar *data;
guint len;
};
struct _GByteArray
{
guint8 *data;
guint len;
};
struct _GPtrArray
{
gpointer *pdata;
guint len;
}; |
しかしライブラリー内部では、以下のように定義されています。ちょっとしたテクニックでデータ隠蔽を行っています。 プログラム側に見せたくないところは隠されているわけです。この例の場合、alloc,elt_size,zero_terminatedと clear(C++言語的に言うとプライベート変数)になります。実際、 他の型も同様にこのようなテクニックが使われています。興味があれば、ヘッダーファイルと実際に処理している部分を比べてみてください。
struct _GRealArray
{
guint8 *data;
guint len;
guint alloc;
guint elt_size;
guint zero_terminated : 1;
guint clear : 1;
};
struct _GRealPtrArray
{
gpointer *pdata;
guint len;
guint alloc;
}; |
配列が実際に作られたときのイメージを、以下の図で表してみました。 zero_terminatedが指定されたとき配列の最後にゼロが埋められた要素が余計に一つ追加されます。
配列の作成、破壊
GArrayは、g_array_new() 関数で生成され、g_array_free() 関数で破壊されます。C++言語の言葉をかりると、g_array_new() 関数はコンストラクター、 g_array_free() 関数デストラクターのようなものです。g_array_new() 関数が返したGArray型のポインター変数が示すものはインスタンスに対応します。 以下で説明する挿入、削除などの配列への操作は、メソッドに対応します。
配列の操作関数 - 作成、破棄 -
[関数宣言]
- 作成 -
GArray* g_array_new (gboolean zero_terminated,
gboolean clear,
guint element_size);
GByteArray* g_byte_array_new (void);
GPtrArray* g_ptr_array_new (void);
- 破壊 -
void g_array_free (GArray *array,
gboolean free_segment);
gpointer user_data);
void g_byte_array_free (GByteArray *array,
gboolean free_segment);
void g_ptr_array_free (GPtrArray *array,
gboolean free_seg);
|
配列へのオペレーション
GArrayに関しては、データの挿入、追加および削除に関して５つのオペレーションを持っています(下図参照)。 remove_indexとremove_index_fastの処理に関して少し注意してください。removeは、データの順序を崩しませんが、 remove_fastは、 データの順序を崩します。その分、remove_fastは、削除した要素の部分へ一番最後にある要素を移動することでデータコピーの分の処理時間を短縮します。
配列の操作関数 - 削除、挿入 -
- GArrayの操作(メソッド) -
GArray* g_array_append_vals (GArray *array,
gconstpointer data,
guint len);
GArray* g_array_prepend_vals (GArray *array,
gconstpointer data,
guint len);
GArray* g_array_insert_vals (GArray *array,
guint index,
gconstpointer data,
guint len);
GArray* g_array_set_size (GArray *array,
guint length);
GArray* g_array_remove_index (GArray *array,
guint index);
GArray* g_array_remove_index_fast (GArray *array,
guint index);
#define g_array_append_val(a,v) g_array_append_vals (a, &v, 1)
#define g_array_prepend_val(a,v) g_array_prepend_vals (a, &v, 1)
#define g_array_insert_val(a,i,v) g_array_insert_vals (a, i, &v, 1)
#define g_array_index(a,t,i) (((t*) (a)->data) [(i)])
- GPtrArrayの操作(メソッド) -
#define g_ptr_array_index(array,index) (array->pdata)[index]
void g_ptr_array_set_size (GPtrArray *array,
gint length);
gpointer g_ptr_array_remove_index (GPtrArray *array,
guint index);
gpointer g_ptr_array_remove_index_fast (GPtrArray *array,
guint index);
gboolean g_ptr_array_remove (GPtrArray *array,
gpointer data);
gboolean g_ptr_array_remove_fast (GPtrArray *array,
gpointer data);
void g_ptr_array_add (GPtrArray *array,
gpointer data); |
GByteArrayに対する操作関数の名前は、関数名のプリフィックスをg_array_から g_byte_array_ に変更した名前で呼出しできます。GPtrArrayも基本的には、 関数名のプリフィックスをg_array_からg_ptr_array_ に変更しますが、操作関数が若干違います。GPtrArrayは、単純に追加するだけの add 操作 のみで、 insert, prepend 操作は持ちません。また削除に関しては、 そのコンテンツ(ポインター値)を比較してマッチした要素を削除する操作 remove, remove_fast が追加されています。
以下は簡単なサンプルプログラムです。GArray型の配列をgint型で生成し、0から9までの整数を追加します。 g_array_remove_index_fast()関数を使って追加した要素を削除します。その際に配列の中を表示するようにしているのでこの関数の動作がわかるようになっています。
リスト3: array.c
#include <glib.h>
int main(int argc, char* argv[])
{
GArray* array;
gint i,j;
array = g_array_new(FALSE,FALSE,sizeof(gint));
for(i=0; i<10; i++) {
g_array_append_val(array, i);
g_assert(g_array_index(array, gint, i) == i);
}
for(i=0; i<10; i++) {
g_array_remove_index_fast(array,0);
for(j=0; jlen ; j++ )
g_print("%d ", g_array_index(array, gint, j) );
g_print("\n");
}
g_array_free(array,FALSE);
return 0;
} |
ハッシュテーブル(GHashTable)
GLibは、ハッシュテーブルの機能を提供しています。ハッシュテーブルは、データの個数に関係なくデータの操作(挿入、削除、 検索)を実質的に一定時間で行うハッシュ方に基づくデータ構造です。実際のプログラミングにおいて、 ハッシュテーブルの利用は実用性の高い場合が多いです。いくつかのプログラミング言語 (Perl, Python など)では、 ハッシュテーブルの応用である連想配列の機能を基本言語仕様として持っています。C言語でプログラムを作成する際も必要な場合があるでしょう。
まず最初に、簡単に基本原理を説明しておきます。ある(正の)整数の値を持つキーとそのキーに関連するデータの群があるとします。 キーの値は重複しないものとすると、整数の最大値の大きさの配列を用意しておくことでデータを格納でき、 キーにより即座にデータを検索することができます。当り前のことですがこれが基本原理です。
テーブル(一次元の配列)をアクセスするため最終的なキーは整数ですが、もちろん文字列を使用することもできます。配列の大きさを100とした場合、 以下のような関数(ハッシュ関数と呼ばれる)によりキーを生成することで、あるデータを文字列を利用し参照することができます。 他言語で言うところの連想配列に似たような処理が可能になります。
簡単なハッシュ関数
int hashval(char* p)
{
int v=0;
while(*p) v+=*p++;
return v % 100;
} |
しかしハッシュ関数が返す値は、有限の大きさのテーブルに対して行うため違う文字列でも同じハッシュ値が得られてしまい、 データを登録する場所が重複してしまうと言う問題が発生します(衝突という状態)。ハッシュ法では、一般に、 チェイン法あるいはオープンアドレス法と呼ばれる方法で衝突を回避します。GLibの実装では、チェイン法が使用されており、 衝突が発生すると、あとから追加されたデータは連結リストでつなぐ方法を採用しています(図3参照)。
では、実際にGLibのハッシュテーブルを利用するプログラミングを解説します。
ハッシュテーブル構造体
以下は、GLibがハッシュテーブルを実現するために利用している構造体宣言です。しかしこの宣言はアプリケーション側からはみることができません。 良く言えばこの構造体はカプセル化されています。GLibが提供するハッシュ機構を理解するには、まずこの構造体を理解しておくことが近道かもしれません。
typedef struct _GHashNode GHashNode;
struct _GHashNode
{
gpointer key;
gpointer value;
GHashNode *next;
};
struct _GHashTable
{
gint size;
gint nnodes;
guint frozen;
GHashNode **nodes;
GHashFunc hash_func;
GCompareFunc key_compare_func;
}; |
ハッシュテーブルの作成および破棄
ハッシュテーブルは、基本的に、GHashTableのインスタンスを g_hash_table_new()によって作成し, GHashTableのインスタンスに対して挿入や検索などの処理を行いg_hash_table_destroy()で破棄する流れになります。
ハッシュテーブル操作関数 - 作成、破棄 -
[関数宣言]
- 作成 -
GHashTable* g_hash_table_new (GHashFunc hash_func,
GCompareFunc key_compare_func);
guint (*GHashFunc) (gconstpointer key);
gint (*GCompareFunc) (gconstpointer a,
- ポインター値用 ハッシュ関数、比較関数 -
gint g_direct_equal (gconstpointer v,
gconstpointer v2);
guint g_direct_hash (gconstpointer v);
- 整数値用 ハッシュ関数、比較関数 -
gint g_int_equal (gconstpointer v,
gconstpointer v2);
guint g_int_hash (gconstpointer v);
- 文字列用 ハッシュ関数、比較関数 -
gint g_str_equal (gconstpointer v,
gconstpointer v2);
guint g_str_hash (gconstpointer v);
- 破棄 -
void g_hash_table_destroy (GHashTable *hash_table);
guint g_hash_table_foreach_remove (GHashTable *hash_table,
GHRFunc func,
gpointer user_data);
gboolean (*GHRFunc) (gpointer key,
gpointer value,
gpointer user_data);
[使用例]
GHashTable* table;
table = g_hash_table_new(g_direct_hash, g_direct_equal);
...
(処理)
....
g_hash_table_destroy(table); |
まずテーブルの作成に関してですが、ハッシュ関数、比較関数を登録する必要があります。 それぞれ関数ポインター型 GHashFunc, GCompareFuncにあった関数を登録することになります。GLibは、ディフォルトで、ポインター値、 整数値あるいは文字列に対するハッシュ関数、比較関数を提供しています。上記の使用例では、ポインター値に対する関数を指定しています。
もしオリジナルのハッシュ関数、比較関数を実装したい場合、以下を参考にしてください。
static guint hash_func(gconstpointer key)
{
gchar *str = (gchar*)key;
guint val=0;
int i;
if( key==NULL) return 0;
for(i=0; i |
ハッシュテーブルの破棄に関してですが、キー、データともポインター値、整数値に元ずく操作の場合は、 新たにメモリー確保が発生しないため g_hash_table_destroy()を利用することができますが、 キーやデータを文字列もしくは他の型などのハッシュテーブルのバッケト以外にメモリーを確保している場合は、 g_hash_table_foreach_remove()を使用する必要があります(後述)。
ハッシュテーブルに対しては、データの挿入、削除および検索などの操作を行うことができます。これらの操作の挙動は、 テーブルを作成するときに設定したハッシュ関数、比較関数に依存します。以下に、データを操作する関数を示します。 ほとんどが直観的に使い型がわかる関数だと思いますが、 g_hash_table_remove()の使用には注意が必要です。 もしキーやデータを動的にメモリーを確保している場合は、不用意にg_hash_table_remove()を呼ぶとバケットの領域のみ解放し、 キーやデータの領域を解放しないままリンクを気ってしまうことになります。g_hash_table_lookup_extended()によりオリジナルキー、 データのアドレスをあらかじめ取得しておく必要があります。
ハッシュテーブル操作関数 - データの操作 -
[関数宣言]
- データの挿入 -
void g_hash_table_insert (GHashTable *hash_table,
gpointer key,
gpointer value);
- データの削除 -
void g_hash_table_remove (GHashTable *hash_table,
gconstpointer key);
- データの検索 -
gpointer g_hash_table_lookup (GHashTable *hash_table,
gconstpointer key);
- データの検索(オリジナルキー/データの取得) -
gboolean g_hash_table_lookup_extended (GHashTable *hash_table,
gconstpointer lookup_key,
gpointer *orig_key,
gpointer *value);
- 全データの捜査 -
void g_hash_table_foreach (GHashTable *hash_table,
GHFunc func,
gpointer user_data);
void (*GHFunc) (gpointer key,
gpointer value,
gpointer user_data); |
リスト4は、いままでに紹介した関数を使ったサンプルプログラムです。この例では、 文字列定数を使用しているためメモリーを動的に確保する必要が無いので比較的処理は簡単になっています。
リスト4: simple-hash.c
#include <glib.h>
static void print_func(gpointer k, gpointer v, gpointer ud)
{
g_print("%s -> %s\n", (gchar*)k, (gchar*)v);
}
static void forachall(GHashTable* table)
{
g_print("[foreach all]\n");
g_hash_table_foreach(table, print_func, NULL);
g_print("-------------\n");
}
int main(int argc, char* argv[])
{
GHashTable* table;
gchar* ret;
gchar* orig_key;
gchar* val;
table = g_hash_table_new( g_str_hash, g_str_equal);
g_hash_table_insert( table, "one", "uno");
g_hash_table_insert( table, "two", "dos");
g_hash_table_insert( table, "three", "tres");
ret = g_hash_table_lookup( table, "two");
g_print("%s -> %s\n", "two", ret );
forachall(table);
g_hash_table_remove( table, "one");
forachall(table);
if( g_hash_table_lookup_extended( table,
"three",
(gpointer*)&orig_key,
(gpointer*)&val) == TRUE ) {
g_print("%s -> %s\n", orig_key, val);
}
g_hash_table_destroy(table);
return 0;
} |
次に、キー、データを動的に確保する例を紹介します(リスト5)。この例は、標準入力から一行毎に３つのトークンを読み込み、 先頭のトークンをキーとしハッシュテーブルに挿入するプログラムになっています。実は、このプログラム、 インストールされているRPMのリストを処理するプログラムだったりします(ごめんなさいRPMがインストールされていないシステムを使っている皆さん)。各行は、 最初のトークンをRPM名、２番目をバージョン、３番目をリリースの文字列を持ち、コマンドの第一引数にRPM名を指定すると検索し、 引数がないばあいは全部のリストを表示するようになっています。例えば、次のように実行します。
$ rpm -qa --qf "%{NAME} %{VERSION} %{RELEASE}\n" | ./hash kernel
kernel 2.2.18 2
the size of table= 604
$ rpm -qa --qf "%{NAME} %{VERSION} %{RELEASE}\n" | ./hash
...
...
the size of table= 604 |
リスト5: hash.c
#include <glib.h>
/* ------------------------------------------------------------
This program is free software; you can redistribute it and/or modify
it under ther terms of GNU General Public License, version 2.
written by Kazutomo Yoshii
------------------------------------------------------------ */
#include <stdio.h>
#include <stdlib.h>
#include <glib.h>
typedef struct {
gchar* ver;
gchar* rel;
} VR;
static void print_func(gpointer key, gpointer val, gpointer user_data)
{
g_print("%s %s %s\n", (gchar*)key, ((VR*)val)->ver, ((VR*)val)->rel );
}
static gboolean remove_func( gpointer key, gpointer val, gpointer ud)
{
VR* _val = val;
g_assert( key != NULL );
g_assert( _val != NULL );
g_assert( _val->ver != NULL );
g_assert( _val->rel != NULL );
g_free(key);
g_free(_val->ver);
g_free(_val->rel);
g_free(_val);
return TRUE;
}
int main(int argc, char *argv[])
{
GHashTable* table;
gchar buf[BUFSIZ];
gchar** tokens;
VR* vr;
table = g_hash_table_new(g_str_hash, g_str_equal);
while( fgets(buf, BUFSIZ,stdin)!=NULL ) {
g_strchomp( buf );
tokens = g_strsplit( buf, " ", 3 );
if( tokens[0] ) {
vr = g_new( VR, 1 );
vr->ver = g_strdup( tokens[1] );
vr->rel = g_strdup( tokens[2] );
g_hash_table_insert( table, g_strdup(tokens[0]), vr) ;
g_strfreev(tokens);
}
}
if( argc < 2 ) {
g_hash_table_foreach(table, (GHFunc)print_func, NULL);
} else {
VR* ret;
ret = (VR*)g_hash_table_lookup(table, argv[1]);
if( ret ) {
g_print("%s %s %s\n", argv[1], ret->ver, ret->rel);
}
}
g_print("the size of table= %d\n",g_hash_table_size(table));
g_hash_table_foreach_remove( table, (GHRFunc)remove_func, NULL);
return 0;
} |
その他、ハッシュテーブルの関数としてテーブルサイズに関係するものがあります。
ハッシュテーブル操作関数 - データの操作 -
[関数宣言]
- テーブルサイズの取得 -
guint g_hash_table_size (GHashTable *hash_table);
- テーブルのリサイズを止める -
void g_hash_table_freeze (GHashTable *hash_table);
- テーブルのリサイズを再開する -
void g_hash_table_thaw (GHashTable *hash_table); |
|
■さいごに
今回は、GLibが提供する機能の氷山の一角しか紹介できませんでしたが、まだまだ興味深い機能がたくさんあります。例えば、 字句解析(Lexical Scanner)、 I/O関連、スレッドサポートなど大物がいっぱいあります。リファレンスやソースコードを頼み綱にしてハックしてみましょう。
|
