読者です 読者をやめる 読者になる 読者になる

言語のしくみを読む

ライブラリとして使われているkhash.hを調べる。

C言語用のハッシュテーブルライブラリ。 ヘッダファイルkhash.hをインクルードするだけで利用できる。 マクロが多用してありその点、気をつけないとこける。

ハッシュテーブルに名前をつけ他のハッシュテーブルと区別する。 ハッシュテーブルの要素はバケット(bucket)と呼ばれている。 このバケットにvalueを入れていく。バケットにアクセスするには イーサレータでおこなう。データの追加時の衝突対策をどうやって いるのかはよくわからない。 ハッシュテーブルにはmap型とset型があるが違いがよくわからない 主にmap型を使用している。
コード例

An example:(khash.hにあるコード例)
#include "khash.h"

KHASH_MAP_INIT_INT(32, char) //ここでハッシュテーブルに'32'という名前を付けている。charはハッシュテーブルのデータ(value)型を指定
int main() {
  int ret, is_missing;
  khiter_t k; //ハッシュテーブルのバスケット(bucket)にアクセスするためのイーサレータ
  khash_t(32) *h = kh_init(32); //hはハッシュテーブルへのポインタ
  //kh_putが指定されたハッシュテーブルの任意のkeyに対してバスケットを作成する(この時点ではvalueは入っていない)
  //ret変数にはkeyがすでにハッシュテーブルに存在する場合は0、存在しない場合は1。この値でユーザー側が衝突対策をするのかな?
  k = kh_put(32, h, 5, &ret);
  kh_value(h, k) = 10; //ハッシュテーブルへのポインタ(h)とイーサレータ(k)で指定したバスケットにvalueを代入する
                                 //代入文ではなくprintf("bucket=%d\n",kh_value(h, k))とするとバスケットにvalueがあればそれを返してくる。
  k = kh_get(32, h, 10); //指定したハッシュテーブル・ポイントの指定したkey(ここでは10)に対応するバスケットがあればそのイーサレータを返す
                                    //なければ特別なイーサレータkh_end(h)を返すのでkeyに対応したバスケットはないことがわかる。次の文がそれを判定している。
  is_missing = (k == kh_end(h));
  k = kh_get(32, h, 5); 
  kh_del(32, h, k); //イーサレータ(k)に対応したバスケットを削除
  for (k = kh_begin(h); k != kh_end(h); ++k) //イーサレータをスキャンすることでハッシュテーブルを舐めることができる
    if (kh_exist(h, k)) kh_value(h, k) = 1; //kh_exist関数はイーサレータにデータがあれば1なければ0
  kh_destroy(32, h);  //ハッシュテーブルの破壊
  return 0;
}

ハッシュテーブルの生成

//整数キーを持つセット型ハッシュテーブルを作る
KHASH_SET_INIT_INT(name)->KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
//整数キーを持つマップ型ハッシュテーブルを作る
KHASH_MAP_INIT_INT(name, khval_t)->KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
//整数キー(64bit)を持つセット型ハッシュテーブルを作る
KHASH_SET_INIT_INT64(name)->KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
//整数キー(64bit)を持つマップ型ハッシュテーブルを作る
KHASH_MAP_INIT_INT64(name, khval_t)->KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
//文字列キーを持つセット型ハッシュテーブルを作る
KHASH_SET_INIT_STR(name)->KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
//文字列キーを持つマップ型ハッシュテーブルを作る
KHASH_MAP_INIT_STR(name, khval_t)->KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)

ハッシュテーブルの操作

整数キー同士が同じか判定する
kh_int_hash_equal(a,b) #整数キーの同一判定をする
kh_int64_hash_equal(a,b) #整数キー(64bit)の同一判定をする

与えられた整数キーをハッシュテーブルのindexにする関数
kh_int_hash_func(key)  #32bit
kh_int64_hash_func(key) #64bit->32bitのインデックスに変換する

与えられた文字列キーをハッシュテーブルのindexにする関数
kh_str_hash_func(key)

文字列キー同士が同じか判定する
kh_str_hash_equal(a,b)

名前を与えられたハッシュテーブルの初期化とインスタンス変数
khash_t, kh_init
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前

ハッシュテーブルのリセット
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
 ..
kh_clear(hashtable_name,h) #メモリはそのまま

ハッシュテーブルのリサイズ
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
 ..
kh_resize(hashtable_name,h,s) #sはリサイズ数

ハッシュテーブルにkeyを挿入(valueはまだ)
int ret;
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
    ret変数の解釈
    keyがハッシュテーブルに存在する場合は0,存在しない場合は1
    戻り値:
    挿入された要素のイテレータ、この時点ではhashtableにvalueのための領域(bucketと呼んでいる模様)がputされた
    だけでvalue自体はまだ。

ハッシュテーブルからキーを削除する
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
 ... 
kh_del(hashtable_name,h,key)

ハッシュテーブルのkeyにデータが入っているかテストする
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
 ...  
kh_exist(h,key)
 戻り値:データがあれば1,なければ0

ハッシュテーブルの要素数を取得
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_size(h)

 ハッシュテーブル内のバケット数を取得する
 khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
khint_t size = kh_n_buckets(h)

イーサレータ

ハッシュテーブルからkeyに対応したイーサレータを取得
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
khiter_t iter;
iter = kh_get(hashtable_name,h,key)

イータレータを指定してkeyを取得
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
 ...  
kh_key(h,iter)

イータレータを指定してvalueを取得、設定
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
...  
kh_val(h,iter) #kh_value(h,iter)としてもOK

スタートイータレータを取得
kh_begin(h) #最初のイータレータを返す

エンドイータレータを取得
kh_end(h) #最後のイータレータを返す

ハッシュテーブルの破壊

kh_destroy

khash_t(hashtable_name) *h = kh_init(hashtable_name)
....

kh_destroy(hashtable_name,h)

Google Maps javascript API V3入門マスターを読む

GoogleのAPIkeyは以前取得したものがあったのでそれを使用

例題のsample.html,map.jsを入力して、sample.htmlをブラウザーで読み込ましたが エラーがでて地図が表示されない。

デペロッパーツールを表示させると ApiNotActivatedMapErrorがでて地図が表示されないと出ているので

https://developers.google.com/maps/documentation/javascript/error-messages#api-not-activated-map-error

でApiNotActivatedMapErrorを検索、日本語に翻訳させると

GoogleマップJavaScript APIは、あなたのAPIプロジェクトでアクティブにされていません。 あなたは、Google APIコンソールでAPIの下にGoogle Maps JavaScript APIのを有効にする必要があります。」 とでたのでGoogleのAPIManagerでGoogle Maps JavaScript API有効にさせ、再度sample.htmlブラウザに読み込ませ ると無事地図を表示した。

言語のしくみを読む

例題の05filler.strmを実行してみる
オプションの-vをつけて実行してみると構文木を表示してくれる。

./streem -v ../examples/05filter.strm

05filter.strmの中身
    seq(100) | filter{x-> x % 2 == 0} | stdout
構文木を表示させたもの
    NODES:
    OP:
    op: |
    OP:
    op: |
    CALL:
    seq
    ARRAY:
    VALUE(NUMBER): 100
    CALL:
    filter
    ARRAY:
    LAMBDA:
    ARGS(1):
            x
    NODES:
            OP:
            op: ==
            OP:
            op: %
            IDENT: x
            VALUE(NUMBER): 2
            VALUE(NUMBER): 0
    IDENT: stdout

言語のしくみを読む

パーサで解析されたスクリプトは構造体のリンクで表現されたノードで返される。
state.lvalにつながれたリンク。

node(node_value)
type:NODE_STMTS
void** data

node(node_op)
type:NODE_OP
op:strm_string
len:1
ptr:“|”
lhs:
node(node_values)
type:NODE_ARRAY
data
node(node_value)
value:
t:NODE_VALUE_STRING
v.s->ptr:“Hello world
v.s->len:11
rhs:
node(node_value)
type:NODE_IDENT
v.s->ptr:“STDOUT”
v.s->len:6
ノードをかたち作るのはnode構造体でその末端に納められているデータなどはnode_valueに収められている
共用体でint,long,double,void:,strm_string(const char *ではない)
main関数のnode_run関数呼ぶ

exe_expr(ctx,(node)p->lval,&v)関数に構造体のリンクを投入する
リンクを辿りながらnodeのtypeごとに処理をしている。
最初はtype:NODE_STMTS
data[i]にリンクしてある次のノードを引数にexe_expr関数を再帰呼び出しをする。 リンクしてあるのはNODE_OPタイプのノードになる。
ノードのメンバーであるlhsにリンクされている次のノードを引数にexe_expr関数を呼ぶ
リンクされているのはNODE_ARRAY(node_values)タイプである。
ここであらかじめstrm_arrayの構造体を用意しておく。
ノード内のdataをexe_expr関数に渡して呼び出すとようやく末端データ構造体の
NODE_VALUE(NODE_VALUE_STRING)にたどり着く。
ノード構造体に入っているデータ(string型)をstrm_ptr_value関数を使って
strm_value構造体にタイプ型と一緒にコピーしている。
ノードのデータをstrm_value構造体にコピーする関数はvalue.cにまとめて入っている。
bool値(NODE_VALUE):
 strm_bool_value関数
nil値(NODE_VALUE_NIL):
 strm_nil_value関数
string,IDENT値:
 strm_ptr_value関数
double値:
 strm_flt_value関数
int値
 strm_int_value関数
これら関数を使ってノードに登録しておいたデータ(ここでは"Hello World")を
val(strm_value
)変数に格納しておく。

次にNODE_OPに戻ってきたらrhsを引数にexe_expr関数を呼ぶ。
rhs(右辺)にリンクされているのはNODE_IDENT(node_value)タイプで
strm_var_get関数を呼ぶ、このとき引数には右辺の"STDOUTが渡されている。
このstreemに設定してある識別子を探しているようだ。
見つけた識別子はstrm_value配列(args[2])保管しておき、exec_call関数に引数として渡す。
今回はSTRM_VALUE_CFUNCのexec_bar関数を呼び出す。
exec_bar関数内でlhsがARRAYタイプを探して行き
strm_alloc_stream関数を呼び実際にコールする関数をstart_funcに登録する
strm_task構造体
  id:-1
  mode:strm_task_prod
  start_func:arr_exec関数
  close_func:arr_finish関数
  data:
  dst:NULL
  nextd:NULL
  flags:0
続いて右辺の処理
rhs:ioを選択しstrm_value_io関数を呼び
strm_io構造体に値を設定する
  type:STRM_OBJ_IO
  fd:1
  mode:2
  read_task = 0x0
  write_task:0x0
これをstrm_io_open関数に渡す。
modeがSTRM_IO_WRITEなのでstrm_task構造体に設定して返してくる。
strm_task構造体
  id:-1
  mode:strm_task_cons
  start_func:write_cb関数
  close_func:write_close関数
  data:
  dst:NULL
  nextd:NULL
  flags:0
/task x task/
strem_connect関数を呼ぶ
task_init関数を呼び、task_loop関数をマルチスレッドで待機させておく
strem_connect関数に戻ってきたらstrm_tasak_push関数でtaskをキューに
押し込んでおく。
strem_queue_task構造体に設定する内容
strm:strm_task構造体で左辺のtask
func:arr_exec
data
next:NULL

ここでexec_bar関数に戻り、exec_call関数に戻り、exec_expr関数に戻る。
再帰で呼ばれていたexec_expr関数に次々に戻っていく。
node_run関数まで戻ったらmain関数のstrm_loop関数を呼ぶ
キューにタスクが詰められていたらstrm_queue_exec関数を呼び
実行させる。
このときに関数はwrite_cb関数で"Hello World"を標準出力に表示させた。

言語のしくみを読む

./strem ../examples/02hello.strmで実行
main.cのmain関数内のnode_parse_file(&state,argv[i])で止める
node.c内のnode_parse_file(parse_state p,const char fname)
fnameにはコマンドライン引数"../examples/02hello.strm"が入っている
fnameで指示されたファイルをリードモードで開いて読み込む。
実際にパースしているのはnode_parse_input関数。
yyrestart,yyparse関数内は複雑そうで見ていない。

結果は渡されたstate変数のlvalフィールドに格納されている。

通常はverbose変数はFALSEになっているがこれをTRUEにして
パースされたnodeを表示させてみる。

STMTS:
OP:
op: |
ARRAY:
VALUE(STRING): “Hello World
IDENT: STDOUT

もともとのスクリプト
[“Hello World”] | STDOUT

他のスクリプトも表示させてみる。

01car.strm
スクリプト
STDIN | STDOUT
パース展開
STMTS:
 OP:
  op: |
  IDENT: STDIN
  IDENT: STDOUT

03fizzbuzz.strm
スクリプト
seq(100) | {x ->
  if x % 15 == 0 {
    "FizzBuzz"
  }
  else if x % 3 == 0 {
    "Fizz"
  }
  else if x % 5 == 0 {
    "Buzz"
  }
  else {
    x
  }
} | STDOUT
パース展開
STMTS:
 OP:
  op: |
  OP:
   op: |
   CALL:
     NIL
     seq
     ARRAY:
      VALUE(NUMBER): 100
     NIL
   LAMBDA:
    ARGS(1):
     x
    IF:
     OP:
      op: ==
      OP:
       op: %
       IDENT: x
       VALUE(NUMBER): 15
      VALUE(NUMBER): 0
    THEN:
     VALUE(STRING): "FizzBuzz"
    ELSE:
     IF:
      OP:
       op: ==
       OP:
        op: %
        IDENT: x
        VALUE(NUMBER): 3
       VALUE(NUMBER): 0
     THEN:
      VALUE(STRING): "Fizz"
     ELSE:
      IF:
       OP:
        op: ==
        OP:
         op: %
         IDENT: x
         VALUE(NUMBER): 5
        VALUE(NUMBER): 0
      THEN:
       VALUE(STRING): "Buzz"
      ELSE:
       IDENT: x
  IDENT: STDOUT

04emit.strm
スクリプト
seq(100) | {x -> emit x, x} | STDOUT
パース展開
      STMTS:
      OP:
      op: |
      OP:
      op: |
      CALL:
      NIL
      seq
      ARRAY:
      VALUE(NUMBER): 100
      NIL
      LAMBDA:
      ARGS(1):
      x
      EMIT:
      ARRAY:
      IDENT: x
      IDENT: x
      IDENT: STDOUT

05skip.strm
スクリプト
seq(100) | {x -> if x % 2 == 1 {skip}; x} | STDOUT
パース展開
    STMTS:
    OP:
    op: |
    OP:
    op: |
    CALL:
    NIL
    seq
    ARRAY:
    VALUE(NUMBER): 100
    NIL
    LAMBDA:
    ARGS(1):
    x
    STMTS:
    IF:
    OP:
    op: ==
    OP:
            op: %
            IDENT: x
            VALUE(NUMBER): 2
    VALUE(NUMBER): 1
    THEN:
    IDENT: skip
    IDENT: x
    IDENT: STDOUT

06echo.strm
スクリプト
    tcp_server(8007) | {s ->
    s | s
    }
パース展開

    STMTS:
    OP:
    op: |
    CALL:
    NIL
    tcp_server
    ARRAY:
    VALUE(NUMBER): 8007
    NIL
    LAMBDA:
    ARGS(1):
    s
    OP:
    op: |
    IDENT: s
    IDENT: s

07netcat.strm
スクリプト
    s = tcp_socket("localhost", 8007)
    STDIN | s
    s | STDOUT
パース展開
    STMTS:
    LET: s
    CALL:
    NIL
    tcp_socket
    ARRAY:
    VALUE(STRING): "localhost"
    VALUE(NUMBER): 8007
    NIL
    OP:
    op: |
    IDENT: STDIN
    IDENT: s
    OP:
    op: |
    IDENT: s
    IDENT: STDOUT

08chat.strm
スクリプト
broadcast = chan()
tcp_server(8008) | {s ->
  broadcast | s   # connect to broadcast channel
  s | broadcast   # broadcast incoming message
}
パース展開
  STMTS:
  LET: broadcast
    CALL:
      NIL
      chan
      ARRAY:
      NIL
  OP:
    op: |
    CALL:
      NIL
      tcp_server
      ARRAY:
      VALUE(NUMBER): 8008
      NIL
    LAMBDA:
    ARGS(1):
      s
    STMTS:
      OP:
      op: |
      IDENT: broadcast
      IDENT: s
      OP:
      op: |
      IDENT: s
      IDENT: broadcast