GLibのハッシュテーブルをVala言語で用いる(前半)
GLibにはハッシュテーブルというデータ構造があり、これを用いるとキーとなるデータとそれに対応する値とをまとめて幾つも格納することができる。キーとデータの型はそれぞれ任意となり、ハッシュテーブルごとにそれぞれの型を決めることができる。
ハッシュテーブルはC言語でも用いることはできるが、ここではより扱いやすいVala言語で扱うことにする。
オブジェクト生成
ハッシュテーブルはVala言語からはHashTableというクラスのオブジェクトとして用いることができる。しかし、これはGLibの機能なのでGObjectライブラリ(GLibの上で動作)の提供するオブジェクトシステム上のオブジェクトではなく、Compactなクラス*1となっている。
キーとデータの型はそれぞれ任意と書いたが、オブジェクト生成時に「<」と「>」でキー,値の順にコンマ区切りで型名を記述したものを囲んだもの(例:「<string,int>」)を「HashTable」の右に付ける。
コンストラクタ引数は2つあり、1つ目はキーのデータをハッシュ計算するための関数,2つ目はキーのデータを比較するための関数をそれぞれ指定するのだが、これはキーの型に応じたものを選択する。それぞれに適する関数はGLibが用意しており、キーの型が文字列型であれば
- 1番目の引数:GLib.str_hash()
- 2番目の引数:GLib.str_equal()
への参照を指定すればよい。他の型では上の「str」の部分が「int」「int64」「direct」のものがあり、1番目のコンストラクタ引数をnullにした場合はGLib.direct_hash(),2番目の引数をnullにした場合ではGLib.direct_equal()が用いられる。
下はキーにstring,値にintの型を用いる場合のオブジェクト生成の例。
// オブジェクト変数の宣言 GLib.HashTable<string,int> fruits; // オブジェクト生成 fruits = new GLib.HashTable<string,int> (GLib.str_hash, GLib.str_equal);
関数の中で宣言して使う場合は下のようにも書ける。
// 関数の中で宣言して用いる場合 var fruits = new GLib.HashTable<string,int> (GLib.str_hash, GLib.str_equal); });
コンストラクタ引数で指定する2つの関数は自分で定義することもでき、ハッシュ計算の関数は1つのvoid *型の引数(キーのデータが入る)を受け取る。比較の関数では2つのvoid *型の引数(2つのキーのデータが入る)を受け取り、中で一致の判定を行った上で一致した場合にtrue,一致しない場合にfalseを返すようにする。ここを間違えるとデータの出し入れが正常に行われない場合がある。
上のオブジェクト生成の記述は
fruits = new GLib.HashTable<string,int> (GLib.str_hash, (a, b) => { // 引数はvoid *型なので文字列としての比較のために型変換をする return ((string) a == (string) b); });
と書くこともできる。
データの出し入れ
データの書き込み
insert()やreplace()はキーと値をその順に引数として受け取り、テーブルにそのデータを追加し、既に同じキーのデータがあるときにその値を置き換える。
これらの違いはドキュメントでは分かりにくかったのでソースを見たのだが
[引用]ファイル名: glib-2.24.2/glib/ghash.c より
void g_hash_table_insert (GHashTable *hash_table, gpointer key, gpointer value) { g_hash_table_insert_internal (hash_table, key, value, FALSE); } void g_hash_table_replace (GHashTable *hash_table, gpointer key, gpointer value) { g_hash_table_insert_internal (hash_table, key, value, TRUE); } /* * g_hash_table_insert_internal: * @hash_table: our #GHashTable * @key: the key to insert * @value: the value to insert * @keep_new_key: if %TRUE and this key already exists in the table * then call the destroy notify function on the old key. If %FALSE * then call the destroy notify function on the new key. * * Implements the common logic for the g_hash_table_insert() and * g_hash_table_replace() functions. * * Do a lookup of @key. If it is found, replace it with the new * @value (and perhaps the new @key). If it is not found, create a * new node. */ static void g_hash_table_insert_internal (GHashTable *hash_table, gpointer key, gpointer value, gboolean keep_new_key) { GHashNode *node; guint node_index; guint key_hash; guint old_hash; g_return_if_fail (hash_table != NULL); g_return_if_fail (hash_table->ref_count > 0); node_index = g_hash_table_lookup_node_for_insertion (hash_table, key, &key_hash); node = &hash_table->nodes [node_index]; old_hash = node->key_hash; if (old_hash > 1) { if (keep_new_key) { if (hash_table->key_destroy_func) hash_table->key_destroy_func (node->key); node->key = key; } else { if (hash_table->key_destroy_func) hash_table->key_destroy_func (key); } if (hash_table->value_destroy_func) hash_table->value_destroy_func (node->value); node->value = value; } else { node->key = key; node->value = value; node->key_hash = key_hash; hash_table->nnodes++; if (old_hash == 0) { /* We replaced an empty node, and not a tombstone */ hash_table->noccupied++; g_hash_table_maybe_resize (hash_table); } #ifndef G_DISABLE_ASSERT hash_table->version++; #endif } }
名前付きコンストラクタGLib.HashTable.full()でキーと値の解放に用いる関数(3番目と4番目のコンストラクタ引数)を定義してその中でキーや値の解放処理をするようにしているときにはreplace()では古いほうのキーのデータを解放し、insert()では新しいほうのキーのデータを解放するようになる(解放の対象が変わる)という違いがあるが、通常のコンストラクタを用いた場合など、他の多くの場合には動作に違いはないようだ。
(「GLibのハッシュテーブルをVala言語で用いる(後半)」に続く)
関連記事:
参考URL:
