Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 

2016年05月31日

[]隙間詰め付き LRU 文字列キャッシュ

文字列をキャッシュする何かとお世話になることがあるオブジェクトを作ります。 エントリのキーは整数。 値はもちろん文字列です。 キャッシュへの書き込みはキーと文字列へのイテレータの組でおこないます。 キャッシュからの読み取りはキーを指定して、文字列へのイテレータを受け取ります。 読み書きをおこなうと内部で管理しているリングの新しい方へエントリを移します。 キャッシュ可能なエントリ数は固定です。 それを越えると古い方から捨てていきます。

キャッシュは様々な大きさの文字列を頻繁に追加・削除するため、メモリの断片化を生じます。そのため、文字列を一つの大きなバッファに書き込んでいくことにして、 ゴミ集めをおこなって利用していない隙間を詰めることにします。 隙間詰め方式のゴミ集めには、てっとり早く記述できるというメリットから古典的な mark-compact である Lisp2 アルゴリズムを採用しました。 動作が遅いアルゴリズムですが、 確実に隙間詰めできます。

#include <string>
#include <vector>
#include <utility>
#include <algorithm>

// 隙間詰め付きの文字列バッファ
class string_buffer_type {
public:
    string_buffer_type (void);
    int allocate (std::size_t const n);
    void grow (std::size_t const n);
    bool put (int const id, std::string::const_iterator s, std::string::const_iterator e);
    bool get (int const id, std::string::const_iterator& s, std::string::const_iterator& e);
    void gcmark_slot (int const id);
    void gcscan (void);
    int gcforwarding_address (int const id);
    void gcrelocate (void);
private:
    struct slot_type {
        int pos, len, mark;
    };
    std::vector<slot_type> slot;
    std::string content;
    int slot_hall, content_hall;
};

// LRU 文字列キャッシュ
class string_cache_type {
public:
    explicit string_cache_type (std::size_t const n);
    bool put (int const key, std::string::const_iterator s, std::string::const_iterator e);
    bool get (int const key, std::string::const_iterator& s, std::string::const_iterator& e);
private:
    struct entry_type {
        int prev, next;
        int key, value;
    };
    enum {FREE = 0, USED = 1};
    std::vector<entry_type> entry;
    string_buffer_type buffer;
    int allocate_buffer (int const n);
    void move (std::size_t const p, std::size_t const j);
};

キャッシュ・オブジェクトは 2 つのリングを利用します。 初期化時は、 FREE リングにエントリをすべてつなげ、 USED リングを空にします。

string_cache_type::string_cache_type (std::size_t const n)
    : entry (n + 2), buffer ()
{
    std::size_t const m = entry.size ();
    for (std::size_t i = 0; i < m; ++i) {
        entry[i].prev = (i + m - 1) % m;
        entry[i].next = (i + 1) % m;
    }
    entry[entry[USED].prev].next = entry[USED].next;
    entry[entry[USED].next].prev = entry[USED].prev;
    entry[USED].prev = entry[USED].next = USED;
}

バッファ・オブジェクトは部分文字列の位置と長さを表すスロットと大きな文字列の組になっています。 スロットのゼロ番は番兵です。 1 番以降を有効なスロットに使います。

string_buffer_type::string_buffer_type (void)
    : slot (), content ()
{
    slot.resize (8);
    content.resize (256, ' ');
    slot_hall = 1;
    content_hall = 0;
}

キャッシュからの読み出しは、 USED リングのエントリを順に調べて、キーに一致するエントリを見つけると、 USED リングの先頭へ移してから、 文字列バッファに文字列イテレータを作らせます。

bool
string_cache_type::get (int const key, std::string::const_iterator& s,
    std::string::const_iterator& e)
{
    for (int i = entry[USED].next; i != USED; i = entry[i].next) {
        if (key == entry[i].key) {
            move (USED, i);
            return buffer.get (entry[i].value, s, e);
        }
    }
    return false;
}

キャッシュへの書き込みは、 まず USED リングからキーが一致するエントリがあると削除し、 FREE リングが空のときは、 USED リングの末尾のエントリを削除します。 文字列バッファに必要な文字数分割り当てて、 内容をコピーしてからエントリを USED リングの先頭に追加します。

bool
string_cache_type::put (int const key, std::string::const_iterator s,
    std::string::const_iterator e)
{
    for (int i = entry[USED].next; i != USED; i = entry[i].next) {
        if (key == entry[i].key) {
            move (FREE, i);
            break;
        }
    }
    if (entry[FREE].next == FREE) {
        move (FREE, entry[USED].prev);
    }
    int const id = allocate_buffer (e - s);
    if (0 == id || ! buffer.put (id, s, e)) {
        return false;
    }
    move (USED, entry[FREE].prev);
    int const p = entry[USED].next;
    entry[p].key = key;
    entry[p].value = id;
    return true;
}

リングのエントリの移動は、 つながっているリングからエントリ j を切り離して、 移動先 q の後ろへ挿入します。

void
string_cache_type::move (std::size_t const p, std::size_t const j)
{
    if (j <= USED || p == entry[j].prev) {
        return;
    }
    entry[entry[j].prev].next = entry[j].next;
    entry[entry[j].next].prev = entry[j].prev;
    entry[j].next = entry[p].next;
    entry[j].prev = p;
    entry[entry[j].prev].next = j;
    entry[entry[j].next].prev = j;
}

バッファ・オブジェクトの allocate メンバ関数は、 バッファに十分な空きがあるときにスロットと部分文字列を割り当ててスロット番号を返します。 空きがないときはゼロを返します。

int
string_buffer_type::allocate (std::size_t const n)
{
    if (slot_hall >= slot.size () || content_hall + n > content.size ()) {
        return 0;
    }
    int const id = slot_hall;
    slot[id].pos = content_hall;
    slot[id].len = n;
    ++slot_hall;
    content_hall += slot[id].len;
    std::fill_n (content.begin () + slot[id].pos, slot[id].len, ' ');
    return id;
}

grow メンバ関数は、 スロットと文字列領域のいずれかを倍に伸ばします。

void
string_buffer_type::grow (std::size_t const n)
{
    if (slot_hall >= slot.size ()) {
        slot.resize (slot.size () * 2);
    }
    int m = content.size ();
    while (content_hall + n >= m) {
        m *= 2;
    }
    if (m > content.size ()) {
        content.resize (m, ' ');
    }    
}

put メンバ関数は、 割り当て済みのスロットに文字列をコピーします。

bool
string_buffer_type::put (int const id, std::string::const_iterator s,
    std::string::const_iterator e)
{
    if (id < 1 || id >= slot_hall) {
        return false;
    }
    if (e - s > slot[id].len) {
        return false;
    }
    std::copy (s, e, content.begin () + slot[id].pos);
    return true;
}

get メンバ関数は、 文字列のイテレータを作って返します。

bool
string_buffer_type::get (int const id, std::string::const_iterator& s,
    std::string::const_iterator& e)
{
    if (id < 1 || id >= slot_hall) {
        return false;
    }
    s = content.begin () + slot[id].pos;
    e = s + slot[id].len;
    return true;
}

文字列バッファへの割り当ては、 バッファに十分な空きがあるときはそれを使います。 なお、文字列バッファのスロットは 1 番から始まり、ゼロはスロットの割り当てができなったことを表します。 空きがないときはゴミ集めをします。 それでもバッファに空きがないときは、 バッファの長さを倍にします。 ゴミ集めを始めると、 まず使っているスロットにマークをつけます。 続いてスロットを先頭から調べていき、 マークがついているスロットの移動予定先のスロット番号を計算します。 USED リング・エントリのスロット番号を移動予定先に変更し終えたら、 スロットと部分文字列を再配置して隙間を詰めます。

int
string_cache_type::allocate_buffer (int const n)
{
    int const id1 = buffer.allocate (n);
    if (0 < id1) {
        return id1;
    }
    // マーク
    for (int i = entry[USED].next; i != USED; i = entry[i].next) {
        buffer.gcmark_slot (entry[i].value);
    }
    // 移動予定先スロット番号を求める
    buffer.gcscan ();
    // スロット番号を移動予定先へ付け替える
    for (int i = entry[USED].next; i != USED; i = entry[i].next) {
        entry[i].value = buffer.gcforwarding_address (entry[i].value);
    }
    // スロットと部分文字列の隙間を詰める
    buffer.gcrelocate ();
    // ゴミ集め完了 もういちど割り当てを試みる
    int const id2 = buffer.allocate (n);
    if (0 < id2) {
        return id2;
    }
    // ゴミ集めしても空きがないときはバッファを伸ばす
    buffer.grow (n);
    return buffer.allocate (n);
}

スロットの mark メンバを真にします。この実装では、 2 色マークしか使えず、 逐次マーキングに対応していません。

void
string_buffer_type::gcmark_slot (int const id)
{
    if (0 < id && id < slot_hall) {
        slot[id].mark = 1;
    }
}

再配置をする前に、 移動予定先のスロット番号を計算しておきます。 再配置の対象は、スロットと部分文字列の両方ですが、 事前に計算しておかないといけないのはスロットだけです。 Lisp2 アルゴリズムではスロットと対応する部分文字列の順番が常に一致していることが重要で、 対応関係を維持しつづけるために両方とも順番を崩さずに再配置しないといけません。 スロットを再配置するため、 移動先を求めておき、 キャッシュ・オブジェクトが移動先を調べることができるようにしておきます。 gcscan メンバ関数は、 mark メンバを移動先のメモのために流用します。 同時にマークがついていない連続するスロットを、再配置時に読み飛ばすために、 次のマークがついているスロットへリンクします。

void
string_buffer_type::gcscan (void)
{
    int forwarding_address = 1;
    for (int k = 1; k < slot_hall;) {
        if (slot[k].mark) {
            slot[k].mark = forwarding_address;
            ++forwarding_address;
            ++k;
        }
        else {
            int const j = k;
            do {
                ++k;
            } while (k < slot_hall && ! slot[k].mark);
            slot[j].pos = k;
        }
    }
}

再配置による移動先スロット番号は mark メンバを流用しているので、その内容を返します。

int
string_buffer_type::gcforwarding_address (int const id)
{
    return 0 < id && id < slot_hall ? slot[id].mark : 0;
}

再配置では、スロットと部分文字列の隙間をそれぞれ同時に詰めていきます。 先頭側へと、利用中の領域をコピーしていけば良いわけで、 全部コピーし終えた端を新しい割り当て領域の始まりとして slot_hall メンバと content_hall メンバに記録しておきます。

void
string_buffer_type::gcrelocate (void)
{
    int top = 1;
    int pos = 0;
    std::string::iterator const s = content.begin ();
    for (int k = 1; k < slot_hall;) {
        if (slot[k].mark == 0) {
            k = slot[k].pos;    // gcscan メンバ関数で作ったリンクを使って連続未使用スロットを読み飛ばす
        }
        else {
            slot[k].mark = 0;
            if (top < k) {
                slot[top] = slot[k];     // スロットを再配置する
            }
            if (pos < slot[top].pos) {
                std::copy_n (s + slot[top].pos, slot[top].len, s + pos);   // 部分文字列を再配置する
                slot[top].pos = pos;
            }
            pos += slot[top].len;
            ++top;
            ++k;
        }
    }
    slot_hall = top;
    content_hall = pos;
}

2016年05月25日

[]Terminfo のパラメータ展開 (その2)

パディングを字句解析すると 0.1 ミリ秒単位の待ち時間、 プロポーショナル指定、 必須指定の 3 つの構成要素が手に入ります。 これらをメンバにして字句解析部と利用する側で共用するために構造体にしておきます。 match メンバ関数で文字列 fmt の pos 位置から字句解析をおこない、パディングとして解釈できたときは真を返します。 さらに、 derivs メンバに pos を進める位置を格納します。

struct padding_type {
    bool match (std::string const& fmt, int pos);
    int derivs;
    int period;         // 0.1ms
    bool proportional;
    bool mandatory;
};

指令の字句解析も同じやりかたにしています。 指令の方は構成要素がさらに増えます。 数値定数、文字定数の値を immediate メンバにいれます。 パラメータ指令 p1 の数字は数字のまま immediate にいれます。 変数指令 Paga のアルファベットもアルファベットのまま immediate にいれます。 書式指令のオプション要素は flag、width、precision メンバにそれぞれいれます。 演算指令も書式指令も指令の文字を元の文字のまま op メンバにいれます。

struct instruction_type {
    static const unsigned long flag_space = 1UL << (' ' - ' ');
    static const unsigned long flag_sharp = 1UL << ('#' - ' ');
    static const unsigned long flag_minus = 1UL << ('-' - ' ');
    static const unsigned long flag_plus = 1UL << ('+' - ' ');
    static const unsigned long flag_zero = 1UL << ('0' - ' ');
    bool match (std::string const& fmt, int pos);
    int arity (void) const;
    int derivs;
    int op;
    int immediate;              // p1..p9=>'1'..'9',PA..PZ=>'A'..'Z',..
    unsigned long flag;     // 1 << (ch-' ')) for ch in {' ','#','+','-','0'}
    int width;
    int precision;

    void put_number (std::ostream& out, int value);
    void put_string (std::ostream& out, std::string const& str);
};

match メンバ関数は、 pos 位置からパターン・マッチングを試みます。 パターン・マッチングは状態遷移を BASE-CHECK の表駆動で動かす、いつものやりかたで書いています。 開始状態は 2 で、終了状態は 1 かゼロです。 マッチングに成功すると状態 1 で遷移を完了します。

パディングは小数点以下 1 桁の数の待ち時間に続けて 2 種類の修飾子をつけることができます。 小数点以下は省略可能です。 なお、 念のため、小数点に続く数字を省略して小数点だけのときもエラーにしないようにしています。

//      [$][<][0-9]+(?:[.][0-9]?)?(?:[*][/]?|[/][*]?)?[>]
bool
padding_type::match (std::string const& fmt, int pos)
{
    static const signed char BASE[] = {0, 0, -1, -1, -1, 0, 6, 9, 11, 3, 12};
    static const unsigned short RULE[] = {
        0x032, 0x043, 0x154, 0x155, 0x065, 0x385, 0x495, 0x015,
        0x3a9, 0x276, 0x019, 0x386, 0x496, 0x016, 0x387, 0x497,
        0x017, 0x4a8, 0x018, 0x01a,
    }; // packed (ACTION << 8) | (STATE << 4) | CHECK
    static const int NRULE = sizeof (RULE) / sizeof (RULE[0]);
    static const char CODE[] = "@@@@A@@@@@E@@@DFCCCCCCCCCC@@B@G@";
    derivs = pos;
    period = 0;
    int fraction = 0;
    proportional = false;
    mandatory = false;
    int next_state = 2;
    for (; next_state > 1 && pos <= fmt.size (); ++pos) {
        int const state = next_state;
        next_state = 0;
        int const ch = pos < fmt.size () ? fmt[pos] : 0;
        int const code = 0x20 <= ch && ch <= 0x3f ? CODE[ch - 0x20] - '@' : 0;
        int const shift = BASE[state] + code;
        unsigned const rule = 0 <= shift && shift < NRULE ? RULE[shift] : 0;
        if ((rule & 0x00f) != state)
            break;
        next_state = (rule & 0x0f0) >> 4;
        switch (rule & 0xf00) {
        case 0x100:
            period = period * 10 + ch - '0';
            break;
        case 0x200:
            fraction = ch - '0';
            break;
        case 0x300:
            proportional = true;
            break;
        case 0x400:
            mandatory = true;
            break;
        }
    }
    if (1 != next_state)
        return false;
    derivs = pos;
    period = period * 10 + fraction;
    return true;
}

演算指令と書式指令のパターン・マッチングは一つにまとめてあります。書式指令の flag は、文字コードでビットシフトしています。 なお、書式の精度指定がゼロ・フラグを上書きする処理はここでおこなっています。

//        [%][%cl+\-*/m&|^=><AO!~i?te;]
//      | [%][p][1-9] | [%][Pg][A-Za-z] | [%][{][0-9]+[}] | [%]['].[']
//      | [%](?:(?:[#0 ]|[:])[#0 +-]*)?[0-9]*(?:[.][0-9]*)?[dosxX]
bool
instruction_type::match (std::string const& fmt, int pos)
{
    static const signed char BASE[] = {
        0, 0, -1, 0, 2, 13, 14, 16, 6, 8, 15, 19, 22};
    static const unsigned short RULE[] = {
        0x032, 0x113, 0x113, 0x143, 0x153, 0x163, 0x183, 0x0a3,
        0x113, 0x4a3, 0x0c3, 0x4a3, 0x5b3, 0x113, 0x214, 0x215,
        0x276, 0x398, 0x398, 0x399, 0x399, 0x017, 0x019, 0x4aa,
        0x4aa, 0x7ca, 0x4aa, 0x5ba, 0x11a, 0x7cb, 0x5bb, 0x5bb,
        0x11b, 0x6cc, 0x6cc, 0x11c,
    }; // packed (ACTION << 8) | (STATE << 4) | CHECK
    static const int NRULE = sizeof (RULE) / sizeof (RULE[0]);
    static const char CODE[] =
        "IB@I@ABE@@BH@HJBKLLLLLLLLLGBBBBB@B@@@@@@@@@@@@@BD@@@@@@@M@@@@@B@"
        "@@@BMB@D@B@@BB@MC@@MB@@@M@@FBNB@"; // [0x20-0x7f]
    derivs = pos;
    immediate = 0;
    flag = 0;
    width = 0;
    precision = 0;
    int next_state = 2;
    for (; next_state > 1 && pos <= fmt.size (); ++pos) {
        int const state = next_state;
        next_state = 0;
        int const ch = pos < fmt.size () ? fmt[pos] : 0;
        int const code
            = 5 == state ? (std::isalpha (ch) ? 2 : 0)
            : 6 == state ? (pos < fmt.size () ? 2 : 0)
            : 0x20 <= ch && ch <= 0x7f ? CODE[ch - 0x20] - '@'
            : 0;
        int const shift = BASE[state] + code;
        unsigned const rule = 0 <= shift && shift < NRULE ? RULE[shift] : 0;
        if ((rule & 0x00f) != state)
            break;
        next_state = (rule & 0x0f0) >> 4;
        switch (rule & 0xf00) {
        case 0x100:
            op = ch;
            break;
        case 0x200:
            immediate = ch;
            break;
        case 0x300:
            immediate = immediate * 10 + ch - '0';
            break;
        case 0x400:
            flag |= 1UL << (ch - ' ');
            break;
        case 0x500:
            width = width < 4096 ? width * 10 + ch - '0' : width;
            break;
        case 0x600:
            precision = precision < 4096 ? precision * 10 + ch - '0' : precision;
            break;
        case 0x700:
            flag &= ~flag_zero;
            break;
        }
    }
    if (1 != next_state)
        return false;
    derivs = pos;
    return true;
}

書式指令による出力は snprintf を使わずに、 自力でおこなっています。

文字列は、精度指定がゼロより大きなときは文字列を切り詰めて表示します。

static inline void
put_times (std::ostream& out, int const pad, int const width)
{
    for (int i = 0; i < width; ++i)
        out.put (pad);
}

void
instruction_type::put_string (std::ostream& out, std::string const& str)
{
    int const n = precision == 0 || str.size () < precision ? str.size ()
        : precision;
    if (! (flag & flag_minus) && n < width)
        put_times (out, ' ', width - n);
    out.write (&str[0], n);
    if ((flag & flag_minus) && n < width)
        put_times (out, ' ', width - n);
}

整数の表示は、補助の数表示クラスを使います。 これは、符号の有無 sign、 符号文字 signchar、 0x 等の sharp、 位取りを逆順にした digits を保持し、 put_zeros メンバ関数等で書式出力します。

struct number_type {
    int sign;
    int signchar;
    std::string sharp;
    std::string digits;

    void utod (int precision, unsigned base, unsigned n);
    void put_zeros (std::ostream& out, int width, int op);
    void put_right (std::ostream& out, int width, int op);
    void put_left (std::ostream& out, int width, int op);
};

指令オブジェクトの put_number メンバ関数は、 数表示オブジェクトのメンバに適切な値をセットしてから、 flag により、 左寄せ、 ゼロ・パディング、右寄せで表示をおこないます。

void
instruction_type::put_number (std::ostream& out, int value)
{
    if ('d' != op)
        flag &= ~(flag_plus | flag_space);
    unsigned const base = 'o' == op ? 8U : 'd' == op ? 10U : 16U;
    int const negative = 'd' == op && value < 0;
    number_type number;
    number.sign = negative || (flag & (flag_plus | flag_space)) != 0;
    number.signchar = negative ? '-' : (flag & flag_plus) ? '+' : ' ';
    number.utod (precision, base, negative ? -value : value);
    number.sharp = 10U == base || 0 == value || ! (flag & flag_sharp) ? ""
        : 'x' == op ? "0x"
        : 'X' == op ? "0X"
        : number.digits.back () != 0 ? "0" : "";
    if (flag & flag_minus)
        number.put_left (out, width, op);
    else if (flag & flag_zero)
        number.put_zeros (out, width, op);
    else
        number.put_right (out, width, op);
}

位取りを逆順に各桁を digits メンバに入れて、 精度指定分のゼロを補います。

void
number_type::utod (int precision, unsigned base, unsigned n)
{
    digits.clear ();
    do {
        digits.push_back (n % base);
        n /= base;
    } while (n != 0);
    if (digits.size () < precision)
        digits.resize (precision, 0);
}

符号文字・0x 等・各桁・空白の順に出力すると左寄せ出力になります。

void
number_type::put_left (std::ostream& out, int width, int op)
{
    if (sign)
        out.put (signchar);
    if (! sharp.empty ())
        out << sharp;
    for (auto s = digits.crbegin (); s != digits.crend (); ++s)
        out.put (*s < 10 ? *s + '0' : 'x' == op ? *s + 'a' - 10 : *s + 'A' - 10);
    if (digits.size () + sharp.size () + sign < width)
        put_times (out, ' ', width - digits.size () - sharp.size () - sign);        
}

符号文字・0x 等・ゼロのパディング、各桁の順に出力するとゼロ・パディング出力になります。

void
number_type::put_zeros (std::ostream& out, int width, int op)
{
    if (sign)
        out.put (signchar);
    if (! sharp.empty ())
        out << sharp;
    if (digits.size () + sharp.size () + sign < width)
        put_times (out, '0', width - digits.size () - sharp.size () - sign);
    for (auto s = digits.crbegin (); s != digits.crend (); ++s)
        out.put (*s < 10 ? *s + '0' : 'x' == op ? *s + 'a' - 10 : *s + 'A' - 10);
}

空白・符号文字・0x等・各桁の順に出力すると右寄せになります。

void
number_type::put_right (std::ostream& out, int width, int op)
{
    if (digits.size () + sharp.size () + sign < width)
        put_times (out, ' ', width - digits.size () - sharp.size () - sign);
    if (sign)
        out.put (signchar);
    if (! sharp.empty ())
        out << sharp;
    for (auto s = digits.crbegin (); s != digits.crend (); ++s)
        out.put (*s < 10 ? *s + '0' : 'x' == op ? *s + 'a' - 10 : *s + 'A' - 10);
}

[]Terminfo のパラメータ展開 (その1)

Terminfo のパラメータ展開ではスタック演算と if 構文を扱います。 スタック演算は数値演算が基本ですが、文字列をスタックに置いて出力に書式整形出力することもあるので、 数値と文字列のバリアントを値型としてスタックへプッシュ・ポップするようにします。 ここでは横着して、 バリアントをペアで表し、 文字列は文字列用のパラメータ配列への添字を値に入れておくことにします。 今の terminfo データベースで文字列をパラメータに渡す場合はプログラマブルファンクション・キーの設定のときだけで、ファンクション・キー番号の数値を p1 に、 ファンクション・キーに設定する文字列を p2 に渡します。 ANSI 互換端末ではファンクション・キーはプログラマブルではないので、無視しても良いのですが、たいして面倒になるわけではないので実装しておきます。 過去の遺産であるパディング処理はパラメータ構文のパディング記述を読み飛ばして処理しません。 古い端末の terminfo 設定では、 端末状態を変数に記録するものがあるので、パラメータ展開は関数ではなくオブジェクトにします。

#include <string>
#include <stack>
#include <vector>
#include <array>
#include <utility>
#include <cctype>
#include <ostream>

struct terminfo_format_type {
    using VALUE_TYPE = std::pair<bool,int>;
    // 数値:   {true, 値}
    // 文字列: {false, string_parameters の添字}
    std::array<VALUE_TYPE, 52> variables;
    std::array<VALUE_TYPE, 9> parameters;
    std::array<std::string, 4> string_parameters;

    terminfo_format_type ();
    virtual ~terminfo_format_type () {}

    void expand (std::ostream& out, std::string const& fmt,
        int p1 = 0, int p2 = 0, int p3 = 0, int p4 = 0, int p5 = 0,
        int p6 = 0, int p7 = 0, int p8 = 0, int p9 = 0);
    void expand (std::ostream& out, std::string const& fmt,
        int p1, std::string const p2, std::string const p3 = "",
        std::string const p4 = "");

    void run (std::ostream& out, std::string const& fmt);
    virtual void pad (std::ostream& out, int period, bool proportional, bool mandatory) {}
};

コンストラクタは変数を数値で初期化します。terminfo (5) のマニュアル・ページでは、A から Z の変数と、 a から z の変数は扱いが異なると記されていますが、 古い端末の Terminfo 設定の中には、 両者とも static 変数のようにずっと値を保持し続けていることを期待しているものがあります。 もはやそんな端末を使うこと自体ありえないので、無視しても良いのでしょうけど、 初期化はコンストラクタだけがおこない、 後はオブジェクトが生存している間は変数の値を保持するようにします。 なお、 ANSI 端末の設定でも変数を使っている書式がありますが、 調べた限りでは一回の書式展開ごとに値を一時的に保管する auto 変数の使い方しかしていません。

terminfo_format_type::terminfo_format_type ()
    : variables (), parameters (), string_parameters ()
{
    for (int i = 0; i < variables.size (); ++i) {
        variables[i].first = true;
        variables[i].second = 0;
    }
}

expand メンバ関数引数のパラメータをメンバに適切に設定してから run メンバ関数で展開をおこないます。 パラメータが全部数値だけのときは、 parameters メンバだけを使います。

void
terminfo_format_type::expand (std::ostream& out, std::string const& fmt,
    int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8, int p9)
{
    for (int i = 0; i < parameters.size (); ++i)
        parameters[i].first = true;
    parameters[0].second = p1;
    parameters[1].second = p2;
    parameters[2].second = p3;
    parameters[3].second = p4;
    parameters[4].second = p5;
    parameters[5].second = p6;
    parameters[6].second = p7;
    parameters[7].second = p8;
    parameters[8].second = p9;
    run (out, fmt);
}

p1 が数値、 p2 から p4 が文字列のときは、 parameters メンバと string_parameters メンバに両方を使います。

void
terminfo_format_type::expand (std::ostream& out, std::string const& fmt,
    int p1, std::string const p2, std::string const p3,
    std::string const p4)
{
    parameters[0].first = true;
    parameters[0].second = p1;
    parameters[1].first = false;
    parameters[1].second = 1;
    string_parameters[1] = p2;
    parameters[2].first = false;
    parameters[2].second = 2;
    string_parameters[2] = p3;
    parameters[3].first = false;
    parameters[3].second = 3;
    string_parameters[3] = p4;
    for (int i = 4; i < parameters.size (); ++i) {
        parameters[i].first = true;
        parameters[i].second = 0;
    }
    run (out, fmt);
}

run メンバ関数は、 パディングでもなく指令でもない平文を出力しておいてから、 それぞれの字句解析をおこないます。パディング字句が取得できたときは、ダミーの何もしない pad メンバ関数を呼びます。 指令が取得できたときはそれに応じた処理をします。どちらでもないときは、1 文字出力して次のパディングか指令を探します。

void
terminfo_format_type::run (std::ostream& out, std::string const& fmt)
{
    padding_type padding;
    instruction_type instruction;
    std::stack<VALUE_TYPE> data;
    int pos = 0;
    while (pos < fmt.size ()) {
        int const plain = pos;
        pos = fmt.find_first_of ("$%", pos);
        pos = pos == fmt.npos ? fmt.size () : pos;
        if (plain < pos)
            out.write (&fmt[org], pos - plain);
        if (pos >= fmt.size ())
            break;

        if (padding.match (fmt, pos)) {
            pad (out, padding.period, padding.proportional, padding.mandatory);
            pos = padding.derivs;
            continue;
        }
        else if (! instruction.match (fmt, pos)) {
            out.put (fmt[pos++]);
            continue;
        }

        pos = instruction.derivs;
        int const op = instruction.op;
//<@    指令の引数分をスタックからとりだします@>
        switch (op) {
        case '%':
            out.put ('%');
            break;
//@<    スタック・トップの値を書式整形出力します@>
//@<    パラメータをスタックに読み出します@>
//@<    即値をスタックへおきます@>
//@<    変数操作をします@>
//@<    四則演算をします@>
//@<    比較演算をします@>
//@<    ビット演算をします@>
//@<    %i と %l をおこないます@>
//@<    if 分岐をします@>
        }
    }
}

その 2 で定義する指令構造体の arity メンバ関数は、 演算に必要な引数を返します。 0、1、2 の 3 通りがあります。

int
instruction_type::arity (void) const
{
    static const char ARITY[] =
        "0100002000220202000000000000222002000000000000021000000010000020"
        "00011000000012010001100010002010"; // [0x20-0x7f]
    return 0x20 <= op && op <= 0x7f ? ARITY[op - ' '] - '0' : 0;
}

必要な引数をスタックからとりだします。数値が欲しいときに文字列になっているときは、エラーにせずにゼロを使います。スタックが空のときもゼロにします。 引数の順番は FORTH や PostScript と同じです。 スタック2番目が左辺 n1、 スタック先頭が右辺 n2 です。

//<@    指令の引数分をスタックからとりだします@>=
        // "%{6}%{2}%/" を中置記法にすると 6 / 2 の意味。
        int const arity = instruction.arity ();
        int const n2 = arity < 2 ? 0
            : data.empty () ? 0
            : data.top ().first ? data.top ().second : 0;
        if (arity == 2) data.pop ();
        VALUE_TYPE const x1
            = arity < 1 ? std::make_pair<bool,int> (true, 0)
            : data.empty () ? std::make_pair<bool,int> (true, 0)
            : data.top ();
        int const n1 = x1.first ? x1.second : 0;
        if (arity > 0) data.pop ();
        int const imm = instruction.immediate;

書式整形出力は指令オブジェクトのメンバ関数でおこないます。

//@<    スタック・トップの値を書式整形出力します@>=
        case 'c':
            out.put (n1);
            break;
        case 'd':
        case 'o':
        case 'x':
        case 'X':
            instruction.put_number (out, n1);
            break;
        case 's':
            if (! x1.first)
                instruction.put_string (out, string_parameters[x1.second]);
            break;

パラメータは 9 個利用できます。 imm 欄にパラメータ指定文字が入ってるので、それを使います。

//@<    パラメータをスタックに読み出します@>=
        case 'p':
            data.push (parameters[imm - '1']);
            break;

即値は文字と数値で指定する両方があります。どちらの場合も数値をスタックへ積みます。

//@<    即値をスタックへおきます@>=
        case '\'':
        case '{':
            data.emplace (true, imm + 0);
            break;

変数をスタックへ積むか、 スタックトップを変数に代入します。

//@<    変数操作をします@>=
        case 'P':
            variables[imm < 'a' ? imm - 'A' + 26 : imm - 'a'] = x1;
            break;
        case 'g':
            data.push (variables[imm < 'a' ? imm - 'A' + 26 : imm - 'a']);
            break;

四則演算は数値に対しておこないます。文字列がスタックにあるときはゼロとみなして計算する流儀のようです。端末制御の途中で例外を生じるのは不便なので、ゼロ除算は大きな値にします。同様の理由でゼロ剰余はゼロにしています。

//@<    四則演算をします@>=
        case '+':
            data.emplace (true, n1 + n2);
            break;
        case '-':
            data.emplace (true, n1 - n2);
            break;
        case '*':
            data.emplace (true, n1 * n2);
            break;
        case '/':
            if (n2 == 0)
                data.emplace (true, 1 << (sizeof (n1) * 8 - 2));
            else
                data.emplace (true, n1 / n2);
            break;
        case 'm':
            if (n2 == 0)
                data.emplace (true, 0);
            else
                data.emplace (true, n1 % n2);
            break;

比較演算も数値に対しておこないます。 A と O は論理演算ですが、比較演算と組み合わせて使うので、ここにいれておきます。

//@<    比較演算をします@>=
        case '=':
            data.emplace (true, n1 == n2);
            break;
        case '>':
            data.emplace (true, n1 > n2);
            break;
        case '<':
            data.emplace (true, n1 < n2);
            break;
        case 'A':
            data.emplace (true, n1 && n2);
            break;
        case 'O':
            data.emplace (true, n1 || n2);
            break;

ビット演算は2項と単項の両方があります。

//@<    ビット演算をします@>=
        case '&':
            data.emplace (true, n1 & n2);
            break;
        case '|':
            data.emplace (true, n1 | n2);
            break;
        case '^':
            data.emplace (true, n1 ^ n2);
            break;
        case '!':
            data.emplace (true, ! n1);
            break;
        case '~':
            data.emplace (true, ~ n1);
            break;

%i は先頭 2 つのパラメータの数値にそれぞれ 1 を加えます。カーソル移動他で多用します。 %l はスタック先頭の文字列の長さを求めます。 文字列長さを展開したいときに使います。

//@<    %i と %l をおこないます@>=
        case 'i':
            if (parameters[0].first)
                ++parameters[0].second;
            if (parameters[1].first)
                ++parameters[1].second;
            break;
        case 'l':
            data.emplace (true, x1.first ? 0 : string_parameters[x1.second].size ());
            break;

Terminfo では then-else 連鎖と、 if 分岐の入れ子の両方を利用します。 入れ子をスキップするには、 初期レベル 1 で始めて、 if の %? でレベルに 1 を足して深くし、 endif の %; でレベルを浅くします。 レベルがゼロになったら、 then の %t と同じレベルの endif に到達したので読み飛ばしを終えます。 さらに、 then-else 連鎖のために、 then の読み飛ばしでは同じレベルにある直後の else で読み飛ばしを中断します。 そのためレベル 1 の else でレベルをゼロにします。 このコードでは else の arity がゼロなので n1 が必ずゼロになることを利用し、 then と else で同じコードを使って読み飛ばしをおこなっています。

//@<    if 分岐をします@>=
        case '?':
            break;
        case 't':
        case 'e':
            if (! n1) { // always n1 == 0 on %e
                int state = 1;
                for (int level = 1; level > 0 && pos < fmt.size ();) {
                    int const c = fmt[pos++];
                    if (1 == state) {
                        if ('%' == c)
                            state = 2;
                    }
                    else {
                        if ('?' == c)
                            ++level;
                        else if (';' == c)
                            --level;
                        else if ('t' == op && 'e' == c && 1 == level)
                            --level;
                        state = 1;
                    }
                }
            }
            break;
        case ';':
            break;

2016年05月24日

[]ケーパビリティ名で引く Terminfo

ncurses の低レベル Terminfo アクセスは、 tigetflag (3)、 tigetnum (3)、 tigetstr (3) の 3 つも利用でき、 これらではケーパビリティ名を指定して端末設定中の項目をとりだすことができます。 include/Caps を読めるようにしたので、 同様の使い方ができるようにします。

ケーパビリティ名はダブル配列にしてソースコードにハードコードしています。 ケーパビリティ名 key から、 id 番号を参照するには、 状態 1 から始めて、 key の終端に状態遷移できたら、 code = 1 の caps_base の位置から id 番号をとりだします。

// caps_check[caps_base[state] + caps_code[ch - 32]] == state
// then state = caps_base[state] + caps_code[ch - 32];
// id = caps_base[caps_base[last_state] + 1];
static char const caps_code[] = { /* 省略 */ };
static short const caps_base[] = { /* 省略 */ };
static short const caps_check[] = { /* 省略 */ };

static int
caps_lookup (std::string const& key, int const failure)
{
    static const int ncaps_check = sizeof (caps_check) / sizeof (caps_check[0]);
    int state = 1;
    for (int c : key) {
        int const k = c < 33 ? 0 : 128 < c ? 0 : caps_code[c - 32];
        int const x = caps_base[state] + k;
        if (x < 1 || ncaps_check <= x || caps_check[x] != state)
            return failure;
        state = x;
    }
    int const y = caps_base[state] + 1;
    if (y < 1 || ncaps_check <= y || caps_check[y] != state)
        return failure;
    return caps_base[y];
}

これを使って、ケーパビリティを引くメンバ関数を terminfo_entry_type クラスに追加します。

bool
terminfo_entry_type::get_boolean (std::string const& cap) const
{
    int id = caps_lookup (cap, -1);
    return id >= 0 && get_boolean (id);
}

int
terminfo_entry_type::get_number (std::string const& cap) const
{
    int id = caps_lookup (cap, -1);
    return id >= 0 ? get_number (id) : -1;
}

char const*
terminfo_entry_type::get_string (std::string const& cap) const
{
    static char const null_c_str[] = "";
    int id = caps_lookup (cap, -1);
    return id >= 0 ? get_string (id) : null_c_str;
}

include/Caps からダブル配列を作るプログラムの主要部は trie_type クラスです。

#include <fstream>
#include <cctype>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>

struct trie_type {
    std::vector<std::pair<std::string,int>> list;
    int code_max;
    std::vector<int> code;
    std::vector<int> base;
    std::vector<int> check;

    bool load_file (std::string const& file, int field_number);
    void fill (void);

    void fill_code (void);
    void fill_subtrie (int const node, std::vector<int> const& parents, int const col);
    void fill_basecheck (int const node, std::vector<int> const& parents,
        int const col, std::vector<bool>& branch);
    bool occupy (int const offset,
        int const cmin, int const cmax, std::vector<bool> const& branch);
};

include/Caps ファイルからの読み取りメンバ関数 load_file は list にケーパビリティ名と id 番号をペアにしてセットしていきます。 readline 関数と split_of 関数は先日のものをそのまま使います。

bool
trie_type::load_file (std::string const& file, int field_number)
{
    std::ifstream in (file);
    if (in.bad ())
        return false;
    int idbool = 0;
    int idnum = 0;
    int idstr = 0;
    for (std::string line; readline (in, line); ) {
        if (std::isalpha (line[0])) {
            std::vector<std::string> f = split_of ("\t\n ", line);
            if (f.size () < 2)
                ;
            else if (f[2] == "bool")
                list.emplace_back (f[field_number], idbool++);
            else if (f[2] == "num")
                list.emplace_back (f[field_number], idnum++);
            else if (f[2] == "str")
                list.emplace_back (f[field_number], idstr++);
        }
    }
    in.close ();
    return true;
}

fill メンバ関数で、 list からトライを、 さらに caps_code、caps_base、caps_check のダブル配列に作ります。 これらは一度作れば内容固定なので、 static 配列の初期化コードへ変換し、terminfo-entry.cpp にハードコードして利用します。

void
trie_type::fill (void)
{
    fill_code ();
    base.resize (2);
    base[0] = 0;
    base[1] = 0;
    check.resize (2);
    check[0] = 1;
    check[1] = 1;
    std::vector<int> child (list.size ());
    std::iota (child.begin (), child.end (), 0);
    fill_subtrie (1, child, 0);
    check[0] = 0;
    check[1] = 0;
}

まず、 caps_code 配列を作ります。 すべてのケーパビリティ名の文字を調べて、 ASCII 順で 2 番以降の code 番号を割り当てます。 code 番号ゼロはトライが使っていない文字、 1 は文字列の終端、 2 番以降が文字です。

void
trie_type::fill_code (void)
{
    code.resize (128 - 32);
    std::fill (code.begin (), code.end (), 0);
    for (auto eachpair : list) {
        for (int c : eachpair.first) {
            if (32 < c && c < 128)
                ++code[c - 32];
        }
    }
    code_max = 1;
    for (int i = 0; i < code.size (); ++i) {
        if (code[i])
            code[i] = ++code_max;
    }
}

code 配列ができたら、 fill_subtrie でルートからトライの部分木へ降りていきながら、 状態遷移表をダブル配列に埋めていきます。

void
trie_type::fill_subtrie (int const node, std::vector<int> const& parents, int const col)
{
    std::vector<bool> branch (code_max + 1, false);
    fill_basecheck (node, parents, col, branch);
    std::vector<int> child;
    for (int c = 33; c < 128; ++c) {
        if (branch[code[c - 32]]) {
            child.clear ();
            for (int j : parents) {
                if (col < list[j].first.size () && list[j].first[col] == c)
                    child.push_back (j);
            }
            fill_subtrie (base[node] + code[c - 32], child, col + 1);
        }
    }
}

トライは多分木で、 branch ベクタにコード番号に対して部分木への遷移が生じるかどうかを抜き出します。 fill_basecheck は branch ベクタを作り、 それをダブル配列の先頭から最初にはめ込めることができる空き場所を探します。 場所が見つかったら、 そこの check を遷移元の状態を書き込み、 遷移元の base にオフセットを書き込みます。

void
trie_type::fill_basecheck (int const node,
    std::vector<int> const& parents, int const col, std::vector<bool>& branch)
{
    int cmin = branch.size (), cmax = 0;
    int value = 0;
    for (int j : parents) {
        int const n = list[j].first.size ();
        if (col > n)
            continue;
        int const c = col == n ? 1 : code[list[j].first[col] - 32];
        branch[c] = true;
        cmin = c < cmin ? c : cmin;
        cmax = c > cmax ? c : cmax;
        if (col == n)
            value = list[j].second;
    }
    int offset = 2 - cmin;
    while (occupy (offset, cmin, cmax, branch)) {
        ++offset;
    }
    if (offset + cmax + 1 > check.size ()) {
        base.resize (offset + cmax + 1, 0);
        check.resize (offset + cmax + 1, 0);
    }
    base[node] = offset;
    if (branch[1])
        base[base[node] + 1] = value;
    for (int i = cmin; i <= cmax; ++i) {
        if (branch[i])
            check[base[node] + i] = node;
    }
}

occupy は offset からの場所が利用済みだと真を返します。

bool
trie_type::occupy (int const offset,
    int const cmin, int const cmax, std::vector<bool> const& branch)
{
    for (int i = cmin; i <= cmax && i + offset < check.size (); ++i) {
        if (branch[i] && check[i + offset] != 0)
            return true;
    }
    return false;
}

これで code、 base、 check ができあがるので、 適当な改行をいれつつ C++ の配列初期子のソースコードに整形出力して、 terminfo-entry.cpp に追加して利用します。 出力部分のソースコードは省略します。