ログ先行書き込み B+-Tree (その4)

B+-Tree では葉同士を双方向リンクでつなぎ、 キーの昇順または降順で次々とセルを辿っていけるようにします。 双方リンクへの挿入・削除はリンクのその場書き換えが向いており、 ログ先行書き込みとの相性が良い方式です。page_type 構造体に双方向リンク用…

ログ先行書き込み B+-Tree (その3)

前回の (その2) の削除では、 子ページを統合するとき、 下の例のようにペアの左側の子ページへ寄せていました。 反対に右側へ寄せるようにすると、 コードが若干ですが素直になるため、 今回はこちらを採用することにします。 削除前 ..,{L0,A0,L1,A1,L2},A…

ログ先行書き込み B+-Tree (その2)

木の削除では、 ノード間・葉間でセルを移し替えるバランス調整が必要になるので、 削除対象のセルを含むページ自体ではなく、 その親ノードに着目して処理します。 例外として、 ルートが葉のときは親ノードが存在しないので、 特別扱いします。 void bplus…

ログ先行書き込み B+-Tree (その1)

トランザクション処理が可能な B+-Tree をログ先行書き込み方式 (write ahead logging, WAL) でモデル化してみます。 本来なら外部記憶装置上に木を作るものですが、 モデル化なので、 スナップショットとログの両方ともメモリ上に置くことにします。 ただし…

二分探索

整列済みデータ列の二分探索で、 データが見つからなかったときに返す値からデータの挿入位置を簡単に求めることができると便利です。 その配慮がなく、 見つからなかったときに NULL を返すだけの POSIX の bsearch (3) 関数や、 真偽値しか返してくれない …

整数 ML インタプリタの CEK マシン部の入れ替え

型なし版の CEK マシンを型なし版から型付け版へ入れ替えました。 本質である状態遷移はそのままです。⇒ https://github.com/tociyuki/ml4-inter-cxx11型付けにより、 一例として、 ラムダ項を評価して関数を得る部分は次のように素直になります。 // (fun x…

整数 ML の CEK 状態遷移

例によって備忘録です。環境を直前のプログラム式の終了状態から受け継いでいくため、 初期状態の継続は KStop だけでなく、 環境を元に戻す KRt 継続をつないであります。プログラム式 m を環境 E0 の元で評価して、 値 v を得るとき。 m E0 (KRt - E0 (KSt…

CEK マシンによる整数 ML インタプリタ

五十嵐先生が「MLインタプリタの作成」を OCaml で記述されていらっしゃいます。 そこの ML4 の再帰的関数定義 (let rec) までを CEK マシンで実装するとどうなるのだろうと興味本位で C++11 でやってみました。 型推論は省いています。改訂 ⇒ 整数 ML イン…

四則演算の小町算

加減算に限定せず、 乗除算も加えた真の小町算を解いてみましょう。 除算で精度を失わないようにするため、 分数計算で値を求め、 分母の 100 倍が分子に一致するかどうかで判定するようにします。分数計算では途中の約分を省略することにします。 約分をし…

ループで小町算

小町算「数字の 1 から 9 までを昇順に並べ、 数字の間に + と - を挿入して、 評価結果が 100 になる数式」を求めてみます。 数字の間の 8 ヶ所には、 プラスを挿入する、 マイナスを挿入する、 何も挿入しないの 3 通りがありえます。 ですので、 3 進数 8…

UTF-8 用 wordcounter

単語を、 wc (1) コマンドに合わせて、 空白で区切られている文字列の並びと定義して、 単純化した扱いをする wordcounter オブジェクトを作ります。 UnicodeData.txt と EastAsianWidth.txt の両方の属性をコードポイントから参照し、 合成文字のマークや異…

ucd::width 関数 (その2)

EastAsianWidth.txt も UnicodeData.txt も、 昇順にコード・ポイント範囲が並んでいるのですけど、 範囲を表す書式が異なっています。 相違点を吸収してコード・ポイント単位で幅属性を返すジェネレータ・クラスを作ります。EastAsianWidth.txt から一行を …

ucd::width 関数 (その1)

ユニコード・コード・ポイントのカラム幅に関連する属性をコード化したものを返す ucd::width 関数を作ります。 EastAsianWidth 属性だけでは、 ゼロ幅かどうか、 文字合成用の付加記号かが判別できないので、 UnicodeData.txt から種類判別に必要な情報を補…

Least Recently Used 用リング

Least Recently Used (LRU) を、 一つのリングで書いてみます。 つまり、 Baker のトレッドミルからぱくって、 リングの途中に 2 つの番兵項目を置き、 リングを 2 つのリストに分割します。 リストの一方を使用中項目リストに使い、 もう一方をフリー・リス…

Unicode の文字数カウント

一年半前に C++11 に慣れるために GNU coreutils の wc (1) コマンドを書き直したときに、 wc (1) に合わせて文字数をワイド文字の個数としていました。 ところで、 LC_CTYPE が ja_JP.UTF8 のとき、 UTF-8 をデコードしたコード・ポイント一つずつがそのま…

UnicodeData Canonical Combining Class のダブル配列トライ

Unicode の合成文字は、 UnicodeData.txt の第 3 欄 Canonical Combining Class の数値がゼロでないものを抽出します。 以前は狭い範囲で収まっていて単純なテーブル参照で済んでいたのですけど、 広い範囲にばらけながら増える一方なので、 ダブル配列のト…

Unicode East Asian Width さらに

「Unicode East Asian Width 再び 」では、 コードポイント範囲を二分探索して幅を求めていました。 コードポイント範囲のテーブルのメンテナンスのやりやすさと、 テーブル・サイズを小さくできるというメリットがある反面、 ワースト・ケースでは 8 回の繰…

less もどきのコマンド処理オブジェクト

機能簡略版の less もどきで、 キー 1 回入力で画面の上下スクロールをするだけの単純な場合はコマンド処理オブジェクトなしでも済ませることができますが、 エスケープ・キーとキーを順に押してメタ・キーの代わりの入力としたり、 コマンドに数値パラメー…

less もどきの行分割処理の作り直し

less もどきの行分割処理の大枠を変更せずに、 SGR が閉じていない行表示不都合のバグをもりこんだところ、 2 つの効率の悪さが生じました。 1 つ目は行頭で、 SGR のシーケンスを見つけるために文字走査をいちいちおこなうようになったこと。 2 つ目は SGR …

端末入力の状態遷移機械のエラー回復処理

前回の端末入力の状態遷移機械は、判別不能でエラー停止したとき、このオブジェクトを利用する側でなんとかすることにしていました。 ところが、利用する側でなんとかしようとしても簡単ではないことが発覚してきたので、状態遷移機械にエラー回復処理を組み…

less もどきのバグ修正: SGR が閉じていない行表示不都合

端末にいろんな色でいろんな長さの行を less もどきで表示していたら、 行が文字属性が閉じないとき、 続く行を正しく表示しない不都合があることに気がつきました。 less もどきは、 文字属性を変更するエスケープ・コード SGR (Select Graphic Rendering: …

xterm の色コードの変換

xterm の色コードは、24 ビット・フルカラー、256 色、16色、8色の 4 通りが利用できます。 xterm のカラー・パレットが既定値のままであるとして、それぞれの間での相互変換をするオブジェクトを作ってみます。 このオブジェクトは、 メンバに 24 ビット・…

Terminfo のパディング出力

端末エミュレータでは無視しても問題にならないので Terminfo のパディング記述を読み飛ばしていたのを、 今度はまともに出力するようにします。 それに合わせて、 terminfo_expand_type クラスを terminfo_output_type クラスへ改名し、 expand メンバ関数…

端末からの入力待ち next_event

昨日の入力シーケンス判別用の状態遷移機械と less もどき用に書いたシングルバイト単位入力 next_event を統合してバイト・シーケンス対応にします。 将来の使いまわしのために、 エスケープ・キー単独の入力を判別する機能は残しておきたいので、 定石通り…

端末入力の状態遷移機械

ANSI 端末エミュレータからの入力を扱うのは簡単ではありません。 7 ビット ASCII だけが送られてくるなら単純ですけど、 UTF-8 マルチバイトで日本語も送られてきますし、 矢印キー等も一連のエスケープ・コードで送られてきます。 それらを判別する必要が…

動的ダブル配列

Terminfo ケーパビリティ名に使ったダブル配列は静的に構築したもので、キーと値のペアの組からまとめてダブル配列を作りました。 同じ Terminfo 関連で使うにしても、 矢印入力等のエスケープ・シーケンスを扱うには、 キーと値の組を順次登録したり、 削除…

less もどきで旧式テレタイプ重ね打ち

less (1) コマンドは、 man (1) コマンド用に旧式テレタイプの重ね打ちから ANSI 文字属性への変換機能を内蔵しています。 これは、 man (1) が後方互換性のため、 古い nroff (1) の太字や斜体を出力する方法を受け継いでおり、 太字を「太^H太」と後退記号…

less もどきの制御文字表示と文字属性変更

これまでの less もどきでは、 タブと改行以外の制御文字をそのまま出力してしまうので、 画面が乱れてしまいます。 特にバックスペース、ANSI エスケープ・コードのカーソル移動や行・文字挿入・削除が含まれていると最悪です。 そこで、 制御文字は ^A の…

less もどきに hbox を導入

less もどきよりも前はワイド文字でコーディングしてきて、 今回、 試しにマルチバイト文字のままで内部エンコーディングを UTF-8 で扱っています。そこで、「less もどきのための行分割処理」はその都度 decoder_u8_type オブジェクトで一文字をスキャンし…

less もどきのイベントループ

less もどきでは、 SIGINT、 SIGWINCH とキーボード入力をイベント・ループで受け取り、 screen_type オブジェクトで画面更新をおこなう作りにしています。 キーバインドはハードコードしており、ほぼ less に合わせてあります。 void uless_application::ev…