GLib入門 GList編

今回はGList(紛らわしいがGSListではない)を扱う。

GListは双方向連結リストと呼ばれるデータ形式で、Lispのリストとはちと違う実装方式だ。

片方向連結リストはスロット/フィールドとしてdata、とnextと言うたった2つのポインタ変数を含む構造体だったが、双方向連結リストはそれに合わせてprevと言う、「自分を指してるGListオブジェクト」のアドレスをポインタ変数として保持するスロット/フィールドをも併せ持っている。

結果、「双方向連結リストの単位」は次のように図示される。

結果、Lispではあり得ない「逆cdr」と言うべき能力がある。

C++でもこの「双方向連結リスト」がList、と名付けられていて、C/C++では「双方向連結リスト」がリストの基礎だと捉えられているようだ(※1)。

とは言っても、GListの基本関数群の構成はGSListと全く同じだ。

登場順に、

g_list_append(GList* list, gpointer data): dataをlistのケツ側に追加していき、返り値はGList*。GSListのg_slist_appendにあたる。
g_list_insert(GList* list, gpointer data, gint position): dataをlistのposition番目に挿入する。返り値はGList*。GSListのg_slist_insertにあたる。
g_list_nth_data(GList* list, guint n): listのn番目が指してるデータのアドレス(gpointer)を返す。アドレスのメモリの中身が何の型になってるかはプログラマが分かってないとならない。GSListのg_slist_nth_dataにあたる。
g_list_remove(GList* list, gconstpointer data): listから最初に見つかったdataを削除したGListを返す。見つからなかったら何もしない。GSListのg_slist_removeにあたる。
g_list_length(GList* list): listの長さを返す。GSListのg_slist_lengthにあたる。
g_list_concat(GList* list1, GList* list2): list1とlist2を結合したGListを返す。GSListのg_slist_concatにあたる。
g_list_foreach(GList* list, GFunc func, gpointer user_data): GList用のg_slist_foreachのようなモノ。高階関数モドキ。コールバック関数であるGFuncは最大で二引数関数を想定してて、１つはuser_dataが手渡される。一引数関数の場合は、user_dataにNULLを与える。
g_list_reverse(GList* list): listを逆順に並べ替えたGListを返す。GSListのg_slist_reverseにあたる。
g_list_free(GList* list): listで使われたメモリを解放する。返り値はない。GSListのg_slist_freeにあたる。

とまぁ、GSListを使えてれば同機能のGList用関数がある、って事だ。

って事は前回見たような、ユーティリティ2つを作ってれば利便性も上がるだろう。

双方向連結リストと言うデータ型の特徴を表す例として次のようなモノを考える。

ここで新しく出て来た関数は登場順に次のようなモノだ。

g_list_last(GList* list): listの最後の部分を取り出す。そこもGListなんで返り値はGListになり、「中に何が含まれてるのか」はdataフィールド/スロットの指してるアドレスの中身を具現化しないと分からない。
g_list_first(GList* list): listの最初の部分を取り出す。そこもGListなんで返り値はGListになり、「中に何が含まれてるのか」はdataフィールド/スロットの指してるアドレスの中身を具現化しないと分からない。
g_list_previous(list): ホントは関数じゃなくマクロ。実態はGListのprevフィールド/スロットを取り出しているだけ。つまりアロー演算子を使ったGListオブジェクト->prevがその本体だ。
g_list_nth_prev(GList* list, guint n): 現在のGListからn個分遡った(prevした)GListを返す。

特に4番の関数に着目してほしい。29行目で、ポインタ変数lastにはlistの最後の項を代入してる(正確にはlistの最後のアドレスだが)。

しかし、このコードはそこから「逆に辿って」、全く関係ない筈のlistの先頭情報やら「存在しない筈の」lastの前のGListの情報を手繰り寄せている。

これは、lastに入ってるGListの情報にprevと言うカタチで「自分を指してる」GListオブジェクトのアドレス情報を保有してるから、だ。

結果、Lispではあり得ない「逆cdr」みてぇな事が出来るわけだ。

> (define ls '("Austin" "Bowie" "Charleston"))
> (define lst (last-pair ls))
> lst
'("Charleston")
>
;;; Lispの場合は、最後のcons-cellを入手しても、それより「前」を手繰る事は出来ない。単方向連結リストが基本だからだ。

さて、単一のGListにリンクが2つ存在する、と言う事は、そのオブジェクトを消す、つまり、リンクを消滅させるのは単方向リストに比べると煩わしい、と言う事だ。

次のコードを見てみよう。

このコードで新しく出て来た関数は登場順に次のようなモノだ。

g_list_nth(GList* list, guint n): listのn番目のGListを返す関数。含まれてるdataを直接返す関数ではないので、気をつける事。dataはgpointerなんで、指してる先の中身を取り出すにはプログラマ側が型を指定しないとならない。
g_list_remove_link(GList* list, GList* llink): listからllinkとして指定されたGListを削除する。この時点でllinkのprevとnextはNULLに設定されるが、llink自体のメモリを解放するわけじゃないんで気をつける事(llink自体はメモリ上に残る)。なお、GSListにもg_slist_remove_linkと言う関数がある。
g_list_free_1(GList* list): 単項のGListであるlistを削除する。ただし、参照先がいきなり消えてしまえば、listを含んでるGListが指した先が急に無くなる、って事になるんで、バグの元となる。g_list_remove_linkと組み合わせて使う事。GSListではg_slist_free_1がこの関数の代わりとなる。
g_list_delete_link(GList* list, GList* link_): 機能的にはg_list_remove_link + g_list_free_1。2ステップが1つに纏められていて、どっちかっつーとこれを使った方が良い。GSListではg_slist_delete_linkがこの関数にあたる。

GListは「逆cdr」的機能があるんで面白いんだが、リンクを司る「ポインタ」が2つあるんで、GListから要素になってる部分GListを削除しようとすると、結構メンドイ事になる、ってのが分かると思う。

個人的な趣味の問題で言うと、GListは「恒久的データ」として扱った方が良い気がしてる。関数プログラミング的に「削除しない」データとして捉えた方がいいんじゃなかろうか。

最後に双方向連結リストに対するインデックスに纏わる関数を取り上げる。

新しく出て来た関数は登場順に、

g_list_index(GList* list, gconstpointer data): list内で(アドレス比較で)dataが見つかったインデックスナンバー(gint型)を返す。なお、インデックスナンバーは0から数え、見つからなかった場合は-1を返す。GSListではg_slist_index。
g_list_position(GList* list, GList* llink): g_list_indexと似てるが、「含有されてるデータ」を元にして探すのではなく、「リストの一部」(GListオブジェクト)を検索対象にしてる辺りが違う。こちらも返り値の型はgintで、先頭(0)から数えたインデックスナンバーを返し、発見出来なかった場合は-1を返す。GSListではg_slist_positionがこれにあたる。

だ。これらは特に難しくないだろう。