C で正規表現!

Ruby は超強力な正規表現エンジンである鬼雲を搭載しています。試しに鬼雲 (鬼車) の C API を使って、複雑なパターンマッチを試してみました。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "oniguruma.h"

int main(int argc, char *argv[])
{
  int rv;
  regex_t *re;
  OnigErrorInfo einfo;
  UChar *start, *end, *range;
  OnigRegion *region = onig_region_new();

  /* Programming Ruby 1.9 & 2.0 より */
  /* 正規表現パターン */
  UChar *pat = (UChar*)
      "(?<subject>   cat   | dog    | gerbil   ){0}"
      "(?<verb>      eats  | drinks | generates){0}"
      "(?<object>    water | bones  | PDFs     ){0}"
      "(?<adjective> big   | small  | smelly   ){0}"
      "(?<opt_adj>   (\\g<adjective>\\s)?      ){0}"
      "The\\s\\g<opt_adj>\\g<subject>\\s\\g<verb>\\s\\g<opt_adj>\\g<object>";
  /* マッチ対象 */
  UChar *str = (UChar*)"The cat drinks water";

  /* 正規表現オブジェクトの生成 */
  (void)onig_new(&re, pat, pat + strlen((char*)pat),
    ONIG_OPTION_DEFAULT | ONIG_OPTION_EXTEND,
    ONIG_ENCODING_UTF8,
    ONIG_SYNTAX_RUBY,
    &einfo);

  start = str;
  end = range = str + strlen((char*)str);

  /* パターン検索 */
  rv = onig_search(re, str, end, start, range, region, ONIG_OPTION_NONE);
  if (rv >= 0) {
    UChar *name = (UChar*)"subject";
    int *nsubject;
    /* 名前付きグループから番号 (の配列) を得る */
    rv = onig_name_to_group_numbers(re, name, name + strlen((char*)name),
        &nsubject);
    assert(rv > 0);
    char *subject = strndup((char*)(str + region->beg[nsubject[0]]),
        region->end[nsubject[0]] - region->beg[nsubject[0]]);

    name = (UChar*)"verb";
    int *nverb;
    rv = onig_name_to_group_numbers(re, name, name + strlen((char*)name),
        &nverb);
    assert(rv > 0);
    char *verb = strndup((char*)(str + region->beg[nverb[0]]),
        region->end[nverb[0]] - region->beg[nverb[0]]);

    /* 結果の表示 */
    printf("%s\n\n", (char*)str);
    printf("subject: %s\nverb: %s\n", subject, verb);

    free(subject);
    free(verb);
  }

  onig_region_free(region, 1);
  onig_free(re);
  onig_end();

  return 0;
}

実行結果:

The cat drinks water

subject: cat
verb: drinks

これは凄い。しかし、簡単な文法で同じことができちゃうあたり、Ruby ってよく出来てるんだなあ…なんて思ったり。

ちなみに、Programming Ruby 1.9 & 2.0 は今どきの Ruby の機能を丁寧に解説していて勉強になります。

http://pragprog.com/book/ruby4/programming-ruby-1-9-2-0

(コウヅ)

広告

Ruby を組み込みまくれ!

Ruby は強力で便利なインタプリタ言語です。ちょっと調べてみたところ、Ruby (CRuby) は既存の C プログラムに簡単に組み込めることが分かりました。

まずは基本形 (?) です。CRuby の API リファレンスはこれです:http://docs.ruby-lang.org/ja/2.1.0/function/index.html

ちなみに、CRuby を configure する時に –enable-shared というオプションを付けると libruby.so を作ってくれます。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "ruby.h"

void sigint_handler(int sig)
{
  ruby_finalize();
  printf("bye!\n");
  exit(0);
}

int main()
{
  ruby_init();
  /* ちゃんと SIGINT に適当なハンドラをセットしておかないと、^C した途端
   * ruby インタプリタが Segmentation Fault を起こしてフリーズします
   * (KILL シグナルを送れば終了します)
   */
  signal(SIGINT, sigint_handler);

  for (int i = 0; i < 100; i++) {
    /* Kernel.puts i を実行する
     * ruby の「関数」は Kernel モジュールのメソッド
     */
    rb_funcall(rb_mKernel, rb_to_id(rb_str_new2("puts")), 1, INT2FIX(i));
    sleep(1);
  }

  ruby_finalize();
  return 0;
}

※ 2014-05-20
初期化と終了処理はこう書く模様?あと、ID は rb_to_id(rb_str_new2(“foo”)) と書くより rb_intern(“foo”) の方がどう見てもスマート!(詳しくは Extending Ruby 1.9 参照)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "ruby.h"

void sigint_handler(int sig)
{
  printf("bye!\n");
  exit(ruby_cleanup(0));
}

int main(int argc, char *argv[])
{
  ruby_sysinit(&argc, &argv);
  RUBY_INIT_STACK
  ruby_init();
  ruby_init_loadpath();

  /* ちゃんと SIGINT に適当なハンドラをセットしておかないと、^C した途端
   * ruby インタプリタが Segmentation Fault を起こしてフリーズします
   * (KILL シグナルを送れば終了します)
   */
  signal(SIGINT, sigint_handler);

  for (int i = 0; i < 100; i++) {
    /* Kernel.puts i を実行する
     * ruby の「関数」は Kernel モジュールのメソッド
     */
    rb_funcall(rb_mKernel, rb_intern("puts"), 1, INT2FIX(i));
    sleep(1);
  }

  return ruby_cleanup(0);
}

もうちょっと ruby 成分を増やして、for ループを ruby の Fixnum#times メソッドに変えてみましょう:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "ruby.h"

void sigint_handler(int sig)
{
  ruby_finalize();
  printf("bye!\n");
  exit(0);
}

/* proc の中身。yieldarg に yield された値が入る
 * 引数は必要なければ省略可 (rb_funcall の引数を変更し忘れないように)
 *   i.e. times_block(VALUE yieldarg) or times_block()
 */
VALUE times_block(VALUE yieldarg, VALUE foo)
{
  VALUE rv = rb_funcall(rb_mKernel,
      rb_to_id(rb_str_new2("puts")),
      2,
      foo,
      yieldarg);
  sleep(1);

  return rv;
}

int main()
{
  ruby_init();
  signal(SIGINT, sigint_handler);

  /* 100.times{|i| times_block.(i) } を実行する
   */
  rb_funcall_with_block(INT2FIX(100),
      rb_to_id(rb_str_new2("times")),
      0,
      NULL,
      rb_proc_new(times_block, rb_str_new2("foo!")));

  ruby_finalize();
  return 0;
}

ruby.h とかも眺めながら、何度か試してやっとこさできました…。

最近 mruby なんていう組込み機器向けの ruby も出たので、そちらも組み込みまくりましょう。CRuby と似たような感じです。こっちも mruby.h を見ながら頑張りましょう。なお、mruby は SIGINT のハンドラを書かなくても綺麗に終了するみたいです。

#include <stdlib.h>
#include <unistd.h>
#include "mruby.h"

mrb_state *mrb;

void sigint_handler(int sig)
{ 
  mrb_close(mrb);
  printf("bye!\n");
  exit(0);
}

int main()
{
  mrb = mrb_open();
  (void)signal(SIGINT, sigint_handler); 

  for (int i = 0; i < 100; i++) {
    mrb_funcall(mrb, mrb_top_self(mrb), "puts", 1, mrb_fixnum_value(i));
    sleep(1);
  }   
      
  mrb_close(mrb);

  return 0;
}

Ruby のスクリプトファイルを用意しておいて、C からそのファイルで定義したメソッドを呼んだり、ファイルの実行結果を取り出したりとやりたい放題。ちょっとしたツールにも ruby をバンバン組み込んでしまおう!

(コウヅ)

APR のハッシュテーブル(再挑戦)!

前回の続きです。需要の大きい C 言語用のハッシュテーブルです。GLib のハッシュテーブルと比べてみると面白いです。

APR のハッシュテーブルは GLib よりもコンパクトにまとまってるようです。また、APR 自体もそのようです。

APR は Apache License なので、LGPL を採用する GLib よりは使いやすい……のかな。この辺りの法律的な問題はよく分かりません。

なお、ハッシュテーブルではない辞書(連想配列)型として、apr_table_t なんていうのもあります。

include <stdio.h>
#include <assert.h>

#include <apr_pools.h>
#include <apr_hash.h>

/*
 * コンパイルのしかた:
 *   gcc -Wall -pedantic `pkg-config --cflags --libs apr-1` hoge.c
 *
 * API リファレンス:
 *   https://apr.apache.org/docs/apr/1.5/group__apr__hash.html
 */

int print_key_val(void *rec, const void *key, apr_ssize_t klen,
    const void *value);

int main(int argc, char *argv[])
{
  apr_pool_t *mp;
  apr_status_t rv;

  apr_hash_t *population;
  apr_hash_index_t *iter;
  const void *key;
  apr_ssize_t klen;
  void *val;

  int i;

  apr_hash_t *another_population;
  apr_hash_t *new_population;

  /* APR の初期化 */
  rv = apr_initialize();
  assert(rv == APR_SUCCESS);
  /* メモリプールの作成 */
  apr_pool_create(&mp, NULL);

  /* ハッシュテーブルの作成
   * キーに文字列以外のデータを使う場合、apr_hash_make_custom を呼ぶ
   */
  population = apr_hash_make(mp);

  /* 要素の追加 */
  key = "横浜市";
  apr_hash_set(population, key, strlen(key), (void*)3702225);
  /* 通常の NULL 終端の文字列を渡す場合、APR_HASH_KEY_STRING を
   * キーの長さの代わりに渡すことができる
   */
  apr_hash_set(population, "大阪市", APR_HASH_KEY_STRING,
      (void*)2682140);
  apr_hash_set(population, "名古屋市", APR_HASH_KEY_STRING,
      (void*)2272075);
  apr_hash_set(population, "札幌市", APR_HASH_KEY_STRING,
      (void*)1921237);
  apr_hash_set(population, "神戸市", APR_HASH_KEY_STRING,
      (void*)1539546);

  /* 要素の取得 */
  val = apr_hash_get(population, "横浜市", APR_HASH_KEY_STRING);
  printf("%s => %d\n", (char*)key, (int)(size_t)val);

  /* 要素の削除
   * バリューに NULL を指定すればよい
   */
  apr_hash_set(population, key, APR_HASH_KEY_STRING, NULL);
  if (apr_hash_get(population, key, APR_HASH_KEY_STRING) == NULL) {
    printf("要素数: %u\n", apr_hash_count(population));
    printf("そんなキーはありません……: %s\n", (char*)key);
  }

  /* for ループ */
  printf("\n----- 全要素一覧 -----\n\n");
  for (iter = apr_hash_first(mp, population); iter;
      iter = apr_hash_next(iter)) {
    apr_hash_this(iter, &key, &klen, &val);
    /* こう書いても同じ
     *   key = apr_hash_this_key(iter);
     *   val = apr_hash_this_val(iter);
     */
    printf("%s => %d\n", (char*)key, (int)(size_t)val);
  }

  /* for each */
  printf("\n----- 全要素一覧 -----\n\n");
  i = 0;
  apr_hash_do(print_key_val, &i, population);


  another_population = apr_hash_make(mp);
  apr_hash_set(another_population, "夕張市", APR_HASH_KEY_STRING,
      (void*)10925);
  apr_hash_set(another_population, "三笠市", APR_HASH_KEY_STRING,
      (void*)10225);
  apr_hash_set(another_population, "歌志内市", APR_HASH_KEY_STRING,
      (void*)4020);

  /* ハッシュテーブルのマージ
   * 2つのテーブルのキーが衝突する際は第二引数のテーブルの値が優先する
   * キーの衝突時の挙動を指定するには、apr_hash_merge を使う
   */
  new_population = apr_hash_overlay(mp, population, another_population);
  printf("\n----- 全要素一覧 -----\n\n");
  i = 0;
  apr_hash_do(print_key_val, &i, new_population);

  /* メモリプールの破壊 */
  apr_pool_destroy(mp);

  return 0;
}

int print_key_val(void *rec, const void *key, apr_ssize_t klen,
    const void *value)
{
  printf("%d: %s => %d\n", (*(int*)rec)++, (char*)key,
      (int)(size_t)value);
  return 1;  /* 0 を返すとイテレーションが停止する */
}

実行結果:

横浜市 => 3702225
要素数: 4
そんなキーはありません……: 横浜市

----- 全要素一覧 -----

大阪市 => 2682140
名古屋市 => 2272075
神戸市 => 1539546
札幌市 => 1921237

----- 全要素一覧 -----

0: 大阪市 => 2682140
1: 名古屋市 => 2272075
2: 神戸市 => 1539546
3: 札幌市 => 1921237

----- 全要素一覧 -----

0: 神戸市 => 1539546
1: 夕張市 => 10925
2: 三笠市 => 10225
3: 札幌市 => 1921237
4: 歌志内市 => 4020
5: 名古屋市 => 2272075
6: 大阪市 => 2682140

(コウヅ)

APR の配列!

もう一度 APR のハッシュテーブルを紹介!の前に、配列 (apr_array_t) を紹介します。

#include <stdio.h>
#include <assert.h>

#include <apr_pools.h>
#include <apr_strings.h>
#include <apr_tables.h>

/*
 * コンパイルのしかた:
 *   gcc -Wall -pedantic `pkg-config --cflags --libs apr-1` hoge.c
 *
 * API リファレンス:
 *   https://apr.apache.org/docs/apr/1.5/group__apr__tables.html
 */

int main(int argc, char *argv[])
{
  apr_pool_t *mp;
  apr_status_t rv;

  apr_array_header_t *ary;
  void **item;
  int i;

  apr_array_header_t *another_ary;
  apr_array_header_t *new_ary;

  /* APR の初期化 */
  rv = apr_initialize();
  assert(rv == APR_SUCCESS);
  /* メモリプールの作成 */
  apr_pool_create(&mp, NULL);

  /* 配列の作成
   * 第一引数はメモリプール、第二引数は配列の要素数の初期値、
   * 第三引数は各要素の大きさ
   * 配列の長さは必要に応じて自動的に伸長する
   *
   * ここで void* 型の配列を作成しているので、ary->elts は void** になる
   */
  ary = apr_array_make(mp, 0, sizeof(void*));

  /* 要素の追加
   * 任意の場所に挿入する API はない
   */
  item = apr_array_push(ary);
  *item = "最初の要素";
  /* このように省略することもできる */
  *(void**)(apr_array_push(ary)) = "2番目の要素";
  /* 便利なマクロもある */
  APR_ARRAY_PUSH(ary, void*) = "3番目の要素";
  /* apr_pstrdup はメモリプール版の strdup.
   * free してはいけない
   */
  APR_ARRAY_PUSH(ary, void*) = apr_pstrdup(mp, "4番目の要素");

  /* 各要素の取得 */
  for (i = 0; i < ary->nelts; i++) {
    item = APR_ARRAY_IDX(ary, i, void*);
    /* APR_ARRAY_IDX マクロを使わない場合はこのようになる
     *   item = ((void**)(ary)->elts)[i];
     */
    printf("%d: %s\n", i, (char*)item);
  }

  /* 要素の取り出しと削除
   * 任意の場所の要素を削除する API はない
   * 要素が存在しない場合、NULL が返る
   *
   * 要素を free してはいけない (メモリプールが壊れる) ので、
   * apr_pstrdup や apr_palloc で作成した要素を削除したい時は、
   * 単に返り値を無視すればよい
   */
  (void)apr_array_pop(ary);

  /* 要素が文字列の場合、全要素を連結した文字列を作ることができる
   * (いわゆる join)
   * 返り値の文字列はメモリプール上に作成される
   */
  printf("\n----- 文字列の連結 (デリミタに '\\n' を指定) -----\n\n");
  printf("%s\n", apr_array_pstrcat(mp, ary, '\n'));

  another_ary = apr_array_make(mp, 0, sizeof(void*));
  APR_ARRAY_PUSH(another_ary, void*) = "5番目の要素";

  /* 2つの配列を連結して新しい配列を作る */
  new_ary = apr_array_append(mp, ary, another_ary);
  printf("\n----- 新しい配列 -----\n\n");
  for (i = 0; i < new_ary->nelts; i++) {
    item = APR_ARRAY_IDX(new_ary, i, void*);
    printf("%d: %s\n", i, (char*)item);
  }

  /* 既存の配列に別の配列をつなげる */
  apr_array_cat(another_ary, ary);
  printf("\n----- 配列の連結 -----\n\n");
  for (i = 0; i < another_ary->nelts; i++) {
    item = APR_ARRAY_IDX(another_ary, i, void*);
    printf("%d: %s\n", i, (char*)item);
  }

  /* 配列のコピー */
  new_ary = apr_array_copy(mp, another_ary);
  printf("\n----- 配列のコピー -----\n\n");
  for (i = 0; i < new_ary->nelts; i++) {
    item = APR_ARRAY_IDX(new_ary, i, void*);
    printf("%d: %s\n", i, (char*)item);
  }

  /* メモリプールの破壊 */
  apr_pool_destroy(mp);

  return 0;
}

実行結果:

0: 最初の要素
1: 2番目の要素
2: 3番目の要素
3: 4番目の要素

----- 文字列の連結 (デリミタに '\n' を指定) -----

最初の要素
2番目の要素
3番目の要素

----- 新しい配列 -----

0: 最初の要素
1: 2番目の要素
2: 3番目の要素
3: 5番目の要素

----- 配列の連結 -----

0: 5番目の要素
1: 最初の要素
2: 2番目の要素
3: 3番目の要素

----- 配列のコピー -----

0: 5番目の要素
1: 最初の要素
2: 2番目の要素
3: 3番目の要素

(コウヅ)

GLib のハッシュテーブル(再挑戦)!

前回 の続きです。今回は需要の大きい C 言語用のハッシュテーブルです。

GLib すごいけど、よく考えるとライセンスが LGPL なのでちょっと気をつけないといけません。

下のサンプルコードで色んな API を使ってみましたが、これで全部ではありません。

#include <glib.h>
#include <glib/gprintf.h>

/*
 * コンパイルの仕方:
 *   gcc -Wall -pedantic `pkg-config --cflags --libs glib-2.0` hoge.c
 *
 * API リファレンス:
 *   https://developer.gnome.org/glib/2.40/glib-Hash-Tables.html
 */

void destroy_key(gpointer key);
void destroy_val(gpointer val);
void print_key_val(gpointer key, gpointer val, gpointer user_data);

int main(int argc, char *argv[])
{
  GHashTable *population;
  gpointer key;  /* gpointer は総称ポインタ */
  gpointer val;

  GList *keys;
  GList *vals;
  GList *item;

  guint size;
  gchar **keysp;

  gint i;

  GHashTableIter iter;
  
  /* ハッシュテーブルの作成
   * 第一引数はキーをハッシュする関数、第二引数はキーを比較する関数
   * ハッシュ関数には g_direct_hash, g_int_hash, g_int64_hash,
   * g_double_hash, g_str_hash がある
   * 比較関数には g_direct_equal, g_int_equal, g_int64_equal,
   * g_double_equal, g_str_equal がある
   * キーやバリューを自動的に破壊する (free する) 必要がある場合は
   * g_hash_table_new_full を使い、デストラクタ (free 等) を指定する
   */
  population = g_hash_table_new(g_str_hash, g_str_equal);

  /* 要素の追加
   * ここでは gint 値を直接ポインタ型にキャストしている
   *
   * 追加したいキーが既にハッシュテーブルに存在する場合の挙動:
   *   g_hash_table_insert は古いバリューを破壊する
   *   g_hash_table_replace は古いバリューとキーを破壊する
   */
  g_hash_table_insert(population, "横浜市",
      GINT_TO_POINTER(3702225));
  g_hash_table_insert(population, "大阪市",
      GINT_TO_POINTER(2682140));
  g_hash_table_insert(population, "名古屋市",
      GINT_TO_POINTER(2272075));
  g_hash_table_insert(population, "札幌市",
      GINT_TO_POINTER(1921237));
  g_hash_table_insert(population, "神戸市",
      GINT_TO_POINTER(1539546));

  /* 要素の取得 */
  key = (gpointer)"横浜市";
  val = g_hash_table_lookup(population, key);
  g_printf("%s: %d\n", (gchar*)key, GPOINTER_TO_INT(val));

  /* 要素の削除
   * デストラクタを呼ばずに要素を削除したい場合は g_hash_table_steal を使う
   */
  g_hash_table_remove(population, key);
  val = g_hash_table_lookup(population, key);
  if (val == NULL) {/* g_hash_table_contains でもキーの存否が確認できる */
    g_printf("そんなキーはありません……: %s\n", (gchar*)key);
  }

  /* 全てのキーを取得する */
  keys = g_hash_table_get_keys(population);
  g_printf("\n----- 全キー一覧 -----\n");
  for (item = keys; item != NULL; item = g_list_next(item)) {
    g_printf("%s\n", (gchar*)item->data);
  }

  /* 全てのバリューを取得する */
  vals = g_hash_table_get_values(population);
  g_printf("\n----- 全バリュー一覧 -----\n");
  for (item = vals; item != NULL; item = g_list_next(item)) {
    g_printf("%d\n", GPOINTER_TO_INT(item->data));
  }

  /* 全てのキーを取得する
   * GList ではなく、配列として取得する方法
   */
  size = g_hash_table_size(population);
  /* g_new は calloc のようなもの */
  keysp = (gchar**)g_new(gpointer, size);
  /* g_hash_table_get_keys_as_array は NULL 終端の配列を返す */
  keysp = (gchar**)g_hash_table_get_keys_as_array(population,
      &size);
  g_printf("\n----- 全キー一覧 -----\n");
  for (i = 0; i < size; i++) {
    g_printf("%s\n", keysp[i]);
  }
  /* 用済みのキーの配列を free し忘れないように */
  g_free(keysp);

  /* for each */
  g_printf("\n----- 全キー・バリュー一覧 -----\n");
  i = 0;
  g_hash_table_foreach(population, print_key_val, &i);

  /* 全てのキー・バリューの組を取得する */
  g_printf("\n----- 全キー・バリュー一覧 -----\n");
  g_hash_table_iter_init(&iter, population);
  while (g_hash_table_iter_next(&iter, &key, &val)) {
    g_printf("%s => %d\n", (gchar*)key, GPOINTER_TO_INT(val));
  }

  /* イテレーションの最中にバリューを変更したり、組を削除することもできる */
  g_hash_table_iter_init(&iter, population);
  while (g_hash_table_iter_next(&iter, &key, &val)) {
    g_hash_table_iter_replace(&iter, GINT_TO_POINTER(4649));

    if (! g_strcmp0((gchar*)key, "神戸市")) {
      g_hash_table_iter_remove(&iter);
    }
  }
  g_printf("\n----- 全キー・バリュー一覧 -----\n");
  g_hash_table_iter_init(&iter, population);
  while (g_hash_table_iter_next(&iter, &key, &val)) {
    g_printf("%s => %d\n", (gchar*)key, GPOINTER_TO_INT(val));
  }

  /* ハッシュテーブルの破壊 */
  g_hash_table_destroy(population);


  /* ハッシュテーブルの作成 (デストラクタ付き) */
  population = g_hash_table_new_full(g_str_hash, g_str_equal,
      destroy_key, destroy_val);

  val = g_new(gint, 1);
  *(gint*)val = 10925;
  g_hash_table_insert(population, g_strdup("夕張市"), val);
  val = g_new(gint, 1);
  *(gint*)val = 10225;
  g_hash_table_insert(population, g_strdup("三笠市"), val);
  val = g_new(gint, 1);
  *(gint*)val = 4020;
  g_hash_table_insert(population, g_strdup("歌志内市"), val);

  g_printf("\nグッバイ、GHashTable!\n\n");
  g_hash_table_destroy(population);

  return 0;
}

void destroy_key(gpointer key)
{
  g_printf("%s を破壊します\n", (gchar*)key);
  g_free(key);
}

void destroy_val(gpointer val)
{
  g_printf("%d を破壊します\n", *(gint*)val);
  g_free(val);
}

void print_key_val(gpointer key, gpointer val, gpointer user_data)
{
  g_printf("%d: %s => %d\n", (*(gint*)user_data)++, (gchar*)key,
      GPOINTER_TO_INT(val));
}

実行結果:

横浜市: 3702225
そんなキーはありません……: 横浜市

----- 全キー一覧 -----
名古屋市
神戸市
大阪市
札幌市

----- 全バリュー一覧 -----
2272075
1539546
2682140
1921237

----- 全キー一覧 -----
札幌市
大阪市
神戸市
名古屋市

----- 全キー・バリュー一覧 -----
0: 札幌市 => 1921237
1: 大阪市 => 2682140
2: 神戸市 => 1539546
3: 名古屋市 => 2272075

----- 全キー・バリュー一覧 -----
札幌市 => 1921237
大阪市 => 2682140
神戸市 => 1539546
名古屋市 => 2272075

----- 全キー・バリュー一覧 -----
札幌市 => 4649
大阪市 => 4649
名古屋市 => 4649

グッバイ、GHashTable!

歌志内市 を破壊します
4020 を破壊します
夕張市 を破壊します
10925 を破壊します
三笠市 を破壊します
10225 を破壊します

(コウヅ)

GLib の双方向リスト!

C 言語用のハッシュテーブル探してる方が多いみたいです。僕もどんなのがあるか調べてみたんですが、やっぱり GLib か APR か、という気がします。

以前も GLib のハッシュテーブルを紹介しましたが、せっかくなので再チャレンジしましょう!が、今回は前哨戦で GLib の GList (双方向リスト) です!

API リファレンスはこれです:https://developer.gnome.org/glib/2.40/glib-Doubly-Linked-Lists.html

あと、コンパイルの仕方は gcc -Wall -pedantic `pkg-config –cflags –libs glib-2.0` hoge.c です。

#include <glib.h>
#include <glib/gprintf.h>

void print_list_item(gpointer data, gpointer user_data);

int main(int argc, char *argv[])
{
  /* GList は双方向リスト */
  GList *lst;
  GList *item;
  GList *another_lst;
  /* int と同じ */
  gint i;

  /* リストの作成には g_list_prepend を使う。第一引数は NULL */
  lst = g_list_prepend(NULL, "最初のデータ");
  /* prepend と append は各々スタックの unshift, push に相当する */
  /* prepend のオーダは O(1), append は O(n) */
  lst = g_list_append(lst,  "2番目のデータ");
  lst = g_list_append(lst,  "3番目のデータ");

  /* 最初の要素を取得する。gchar は char と同じ */
  item = g_list_first(lst);
  g_printf("%s\n", (gchar*)item->data);
  /* 2番めの要素を取得する */
  /* ただし、この場合は item = g_list_next(item) の方が手っ取り早い */
  item = g_list_nth(lst, 1);
  g_printf("%s\n", (gchar*)item->data);
  /* 最後の要素を取得する */
  item = g_list_last(lst);
  g_printf("%s\n", (gchar*)item->data);

  /* 要素を挿入する */
  lst = g_list_insert(lst, "4番目のデータ", 1);
  /* 要素を挿入する(別の方法) */
  lst = g_list_insert_before(lst, g_list_last(lst), "5番目のデータ");
  /* 最後から2番めに挿入する場合、g_list_last の代わりに
   * NULL を入れても同じ
   */
  lst = g_list_insert_before(lst, NULL, "6番目のデータ");

  /* 要素を削除する */
  /* free する必要がある時は g_list_delete_link を使う */
  lst = g_list_remove(lst, g_list_first(lst)->data);

  /* for ループ */
  g_printf("\n----- for ループ ------\n\n");
  for (item = lst, i = 0; item != NULL; item = g_list_next(item)) {
    print_list_item(item->data, &i);
  }

  /* for each */
  g_printf("\n----- for each ------\n\n");
  i = 0;
  g_list_foreach(lst, print_list_item, &i);

  /* ソート */
  g_printf("\n----- ソート ------\n\n");
  lst = g_list_sort(lst, (GCompareFunc)g_strcmp0);
  i = 0;
  g_list_foreach(lst, print_list_item, &i);

  /* リストのコピー */
  another_lst = g_list_copy(lst);

  /* 逆順に並び替え */
  another_lst = g_list_reverse(another_lst);

  /* リストの連結 */
  lst = g_list_concat(lst, another_lst);

  g_printf("\n----- リストの連結 ------\n\n");
  i = 0;
  g_list_foreach(lst, print_list_item, &i);

  /* リストの破壊 */
  /* 各要素も free する時は g_list_free_full を使う */
  g_list_free(lst);

  return 0;
}

void print_list_item(gpointer data, gpointer user_data)
{
  /* printf と同じ */
  g_printf("%d: %s\n", (*(gint*)user_data)++, (gchar*)data);
}

実行結果:

最初のデータ
2番目のデータ
3番目のデータ

----- for ループ ------

0: 4番目のデータ
1: 2番目のデータ
2: 5番目のデータ
3: 3番目のデータ
4: 6番目のデータ

----- for each ------

0: 4番目のデータ
1: 2番目のデータ
2: 5番目のデータ
3: 3番目のデータ
4: 6番目のデータ

----- ソート ------

0: 2番目のデータ
1: 3番目のデータ
2: 4番目のデータ
3: 5番目のデータ
4: 6番目のデータ

----- リストの連結 ------

0: 2番目のデータ
1: 3番目のデータ
2: 4番目のデータ
3: 5番目のデータ
4: 6番目のデータ
5: 6番目のデータ
6: 5番目のデータ
7: 4番目のデータ
8: 3番目のデータ
9: 2番目のデータ

(コウヅ)

C 言語のハッシュテーブル!

※ 2014-05-09 書き直しました

GLib のハッシュテーブルを使う は人気の記事のようなので、もう1つ C 言語のハッシュテーブルをご紹介します!

今回は Apache Portable Runtime のハッシュテーブルを使ってみました。Apache といえば人気の Web サーバーソフトウェアです。Apache は移植性を高めるために、独自のランタイムライブラリである APR の上に構築されています。APR の目玉はメモリ管理機能でしょうか。malloc とか free とかをこまめに呼び出すのではなく、まずメモリプールという 8 KB 程度の領域をあらかじめ確保し、malloc の代わりに apr_palloc でメモリプールから必要な大きさのメモリをもらいます。メモリを解放する時は、メモリプールごとドバッといきます。Apache はコネクション単位やセッション単位で色んなデータを作ったり消したり整理しないといけないので、こういう仕組みが適してる、ということなんでしょう。

APR にはメモリプール版の strdup である apr_pstrdup といった基本的な関数の他に、動的な配列や、ハッシュテーブルといったコンテナも用意しています。

ということで、GLib のハッシュテーブルを使う と同じ例を APR で書いてみました。

/*
 * Apache Portable Runtime のハッシュテーブルの使用例
 *   APR 1.4.5 で動作確認しました。
 *
 *   コンパイルの仕方:
 *     gcc `pkg-config --cflags --libs apr-1` <this_file>
 *
 *   リファレンスマニュアル:
 *     http://apr.apache.org/docs/apr/1.4/modules.html
 *
 *   参考にしたサイト:
 *     ありえるえりあ http://dev.ariel-networks.com/apr/apr-tutorial/html/apr-tutorial-19.html#ss19.3
 *
 * Linux 修験道 https://linuxshugendo.wordpress.com
 *                                             2014-02-28
 */
#include <stdio.h>
#include <assert.h>

#include <apr_pools.h>
#include <apr_strings.h>
#include <apr_hash.h>

int print_hash(void *rec, const void *key, apr_ssize_t klen, const void *value);

int main(int argc, char *argv[])
{
  apr_status_t rv;
  apr_pool_t *mp;
  apr_hash_t *ht;
  char *key;
  int *val;

  /* APR の初期化 */
  rv = apr_initialize();
  if (rv != APR_SUCCESS) {
    assert(0);
    return -1;
  }

  /* メモリプールの作成 */
  apr_pool_create(&mp, NULL);
  /* メモリプール上にハッシュテーブルを作成する */
  ht = apr_hash_make(mp);

  /* キー(文字列)のメモリ割当と文字列のコピー */
  key = apr_pstrdup(mp, "りんご");
  /* 値(int)のメモリ割当 */
  val = apr_palloc(mp, sizeof(int));
  *val = 100;
  /* key と val を ht に登録する */
  apr_hash_set(ht, key, APR_HASH_KEY_STRING, val);

  key = apr_pstrdup(mp, "いちご");
  val = apr_palloc(mp, sizeof(int));
  *val = 300;
  apr_hash_set(ht, key, APR_HASH_KEY_STRING, val);

  printf("要素削除前\n");
  /* いわゆる for each */
  apr_hash_do(print_hash, NULL, ht);

  /* 要素を削除するには、値に NULL をセットする */
  apr_hash_set(ht, "いちご", APR_HASH_KEY_STRING, NULL);
  printf("\n要素削除後\n");
  apr_hash_do(print_hash, NULL, ht);

  /* メモリプール領域を解放する。全てのキー、バリュー、テーブルが破壊される */
  apr_pool_destroy(mp);
  return 0;
}

int print_hash(void *rec, const void *key, apr_ssize_t klen, const void *value)
{
  printf("%s: %d 円\n", (char*)key, *(int*)value);
  return 1; /* Iteration continues while this callback function returns non-zero. */
}

以下実行例です:

me@kozu-mba-> gcc -Wall -pedantic hash_table.c `pkg-config --cflags --libs apr-1`
me@kozu-mba-> ./a.out 
要素削除前
いちご: 300 円
りんご: 100 円

要素削除後
りんご: 100 円

便利ですね!

(コウヅ)