まじかんと雑記

入力は一バイトづつ受け取った後、それが特殊なキー (割込みキー、カーソルキー、F1 キー等) を表す文字列かどうかを調べる。特殊なキーは対応する規定のワイド文字列に変換する。そうでないものはそのままワイド文字列に変換する。ワイド文字列に変換したら、それがカーソル移動等に割り当てたキー操作かどうかを調べる。何も割当たっていなければ行内に入力する。

ここで問題となるのはこれらの文字列が特殊なキーやキー操作を表す文字列になっているかどうかを調べるマッチング処理である。これは登録済みの多数の文字列の中から一致するものを探し出す処理になるが、入力された文字列全体がちょうど一致するとは限らないので、文字列の先頭から一文字づつ一致する可能性のある候補を絞ってゆくことになる。

このような処理にはハッシュ表よりもトライ (trie) が向いている。しかし単純にトライの各ノードに文字列の値をインデックスとする配列を持たせると、一ノード当たり 256 × sizeof(struct X*) バイトものメモリを食ってしまうため、ノードの構造を工夫する必要があると感じている。また、各ノードのデータサイズがバラバラの場合、多くのノードを配列上に一気に確保することが難しくなる点も考慮しなければならない。各ノードを個別に malloc するということは、メモリアクセスの空間的局所性が薄れるということを意味する。