ヘッダだけで使えるCのコンテナライブラリ uthash

Cには標準のコンテナライブラリがありません。有名なOSSは自前の実装を抱えているようですが、小規模なプロダクトではそうはいかないので、何かしらのライブラリを利用するのが現実的です。

といっても、デファクトスタンダードのようなものが見当たらないので、とりあえずuthashを試してみました。GLibが有力かなとも考えたのですが、少しコンテナを使いたいだけなのに大げさすぎるかなというのと、uthashはヘッダファイルをインクルードするだけで使えるというのがあって、とりあえずuthashを選択しました。修正BSDライセンスで利用できるというのも、場合によってはポイントになるかなと思います。

uthash: a hash table for C structures

この記事では、uthashの使い方を簡単に紹介します。uthashにはハッシュテーブルだけでなくリンクリスト (単方向/双方向/双方向循環)・動的配列・動的文字列も含まれていますが、今回はそれらには触れません。

使い方

インストール

ヘッダファイルだけで利用できるので、srcディレクトリにパスを通すなりコピーして自分のところに持ってくるなりすればOKです。

構造体の定義

uthashでは、構造体に管理用のハンドルを埋め込むことでその構造体を扱うことができるようになります。hhというメンバがそれです。hh以外の名前にすることも可能ですが、記述が増えて面倒なので、複数キーを扱うなどの目的以外ではオススメはしません。

struct my_struct {
  char key[32];
  int value;

  UT_hash_handle hh;
};

keyは構造体のキーです。こちらは自由な名前を付けることができます。今回は文字列を構造体に埋め込んでいますが、整数・文字列のポインタ・ポインタ・構造体をキーにすることも可能です。

宣言

struct my_struct *table = NULL;

要素の追加

struct my_struct *item = malloc(sizeof(struct my_struct));
strncpy(item->key, "abc", 32);
item->value = 123;
HASH_ADD_STR(table, key, item);

ただし、この時 “abc” というkeyの要素がハッシュテーブルに存在してはならず、そのことを保証するのは利用者の責任です。すでに要素が存在する場合にはその要素を取得し、存在しない場合だけ追加するのであれば以下のようにします。

struct my_struct *item;
HASH_FIND_STR(table, "abc", item);
if (item == NULL) {
  item = malloc(sizeof(struct my_struct));
  strncpy(item->key, "abc", 32);
  HASH_ADD_STR(table, key, item);
}
/* ... */

要素の検索

struct my_struct *item;
HASH_FIND_STR(table, "abc", item);

イテレーション

struct my_struct *item;
for (item = table; item != NULL; item = item->hh.next) {
  /* ... */
}

ただし、これだと途中で要素を削除するとうまく動作しないため、ループ内でHASH_DELを利用する場合はHASH_ITERを利用します。

struct my_struct *item, *tmp;
HASH_ITER(hh, table, item, tmp) {
  /* ... */
}

要素の削除

struct my_struct *item;
HASH_FIND_STR(table, "abc", item);
HASH_DEL(table, item);
free(item);

すべての要素を削除する場合はHASH_ITERと組み合わせます。

struct my_struct *item, *tmp;
HASH_ITER(hh, table, item, tmp) {
  HASH_DEL(table, item);
  free(item);
}

要素数のカウント

unsigned int count = HASH_COUNT(table);

ハッシュテーブルを引数に取る関数

uthashはマクロで構築されているので分かりづらいのですが、tableの中身は機能の呼び出しによって変化しています。そのため、ハッシュテーブルを引数に取る関数を作る場合は、以下のように要素のポインタのポインタを受け取るようにし、新しい値が関数の呼び出し元に反映されるようにします。

void add_item(struct my_struct **table, const char *key, int value) {
  struct my_struct *item = malloc(sizeof(struct my_struct));
  strncpy(item->key, key, 32);
  item->value = value;
  HASH_ADD_STR(*table, key, item);
}